【作者】 覃锦华；

【导师】 王宇平；

【作者基本信息】 西安电子科技大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 进化算法是人们从大自然的生物进化过程所得到的灵感中发展起来的一种现代优化方法,它作为一种新型的、模拟生物进化过程的随机化搜索、优化方法,具有全局优化,隐并行性,鲁棒性强,操作简单等特点,近十几年来在组合优化领域得到了相当广泛的应用,并已在解决诸多典型的组合优化问题(如旅行商问题)中显示了良好的性能和效果。首先,针对一类特殊的大规模旅行商问题,比如说城市可以分为若干组、而且各组内城市之间的距离较小的问题,本文提出了一种基于聚类以及局部搜索技术的新进化策略来进行求解,并且证明了该算法的全局收敛性。其次,针对对称型的旅行商问题,本文设计了一个新的进化算法进行求解,该算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解的质量,同时被证明是全局收敛的。最后,数值模拟实验结果表明,本文所提出的这两个算法都是有效的。更多还原

【Abstract】 Evolutionary algorithms are new kinds of modern optimization algorithms which are inspired by the principle of nature evolution. As new kinds of random search algorithms, they have some advantages such as global search ability, implicit parallelism, robustness, simple operation and so on. In the recent decades, evolutionary algorithms have a wide range of applications in the area of combinatorial optimization. They have been used to solve many classical combinatorial optimization problems (e.g. Traveling Salesman Problem) and show their good performance and effectiveness.Firstly, a new evolution strategy based on clustering and local search scheme is proposed for some kind of large-scale traveling salesman problems in which the cities can be classified into several groups and in each group the cities crowd together. This algorithm is then proved to converge to the global optimal solution with probability 1.Secondly, a new evolutionary algorithm is proposed to deal with the symmetric traveling salesman problems. In this new algorithm, a new crossover operator and a new mutation operator are designed to generate offspring. Then a local search scheme is used to improve the solutions. Also, the global convergence with probability 1 of the proposed algorithm is proved.Finally, the simulation results show the effectiveness of the two proposed algorithms.更多还原