（计算机软件与理论专业论文）一种求解tsp问题的改进遗传算法.pdf

一种求解t s p 问题的改进遗传算法 专业：计算机软件与理论 硕士生：庞文颖 指导教师：张军 摘要 本文为求解t s p 问题设计了一种改进的遗传算法。在学习和研究过程中， 了解到遗传算法在求解t s p 问题的有效性，且影响遗传算法性能的参数主要有 初始种群的质量、群体的大小、交叉概率和变异概率的值等。因此，本文提出 了一种求解t s p 的改进遗传算法，在初始种群的产生方面通过最短路径算法构 造较优的基因片断对随机产生的个体进行优化，然后结合基于聚类自动调整交 叉概率和变异概率的自适应遗传算法，使用单亲演化与群体演化相结合的方式 对t s p 问题进行求解。使用遗传算法求解t s p 问题过程中，通过提高初始种群 的质量、自适应调整交叉概率和变异概率的值、适当地设计适应值函数和交叉 算子，使得此算法不但提高了收敛速度，还提高了收敛的精度，整个性能得到 了提高。实验结果证明了该算法的有效性。 关键词：遗传算法；t s p 问题；基因片断；交叉概率；变异概率 am o d i f i e dg e n e t i ca l g o r i t h mf o rt s p m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：p a n gw e n y i n g s u p e r v i s o r ：z h a n gj u n a b s t r a c t t h i sd i s s e r t a t i o nd e v e l o p sag e n e t i ca l g o r i t h mf o rs o l v i n gt h et s pp r o b l e m c o n s i d e r i n gt h ee f f e c t i v e n e s so ft h eg e n e t i ca l g o r i t h mi nt s pp r o b l e m ，t h er e l e v a n t p a r a m e t e r sw h i c ha f f e c tt h ea l g o r i t h m sr e s u l t , s u c ha st h eq u a l i t ya n ds i z eo ft h e i n i t i a lp o p u l a t i o n , c r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t y , t h i se s s a yt h e r e f o r e p u t sf o r w a r dam o d i f i e dg e n e t i ca l g o r i t h m i te l i m i n a t e sr a n d o m i c i t yo ft h ei n i t i a l g r o u pt h r o u g ho p t i m i z i n gr a n d o mi n d i v i d u a l st og e n e r a t eb e t t e rg e n ef r a g m e n t s ，a n d p r o c e e d st os o l v et h et s pp r o b l e mv i aas e l f - a d a p t i v eg e n e t i ca l g o r i t h mb a s e do na c o m b i n a t i o no ft h ec l u s t e r - b a s e ds e l f - a d a p t i v ec r o s s o v e rp r o b a b i l i t ya n dm u t a t i o n p r o b a b i l i t y , a n da l li n t e g r a t i o no fp a r t h e n oa n dc o l l e c t i v ee v o l u t i o n t h r o u g ht h e i m p r o v e m e n to ft h eq u a l i t yo ft h ei n i t i a lp o p u l a t i o na n dt h ev a l u eo fs e l f - a d a p t i v e c r o s s o v e ra n dm u t a t i o np r o b a b i l i t y , a n dap r o p e rd e s i g no ff i t n e s sf u n c t i o na n d c r o s s o v e ro p e r a t o r s ，t h ec o n v e r g e n c er a t ea n dp r e c i s i o na sw e l la st h eo v e r a l l c a p a b i l i t i e sa r ee n h a n c e d f i n d i n g sh a v ep r o v e dt h ee f f e c t i v e n e s so ft h i sa l g o r i t h m k e yw o r d s ： g e n e t i ca l g o r i t h m ，t s pp r o b l e m ，g e n e t i cf r a g m e n t ，c r o s s o v e r p r o b a b i l i t y , m u t a t i o np r o b a b i l i t y 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：荔艺丈等欠 日期易帕降r 月加日 i 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文储虢庑女勃 导师虢旁仁莓 日慨降，月伽日日期：如7 年，为2 6 日 l 第一章概述 t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) i o - 题也称为旅行商问题、货郎担问题。t s p 问题是一个经典的组合优化问题，已被证实是n p 难解问题【l 】。其所有的路线的 组合数为( n 一1 ) ! 2 ，其搜索空间随着城市数增大而迅猛增大，这就产生了组 合爆炸问题。由于该阀题在工程领域有着广泛的应用，如网络通讯、电气布线、 管道铺设、货物运输、加工调度等，因而吸引了众多领域的学者对它进行研究。 目前求解t s p 问题的方法主要有精确算法，如贪婪法、分支定界法和动态规划 法等以及另一类是近似算法，如传统的最近邻法等和现代智能优化算法如遗传 算法、蚁群算法、模拟退火算法、禁忌搜索算法、免疫算法等。由于t s p 问题 是n p 难解问题，因此，贪婪法、分支定界法和动态规划法等精确算法，在城 市数n 较大时计算量太大而无法实现。而7 0 年代早期，m i c h i g a n 大学的j o h n h o l l a n d 教授提出的遗传算法是一种基于自然选择和遗传变异等生物进化机制 的全局性概率搜索算法，在搜索过程中能自动获取和积累有关搜索空间的知识， 并自适应地控制搜索过程，因此近年来利用遗传算法来求解t s p 问题的研究相 当活跃，遗传算法已经显示了巨大的优势。 遗传算法虽然具有很好的适应性，但在实际应用中发现初始种群的质量、 种群的大小、交叉概率和变异概率的值等参数对遗传算法的性能有较大的影响。 初始种群中每个个体质量的高低决定了算法效率，如果所有个体的适应值都较 差，必会影响算法的全局性能。而交叉概率和变异概率的值设置得好不好，也 决定了算法是否能够找到最优值或者找到最优值的效率。因此，研究如何构建 优良的初始种群、如何调整交叉概率和变异概率的值在遗传算法研究中是一个 重要的部分。另外，传统的遗传算子( 如部分匹配交叉、循环交叉和倒位交叉 等) 收敛速度较慢，而且交叉算子的使用对群体的多样性存在很大影响，容易 使算法过早收敛陷入局部解。因此，为了能够加快遗传算法的收敛速度，又能 得到更好的近似最优解，本文采纳了杨辉等 2 】提出的基因片断的想法，并结合 j u nz h a n g 等【3 提出的基于聚类自动调整交叉概率和变异概率的自适应遗传算法 思想，使用单亲演化与群体演化相结合的方式来求解t s p 问题。即在初始种群 的产生方面通过图的最短路径算法构造较优的基因片断对随机产生的个体进行 优化，从而提高初始种群的质量，缩短进化的过程；然后再采用次序交叉算子 和变异算子进行群体演化；在演化过程中，利用一定的规则，根据系统性能测 量值实时地自适应调整交叉概率和变异概率的值，提高算法的搜索能力和收敛 速度。 2 第二章综述 2 1t s p 问题的介绍 2 1 1t s p 问题的描述 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 是一个经典的组合优化问题， 可以描述为：一名商人欲到1 1 个城市推销商品，每两个城市i ，j 之间的距离为 d i j ( i , j = l 2 ，n ) ，如何选择一条路径，使得商人从一个城市出发，经过所有城 市一次且仅一次后回到出发点，所行走的总行程最短。 t s p 问题是一个典型的组合优化问题。从图论的角度看，该问题实质是在 一个带权完全无向图中，找一个权值最小的h a m i l t o n 回路。由于该问题的可行 解是所有顶点的全排列，随着顶点数的增加，其可能的路径总数与城市数目n 是成指数型增长的，会产生组合爆炸，是一个n p 完全问题，所以一般很难精 确地求出其最优解，因而寻找出有效的近似求解算法就具有重要的意义。 2 1 2t s p 问题的历史和研究现状 t s p 问题的历史很久，最早的描述是1 7 5 9 年e u l e r 研究的骑士周游问题， 即对于国际象棋棋盘中的6 4 个方格，走访6 4 个方格一次且仅一次，并且最终 返回到起始点。t s p 问题的历史可以分为以下几个阶段： 1 8 0 0 - 1 9 0 0 ：首次描述t s p 问题： 1 9 2 0 1 9 3 0 ：t s p 问题得到较好的定义； 1 9 4 0 1 9 5 0 ：开始意识到t s p 问题是“难”的问题； 1 9 5 4 ：4 2 个城市的t s p 问题求得最优解。 t s p 是由美国r a n d 公司于1 9 4 8 年引入，该公司的声誉以及线性规划这 一新方法的出现使得t s p 成为一个知名且流行的问题 4 】。从1 9 5 4 年以后，求 得最优解的t s p 问题规模越来越大，在1 9 9 8 年求得了1 3 5 0 9 个城市的最优解， 3 在2 0 0 4 年5 月瑞典求得了2 4 9 7 8 城市的最优解。随着时间的推移，肯定有更大 规模的t s p 问题得到求解。 2 1 3t s p 问题的数学模型 g = ( v ，e ) 为一个带权图，v _ 1 ，2 ，n 为顶点集，e 寻 铴li ，j v ， i j ) 为边集。d o ( i ，j v ，i j ) 为顶点i 到j 的距离，其中如 o 且屯， 同时d i j = d j i ( i ，j v ) ，则经典t s p ( c l a s s i c a lt s p ，c t s p ) 的数学模型 5 1 为： m i n f = d f f z 矿 式( 2 1 ) 嘞： h 崆氅慧叙 船2 ) 一10 为非最优路径 扎峥7 勤= 1 ，i ，j v 式( 2 3 ) = i s i ，s 为g 的子图 式( 2 4 ) _ 一， i 其中，蚓为图s 的顶点数。式( 2 1 ) 为c t s p 的目标函数，求经过所有顶点 的回路的最小距离。式( 2 2 ) 和式( 2 。3 ) 限定回路上每个顶点仅有一条入边和一条 出边。式( 2 4 ) 限定在回路中不出现子回路。模型实质上是在一个带权图中求一 条h a m i l t o n 回路。若对所有的i ，j ，k e v ，不等式d i j + d j k 一d i k 均成立，则称该 问题是满足三角不等式的。 2 2 求解t s p 问题的算法综述 求解t s p 问题的算法可分为：精确算法、近似算法和启发式算法。精确算法 目的在于求出最优解，包括完全枚举、动态规划等，由于精确算法的时间和空 间复杂性随着城市数目的指数倍增加，使得精确算法只能用来处理规模较小的 t s p 实例，这对于实际及理论研究都失去了意义。因此，在t s p 的求解过程中， 近似算法和启发式算法占据着主要的位置，其包括传统的最近邻法等和现代智 能优化算法如遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、免疫算法 等。下面从综合性能的角度对典型t s p 算法进行分析比较。 4 2 2 1 精确算法 ( 1 ) 线性规划算法 这是求解t s p 的最早的一种算法，主要是采用整数规划中的割平面法，即 先求解棋型中由前二个约束构成的松驰l p 问题，然后通过增加不等式约束产 生割平面，逐渐收到最优解。但是，由于该方法在寻找割平面时常常要凭借经 验，因此，后来很少作为一般方法使用。 ( 2 ) 动态规划算法 动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题 的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划法是 将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最 优解。由于动态规划算法的时间复杂度为o g 2 ) ，空间复杂度为o g 2 ) ，故一般 除了很小规模的问题外，几乎不予采用。 2 2 2 近似算法和启发式算法 ( 1 ) 最近邻居法 最近邻居法采用向量空间模型来分类，概念为相同类别的个体，彼此的相 似度高，而可以由计算与已知类别各地的相似度来评估未知类别个体可能的分 类。然而最近邻居法因为计算量相当的大，所以相当的耗时。 ( 2 ) 模拟退火算法 模拟退火算法应用于t s p 取得了非常好的解，其缺点在于搜索速度慢，因 此就出现了一些改进算法。模拟退火算法也经常与其他的局部搜索方法相结合， 取长补短，以取得更好的搜索速度和解质量。 ( 3 ) 禁忌搜索算法 禁忌搜索算法应用于t s p ，其目的在于更细致地搜索局优解近邻，但困难 之处在于禁忌表的设计以及有效管理。遗憾的是，禁忌搜索算法在搜索速度和 解的精度都无法与改善型启发式算法相比，因此，现在的一些研究人员将目标 转向并行计算，到目前为止，还没有好的结论。 ( 4 ) 遗传算法 5 在求解t s p 的过程中，遗传算法存在的问题是收效到局部最优解，而非全 局最优解，以及收敛速度慢。同样，它也经常被用来与其他方法相结合，以得 到更好的算法。在下一节将会进行详细的介绍。 另外，其他算法，如蚁群算法、混合算法、各种算法的变异等，也对t s p 的求解作了尝试。 2 3 遗传算法的研究现状 近年来有关遗传算法的期刊论文和会议论文每年都有数百乃至上千篇，这 些文献主要是从某个方面对遗传算法进行不同形式的改进，并且都有针对性的 用于解决某类实际问题。下面从几个方面进行讨论： 2 3 1 编码表示 h o l l a n d 在运用模式定理分析编码机制时，建议使用二进制编码，但二进制 编码不能直接反映问题的固有结构，精度不高，个体长度大，占用计算机内存 多。g r a y 编码是将二进制编码通过一个变换进行转换得到的编码，其目的是克 服h a m m i n g 悬崖的缺点，动态编码( d y n a m i ce n c o d i n g ) 是当算法收敛到某局部最 优时增加搜索的精度，从而使得在全局最优解附近可以进行更精确的搜索，增 加精度的办法是在保持串长不变的前提下减小搜索区域，对于问题的变量是实 向量的情形，可以直接采用实数进行编码，这样可以直接在解的表现形上进行 遗传操作从而便于引入与问题领域相关的启发式信息以增加算法的搜索能力。 复数编码的g a 是为了描述和解决二维问题，基因用x _ 卜y i 表示；它还可以推 广到多维问题的描述中，多维实数编码g a 使无效交叉的可能性大大降低，同 时其合理的编码长度也有助于算法在短时间内获得高精度的全局最优解。当问 题表示的是树和图时，我们还可以使用结构式编码。 由于遗传算法过程的鲁棒性，它对编码的要求并不苛刻。实际上，大多数 问题都可以采用基因呈一维排列的定长染色体表现形式，尤其是基于 o ，1 ) 符 号集的二进制编码形式。然而，编码的策略或方法对于遗传算子，尤其是对于 交叉和变异算子的功能和设计有很大的影响。 6 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码一交叉 问题。因此，作为遗传算法流程中第一步的编码是遗传算法中需要认真研究的 问题，很多专家提出了各种编码方法。 2 3 2 适应度函数 适应度函数是用来区分群体中个体好坏的标准，是自然选择的唯一标准， 选择的好坏直接影响算法的优劣。引入适应值调节和资源共享策略可以加快收 敛速度和跳出局部最优点。对适应值进行调节就是通过变换改变原适应值间的 比例关系，常用的比例变换有线性变换、乘幂变换和指数变换等；对于一个问 题采用什么变换才能达到较优的效果。v k r e i n o b i c h 等做了较详细的讨论，而s wm a h f o u d 6 】采用了共享的技术，对子群的形成和稳定起了一定作用，文中主 要用子群消失时间的近似形式估计s h a r i n g 的界。vp e t r i d i s 采用了依据搜索进 展可变的适应值函数，并用于分割问题，取得了较好的效果。杨旭东等f 7 】设计 了自适应选取遗传算法的适应值函数的方法，该方法的计算量要比排序选择的 计算量小的多，而且有效的避免了算法的早熟收敛。 2 3 3 选择策略 优胜劣汰的选择机制使得适应值大的个体有较大的存活机会，不同的选择 策略对算法的性能有较大的影响。赌轮选择是使用最多的选择策略，但这种策 略可能会产生较大的抽样误差，于是对此提出了很多的改进方法，如繁殖池选 择，b o l t a m a n n 选择等等，但是这几种策略都是基于适应值比例的选择，常常 会出现早熟收敛和停滞现象。为此又提出了非线性排名选择，这种选择不仅避 免了上述问题，而且可以直接采用原始适应值进行排名选择，而不需对适应值 进行标准化；但这种选择在群体规模很大时，其额外计算量( 如计算总体适应 值和排序) 也相当可观，甚至在进行并行实现时会带来一些同步限制。dt p h a m 等采用了类似梯度的方式来选择，不仅使较差的染色体比较好的染色体得到更 大的改进，而且还不断产生新的个体，从而不断拓展了新的空间。dn o v e r 等 引入了h a r v e s t i n gs t r a t e g i e s 来分析遗传算法的性能，h a r v e s t i n gs t r a t e g i e s 是指 在每一代交叉和突变后进行两次乃至多次筛选作为下面的群体。tk a o 采用了 7 d i s r u p t i v es e l e c t i o n ，它吸收了优等和劣等个体，实验结果表明了两级分化有可 能更容易找到最优解。为了提高种群的多样性，高峰提出了一种基于免疫多样 性的选择算子，该选择算子依赖于串的稠密度和适应值，串的稠密度越大，其 保留下来的可能性就越小，具体事例证明改进算法是有效的。 2 3 4 控制参数 控制参数一般都有种群大小、交换概率、变异概率等，这些参数对遗传算 法性能影响较大。在标准遗传算法中采用经验进行估计，这将带来很大的盲目 性，而影响算法的全局最优性和收敛性。目前许多学者意识到这些参数应该随 着遗传进化而自适应的变化，d a v i s 提出自适应算子概率方法即用自适应机制把 算子概率与算子产生的个体适应性相结合，高适应性值被分配高算子概率。 w h i t l e y 提出一种自适应突变策略与一对父串间的h a m m i n g 距离成反比，结果 显示能有效的保持种群的多样性。a r a b a s 等设计了一种群体规模可变的遗传算 法，它提出每个个体应该有年龄和生命周期的概念并淘汰年龄大于生命周期的 个体，从而使遗传算法动态的控制了群体数目，这种方法可以找出一个接近最 小代价的遗传算法，同时尽量将群体规模保持在现有水平，防止群体规模指数 级增长，以降低计算的开销。为保证种群的有用多样性，提出动态种群法当迭 代到一定代数，若目标函数的值相同，则现存种群中的较差的n 个染色体被随 机产生的n 个染色体所代替，使进化过程中不断有新个体引入。 2 3 5 遗传算子 基本遗传算法中采用单点交叉算子和简单的变异算子。它们操作比较简单， 计算量小，但是在使用过程中有很大的局限性，例如：由于单点交叉破坏模式 的概率较小，致使搜索到的模式数也较少，使算法具有较低的搜索能力。g a o f e n g 对多维连续空间的g a 复杂多样性进行了分析，通过建立相应的数学模型， 解释了在多维连续空间和大规模群体中使用均匀杂交算子是如何探索新的解空 间区域，为了使得变异能够根据解的质量自适应的调整搜索区域，从而能较明 显的提高搜索能力，提出自适应变异算子。为了保护适应值较高的模式，提出 了自适应交叉和变异，如果遇到适应值较高的模式，则通过随机引入模式外的 8 位进行保护。为了克服早熟，引入多种群g a ，不同种群赋以不同的参数，实 现不同的搜索目的，通过移民算子联络各种群，通过人工选择算子保存各种群 每个进化代中的最优个体。为了防止近亲繁殖，扩大种群的多样性，抑制超长 个体快速繁殖，引进近亲繁殖算子，两个个体是否为近亲可以通过基因片段的 h a m m i n g 距离来判断，距离越大，则为近亲的可能性越小；为了加强局部搜索 能力，增加漂移算子，将染色体各基因片段的后二分之一的基因分别按一定的 概率做1 的漂移，排位越后的基因漂移的概率越大，由此产生一定数量的新个 体，用基因预选机制的小生境技术控制漂移方向。因为格点法产生的点集能均 匀的分布于搜索空间，并且佳点又是最好的格点，所以可以用数论中的佳点集 理论设计交叉算子，结果表明它的搜索效果要比纯随机方法好，而且有效的避 免早熟现象。基于生物免疫性提出的免疫算子，能够明显抑制进化过程中的退 化现象，减轻g a 的后期波动，从而提高了搜索效率和收敛速度。 2 3 6 综合方面 增强型g a 中，引入了几个新算子和新的种群迁移策略，并用其对模糊逻 辑控制器进行设计，得到了便于理解的模糊集和模糊规则。用小波分析中的多 尺度分析对g a 中的染色体进行多尺度分解，这样分解后的染色体长度变短， 基因交换、变异等遗传操作更为彻底，有效的克服了基因丢失引起的早熟问题。 小生境技术不仅能够保证种群中解的多样性，而且具有很强的引导进化能力， 所以小生境技术的引入，提高了g a 处理多峰函数优化问题能力。将模拟退火 过程引入遗传算法，在优选交叉和变异个体的过程中加入一定的“扰动”，以 达到保持种群内位串的多样性和位串之间的竞争机制，克服了算法易陷入局部 极小点的问题，使得搜索沿着全局最优方向进行。广义遗传算法，它以多点突 变操作为主，以基因交叉操作为辅，实现了从一个局部最优状态到另一个局部 最优状态的转移，使得算法获得全局最优。为了使g a 用于约束最优化，提出 了一种非稳态罚函数g a ，非稳态罚函数是遗传代数的函数，当代数增加时，罚 函数也随着增大，同时给g a 也带来更多的选择压力，促使g a 找到可行解。 综合遗传算法的全局性和神经网络的并行快速等特点，提出的遗传神经网络算 法，可克服遗传算法最终进化至最优解速度较慢和神经网络易陷入局部最优解 9 的缺陷，具有较好的全局性和收敛速度。采用面向对象技术设计了面向对象遗 传算法，这种方法改变了传统的g a 中各个函数间只有参数的传递，而没有代 码的继承性的状况，从概念上提高了软件的可重用性，用户可以更方便的实现 自己的编码方案和遗传算子。变异基遗传算法，采用变异算子进行局部优化搜 索，并利用随机初始化技术使算法在局部搜索能力提高的同时仍有可能找到全 局最优解。贪婪遗传算法在二次分配问题中取得了较好的效果，在该算法中引 入了新的交叉算子和移民算子，保证了种群的多样性，并且通过比赛竞争使得 各种群得到进化，很好的解决了种群多样性及对个别好个体偏爱之间的矛盾。 2 4 遗传算法求解t s p 问题的综述 t s p 问题是一个典型的、容易描述但是难以处理的n p 完全问题，而且t s p 问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。所以，有效 解决t s p 问题在计算理论上和实际应用上都有很高的价值。而且t s p 问题由于 其典型性已经成为各种启发式的搜索优化算法的间接比较标准。 遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随 机搜索算法。因此遗传算法在t s p 问题求解方面的应用研究，对于构造合适的 遗传算法框架、建立有效的遗传操作以及有效地解决t s p 问题等有着多方面地 重要意义。 遗传算法是7 0 年代早期m i c h i g a n 大学的j o h nh o l l a n d 教授提出的一种基 于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，在搜索过程中 能自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程。后g o l d b e r g 和g r e f e n s t e t t e 首先利用遗传算法求解t s p 问题，并提出了部分匹配交叉算子、 顺序交叉算子和环交叉算子。此后利用遗传算法求解t s p 问题的研究相当活跃， 有关t s p 问题的演化方法的文章非常多( 如在期刊网上有近5 0 0 篇有关的论文) 。 并且，几乎遗传算法的每个会议上都会有一些关于t s p 的论文。人们希望能找 到一个求解t s p 的完美遗传算法，能和目前的最好方法( l k h ) 相媲美。 遗传算法虽然具有很好的适应性，但在实际应用中发现传统的遗传算子收 敛速度较慢，而且交叉算子的使用对群体的多样性存在很大影响，容易使算法 过早收敛陷入局部解 8 】。在遗传算法中，设计好的遗传算子对于算法至关重要。 1 0 为此，许多研究人员设计了各种交叉算子，例如p m x ，o x ，e r x ，s s x ，d p x 和c s e x 等，但这类算子通常实现起来计算量较大。而另一类以倒置为基础的变 异算子执行效率高，但由于随机性过强，本身不能利用群体中个体的信息进行重 组。在这两类算子中一种好的折衷就是由郭涛和m i c h a l e w i c z 9 】提出来的i n v e r o v e r 算子。h e r o v e r 算子实现简单，搜索空间大，其核心思想是：t s p 的基 本基因块是边而不是城市的位置表达。因而该算子产生的新个体中大部分边来 自于群体中存在的边，j 、部分则是引入的新边。这个算法对于小规模t s p 问题非 常有效，但是对于大规模t s p 问题，算法收敛就比较缓慢，速度上远远比不上与问 题特征相关的启发式优化算法。 由于传统遗传算法要求初始群体的广泛多样性、存在“早熟收敛”问题等。 所以，胡纯德等【l o 】提出单亲遗传算法，利用遗传算法的优胜劣汰的遗传特性， 在单个染色体内采用基因换位、基因段移位、基因段逆转和基因分组定界等基 因重组操作繁衍后代，保留适应值高的染色体种群，最终收敛到最优个体，从 而求得问题的近似最优解。因单亲遗传算法只在一条染色体上操作，比传统遗 传算法在两条染色体上操作计算的复杂性要小，速度要快。 除了遗传算子外，有的学者已开始注意到群体质量对于整个遗传算法的效 能有着至关重要的作用。杨辉等 2 】借鉴生物学上的成果，提出了建立基因库来保 存好的基因块。利用基因库提高群体质量，在一定程度上指导种群的发展方向； 反过来，又可以通过种群现有信息更新基因库，以提高基因库的效能。 另外，遗传算法的性能很大程度上取决于解空间搜索广度和深度之间的平 衡。遗传算法控制参数的设置，如交叉概率，变异概率和种群大小都是决定搜 索广度和深度之间关系的重要因素【1 1 1 。最优的遗传参数设置应该能在优化过程 中根据系统性能测量值实时自适应调整，并且不依赖问题本身。因此，陈贤富 等【1 2 】提出依据遗传群体的环境参量动态调整遗传进化策略和控制局部搜索强度 的自适应进化算法。金晶等 1 3 】提出一种自适应遗传算法，将个体的适应度与当 代种群的平均适应度进行比较，结合最佳和最劣个体计算出该个体的交叉概率 及变异概率。刘瑞国等 8 】提出通过增加一个反映种群进化优良程度的因子来调 节整个种群遗传交叉、变异概率，同时种群的进化机制随着进化进程也在不断地 自适应地调整。j u nz h a n g 等 3 】提出通过k - - m e a l l s 算法对种群进行分组，基于 含最佳个体和最差个体的群组的相对大小利用一模糊系统来自适应调整交叉概 率和变异概率的值。 1 2 3 1 引言 第三章遗传算法介绍 生物的进化是一个奇妙的优化过程，它通过选择淘汰、突然变异、基因遗 传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发 得出的一种全局优化算法。 遗传算法的概念最早是由j d b a g e l y 在1 9 6 7 年提出的；而开始遗传算法的 理论和方法的系统性研究是1 9 7 5 年，这一开创性工作是由m i c h i g a n 大学的 j h h o l l a n d 所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) ，为了不至于混淆，我们把h o l l a n d 所提出的算法称为标准遗传算法，简称g a 或s g a ；而将它的“g a 类”算法 称为g a s ，可以把g a 看成g a s 的一种特例。 遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解 问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、 机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、 社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、 自适应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计 算技术有重大影响的关键技术”。 3 2 遗传算法的发展概况 6 0 年代，m i c h i g a n 大学的h o l l a n d 教授认识到生物的遗传和自然进化现象 与人工智能自适应系统的相似关系，提出在研究和设计人工自适应系统时，可 以借鉴生物的遗传机制，以群体的方式进行自适应搜索。1 9 6 7 年，h o l l a n d 的 学生j d b a g l e y 在他的博士论文中首次提出了遗传算法一词，采用双倍体编码， 发展了复制、交叉、变异、显性倒位等遗传算子。同时他还敏锐的觉察到防止 早熟收敛机理的重要性，并发展了自组织遗传算法的概念。与此同时，r o s e n b e r g 1 3 在他的博士论文中进行了单细胞生物群体的计算机仿真研究，他的工作为遗传 算法在函数优化中的研究和应用提供了基础。 7 0 年代初，h o l l a n d 提出了遗传算法的基本定理一模式定理( s c h e m a t h e o r e m ) ，奠定了遗传算法的理论基础。1 9 7 5 年，h o l l a n d 出版了第一部系统 论述遗传算法和人工生命自适应系统的专著自然系统和人工系统的适配 ( a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m s ) ) ) ，该书详细阐述了遗传算法的理论， 为其奠定了数学基础，发展了一套模拟生物自适应的理论，同年，d ej o n g 在 其论文遗传自适应系统的行为分析( a na n a l y s i so ft h eb e h a v i o ro fac l a s so f g e n e t i ca d a p t i v es y s t e m ) 中结合模式定理进行了大量纯数值优化实验，将选 择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟( g e n e r a t i o n g a p ) 等新的遗传操作技术，建立了著名的d ej o n g 五函数测试平台，定义了评 价遗传算法性能的在线指标和离线指标，并以函数优化为例，对遗传算法六种 方案的性能及理论机理进行了详细的实验分析。 8 0 年代，对遗传算法的理论研究更为丰富和深入。b r i n d l e 在她的博士论 文中讨论了六种复制策略，以克服d ej o n g 的轮盘赌选择操作中的随机误差。 h o l l a n d 实现了第一个基于遗传算法的机器学习系统一分类器系统( c l a s s i f i e r s y s t e m ) ，建立了基于遗传算法的机器学习的新概念，为分类器的构造提出了 一个完整的框架。1 9 8 9 年，g o l d b e r g 出版了专著搜索、优化和机器学习中的 遗传算法( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ， 系统总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理 和应用，奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者 所瞩目。 9 0 年代是遗传算法研究与应用的黄金年代，有关遗传算法的研究与应用的 文章有数千篇之多，这是有许多学者认识到遗传算法在求解n p 完全问题及非 线性模型、多目标的函数优化问题时有着不可比拟的优越性。其中，d a v i s 编辑 出版了( ( h a n d b o o ko f g e n e t i ca l g o r i t h m s ) ) ，书中包括了遗传算法在科学计算、 工程技术和社会经济中的大量应用实例，为推广和普及遗传算法的应用起到了 重要的指导作用；k o z a 将遗传算法应用于计算机程序的优化设计及自动生成， 提出了遗传编程( g e n e t i cp r o g r a m m i n g ，简称g p ) 的概念，成功地将其应用于 1 4 人工智能、机器学习、符号处理等方面。 目前在遗传算法的研究中，尽管还存在一些有争议的问题，甚至还有某些 截然不同的学术观点和设计原则，一时尚难统一，整个遗传算法的理论基础还 比较薄弱，但是很多实例及应用充分表明，模拟自然进化的搜索过程往往可以 产生非常简单、通用和鲁棒性很强的计算方法。如今，无论是对遗传算法的理 论研究还是应用研究都分外活跃。 3 3 遗传算法的基本原理 遗传算法抽象于生物体的进化过程，通过全面模拟自然选择和遗传机制， 形成一种具有“生成+ 检验”特征的搜索算法。遗传算法以编码空间代替问题的 参数空间，以适应度函数为评价依据，以编码群体为进化基础，以对群体中个 体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程 1 4 1 。 遗传算法把问题的解表示成“染色体 ，在算法中也就是二进制编码的串。 并且，在执行遗传算法之前，给出一群“染色体 ，也就是假设解。然后，把 这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应 环境的“染色体 进行复制，再通过交叉，变异过程产生更适应环境的新一代 “染色体”群。这样，一代一代的进化，最后就会收敛到最适应环境的一个“染 色体 上，它就是问题的最优解。很明显，遗传算法是一种最优化方法，它通 过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到 一个特定的串，即求出最优解。 3 4 遗传算法的基本操作 在用遗传算法求解t s p 问题时，有下面几个因素是要着重考虑的： 3 4 1 编码形式 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实 际表示与遗传算法的染色体位中结构之间建立关系，即确定编码和解码运算。 编码就是将问题的解用一种码来表示，从而将问题的状态空间与g a 的编 1 5 码空间相对应，编码的选择是影响算法性能与效率的重要因素。 对于给定的优化问题，由g a 个体的表现型集合所组成的空间称为问题空 间，由g a 基因型个体所组成的空间称为g a 编码空间。遗传算子在g a 编码 空间中对位串个体进行操作。 编码应该适合要解决的问题，而不是简单的描述问题，问题编码一般应满 足以下几个原则： ( 1 ) 完备性：问题空间中的所有点( 潜在解) 都能成为g a 编码空间中的 点( 染色体位串) 的表现型。 ( 2 ) 健全性：g a 编码空间中的染色体位串必须对应问题空间中的某一潜 在解。 ( 3 ) 可扩展性：对于具体的问题，编码的大小确定了解码的时间，两者存 在一定的函数关系，若增加一种表现型，作为基因型的编码大小也应作出相应 的增加。 ( 4 ) 多重性：多个基因解码成一个表现型，即从基因型到相应的表现型空 间是多对一的关系，这是基因的多重性。若相同的基因型被解码成不同的表现 型，这是表现型的多重性。 ( 5 ) 个体可塑性：决定表现型与相应给定基因型是受环境影响的。 ( 6 ) 模块性：若表现型的构成中有多个重复的结构，在基因型编码中这种 重复是应当避免的。 ( 7 ) 冗余性：冗余性可提高可靠性和鲁棒性。 ( 8 ) 复杂性：包括基因型的结构复杂性、解码复杂性、计算时空复杂性。 ( 9 ) 非冗余性：染色体和潜在解必须一一对应。 以上特性有些是矛盾的。 按照遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估 准则，称为编码原理( b u i l d i n gb l o c k s ) ： ( 1 ) 有意义建筑模块编码规n - 编码应当生成与所求问题相关的短距和低 阶的建筑模块。 ( 2 ) 最小字符集编码规则：编码应采用最小字符集以使问题得到自然、简 单的表示和描述。 1 6 常用的编码方法有如下几种： ( 1 ) 二进制编码：二进制编码将问题空间的参数表示为基于字符集 0 ，1 ) 构成的染色体位串，是最常用的一种编码方式。 ( 2 ) 大字符集编码：除基于字符集 0 ，1 ) 的二进制编码之外，可以结合实 际问题的特征采用d 进制数或字符集来表示长度为l 的位申。 ( 3 ) 序列编码：采用g a 求解t s p 问题时，用排列法进行编码似乎更为 自然、合理。 ( 4 ) 实数编码：实数编码具精度高、大空间搜索的优点。 ( 5 ) 树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。 在搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的问题 解，实际应用中往往可以加以限制。 ( 6 ) 自适应编码：实现选择合适的固定编码方式对潜在的遗传算法用户来 说是一个难题。事实上，提出合适的编码同解决问题本身一样困难。因此，许 多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码呢? 一些专 家就采用了自适应编码。 ( 7 ) 乱序编码：g o l e b e r g 和他的同事提出了一种基于乱序编码的遗传算法， 用于提高函数优化和概念学习问题中g a 的搜索能力。其主要思想是促进短距 模式的检测和重组效率，降低模式被交叉算子破坏的概率。 3 4 2 初始种群的产生 初始种群的产生通常是随机产生，该方法可以产生足够数目的种群，但优 化度不高。 3 4 3 适应度函数及尺度变换 遗传算法在进化搜索中基本不用外部信息，仅以适应度函数为依据，利用 种群中每个个体的适应度值来进行搜索。因此适应度函数的选择至关重要，直 接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是 由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺度变 换。 1 7 计算适应度函数有两种基本方法。 方法一：直接把待求解的目标函数转化为适应度函数。 若目标函数为最大化问题 f i t ( f ( x ) ) = f ( x ) 若目标函数为最小化问题 f i t ( f i x ) ) = 一f ( x ) 方法二：若目标函数为最小问题，则 f i t ( 俐) = 融c g l a x 他八破八功q 式中c m a x 为最大值估计。 若目标函数为最大问题， 咧删) = 恬巍八功 式中c m i n 为最小值估计。 适应度函数的设计主要满足以下条件： ( 1 ) 单值、连续、非负、最大化：这个条件是容易理解和实现的。 ( 2 ) 合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达 成比较难以衡量。 ( 3 ) 计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和 空间上的复杂性，降低成本。 ( 4 ) 通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使 用者改变适应度函数中的参数。 适应度函数的尺度变换有线性变换法、幂函数变换法、指数变换法。 3 4 4 选择算子 用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。首先计 算适应度，可以选用按比例的适应度计算、基于排序的适应度计算；适应度计算 之后是实际的选择，即按照适应度进行父代个体的选择。选择方法有轮盘赌选 择、随机遍历抽样、局部选择、截断选择、锦标赛选择。 3 4 5 交叉算子 遗传算法的交叉算子是模仿自然界有性繁殖的基因重组过程，在该过程中 群