计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (36): 46-49.

• 研究、探讨 • 上一篇    下一篇

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

钟海萍,张培爱,张京友,余隆鹰   

  1. 暨南大学 信息科学技术学院 数学系,广州 510632
  • 出版日期:2012-12-21 发布日期:2012-12-21

Combination of Primal-Dual Genetic Algorithm and ant algorithm

ZHONG Haiping, ZHANG Pei’ai, ZHANG Jingyou, YU Longying   

  1. Department of Mathematics, School of Information Science & Technology, Jinan University, Guangzhou 510632, China
  • Online:2012-12-21 Published:2012-12-21

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

关键词: 原对偶遗传算法, 遗传算法, 蚁群算法, 融合

Abstract: Primal-Dual Genetic Algorithm(PDGA) has higher ability of global searching quickly and stochastically. It improves the searching ability in the searching space. But it can’t make full use of system feedback information such that it iterates redundantly and its efficiency is reduced. Meanwhile, Ant Colony Optimization converges to the optimization path by information pheromone accumulation and renewal. It has the ability of parallel processing and global searching. Since there is little information pheromone on the path at the beginning, the speed of the Ant Colony Optimization is slowed down. A combination algorithm of PDGA and Ant Colony Optimization is put forward. It utilizes the advantages of the two algorithms and overcomes their disadvantages. It is heuristic, and performs better in converging and more efficient. Experimental results from the simulation of the algorithm show that the algorithm excels genetic algorithm, Primal-Dual Genetic Algorithm and ant colony optimization in performance.

Key words: Primal-Dual Genetic Algorithm(PDGA), genetic algorithm, ant colony optimization, combination