基于新型信息素更新策略的蚁群算法*

深入研究了蚁群优化算法（ACO）的路径搜索及参数控制策略,分析了其存在的缺陷。为了提高ACO算法的解题能力,提出一种新型信息素更新策略（PACS）,然后将PACS算法与其他蚁群算法分别应用于旅行商问题（TSP）进行仿真实验。仿真结果表明,PACS算法具有优良的全局优化性能,可抑制算法过早收敛于次优解,有效防止了停滞现象,收敛速度也大大加快。     

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

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

结合头脑风暴优化的混合蚁群优化算法

特征选择能够有效提升数据分类的性能。为了进一步提升蚁群优化（ACO）在特征选择上的求解能力,提出一种结合头脑风暴优化的混合蚁群优化（ABO）算法。该算法利用信息交流档案维护历史较好解,并通过基于松弛因子的时间最久优先方法动态更新档案。当ACO的全局最优解多次未更新时,采用基于Fuch混沌映射方法的路径-想法转换算子将档案中的路径解转换为想法解,并将其作为初始种群,通过头脑风暴优化（BSO）在更广阔的空间中搜索较好解。对所提算法在6组典型的二分类数据集上进行实验,分析了其参数敏感性,并与混合萤火虫粒子群优化（HFPSO）算法、粒子群优化与引力搜索算法（PSOGSA）以及遗传算法（GA） 这三种典型的演化算法进行对比。实验结果表明,相较于对比算法,所提算法在分类正确率上至少可提高2.88%~5.35%,在F1指标上至少可提高0.02~0.05,验证了所提算法的有效性和优越性。     

针对混合变量优化问题的协同进化蚁群优化算法

针对由连续变量和分类变量构成的混合变量优化问题（MVOP）,采用协同进化策略来对混合变量决策空间进行搜索,提出了一种协同进化蚁群优化算法（CACOA_MV）。CACOA_MV分别采用连续和离散蚁群优化（ACO）策略生成连续和分类变量子种群,通过合作者来对连续和分类变量子向量进行评价,分别对连续和分类变量子种群进行更新来实现对混合变量决策空间的高效协同搜索。进一步地,利用信息素平滑机制增强对分类变量解空间的全局探索能力,并设计了一种面向协同进化框架的“最佳+随机合作者”的重启策略来提高协同搜索效率。与混合变量的蚁群（ACO_MV）算法和种群规模线性变小的差分进化-蚁群混合变量优化算法（L-SHADE_ACO）的比较表明,CACOA_MV能够进行更有效的局部开发,从而提高最终结果在目标空间中的近似精度;与基于集合的混合变量差分进化算法（DE_MV）相比较,CACOA_MV能够在决策空间中更好地逼近全局最优解,具有更好的全局探索能力。综上,采用协同进化机制的CACOA_MV能有效保持全局探索和局部开发的平衡,从而具有更好的寻优性能。     

基于群智能的连续优化算法研究

在对蚁群优化算法(ACO)和粒子群优化算法(PSO)进行分析的基础上,提出一种解决函数连续优化的群智能混合策略-CA-PSO.在求解过程中,首先对解空间进行区域划分,进而利用ACO在优化初期具备的快速收敛性能,在整个解空间内搜索最优解的敏感区域.然后利用蚁群的搜索结果初始化PSO粒子,利用PSO快速和全局收敛性进行所在小区域内的搜索.种群更新时根据蚁群的拓扑结构和小区域间的阶跃规则,蚁群不断向最优解敏感区域聚集,使得敏感区域内粒子数增加,则局部的PSO搜索策略可以更细密的搜索最优.实例结果表明,CA-PSO既能保证解的分布性与多样性,又避免了在多峰值函数寻优过程中陷入局部最优解而停止运算,最终将收敛到全局最优解.     

基于滑动窗口和蚁群优化算法的二次路径规划算法

针对蚁群优化(ACO)算法在复杂环境下规划能力较弱的问题,提出了一种基于滑动窗口和蚁群优化算法的二次路径规划(QACO)算法.对回退蚁群优化(ACOFS)算法的回退策略进行改进,通过降低回退路径上的信息素量,减少回退次数.第一次规划中,使用改进后的ACO算法对栅格环境进行全局路径规划;第二次规划中,滑动窗口沿着全局路径滑动,通过ACO算法规划出滑动窗口中的局部路径,并使用局部路径对全局路径进行优化,直至滑动窗口中包含目标位置.仿真实验表明:相比ACO、ACOFS算法,QACO算法的平均规划时间分别下降了26.21%、52.03%,平均路径长度下降了47.82%、42.28%,因此在复杂环境下QACO算法具有将强的路径规划能力.     

求解Job Shop调度问题的混合蚁群算法研究

为了解决单一算法求解Job Shop调度问题存在的不足，该文提出了一种混合算法，将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况，提出了一种基于关键工序的邻域搜索方法，将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力，提高了蚁群算法的优化能力，达到改善Job Shop调度问题解的质量。实验结果表明，混合算法在较短的时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。     

基于多蚁群的并行ACO算法

通过改变蚁群优化(ACO)算法行为,提出一种新的ACO并行化策略——并行多蚁群ACO算法。针对蚁群算法存在停滞现象的缺点,改进选择策略,实现具有自适应并行机制的选择和搜索策略,以加强其全局搜索能力。并行处理采用数据并行的手段,能减少处理器间的通信时间并获得更好的解。以对称TSP测试集为对象进行比较实验,结果表明,该算法相对于串行算法及现有的并行算法具有一定的优势。     

基于视觉抓取的并联桁架机器人最优路径控制

针对元件的抓取路径规划问题,提出一种以最小化时间为目的,结合蚁群算法和禁忌搜索算法的混合优化算法。首先,将基于机器视觉抓取元件的问题确定为有约束的旅行商问题（TSP）;然后,分析了元件大小和抓取放置过程对于路径规划的综合影响,对路径选择概率和禁忌域进行了适应性改进;其次,一方面引入了2-opt局部优化以及信息素惩罚、奖励机制以改善蚂蚁的搜索能力,另一方面对信息挥发因子作适应性改进以提高蚂蚁的自适应能力;最后,针对基本算法和改进的混合优化算法,仿真实验和平台实验分别进行了性能指标和抓取时间的对比分析。实验结果表明,仿真环境下,与蚁群优化（ACO）算法和禁忌搜索（TS）算法相比,混合优化算法的平均迭代次数降低了约50%,且其他性能较为优越,平台测试的抓取用时测试结果也说明了混合优化算法较随机结果和基本算法的优越性,可以快速完成元件抓取任务。     

基于蚁群数量动态调整的改进蚁群优化算法

蚁群优化（ACO）算法是一种常用的元启发式算法，它通过模拟蚁群寻找食物的过程，为求解多维背包问题（MKP）等NP难（Non-deterministic Polynomial hard）问题提供可行途径。原始ACO算法及其改进算法，通常分为多个轮次，每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中，每轮蚁群中蚂蚁的数量是固定的，因此，如果将其指定一个较大的值，会导致算法出现不必要的时间消耗；反之，如果指定的值较小，则会降低算法全局最优解搜索能力。为此，提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA(ACO algorithm based on Ant Number Dynamic Adjustment)，所提算法在可行解搜索过程中，引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后，均根据近几轮可行解和历史最优解之间的关系，调整下一轮蚁群数量，实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明，相较于原始ACO算法，所提算法能够在最优解利润平均降低0.02%的情况下，平均降低77.85%的时间耗费。     

A survey on the Metaheuristics for Cryptanalysis of Substitution and Transposition Ciphers

This paper presents state-of-art cryptanalysis studies on attacks of the substitution and transposition ciphers using various metaheuristic algorithms. Traditional cryptanalysis methods employ an exhaustive search, which is computationally expensive. Therefore, metaheuristics have attracted the interest of researchers in the cryptanalysis field. Metaheuristic algorithms are known for improving the search for the optimum solution and include Genetic Algorithm, Simulated Annealing, Tabu Search, Particle Swarm Optimization, Differential Evolution, Ant Colony, the Artificial Bee Colony, Cuckoo Search, and Firefly algorithms. The most important part of these various applications is deciding the fitness function to guide the search. This review presents how these algorithms have been implemented for cryptanalysis purposes. The paper highlights the results and findings of the studies and determines the gaps in the literature.     

New metaheuristic approaches for the edge-weighted k-cardinality tree problem

In this paper we propose three metaheuristic approaches, namely a Tabu Search, an Evolutionary Computation and an Ant Colony Optimization approach, for the edge-weighted k-cardinality tree (KCT) problem. This problem is an NP-hard combinatorial optimization problem that generalizes the well-known minimum weight spanning tree problem. Given an edge-weighted graph G=(V,E), it consists of finding a tree in G with exactly k⩽|V|−1 edges, such that the sum of the weights is minimal. First, we show that our new metaheuristic approaches are competitive by applying them to a set of existing benchmark instances and comparing the results to two different Tabu Search methods from the literature. The results show that these benchmark instances are not challenging enough for our metaheuristics. Therefore, we propose a diverse set of benchmark instances that are characterized by different features such as density and variance in vertex degree. We show that the performance of our metaheuristics depends on the characteristics of the tackled instance, as well as on the cardinality. For example, for low cardinalities the Ant Colony Optimization approach is best, whereas for high cardinalities the Tabu Search approach has advantages.     

联盟运输调度问题模型结构与算法研究

联盟运输调度问题是在基本运输调度问题基础上衍生出的最具现实意义的一类组合优化难题,是近年来物流控制优化领域的研究热点。依据运输调度问题分类方法,描述了联盟运输调度问题的结构;通过分析遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群算法的特点及其求解运输调度问题的现状,讨论了它们求解联盟运输调度问题的可能性;展望了联盟运输调度问题发展的前景,指出改进原算法、提出新算法、并行算法是解决联盟运输调度问题的重要手段。     

Disassembly Sequencing Using Tabu Search

End-of-life disassembly has developed into a major research area within the sustainability paradigm, resulting in the emergence of several algorithms and structures proposing heuristics techniques such as Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Neural Networks (NN). The performance of the proposed methodologies heavily depends on the accuracy and the flexibility of the algorithms to accommodate several factors such as preserving the precedence relationships during disassembly while obtaining near- optimal and optimal solutions. This paper improves a previously proposed Genetic Algorithm model for disassembly sequencing by utilizing a faster metaheuristic algorithm, Tabu search, to obtain the optimal solution. The objectives of the proposed algorithm are to minimize (1) the traveled distance by the robotic arm, (2) the number of disassembly method changes, and (3) the number of robotic arm travels by combining the identical-material components together and hence eliminating unnecessary disassembly operations. In addition to improving the quality of optimum sequence generation, a comprehensive statistical analysis comparing the previous Genetic Algorithm and the proposed Tabu Search Algorithm is also included     

一种带有摄动的导向性蚁群算法

针对加入导向性局部搜索(Guided Local Search,GLS)的蚁群算法(Ant Colony Optimization,ACO)容易过早收敛的问题,提出一种带有摄动的导向性蚁群算法(Perturbation Guided Ant Colony Optimization,PGACO),该算法在当前解表现出过早收敛的趋势时,采用摄动(Perturbation)方式干扰解构建过程,使当前解移动到其邻域空间,从而产生一个新的可行解来避免算法过早收敛,提高算法求解的精度。实验结果表明,PGACO能有效地改善过早收敛问题,获得更优的可行解和执行速度,同时具有更强的全局搜索能力,能进一步提高算法的性能。     

Size optimization of space trusses using Big Bang–Big Crunch algorithm

A Hybrid Big Bang–Big Crunch (HBB–BC) optimization algorithm is employed for optimal design of truss structures. HBB–BC is compared to Big Bang–Big Crunch (BB–BC) method and other optimization methods including Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization and Harmony Search. Numerical results demonstrate the efficiency and robustness of the HBB–BC method compared to other heuristic algorithms.     

原对偶遗传与蚁群算法的融合

原对偶遗传算法(PDGA)较好地保持了种群的多样性和较强的稳定性,改善了在搜索空间里的搜索能力,使搜索更为有效,但没有利用系统中的反馈信息,导致无为的冗余迭代,求解效率不高。而蚁群算法是通过信息素的累积和更新来收敛于最优路径,具有分布、并行、全局收敛能力,但是搜索初期信息素匮乏,导致算法速度慢。通过将两种算法进行融合,克服两种算法各自的缺陷,优势互补,形成一种全局寻优性能好,稳定性强,效率高的启发式算法,通过仿真计算,表明融合算法的性能优于遗传算法,原对偶遗传算法和蚁群算法。