菜单
　　
    摘 要遗传算法（Genetic Algorithm, GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J. Holland教授于1975年首先提出的。遗传算法的大致过程是这样的：将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，即给出一个适应度值。开始时，总是随机的产生一些个体，根据这些个体的适应度利用遗传算子——选择（Selection）、交叉（Crossover）、变异（Mutation）对它们重新组合，得到一群新的个体。这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化。遗传算法主要的特点在于：简单、通用、鲁棒性强。4852
    旅行商问题(Traveling Salesman Problem, TSP)是典型的NP完全问题，遗传算法是求解NP完全问题的一种常用方法。本48文利用遗传算法解决组合优化问题——TSP问题，考察遗传算法在求解NP问题中的性能，并在MATLAB中用遗传算法对TSP问题进行求解，进行了选择、交叉和变异算子进行了算法设计，最后在MATLAB软件上进行编程实现，并对测试结果作适当的分析。通过两点交叉和部分映射交叉(Partially Mapped Crossover, PMX)这两种交叉操作的比较，探讨了采用PMX交叉算子的改进遗传算法解决旅行商问题时的特点。
    关键词：遗传算法，TSP问题，MATLAB软件，PMX
    Abstract
    Genetic Algorithm (GA) is an evolutionary computing originally proposed by Dr J. Holland in the year 1975 and developed by him and his students and colleagues. As can be seen literally, Genetic Algorithm is inspired by Darwins theory about evolution. A basic GA employs selection, crossover and mutation operators. The whole process can be referred to as "reproduction". Algorithm is started with a set of solution (represented by chromosomes) called sub-population. Solutions from one sub-populations are taken and used to form a new sub-population by a hope that the new population will be better, at least not worse than the old one. Solutions are selected according to their fitness. The more suitable they are the more chances they have to reproduce. The main characteristic of the GA is that it is simple, universal and robust. After about 20 year’s development, GA has been successfully used in a lot of fields such as the Travelling Salesman Problem, Scheduling, Function Optimization, Machine Learning etc.
    Traveling Salesman Problem is a typical NP complete problem, GA is the perfect method for solving it. This paper uses GA in MATLAB software to solve the typical TSP problem，and the performance of GA in solving TSP problem was analyzed. We designed algorithms for all genetic operators (select, intercross, mutate). Finally, we programmed in Matlab to implement the algorithms, and discussed the characteristic of partially mapped crossover in GA through comparing two point crossover with PMX.
    Keywords: Genetic Algorithm, TSP, MATLAB, PMX
    目 录
    1 绪论.1
    1.1 遗传算法简介.1
    1.2 旅行商问题..3
    1.3 本文研究内容.5
    1.4 全文安排6
    2 遗传算法的基本原理和实现技术..7
    2.1 理论基础7
    2.2 编码策略.10
    2.3 群体设定.12
    2.4 适应度数.13
    2.5 遗传操作.13
    2.6 本章小结.16
    3 改进的遗传算法17
    3.1 遗传算法存在的问题.17
    3.2 现有的遗传算法的几种改进17
    3.3 分析遗传算法的交叉操作.18
    3.4 改进交叉算子.18
    3.5 算法描述19
    3.6 本章小结..20
    4 基于改进遗传算法的仿真实验.21
    4.1 算法总体设计.21
    4.2 算法详细设计.21
    4.3 实验结果及分析25
    4.4 改进算法性能分析..29
    4.5 本章小结.35
    5 总结及展望..36
  1. 上一篇：电气EDA仿真软件在滤波器中的应用
  2. 下一篇：基于PLC的变频恒压供水系统设计

  1. MATLAB小电流接地故障选相方法研究

  2. Matlab基于前馈控制的加热炉温度控制系统设计

  3. Matlab微流控芯片热键合工艺优化研究

  4. MATLAB永磁同步电机矢量控制模型与算法设计

  5. MEMS基于SHARC型DSP的组合导航算法实现

  6. MATLAB排爆机器人移动平台控制系统的设计

  7. 基于LabVIEW和MATLAB混合编程...

  8. 河岸冲刷和泥沙淤积的监测国内外研究现状

  9. 酸性水汽提装置总汽提塔设计+CAD图纸

  10. java+mysql车辆管理系统的设计+源代码

  11. 杂拟谷盗体内共生菌沃尔...

  12. 电站锅炉暖风器设计任务书

  13. 大众媒体对公共政策制定的影响

  14. 十二层带中心支撑钢结构...

  15. 当代大学生慈善意识研究+文献综述

  16. 中考体育项目与体育教学合理结合的研究

  17. 乳业同业并购式全产业链...

　　

About

751论文网手机版...

主页：http://www.751com.cn

关闭返回