MATLAB遗传算法的改进及其在TSP问题中的应用(5)
1．TSP问题是一个典型的、易于描述却难以处理的NP完全问题。有效的解决TSP问题在可计算理论上有着重要的理论价值；
2．TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效的解决TSP问题有着极高的实际应用价值；
3．TSP问题因其典型性已经成为各种启发式搜索、优化算法的间接比较准则（如神经网络优化法、列表寻优法（TABU）法、模拟退火法等）[5]。
1.3 本文研究内容
遗传算法一直都是智能优化方面一个重要的研究内容，在生物科学，计算机科学，信息科学的交叉学科，都以其简单、易行、鲁棒性强而备受关注。
遗传算法的优势在于它不需要专深的领域知识就能取得很好的结果，但是标准的遗传算法本身也存在着缺陷，究其原因就是交叉操作的开发能力和利用能力之间造成的矛盾，本文的主要研究内容就集中在遗传算法交叉操作的性能以及遗传算法在应用到TSP问题中时交叉操作对算法性能的影响。
本文研究了遗传算法在求解旅行商问题的中的应用。通过在MATLAB中编写程序实现该问题的遗传算法，本文分别实现了采用两种不同交叉操作的遗传算法来比较它们在TSP问题应用中的性能。一种是采用传统的两点交叉，另一种是在两点交叉的基础上改进的部分映射交叉操作。计算机上的仿真试验结果表明，在求解旅行商问题时，部分映射交叉比两点交叉更好，能够取得更好的效果，在早熟问题和最优解上
1.4全文安排
本文共分五章：
第一章简单介绍了遗传算法的特点和研究现状，并针对本课题的应用，介绍了旅行商问题以及研究旅行商问题的意义，最后提出本文的研究内容和文章安排。
第二章介绍遗传算法的基本原理，包括其理论基础和基本实现技术，是开展课题工作的知识铺垫和全文的基础。
第三章主要分析标准遗传算法的不足，针对两点交叉在解决旅行商问题时的缺点，提出两点交叉的改进――部分映射交叉，即PMX，并给出其主要思想，对本文遗传算法进行描述，画出算法流程图。
第四章根据上一章中的流程图对算法进行详细设计，并分析在MATLAB中得到的试验结果，对改进后的遗传算法的性能进行比较分析。
第五章是对本文工作的总结及对以后工作的展望。
2 遗传算法的基本原理和实现技术
遗传算法是一个以适应度函数为依据，通过对群体个体施加遗传操作，实现群体内个体结构重组的迭代处理过程。在这一过程中，群体个体一代一代得以优化并逐渐逼近最优解。这一章将在理论分析遗传算法的基本原理。
2.1 理论基础
遗传算法的理论基础就是模式定理（schemata theorem），首先介绍一下模式的概念。
2.1.1模式
模式（schema）是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。例如二值字符集｛0，1｝，由此可以产生通常的0,1字符串。现在增加一个通配符“*”，“*”既可以被当作“0”，又可以被当作“1”。这样二值字符集｛0，1｝就可扩展成三值字符集｛0，1，*｝[6]。
【定义2.1】基于三值字符集｛0，1，*｝所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。
引入模式概念并不是仅仅为了描述上的方便。在引入模式概念前，我们看到的遗传算法是：在某一代中，N个互不相同的串在选择、交叉、变异等遗传算子的作用下产生下一代的N个新的互不相同的串。那么，两代之间究竟保留了什么性质，破坏了什么性质，我们无从得知，因为我们所看到的串都是相互独立的，互不联系的。在引入模式概念后，我们看到的一个串实际上隐含着多个模式（长度为l的串隐含着 个模式），一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。
下一篇：基于PLC的变频恒压供水系统设计