MATLAB遗传算法的改进及其在TSP问题中的应用(2)
参考文献..37
致 谢.39
1 绪论
在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像旅行商问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明的特别有效的算法。
1.1 遗传算法简介
遗传算法（Genetic Algorithm,GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）[1]。近年来，遗传算法已被成功地应用于工业、经济管理、交通运输、工业设计等不同领域，解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。
1.1.1遗传算法的特点
遗传算法具有如下优点[2]：
⑴对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。此编码操作使得一度患算法可以直接对结构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、图、链和表等各种一文或二文甚至多文结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。比如：
①通过对连接矩阵的操作，遗传算法可以用来对神经网络或自动机的结构或参数加以优化；
②通过对集合的操作，遗传算法可以实现对规则集合和知识库的精炼而达到高质量的机器学习目的；
③通过对树结构的操作，用遗传算法可以得到用于分类的最佳决策树；
④通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造顺序控制系统。
⑵群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是
同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易于并行化。
⑶不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。更重要的四，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。
⑷内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在的并行搜索机制。
下一篇：基于PLC的变频恒压供水系统设计