| 改进遗传—蚁群算法求解多维0/1背包问题 |
| |
| 引用本文： | 余 典,吴 勇,余 山.改进遗传—蚁群算法求解多维0/1背包问题[J].教育技术导刊,2020,19(3):87-90. |
| |
| 作者姓名： | 余 典 吴 勇 余 山 |
| |
| 作者单位： | 1. 电信科学技术研究院，北京 100083；2. 中芯国际集成电路制造（北京）有限公司，北京 100176 |
| |
| 摘 要： | 针对传统启发式算法难以平衡求解收敛次数与求解精度问题，通过充分分析GA和ACO两种算法的优缺点，设计了一种改进的遗传蚁群算法。将算法分为上下两步，分别以GA和ACO为主。在GA中引入信息素更新机制连接上下两部分算法|在ACO中引入遗传变异操作尽可能扩大解的范围。同时结合两种算法各自解的继承方式，采用合适的方法分别处理这两部分产生的不可行解。获得解后，通过引入交换邻域的爬山法思想进一步尝试优化解。最终在保证求解精度的前提下，减少求解所需的迭代次数。实验结果表明，在需要保证求解精度的前提下，相比传统GA，该方法的求解效率提高了一个量级。
|
| 关 键 词： | 0/1多维背包 遗传蚁群混合算法 交换邻域爬山算法 |
| 收稿时间： | 2019-04-24 |
Modified Genetic Ant Colony Hybrid Algorithm for Solving Multidimensional 0-1 Knapsack Problem |
| |
| YU Dian,WU Yong,YU Shan.Modified Genetic Ant Colony Hybrid Algorithm for Solving Multidimensional 0-1 Knapsack Problem[J].Introduction of Educational Technology,2020,19(3):87-90. |
| |
| Authors: | YU Dian WU Yong YU Shan |
| |
| Institution: | 1. China Academy of Telecommunication Technology，Beijing 100083，China| 2. Semiconductor Manufacturing International Corporation （Beijing），Beijing 100176，China |
| |
| Abstract: | 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. |
| |
| Keywords: | multidimensional knapsack problem genetic ant colony hybrid algorithm hill-climbing algorithm of exchange neighborhood search |
|
| 点击此处可从《教育技术导刊》浏览原始摘要信息 |
| 点击此处可从《教育技术导刊》下载免费的PDF全文 |
