基于信息素扩散模型解耦控制策略的蚁群算法

蚁群优化是一种元启发式的随机搜索技术．信息素是蚁群进行交流并实现群集智能的媒介，所以信息素的更新策略一直是蚁群算法中的一个研究热点．针对信息素扩散的耦合特征，提出一种基于信息素扩散模型解耦控制策略的蚁群算法．对信息素扩散模型进行改善，建立以蚂蚁经过的路径（直线段）为信源的信息素扩散模型，通过分析信息素扩散浓度场的耦合性，引入去耦控制策略来修正信息素的更新公式，大量TSP（traveling salesman problem）问题的实验表明：该算法不仅能获得更好的解，而且能加快算法的收敛速度．     

基于变异和信息素扩散的多维背包问题的蚁群算法

针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.     

蚁群算法中信息素增量和扩散模型的研究

文章提出一种新的基于信息素增量和扩散模型的蚁群算法。首先,基于能量守恒与转换定律对信息素的增量模型进行修正,以体现蚂蚁在不同路径上行走时所产生的信息量差异;其次,以蚂蚁经过的路径(直线段)作为信息素扩散浓度场的信源,改善了信息素扩散模型,强化了蚂蚁间的协作和交流。大量TSP(Traveling Salesman Problem)问题的实验表明:该算法不仅能获得更好的解,而且能加快算法的收敛速度。     

基于信息素扩散机制的双种群蚁群优化算法

针对基本双种群蚁群算法在进化中容易出现早熟、停滞的现象,对算法进行了改进.在双种群蚁群分别独立进化、定期进行信息交换的基础上,提出一种新的蚁群优化算法,通过建立信息素扩散模型,并在每种蚁群的局部信息素更新上采用扩散模型,使蚂蚁更好的发挥了协作能力.以旅行商(Travel Salesman Problem,TSP)问题为例的仿真实验表明,该算法比基本双种群蚁群算法具有更好的收敛速度和寻优能力.     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

精英扩散蚁群优化算法求解运输无人机三维路径规划

针对受灾山区运输物资的三维无人机路径规划问题,提出了一种精英扩散蚁群优化算法EDACO,首先通过极值限定策略限定了信息素浓度的范围,防止算法前期陷入局部最优;然后采用精英策略改进信息素浓度更新公式,加强优质个体对种群的影响力; 再引入信息素扩散策略,加强距离较近个体间的交流协作,以防止蚂蚁个体间联系不紧密造成的算法停滞。最后,将精英扩散蚁群优化算法、传统蚁群算法、遗传算法和萤火虫算法运用于4个山区受灾无人机运输实例中,结果表明了EDACO的优越性和有效性,且该算法对无人机三维路径规划问题有着良好的适应性。     

基于改进蚁群算法的机器人路径规划算法

针对机器人路径规划中,传统蚁群算法收敛速度慢、易陷入局部最优解等问题,提出了一种移动机器人路径规划的改进蚁群优化(ACO)算法。用栅格法建立环境模型,并基于人工势场建立启发信息素矩阵,降低了蚂蚁在初始阶段搜索的盲目性;引入激励函数,降低搜索过程中的死锁现象;改进信息素的更新机制,增强了优秀蚂蚁对全局路径规划的影响。仿真结果表明:改进后蚁群算法的机器人路径规划算法加快了收敛速度,具有较强的鲁棒性和全局寻优能力。     

基于信息素扩散的优化蚁群算法的研究

在蚁群算法实验性分析的基础上,对算法模型改进和信息素更新机制方面,首次引入了信息素扩散的概念,在信息素更新的时候更好地考虑了先前经过的节点,以尽力避免不必要的无用搜索,同时基于信息素扩散的蚁群算法具有不断获得新的最优解的能力,使得改进蚁群算法在不断的迭代过程后,可获得全局最优解,而不易陷入局部最优解.在解决实际旅行商问题时,首先对所有节点的坐标预处理,然后采取信息素扩散机制和蚂蚁泛滥技术来对蚁群算法进行改进,力求在相同的迭代次数内可以寻找到更短及代价更小的路径.最后,通过在vc++环境下实现改进蚁群算法程序,验证了改进后的蚁群算法的可行性以及改进后的蚁群算法求解的高效性.     

连续域蚁群算法在扩散工艺路线优选中的应用

针对工艺快速扩散系统中的扩散工艺路线决策问题,提出了扩散工艺路线优选模型.该模型以成本和时间为约束,结合了工艺快速扩散系统中工艺单一性的特点,构建了改进的连续域蚁群算法.该算法提出了最小路径蚂蚁信息素的局部更新,加快了收敛速度,能够快速解决扩散工艺路线优选问题.最后以一个实例验证了该算法的实用性.     

基于自适应机制改进蚁群算法的移动机器人全局路径规划

针对基本蚁群算法在二维静态栅格地图下进行移动机器人路径规划时出现的搜索效率低下、收敛速度缓慢、局部最优解等问题,提出一种自适应机制改进蚁群算法,用于移动机器人在二维栅格地图下的路径规划.首先采用伪随机状态转移规则进行路径选择,定义一种动态选择因子以自适应更新选择比例,引入距离参数计算转移概率,提高算法的全局搜索能力以及搜索效率;然后基于最大最小蚂蚁模型和精英蚂蚁模型,提出一种奖励惩罚机制更新信息素增量,提高算法收敛速度;最后定义一种信息素自适应挥发因子,限制信息素浓度的上下限,提高算法全局性的同时提高算法的收敛速度.在不同规格的二维静态栅格地图下进行移动机器人全局路径规划对比实验,实验结果表明自适应机制改进蚁群算法具有较快的收敛速度,搜索效率明显提高且具有较好的全局搜索能力,验证了所提算法的实用性和优越性.     

基于多粒度的旅行商问题描述及其蚁群优化算法

针对蚁群算法在求解大规模旅行商问题(Traveling Salesman Problems,TSP)中时间性能方面的不足,提出了一种快速的求解算法.首先,从TSP问题描述入手,给出了一种新的多粒度的问题描述模型;然后,基于该模型,设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度间可行解的合成以及循环分段优化6个阶段在内的求解算法.算法的复杂度分析及在中、大规模TSP问题上的实验表明:本算法的时间性能不仅比经典的蚁群算法有显著的提高,而且与近年来的一些同类算法相比也具有一定的优势,显示了快速求解大规模TSP问题的能力.     

多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.     

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

Ant colony optimization (ACO) has been successfully applied for combinatorial optimization problems, e.g., the travelling salesman problem (TSP), under stationary environments. In this paper, we consider the dynamic TSP (DTSP), where cities are replaced by new ones during the execution of the algorithm. Under such environments, traditional ACO algorithms face a serious challenge: once they converge, they cannot adapt efficiently to environmental changes. To improve the performance of ACO on the DTSP, we investigate a hybridized ACO with local search (LS), called Memetic ACO (M-ACO) algorithm, which is based on the population-based ACO (P-ACO) framework and an adaptive inver-over operator, to solve the DTSP. Moreover, to address premature convergence, we introduce random immigrants to the population of M-ACO when identical ants are stored. The simulation experiments on a series of dynamic environments generated from a set of benchmark TSP instances show that LS is beneficial for ACO algorithms when applied on the DTSP, since it achieves better performance than other traditional ACO and P-ACO algorithms.     

Multi-satellite control resource scheduling based on ant colony optimization

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP–ACO) is presented in this paper. The main idea of MSCRSP–ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (CISM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP–ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP–ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max–min ant system.     

Modeling the dynamics of ant colony optimization

The dynamics of Ant Colony Optimization (ACO) algorithms is studied using a deterministic model that assumes an average expected behavior of the algorithms. The ACO optimization metaheuristic is an iterative approach, where in every iteration, artificial ants construct solutions randomly but guided by pheromone information stemming from former ants that found good solutions. The behavior of ACO algorithms and the ACO model are analyzed for certain types of permutation problems. It is shown analytically that the decisions of an ant are influenced in an intriguing way by the use of the pheromone information and the properties of the pheromone matrix. This explains why ACO algorithms can show a complex dynamic behavior even when there is only one ant per iteration and no competition occurs. The ACO model is used to describe the algorithm behavior as a combination of situations with different degrees of competition between the ants. This helps to better understand the dynamics of the algorithm when there are several ants per iteration as is always the case when using ACO algorithms for optimization. Simulations are done to compare the behavior of the ACO model with the ACO algorithm. Results show that the deterministic model describes essential features of the dynamics of ACO algorithms quite accurately, while other aspects of the algorithms behavior cannot be found in the model.     

Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays

Ant Colony Optimization (ACO) is a metaheuristic used to solve combinatorial optimization problems. As with other metaheuristics, like evolutionary methods, ACO algorithms often show good optimization behavior but are slow when compared to classical heuristics. Hence, there is a need to find fast implementations for ACO algorithms. In order to allow a fast parallel implementation, we propose several changes to a standard form of ACO algorithms. The main new features are the non-generational approach and the use of a threshold based decision function for the ants. We show that the new algorithm has a good optimization behavior and also allows a fast implementation on reconfigurable processor arrays. This is the first implementation of the ACO approach on a reconfigurable architecture. The running time of the algorithm is quasi-linear in the problem size n and the number of ants on a reconfigurable mesh with n ² processors, each provided with only a constant number of memory words.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

Search bias in ant colony optimization: on the role of competition-balanced systems

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.     

An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis

Clustering is a popular data analysis and data mining technique. A popular technique for clustering is based on k-means such that the data is partitioned into K clusters. However, the k-means algorithm highly depends on the initial state and converges to local optimum solution. This paper presents a new hybrid evolutionary algorithm to solve nonlinear partitional clustering problem. The proposed hybrid evolutionary algorithm is the combination of FAPSO (fuzzy adaptive particle swarm optimization), ACO (ant colony optimization) and k-means algorithms, called FAPSO-ACO–K, which can find better cluster partition. The performance of the proposed algorithm is evaluated through several benchmark data sets. The simulation results show that the performance of the proposed algorithm is better than other algorithms such as PSO, ACO, simulated annealing (SA), combination of PSO and SA (PSO–SA), combination of ACO and SA (ACO–SA), combination of PSO and ACO (PSO–ACO), genetic algorithm (GA), Tabu search (TS), honey bee mating optimization (HBMO) and k-means for partitional clustering problem.