（计算机软件与理论专业论文）用混合遗传算法解决车辆优化配置数的研究.pdf

用混合遗传算法解决车辆优化配置数的研究 专业：计算机理论与软件 硕士：韦立军 指导教师：王甲海 摘要 随着市场经济的深入发展，作为“第三利润源泉”的物流在我国的生产、分配、 流通和消费的各个领域起着越来越重要的作用。配送是物流系统中很重要的一个环 节，在物流的各项成本中，配送成本占了相当高的比例。配送线路与运输车辆数成 为许多专家学者研究的焦点。降低运输成本，提高配送的及时性和配送的服务质量， 优化车辆配置问题，是降低企业成本的追切需要。因此对车辆优化配置数问题的研 究更加具有实际意义。 针对物流运输的车辆数优化问题，研究了该问题的数学模型，构造出了新的适 应度函数，应用适应度函数的良好的单调性质，提出了一种遗传模拟退火算法，实 现了车辆数的优化计算与最优车辆数下的路径优化计算。实验表明提出的混合遗传 算法能够有效地解决复杂的车辆优化配置数问题。 关键字：车辆数优化，适应度函数，混合遗传算法。 o p t i m i z a t i o no fn u m b e r o fv e h i c l ei nv e h i c l er o u t i n gp r o b l e m u s i n gh y b r i dg e n e t i ca l g o r i t h m s m a j o r ：c o m p u t es o f ta n dt h e o r y n a m e ：w e il i j u n s u p e r v i s o r ：w a n gj i a h a i a b s t r a c t w i t ht h ed e v e l o p m e n to ft h em a r k e te c o n o m y , l o g i s t i c s ( t h i r dp r o f i ts o u r c e ) p l a y sa n i n c r e a s i n g l yi m p o r t a n tr o l ei np r o d u c t i o n ，d i s t r i b u t i o n ，c i r c u l a t i o na n dc o n s u m p t i o n d i s t r i b u t i o ns y s t e mi sa ni m p o r t a n tp a r to ft h el o g i s t i c s i t sc o s t sa c c o u n tf o rav e r yh i 曲 p e r c e n t a g ei nl o g i s t i c s v e h i c l er o u t i n gp r o b l e ma n dn u m b e r so f v e h i c l eh a db e c o m e f o c u so fm a n ys c h o l a r st os t u d y o b v i o u s l y , l o w e r i n gd i s t r i b u t i o nc o s t ，t r a n s p o r t i n gg o o d s t i m e l y , i m p r o v i n gt h es e r v i c eq u a l i t y s oo p t i m i z a t i o no fn u m b e ro fv e h i c l ep r o b l e mi s e x i g e n tt oe n t e r p r i s e s t h i sp a p e rr e s e a r c h e dt h em a t h e m a t i c sm o d e la b o u to p t i m a ln u m b e ro fv e h i c l eo f l o g i s t i c st r a n s p o r ts y s t e m ，a n dc o n s t r u c t e de n e r g yf u n c t i o ns h o w e db y ( 4 一1 ) ，( 4 - 2 ) ，( 4 3 ) a n df i t n e s sf u n c t i o ns h o w e db y ( 4 - 4 ) a n dm o r e ，t h ep a p e rf o u n dm e t h o da b o u ts o l v i n g o p t i m a ln u m b e ro fv e h i c l ea n dt h es h o r t e s tr o u t eu n d e rt h ec o n d i t i o na p p l y i n gt h e e x c e l l e n tm o n o t o n ep r o p e r t i e sa n dg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m s i ns i m u l a t i n g c a l c u l a t i o n ，t h i sc o m p u t a t i o nm e t h o dc o u l df i n dt h eo p t i m a ls o l u t i o no ft h i se x a m p l ei n v i - p r o b a b i l i t y1 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sg e n e t i ca l g o r i t h m sc a l ls u i tf o r s o l v i n gc o m p l e x i t yo fn u m b e ro fv e h i c l ei nv e h i c l er o u t i n gp r o b l e m k e y w o r d s ：o p t i m i z a t i o na b o u tn u m b e ro fv e h i c l e s ，f i t n e s sf u n c t i o n ，h y b r i dg e n e t i c a l g o r i t h m s - v i i - 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究工作所取得的成果。除文中已经注明引用的 内容外，本论文不包含任何其他个人或集体已经发表或撰写过 的作品成果。对本文的研究作出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 学位论文作者张孝乏亏 日期：纠年，。月日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定， 即：学校有权保留学位论文并向国家主管部门或其指定机构送 交论文的电子版和纸质版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆、院系资料室被查阅，有 权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者签砖孑季 日期：吁年，参月矿日 锄鲐研j 日期：训，年p 月们日 1 1 研究背景及意义 第一章引言 1 1 1 研究背景 物流( l o g i s t i c s ) 是2 0 世纪中期发展起来的- f - j 新兴学科，也是现代较有影响的学 科之一。它是指为了实现顾客满意，连接供给主体和需求主体，克服空间和时间阻碍 的有效、快速的商品、服务流动经济活动过程，以现代信息技术为基础，整合运输、 包装、装卸、搬运、仓储、流通加工、配送、回收加工及物流信息处理等各种功能而 形成的综合性物流活动模式。世界各国都已经意识到物流的重要性，尤其是在工业发 达国家，物流管理与物流技术己经得到了广泛的应用与发展，己成为适合于市场经济 发展的基础产业之一。 据中国物流信息中心统计测算，2 0 0 4 年，全国社会物流总额达3 8 4 万亿元，同比 增长2 9 9 ( 按现价计算) ，增幅比上年同期提高2 9 个百分点【1 1 。虽然我国物流发展持 续加速，但与国民经济发展的要求还相差甚远，这就要求我们对物流产业的各个环节 进行研究。 物流配送车辆路径问题是现代生产企业和物流管理中最重要的一个环节，据统计， 各国运输成本占国民生产总值的1 0 1 5 蒯5 t 2 1 。这就意味着运输系统的效率提高一 点就可以节约很多成本。只要我们能够将现有运输成本降低，我们的国民经济总体水 平就能出现一次新的飞跃，一次真正的飞跃。但是，目前我国现阶段物流服务的实施 有着不可回避的问题：物流技术、基础设施和装备条件还不够完善；物流效率低下； 物流业发展比发达国家落后。在这种严峻的形势下，大力推进现代物流产业发展，降 低运输成本，增强物流环节的服务质量，是提高物流效率的迫切需要。由于物流配送 问题是一个n p 难的问题，近年来国内外许多专家学者开展深入研究，取得了不错的成 绩，下面研究综述作简单的介绍。 1 1 2 课题研究意义 从上面论述了解到，物流的的整个系统工程中，物流运输系统资源优化问题是物 流中心为客户提供优质服务所要求解决的首要问题，也是物流中心节约成本、增加生 产效益所解决的重要问题。 它主要面临三个问题： ( 1 ) 物流中心选址问题： ( 2 ) 运输车辆的路径优化问题； ( 3 ) 运输车辆数目的优化配置问题。 其中第一、二个问题有许多专家与学者进行深入的研究，特别是路径优化问题 ( v e h i c l er o u t i n gp r o b l e m ，v r p ) ，详见下节综述以及提到的相关文献。特别对于车辆数 不确定的路径优化问题，曹亮用遗传算法与禁忌搜索算法取得了较为满意的结果【2 1 ，但 没有涉及到车辆数的优化计算，其车辆数是通过车辆的载重量与各个城市的货物需求 量估计出来的，对于有时间限制的路径优化问题来说，由于时间的约束，车辆的运货 量很难达到满载的程度，因而，他给出的公式无法进行估计，如本文事例按照文献【2 】 的公式估计应该是3 ，但是3 台车辆是无法在规定的时间内完成任务的。这远远达不到 规定的有限时间内要做到相应的物流配送。 k c t a n ，l h l e e ，q l z h u 等人提到提出了基于客户的编码方式【3 1 ，并用简单遗 传算法能够以一定的概率寻到最优解，是属于车辆路径优化问题，不是专门针对于车 辆数优化而设计的，虽然能够找到最优解，但能搜索到最优解的概率比较低。 在实际工作中，往往车辆数目的优化问题要比路径优化问题重要。我们曾与东莞 市某商业银行有过项目合作，他们提出能否优化银行中心金库中钱箱运输问题，如何 找到一个车辆最优配置数，保证安全，减小成本。由于东莞市地理位置较为特别二十 多个镇区与开发区，网点分散，但交通较便利( 半小时圈) ，而市总行的的总中心金库 的运输量一般很少有变化，即运输量一定，这时银行考虑得更多是车辆数目优化问题， 而不是路径优化问题，因为增加一台车辆，也就是增加一条运输线路，从而就要增加 一台车辆的投入，同时要多雇佣几个员工( 如司机、押送人员) 。车辆数的尽可能小，更 易确保安全。就是说增加一条线路的投入要比车辆多行一大段距离的成本大得多。因 此，在某些特定的工作环境中，车辆数目优化问题要比路径优化问题重要。 表1 1 市某商业银行中心金库增加一条路线的估计成本 预算项司机的工资押送员的工资运钞车辆的损耗其它开支 每天的成本1 5 0 元 1 5 0 元宰4 人2 0 0 元1 0 0 元 表1 1 估计增加一条运输线路的成本，那么所增加的成本可供运钞车辆行驶1 0 5 0 公里( 以1 元公里的运输成本进行计算) o 基于以上的原因，本文对物流中心运输车辆数目优化配置问题进行了研究，用混 合的遗传算法和模拟退火算法在w i n d o w s 2 0 0 0 x p 环境下实现了车辆数目的优化计算， 并解决了最优车辆数下的路径优化问题。 1 2 论文的主要工作 遗传算法是建立在自然选择和群体遗传学机理基础上的随机迭代和进化，具有广 泛适用性的搜索方法，近年来受到专家学者的广泛关注。模拟退火算法是基于金属退 火的机理而建立起来的一种全局优化方法，它能够以随机搜索技术找n i 商- j 题的全局最 优点，有很强局部搜索能力。将两种算法混合使用，通过算法编码、仿真测试，分析 数据，找出适应的优化配置数，有效地应用于实际生产工作，将获得良好的经济效益。 1 2 1 主要研究内容如下： ( 1 ) 通过大量参阅国内外文献，简单了解物流配送中v s p 的模型及求解方法，为本 文模型的提出和求解奠定基础。 ( 2 ) 描述本文模型的研究问题，根据特殊的物流配送要求，即运输车辆的优化配置 问题，要求在一定条件下找出车辆最优化配置，最小车辆的配置要求，建立混合混合 算法的车辆优化配置数学模型。 ( 3 ) 将建立的混合混合算法的车辆优化配置数学模型看作是一个复杂的组合优化问 题，根据求解问题的特征，对求解算法进行比较分析，具体举例提出求解算法的最优 模型的选择要求。用c + + 语言对算例编写程序对模型求解，确定物流配送车辆优化数。 最后对本文的研究工作做了总结，并指出了进一步的研究方向。 1 2 2 论文具体安排如下： 第一章引言，介绍了论文的课题的提出背景、研究内容及论文安排。 第二章遗传算法与模拟退火算法，介绍遗传算法的基本概念及其在物流配置的应 用研究。 第三章车辆优化配置数的数学模型，根据车辆优化配置数的求解，建立相应的数 学模型。 第四章混合遗传算法解决车辆优化配置数，根据数据模型，研究给出编码和解码， 提出算法构造。 ， 第五章计算分析及实验结果，进行仿真实验并对结果进行分析讨论。 第六章结论与展望，对混合型遗传算法求解车辆优化配置数的研究进行总结。 最后是参考文献、附录和致谢。 第2 章遗传算法与模拟退火 2 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是由美国密歇根( m i c h i g a n ) 大学的j o h n h o l l a n d 教授和他的学生们于上个世纪6 0 年代末到7 0 年代初提出的，是一种借鉴生物界自然 选择和进化机制发展起来的高度并行、随机、自适应搜索算法。遗传算法的基本思想 是基于d a r w i n 进行论和m e n d e l 的遗传学说。遗传算法使用种群代表一组解，通过对 当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代种群，并逐步使 种群进化到包含近似最优解的状态。由于该算法采用随机和选择对搜索空间无特殊要 求，无需条件。具有运算简单，收敛速度快等优点，尤其适用于处理传统方法难于解 决的复杂和非线性的问题。作为强有力且应用广泛的随机搜索和优化方法，遗传算法 可能是当今影响最广泛的进化计算方法之一。遗传算法目前已经在优化、机器学习和 并行处理等领域得到了越来越广泛的应用。 2 1 1 遗传算法的产生和发展 从六十年代开始，美国密切根大学教授h o l l a n d 4 , 5 j q ：始研究自然和人工系统地自适 应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论，通用程序 和机器具有适应任意环境的能力，他意识到用群体方法搜索以及选择、杂交等操作策 略的重要性。 在六十年代中期至七十年代末期，基于语言智能和逻辑数学智能的传统人工智能 十分兴盛，而基于自然进化的思想则遭到怀疑和反对，h o l l a n d 及数位博士生仍坚持了 这一方向的研究。b a g l e yj d 在1 9 6 7 年发明了“遗传算法 一词并发表了第一篇有 关遗传算法应用的论文，在他开创性的博士论文中采用双倍体编码，发展了与目前类 似的复制、交换、突变、显性、倒位等基因操作。他还敏锐地察觉到防止早熟收敛， 并发展了自组织遗传算法的概念。与此同时，r o s e n b e r g 在他的博士论文中进行了单细 胞生物群体的计算机仿真研究，对以后函数优化的研究有很大的启发，并发展了自适 应交换策略，c a b i c c h i o 于1 9 7 0 年研究了基于遗传算法的子程序选择和模式识别问题， 在模式识别问题上，采用整数编码，检索空间很大，他提出了以预选择策略保证群体 多样性，对遗传算法参数进行中心控制的方法。同年，w e i n b e r g 研究了生物体的计算 机仿真，他的贡献在于提出运用多层遗传算法来进行遗传算法参数自由化。1 9 6 8 年至 1 9 7 1 年，h o l l a n d 提出了重要的模式理论，建议采用二进制编码。 与前面几位博士不同，h o l l a n d 首次采用二进制编码来研究函数优化问题，并指出 了运用g r a y 码的一些优点，他研究了从生物系统引申各种不同的选择和配对策略。1 9 7 5 年树立了遗传算法发展史上的两块里程碑，一是h o l l a n d 出版了经典著作“a d a p t a t i o ni n n a t u r ea n d a r t i f i c i a ls y s t e m ”，该书是h o l l a n d 十几年间许多思想及其实现的结晶，详细 阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整套模拟生物自适应系统 的理论；二是d e j o n g 完成了其具有指导意义的博士论文“a n a n a l y s i so f t h eb e h a v i o r o f ac l a s so f g e n e t i c a d a p t i v es y s t e m ”，他深入领会了模式定理并做了严格的计算实验，给 出了明确的结论，他还建立了著名的d e j o n g 五函数测试平台，定义了性能评价标准， 并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细实验和分析，他 的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克服d e j o n g 的轮 盘选择操作的基因误差，b r i n d l e 于1 9 8 1 年在她的博士论文中研究了六种选择策略。 进入二十世纪八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入 困境，神经网络、机器学习和遗传算法等生物系统底层模拟智能的研究重新复活并获 得繁荣。g o l d b e r g 在遗传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士论文中 第一次把遗传算法用于实际的工程系统一煤气管道的优化，从此，遗传算法的理论研 究更为深入和丰富，应用研究更为广泛和完善。 ， 进入二十世纪九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题 为对象的科学方式得到学术界普遍认同，如广义进化综合理论，由于遗传算法能有效 地求解属于n p 类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得 到了多学科地广泛重视，一些学者也认识到求解复杂问题最优解是不现实的，故而寻 求近似解，而遗传算法是最佳工具之一。遗传算法在吸收遗传学、进化论及分子生物 学最新成果和在实验得到证明和证伪的同时本身也在不断发展。 2 1 2 遗传算法的基本特征 从数学角度看，遗传算法实质上是一种搜索寻优技术6 ，7 1 。它从某一初始群体出发， 遵照一定的操作规则，不断迭代计算，逐步逼近最优解，它有如下特点： ( 1 ) 智能式搜索：遗传算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式的 全面搜索，它是有指导的搜索。指导遗传算法执行搜索的依据是适应度，也就是它的 目标函数。利用适应度，使遗传算法逐步逼近目标值。 ( 2 ) 渐进式优化：遗传算法利用复制、交叉、变异等操作，使新一代的结果优越于 旧一代，通过不断迭代，逐渐得出最优的结果，它是一种反复迭代的过程。 ( 3 ) 全局最优解：遗传算法由于采用交叉、变异等操作，产生新的个体，扩大了搜 索范围，使得搜索得到的优化结果全是全局最优解而不是局部最优解。 ( 4 ) 黑箱式结构：遗传算法根据所解决问题的特性，进行编码和选择适应度。一旦 完成字符串和适应度的表达，其余的复制、交叉、变异等操作都可以按常规手续执行。 个体的编码如同输入，适应度如同输出。因此，遗传算法从某种意义讲是一种只考虑 输出与输入关系的黑箱问题。 ( 5 ) 通用性强：传统的优化算法，需要将所解决的问题用数学式子表示，常常要求 解该数学函数的一阶导数或二阶导数。采用遗传算法，只用编码及适应度表示问题， 并不要求明确的数学方程及导数表达式。因此，遗传算法通用性强，可应用于离散问 题及函数关系不明确的复杂问题，有人称遗传算法是一种框架型算法，它只有一些简 单的原则要求，在实施过程中可以赋予更多的含义。 ( 6 ) 并行式算法：遗传算法是从初始群体出发，经过复制、交叉、变异等操作，产 生一组新的群体。每次迭代计算，都是针对一组个体同时进行，而不是针对某个个体 进行。因此，尽管遗传算法是一种搜索算法，但是由于采用这种并行计算机原理，搜 索速度很高。 2 1 3 基本遗传算法 基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了 许多不同的编码方法来表示问题的可行解，开发出了许多不同的遗传算子来模仿不同 环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不 同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选 择( s e l e c t i o n ) 、交3 7 , ( c r o s s o v e r ) 、变异( m u t a t i o n ) 机理的模仿，来完成对问题最优解的自 适应搜索过程。基于这个共同点，g o l d b e r g 总结出了一种统一的最基本的遗传算法一 基本遗传算法( s i m p l e g e n e t i ca l g o r i t h m s ，简称s g a ) 。从这里只简单介绍基本遗传算 法的编码及应用。 基本遗传算法只使用选择算子、交叉算子、和变异算子这三种基本遗传算予，其 遗传进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。 基本遗传算法的构成要素： ( 1 ) 染色体编码。 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是 由二值符号集 o ，1 ) 所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来 生成。 如： x = 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 就可表示一个个体，该个体的染色体长度是n = 1 8 。 ( 2 ) 个体适应度评价。 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下 一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应到个体适应 r 度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。 ( 3 ) 遗传算子。 基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子；交叉运算使 用单点交叉算子；变异运算使用基本位变异算子或均匀变异算子。 ( 4 ) 基本遗传算法的运行参数。 基本遗传算法有四个运行参数需要提前设定： m ：群体大小，即群体中所含个体的数量，一般取为2 0 1 0 0 。 t ：遗传运算的终止进化代数，一般取为1 0 0 5 0 0 。 p c ：交叉概率，一般取为o 4 0 9 9 。 p m ：变异概率，一般取为0 0 0 0 1 0 1 0 。 2 2 遗传算法的简单技术 2 2 1 编码 如何将问题的解编码成为染色体是遗传算法使用中的关键问题。比如当个体需要 解码成为何解时从基因型空间到表现空间的映射性质，以及个体被遗传算子操作时的 变形特性等。遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结 构重组处理，从而不断地搜索出群体中个体结构相似性。由此可见，遗传算法不能直 接处理问题空间的参数，必须把它们转成遗传空间的由基因组成的染色体或个体。首 先要把实际问题的有关参数和可能解集( 问题空间) 转换为g a 空间的代码串，该代码串 能够表示的全体编码，这一转换操作称为编码：当用g a 方法求得满意解后，再将其 对应的代码串转为实际问题的解，这一转换操作称为解码。从数学角度来看，编码是 从问题空间到表示空间的映射，解码为其逆映射【8 邶j 。 遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数 据，这些串结构数据的不同组合便构成了不同的点。 传统的遗传算法一般使用浮点数编码和二进制编码。浮点数编码使用一组浮点数 表示问题的一个解，而二进制编码使用一个二进制数序列表示问题的一个解。为了使 用遗传算法求解v r p ，大量研究者设计了多种适合v r p 解表示的编码方式，主要包括： 路径编码方式，该编码方式中，每个个体由区间【1 ，m + n - 1 】中互不相同的自然数序列构 成，即n 个客户，其中1 n 表示客户，m 个配送中心，其中n + 1 - - n + m 1 表示配送中 心。 例如，若有2 辆运输车和5 个客户，则个体为2 1 3 5 4 表示的两条配送路径为：配 送中心一2 1 3 一配送中心，配送中心一5 4 一配送中心。 二元组编码方式，该编码方式对有n 个客户的v r p ，编码长度为n ，每位由二元 组( 客户编号，车辆编号) 表示。 2 2 2 适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。 遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯 一要求是，针对输入可计算出能加以比较的非负结果。例如：在车间作业调度问题中 的目标函数，就是寻求一个调度，该调度的全部工序完成所需时间( 包括机器的执行 时间和等待时间) 最短。本文的车辆优化配置数的目标函数，就是要找出满足中心金 库运输钱箱的最小的车辆配置数。 适应度函数的设计主要满足以下条件： ( 1 ) 单值、连续、非负、最大化这个条件是很容易理解和实现的。 ( 2 ) 合理、一致性要求适应度值反映对应解的优劣程度，这个条件的达成往往比较 难以衡量。 ( 3 ) 计算量小适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复 杂性，降低计算成本。 ( 4 ) 通用性强适应度对某类具体t - j 题，应尽可能通用，最好无需使用者改变适应度 函数中的参数。 几种常见的适应度函数： ( 1 ) 直接以待求解的目标函数的转化为适应函数，即： 若目标为最大化l 口- j 题； 若目标为最小化l - j 题。 这种适应度函数简单直观，但存在两个i 口- j 题，其一是可能不满足常用的轮盘赌选 择中的概率非负的要求；其二是某些待求解的函数值分布上相差很大，由此得到的平 均适应度可能不利于体现这种群的平均性能，影响算法的性能。 ( 2 ) 若目标函数为最小i 口- j 题，则 触蛳胪卜一譬嚣冰 协， 其中c 懈为f ( x ) 的最大估计。 若目标函数为最大问题，则 触毗舻p 一锚p 协2 ， 其中c 幽为f ( x ) 的最小估计。 这种方法是针对第一种方法的改进，可以成为“界限构造法，但有时存在界限值 预先估计困难、不可能精确的l 口- j 题。 ( 3 ) 若目标函数为最小问题，则 施( m ) ) = 杰c o c 坝啦。 ( 2 - 3 ) 若目标函数为最大问题，则 加p 船( ( x ) ) = 去c 。，c f ( x ) 。 ( 2 - 4 ) 这种方法与第二种方法类似，c 为目标函数界限的保守估计。 2 2 3 遗传算子 遗传算法是一种结合了有向和随机两种能力的通用搜索方法，该算法可以在对搜 索空间进行深度和广度搜索之间维持很好的平衡。由选择机制来深度搜索积累的信息， 由遗传算子来广度搜索空间中新的区域。从搜索能力和角度来看，期望设计出能够同 时具有随机搜索( r a n d o ms e a r c h ) 和局部搜索( 1 0 c a ls e a r c h ) 两种能力的方法，c h e n g 和g e n 提出了设计的遗传算子的方法【1 1 1 。 ( 1 ) 选择算子( r e p r o d u c t i o no p e r a t o r ) 选择算子遗传算法使用选择算子( 或称复制算子) 来对群体中的个体进行优胜劣汰 操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗 传到下一代的概率较小。 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体 遗传到下一代群体中的一种遗传运算。选择操作建立在对个体的适应度进行评价的基 础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。下 面介绍几种常用的选择算子。 适应度比例方法 比例选择方法是一种回放式随机采样的方法。其基本思想是：各个个体被选中的 概率与其适应度大小成正比，适应度越高的个体被选中的概率越大；反之，适应度越 低的个体被选中的概率越小。由于是随机操作，这种选择方法的选择误差比较大，有 时甚至适应度较高的个体也选不上。 ” 最佳个体保存方法 在遗传算法中，通过对个体进行交叉、变异等遗传操作而不断产生出新的个体。 虽然随着群体的进化过程会产生出越来越多的优良个体，但由于选择、交叉、变异等 操作的随机性，它们也有可能破坏当前群体中适应度最好的个体。这是我们不希望发 生的，因为它降低了群体的平均适应度，对遗传算法的运行效率、收敛性产生了不利 的影响。所以，我们希望适应度最好的个体要尽量保留到下一代群体中。为达这一目 的，可以使用最佳个体保存方法来进行选择操作，让群体中适应度最高的个体不进行 配对交叉而直接复制到下一代。 排序选择方法 所谓排序选择方法是指在计算每一个个体的适应度后，根据适应度的大小对群体 中的个体进行排序，然后把事先设计好的概率表按序分配给个体，作为各个个体的选 择概率。这种选择方法的主要着眼点是个体适应度之间的大小关系，并不考虑个体适 应度之间的差异程度。此种方法的不足之处在于选择概率和序号的关系需事先确定。 此外，它适应度比例方法一样都是一种基于概率的选择，所以仍有统计误差。 联赛选择方法 这也是一种基于个体适应度之间大小关系的选择方法。其操作思想是每次从群体 中任意选择一定数目的个体( 称为联赛规模) ，其中适应度最高的个体保存到下一代。这 一过程反复执行，直到保存到下一代的个体数达到预先设定的数目为止。通常，联赛 的规模取为2 0 。 排挤方法 自然界中，当一种群的个体大量繁殖生存时，为争夺有限的生存资源，群体中个 体之间的竞争压力必然加剧，因此，个体的寿命和出生率也因此而降低。基于这种机 制，d e j o n g 提出了排挤选择方法。采用该方法时，新生成的子代将替代或排挤相似的 旧父代个体。该方法可提高群体的多样性。 在过去的2 0 多年中，h o l l a n d 提出的轮盘赌选择是最知名的选择方式【1 2 】。其基本 原理是根据每个染色体适应值的比例来确定该个体的选择概率和生存概率。 ( 2 ) 交叉算子( c r o s s o v e ro p e r a t o r ) 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体从 而产生出新的个体或物种。交配重组是生物进化过程中的一个主要环节。模仿这个环 节，也使用交叉算子来产生新的个体，这种方法称交叉算子。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换 其部分基困，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化运算的重 要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。遗传算法中，交 叉运算前还必须先对群体的个体进行配对。目前常用的配对算法策略是随机配对，即 将群体中的m 个个体以随机的方式组成m 2 个配对体组，交叉操作是在这些配对个体 组的两个个体之间进行的。常用的几种交叉算子有：离散实值重组，二进制交叉等。 ( 3 ) 变异算子( m u t a t i o no p e r a t o r ) 在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然的 因素的影响而产生一些复制差错，这样会导致生物的某些基因发生某种变异，从而产 生出新的染色体，表现出新的生物性状。模仿生物遗传和进化过程中的变异环节，在 遗传算法中也引入了变异算子来产生新的个体。 遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因 值用该基因座的其他等位基因来替换，从而形成一个新的个体。从遗传运算过程中产 生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的 全局搜索能力：而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个步 骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子的相互配合，共同 完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完 成最优化问题的寻优过程。 在遗传算法中使用变异算子主要有以下两个目的： 改善遗传算法的局部搜索能力。遗传算法使用交叉算子己经从全局的角度出发 找到了一些较好的个体编码结构，它们己接近或有助于接近问题最优解。但仅使用交 叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码 串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗 传算法的局部搜索能力。 维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因 值，从而可以改变个体编码串的结构，维持群体的多样性，这样有利于防止出现早熟 现象。 2 2 4 遗传算法的关键参数确定 ( 1 ) 群体规模1 1 群体规模影响遗传算法优化的最终结果以及遗传算法的执行效率。当群体规模n 太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模则可以减少遗传 算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂度高。一般取n 从1 0 到1 6 0 之间。 ( 2 ) 杂交概率p c 杂交概率p c 控制着杂交操作被使用的频度。较大的杂交概率可以增强遗传算法开 辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性也增大。若杂交概率太低， 遗传算法搜索可能陷入迟钝状态。一般取p c 从o 2 5 到1 0 0 之间。 ( 3 ) 变异概率p m 变异在遗传操作中属于辅助性的搜索操作，它的主要目的是维持解群体的多样性。 一般，低频度的变异可防止群体中重要的、单一基因的可能丢失，高频度的变异将使 遗传算法趋于纯粹的随机搜索。通常取变异概率p m 为0 0 0 1 左右。 2 3 遗传算法应用概况 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，遗传算法的应用 按其方式可分为三大部分，即基于遗传的优化计算，基于遗传的优化编程，基于遗传 的机器学习，分别简称为遗传计算、遗传编程、遗传学习。 2 3 1 遗传计算 g a 最直接、最简单的应用，其应用面也最广。自d e j o n g 起，函数优化己成为典 型例子，常采用二进制编程，目前使用实数编码的研究增多，与函数优化问题区别最 大的是组合优化问题，使用序号编码，使用特殊的交换操作。遗传算法己渗透到许多 学科，如工程结构优化、计算数学、制造系统、航空航天、交通、计算机科学、通信、 电子学、电力、材料科学等等。 2 3 2 遗传编程 遗传算法除了优化计算以外还可以应用于更为复杂的情况，而要求强有力的编码 表达最为关键。 k a z a ，d e j o n g 等发展了遗传编程的概念。k a z a 运用l i s p 编程语言来编码，l i s p 符号串表示树，串由特定问题域的各种函数和终端组成，群体进行复杂超平面的搜索， k a z a 成功地把遗传编程用于人工智能、机器学习、符号处理等。遗传编码是遗传算法 应用的深入，目前还不成熟，许多问题有待解决。 2 3 - 3 遗传学习 遗传学习系统是由g a 为内核构成的增强式学习系统，一般地，群体由产生式规 则组成，利用和环境的接触来学习、完成给定任务。遗传学习己被应用于许多领域， 在机器人学中，w i l s o n 运用分类器系统进行了传感器一马达地协调研究，然后发展了 a i v i m a t 系统，进行模拟人工生物环境中自主适应的研究，d o r i g o 结合遗传学习和基 于行为的机器人学进行了简单的、模拟生物在变化环境中学习趋光和避热两种行为模 式的研究。遗传学习还应用于模式识别等。遗传学习本身的研究也正在深入。 遗传算法是一种全局搜索能力很强而局部搜索能力不足的算法。研究发现，遗传 算法可以用极快的速度达到最优解的9 0 左右。但要得到真正的最优解则要花费很长 的时间【13 1 。所以单以其解决本文的问题是不科学、不全面的。 2 4 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m s ，s a ) 是1 9 8 3 年由k i r k p a t r i c k s 等 人首次提出的随机性搜索算法。特别是n p 完全完全问题的通用启发式算法，它以优 化问题求解过程与物理系统退火过程之间的相似性为基础，利用m e t r o p o l i s 准则并适 当地控制温度的下降过程实现模拟退火，从而达到求解全局优化问题的目的。目前， 该类优化方法被认为与其它方法一样具有竞争力，现己在工程中得到较广泛应用，如 旅行商问题、生产调度、机器学习、物流配送路径、图像处理等领域。 2 4 1 模拟退火算法思想 模拟退火算法的基本思想就是用物质系统的退火过程来模拟优化问题的寻优过 程，当物质系统达到最小能量状态时，优化问题的目标函数也相应地达到全局最优值 【1 4 】 o 设优化问题的一个解f 等价于固体的一个微观状态f ，其目标函数f ( o 等价于固体 能量e ，用随算法进程递减的控制参数t 担当固体退火过程中温度t 的角色，则对于t 的每一取值，算法持续进行“产生新解一判断一接受舍弃 的迭代过程就类似于固体 在某一温度下趋于热平衡的过程，也就是执行了一次m e t r o p o l i s 算法。模拟退火算法 从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时优化问题的相 对最优解；然后减小t 的值，重复执行m e g o p o l i s 算法，就可以在t 趋于0 时，得到优 化问题最终的全局最优解。固体必须徐徐降温，才能使其在每一温度下都达到热平衡， 最终趋于能量最小的基态；温度t 也必须缓慢递减，才能确保模拟退火算法最终趋于优 化问题的全局最优解。 模拟退火算法用m e t r o p o l i s 算法产生优化问题解的序列，并由与m e t r o p o l i s 准则相 对应的概率转移。 i 1 厂( i ) f ( j ) 默旧力2 i e x p ( 垃掣) 朋 5 确定是否进行从当前解i 到新解j 的转移。由式( 2 5 ) 可知，系统温度t 决定着随机 移动的转移( 接受) 概率。温度越高，则算法接受使目标函数上升移动的能力越强，具有 较强的“爬山”能力，温度很低则使目标函数值上升移动的接受概率很低。 2 4 2 模拟退火算法特性 模拟退火算法在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随 机因素，而且还引入了物质系统退火过程的自然机理。模拟退火算法依据m e t r o p o l i s 准则接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这正是模拟 退火算法优于局部搜索算法的本质区别所在。开始时，t 的值较大，可能接受较差的恶 化解，随着t 的减小，只能接受较好的恶化解，最后在t 趋于零时，就不再接受任何恶 化解了，这就使模拟退火算法可以从局部最优的陷阱中跳出，最后求出近似整体最优 解。 需要说明的是，由于模拟退火是随机搜索算法，尽管理论上以概率l 收敛于全局 最优解，但实际应用中由于参数选取及时间条件的限制，一般只能得出优化问题的某 近似最优解。而且算法的随机性也会导致优化结果的不确定性，即每次优化计算结果 是不确定的。模拟退火算法的状态产生和接受操作每一时刻仅保留一个解，缺乏冗余 和历史搜索信息；算法的优化行为对退温历程具有很强的依赖性，而理论上的全局收 敛对退温历程的限制条件很苛刻，因此它的优化时间性能较差。 2 4 3 模拟退火算法的结构 模拟退火算法的基本思想是：从选定的初始解开始，在借助于控制参数递减时产 生的一系列m a p k o b 链中，利用一个新解产生装置和接受准则，重复进行包括“产生 新解一计算目标函数差一判断是否接受新解一接受抛弃新解”这四个步骤的过程，不 断对当前解进行迭代，当t 值趋于0 时，整个系统趋于平衡状态，从而使目标函数达到 最优。基本的模拟退火算法详细步骤如下： s t e p l ：任意选取一个初始状态f ( 初始解，o ) ，令迭代次数k = l ；并设定一个较高 的起始温度t ； s t e p 2 ：求目标函数厂( x ) 的函数值； s t e p 3 ：如果该函数值在该温度下满足内循环停止条件转s t e p 4 ，否则在当前状态f 的一个邻域内随即选一个新状态- ，若，将钙= 厂( x ，) 一厂 ，) o ，将x j 取代一；成 为新状态，若钙o ，以e x p ( 一钙) r a n d o 朋( o ，1 ) 的概率接受新状态x ，。若不接受新 状态，重复s t e p 3 ； s t e p 4 ：按照退火时间表降低温度，迭代次数k = k + 1 ，若满足外终止条件。 输出结果，否则回到s t e p 2 ； 下面图2 1 是模拟退火算法的流程图。 图2 1 模拟退火算法的流程图 2 4 4 模拟退火算法的参数设定 从图2 1 看，模拟退火可直观理解为：在一个给定的温度，搜索从一个状态随机 地变化到另一个状态，每个状态到达次数服从一个概率分布。对模拟退火算法而言状 态产生函数，状态接受函数，温度更新函数，内循环准则