函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。 (2) 组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用 (3) 自动控制
在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示了良好的效果。基于遗传算法的参数辨识，基于遗传算法的模糊控制规则的学习，利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。 (4)人工生命
人工生命是用计算机，机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统，自组织能力和自学能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。
第3章 TSP问题及研究的基本方法
3.1 TSP
问题概述
旅行商问题(Travelling Salesman Problem，简记TSP) 经典说法为：有一名旅行商要从一个城市去若干个城市推销货物，从城市A出发，经其余各城市且每个城市只能访问一次，然后回到城市A，问选择怎样的旅行路线，才能使旅行的总长度最短(各城市间距离为已知)。旅行商问题是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入经典的NP-hard组合优化问题之一，。该问题在图论的意义下就是所谓的最小Hamilton圈问题，由于可以广泛应用在许多领域，所以寻找出实际而有效的算法就显得比较重要了。但是遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。
3.2 TSP的应用与价值
TSP在现实生活中有很多应用。直观上，最普通的TSP的运用莫过于找出旅行商为遍历每个地理位置上的点的顺序，使他所经历的路径最短。了解了对每个城市访问一次的最优旅行路径能
够为旅行节约很多潜在的时间。对提到的实例，图中的节点将通过地理位置顺序连接，而且连接两节点的路径的长度是公制的。在当前，很多的现实事物，包括城市，建筑和地标都已经有了平面电子地图。为解决以上提及的实例，仅需要把期望访问的地理位置具体化，然后用旅行商问题的算法进行求解就行了。TSP在其他领域还有很多重要的实际应用。例如在组装线上的机器。一些机器的目标就是为了在某种材料片上钻削不同的孔。材料可能是电路板、汽车底盘甚至是用来做书架的木板。钻头通过定位装置在材料片上重定位。在某个局部的区域，钻头可以沿着轨迹移动到任何位置。钻头的重定位所消耗的时间依赖于钻头需要移动的距离。旅行商问题的解可以用来找出孔被加工的最优顺序。在装配线的实例中，对每个工件为完成装配过程节约的少许时间意味着一天的产量的相应增加。为了通过TSP解决这个时间的节约问题，对每个节点做了简化，用需要钻孔的位置来代替，而边用节点之间的距离来代替。
3.3 TSP问题的数学模型
TSP问题的数学模型如下：设有n个城市，寻找一条巡回路径 T=(t1，t2，．．．，tn)，使得下列目标函数最小：
f(T)= (ti,ti+1)+d(tn,t1)
其中ti为城市号，取值为1到n之间的自然数，d(i,j)为城市i和城市j之间的距离，对于对称式TSP，有d(i，j)=d(j，i)。
除此之外，模型还有其它一些等价的书写形式，这就不一一列举。
TSP问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。虽然陈述起来很简单，但求解却很困难，它一直是运筹学中最富挑战性的问题之一，且已经被证明是NP完全问题。对于具有一个城市的TSP问题，其可能的路径数目为(n-1)!／2，5个城市的情形对应个城市TSP找到最优解的时间复杂性函数的数量级是O(n!)，当n比较大时，耗费的时间己经是个天文数字，至今尚未找到有效的求解方法。在理论上虽然枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径。快速、有效地解决TSP问题有着极高的实际应用价值，也就吸引了众多领域的学者对它进行研究。尽管TSP仍未找到最优解，但是求解它的算法逐渐在改进。1954年Dantzig，Fulkerson和Johnson解决了49个城市数目的TSP问题，经过半个世纪的研究，目前，最大的已成功求解的旅行商问题有24798个城市。
3.4 TSP 问题的分类
从 TSP问题映射到图的类型,可以分为两类:
(1)城市间的距离都是对称的,它对应的是图论中的无向图;
(2)两个城市间的距离是非对称的,它所对应的是图论中的有向图. 从问题本身的限制条件的强弱,可分为三类:
1.不做任何限制(但是一般都要求城市间的费用不为负数),只是给出距离矩阵,求最小回路; 2.要求距离间要满足三角不等式;
3.定义在欧式平面上的 TSP问题,即 EuclidTSP,它给出每个点在欧式平面 上的坐标,而城市间的距离就是以他们的欧式距离来定义.
3.5 现有的求解TSP问题的几种算法
在求解TSP的算法的过程中，人们一直在寻找切实有效的方法，按招时间出现的顺序大致可分为：传统算法和智能演化算法。传统算法有精确算法和近似优化算法，精确算法又有线性规划方法、动态规划方法、分支定界方法等，而近似算法有插入法、最近邻算法、r-opt算法、混合算法、概率算法等。
虽然传统算法能够找TSP问题的最优解，但随着问题规模的不断增长，算法所需要的时间非常巨大，因此只适用于求解规模较小的TSP问题。
20世纪80年代以来，一些新颖的智能优化算法，如模拟退火、遗传算法、禁忌搜索、人工神经网络、蚁群算法、粒子群算法、郭涛算法、免疫算法等，通过模拟或揭示某些自然现象(或过程)而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段．由于这些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算法。引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。 (1)禁忌搜索算法
禁忌搜索算法是局部领域搜索算法的推广，主要思想是标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。此方法需较强技术性，禁忌长度较难取。若禁忌长度过长，则所需内存较大，否则，易陷入局部最优解。 (2)模拟退火算法
这是一种源于五十年代、基于Monte Carlo迭代求解思想的随机搜索算法，八十年代才开始应用于组合优化领域，其出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从Boltzmann分布，若退火步骤恰当，则最终会形成最低能量的基态。这种算法思想在求解优化问题时，不但接受对目标函数(能量函数)有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动能够使之跳出局部极值点，故而得到的解常常很好。
(3)蚁群算法
又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，过模拟蚂蚁的觅食行为， 蚂蚁觅食的时候会在所走过的路径上留下信息激素， 同时信息激素会随时间而挥发.一条路径走过的蚂蚁越多， 留下的信息激素越多; 反过来， 信息激素浓度高的路径上会吸引更多的蚂蚁。通过这种正向反馈， 最终将找到一条最优路径。为了避免蚂蚁两次走上同一条路径( 非法路径) ， 为每个蚂蚁设置一个禁忌表以记录它已走过的路径。该算法的优点是: 它是一种自 适应度、自组织、本质上并行的方法，而且是一种正向反馈的方法，可以促使整个系统向最优解进化，而且参数少、易于调整，易于移植到其他组合优化问题。 但是，它存在收敛慢、易于陷人局部最优 的缺点。
(4)人工神经网络
人工神经网络(Artificial Neural Network，ANN)，是由大量处理单元即神经元(Neurons)互相连接而成的网络，对人脑进行抽象，简化和模拟的一种工程系统，反映人脑的基本特性。人工神经网络算法成为近年来的热点研究领域，涉及到数学、电气工程、计算机工程、物理学等诸多学科，其应用领域包括了建模、时间序列分析、模式识别和控制等，并且仍然在一断扩展。作为神经网络的基本单元，神经元模型具备三个基本要素。其一是有一组突触或连接，常用表示内部神经元的联接强度，或者称为权值，取值范围可在负值和正值之间，其二是可以反映生物神经元时空整合功能的输入信号累加器，其三是具有一个激励函数用于限制神经元的输出。
第4章 遗传算法在TSP的应用
4.1遗传算法在TSP上的应用
在遗传算法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。TSP问题因其典型性已成为各种启发式的搜索，优化算法的间接比较标准，而遗传算法方法就本质来说，主要处理复杂问题的一个鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架，建立有效的遗传操作以及有效地解决TSP等有着多方面的重要意义。
4.2算法的实现
图4-1遗传算法运用在TSP上的流图程
4.3编码
遗传算法的进化过程是建立在编码机制基础上的，编码对于算法的性能，如搜索能力和种群多样性等影响很大。如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。编码机制的主要工作是把对象抽象为由特定符号按一定顺序排成的串。这就如同研究生物遗传是从染色体着手，而染色体则是由基因排成的串。遗传算法中经常使用二进制串进行编码，其优点是编码、解码操作简单，交叉、变异等操作也易于实现，且便于应用模式定理进行理论分析；其缺点主要是处理连续函数的优化问题时存在映射误差：编码长度较小时达不到精度要求，度较大时又会使算法搜索空间过大。
4.4初始化种群
选择一个群体，就是选择一个个体的集合。这个初始群体也就是问题假设解得集合。在遗传算法求解TSP问题中通常以随机方式产生串或者个体的集合。初始种群个数越多，得到最优解的希望越大，但个数过多会导致每进行一轮的机器时间变长，致使算法效率低下。