摘要
针对传统启发式算法难以平衡求解收敛次数与求解精度问题,通过充分分析GA和ACO两种算法的优缺点,设计了一种改进的遗传蚁群算法。将算法分为上下两步,分别以GA和ACO为主。在GA中引入信息素更新机制连接上下两部分算法;在ACO中引入遗传变异操作尽可能扩大解的范围。同时结合两种算法各自解的继承方式,采用合适的方法分别处理这两部分产生的不可行解。获得解后,通过引入交换邻域的爬山法思想进一步尝试优化解。最终在保证求解精度的前提下,减少求解所需的迭代次数。实验结果表明,在需要保证求解精度的前提下,相比传统GA,该方法的求解效率提高了一个量级。
Aiming at the problem that traditional heuristic algorithm is difficult to balance the solution of convergence times and solution precision,we design an modified genetic and ant colony hybrid algorithm by analyzing the advantages and disadvantages between GA and ACO algorithms.The algorithm is divided into two steps which are based on GA and ACO respectively.The pheromone update method is introduced in the step based on GA to connect with the next step.Meanwhile,mutation operation and crossover operation are introduced in the step based on ACO for getting more solutions.Besides,the appropriate method is used to deal with the infeasible solutions generated in these two steps.Finally,in order to optimize the solution further,hill-climbing algorithm of exchange neighborhood search is introduced after the solution is obtained.Finally,under the premise of ensuring the accuracy of the solution,the number of iterations required for the solution is shortened.The experimental results show that the efficiency of the proposed method is increased by an order of magnitude compared with the traditional GA under the premise of ensuring the accuracy of the solution.
作者
余典
吴勇
余山
YU Dian;WU Yong;YU Shan(China Academy of Telecommunication Technology,Beijing 100083,China;Semiconductor Manufacturing International Corporation(Beijing),Beijing 100176,China)
出处
《软件导刊》
2020年第3期87-90,共4页
Software Guide
关键词
0/1多维背包
遗传蚁群混合算法
交换邻域爬山算法
multidimensional knapsack problem
genetic ant colony hybrid algorithm
hill-climbing algorithm of exchange neighborhood search
