（应用数学专业论文）基于个体间相似性的演化优化方法及应用研究.pdf

中文摘要 不论在科学实验还是在工程设计中，很多实际问题都可转化为优化问题， 因此优化计算已越来越得到人们的重视。但是当搜索空间非常大时，传统算法 无法在一个合理的计算时闻内得出用户可接受的次优解，而演化算法作为一种 随机搜索优化技术，却能解决这类复杂的问题，并已广泛应用于求解实际问题。 但是传统演化策略中存在一定的半盲目性，使得种群进化缺乏方向性，导 致求解效率与效果不能达到平衡，因此本文研究基于个体相似性的演化优化算 法以求解决这一问题。围绕这一目的本文进行了如下工作： 本文主要由理论研究和应用实践两部分组成。第一部份是理论研究：介绍 演化算法的一般理论和概念，提出了基于个体间相似性的自适应变异算子的思 想。采用单亲繁殖方式，结合所设计的变异算子，提出一种新的演化算法。第 二部分是应用实践：将所提出的演化算法应用于工程优化中的下料问题，与传 统算法的结果进行比较，显示出本文所设计算法的优良性能。本文的具体内容 如下： 第一章介绍了研究背景，指出本文研究要解决的关键技术问题及研究策略。 第二章介绍了演化计算的一般理论，包括演化计算的基本概念、基本特征 及设计演化算法所应遵循的基本原则等。 第三章阐述了作者对基于个体间相似往变异算子以及自适应演化算法的研 究。在系统研究了演化优化、单亲遗传等的基础上，定义了个体距离、相似性 和邻域等概念( 用距离反映个体间的差异程度，用相似性描述个体间对应基因 位的类似程度，用邻域实现对种群按相似性分割) ，提出了基于个体相似性的 单亲变异算子，在变异过程中引入分级策略，设计出基于相似性的自适应演化 算法。从而使得变异算子具有了很强的导向性，避免了传统达尔文演化策略的 半盲目性，使计算结果更稳定地收敛到所求解问题的全局最优解。 第四章描述了对算法进行数值试验的效果。应用上述新的演化算法解决一维 下料问题时，运算结果证明了新算子和新算法的优良性能。 最后对全文进行了总结。 关键字：演化算法，优化，变异算子，相似性，一维下料问题 a b s t r a c t m 柚yp m b l e m sc 柚b ec l 髂s i 6 e d i n t o o p t i m i z a t i o np m b l e m s ，w h c t h e r 盘o m s d e n c ct e s to r 敏i me n 西n c 喇n gd e s i 弘王l u ti nr e 髂o a b l e c o m p u t a t i o n a lt i m e ， t r a d i t i o n a la l g o r i t h i i l s 锄to b t a i na p p r o x i m a t e t i s f i c do 埘m af o rl a 唱es c a l e p m b l 锄h o w e v c r e v o l 嘶o a r ya 1 9 0 r i t h i l l si sc o m p e t e n tf o r t h c s ep f o b l e m s ，a i l di s u s c d w i d c l y t ow o r ko u tt h ew i t l il a r ：g es c a l co p t i m i z a t i o np r o b l c m si np r a c 6 c c b u t仃a d i t i o n a l c v o l u t i 叽a r ys c h e m c ， w l l i c hh a st h cs 锄砌n e s sw h e n p r o d u d n go f f s 埘n 函啪ta c l l i e v et h eb a l a n c eb e t w e e nt l l ee f e i c i e n c y 觚dr e s u l t t o s o l v ct h ep m b l c m ，w cd i dt h c 陀s e 缸c ha sf 0 1 1 0 w i n g ： t h ed i s s e r t a t i o nc o n s i s t so ft 啪p a n s ：i nt h ef i f s tp a nw es t u d yo nt h et l l e o r yo f e v o l u t i o n a r yc o r i l p u t a t i o n ：as u r v c yi sm a d eo nt l l eg e e 豫l t h c o r yo fe v o l u t j o n a r y c o m p u t a t i o n w bp r o p o s e da n e w a d a p t i v em u t a t i o no p e r a t o rb a s e do n t h es i m i l i t u d e b e 咐e i i i d i v j d u a l s b 觞e do nt h cs y s t e m a t i c a ls u c y 叫t l l eo n c p a r c n tg c n e t i c a l g o r i t h m ，an e wa d a p t i v ee v o l u t i o n a r ya l 鲥t h mu s i n gt h i so p e r a t o ri sp m p o s e d i i l t h es e c o n dp a n ，w et a l l 【a b o u tt h e 印p l i c a t i o no ft h en e we v o l u t i o n a r ya 1 9 0 r i t h mt o s o l v i n go n e - d i n l e n s i o n a lc l l t 血gs t o c kp r o b l e m s n ee x p e r i m t a lr e s u l t ss h o wt h e a d v 蛐t a g e o u sp c r f o 皿a c co ft h ea 1 9 0 r i t l l n l 。t h em a i nr c s c a f c hw o r ki s l i s t c d 髂 f o l l a w s ： h it h ef i r s t c h a p t c r w eg i v e ab i i e fj n t m d u c t i o nt ot h cr e a r c hc o n t e n to f e v o l u t i o n a r yc o m p u t a l i o n t h e n w c p o i n to u tt h ek c yp m b l 锄t h a t m u s tb es 0 1 v e di n 0 u rf e s e a r c hw o r k i nt h es e c o n d c h a p t c lw c d i s c i l s st h eg e n e r a lt h e o r y0 fc v o l u t i o n a r yc o m p u t a t i o n ， i n c l u d i gi 括b 鹤i c n c e p t s ，b 勰i c c h 缸a c t e r i s t i c s 姐df l l n 出血锄t a lp r o c c d u r ct h a to n e h a st of o l l o ww h c n d e s i 驴i l l ge v o l 埘o n a r ya 1 9 0 f i t l l n l s t 1 l et h i f dc h a p t c rp r c s e t so u rr c s e a r c h0 nr e a l - c o d ca d a p t i v cm u t a t i o o p e r a t o r b a s e do nm es i m i l i t u d eb e 抑e e ni n d i v i d u a l s b a s e do t l l es y s t e m a t i c a ls u r v e yo n e v o l u t i o a r y0 p t i m i z a t i o n 趾d0 n e p a r c n tg e n e t i cm g o f i t h m ，w e p m p o s e a o n e p a r e n tm u t a t i o no d e m t o rb a s e do nt l l es i m i l i t u d eb e t w e e nr c a l - c o d ei n d i v i d u a l s f i r s to fa l l ，w ed e f i n c dm ed i s t a c e ，s i m i l i t u d ea n dn e i g h b o r h o o d so fi n d i v i d u a l d i s t a n c c 曲nr c n e c tt h ed i 蜘r e n c cb c m e e nj n d i v i d u a l s ，姐ds i i 血1 i t u d ej sd e s i 印c dt o r c n e c th o wc 1 0 s et w oi n d i v i d u a l sa r e ，a n dn e i 曲b o f h o o d sa r cu s e dt or e a l i z ct h e d i v i s i o no f p o p u l a t i o n w ep m p o s e d a c wa d 印t i v ee v o l u t i o n a r ya l g o r i t l l i nb 鹞e do n s i i n n i t u d ew h i c hh a ss e v e f a lc h a r a d e i i s t i c s 。f i r s t l y “i s c a p a b l e 五疆m u t a t i o no p e m t o r t oa c q u i r c “i 璐i g h tj 啪p s ”o ft h cf i t l l e s s ；s c o 。_ n d i y ，娃锄1a v o i di h e “s e m i 书1 i n d ，0 f n v c m i o n a ld 跏i n i a i l - t y p ce v o l u t i 伽a r yc o m p u t a t i o n t h i r d l y i te n s u r c st h es t a b l e c o n v c r g e o ft h ea l g o r i t 岫i 1 1 t o g l o b a lo p t i m u m - t h ef o u r t h c h a p t c rp r c s c m s o u r a p p h t i o n r c s c a r c ho n u s i n g t h cn c w e v o l u t i o n a r ya l g o r i t l l i i l t os o l v e 0 n e d i m e n s i o n a l c l l t t i n g s t o c k p r o b l e m s t h e e x p e r i m c n t a l r c s u l t ss h o wt l l ea d v a n t a g e o u sp e r f o 珊卸c eo ft h ea l g 耐t h l n a tl a s t ，也er c s e a r c hw o 芏ki n 也ed i s s e n a t i o ni ss u m m a r i z e d w e 鼬g g e s t s 也a t m o r er e s c a r c bw o r kj t h i sa r e as h o u l db ed o n ej nt h ef i l t u f ea n dp r e d i c t sb r i g h t p r o s p e c to f f u t l l r er e s e a r c h k e yw o r d s ：e v o l u t j o n a r yc o m p u t a t i o n ，o p t i l n i z a t i o n m u t a t i o no p e m t o r ，s i m i 重i t i l d e ， o n e d i m e n s i o n a lc u t t i i l gs t o c ：kp r o b l c m s 武汉理工大学硕士学位论文 1 1 研究背景 第一章引言 文献【1 】指出：“很少有一本现代的杂志，不论是工程、经济、管理、数学、 物理或者是社会科学杂志，其中没有“优化”这个关键词。如果概括所有专家 的观点，问题都可概述为从许多可能事件状态中选择一个较好或最好的”。在过 去几十年中，优化的重要性不断提高，不论在科学实验还是在工程设计中，都 需要最优化计算、最优化决策。为了解决各种优化计算问题，人们提出了各种 各样的优化计算方法，如单纯形法、梯度法、隐枚举法、分枝定界法、割平面 法。这些优化算法各有各的长处，各有各的适用范围，也有各自的局限性。由 于这些算法均采用确定性搜索规则，其思想都是通过求解多个连续变量优化问 题来逐步逼近问题的最优解，因而其时间复杂性和空间复杂性均不太好。对于 一些高度非线性的约束优化问题或n p - h a r d 问题，上述方法往往难于奏效，特 别当问题规模较大时，在一个合理的计算时间内，上述算法无法获得一个用户 满意的最优解。而演化算法却能解决这类复杂的问题，并已广泛应用于求解实 际问题。 演化算法是一种基于生物自然选择与遗传机理的随机搜索算法，在优化领 域有着传统方法不可比拟的优点，如对目标函数无连续、可导等要求，具有较 好的全局性，克服了传统算法对问题条件要求高、非全局寻优等缺点，能够通 过种群竞争实现更大范围甚至是无穷空间的搜索，从而能快速逼近最优解。但如 何对优化算法进一步改进，以进一步提高演化算法的效率和搜索到全局最优合 法解的概率，仍在进一步研究中。 当前演化计算应用的如此广泛的原因在于：一方面，各个学科研究的不断 深入，产生了越来越多的难以用传统方法有效解决的实际问题，人们转而尝试 使用演化计算的方法；另一方面，演化计算本身的简单通用性和一定程度的智 能性使得演化计算方法容易被工程技术人员所接受，这在很大程度上促进了演 化计算在各个应用领域的运用。 随着国家信息化建设的进行，无论在科学实验中还是在工程实践中，各衍 武汉理工大学硕士学位论文 各业都将出现各种各样的优化问题，而且问题的规模越来越复杂，求解越来越 困难。如何为这些优化问题提供一个强大、高效的优化算法变得越来越重要。 由于演化算法具有传统优化算法无法相比的优点，已成为解决优化问题的首选 工具。因此对演化算法的研究具有重要的意义。 1 2 研究中需要解决的技术问题 1 、编码表示 设计演化算法的一个重要步骤是对所解问题的变量进行编码表示，编码表 示方案的选取很大程度上依赖于问题的性质及遗传算子的设计，实际上，在设 计演化算法时，编码表示于遗传算子的设计是同步考虑的。 二进制编码即是将原问题的解空间映射到位串空间矗7 - 0 “上，然后在位 串空间上进行遗传操作，结果再通过编码过程还原成其表现型以进行适应值的 评估。 但如果用二进制编码的遗传算法在求解连续变量优化问题时，存在以下的 缺点： ( 1 ) 相邻整数的二迸制编码可能具有较大的h 锄m i g 距离，例如1 5 和1 6 的二进制表示为0 1 1 1 1 和1 0 0 0 0 ，因此，算法要从1 5 改进到1 6 ，则必须改变所 有的位。这种缺陷将降低遗传算子的收敛效率。二进制编码的这一缺点有时称 为海明悬崖( h 籼i i i g c 凰) ； ( 2 ) 二进制编码时，一般要先给出求解的精度以确定串长，而一当精度确 定后，就很难在算法执行过程中进行调整。从而使算法缺乏微调( f m e t u m i n g ) 的功能。若在算法一开始就选取较高的精度，那么串长就很大，这样也将降低 算法的效率。 ( 3 ) 在求解高维优化问题时，二进制编码串将非常之长。从而使得算法的 搜索效率很低。 为了克服二迸制编码的缺点，对于问题的变量是实向量的情形，可以直接 采用实进制进行编码。这样，便可直接在解的表现型上进行遗传操作。从而便 于引入与问题领域相关的启发式信息以增加演化算法的搜索能力，因此本文着 重对实数编码的演化算法的研究。 2 、定义个体间距离、相似性和邻域等概念 2 武汉理工大学硕士学位论文 本文在对个体的描述中定义了距离、相似性和邻域等概念，用距离反映个 体间的差异程度，用相似性描述个体间对应基因位的类似程度，用邻域实现对 种群的分割。 3 、设计基于相似性的自适应变异算子 采用单亲遗传，利用变异算子调整进化方向，在进化过程中以个体相似性 为指导，在个体竞争中引入分级，将种群按照适应值的大小进行分割，对于不 同级别的子种群采取不同的变异策略。适应值大的子种群中的个体视为优势个 体，发生小距离的邻域内变异，产生的子代于父代相似位高，父代的特征信息 被很好的利用，实现对优势个体邻域内的“开采”。适应值小的子种群中的个体 视为劣势个体，发生大距离的邻域内变异，产生的子代于父代相似性低，扩大 种群的多样性，实现对潜在优势个体的“勘探”。利用变异算予来实现效果与效 率的平衡。 4 、算法设计 本文给出基于个体问相似性的演化算法，并将所设计的新的演化算法应用 于对下料问题的求解。 1 3 本文的主要内容 本文的研究得到了国家自然科学重点基金进化计算的理论、方法及应用 ( 编号：6 0 1 3 3 0 1 0 ) 的资助。本文的主要研究内容及创新如下： 1 、演化算法的理论研究：回顾了演化算法的一般理论和概念，提出了基于 个体间相似性的自适应变异算子的思想。采用单亲遗传算法，结合使用该变异 算子，提出了一种新的演化算法。 2 、演化算法的应用实践：将所设计的算法应用于工程优化中的下料问题， 并将计算结果与解决下料阍题的传统方法进行比较，结果显示本文设计的算法 表现出了良好的性能。 1 4 本文的组织结构 本文结构安排如下： 第章是引言部分。 武汉理工大学硕士学位论文 第二章介绍演化算法的一般理论，包括演化计算的基本概念、基本框架、基 本特征、设计原则、若干理论基础等等 第三章是全文的重点，在一章里，给出实数型个体间相似性的定义，设计自 适应变异算子，个体竞争中引入分级，从而提出了基于实数型个体间相似性的 演化优化方法。该算子与算法的设计是在结合对演化优化与单亲遗传算法的系 统研究后提出的，为此本章阐述了演化算法在多个优化邻域的应用，论证了演 化算法在工程优化中的可行性。对单亲遗传算法的基本理论、单亲变异的优势 作了一定的介绍。 第四章介绍了将所设计的新的演化算法应用于整数规划中的下料问题的情 况，并且与下料问题的传统解决方法进行比较，理论与实践上均表明所设计演 化算法的良好性能。 第五章是对全文的总结，并对进一步的工作作出了一些展望。 4 武汉理工大学硕士学位论文 2 1 演化算法概述 第二章演化算法 大自然是我们解决各种问题时获得灵感的源泉。几百年来，将生物界所提 供的答案应用于实际问题的求解已经被证明是一种成功的方法，并且形成了一 个专门的科学分支仿生学( b i o n i c s ) 。我们知道，自然界提供的答案是经过 漫长的自适应过程演化过程两获得的结果，我们也可以利用这一过程去解 决一些较为复杂的问题，这样就不必非常明确地描述问题的全部特征，只需根 据自然法则来产生新的更好解。 演化计算正是基于这样一种思想发展起来的一种通用的问题求解方法。它 采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单 的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。它的机理主 要是达尔文的“适者生存”的思想，利用染色体( 即简单的编码涞表达问题的具 体结构，并通过对染色体进行简单的遗传操作和优胜劣汰的自然选择来指导解 决问题的方法并最终得到问题的解。简单的遗传操作性使其对问题本身没有太 多的约束f 如连续、可微、单峰等) 。由于它的稳健性、通用性等优点和自组织、 自适应、自学习等智能特征，己广泛应用于众多领域，如机器学习、过程控制、 经济预测、工程优化领域等。演化计算的应用重点面向那些高难度、高度非线 性和大规模的复杂系统，包括复杂系统的演化自适应建模、知识挖掘、演化仿 真和演化硬件等。比起传统的方法，所要解决的闯题越复杂越庞大演化计算的 优越性越明显。 2 2 演化算法的基本概念 假设我们考虑的是如下一个优化问题： 肘m ，o ) i x 岩 这里的，是x 上的一个正值函数，即对任意z x ，g ) o 。盖是问题的 求解空间，即问题的所有可能解的全体。它可以是一个有限集合( 如组合优化 问题) ，也可以是一个实空间r “的子集( 如连续优化问题) 等 武汉理工大学硕士学位论文 演化计算在求解问题时是从多个解开始的，然后通过一定的法则进行逐步迭 代产生新解。这多个解的集合称为一个种群( p o p u l a t j o n ，或称群体，解群等) ， 记为p ( f ) ，这里r 表示迭代步，称为演化代( g c n c r a t i o n ) 。一般地。p ( f ) 中的元 素个数在整个演化过程中是不变的，我们将此称为种群的规模，常记为。p ( f ) 中的元素称为个体( i n d i v i d u a l ) 或染色体( c h m m o s o m e ) ，记为 ( 1 ) ，z ：( 2 ) ，南( 3 ) ，- ，h ( f ) 。在演化过程中，要选择当前解进行操作以产生新解， 这些当前解称为新解的父解( p a r e n t ，或称父亲，父体等) ，产生的新解称为后 代解( o 凰p r i n g ，或称儿子。后代等) 。 2 3 演化算法的基本框架 演化算法是模拟自然演化过程的原理进行算法设计的。大自然的演化过程可 视为新的遗传信息的产生与它的评价与选择之间相互作用，种群中表现优良的 个体，将会有更大的机会存后与繁衍后代，它所繁衍的后代继承了父代的信息， 与此同时，再生过程中的非确定性导致了新的遗传信息产生，从而使得后代具 有多样性。在自然演化的过程中加入一些启发信息，就可以得到演化算法的基 本框架： 演化算法过程 b e 画n f - 0 初始化p o ) 计算p ( f ) 中个体的适应值 w k l e ( 终止条件不满足) d o b e g i n 重组p o ) 以产生p ( f + 1 ) 计算p ( f + 1 ) 中个体的适应值 f - f + 1 e 珏d e n d 从以上框架可以看出演化算法是维持由一群个体组成的种群p ( f ) ( f 表示迭 代步) 。每一个个体均表示问题的一个潜在的解。每一个体都被评价优劣并得到 一 亟堡堡三盔堂堡主兰焦堡塞 其适应值。某些个体要经历被称作遗传操作的随机变换，由此产生新的个体。 新产生的个体p ( f + 1 ) 继续被评价优劣。从中选择比较优秀的个体形成新的种群。 在若干代后，算法收敛到一个最优个体，该个体很有可能代表问题的最优解或 次优解。 2 4 演化算法的设计 演化算法作为一种强有力且应用广泛的随机搜索和优化方法，其核心思想 主要包括以下几个部分： 1 ) 问题的解的编码表示： 2 ) 定义解的适应值； 3 ) 确定用以改变复制过程中产生子个体的遗传算子； 4 ) 选择对其进行优劣判定的评价函数； 下面分别对各个部份作一个详细的解释。 2 4 1 解的编码表示 解的编码表示是指在特定的数据结构下，从可能解的状态空间到编码解的状 态空间的一个映射。如何将问题的解编码称为个体是演化算法使用中的关键问 题。该问题已经从多个方面进行过研究，比如当个体需要解码称为解时从编码 空间到解空间的映射性质，以及个体被遗传算子操作时的变形特性等。 在过去1 0 年，已经针对特定问题提出了各种编码方法，其目的都是为了能 够更好地实现演化算法。根据采用何种符号作为基因，编码方式可以分类如下： 二进制编码( 岫e n c o d j n g ) 实数编码( r c a l n u m b e re r 啪d i n g ) 结构式编码 二进制编码即是将原闯题的解空间映射到位串空间- y 上，然后在位 串空间上进行遗传操作，结果再通过编码过程还原成其表现型以进行适应值的 评估。但是由于h a m m i i l g 悬崖的存在，二进制编码对于函数优化问题存在严重 缺陷。h a m m i n g 悬崖指的是表现型空间中距离很小的个体对可能有很大的 h a m m i n g 距离。例如1 5 和1 6 的二进制表示为0 1 1 n 和1 0 0 0 0 ，因此，算法从 1 5 改进到1 6 必须改变所有的位。为了翻越h a m m i n g 悬崖，个体的所有位需要 7 武汉理工大学硕士学位论文 同时改变。由杂交和变异实现翻越h a m m i n g 悬崖的可能性非常小。在这种情况 下，二进制编码无法维持表现型空间中点的位置。 实数编码对于函数优化问题最为有效，关于实数编码在函数优化和约束优 化邻域比二进制编码更有效的说法，已经得到广泛的验证，由于实数编码基因 型空间中的拓扑结构与表现型空间中的拓扑结构一致，因此很容易从传统优化 方法中借鉴好的技巧来形成有效的遗传算子。 对于很多问题其更自然的表现是树或图的形式，这时采用将问题的解表示 成树或图的形式的编码称为结构式编码。这种情况下，需要非常谨慎的设计遗 传算子以避免产生或少产生非法后代，对于结构式编码的遗传算子一般是具体 问题具体分析，因为遗传算子是直接在解的表现型上进行操作，这样比较容易 加入与邻域相关的知识和一些启发式的信息。 2 4 2 定义解的适应值 自然界中，个体的适应能力体现在它的综合素质上，如个体对环境的承受 能力、个体的繁殖能力、个体的应急能力等。适应性强的个体将有更大的可能 繁殖更多的后代。演化计算抽象出这一生物特征，给各个解赋予一种关于适应 性的量度，以此为基础，引导种群中的个体向更高适应值方向发展。通常情况 下，可以将问题的求解目标直接定义为解的适应值，在数值优化中，多采用这 种方式。但有时候如此简单的定义不充分，即对问题的解的适应信息挖掘的不 够，需要人为的调节或引入适当的辅助信息，例如，对于布尔可满足性问题( s t 问题) 就不能仅将适应值定义为布尔表达式的值即o 和1 ，因为这样的定义并不 能提供引导搜索向逐步改进的方向进行的必要信息。另外，适应值定义的好坏 还关系到适应值计算的繁简，进而影响算法的效率，所以。算法设计时应结合 问题背景适当的予以定义。 2 4 3 设计演化算子 演化算子的设计占据着演化算法设计的核心地位。演化算子的设计与解的编 码表示是紧密相关的，不同的编码方式其演化算子的设计思想一般差异较大。 演化算予广义上可分为杂交算子和变异算子。本文主要是针对实数型个体设计 演化算法，所以在这里将主要介绍实数编码的演化算子设计，对于二进制编码 武汉理工大学硕士学位论文 与结构式编码的演化算子的设计就一笔代过。 2 4 3 1 二进制编码 1 、杂交算子 二迸制编码的杂交算子包括点式杂交和均匀杂交等； 点式杂交0 面n t a lc m s s o v e r ) 点式杂交算子又分为单点式杂交和多点式杂交。单点杂交即是随机地在两 个父串上选择一个杂交点，然后交换这两个串的对应的子串。多点杂交则是一 次随机生成多个杂交点，然后间断交换父串的对应子串 均匀杂交( u n 讧。彻c r o s s o v e r ) 均匀性杂交则是依概率交换两个父串的每一位。其过程是：先随机地产生一 个与父串具有同样长度的二进制串，其中o 表示不交换，l 表示交换。这个二进 制串称为杂交模板( c r o s s o v e rt e n l p l a t e ) ，然后则根据该模板对两父串施行杂交， 所得的两个新串即为后代串。例如： 父串 1 ：1 1 0 0 1 0 1 1 1 0 0 0 子串 2 ：1 0 1 0 1 1 1 0 1 0 1 1 模板t ：0 0 1 1 0 1 0 1 1 1 0 0 后代串1 ：1 1 1 0 1 1 1 0 1 0 0 0 后代串2 ：1 0 1 0 1 1 1 0 1 1 2 、变异算子 二进制编码时的变异算子非常简单，只是以一定的概率以( 称为变异概率) 将所选个体的位取反。即若是1 ，则取o ；若是0 ，则取1 ， 2 4 3 2 实数编码 实数编码时的遗传算子与二进制编码时的情形将完全不同。主要有以下原 因： ( 1 ) 编码表示方式是实空间中的向量，而不像二进制编码时考虑的是二进 制串； ( 2 ) 等位基因的类型不再是布尔型，故变异算子不再是简单的取反。 下面我们假设解向量是月维的，并且每一个分量酃在有限区间上定义的，如 设s ；，v ：，v 。) 是一个解向量。则有v k ，6 ；】一l ，2 ，聃。反之对任何满足 武汉理工大学硕士学位论文 v 乍【口j ，岛】的向量s - “，v ：，v ：) ，s 都是问题的解。 6 、杂交算子 实数编码的杂交算子包括离散杂交和算术杂交，为叙述方便，下面设 毛一坩，y ，) 和5 ：一研”，y ! ”，埠) 是两个父解向量，屯= q ，z ：，乙) 和s ，一( ，w ：，) 是通过杂交获得的两个后代， 离散杂交似i s c r c t cc r o s s o v e r ) 离散杂交又分为部分离散杂交和整体离散杂交。部分离散杂交即是在父解向 量中选择一部分分量( 如一个分量或从某分量以后的所有分量) ，然后交换这些分 量以形成后代。如若交换第t 个分量以后的所有分量，则两个后代为 l p ：1 ) ，v 纷，v p ，v 跺，v ) 钆一加防v 笋，v 只v 跺，v 票) 雨整体杂交则是以l 2 的概率交换5 ，与如的所有分量，这有点像二进制编 码时的均匀性杂交，也可以通过生成模板的形式来实现，若某一位是1 ，则交换 相应的分量，否则保留。如肌- 1 0 ，模板丁( 0 1 0 0 1 0 儿0 1 ) ) ，则 巳一 “”，v i “，v j l ) ，v ：1 ) ，v ”，v ，v ；2 ，以“，v 5 ”，喀，) ； “，v ：1 ) ，v j 2 ) ，v 咒v ，v 5 2 ) ，v ；1 ) ，v p ，v 5 2 ) 谢，) 显然，通过离散杂交产生的后代，其分量仍然在其定义区间之内。 算术杂交( a r i t h i i l e t i c a lc r o s s o v e r ) 算术杂交也分为部分算术杂交和整体算术杂交。 部分算术杂交即是先在父解向量中选择一部分分量，如第七个分量以后的所 有分量，然后生成 一七个( 0 ，1 ) 区间的随机数口。，窿。，口。，则两个后代定 义为： t - “”，v ”，a 。+ ，v n l + ( 1 一a 。) “碧，口。v ：”+ ( 1 一a 。) v ：2 s 。曩 v i 甜，v ：2 、，a i + l v 墨+ ( 1 一盘 “) y 恐，d 。v + ( 1 一k 弘 当然，这里我们也可以取吒+ ，一a 。，从而只需生成一个随机数 整体算术杂交为：先生成n 个( 0 ，1 ) 区间的随机数口。，a ：，口。，则两后代5 ， 和s 。分别定义为 s ：= 口t v j ”+ ( 1 一o f ) v ：2 = v j 2 + 口f ( v f ”一v ：2 ) s ，= d f v j 2 十( 1 一a 。) v ! ”= v ：”+ a f p ! “一v ：”) 加 武汉理工大学硕士学位论文 这里f 一1 ，2 ，n 。同样，我们也可以取d ，= d ：- 一口。 易见，通过算术杂交产生的后代，其分量仍在其定义区间之内。从几何角 度看，我们可以通过五，5 ：产生r “中的一个超立方体，则离散杂交生成的后代都 是这个超立方体的顶点，丽算术杂交生成的后代则是起立方体内部的点，从这 一点看，算术杂交的搜索范围比离散杂交要大。只是由于在实数编码时，杂交 算子的作用远没有二进制编码时显得那样重要，故而采用何种杂交算子对算法 性能的影响不是很大。 2 、变异算子 在实数编码时变异算子的作用不再像二进制编码时仅仅是简单地恢复群 体中多样性的损失。这时，它已成为一个主要的搜索算子。为此，人们设计了 很多变异算子，我们的经验是，在设计算法时，将多种变异算子交叉使用或按 照一定的概率分配使用，有时会带来较好的结果， 均匀性变异 为叙述方便，下面设s t ，v ：，v 。) 是父解s - ( z ，z ：，z ) 是变异产生的 后代。均匀性变异则是先在父解向量中随机地选择一个分量，假设是第| 个，然 后，在其定义区间【，以】中均匀随机地取一个数v ：代替h 以得到= ，即 铲雕篓 也可以先确定一些较小的区间【4 ，4 】，f 一1 ，2 ，n 。对y 。变异时均匀随机地在 卜口。，以】中取一个数) ，并令v ：- v 。+ _ ) ，a 这里4 称为变异域，一般取区间卜吼，6 j 】 长度的某个百分比，比如取4 0 1 一4 。) 。 正态性变异( n o r m a ld i s t r i b u t e dm u t a t i o n ) 这种变异算子最初是在演化策略中首先使用的，后来，演化规划也以它作 为主要的搜索算子，目前一些改进的遗传算法中也经常使用它。 在演化策略中，群体中的一个个体是由一个解向量5 n ( v ，v ：，k ) 和一个 摄动向量盯m ( q ，：，) 组成的，这个摄动向量是变异解向量的控制参数，并 且它自己也不断要进行变异假如o ，盯) 是被选个体，则可按下式产生变异后的 新个体0 ，口) ： 盯；= 口f e x p ( i ( o 仃) ) 一= v i + ( o ，丁；) f - 1 ，2 ，一，n 武汉理工大学硕士学位论文 这里盯月及称为二级步长控制参数 ( s t e d s i z e m e t a c o n t r 0 1 ) ：m ( 0 ，盯) ，fm 1 ，2 ，l 相互独立的均值为o 方差为盯符合正态 分布的随机数。 注意，在进行解向量s 的变异之前，曾先要对标准差盯进行变异，由于变异 与选择的结合可以视为是一种爬山过程，故而研有时被称为步长( s t e ps i z e ) 。 关于正态分布的变异算子尚有其它变种。如最初时标准差由一些确定的规 则( 如1 5 成功法则) 来决定而不进行变异及更复杂的相关变异( c o r r e l a t e d m u t a t i o n ) 等等。 非一致性变异 在传统的遗传算法中，算子的作用与代数是没有直接关系的，从而算法演化 到一定代数以后，由于缺乏局部搜索，传统的遗传算子将很难获得收益。基于 上述原因，z m i c h a l e w i c z 首先将变异算子的结果与演化代数联系起来，使得 在演化的初期，变异的范围相对较大，而随着演化的推进，变异的范围越来越 小，起着一种对演化系统的微调( f i n e t u n i n g ) 作用。其具体描述如下： 设s 一( v 。，v ：，y 。) 是一个父解，分量叱被选为进行变异，其定义区间是 【吼，】则变异后的解为s an ，略。，以，k ) ，其中 ，p 。+ a ( f ，坑一)f ，阳n d ( 2 ) - o 。 i 叱一( f ，6 一咋)矿加耐( 2 ) 一1 这里如果m 蒯f 2 ) 表示将随机均匀地产生的正整数模2 所得的结果，f 为当前演 化代数，而函数( f ，) ，) 的值域为【o ，y 】，并使得当f 增大时，a 0 ，y ) 接近于o 的概 率增加。即f 的值越大，0 ，y ) 取值接近于0 的值的可能性越大，从而使得算法 在演化初期能搜索到较大范围。而在后期丰要是进行局部搜索了。 函数0 ，_ ) ，) 的具体表达式可取为 ( f ，y ) 暑y ( 1 一，o 一玎y ) 这里，是 o ，1 上的一个随机数，r 表示最大代数，a 是决定非一致性程度的一 个参数，它起着调整局部搜索区域的作用，其取值一般为2 到5 。 自适应变异 虽然非一致性交异加强了算法的局部搜索能力，但局部搜索的范围只与演 化代数有关，而与解的质量无关。即无论解的质量的好坏，其搜索范围都是相 同的。我们认为更为合理的情形应该是使适应值大的个体在较小范围内搜索而 武汉理工大学硕士学位论文 使适应值小的个体在较大范围内搜索。基于这种考虑，潘正君等在文献 4 2 中 引入了解的变异温度的概念，这一概念类似于模拟退火算法中温度的概念，然 后在非一致性变异算子的基础上提出了自适应性变异算子。 解的变异温度定义如下： 设5i ，v z ，v 一) 是解空间的一个向量，0 ) 是它的适应值，o 是所解 问题的最大适应值，则其变异温度可定义为 丁。1 一地 一 对于很多问题，o 是娃以确定的，我们这里只要一个粗略的上限即可，用当前群 体中的最大适应值作为j 一也可以。 有了变异温度的概念以后，其变异方式与非一致性变异算子相同，只是将 其中的演化 代数f 改为r ，函数表达式改变为 ( 丁，) ，) 篁) ，( 1 一，1 ) 即可。 这样定义的变异算子将保护较好的解，使搜索在其较小的领域内进行，面 对适应度不好的解，搜索的领域较大。这样使得变异能根据解的质量自适应地 调整搜索区域，从而能较明显地提高搜索的能力。 2 4 - 3 3 结构式编码 结构式编码包括有序串编码、树型编码以及加权图编码等，对于这些编码 方式的演化算子的设计将很大程度上取决于所求解的问题。 2 4 4 选择策略 选择策略对算法性能的影响会起到举足轻重的作用。不同的选择策略将导 致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。较大的 选择压力使最优个体具有较高的复制数目，从而使得算法收敛速度较快，但也 较容易出现过早收敛现象。相对而言，较小的选择压力一般能使群体保持足够 的多样性，从而增大了算法收敛到全局最优的概率，但算法的收敛速度一般较 武汉理工大学硕士学位论文 慢。 下面是演化计算中较常用到的几种选择策略。 1 、基于适应值比例的选择 其中包括繁殖池( b r e e d i n gp 0 0 1 ) 选择，转盘式选择( r o u l e t t ew h e e l s e l e c t i o n ) ，b o l t z 腿n n 选择等。这种选择策略在演化计算的早期被采用，但现 在不太被人注意。在这种方法中，每个个体具有一个正的评估值，与个体的相 对适应值成某种比例的多个副本被传播到下一代。平均而言，高于平均适应值 的个体比低于平均适应值的个体具有更大的选择机会。这使得演化算法倾向于 使用较好解作为进一步搜索的基础，但并不是只保留最好解。在这些选择策略 中，后代数目的期望值都可能不是整数。但在实际选择时只有整数才有意义。 于是按照转盘方式选择时，可能会产生较大的抽样误差。即某个体的后代数目 可能偏离期望值较远，仅在群体规模很大时，才能达到期望值。于是对此便有 人提出了很多的改进办法如剩余随机抽样、确实性抽样、随机整群抽样 ( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) 等等 2 、基于排名的选择 包括线性排名选择和非线性排名选择。前面已论述到，使用基于适应值比例 的选择策略常常会出现过早收敛现象和停滞现象，避免这些现象的方法之一是 使用基于排名的选择策略。这种选择策略首先根据个体f 的适应值在群体中的排 名来分配其选择概率p i ，然后再根据这个概率使用转盘选择，这样个体的绝对 适应值不直接影响后代的数量。它的另一个优点是无论对极小化问题或极大化 问题，不需要进行适应值的标准化和调节，可以直接使用原始适应值进行排名 选择。 3 、基于局部竞争机制的选择 包括( ，l ，a ) 和肛+ a 选择、锦标赛( t o u r n 拥e n t ) 选择、b o l t z 腿n n 锦标赛选择。 缸，a ) 选择是先从规模为弘的种群中髓机选择个体通过重组和交异生成a g 芦) 个后代，然后再从这些后代中选取_ 1 个最优后代。锦标赛选择是从当前种群中 抽取部分个体作为样本，识别其中的最好个体并保留下来，然后再对剩余个体 进行抽样和选择。重复此过程直到达到下一代所需的父体数目为止。抽样子集 的大小决定了这一过程的多样性。显然，如果子集大小等于种群规模，则这种 方法实质上等同于一个确定性的( 卢，a ) 选择。b 0 1 t z m n n 锦标赛选择引入概率进 制进行选择，在实际中很少用到。 1 4 武汉理工大学硕士学位论文 2 5 演化算法的基本特征 演化算法的基本特征表现在以下几个方面： 1 、智能性：演化计算的智能性包含自组织、自适应、自学习。应用演化算 法求解问题时，在确定了编码方案、适应值函数和遗传算子后，算法将利用演 化过程中获得的信息自行组织搜索。 2 、多解性：由于演化的不是一个个体，而是群体，在每个演化阶段都存在 多个候选解，故往往一次能找到多个解，这一特点特别适合于求解含有多个极 值点的问题。 3 、全局优化：传统优化算法是从单个初始值迭代求最优解的，很容易