遗传算法在解决经典运筹问题中的应用

［提要］ 本文主要阐述遗传算法的特点，以及在解决运筹经典问题中的应用和不足之处。

关键词：遗传算法；运筹学；应用

中图分类号：F27 文献标识码：A

收录日期：2011年10月28日

一、遗传算法简介

遗传算法（GAS）是由美国密执根大学的Holland等人创立的。与其他启发式方法顺序搜索解空间的工作方式不同，遗传算法采用解的种群作为工作单元，使用模仿生物进化的适者生存原则指导搜索并改进目标。种群由代表个体的定长字符串组成，每个个体表示解空间的一个点，每个解的质量，通过依赖于问题目标函数的适应值函数来进行评估。搜索过程通过进化来进行，每代中的个体以正比于它的适应值的概率遗传到下一代。它使用3个基本算子：选择、交叉和变异。选择是指个体以其适应值比例复制到交配池中；交叉是交配池中的两个个体进行交配，组合形成一个（或几个）新个体，复制和交叉将好的特性进行遗传；变异则是发生在少数字符串某基因位上的基因的突变，它使搜索过程能够有机会从搜索到的局部最优解逃出。

解决一个实际问题的遗传算法通常包括下列两个决策步骤：（1）将求解问题模型化为符合遗传算法的框架。可行解空间的定义，适应值函数的表现形式，解的字符串表达式方式；（2）遗传算法参数的设计。种群规模，复制、交叉、变异的概率选择，进化最大代数，终止准则设定等。

二、遗传算法的基本特点

（一）结构特点。遗传算法是以适应值提供的启发式信息进行搜索的，与其他启发式（模拟退火、爬山法、神经网络等）方法相比，在结构和工作过程方面的特点见表1。（表1）

（二）实验性能方面的特点

1、高效性。遗传算法具有大范围全局搜索的特点，与问题领域无关，前期工作量比较少。

2、健壮性。遗传算法的搜索是用种群作为基本单元，采用三个不同作用的基本算子进行搜索的，解的结果随时间增加而趋于稳定，不受初始解的影响，而且不因实例的不同而蜕变。

3、通用性和灵活性。遗传算法可用于多种优化搜索问题，解题程序可以通用，针对不同的实例，适当调整算子参数，就可以使算法执行获得最佳的解结果和占用CPU机时的关系。

三、遗传算法在解决经典运筹问题中的应用

（一）旅行商问题（TSP）。旅行商问题自诞生以来，颇受数学家推崇，今天的旅行商问题已远远超过其本身的含义，成为一种衡量算法优劣的标准。旅行商问题是采用非标准编码遗传算法求解最成功的一例，基因编码用推销员顺序经历的城市名表示，求最佳路线即是改变编码次序而求最低适应值的问题。对类似字符串使用标准交叉，产生的后代可能有重复或丢失的元素，因而成为非可行解。为克服这种困难，人们提出许多非标准的交叉和变异方法：交叉主要采用重排序方法——部分匹配重排序，顺序交叉和循环交叉等；变异主要采用位点、反转、对换、插入等方法，使旅行商问题得以有效地解决。值得一提的是，清华大学张雷博士提出的自适应多点交叉算子，能够保证多点交叉后路径的可行性，加快了搜索速度。

（二）作业调度问题。作业调度问题同样是自然变更次序的问题，可以用基于变更次序的遗传算法进行处理。（表2）

（三）背包问题。一维、二维和三维背包问题在商业和工业领域有着广泛的应用，基于遗传算法的求解方法很多。传统求解采用启发式规则，决定下一步该装哪一块和装在哪里，此时变更次序的编码与启发式安置策略是利用遗传算法解决这类问题的最为出色的方法，Lin使用一系列的惩罚项指导其搜索策略，测定单个个体的适应值。

Bortfeldt使用一个层次背包问题，个体用它们的层次代表，当两个亲代被选择交叉时，它们的层次混在一起，从中选择最好的作为子代的第一层，再从余下的组件中选择最好的作为第二层，以此类推，直至产生所有的层次。

陈国良等设计了一种“与/或”交叉方法，使子代继承双亲的同型基因，对杂型基因采用不同支配方式，这种策略为遗传算法的硬件实现创造了良好的条件。

（四）时刻表排定问题。Corne对Edinburgh大学7日内的28个时间期间安排40门课的考试问题作了处理，寻找一个可行的时间排定表，使每个学生参加的考试在时间上能够错开，时刻表用字符串代表，字符串每个位置代表一门课，该位置的值代表考试的时间，用均匀交叉和标准变异操作求解。

这类问题扩展到基于二维的矩阵代表的逼近问题，Colorini使用行代表教师列代表可用的小时数的矩阵，每个单元的值为教师在此时承担的任务，包括教室和其他一些资源配置，教师的任务是事先给定的，故行都是可行的，列代表的时间安排可能会发生冲突，将此冲突用惩罚函数表示在适应值函数中，而且采用修复算子在评价之前尽量将结论调整回可行区域内，该算法用Milan学校的实际数据进行了检验。

除此之外，遗传算法在运输问题、指派问题、分割问题及网络计划优化问题等方面都获得了非常成功的应用，这些问题被认为是NP类问题，其规模随变量的增加呈指数增长，遗传算法在这些问题的求解中，充分体现了其操作性能方面的优势。

四、应用和推广中存在的问题

在上述问题中，遗传算法求解展示了优良的性能，但遗传算法并未像其他启发式方法那样容易地被OR学者广泛接受而用于大量的实际问题中，究其原因，主要有以下几点：

（一）传播方式的障碍。遗传算法最初的工作是以密执根大学严谨的研究小组作为研究项目和学术讨论中心，当研究成员扩大时，这类讨论会演变为机构的学术会议（美国现有5个，欧洲有3个，我国目前还没有），许多研究者聚于此而远离问题导向，有关的会议论文公开出版数量很少，而且，由于历史原因，研究者常常将他们的研究结果选择在有关人工智能的杂志上发表，导致了应用遗传算法的信息很缓慢地扩散到其他不同技术应用领域的工作者中，这与模拟退火等其他启发式方法快速在运筹学会议及杂志上发表相反。由于缺乏交流导致了两方面的问题：一是许多关于遗传算法的论文不能与从其他方法得到的结论进行质量的比较，二是削弱了许多遗传算法多的潜在使用者用遗传算法与其他方法竞争的信心。

（二）术语的隔膜。初始跨入遗传算法领域的使用者常常感到起步非常艰难，遗传算法依赖于遗传学的术语也像模拟退火的术语来自于统计热力学一样。然而，温度、冷却等可能很快赋予新的意义，但遗传算法中的基因位、染色体、遗传型却难以很快被人理解和接受；另外，许多发表的研究偏重于用某些专门函数检验他们的新思路或新设想，这对于全面理解该技术固然是一件好事，但对于一个面对如此丰富复杂材料的初用者会发现，他将不知从何做起。即使一个非常愿意使用遗传算法的人，也要有足够的决心去克服上述障碍。

（三）方法的局限性。对于具有强约束的优化问题，采用惩罚函数逼近常常达不到预想的结果。Radcliffe评论说：“约束通常被认为是遗传算法面临的最大问题”因为惩罚因子选择不当时，会招致错误结论。目前，求解带约束优化问题的启发式遗传方法已经有了一些，但是，它们多数与问题领域相关，在这方面还缺少普遍适用的方法的系统研究。

（四）编码的困难。不是所有问题解空间中的点都能明显地用编码表示，作为OR研究者，常常从问题结构取得利益，用矩阵、树、网络或其他更适用的方法建立表达式；串表达中的建筑块假说建议适用较少的字符，导致人们对二进制编码的偏爱，但二进制编码具有一定的映射误差（实际计算时，我们是把问题作为整数规划），特别是它不能直接反映出所求问题本身结构特征，因此很难满足生成有意义的积木块编码原则；再者，二进制字符的长度随问题发生明显变化，当问题复杂时会因为编码太长而无法进行正常工作。

以上的种种阻力，在一定程度上减缓了遗传算法在运筹学实际问题中的推广和应用。

主要参考文献：

[1]陈国良等.遗传算法及其应用.北京：人民邮电出版社，1996.6.

[2]胡运权.运筹学.北京：清华大学出版社，2007.4.

[3]Michalewicz Z.Evolutionary computation techniques for non-linear programming problems.Trans.Opl.Res.1994.2.