并行蚁群算法中的自适应交流策略

提出了并行蚁群算法中处理机间信息交流的两种策略,使得各处理机能够自适应地选择其他处理机以进行信息交换和相应信息素的全局更新.还提出了一种确定处理机之间进行信息交流的时间的策略,可以根据解的分布情况自适应地确定信息交流的时间,以取得全局收敛速度和解的多样性之间的平衡.在算法每一次信息交换后,采用自适应的更新策略,根据信息素的均匀度进行信息素的更新,从而避免了早熟和局部收敛.在MPP处理机曙光2000上对TSP问题的实验结果,表明了基于该自适应信息交换策略的并行蚁群算法比其他算法具有更好的收敛性、更高的加速比     

蚁群算法与免疫算法的融合及其在TSP中的应用

提出一种基于抗体片段局部最优搜索的克隆选择和蚁群自适应融合算法.引入混沌扰动来增加抗体种群的多样性,以提高蚁群算法的搜索能力;利用克隆扩增、免疫基因等相关算子的操作,增强了克隆选择算法搜索的效率;通过自适应控制参数,实现了克隆选择与蚁群优化的有机结合及局部最优搜索策略的应用,加快了收敛速度,克服了抗体种群早熟问题,提高了求解精度.仿真实验结果表明,该算法具有可靠的全局收敛性,较快的收敛速度.     

用自适应的多种群蚁群算法求解频率分配问题

提出一种自适应的多种群蚁群算法求解移动通信中的频率分配问题。该算法改变了传统蚁群算法只有一个蚂蚁群体的做法,使用多个蚂蚁子群体同时进行优化处理。为每个蚂蚁子群体定义一个收敛系数,根据收敛系数来决定子群体内部的路径选择和信息量更新、子群体间的信息交流策略,同时采用自适应的信息更新策略以取得各蚂蚁子群体中解的多样性和收敛性之间的动态平衡。通过对固定频率分配和最小跨度频率分配问题进行仿真的实验,表明此算法不仅具有较强的全局收敛性,而且有更快的寻优速度。     

基于优化成熟度的自适应蚁群优化算法

分析了蚁群算法局部信息素更新系数与全局信息素更新系数对算法寻优能力与收敛速度的关系,定义平均路径相似度(ATS)来表征寻优过程的成熟程度,并据此自适应调整信息素更新系数,提高算法收敛速度并避免陷入局部最优.经过与典型蚁群算法在多个旅行商问题测试用例上进行比较,表明该算法效果更好.     

动态分阶段蚁群算法及其收敛性分析

为了提高蚁群算法的收敛速度和求解精度，根据仿生优化算法在不同阶段的特点，提出一种改进的蚁群算法．该算法对参数和选择策略进行了分阶段设计，而且参数的分阶段是根据寻优状态动态划分的．通过对蚁群系统马尔科夫过程进行分析，证明了该算法的全局收敛性．针对典型的TSP问题进行仿真对比实验，验证了该算法在速度和精度方面优于传统蚁群算法．     

基于自适应蚁群算法的救援直升机航迹规划

基本蚁群算法在航迹规划的应用中缺乏足够的鲁棒性,存在收敛性能较差的问题,针对基本蚁群算法容易出现局部停滞的现象,提出了一种自适应蚁群算法的救援直升机航迹规划方法,建立了救援距离最短和救援效率最高的数学模型.为了保持搜索的平衡性和收敛性,自适应蚁群算法从信息素挥发系数和信息索强度两个方面动态地调整信息素,并根据救援目标的紧急程度对信息素参数化.仿真结果表明,改进的蚁群算法避免了出现局部最优,有效地提高了搜索收敛速度.     

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

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

基于信息素负反馈的超启发式蚁群优化算法

针对蚁群算法应用于自动导引小车路径规划收敛速度慢、极易陷入局部最优的缺点，提出一种基于信息素负反馈的超启发式蚁群优化（ACONhh）算法。该算法充分利用历史搜索信息和持续获得错误经验，较快引导蚁群探索最优路径；分层化选择可行节点，加快算法初期收敛速度；设置挥发因子呈类抛物线变化以及调整信息素更新机制，改善路径全局的随机搜索特性。通过严格的数学方式证明了ACONhh算法具有收敛性。仿真和实验结果表明，该算法的收敛速度以及全局搜索性能显著优于目前流行的ACO、ACOhh和ACOihh算法。     

动态调整路径选择的蚁群优化算法

针对蚁群算法收敛速度慢和存在停滞现象的缺点,提出对比度增强的路径选择规则以增强其全局搜索能力,选择规则加强了对反馈信息的利用,能加快算法的收敛速度,通过信息熵来动态控制对比度增强的方向,在避免算法停滞的同时加快了算法的收敛速度。将改进后的蚁群优化算法与传统的蚁群优化算法进行比较,仿真实验结果表明,改进算法具有较好的稳定性和全局优化性能,且收敛速度较快。     

改进的遗传混合蚁群算法在TSP问题中的应用

为了提高基本蚁群算法的收敛性能和全局求解能力,对基本蚁群算法进行了改进,提出了一种改进的遗传混合蚁群算法。在每代进化中保留最优解和次优解的公共解集后引入遗传操作中的交叉算子进行运算,并采用自适应改变信息素挥发系数的方法,加快了算法收敛速度,提高了解的全局性。通过对TSP问题的仿真运算表明,改进的遗传混合蚁群算法在收敛速度和解的全局性上都有较大的改善。     

On Enforced Convergence of ACO and its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks

In this paper we show that size reduction tasks can be used for executing iterative randomized metaheuristics on runtime reconfigurable architectures so that an improved throughput and better solution qualities are obtained compared to conventional architectures that do not allow runtime reconfiguration. In particular, the problem of executing ant colony optimization (ACO) algorithms on a dynamically reconfigurable mesh architecture is studied. It is shown how ACO can be implemented such that the convergence behavior of the algorithm can be used to dynamically reduce the size of the submesh that is needed for execution. Furthermore we propose a method to enforce the convergence of ACO leading to a faster reduction process. This increases the throughput of ACO algorithms on runtime reconfigurable meshes. The increased throughput is used for repeated runs of ACO algorithms on a given set of problem instances which significantly improves the obtained solution quality.     

A review of ant algorithms

Ant algorithms are optimisation algorithms inspired by the foraging behaviour of real ants in the wild. Introduced in the early 1990s, ant algorithms aim at finding approximate solutions to optimisation problems through the use of artificial ants and their indirect communication via synthetic pheromones. The first ant algorithms and their development into the Ant Colony Optimisation (ACO) metaheuristic is described herein. An overview of past and present typical applications as well as more specialised and novel applications is given. The use of ant algorithms alongside more traditional machine learning techniques to produce robust, hybrid, optimisation algorithms is addressed, with a look towards future developments in this area of study.     

基于AQ覆盖框架的蚁群规则集学习算法

针对规则集学习问题,提出一种遵循典型AQ覆盖算法框架（AQ Covering Algorithm）的蚁群规则集学习算法（Ant-AQ）。在Ant-AQ算法中,AQ覆盖框架中的柱状搜索特化过程被蚁群搜索特化过程替代,从某种程度上减少了陷入局优的情况。在对照测试中,Ant-AQ算法分别和已有的经典规则集学习算法（CN2、AQ-15）以及R.S.Parpinelli等提出的另一种基于蚁群优化的规则学习算法 Ant-Miner在若干典型规则学习问题数据集上进行了比较。实验结果表明：首先,Ant-AQ算法在总体性能比较上要优于经典规则学习算法,其次,Ant-AQ算法在预测准确度这样关键的评价指标上优于Ant-Miner算法。     

PREACO: A fast ant colony optimization for codebook generation

This paper presents an effective and efficient method for speeding up ant colony optimization (ACO) in solving the codebook generation problem. The proposed method is inspired by the fact that many computations during the convergence process of ant-based algorithms are essentially redundant and thus can be eliminated to boost their convergence speed, especially for large and complex problems. To evaluate the performance of the proposed method, we compare it with several state-of-the-art metaheuristic algorithms. Our simulation results indicate that the proposed method can significantly reduce the computation time of ACO-based algorithms evaluated in this paper while at the same time providing results that match or outperform those ACO by itself can provide.     

基于K-均值改进蚁群优化的彩色图像边缘检测算法

为提高图像边缘检测的精度,提出一种基于K-均值改进蚁群优化（ACO）的彩色图像边缘检测算法。将聚类嵌入到边缘检测中,使这2类图像分割方法有效结合,增强了2类方法的优势。实验结果表明,该算法有效解决了传统蚁群算法（ACO）收敛较慢的问题,较好地保留了图像边缘细节,降低了计算复杂度,与典型分割方法相比具有更好的性能。     

On the Invariance of Ant Colony Optimization

Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the issue of the invariance of ACO algorithms to transformation of units. They state (Blum and Dorigo, 2004) that the performance of ACO depends on the scale of the problem instance under analysis. In this paper, we show that the ACO internal state - commonly referred to as the pheromone - indeed depends on the scale of the problem at hand. Nonetheless, we formally prove that this does not affect the sequence of solutions produced by the three most widely adopted algorithms belonging to the ACO family: ant system, MAX-MIN ant system, and ant colony system. For these algorithms, the sequence of solutions does not depend on the scale of the problem instance under analysis. Moreover, we introduce three new ACO algorithms, the internal state of which is independent of the scale of the problem instance considered. These algorithms are obtained as minor variations of ant system, MAX-MIN ant system, and ant colony system. We formally show that these algorithms are functionally equivalent to their original counterparts. That is, for any given instance, these algorithms produce the same sequence of solutions as the original ones.     

基于选路优化的改进蚁群算法

蚁群算法在处理大规模优化问题时效率很低。为此对蚁群算法提出了基于选路优化的两点改进:(1)引入选路优化策略,减少了算法中蚁群的选路次数,显著提高了算法的执行效率。(2)在选路操作中,只根据当前城市的前C个距离最近的且未经过城市为候选城市计算选择概率,从而减少单个蚂蚁选路的计算量。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度有明显提高。     

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.     

蚁群算法的优化及在TSP问题上的应用

蚁群算法是一种模仿真实蚂蚁群集体行为的全局启发式随机搜索算法,目前蚁群算法存在易陷入局部最优、搜索时间长等问题。提出一种改进的蚁群算法,加入扰动策略、挥发因子动态调整策略以避免算法陷入局部最优值,采用奖励策略提高搜索效率。通过在旅行商问题上验证得知,改进后的算法可以获得已知最优值,与最大最小蚁群算法相比,解的平均值、出现最优值的概率都有提高。     

蚁群算法的优化及在TSP问题上的应用

蚁群算法是一种模仿真实蚂蚁群集体行为的全局启发式随机搜索算法．目前蚁群算法存在易陷入局部最优、搜索时间长等问题。提出一种改进的蚁群算法,加入扰动策略、挥发因子动态调整策略以避免算法陷入局部最优值．采用奖励策略提高搜索效率。通过在旅行商问题上验证得知,改进后的算法可以获得已知最优值,与最大最小蚁群算法相比,解的平均值、出现最优值的概率都有提高。