【作者】 朱亨荣；

【导师】 刘伟铭；

【作者基本信息】 长沙理工大学 ， 计算机应用技术， 2005， 硕士

【摘要】 本文对传统的蚂蚁算法和遗传算法进行了研究和改进,并将两者有机结合,提出了一种新型的蚂蚁遗传算法。该算法有效地利用了蚂蚁算法的正反馈特性和遗传算法的全局收敛特性,能快速有效地搜索最优解。将该算法应用到经典的旅行商问题,并通过MATLAB 仿真实现,并与经典算法进行比较分析,结果表明了算法的可行性和有效性。论文的主要工作如下: 一、对标准蚂蚁算法进行了改进。在蚂蚁算法中添加了三条假设,蚂蚁能通过触角实时交流进而决定下一步选择。在触角实时交流中采用了长期记忆和短期记忆的假设,从而提出可变挥发度来影响局部信息素和全局信息素的更新。二、对标准遗传算法进行了改进。对具体问题采用不同的编码方式来优化数据结构;通过修改适应度函数来减少计算量;提出了置顶增强因子来加速收敛;提出了动态自适应方案来控制自然选择以防止早熟。三、提出了一种新的蚂蚁遗传算法。首先,采用遗传算法求得初始路径种群;其次,通过全局信息素更新策略将其转化为蚂蚁算法的初始信息素矩阵,从而加速蚂蚁算法的收敛速度;最后,为了防止陷入局部最优解,用蚂蚁算法求得新的路径来更新遗传算法的种群。四、应用于旅行商问题。对蚂蚁遗传算法、标准遗传算法、改进遗传算法、标准蚂蚁算法、改进蚂蚁算法这五种进化算法进行了仿真实验。结果表明蚂蚁遗传算法的收敛率更高,表明具有更好的全局收敛性能,蚂蚁遗传算法在更少的迭代次数达到全局最优解,具有更高的收敛速度。更多还原

【Abstract】 Some upswings have been done based on the research about the traditional genetic algorithm and ant optimization algorithm. A new hybrid algorithm GAACO is brought forward in this thesis, which combines the ant colony optimization’s positive character and genetic algorithm’s global convergence for faster and better search capability. The algorithm is applied to the classic traveling salesman problem. Compared to the classic algorithm through the tool of MATLAB, the result shows that the feasibility and validity of the algorithm. The main research work in this paper is as follows. 1. Improve on the standard colony optimization algorithm. Three hypothesizes is added on the standard ACO. Ants can communicate with their antenna when they meet on the routine, which can be used to judge the next step. During the communication, the long-term memory and short-term memory is taken effected on the pheromone’s global and local updating strategy. 2. Improve on the genetic algorithm. Different problems should adopt different coding scheme in order to optimize the data structure. The adaptation function is modified in order to decrease the computation. The top strengthening factor is given as to speed the convergence. The dynamic adaptation scheme is used to avoid the algorithm prematurely. 3. Put forward a new hybrid algorithm GAACO. Firstly, adopt the genetic algorithm to initial the population. Secondly, convert the population into the original pheromone matrix in order to speeding the convergence. Thirdly, use the routine of ant colony optimization algorithm to update the population of genetic algorithm. 4. Apply to traveling salesman problem. In this paper, the algorithms are compared with emulation. The result shows that the GAACO is better than any other of standard GA, improved GA, standard ACO, and improved ACO. The result shows that the GAACO has higher convergence probability and global convergence capability. It can reach the global optimal value fast within fewer iteration times.更多还原