基于遗传算法的组合优化问题的研究

基于遗传算法的组合优化问题的研究(论文14000字)
摘要：一直以来，遗传算法作为一种智能信息处理算法的重要一员，鉴于其仿生学的卓越性能被人们不断改进和挖掘，对于以往难以解决的诸多问题乃至现如今发展极为迅速的许多问题，例如经典的多目标规划问题，组合优化问题；如今很时髦的机器学习问题、智能模式识别及控制问题等，遗传算法现已经成为解决这一系列问题的最有效解决方法之一，本文借助遗传算法研究其应用的一类问题——组合优化问题，并基于旅行商问题对全国范围内的34个省级行政区按照Google Earth地图进行matlab模拟，并对原先基础单一遗传算法的步骤中加入了逆转进化机制，提高了在较大种群规模下和较高迭代次数下的全局最优值的收敛速度，在各项参数方面，科学采用了经典的经验参数，并通过控制变量法对种群数量、迭代次数对收敛速度和收敛精度的影响进行了灵敏度分析，以达到精确合理的解决TSP（旅行商问题）的目的。
关键词：遗传算法 灵敏度分析 旅行商问题 逆转操作
 
Research on Combination Optimization Based on Genetic Algorithm
Abstract:Genetic algorithms have long been an important part of intelligent information processing algorithms,which have been constantly polished and excavated because of its superior performance in bionics.Many problems were difficult to solve in the past, and even nowadays, developing rapidly,such as classical multi-objective programming problems,combinatorial optimization problems and very fashionable machine learning problems, intelligent patternrecognition etc.,genetic algorithms have now become one of the most effective solutions to solve this series of problems. This paper uses genetic algorithms to study one type of application-combination optimization problems, based on the traveling salesman problem, which was simulated by Google Earth in accordance with the Google Earth map for 34 provincial administrative regions nationwide, and a reversal evolution mechanism was added to the steps of the original basic single genetic algorithm. The convergence rate of the global optimal value under the larger population size and higher iterations is improved. In terms of various parameters, in order to achieve accurate and reasonable settlement purposes TSP (traveling salesman problem) ,the classical empirical parameters are adopted scientifically, and the number of population and number of iterations are converged by the control variable method to test the influence of speed and convergence accuracy on sensitivity scores .
Key Words:  GA  sensitivity analysis  TSP  reverse operation

目 录
一.绪论    1
1.1研究目的和意义    1
1.2 国内外研究现状    2
1.3 研究内容和相关课题    4
1.4 旅行商问题简介    5
二 遗传算法基本原理和实现    5
2.1 遗传算法的基本原理    5
2.2 遗传算法的基本步骤    7
2.3 TSP问题遗传算法实现    7
2.3.1 编码    8
2.3.2 交叉操作    8
2.3.3 变异操作    9
2.3.4 遗传算法基本步骤的Java语言实现    10
2.3.5 逆转操作    12
2.3.6 基于遗传算法TSP的matlab语言实现    13
2.3.6.1 前期准备    13
2.3.6.2 matlab模拟实现    14
三 过程分析与说明：    15
3.1关于适应度函数、交叉参数、变异参数的说明    15
3.2关于迭代次数的思考    16
3.3 灵敏度分析    16
3.3.1加大种群数量，控制迭代次数，观察收敛速度和精度    16
3.3.2控制种群数量，增加迭代次数，观察收敛速度和精度    17
四 结果分析    18
4,1 优势与创新    18
4.2 改进与缺陷分析    18
4.3 总结与展望    19
五 附录    20
5.1 相关程序    20
参考文献：    23
致谢    24