（运筹学与控制论专业论文）遗传算法求解投资组合决策和流水车间调度问题的研究.pdf

中文摘要 遗传算法( g e n e t i ca l g o r i t h m ) 是基于进化论的原理发展起来的一种广为应用的、 高效的随机搜索与优化方法。自1 9 6 0 年以来，人们对传统方法很难解的复杂优化问题 求解的兴趣日益增加。一种模仿生物自然进化过程的、被称为“进化算法”的随机优化 技术在解这类优化难题中显示出了通常优于传统优化算法的性能并且得到了很大的发 展和应用。目前，这种进化算法主要包括三个领域：遗传算法、进化规划和进化策略。 其中，遗传算法是迄今为止进化算法中最广为人知的算法，它在求解多目标问题中处 理大问题空间的能力是传统方法无法比拟的，而且它还对函数定义域的凸性是不敏感 的，这也使得遗传算法在金融数学、组合优化和工业工程等方向的单目标和多目标优 化问题求解中有很好的应用。 本文在广泛深入地查阅国内外文献的基础上，对遗传算法及其面向多目标求解的 理论和基本方法进行了研究和实例分析，主要内容如下： 1 系统、详尽的介绍了遗传算法的一般流程和基本理论、方法以及面向多目标优 化问题的遗传算法的基本理论和方法。 2 在传统m a r k o w i t z 投资组合模型中考虑了最小交易单位、交易费用以及最大投 资上限等时机因素，得到了一个改进的投资组合模型。该模型是一个非线性整数规划 问题，传统算法难以求解，为此，设计了一种基于整数编码的遗传算法求解该模型。 实际算例表明，所提出的算法是有效的。 3 对于最小化总工期和总拖后时间的双目标流水车间调度问题，文中基于 n s g a i i 算法的选择机制，设计了求解该问题的多目标遗传算法。用随机产生的问题 进行数值试验，结果表明，所提出算法是有效和稳定的。 关键词：遗传算法，多目标，n s g a 一，p a r e t o 解，投资组合，最小交易单位，交 易费用，车间调度，f l o ws h o p 调度 a b s t r a c t g e n e t i ca l g o r i t h mi sas t o c h a s t i cs e a r c ho p t i m i z a t i o na l g o r i t h mw h i c hi sm o r eu s e da n d e f f e c t i v e f r o m19 6 0 ，as t o c h a s t i co p t i m i z a t i o nt e c h n o l o g yc a l l e d e v o l u t i o n a r ya l g o r i t h m s ”， w h i c hs i m u l a t e st h en a t u r ee v o l u t i o n a r yp r o c e s s ，s h o w si t s9 0 0 dq u a l i t i e si ns o l v i n gt h e c o m p l e xo p t i m i z a t i o np r o b l e m sw h i c ha r eh a r dd o n eb yt h et r a d i t i o n a lo p t i m i z a t i o n a l g o r i t h m s n o wt h ee v o l u t i o n a r ya l g o r i t h m s h a st h r e er e s e a r c hl o c a t i o n s ：g e n e t i c a l g o r i t h m ，e v o l u t i o n a r yp r o g r a m m i n ga n de v o l u t i o ns t r a t e g i e s a n dg e n e t i ca l g o r i t h mi s m o s tu s e f u l ，i t sn o to n l yu s e df o rs i n g l eo b j e c t i v eo p t i m i z a t i o np r o b l e m s ，b u ta l s oc a nb e t t e r s o l v el o t so fm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s t h ep a p e rs t u d i e sa n da n a l y z e st h et h e o r i e sa n dg e n e r a la p p l i c a t i o n so ft h eg e n e t i c a l g o r i t h m sa n di ti n c l u d e sl a s tc o n t e n t s i t h ep a p e ri n t r o d u c e sr e l a t e db i o l o g yk n o w l e d g ea n dg i v e sab r i e fr e v i e wo ft h e d e v e l o p m e n th i s t o r yo fe a s t h e nt h ep a p e rc o n c l u d e st h em a i nc h a r a c t e r so f e a sa n ds u m s u pt h ep r e s e n ts i t u a t i o no ft h et h e o r i e sa n da p p l i c a t i o n so fe a s 2 b a s e do nt h ec l a s s i c a lm a r k o w i t zp o r t f o l i om o d e l ，a ni m p r o v e dp o r t f o l i oi sp r o p o s e d f o rp o r t f o l i o s e l e c t i o nw i t hm i n i n l u mt r a n s a c t i o nl o t s ，t r a n s a c t i o nc o s t sa n du p p e rl i m i to n t h em a x i m u ma m o u n to fi n v e s t e dc a p i t a li na n ys e c t t r i t y t h ep o r t f o l i os e l e c t i o nm o d e l i n g ， a san o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e m , i sd i f f i c u l tw i t ht h et r a d i t i o n a lo p t i m i z a t i o n m e t h o d s ag e n e t i ca l g o r i t h mb a s eo ni n t e g e rc o d i n gg e n e t i co p e r a t i o ni sd e s i g n e dt o p r o p o s et h em o d e l i ti si l l u s t r a t e dv i aan u m e r i c a le x a m p l e t h a tt h eg e n e t i ca l g o r i t h mc a nb e - u s e dt os o l v et h ep o r t f o l i oo p t i m i z a t i o np r o b l e me f f i c i e n t l y 3 f o rt h eb i o b j e c t i v ef l o ws h o ps c h e d u l i n gp r o b l e m sw h e r et h eo b j e c t i v e sa r et a k e nt o b et h em i n i m i z a t i o no fm a k e s p a na n dt o t a lt a r d i n e s st i m e ，am u l t i - o b j e c t i v eg e n e t i c a l g o r i t h mi sp r o p o s e dt oo b t a i nt h ep a r e t oo p t i m a ls o l u t i o n se f f i c i e n t l y t h i sm e t h o db u i l d s o l lt h es e l e c t i o ns t r a t e g yo fn s g a - i i ，c o m p u t a t i o n a le x p e r i m e n ti sp e r f o r m e do nt h et e s t p r o b l e m sg e n e r a t e dr a n d o m l y , a n dt h er e s u l t sd e m o n s t r a t et h ee f f i c i e n c ya n dr o b u s t n e s so f t h es u g g e s t e da 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 ，m u l t i - o b j e c t i v e ，n s g a i i ，p a r e t os o l u t i o n , p o r t f o l i o s e l e c t i o n ，m i n i m u mt r a n s a c t i o nl o t s ，t r a n s a c t i o nc o s t s ，j o bs h o ps c h e d u l i n g ，f l o ws h o p s c h e d u l i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得醴太堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：鹰l j ；巳明签字日期：矽7 年月罗f 3 学位论文版权使用授权书 本学位论文作者完全了解云望太堂有关保留、使用学位论文的规定。 特授权云望太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：孝晓l | 胄 签字日期：卅年月7 e t 导师签名：芬芬善卜 签字日期：3 口7 年厂月夕圣 天津大学硕士学位论文 遗传算法的理论与应用简介 第一章序言 遗传算法抽象于生物体的进化过程，是一种基于自然选择和遗传变异等生物进化 机制的自适应全局搜索算法。它是由美国m i c h i g a n 大学的h o l l a n d 教授于2 0 世纪6 0 年代提出的i 卜2 1 。当时h o l l a n d 教授的工作方向主要集中于生物学、人工智能等领域。他 注意到在建立智能机器的研究中，不仅可以完成单个生物体的适应性改进，而且通过 一个种群的许多代的进化也可以取得非常好的适应性效果。h o l l a n d 的基本思想是利用 二进制代码串构成的染色体来表示实际问题的参数。在每一代，对这些染色体进行变 换，利用染色体中所包含的适应值信息来决定新一代染色体；和生物进化过程的“突变” 过程相似，偶尔要在父代染色体中随机改变基因结构，产生具有新染色体的子代个体， 并最终得到问题的解。与自然界的生物进化过程相同，遗传算法对所要解决的问题类 型几乎没有限制，所需要的信息只是每个染色体的评价值。这种使用简单编码和选择 机制的算法能够解决相当复杂的问题，并且解决实际问题时不需要该领域的专门知识。 通过对这些简单的染色体进行迭代处理，从这些染色体中发现并保存好的染色体，进 而逐步发现问题的最优解。这些思想就是遗传算法理论的雏形。 7 0 年代b r e m e r m a n n , d ej o n g 等人将遗传算法应用于参数优化问题，极大的促进了 遗传算法的应用【3 】。8 0 年代g o r d b e r g 4 1 、d a r i s i 5 1 、g r e f e n s t e t t e t 们、b a u e r t 7 1 、s r i n i v a s 和p a m a i l 【t 8 】等大批研究人员对遗传算法理论的基本框架和遗传算子进行了构建和改 进，并将遗传算法分别应用于工程设计、自动控制、经济金融、博弈问题、机器学习 等诸多领域之中。由于其自身的隐性并行性、鲁棒性和随机性的优势，遗传算法对解 决这些领域的具体实践问题起到了极大的促进作用。 1 2 多目标遗传算法的发展过程及研究现状 最优化处理的是在一堆可能的选择中搜索对于某些目标来说是最优解的问题。如 果仅考虑一个目标，就成为单目标优化问题，这种问题在过去5 0 年中已经得到了深入 研究。如果存在的目标超过一个并需要同时处理，就成为多目标优化问题1 9 q o j 。多目 标优化问题起源于许多实际的工程决策问题。由于在考虑不同约束的同时要处理相互 冲突的目标，多目标问题一般都很复杂。自2 0 世纪6 0 年代以来多目标优化 ( m u l t i o b j e c t i v eo p t i m i z a t i o n s ) 问题就倍受关注。早在1 9 6 7 年，r o s e n b e r g 在研究中就 提出了在模拟单细胞有机物的化学遗传特性中采用多属性研究方法1 1 i ，这是遗传算法 首次应用到多目标优化问题。在过去的几年里，将遗传算法应用于多目标优化问题成 为研究热点，这种算法通常称为遗传多目标优化( g e n e t i cm u l t i o b j e c t i v eo p t i m i z a t i o n ) 。 天津大学硕士学位论文 用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个目标来 确定个体的适应值。适应值分配机制在过去的1 0 年中得到了广泛的研究，已经提出并 测试了若干种方法。这些方法可粗略分为：( 1 ) 向量评价方法( v e c t o re v a l u a t i o n a p p r o a c h ) 【1 2 】。该方法采用向量形式的适应值度量来产生下一代。( 2 ) 权重和方法。 该方法采用与传统多目标优化方法相同的基本前提，为每个目标函数分配权重并将权 重目标组合为单一目标函数。从概念上讲，该方法容易理解且便于计算，然而该算法 也存在困难之处。利用遗传算法的种群操作性，两者相结合就可削弱其弱点。因此又 提出了三种权重调整方法来充分利用遗传搜索的力量，分别为：固定权重方法，随机权 重方法，适应性权重方法。在固定权重方法( f i x e d - w e i g h ta p p r o a c h ) q b ，权重在整个进化 过程中不会改变：在m u r a t a , i s h i b u c h i 和t a n a k a 提出的随机权重方法( r a n d o m - w e i g h t a p p r o a c h ) 1 1 3 】中，选择过程中每一步都随机给出权值，以给所有可能的组合一个平等 的机会；在g e n 和c h c n g 提出的适应性权重方法( a d a p t i v ew e i g h ta p p r o a c h ) 中降1 5 1 ， 权重根据当前代进行适应性调整以获得朝向正理想点的搜索压力，它的选择压力介于 固定权重方法和随机权重方法之间。( 3 ) 基于p a r e t o 的方法( p a r e t o - b a s e da p p r o a c h ) 。 分为两种：p a r e t o 排序( p a r e t or a n k i n g ) 和p a m t o 竞争( p a r e t ot o u r n a m e n t ) 。p a r e t o 排 序法由g o l d b e r g 首先提出f 1 6 1 ，目的是使所有的p a r e t o 个体得到相同的复制概率。p a r e t o 竞争方法由h o r n ，n a f p l i o t i s 和g o l d b e r g 提出 1 7 】，该方法采用了小生境p a r e t o 概念，而 不是非支配分类和排序选择。( 4 ) 基于妥协的适应值分配方法( c o m p r o m i s e - b a s e df i t n e s s a s s i g n m e n tm e t h o d ) 由c h c n g 和g c n 在解决双目标最小路径问题时提出l l 射，该方法通 过某种距离的度量来确定与理想解最近的解。由此可以获得一个妥协解，而不是产生 所有p a m t o 解。( 5 ) 目标规划( g o a lp r o g r a m m i n g ) 是解决多目标优化问题的强大方法。 它的基本思想是给每个目标函数建立明确的数值目标，然后寻找一个其目标函数值到 对应目标的偏差之加权和最小的解1 1 9 。此法适用于目标函数是线性的或者是部分线性 的情况，对于非线性的情况它可能不太适用。 后来又出现了基于多种群的v e g a 、基于字典的方法和基于博弈论的方法等，这 些方法的缺点在于实用性较差、解的精度不高。目前多目标遗传算法的研究热点是基 于p a r e t o 机制的多目标优化技术，例如：m o g a l 2 0 】、s p e a i 2 1 1 、p a e s t 2 2 1 、n s g ar 2 3 1 、 n s g a i i t 2 4 】等。 m o g a 是由f o n s e c a 和f l e m i n g 于1 9 9 3 年提出的。其思想中体现了小生境技术、 共享因子和独特的个体排序方法。其优点是便于执行，缺点是相对于其它的p a r e t o 排 序技术，它更依赖于共享因子的合适选择。 s p e a 由z i t z l e r 和t h i c l e 于1 9 9 8 年提出。该方法使用了精英选择策略，这种策略 在以后的研究中被证明是有效的，并广为应用。 天津大学硕士学位论文 由k n o w l c s 和c o m e 于19 9 9 年提出的p a e s 则使用一个父代和一个子代比较的方 法来保持种群中个体的数量，同时在取舍中又兼顾了种群的多样性。 n s g a ( 非支配排序遗传算法) 由d c b 和s r i n i v a s 于1 9 9 3 年提出，其思想是使用 共享因子和p a r c t o 排序对个体分类。n s g a 一提出就得到了广泛应用。在应用中，人 们发现其在处理高维、多模态问题时结果不理想。n s g a 存在的主要问题有：( 1 ) 计 算量大，耗时；( 2 ) 缺乏精英选择策略；( 3 ) 需要特别指定共享半径蛔。 2 0 0 0 年，d c b 对n s g a 算法进行了改进，得到了n s g a - i i 算法。n s g a i i 解决了 n s g a 存在的问题，提出了快速非支配排序法，构建了新的交配池，提高了运算速度 和算法的鲁棒性。 1 3 本文所做的工作及安排 本文的第二章介绍了遗传算法和多目标遗传算法的基本概念和发展历史，展示了 遗传算法的基本操作流程并介绍了几种常见的多目标遗传算法。本文的第三章中，在 传统的m a k o w i t z 投资组合模型中考虑了最小交易单位、交易费用以及最大投资上限等 实际因素，我们得到了一个改进的投资组合模型。该模型是一个非线性的整数规划问 题，传统算法难以有效求解。我们设计了一种基于整数编码的遗传算法求解该模型。 最后用实际算例进行模拟计算，检验所提出的算法的有效性。在本文的第四章中，我 们提出了一种基于n s g a i i 选择机制的多目标遗传算法，来求解最小化总工期以及最 小化总拖后时间的双目标流水车间调度问题。并通过一系列随机测试实例检验该算法， 结果表明了该算法的有效性和稳定性。 天津大学硕士学位论文 第二章遗传算法概述 2 0 世纪4 0 年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的 新思想、新方法，比如早期的自动机理论就试图采用类似神经元的元素构造种新型 的思维机器。这种以生物系统为基础的计算机模拟研究经历了多次的复兴和衰落，2 0 世纪g o 年代以来在计算机领域再一次活跃起来。首先是人工神经网络，然后是机器学 习，当前即所谓的进化算法( e c ) 。遗传算法就是其中最重要的一个分支嘲。 遗传算法( g e n e t i ca l g o r i t h m ，g a s ) 是一种模拟自然界生物进化过程的全局随机搜索 算法，由美国m i c h i g a n 大学的h o l l a n d 教授于6 0 年代首先提出。它将计算机科学与进 化论的思想结合起来，依据达尔文“优胜劣汰，适者生存”的原则，通过模拟自然界中 生物群体由低级到高级，由简单到复杂的生物进化过程，最终逐渐逼近问题的最优解 或准最优解。遗传算法作为一种有效的全局搜索方法，因具有较好的普遍适用性和易 扩充性；基本思想简单，便于具体使用；具有很高的并行性等优点而得到广泛的应用，并产 生了大量的成功案例。 2 1 遗传算法的产生与发展 早在2 0 世纪5 0 年代和6 0 年代，几个科学家进行的“人工进化系统”的研究，就形 成了遗传算法的雏形。其中包括“适者生存”的仿自然法则，自然选择和变异操作的加 入，基于种群的设计方案生物染色体编码的抽象处理等1 。 6 0 年代初期，柏林工业大学的i n g or e c h e n b e r g 和h a n s - p a u ls c h w e f e l 等人在进行 风洞实验时，利用生物变异的思想来随机改变参数值，获得了较好的结果。他们对这 种方法进行深入研究，逐渐形成了进化计算的一个分支一进化策略( e s ) 1 3 1 - 3 2 。 也是在2 0 世纪6 0 年代，f o g e l 等人在设计有限状态自动机( f s m ) 时提出了进化 规划( e p ) ，他们借用进化的思想对一组f s m 进行进化，获得了较好的f s m 。他们后 来将此方法应用到数据诊断、模式识别和分类及控制系统的设计等问题中，都取得了 较好的结果。此方法逐渐发展为进化计算的另一个分支进化规划( e p ) 3 1 , 3 3 。 1 9 6 2 年，h o l l a n d 在o u t l i n ef o ral o g i ct h e o r yo f a d a p t i v es y s t e m s 文中，在f r a s e r 和b r e m e r m a n n 等人的基础上提出了位串编码技术，此技术改变了先前只能依赖变异来 产生新的基因结构的状况，使编码既适用于变异操作，又适用于交叉操作，并且强调 将交叉作为主要的遗传操作。1 9 6 7 年，h o l l a n d 的学生j d b a g l e y 通过对跳棋游戏参数 的研究，在其博士论文中首次提出“遗传算法”一词( 4 , 3 4 1 。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 a la n da r t i f i c i a ls y s t e m s ) 1 2 】。 以后，h o l l a n d 等人将其应用于适应性系统模拟、函数优化、机器学习、自动控制等领 天津大学硕士学位论文 域，并正式定名为遗传算法。 1 9 7 5 年以后，遗传算法的基本理论得到了丰富和发展。g o l d b e r g t 4 1 、d a v i s t 5 1 、 g r e f e n s t e t t e t 6 1 、b a u e r t 7 1 、s r i n i v a s 和p a t n a i k t 8 】等大批研究人员对遗传算法理论的基本 框架和遗传算子进行了构建和改进。1 9 8 9 年，d a v i dg 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 【4 】。 2 0 余年来，遗传算法的发展日益成熟，许多学者提出了各种不同的遗传基因表达 方式，不同的交叉和变异算子以及不同的再生和选择方法。这些改进方法产生的灵感 都来自于大自然的生物进化过程，可归为同一个“算法簇”。人们把这个遗传“算法簇” 称为进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 。它基本分为四个分支：遗传算法( g a ) 、 进化规划( e p ) 、进化策略( e s ) 和遗传规划( g p ) 。 随着遗传算法研究和应用的不断深入与扩展，世界范围的遗传算法学术会议也开 始举办。主要有从1 9 8 5 年开始在美国隔年召开的遗传算法国际会议( i c g a ) 和之后 的遗传和进化国际会议( g e c c o ) ，从1 9 9 0 年开始在欧洲隔年举办的并行问题自然算 法会议( p p s n ) 和之后隔年一次的遗传算法理论基础学术会议( f o g a ) ，从1 9 9 6 年 6 月开始之后每年召开一次的“进化计算”国际学术会议( 匝e ei c e c ) 。从1 9 9 9 年开始， i e e e 神经网络委员会与进化规划( e p ) 的年会合并为进化计算国际会议，每年召开一 次【3 5 1 。 关于遗传算法的专集和杂志也陆续出版。1 9 9 4 年1 月，髓e 神经网络委员会出版 了第一本“进化计算”专集。1 9 9 7 年，该委员会创办了i e e et r a n s a c t i o no i le v o l u t i o n a r y c o m p u t a t i o n 杂志。从1 9 9 3 年开始美国m i t 出版社开始出版e v o l u t i o n a r yc o m p u t a t i o n 和a d a p t i v eb e h a v i o r 杂志。世界上第一本关于人工智能研究的杂志a it r e n d s 于1 9 9 3 年更名为c r i t i c a lt e c h n o l o g yt r e n d s ，并在更名启事中讲到一“遗传算法、自适应系统、 细胞自动机、混沌理论和人工智能一样，都是对今后十年的计算机技术有重大影响的 关键技术”。 随着国际互联网的发展和普及应用，遗传算法的有关研究单位建立了大量的专题 g a 网站，其中最为著名的是由美国海军人工智能应用研究中心建立的g a a r c h i v e s 检 索网站( h t t p ：w w w a i c n r l n a r y m i l g a l i s t ) 。 这些众多的研究单位和频繁的国际学术活动集中反映了遗传算法的学术意义和应 用价值。遗传算法已成为一个多学科、多领域的重要研究方向。 2 2 遗传算法的基础1 3 6 瑚】 2 2 1 遗传算法的基本原理 天津大学硕士学位论文 按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程， 各种生物要生存下去就必须进行生存斗争。具有较强生存能力的生物体更容易存活下 来并繁殖后代；具有较低生存能力的个体则容易被淘汰直至消亡。因此，凡是在生存斗 争中获胜的个体都有较强的环境适应性。而个体是由不同的基因组合而成的，通过基 因的杂交和突变可以产生对环境适应性强的后代。杂交可以使子代继承父代的一些基 因结构，保持物种的特性；变异则随机改变父代个体的染色体上的基因结构，产生具有 新特性的子代个体。因此，基因的杂交和变异使生物的进化成为可能。生物体进化的 基本过程为：一些个体构成的初始种群经过生存斗争，产生新的种群。新种群中的一 部分个体为原始种群中适应性强的个体，而另一部分个体则是通过杂交和变异产生的 新个体。新种群又面临生存斗争，这样，新种群变成旧种群开始新的循环，从而使生 物体不断向前进化，也就不断的完善和发展。可见，生物进化过程本质上是一种优化 过程。 2 2 2 遗传算法的基本术语 由于遗传算法研究与应用尚在不断发展中，有关术语的应用尚未完全取得统一。 为了在下面研究中做到准确、清晰、规范地描述，本文中采用的术语及其含义解释如 下： 个体( i n d i v i d u a l ) ：g a 所处理的基本对象、结构。 群体( p o p u l a t i o n ) ：个体的集合。 位串( b i ts t r i n g ) ：个体的表示形式。对应于遗传学中的染色体。 基因( g e n e ) ：位串中的元素，表示不同的特征。对应于生物学中的遗传物质 单位，以d n a 序列形式把遗传信息译成编码。 基因型( g e n o t y p e ) ：也称遗传型，指用基因组定义遗传特征和表现。对应于 g a 中的位串。 表现型( p h e n o t y p e ) ：生物体的基因型在特定环境下的表现特性。对应于g a 中的位串解码后的参数。 基因位( 1 0 c u s ) ：某一基因在染色体中的位置。 等位基因( a l l e l e ) ：表示基因的特征值，即相同基因位的基因取值。 适应值( f i t n e s s ) ：某一个体对于环境的适应程度，或者在环境压力下的生存 能力，取决于遗传特性。 复制或选择( r e p r o d u c t i o no rs e l e c t i o n ) ：在有限资源空间上的排他性竞争。 6 天津大学硕士学位论文 交叉或重组c r o s s o v e ro rr e c o m b i n a t i o n ) ：一级位串或者染色体上对应基因段 的交换。 变异( m u t a t i o n ) ：位串或染色体水平上的基因变化，可以遗传给子代个体。 遗传( h e r e d i t y ) ：父代个体通过有性方式向子代个体的特征传递过程。 编码( c o d i n g ) ：把问题空间中的参数转换成遗传空间中的个体。即从表现型 到基因型的转换。 解码( d e c o d i n g ) ：编码的相反操作。即从基因型到表现型的转换。 2 2 3 遗传算法的基因操作 遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是 完全随机搜索，它能有效地利用历史信息来推测下一代的信息。代代进化，最后求得 问题的最优解。标准遗传算法的基本流程和结构大体如下所示： 1 ) 随机生成所求问题的初始群体，该群体包括由适合表示问题域的函数及变常 量集合构成的一组计算机程序个体： 2 ) 评价群体中个体的适应性； 3 ) 根据适者生存、优胜劣汰原则，对群体中的个体施加遗传操作，以产生更好的 一代群体； 4 ) 重复2 ) 、3 ) 步操作，直到满足停止准则为止。 我们可以看出，遗传算法的运行过程为典型的迭代过程，它涉及了六大要素：( 1 ) 参数编码；( 2 ) 初始群体的设定；( 3 ) 适应度函数的设计；( 4 ) 遗传操作的设计；( 5 ) 控制 参数的设定( 主要是指群体规模和交叉概率、变异概率等) ；( 6 ) 终止循环的条件。这 六个要素构成了遗传算法的核心内容。 ( 1 ) 参数编码 按照遗传算法的工作流程，求解时必须在目标问题实际表示和遗传算法的染色体 间建立联系，即确定编码和解码运算。 由于遗传算法计算的鲁棒性，它对编码的要求并不苛刻。实际上，大多数问题都 采用h o l l a n d 建议的二进制编码设计，因为它最为实用并符合d ej o n g 的编码原理n ”9 1 。 然而，在很多情况下，编码形式也就决定了交叉操作，编码问题往往被称作编码一交 叉问题。因此，作为遗传算法流程中第一步的编码技术是一个值得认真研究的问题， 很多专家提出了各种编码方法。 天滓大学硕士学位论文 非二进制编码中具有代表性的是十进制编码方案【4 1 】和实数编码方案【引。在采用g a 求解t s p 类问题时 4 , 4 2 1 ，用序列编码更为合理、自然。由此可见非二进制编码往往结 合问题的具体形式，一方面可简化编码解码过程，另一方面可以在遗传操作中采用非 传统操作算子，或者与其它搜索算法相结合。 ( 2 ) 初始化群体 遗传算法是群体性的操作，因此必须具备一个由若干初始解构成的初始群体。初 始群体中的个体一般是随机产生的。群体规模n 越大，群体中个体的多样性越高，g a 搜索的质量可以得到改进，但是计算量也随之增加；群体规模太小，则可能产生早熟收 敛。因此群体规模不宜太大也不宜太小。在不具有关于问题解空间的先验知识的情况 下，很难判定最优解的数量及其在可行解空间中的分布情况。因此我们往往希望在问 题解空间均匀采样，随机生成一定数目的个体( 为群体规模的2 倍) ，然后从中挑出较 好的个体构成初始群体。 ( 3 ) 适应度函数 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必须对 个体位串的适应性进行评价。因此，适应函数( f i m e s sf u n c t i o n ) 就构成了个体的生存 环境。根据个体的适应值，就可决定它在此环境下的生存能力。一般来说，好的染色 体位串结构具有比较高的适应函数值，即可以获得较高的评价，具有较强的生存能力。 由于适应值是群体中个体生存机会选择的惟一确定性指标，所以适应函数的形式 直接决定着群体的进化行为。为了能够直接将适应函数与群体中的个体优劣度量相联 系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。 一般而言，适应值函数是由目标函数变换而成的。需要注意的是，只有对整个群 体的目标函数变换，才能计算出经过变换后的适应值，对单个个体计算适应值无意义。 目前遗传算法中常用的适应值函数有以下几种：按比例的适应值分配：基于排序的 适应值分配；等机会变换；非单调适应值变换。 ( 4 ) 遗传算子 标准遗传算法的操作算子一般都包括选择、交叉、变异三种基本形式，它们构成 了遗传算法具备强大搜索能力的核心。 1 ) 选择( 复制) 选择即从当前群体中选择适应值高的个体以形成下一代种群的过程。发展各种选 择算子的目的是为了避免基因缺失，提高全局收敛性和效率。目前，常用的选择有： 天津大学硕士学位论文 适应值比例选择( 轮盘赌选择) ；排序选择；联赛选择；稳态选择；随机遍历选择和精英选 择策略【3 1 。 需要注意的是，选择算子只是从当前群体中选择较好的个体形成交配池，其本身 并没有产生新的个体。 2 ) 交叉( 重组) g a 交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基 因遗传给下一代个体，并生成包含更多基因结构的新个体。交叉操作一般分为以下三 个步骤：首先从交配池中随机选出要交配的一对个体；然后根据位串长度l ，在要交配 的一对个体中分别随机选取 1 ，l - 1 q 口的一个或多个整数k 作为交叉位置；最后根据交 叉概率实施交叉操作，相互交换交叉位置中的内容，从而形成新的一对个体。 采用二进制编码、实数编码和自然数编码所用的交叉策略不一样，目前通常使用 的遗传算子包括适用于二进制编码的一点交叉、两点交叉、多点交叉、一致交叉；适用 于自然数编码的部分匹配交叉、顺序交叉、圈交叉和启发式交叉和适用于实数编码的 算术交叉等。 3 ) 变异 在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异 操作的作用是第二位的，仅仅充当背景性的角色。但变异却是不可或缺的。当交叉算 子产生的后代的适应度不再比前辈好又未达到最优解，就会产生成熟前收敛或早熟收 敛，发生这种情况的根源是发生了有效基因缺失，这时，为了克服这种情况，只有信 赖于变异。一方面，变异算子可以使种群进化过程中丢失的等位基因信息得以恢复， 以保持群体中的个体差异性，防止发生成熟前收敛；另一方面，当种群规模较大时，在 交叉操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。 变异操作模拟自然界生物体进化中的突变现象，从而改变染色体的结构和物理性 状。常规变异的效果是不明显又很慢的，目前发展的主要变异算子有：基于二进制编 码的常规位变异、有效基因变异、自适应有效基因变异、概率自调整变异和基于实数 编码的均匀变异、非均匀变异、零变异等。 另外，许多高级遗传算子得到了研究，如显性算子、倒位算子、分离和易位牌子、 增加和缺失算子以及迁移算子等。这些遗传算子来源于群体遗传学，目前应用尚少， 机理及其表现有待进一步的深入研究。 ( 5 ) 控制参数和选择 天津大学硕士学位论文 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。主要参数 包括群体规模挎，交叉概率致以及变异概率。许多学者进行了大量实验研究，给出 了最优参数建议( d ej o n g ”，g r e f e n s t e t t e 6 1 ，s c h a f f e r 删) 。 1 ) 群体规模刀：大群体含有较多模式，为遗传算法提供了足够的模式采样容量， 可以改进g a 搜索的质量，防止成熟前收敛。但大群体增加了个体适应性评价的计算 量，从而使收敛速度降低。一般情况下专家建议n = 2 0 2 0 0 。 2 ) 交叉概率以：交叉概率控制着交叉算子的应用频率，交叉概率越高，群体中新 结构的引入越快，己获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则 可能导致搜索阻滞。一般取p 。= o 6 0 1 0 0 。 3 ) 变异概率磊：变异操作是保持群体多样性的有效手段，变异概率太小，可能 使某些基因位过早丢失的信息无法恢复；而变异概率过高，则遗传搜索将变成随机搜索。 一般取= 0 。0 0 5 - 0 0 1 。 实际上，上述参数与问题的类型有着直接的关系，不存在一组适用于所有问题的 最佳参数值，在实际问题中应根据需要改变上述参数值以获得最佳结果。 ( 6 ) 终止循环的条件 由于遗传算法具有较大随机性，这里根据几条启发式的终止条件m ，给定参数“ 允、x 、y 和四种终止条件。 & 计算每代群体中染色体适应度的方差，当方差小于占时，可认为算法收敛： b 计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于五时，可认为 算法收敛； c 记录每代最佳染色体，若某染色体连续保持最佳达到x 代，可终止算法。 d 由于计算时间和机器容量都是有限的，代数不能无限长，故迭代次数达到规定值 y 时，可停止计算。 2 2 4 遗传算法的收敛性【4 5 1 遗传算法的基础理论主要以收敛性分析为主。对算法收敛性的分析主要分为基于 随机过程的研究和基于模式理论的研究。这里简要给出基于随机过程的收敛定理。 在遗传算法的进化过程中，个体集合一代代的变化过程作为一个随机过程来加以 考察，并可利用m a r k o v 链来对进化过程进行理论分析，从而得到遗传算法收敛性方面 的重要结论。 天津大学硕士学位论文 这里先定义几个随机过程中的术语。 定义l 设随机过程 x ( 刀) ，n 2 0 ) 只能取可列个值，= f 。，) ，并满足条件：对于 任意刀及乇，如尸 x ( o ) = f o ，x ( 1 ) = ，x ( 刀) = o 必有：p 以刀+ 1 ) = o l 烈o ) = 毛，以1 ) = o ，以功= ) = p x 仰+ 1 ) = + 。i x ( 力) = i _ ) 则称 x 研) ，拧0 ) 为时间状态离散的m a r k o v 链，简称m a r k o v 链。 定义2 乖g p x ( n ) = j l x ( m ) = i ，刀 肌) 为m a r k o v 链的转移矩阵，记为弓( 聊，刀) 。 弓( m ，刀) 具有下面两条性质：( 1 ) 弓仰，力) o ；( 2 ) ，e 弓( m ，z ) o = l 定义3 对于m a r k o v 链，如果 弓( 肌，m + 1 ) = 尸 石( 聊+ 1 ) = 歹l x ( 聊) = f ) = 弓( f ，j j ) 即从状态f 出发转移到状态_ ，的转移概率与时间点m 无关，则称这类m a r k o v 链为 其次m a r k o v 链。 定义4 对于其次m a r k o v 链，称弓为一步转移概率，全部弓( f ，) 所组成的一个 矩阵尸= ( 弓) 称为一步转移概率矩阵，或称为随机矩阵。 为了简单起见，我们只对基本遗传算法的收敛性进行分析。基本遗传算法可描述 为一个齐次的m a r k o v 链只= p ( f ) ，t o ) ，因为基本遗传算法的选择、交叉、变异操作 都是独立随机进行的，新群体仅与父代群体及遗传算子有关，而与其父代群体之前的 各代群体无关，即群体无后效性，并且各代群体之间的转移概率与时间起点无关。 定理1 【删基本遗传算法收敛于最优解的概率小于1 证明：将群体的各种可能状态，分解为包括最优个体的状态厶和不包