一种改进的遗传算法在TSP问题中的应用研究

摘要

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题。 本文对影响遗传算法性能的因素进行了分析，引入了自适应遗传算子的设计，交叉概率P。和变异概率Pm能随适应度值自动改变，提出了一种改进的遗传算法IGA(ImprovedGenericAlgorithm)。对于适应值高于群体平均适应度的个体，对应于较低的P。和Pm，使得该解得以保护进入下一代；而低于平均值的个体，对应于较高的P。和Pm，使该解被淘汰掉，自适应遗传算法在保持群体多样性的同时，也可保证遗传算法的收敛性。 旅行商问题是一个典型的NP完全性问题。本文基于改进的自适应遗传算法设计并开发了一个求解旅行商问题的软件程序，并将此程序进行了48个城市的TSP问题计算，与模拟退火算法的计算过程及计算结果进行了比较。文中给出了遗传算法在解决TSP问题中的参数选择和编码方式、适应度函数的设计、种群的初始化和遗传算子的详细设计。通过对此程序的改装，即可用于其他NP完全性问题的求解。 实验结果证明，基于自适应遗传算法的TSP问题求解程序的效果更优，能在较短的时间内得出令人满意的结果。

目录

文摘

英文文摘

1 绪论

1.1引言

1.2遗传算法简介

1.2.1遗传算法的基本概念

1.2.2遗传算法的基本原理

1.2.3遗传算法的步骤和意义

1.3遗传算法研究现状

1.4本文主要内容

2计算复杂性问题

2.1计算复杂性与NP问题

2.2搜索空间与NP难题

2.3一些典型的NP完全问题

2.3.1 旅行商问题(Traveling Salesman Problem，简称TSP)

2.3.2顶点覆盖问题

2.3.3子集合问题

2.3.4哈密顿回路问题

2.4 NP完全问题的近似解法

3基本遗传算法的改进

3.1 引言

3.2种群“早熟”程度的定量评价指标

3.2.1 三种定量评价指标的定义

3.2.2三种指标性能评述

3.2.3 新的种群“早熟”程度评价指标

3.3改进的自适应遗传算法

3.3.1 算法描述

3.3.2 实例计算

3.4小结

4遗传算法在TSP问题中的应用

4.1遗传算法的应用领域

4.2遗传算法在TSP问题中的应用

4.2.1 旅行商问题的描述与建摸

4.2.2 自适应遗传算法解决TSP问题程序设计框架

4.2.3 用遗传算法解决TSP问题的步骤

4.2.4 用遗传算法解决TSP问题与其他近似搜索算法的比较

5 结束语

5.1本文主要工作

5.2进一步的工作

致 谢

参考文献