MATLAB遗传算法的改进及其在TSP问题中的应用(3)
⑸遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。
⑹遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。
⑺遗传算法具有固有的并行性和并行计算的能力。
⑻遗传算法具有可扩展性，易于同别的技术混合。
1.1.2遗传算法的研究现状
上面介绍了遗传算法的特点,实际上，遗传算法也有许多不足和缺陷。客观的说，遗传算法尽管有各种新策略和新提案不断被提出，但几乎都是针对特定问题求解而言的，对它们的评估也都基于对比试验，其中缺乏深刻而具普遍意义的理论分析。正因为如此，遗传算法现阶段的研究重点回到了基本理论的开拓和深化以及更通用、更有效的操作技术和方法的研究上。以下是遗传算法现阶段研究课题的几个主要方面[3]。
●优化搜索方法的研究
迄今为止，优化问题的求解仍在遗传算法研究中占很大的比例。例如TSP等组合优化问题一直是遗传算法十分活跃的研究课题。据报道，遗传算法对431个城市的TSP问题的求解已经取得最优解，对666个城市已经得到准最优解。尽管遗传算法比其它搜索方法有更强的鲁棒性，但它更擅长全局搜索而局部搜索能力却不足。研究发现，遗传算法可以用极快的速度达到最优解的90%左右，但要达到真正的最优解则要花费很长的时间。
● 遗传算法的分布式并行处理
伴随着遗传算法应用的深入发展，并行分布遗传算法及其实现的研究也变得十分重要。遗传算法由于其群体性操作，所以本质上具有很好的并行分布处理特性。尤其是遗传算法中作为最大的计算开销的各个体适应度计算可独立进行而彼此之间无需任何通信。但是，标准的遗传算法除了适应度计算外，几乎所有的遗传操作都是建立在全局统计处理的基础上（比如说比较适应度值的大小并进行排序等等），这意着在整个进化过程中，这种全局统计处理所引起的通信开销依然不可忽视，有时甚至成为主要问题。因此，设计有效的并行遗传算法以及相应的实现系统对于遗传算法的理论研究和应用研究都是十分重要而迫切的任务。
另外，遗传算法的研究方向还有学习系统的遗传算法研究、生物进化与遗传算法的研究、人工生命与遗传算法的研究等等。
1.2 旅行商问题
遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。而旅行商问题是最有代表性的优化组合问题之一，遗传算法在解决该问题时表现出来优异的性能，因此以旅行商问题为应用背景的遗传算法研究一直是广大学者研究的热点。下面对什么是旅行商问题作简要概述。
1.2.1旅行商问题概述
旅行商问题是威廉•哈密尔顿爵士和英国数学家克克曼(T. R Kirkman)于19世纪初提出的一个数学问题。这是一个典型的NP完全性问题。
简单描述是：一名商人欲到n个城市推销商品，每两个城市i和J之间的距离为d，存在i，i如何使商人每个城市走一遍后回到起点，且所走的路径最短。用数学符号表示为 ：设n文向量表示一条路径X：(C．．C ⋯⋯ ， ) ，目标函数为
minF(x)=
用图语言来描述TSP，给出一个图G=(v，E)，每边e∈E上有非负权值w(e)，寻找G的Hamilon圈C，使得C的总权W(C)= 最小。TSP搜索空间随着城市数n的增加而增大，所有的旅程路线组合数为(n一1)!／2。5个城市的情形对应120／10=12条路线，10个城市的情形3628800／20=181440条路线，100个城市的情形则对应有4．6663x10 条路线。在次庞大的搜索空间中寻求最优解，对于常规方法和现有的搜索而言，存在诸多的计算困难。借助遗传算法的搜索能力解决TSP问题是很自然的想法。[4]。
下一篇：基于PLC的变频恒压供水系统设计