（计算机软件与理论专业论文）混合分布式并行遗传算法的研究与应用.pdf

摘要 中文摘要 遗传算法( g a ) 作为一门新兴学科，从二十世纪八十年代开始迅速发展。遗传 算法是一种用于解决优化问题的并行寻优算法，已被广泛用于解决各类n p 问题。 但标准遗传算法仍然存在一些缺陷。为了克服这些缺陷，本文设计了一个全 新的混合遗传算法s e g a ，这一算法在进化方式上与传统的混合遗传算法明显不 同，然后，用马尔可夫链的有关知识对s e g a 算法进行数学分析。它综合了遗传 算法和邻域搜索算法各自优势的全局搜索算法。它即有遗传算法的全局搜索能力， 又有高效的局部搜索能力。该算法较好的解决了两种不同算法结合所产生的矛盾。 通过实验表明，该算法具有良好的全局寻优性能。 随着问题规模的不断扩大，面对复杂度越来越高的搜索空间，遗传算法在优 化效率和求解质量上都显得“力不从心”。为解决大规模复杂优化问题，本文就并 行遗传算法的并行化原理和应用平台进行分析，并结合s e g a 算法和分布式遗传 算法两种思想提出了一种基于网络环境的分布式遗传算法( e x t e n d e d n e t w o r k - b a s e d d i s t r i b u t e d g e n e t i c a l g o r i t h m ，简称e n d g a ) 。并着重讨论了e n d g a 实现中的关键问题，用马尔可夫链的有关知识对e n d g a 算法进行数学分析，并 给出了算法的具体程序实现。 在本文中，我们实现了一个解决带约束条件的并行多机调度问题的分布式网 络p g a 。实验表明，e n d g a 能显著节约寻优的时间，大大提高寻优的质量，为 解决巨量优化问题提供一个可行的解决方法。 关键词：并行遗传算法，混合遗传算法，基于网络的分布式遗传算法 a b s t r a c t a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i san e ws u b j e c t i t sa p p l i c a t i o nb e g a nt of l o u r i s hs i n c e t h ee i g h t i e so ft h e2 0 sc e n t u r y t h eg e n e t i ca l g o r i t h m ( g a ) i san e wp a r a l l e lo p t i m i z e a l g o r i t h m ，w h i c hc a nb eu s e dt os o l v em a n yk i n d so f n p h a r dp r o b l e m s b u ts t a n d a r dg e n e t i ca l g o r i t h mh a ss o m ef a u l t s i no r d e rt oo v e r c o m et h e s ef a u l t s ， w ed e s i g n e dan e wh y b r i dg e n e t i ca l g o r i t h m - - s i m u l t a n e o u se v o l u t i o ng e n e t i c a l g o r i t h m ( s e g a ) t h i ss e g ai sd i f f e r e n tf r o mt r a d i t i o n a lg ai ne v o l u t i o nm a n n e r ， a n dt h e nw eu s em a r k o vm o d e l i n gt oa n a l y s i so u rs e g a i ti sag l o b a ls e a r c ha l g o r i t h m w h i c hc o m b i n e st h e r e s p e c t i v ea d v a n t a g e s o fh y b r i d g e n e t i ca l g o r i t h m a n d n e i g h b o r h o o ds e a r c ha l g o r i t h m i th a sag l o b a ls e a r c h i n gc a p a c i t yo fg e n e t i ca l g o r i t h m a sw e l la se f f e c t i v el o c a ls e a r c h i n gc a p a c i t y t h i sa l g o r i t h mr e s o l v e s c o n t r a d i c t i o n s b e t w e e nt w od i f f e r e n tk i n d so fa l g o r i t h m s t h ee x p e r i m e n t a lr e s e a r c hs h o w ss e g ah a s ag o o dp e r f o r m a n c eo fg l o b a ls e a r c h i n g w i t ht h ed e v e l o p m e n to ft h ep r o b l e m s ，t h es e a r c h i n gs p a c eb e c o m e sm o r ea n d m o r ec o m p l i c a t e d t h eo p t i m i z a t i o nt i m ea n dt h eo p t i m i z a t i o nq u a l i t yo fg ac a t l tk e e p u pw i mt h ea c t u a ld e m a n d i no r d e rt os o l v et h em a s s i v ec o m p l i c a t e do p t i m i z a t i o n p r o b l e m s ，t h e a u t h o ra n a l y z e st h e p a r a l l e l i z a t i o np r i n c i p l e a n dt h ea p p l i c a t i o n e n v i r o n m e n to fp a r a l l e lg e n e t i ca l g o r i t h m ，a n dp r e s e n t sak i n do fe x t e n d e d n e t w o r k b a s e dd i s t r i b u t e dg e n e t i ca l g o r i t h m ( e n d g a ) w h i c hc o m b i n e st h e r e s p e c t i v ei d e a lo fs e g aa n dp a r a l l e lg e n e t i ca l g o r i t h m t h ek e yi m p l e m e n t a t i o n so f e n d g aa r ed i s c u s s e d ；w eu s em a r k o vm o d e l i n gt o a n a l y s i s o u re n d g a ；t h e c o r r e s p o n d i n gp r o g r a mf l o wi sa l s og i v e n i nt h i sp a p e r ，w ep r e s e n t e dak i n do fp g aw h i c hi sb a s e do nd i s t r i b u t e d c o m p u t a t i o no f t h en e t w o r kf o rs o l v i n gi d e n t i c a lp a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m w i t hc o n s t r a i n t ，a n dc o m p u t a t i o n a lr e s u l t ss h o wt h a te n d g ac a nn o to n l ys a v et h e o p t i m i z a t i o nt i m ee v i d e n t l yb u ta l s ol a r g e l yi m p r o v et h eo p t i m i z a t i o nq u a l i t y , w h i c h p r o v i d e sa 1 1e f f e c t i v es o l u t i o nt om a s s i v ec o m p l i c a t e do p t i m i z a t i o np r o b l e m s k e y w o r d s ：h y b r i dg e n e t i ca l g o r i t h m ，p a r a l l e lg e n e t i ca l g o r i t h m ，n e t w o r k b a s e d d i s t r i b u t e dg e n e t i ca l g o r i t h m t i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名；二遨日期：抽6 年月多日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 专南 签名：堂 新编衅 日期：矗膨年月厂日 第一章引言 1 1 遗传算法概述 第一章引言 遗传算法( g a ) 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模 型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国m i c h i g a n 大学 的j h o l l a n d 教授于1 9 7 5 年首先提出的，并出版了颇有影响的专著 a d a p t a t i o ni n n a t u r a la n d a r t i f i c i a ls y s t e m s ) ) ，g a 这个名称才逐渐为人所知，j h o l l a n d 教授所提 出的g a 通常称为简单遗传算法( s g a ) 。 1 1 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的，而一个 种群则由经过基因( g e n e ) 编码的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上 是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个 基因的集合，其内部表现( 即基因型) 是某种基因组合，它决定了个体的形状的 外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。 因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编 码的工作很复杂，我们往往进行简化，如二进制编码。初代种群产生之后，按照 适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来越好的近似解。在每 一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自然 遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产 生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比 前代更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为问题 近似堆优解。 过去3 0 年中，在解决复杂的全局优化问题方面，g a 已取得了成功的应用， 受到了人们的广泛关注并已显示了非常广泛的应用前景。 1 2 遗传算法的特点 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优 化算法相比，主要有以下特点： 1 、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策 电子科技大学硕士学位论文 变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借 鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也 使得我们能够方便的应用遗传操作算子。 2 、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3 、遗传算法使用多个点的搜索信息，具有隐含并行性。 4 、遗传算法使用概率搜索技术，而非确定性规则。 1 ，3 遗传算法的应用 由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或 其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗 传算法提供了一种求解复杂系统问题的通用框架，它不依赖于阐题的具体领域， 对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。下面我们将介绍遗传 算法的一些主要应用领域； 1 、函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能 评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离 散函数、凸函数和凹函数、低维函数和高维函数、单峰值函数和多峰值函数等。 对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解， 面遗传算法可以方便的得到较好的结果。 2 、组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的 计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要 精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证 明，遗传算法对于组合优化中的n p 问题非常有效。例如遗传算法已经在求解旅行 商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。 此外，g a 也在生产调度问题、自动控制、机器入学、图像处理、人工生命、 遗传编码和机器学习等方面获得了广泛的运用。 1 4 遗传算法的研究现状 进入9 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究 都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应 都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应 第一章引言 用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产 业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到 了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已 从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是 基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间 的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新 的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希 望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方 法相互渗透和结合，这对开拓2 1 世纪中新的智能计算技术将具有重要的意义。三 是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展， 而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另 一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟 自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命 的重要研究对象，而遗传算法在这方面将会发挥一定的作用。五是遗传算法和进 化规划( e v o l u t i o np r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o ns t r a t e g y ，e s ) 等进化计 算理论日益结合。e p 和e s 几乎是和遗传算法同时独立发展起来的，同遗传算法 一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相 同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形 成热点。 遗传算法在操作上具有高度的并行性，许多研究人员都在探索在并行机和分 布式系统上高效执行遗传算法的策略。对分布式并行遗传算法的研究表明，只要通 过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程，即使不使用 并行计算机，也能提高算法的执行效率。在分布式并行遗传算法的研究中，可以看 到主要有三类研究方向：1 研究分布式并行遗传算法本身的理论基础。2 。用分 布式并行遗传算法作为工具解决工程问题，主要是进行优化，关心的是是否能在 传统方法上有所提高。3 用分布式并行遗传算法研究演化现象，一般涉及到人工 生命和复杂性科学领域。 在国外，近年来，对于遗传算法的理论研究和应用研究，许多计算机科学家 作了大量的工作并取得一定的成果。美国乔治马松大学成立了一个遗传算法研究 组，进行协同进化遗传算法，分布式并行遗传算法，遗传算法分析等方面的研究。 英国格拉斯哥大学控制与信号系统自动设计研究组把分布式并行进化计算应用于 电子科技大学硕士学位论文 系统辨识。x i l i n x 公司生产了一种f p g a 芯片，f p g a 本质上的并行特性使其很适 合用于实现并行的遗传算法。结合两者的并行特性，学者们提出了一种基于f p g a 的并行遗传算法。选用了适合硬件实现的选择、交叉、变异算子，并将它们设计 成流水线结构。算法利用v h d l 语言来描述。实现后的测试表明，这种硬件遗传算 法有效减少了运行时间，使其在一些实时性要求较高的场合得到很好应用。 在国内，也有许多计算机学者从事遗传算法的研究，对g a 的深入研究和应用 做了大量工作。例如：安徽省教委基金项目( 项目号：9 9 j l 0 0 0 0 6 ) 提出了一种基 于模拟退火思想的主从式控制网络p g a ，实现求复函数的方程根；国家自然科学基 金项目( 项目号：6 9 8 7 4 0 0 1 ) 采用遗传算法解决列车控制问题等。国家自然科学 基金项目机械系统分解优化设计及微机网络并行实现，该课题在国内较早开展 机械系统分解优化设计方法及在并行分布式环境下实现的研究，提出了一个基于 松弛因子的线性分解法及一个基于遗传算法的分解优化方法，并将它们用于求解 结构和机械系统的优化设计问题，取得了较突出的研究成果。康立山教授建立一种 新的并行计算模型。结合当今国际并行计算研究的前沿课题，瞄准演化计算这个 新兴领域，对遗传算法等进行了卓有成效的研究，提出了多种群遗传算法等一些 新的并行计算模型和算法。1 2 】 1 5 论文的结构 本文对“混合遗传算法”和“并行遗传算法”进行了详细的阐述和研究，并针 对遗传算法的早熟和收敛速度慢等缺点，提出了一种新的混合分布式并行遗传算 法e n d g a ，并且用它来解决带约束条件的并行多机调度问题。 论文结构安排如下：第一章简述了遗传算法的来源、特点和应用；第二章给 出了标准遗传算法的基本理论；第三章详细阐述了混合遗传算法；第四章全面介 绍了并行遗传算法；第五章作者设计了一个全新的混合遗传算法s e g a ，这一算法 在进化方式上与传统的混合遗传算法明显不同，并结合s e g a 算法和分布式遗传 算法两种思想提出了一种新的基于网络环境的分布式遗传算法e n d g a ，并用 e n d g a 算法解决带约束条件的并行多机调度问题；第六章对论文的意义、目的和 工作内容进行了总结。 第二章标准遗传算法 第二章标准遗传算法 定义2 1 ( 个体和个体空间) 所谓的，一个体x ，即是长度为f 的0 和1 字符 串，简称个体；，称作个体的链长，一个体的全体记作s = o ，1 。，称为个体空间。 按照遗传学的术语，个体也称作染色体( c h r o m o s o m e ) ，个体的分量称作基因( g e n e ) ， 分量的取值称作等位基因( a l l e l e ) 。 定义2 2 ( 母体和母体空间) 所谓母体即是一对个体( x 。，x ：) ，其中 ；s ( i = 1 ，2 ) 。所有的母体的全体称为母体空间，即 s 2 = ( r 1 ，x 2 ) ；置，砭s 定义2 3 ( 种群和种群空间) 所谓的一种群是个个体组成的集合( 个体允 许重复) ，简称种群。称作种群规模，称 t s “= x = ( x 1 ，x 2 ，x n ) ，x fe s ( i ) ) 为一种群空间。 2 1 标准遗传算法的运算过程 如图2 - 1 所示，标准遗传算法的主要过程描述如- y t 3 】 4 i s 6 1 ( 1 ) 置k = 0 ，随机产生初始种群贾( 0 ) = ( x l ( o ) ，z ( o ) ) s “； ( 2 ) 计算群体贾( t ) 中各个个体的适应度。 ( 3 ) 独立地从当前种群贾( 女) 中选取n 个母体： ( 4 1 独立地对于n 个母体进行杂交得到n 个中间个体； ( 5 ) 独立地对n 个杂交后的个体进行变异，得到下代种群 x ( k + 1 ) = ( x t ( k + 1 ) ，x ( + 1 ) ) s “ ( 6 ) 检验停止准则。若满足则停止，否则女= k + 1 并返回到( 2 ) 电子科技大学硕士学位论文 图2 - 1 标准遗传算法流程 2 2 标准遗传算法的基本实现技术 2 2 1 参数编码 g a 是采用问题参数的编码集进行工作的，而不是采用问题参数本身。因此， 在g a 实现时首先要考虑参数的编码。目前编码通常有两种表示方法：二迸制编 码和浮点数编码。另外还存在格雷码( g r e yc o d e ) 编码、符号编码等其它方法。 我们知道，遗传算法中进化过程是建立在编码机制基础上的，编码对于算法性 能如搜索能力和种群多样性等影响很大。就二进制编码而言，其优点在于编码、 解码操作简单，交叉，变异等遗传操作便于实现，而且便于利用模式定理进行理 论分析等；其缺点在于，不便于反映所求问题的特定知识；相邻整数的二进制编 码可能具有较大的海明( h a m m i n 曲距离，将降低遗传算子的搜索效率；二迸制编码 第二章标准遗传算法 时，一般要先给出求解的精度以确定串长，而一旦精度确定后，就很难在算法中 进行调整；在求解高维优化问题中，二进制编码串将非常长，从而使得算法的搜 索效率很低。 为了克服二进制编码的缺点，对于问题的变量是实向量的情形，可以直接采 用实数编码。由于实数编码使得表示比较自然，而且实数编码比二进制编码在变 异操作上能够保持更好的种群多样性。它的使用将越来越广泛。 2 2 2 适应度函数 遗传算法中采用适应度这个概念来度量群体中各个个体在优化计算中有可能 达到或接近于最优解的优良程度。适应度值较高的个体遗传到下一代的概率较大； 适应度值较小的个体遗传到下一代的概率较小。度量个体适应度的函数称为适应 度函数( f i t n e s sf u n c t i o n ) ：适应度函数是个体空间s 到正实数空间的映射，即适应 度函数为： s 崎r + 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适应度来进行搜索。因而适应度函数的选取至关 重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度 函数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应度的尺 度变换( f i t n e s ss c a l i n g ) 。 在选择操作时会出现以下问题：在遗传进化的初期，通常会产生超常的个体， 若按照比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响算法 的全局优化性能；在遗传进化的后期，即算法接近收敛时，由于种群中个体适应 度差异较小时，继续优化的潜能降低，可能获得某个局部最优解。上述问题，我 们通称为遗传算法的欺骗问题。适应度函数设计不当有可能造成这种问题的出现。 因此有必要对种群内各个个体的适应度值进行有效地调整，既不能相差太大，又 要存在相对差异，强化个体间的竞争性。 2 2 3 遗传算子 遗传算子主要包括选择算子、杂交算子和变异算子。遗传算法是对种群通过遗 传机制模拟自然进化过程而不断产生新一代种群，并使新一代种群有更好的性质。 ( 1 ) 选择算子 电子科技大学硕士学位论文 遗传算法使用选择算子来确定如何从父代群体中按某种方法选择那些个体遗 传到下一代群体中的一种遗传运算，即是在一个种群中选择一个个体，它是随机 映射： r s ：s 斗s 。 选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的 是为了避免基因缺失、提高全局收敛性和计算收敛率。从选择算子的执行结果可 以看到，适应度值大的个体易被选择，适应度值小的个体易被淘汰，这样经过不 断的选择使适应度值大的个体不断重复出现，使一个种群可能变为齐次种群。但 是选择算子只是在一个固定的种群中进行选择，选择的结果不可能跑到种群之外。 对于种群之外更好的个体是不可能被选择得到的，选择的结果依赖于初始种祥。 目前常用的几种选择算予有：适应度选择、最优个体保存选择、基于排名的选择、 基于局部竞争机制的选择。 1 、适应度选择 适应度选择方法是目前遗传算法中最基本也是最常用的选择方法。按照概率 规则 蹈? ( 贾) ：x 归掣 ，8 ( 以 选择个体的方式称为适应度选择算子。其中f ( x ，) 表示种群牙中的个体z ，的适应 度，0 a o o 。对于c 3 = 1 称为比例选择算子，简记为r 。 2 、最优个体保存选择 把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中，称为最 优个体保存选择。选择此选择方法的优点是，进化过程中某一代的最优解可不被 交叉和变异操作所破坏。但是隐含着一种危机，使局部最优个体的遗传基因会急 速增加而使进化有可能限于局部解。也就是说该方法全局搜索能力差，它更适合 单峰性质的搜索，而不是多峰性质的空间搜索，所以此方法一般与其它方法结合 使用。 3 、基于排名的选择 所谓排序选择，是指在计算每个个体的适应度后，根据适应度大d , j t 哽序对群 体中个体进行排序，然后把事先设计好的概率表按序分配给个体，作为各自的选 第二章标准遗传算法 择概率。然后再根据这个概率使用轮盘选择，这样个体的绝对适应度不直接影响 后代的数量，它的另一个优点是无论对极小化问题或极大化问题，不需要进行适 应度的标准化和调节，可以使用原始适应度进行排名选择。 4 、基于局部竞争机制的选择 该方法十分简单，其思想为从群体中任意选择一定数目的个体( 称为联姻规 模) ，其中适应度高的选择进入下一代，一般联姻规模选择为2 。这种选择方式只 使用适应度的相对值作为选择的标准，而与适应度的数值大小不成直接比例，从 而避免超级个体的影响，在一定程度上，避免过早收敛和停滞现象的发生。 ( 2 ) 杂交算子 杂交算予是母体空间到个体空间的映射，记作 t ：s 2 斗s 即是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个 新的个体。交叉运算是遗传算法区别于其它进化算法的重要特征，它在遗传算法 中起着关键作用，是产生新个体的主要方法。 2 1 单点杂交算子：等概率的随机确定一个基因位置作为杂交点，再把一对 母体两个个体从杂交点分成前后两个部分，交换两个个体的后半部分得到两个新 个体，并取第一个个体为杂交结果。 2 2 单点随机杂交算予：等概率的随机确定一个基因位置作为杂交点，再把 一对母体两个个体从杂交点分成前后两个部分，以概率只交换两个个体的后半部 分得到两个新个体，取第一个个体为杂交结果。称只为杂交概率。 如果确定两个基因位置将一对母体两个个体分成三个部分，交换中间部分， 称为双点杂交算子，同样有双点杂交与双点随机杂交之分。 2 3 均匀随机杂交算子：独立地以概率只把母体的第一个个体的相应分量交 换为母体第二个个体的相应分量，从而得到杂交结果。 2 4 算术交叉：是指由两个个体的线性组合而产生出两个新的个体。为了能 够进行线性组合运算，算术交叉的操作对象一般是实数编码所表示的个体。假设 两个个体z j ，卫之间进行算术交叉，则交叉运算后产生出的两个新个体是： z = a r ；+ ( 1 一a ) z j z 争1 = a r + ( 1 一a ) 盖 式中，a 为一参数，它可以是一个常数，此时所进行的算术交叉运算称为均匀 9 电子科技大学硕士学位论文 算术交叉；它也可以是一个由进化代数所决定的变量，此时所进行的算术交叉运 算称为非均匀算术交叉 ( 3 ) 变异算子 。变异算予是个体空间到个体空间的随机映射乇：s 斗s ，其作用方式为独立地 以概率岛改变个体分量取值。称为变异概率。从遗传运算过程产生新个体的能 力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索 能力；而变异算法只是产生新个体的辅助方法，但它也是必不可少的一个运算步 骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子的相互配合， 共通完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜 索性能完成最优化问题的寻优过程。 二进制编码时的变异算子非常简单，只是以一定的概率p 卅( 称为变异概率) 将所选的个体的位取反。实数编码时，变异算子的作用不再像二进制编码时仅仅 是恢复群体中多样性的损失，它已经称为一个主要的搜索算子。与二进制相比， 实数编码的变异方式要丰富的多，主要包括均匀性变异、正态性变异、非一致性 变异和自适应变异。 选择、变异和杂交机制各有其功能。单纯利用选择可找到局部最优值，变异 可以使搜索遍及整个空间，而杂交结果依赖于初始分布。因此，一个完整的遗传 算法应当是选择、变异和杂交运算共同构成的。 2 2 4 控制参数设定 在g a 的应用中，要首先给定一组控制参数，如种群规模、杂交率、变异率、 进化代数等。控制参数的选取不同会对g a 的性能产生很大的影响，要想得到g a 的最优性能，必须确定最优的参数设置。通常控制参数的设定分为三种方法： 1 ) 根据自己的经验，对控制参数进行设定。 2 ) 首先选取有限的控制参数表，然后对每个控制参数表执行g a 以比较它们 的性能，并选取最优的控制参数表。 3 ) 将控制参数的选取问题作为一个优化问题，从而将g a 控制参数的选取也 采用一个g a 完成。 2 _ 3 标准遗传算法的马氏链模型 记为变异算予，已为交叉算子，五为选择算子： 第二章标准遗传算法 r = 乇。疋。瓦 则标准遗传算法为 工( ) = t ( x ( n 一1 ) ) = 。l 。瓦( j 0 1 ) ) 从重( o ) 出发，即得到种群序列 萱( n ) ； o ) 。 定理2 3 1不可约非周期的马尔可夫链存在极限分布，且极限分布与初始分 布无关。 定理2 3 2 标准遗传算法的种群序列 j ( h ) ；”o ) 是有限齐次不可约非周期的 马尔可夫链。 定理2 3 3 标准遗传算法的种群马尔可夫链序列 j ( n ) ；月o ) 存在极限分布。 证明：由定理2 3 。2 ，标准遗传算法的神群序列f 量0 ) ；h o 是有限齐次不可约 非周期的马尔可夫链，根据定理2 3 1 知 l i mp = 而2 熙j ( 黧口”珊p 却而 则f ( 矿) 是s 上的分布，且 万( ，) p 豆( n ) = 乞y c ( o ) = 两= z ( 三) y e s ” 则证。 定理2 , 3 3 说明标准遗传算法的种群马尔可夫链是分布收敛的，它不依赖于初 始种群的选择，即 f ( 三) = l i mp 牙) = 2 2 ( 0 ) = p ) ( 乞e s ) 假定，是s 上的适应度函数，记 m 2 x r s ，1 妙( - ) 2 m e a 荨f ( x ) 若j ；n m = 西，贝0 l i me 2 ( n ) n m 雪( o ) = 三 l z ( f ) 0 ，则进行到i v y ( x ( o ) l 0 。并令 k = 0 、 = 0 。 s t e p1 ：若 ( p ，则转s t e p 2 ，否则输出j ( i ) 为目标值 s t e p2 ：对当前种群进行一次遗传算法迭代提中间种群f ( 一) 。计算种群的个体适应 度值，找出，( ) 的最优个体x 。，若f ( x 。) ，( x ( 2 ) ，贝0 令2 ( n + 1 ) = 矿( n ) 为 下一代种群。令k = + 1 ，”= h + i 。否则，令需( ) = x 。，2 ( n + 1 ) = ( x 。，五( n ) ，霸( ”) ) 为下一代种群令n = 月+ 1 。 s t e p3 ：以概率只判断需要进行线性搜索运算，转s t e p4 。否则转s t e p1 。 s t e p 4 ：计算g = 1 w ( x 忙) i ，若g s ，转s t e p 2 。 s t e p5 ：对当前点x ( 女) 进行传统算法搜索，确定搜索方向d ( n ，。然后用一维精确搜索 法计算出步长r ( 柏，得后续点x ( ) = x ( 。+ d ( f 。令k = k + 1 ，转s t e p1 。 从算法中可以得迭代点列：x ( o ) 呻x ( 1 一斗x ( _ x ( 川) 寸，其中x ( i ) 为 最速下降法和遗传算法交替迭代获取的点列，下降步中，遗传算法始终保持最优 第三章混合遗传算法 解。所以点列所对应的函数值是单调递减的，我们可以从原点列 x ( ) 中找到一子 列 x ( k d ) 使得该子列为下降步骤中遗传算法的迭代点列。可以证明 x ( k d 以概率1 收敛到最优解集夙其中口= 魄，f ( x ，) = m a x f ( x ) ，即 l i m x ( t ) 研= 1 0 0 3 3 2 遗传算法与模拟退火算法的结合 模拟退火算法是近年来特别引人注目的一种适用于求解大型组合优化问题的 技术。算法的核心在于模仿热力学中液体的冻结与结晶或金属溶液的冷却与退火 过程。在搜索最优解的过程中，模拟退火算法除了可以接受优化解外，还用一个 随机接受准则有限度地接受恶化解，并且接受恶化解的概率慢慢趋向于0 ，这使 得算法可能从局部最优中跳出，尽可能找到全局最优解，并保证了算法收敛。在 实际的应用中，模拟退火算法是从一个在定义域内随机产生的初始x o 出发的迭代 过程，在每一步，算法从当前点x 产生一个点y ，如果，( ，( y ) ，则y 被接受为 当前点，否则j ，仅以概率e x p t ( f ( x ) 一( y ) ) ，c 】被接受。在进行足够多的上述过程后 减小控制参数c 的值( c 开始时取较大的值) ，如此反复，直至满足某个停止准则 时算法终止。此时的当前点即为算法所得的近似解。 在传统的遗传算法中，当新产生的子代的适应值大于进化群体的方差闽值时， 子代被接受。但由于在遗传算法中存在所谓的欺骗问题，它使得问题可能需要较 长的等待时间来达到近似最优解，甚至使得用遗传算法所得到的解远离全局最优 解。考虑到这种情况，有人把模拟退火算法加到传统的遗传算法中。它的基本思 想是；假定，是一个新产生的适应值，是阈值。如果厂，则新个体被接受， 否则新的个体根据一定的可能性p = e x p ( f ( x ) 一，( y ) ) c 】被接受，这里c 是一个参 数，它类似与热动力学的温度。实验结果显示使用此方法大大减少了陷入局部极 小的概率，并且可导致快速收敛到全局极小值。 可以证明以下两个定理： 定理3 3 2 1 模拟退火遗传算法，当，斗0 时， 贾( n ) 概率强收敛到最优解 集m ，其中m = ，f ( x ) = m a x f ( x ) ) ，即 l i m ， 贾( ”) 仁肘) = 1 n - 定理3 3 2 2 在模拟退火遗传算法中，若父代不参加竞争，则 卫( ”) ) 不可能 概率强收敛到最优解集m ，其中m = 缸。f ( x ，) = m a x f ( x ) ) ，即 l i mp 贾( ”) c 肘 o 。因此 p ( c o ) = ( 圪( 豆，矿) ；量，矿s n ) 具有唯一的不可约非周期常返类m + 。而s m + 中的种群均为非常返状态。于是 j ( h ) ； 0 是强遍历的，即有 且万口) = l ，于是 九m 则证。 l i m ， j ( ) = ，贾( o ) = 石( 而( j ；m + ) h l i mp j ( ) m + 贾( o ) ) h - ：p o o = l i m p 贾( h ) = f ，牙( o ) ) ”。r = = 石( 矿) = 1 几m 定理5 1 4 4 当 斗o o 时，s e g a 算法输出的最优可行解y 以概率1 收敛到满 意解集m ，m = x l s ，使，( x f ) 2 霉嚣，( z ) ) 即 l i m 尸 】，m i x ( o ) = 1 月 证明：根据定理5 1 4 3 ，s e g a 算法中每个子种群序列 霄( n ) ；”o 以概率1 收敛到满意种群集，且当n _ + o 。时，对于s e g a 算法输出的最优可行解】，有： l ，j 0 ) ，贾( ) m 即贾0 ) n m ， 即 j i mp 膏( ) n m 庐贾( o ) ) = 1 n - - , o o 3 2 m m m芒_ y ，y _ y 膳m m芒_x， o o o 降 净 懵 i i n一晤 第五章一种新的混合分布式并行遗传算法 因为r 是种群膏( ) 的最优可行解，则当月斗o o 时y m 则证。 5 1 5s e g a 算法的时间复杂度分析 对于遗传算法我们期望知道首次到达最优解集的时间。由于遗传序列是随机 的，首次到达的时间也是随机的。这里我们关心的是首次到达时间的期望值。 定义5 1 5 1 设疆( ”) 是遗传算法序列，称 t = m i i l 伽；j ( ”) n m 奶m 是算法的最优解集 为遗传算法的首达时间。 为了估计s e g a 算法的首达时间，我们给出了以下方法。将种群分解为n 个 互不相交的子种群集合韪( 琏 ) ，对于子种群p o p l ，它采用杰出子种群选择。为此， 记p 为其中一个子种群代替了子种群p o p l 的概率。 弓，+ 1 = p ( 1 - p 州) 则 三五( 弓一1 ) = l 而 于是 从而 p 0 一j f = 0 肿l ( 1 一黾j + 1 ) 州 丑q 扩1 ) = 马一1 ( 1 一& ，+ l f r = l = - e j l 匹( 1 一弓一1 ) 7 】 f = l 一铀c 去，2 去 电子科技大学硕士学位论文 、o 1 1 联d j = l 而雨 一1 一， j 从理论上讲，s e g a 算法的首达时间期望值随着子种群个数的增加而减小，但 实际上这并不总是成立的。 5 1 6s e g a 算法在有约束性问题中的应用 5 1 6 1 标准遗传算法在解决有约束性问题时的局限 将遗传算法应用于约束最优化问题的关键是对约束问题的处理。假设标准遗 传算法按无约束问题那样求解，在搜索过程中计算由算法产生的目标函数值，并 检查是否有约束违反。如果没有违反，则表明是可行解，就根据目标函数值为其 指定一个适应值；否则，就是不可行解，因而没有适应值( 适应度为o ) 。除了许 多实际问题是高度约束的之外，这样的处理实际上是行不通的，因而遗传算法不 可能从不可行解中得到一些信息。 图5 - 1 一种可能的问题域 例：见图5 1 ，集合a 、1 3 、c 均为问题的编码域，集合a 、b 为可行解域，其 中问题的最优解位于集合b 中，集合c 为非可行解域。对于标准遗传算法而言， 个体空间只能是集合a 、b 。若初始种群贾位于集合a 中，而最优解不在包含种群贾 的最小模式善暖 中。由于选择算子只是在一个固定的种群中进行选择，选择的结 果不可能跑到种群之外。对于种群之外更好的个体是不可能被选择得到的，选择 的结果依赖于初始种群；而杂交算子仅在包含种群的最小模式；暖】中变化，仅用 选择和杂交不可能越过瓠贾】。因此选择和杂交仅在一个“予空间”中搜索，而变 异虽然在一个个体的邻域进行，它可能越过孝暖】，从而扩大搜索范围，原则上可 以扩大到整个个体空间，但是，在变异操作中，变异率往往取得很小，如果变异 率太大，遗传算法就会退化为随机搜索，而遗传算法的一些重要的数学特性和搜 索能力也不复存在了；并且若在变异操作中，所产生的解位于非可行解域，标准 第五章一种新的混合分布式并行遗传算法 遗传算法则认为此解为非法的。综上所述，标准遗传算法在解决有约束条件的问 题时，有很大的局限性。 借鉴常规方法中的罚函数法罚是一个方便的选择。将罚函数包含到适应度评价 中，可以采用以下形式： ，( x ) + ，于( x ) 式中，罚函数，o ) 为满足下列条件的连续函数： 叫卷i 妻 ，