（计算机应用技术专业论文）遗传算法及其工具软件包的研究与设计.pdf

遗传算法及其工具软件包的研究与设计 摘要 遗传算法因其简单、通用、鲁棒性强的特点而被广泛应用于组合优化、机器学习等 许多领域。为遗传算法设计一个工具软件包是一项有意义且必要的工作。 本文首先讨论了遗传算法的 发展情况极其相关的 重要概念与技术。接下来深入剖析 了一个采用面向 对象技术设计的 遗传算法的类库 ( g a l i b ) o 本文在此基础上，结合当今遗传算法领域中的最新研究成果对 g a l i b进行了改进: 通过扩充解决多峰搜索的算法，使 g a l i b具有更广泛的 应用领域; 针对现行算法计算 量大、效率低的缺点， 将并行分布式遗传算法的最新研究成果进行分析、归纳，并镶嵌 于工具包中，改善了 工具包的性能。最后， 通过运用 g a l i b解决具体应用的实例，验 证了该工具包的强大功能与良好性能。 * 文 结 尾 对 全 文 进 行 了 总 结 ， 并 提 出 了 进 一 步 的 研 究 方 向 了 关健字: 遗传算法、工具软件包、多峰搜索、并行遗传算法 r e s e a r c h o f g e n e t i c a l g o r i t h m a n d d e s i g n i n g o f g a c l a s s l i b r a r i e s a b s t r a c t g a ( g e n e t i c a l g o r i t h m ) ， w h i c h i s o f s i m p l e，g e n e r a l a n d r o b u s t c h a r a c t e r s a p p l i e d in ma n y fi e ld s s u c h a s c o m b i n a t o r i a l o p t imi z i n g , ma c h i n e l e a r n i n g a n d d e v e lo p i n g a s o ft wa r e p a c k a g e f o r g a i s a n e c e s s a ry a n d v a l u a b l e w o r k . ， h a s b e e n s o o n . s o t h e f i r s t p a rt o f t h i s p a p e r m a k e a t h o r o u g h d i s c u s s i o n o f t h e i m p o rt a n t t h e o r i e s a n d t e c h n i q u e s o f g a . t h e n t h i s p a p e r a n a l y z e a w e l l d e s ig n e d g a c l a s s l i b r a r i e s - - g al i b， wh i c h i s d e v e l o p e d b y u s i n g o o p t e c h n i q u e a n d c + + l a n g u a g e . o n t h e b a s e o f t h o s e s t u d y a n d a n a l y s i s ， a n d b y a p p l y i n g t h e a d v a n c e d s t r a t e g y a n d c u r r e n t r e s e a r c h i n g r e s u l t i n g a f i e l d，s o m e i m p r o v e m e n t a r e m a d e f o r g a l i b. f i r s t e x p a n d g a l i b t o m a k e i t c a p a b l e t o s o l v e t h e p r o b l e m o f o p t i m i z i n g f u n c t i o n s o f m u lt i p l e p e e k s . s e c o n d , w i t h t h e d i s t r i b u t e e n v i r o n m e n t o f p v m, i m p l e me n t s o m e o f t h e p a r a l le l g e n e t i c a l g o r i t h m t o m a k e g a l i b m o r e e f f i c i e n t a n d p o w e r f u l . i n t h e l a s t p a rt o f th i s p a p e r， w i t h t h e h e l p o f g a l i b， s o m e g a a p p l i c a t i o n i mp l e m e n t e d ,wh i c h i s t o s h o w h o w t o u s e g al i b t o f a c i l i t a t e t h e p r o g r a m mi n g r e s e a r c h i n g i n g a f i e l d， a n d a l s o t o a tt e s t t h e e ff e c t i v e a n d e f f i c i e n c y o f ga l i b. f i n a l l y ， t h e n e w t r i a l s o f t h e p a p e r a r e c o n c l u d e d a n d r e s e a r c h t r e n d s i n t h e f u t u r e i s p o i n t o u t . k e y w o r d : g a ( g e n e t i c a l g o r i t h m ) g e n e t i c a l g o r i t h m) g a l i b，o p t i mi z i n g o f mu lt i p l e p e e k s . p g a ( p a r a l l e l 引言1 引言 近代科学技术发展的显著特点之一是生命科学与工 程科学的相互交叉、相互渗透和 相 互 促进。 遗 传算 法 ( g a - g e n e t i c a l g o r i th m s ) 的 蓬 勃 发 展正 体 现了 学 科发 展的 这 一 特 征和趋势。 遗传算法借鉴于达尔文的物竞天演、优胜劣汰、适者生存的自然选择和自然遗传的 机理，其本质是一种求解问题的高效并行全局搜索方法。 它能在搜索过程中自 动获取和 积累有关搜索空间的知识，并自 适应地控制搜索过程以求得最优解。其主要特点是群体 搜索策略和群体中个体之间的信息交换 ，搜索不依赖于梯度信息。它尤其适用于处理传 统搜索方法难于解决的复杂和非线性问题， 可广泛用于组合优化、机器学习、自 适应控 制、规划设计和人工生命等领域，是2 1 世纪有关智能计算的关键技术之一。 尽管遗传算法已经被应用于解决各种各样的问题，但是它们的基本思想是一致的。 所以，当研究者开发各 自的遗传算法程序时，会重复许多他人的工作，这造成了很大的 时间浪费。因此，有必要为遗传算法设计一个工具软件包，以 便为其他研究者开发新的 遗传算法铺平道路，为遗传算法的研究尽微薄之力，这也是作者研究遗传算法工具软件 包的初衷。 下面介绍一下本文的结构: 第一章:介绍了遗传算法的历史与现状，分析了与遗传算法相关的重要技术，并讨 论了遗传算法的改进与发展方向。由于本文旨 在研究遗传算法的工具软件包的设计，所 以这部分重点介绍了与遗传算法相关的重要概念及技术，因为这些是一个成功的遗传算 法工具软件包所要尽量全面实现的内容。 第二章:深入剖析了一个现有的遗传算法的工具软件包 g a l i b ，这部分着重分析 了g a l i b的设计结构， 进而总结出它的设计思想及设计特点， 并介绍了如何利用g a l i b 进行遗传算法程序开发。 第三章、第四章:在充分分析g a l i b的基础上，本文指出了g a l i b存在的不足之 处，并分两个章节讨论了对 ga l i b所做的改进和扩充，这也是本文的主要创新工作部 分:一是在工具软件包的统一框架下，构造了对多峰情况优化的遗传算法工具包，这不 仅大大扩充了工具包的应用领域和功能， 而且可使更多的学者方便地参与研究这一热点 课题;二是针对现行算法计算量大、 效率低的缺点，将并行分布式遗传算法的最新研究 成果进行分析、归纳，并镶嵌于工具包中，这大大提高了计算效率，改善了工具包的性 育 旨 。 第五章:利用 g a l i b开发了两个解决不同问 题的遗传算法应用程序，来说明如何 运用这个软件包进行遗传算法问题的 研究，并进一步验证了 g a l i b的功能强大，使用 方便，便于扩展等重要特点。 本文的最后，总结了全文并提出在设计中仍有待改进的地方。 其中，二、三、四、五章为了便于分析讨论，在说明过程中给出了一些程序代码的 主要 片段 。 第一章遗传算法综述 第 一 章遗传算法综述 第一节绪论 早在六十年代中期，美国、德 国的一些科学家就开始研究用模仿生物进化的方法求 解复杂的优化问题的方法。但 由于两方面的原因当时未受到普遍的重视 ，一是这种算法 本身的不成熟，二是这种算法需要较大的计算量，而当时的计算机容量小，速度慢，所 以难于实际应用。随着人工神经网络理论与机器学习理论的发展以及计算机容量及速度 的提高，遗传算法 ( g e n e t i c a lg o r i t h m s , g a )逐步成熟，并受到各个学科研究者的普 遍重视。 遗传算法 ( g e n e t i c a l g o r i t h m - - g a ) ， 是由美国m i c h i g a n 大学的j .h o l l a n d 教授于 1 9 7 5 年首先提出的一类仿生型优化算法m，是以达尔文的生物进化论和孟德尔的遗传变异理 论为基础，模拟生物界进化过程，自 适应启发式全局优化的搜索算法。它在思路上突破 了原有最优化方法的框架。其主要特点是群体搜索策略和群体中个体之间的信息交换， 搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问 题，可广泛用于组合优化、机器学习、自 适应控制、 规划设计和人工生命等领域， 是2 1 世纪有关智能计算的关键技术之一。 基本术语 由于遗传算法是自 然遗传学和计算机科学相互结合渗透而成的新的计算方法，所以 遗传算法中经常使用如下一些有关自 然进化的基本术语: 1 . 基因与染色体: 染色体是遗传物质的 主要载体， 基因是它的功能单位及结构单位，数个基因组成染 色体。在遗传算法中处理的是染色体， 或叫基因型个体 ( i n d iv id u a l s ) ， 它对应的是数据 或数组，表示了所求解问题的一个可能解。染色体中基因的位置称作基因座 ( l o c u s ) 而基因所取的值叫等位基因 ( a l l e l e s ) . 2 . 基因型与表现型: 它们是染色体的两种表示模式。 所谓表现型是指生物个体所表现出来的性状，而基 因型指与表现型密切相关的基因组成。 第一章遗传算法综述 3种群: 一定数且的个体组成了群体( p o p u l a t i o n ) ，即种群。群体中个体的数目 称为群体的大 小( p o p u l a t i o n s i z e ) ， 也叫群体规模。 4 . 适应度: 每个个体对环境的适应程度叫做适应度( f i t n e s s ) . 5 . 遗传操作: 对染色体实施的一些操作 ( 处理)如交叉、变异等。 6 . 控制参数: 为了控制被实施遗传操作的染色体的比 例而设置的参数。常用的控制参数有交叉概 率 ( 常用 p 。 表示) ，它决定了所希望交叉染色体的数目 ;变异概率 ( p 砂， 它决定了所 希望被变异基因的数目。 二. 采用遗传算法求解问题的 一般步 砚 1 . r - 0 , 初始化染色体群体p ( 0 ) ，形成第 1 代的侯选解; 2 .评价群体p ( t ) 中每个染色体，得到每个染色体的 适应值: 3 .根 据适 应 值， 从 p ( t ) 群体 ( 即 第t + l 代的 侯 选解 ) 中 选 择 父 母染 色体 ，复 制 到 新一 代 群体p ( t + l ) 中，即形成t + 1 代的匹配集; 4 .对 p ( t + 1 ) 群体 ( 此时为第 t + 1 代的匹配集)中的染色体实施遗传操作 ( 如交叉、变 异)产生后代新染色体，即 形成下一代的侯选解; 5 对 p ( t + 1 ) 群体 ( 此时为 t + 2代的侯选解)中的新染色体重新评价，如果满足终止条 件停止计算，并返回最好的染色体 ( 问题的解) :否则，令t = t + l ， 再从3 . 开始继续。 三. 遗传算法中 的五个基本要素 ; 编码; 初始群体的设定; 适应度函 数 ( 也称评价函数)的设计: 遗传操作设计; 控制参数。 这 5个要素构成了 遗传算法的核心内 容。我们将在下一节对它们作详细深入的讨 a生乐 第一章遗传算法综述 四. 与其它算法的比 较 传统的解决优化问题的方法有穷举法、常规的数学优化方法、动态规划法等。穷举 法需要对对每种可能的情况进行考察，太耗时，而且有时可能解的数 目是无限的，例如 和为 1 的实数组合是无限的。而常规的数学优化方法，如基于梯度寻优的技术虽然求解 快， 但通常只能得到局部最优解，而且需要目 标函数是可微的。遗传算法则克服了这两 方面缺点，因而有很好的应用前景。 其它人工智能的 方法有人工神经网络a n n , 基于知识的系统k b s 、 模糊逻辑系统f l s , 模拟退火 s a等。 a n n 对于维数过高的系统实际效果不好，而且需要进行大量的预处理。 k b s , f l s 在控制中的应用依赖于所解问 题的先验知识. a n n 则不断学习 系统的输入输出 关系。s a是一类求解组合优化问题的有效的随机迭代近似算法，在大系统优化方面引 起了人们的关注， 它利用类似于组合优化的统计机理，但是它的可扩展性不如遗传算法。 遗传算法强调重新组合与生物系统中的其它运算，一但自 然界中的其它现象被人们理 解，就可扩充到遗传算法中 去， 所以 说遗传算法具有可扩展性。遗传算法与传统的搜索 方法相比有以下特点: 1 ，遗传算法 处理的是参数集合。 2 .遗传算法同时搜索解空间中的多个点，因而能快速全局收敛。 3 .遗传算法只需一个适应度函数，不需导数或其它辅助信息，因而有广泛的适应性。 4 ，遗传算法使用概率规则指导搜索而非确定性规则，所以能搜索离散的有噪声的多峰 值的复杂空间。 5 .评价为选择提供了依据，因此遗传算法的搜索不是盲 目的或穷举的。 第二节 遗传算法的理论基础 h o l l a n d 的模式式定理通过计算有用相似性，即模式 ( s c h e m a ) ,奠定了 g a的数学 基础。 该定理是遗传算法的主要定理， 在一定程度上解释了遗传算法的机理、 数学特性、 很强的计算能力。不失一般性，我们以二值串作为编码方式来讨论模式定理: 定义2 . 1 基于三值字符集厦 0 , 1 ,* 所产生的能描述具有某些结构相似性的。 、1 字 符串集的字符串称作模式。 以长度为5 的串为例，模式* 0 0 0 1 描述了在位置2 , 3 , 4 , 5 具有形式 “ 0 0 0 1 ”的所 有 字 符串 ，即 0 0 0 0 1 , 1 0 0 0 1 。 由 此 可以 看出 ， 模 式的 概 念为 我 们提 供了 一 种简 洁的 用 于描述在某些位置上具有结构相似性的 0 , 1 字符串集合的方法。 二. 模式定理 引入模式后， 我们看到一个串实际 上隐含着多个模式 长度为 1的串 隐含着 2 个 模式) ，一个模式可以隐含在多个串中， 不同的串之间通过模式而相互联系。遗传算法 第一章遗传算法综述 中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了 解什么性质被延续，什么 性质被丢弃，从而把握遗传算法的实质 这正是模式定理所揭 示的内容。 定义 2 . 2 模式 h中确定位置的 个数称作该 模式阶，记作 。( h ) 。比如模式0 1 1 * 1 *的阶数为 4 ， 而模式 。 * 为 1 。显 然，一个模式的阶数越高，其样本数就越 少，因而确定性越高。 定义 2 . 3 模式 h中第一个确定位置和最后一个确定位置之间的距离称作该模式的 定义距，记作6 ( h ) 。比 如模式o i l *1 *的定义距为4 ，而模式0 * 为0 e 模式阶和定义距描述了模式的基本性质。下面我们通过分析遗传算法的三种基本的 遗传操作对模式的作用来讨论模式定理。令 a ( t )表示第 t代中串的群体，以 气 ( t ) ( i = i , 2 , . . . , n ) 表 示第t 代中 第j 个个 体串 。 ， . 选择 在选择算子作用下， 与某一模式所匹 配的样本数的增减， 依赖于模式的平均适应度， 与群体平均适应度之比:平均适应度高于群体平均适应度的将呈指 数级增长:而平均适 应度低于群体平均适应度的模式将呈指数级减少。其推导如下: 假设在第 t 代，群体 a ( t ) 中模式 h所能匹配的样本数为 m .记作 。 似 t ) 。在选择 中，一个串是根据其适应度进行复制的。更确切地说，一个串是以 概率 p ,= f , / e f . 进行 选择的， 其中 f , 是个体 a ; ( t ) 的 适应度。假设一代中 群体大小 ( 群体中个体的总数)为 n ，且个体两两互不相同，则模式h 在第t + l 代中的样本数州h , t + 1 ) 为: m ( h . t + l ) = m ( h , t ) n f ( 功 /e 乓 伦1 ) 其中f ( h ) 是 模式n所 有样 本的 平 均 适应 度。 令 群 体平 均 适应 度 为 f . , 二 e f , / n ， 则 有; m ( h , t + l ) = m ( h , t ) f ( 动 / f . , ( 2 . 2 ) 现在 假 定模 式h 的 平 均适 应 度一 直 高于 群 体 平均 适 应度， 且 设高 出 部 分 为c f-q. c 为常数，则有: m ( f t t + l ) = m ( h , t ) ( f e , + c f ,9 ) / f ,9 = m ( h , 0 ) ( 1 4 - c ) ( 2 . 3 ) 假设从t = 0 开始，c 保持为常值，则有: m ( 双t + 1 ) =m ( 双。 ) ( 1 +c ) t ( 2 . 4 ) 2 . 交叉 然而仅仅有选择操作， 并不能产生新的个体，即不能对搜索空间中新的区域进行搜 索，因此引入了交叉操作。下面讨论模式在交叉算子作用下所发生的变化， 这里我们只 考虑单点交叉的情况、 模式h 只有当交叉点落在定义距之外才能生存。在简单交叉 ( 单点交叉)下的h 的 生存概率p , = 1 - 而模式h z 的定义距 为 1 ， 则h z 遭破坏的概率为p a 6 ( h 2 ) / ( 1 - 1 ) = 1 / 5 ， 即生存存概率为4 / 5 . 而交叉本身也是以一定的 概率p 。 发生的，所以模式h 的生存概率为 p s 1 - p p d 二 1 - p 6 ( h ) / ( 1 - 1 ) ( 2 . 5 ) 现在我们考虑交叉发生在定义距内，模式 h 不被破坏的可能性。在前面的例子中， 若a的配偶在位置2 , 6 上有一位与a 相同 则拭将被保留。 考虑到这一点，式 ( 2 . 5 ) 给出的生存概率只是 一个下界，即有 p , 1 - p , 5 ( h ) / ( 1 - 1 ) ( 2 . 6 ) 可见模式在交叉算子作用下短距的模式将增多. 3 . 变异 最后考虑变异操作。假定串的某一位置发生改变的概率为 p m ，则该位置不变的概 率为1 - p m ，而模式h 在变异算子作用下 若要不受破坏，则其中所有的确定位置 ( 为 “ q . , 或 “ 1 ” 的 位) 必 须保 持 不 变。因 此模 式h 保 持 不 变的 概率 为 ( 1 - p 砂 o (h ) ， 其中。 ( h ) 为 模式 h 的阶数.当p m - m ( h , t ) ( f ( h ) / f a g ) l 1 - p 5 ( h ) / ( 1 - 1 ) 一 。 ( h ) p m 7 ( 2 . 9 ) 式 ( 2 . 9 )忽略了 极小项 ( p . - 6 ( f / ) / ( 1 - 1 ) + o ( h ) p m ) o通过式( 2 . 9 ) ,我们就 可以给出模式定理。 定理 2 . 1( 模式定理)在选择、 交叉和变异的作 用下，具有低阶、短定义距以及平 均适应度高于群体平均适应度的模式在子代中将得以指数级增长。 但存在一个问题还有待回答:为什么这样一种性质就有利于找到全局最优解呢?统 计学中的双角子机问题表明e2 1 :要获得最优的可行解，则必须保证较优解的样本数呈指 数级增长。 而模式定理保证了较优的模式 ( 遗传算法的 较优解) 的样本数呈指数级增长， 从而给出了遗传算法的理论基础。 三. 积木块假设 定义2 . 4 具有低阶、短定义距以 及高适应度的模式称作积木块。由 上面的定理可知 积木块将以指数级增长。 假设 2 . 1 积木块假设( b u i l d i n g b l o c k h y p o t h e s i s ) 低阶、短距、 高平均适应度 的模式 ( 积木块) 在遗传算子作用下，相互结合， 能生成高阶、长距、 高平均适应度的 模式， 可最终生成全局最优解。 上面的模式定理保证了较优的模式 ( 遗传算法的较优解)样本数呈指数级增长，从 而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而这 里的积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子 作用下，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。 第一章遗传算法综述 第三节 遗传算法的技术方法 编码与译码 编码与译码是执行遗传算法时包含的两个数据转换操作。编码是表现型到基因型的 转换， 是把搜索空间中的参数或解转换成遗传空间的染色体 ( 由基因按一定结构组成， 也称个体 ) :译码是相反的转换操作。 评估规范和原理: 评估编码策略常采用以下 3个规范闭: 1 )完备性( c o m p l e t e n e s s ) :问题空间中的所有点 候选解)都能作为遗传算法空 间中的点 ( 染色体) 表现。 2 )健全性( s o u n d n e s s ) :遗传算法空间中的染色体能对应所有问题空间中的候选 解。 3 ) j 卜 冗余性( n o n r e d u n d a n c y ) :染色体和候选解一一对应。 上述的 3个编码评估规范虽然带有普遍的意义，但是缺乏具体的指导思想，特别是 满足这些规范的编码设计不一定能有效地提高遗传算法的搜索效率。 相比 之下， d e j o n g 提出的编码原理是一个较为客观明 确的编码评估准则k j ，其内 容如下: 1 )有意义积木块编码规则:所定编码应当易于生成与所求问 题相关的短距的低阶 的积木块。 2 ) 最小字符集编码规则:所定编码应采用最小字符集以使问题得到自然的表示或 描述。二值编码最合此规则。 上述的两个编码原理也仅仅是为编码设计提供了 一定的准则。在实际 应用这些准则 时仍然是针对具体问题， 设计出 具体有效的编码。 2 . 编码技术: 1 )一维染色体编码: 一维染色体是指经编码转换后，相应的基因呈一维排列。一维染色体采用的数据结 构可以是一维数组或列表等。 例如， t s p 问题的 编码可以是由城市编号组成的列表， 如 1 , 3 , 2 , 4 ) 。 二值编码是目 前遗传算法中常用的编码方法，其优点是: ( 1 ) 简单易行: ( 2 ) 符合最小字符集编码原则; ( 3 ) 便于用模式定理进行分析，因为模式定理就是以 二值编码为基础的。 但是，二值编码具有一定的映射误差，特别是它不能直接反映出所求问 题的本身结 构特征，因此很难满足生成有意义积木块编码的原则。目前一维编码己有许多新的提案 和方法，其中包括实数表示、格雷码表示和列表表示等m。 2 )多参数映射编码: 在优化问题中常常会碰到多参数优化问题，对此类问题常采用名参数编码。茸甚太 第一章遗传算法综述 思想是把每个参数先进行二 值编码得到子串，再把这些子串连成一个完整的染色体。 3 )多维染色体编码: 在许多应用场合，问 题的解呈二维或多维的 表示，如图像处理，这种场合宜采用多 维染色体编码。 4 )树结构编码: 前述的编码方法有若干缺点: ( 1 )个体的表示很难反映求解问题的本身结构或者层次: ( 2 ) 需要特定的编码和译码技术，把问 题的解表示成合适的形式; ( 3 ) 不易表示高层次知识及相应的学习系统。 作为对策， 可直接把问 题的结构表示作为染色体来处理，从而省去编码与译码a 例如，树结构编码就是典型的一种方式。 二. 群体的设定 ， . 初始群体的设定: 初始群体中的个体一般是随机产生的，初始群体的设定常采取如下的策略: 1 )根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然 后，在此分布范围内设定初始群体。 2 )先随机生成一定数 目的个体，然后从 中挑出最好的个体加到初始群体中。这种过 程不断迭代，直到初始群体中个体数达到了预先确定的规模。 2 . 群体多样性: 群体规模m 越大， 群体中个体的多样性越高， 算法陷入局部解的 危险就越小。 所以， 从考虑群体多样性出发， 群体规模应较大。 但是，群体规模太大会带来若干弊病:一是 从计算效率着眼，群体越大，其适应度评估次数增加，所以计算量也增加， 从而影响算 法效能;二是群体中个体生存下来的概率 ( 即选择概率)大多采用和适应度成比例的方 法 ，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个 体却被淘汰 s 7这会影响匹配集的形成， 从而影响交叉操作。另一方面， 群体规模太小， 会使遗传算法的搜空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成 熟 收 敛 ( p r e m a t u r e c o n v e r g e n c e ) 现 象。 显 然， 要 避 免未 成 熟收 敛现 象 ， 必 须保 持群 体 多样性，即群体规模不能太小。 3 . 种群的更新方式: 在简单遗传算法中采用的是无重叠种群，即从上一代种群 ( 种群规模为 n )中选择 n个体，对它们进行复制、交叉、变异等操作产生新一代群体。另外一类遗传算法则采 用有重叠种群的更新方式，即按一定比例 g从上一代群体中挑选 n g个个体参与遗传 操作，而其它个体直接保存到下一代中。这里的c是一个描述群体之间关系的参数g , 第一章遗传算法综述 称为代沟( g e n e r a t i o n g a p ) 。通过g 的引用，可将两种群体的更新模式描述为: 非重叠群体 0 g 1重叠群体 尹|七|、 - g 三 适应度函数 7 . 评价函 数 ( 适应度函 数) ; 由于遗传算法中，适应度函数用于对染色体比较排序并在此基础上计算选择概率， 所以适应度函数的值要取正值。由 此可见，在许多场合需要将目标函数映射成函数值非 负的适应度函数，且需要将最小化问题转化为最大化 问题。下面是一个能达到上述转化 要求的有效方法，g ( x )表示未经转化的目 标函数， f ( x ) 表示转化后的目 标函数: r c - - ,- g (x ) f ( x ) = 飞。 显然存在多种方式来选择系数 当 g ( x ) c m 。 二 其它情况 a m a x 。 g m a 、 可以是一个合适的输入值， 也可采用迄今 为止进行过程中 g ( x ) 的最大值或当前群体中g ( x ) 的最大值。当然c m a ， 也可以是前 k 代 中g ( x ) 的最大值。 c m a x 最好与群体无关。 2 . 适应度a数的定标( s c a l i n g ) 应用遗传算法，尤其用它来处理小规模群体时，常常会出现一些不利于优化的现象 或结果。例如，在遗传进行的初期，通常会 出现一些超常的个体，若按照比例选择策略， 这些异常个体有可能在群体中占据很大的比例，可能导致未成熟收敛现象。显然，这是 因为这些异常个体因竞争力太突出会控制选择过程，从而影响算法的全局优化性能。另 外，在遗传进化过程中， 虽然群体中个体多样性尚存在，但往往会出现群体的平均适应 度已 接近最佳个体适应度，这种情况下，个体间竞争力减弱，最佳个体和其它大多数个 体在选择过程中有几乎相等的选择机会，从而使有目 标的优化过程趋于无目 标的随机漫 游过程。对于未成熟收敛现象，我们应该设法降低某些异常个体的竞争力，这可以 通过 缩小相应的适应度函数值为实现;对于随机漫游现象，我们应设法提高个体间竞争力， 这可以通过放大相应的适应度函数值来实现。这种对适应度的缩放调整称作适应度定 标。自 从 d e j o n g开始引入适应度函数的定标以来，定标已 成为保持进化过程竞争水平 的重要技术。目前，定标方式大致有以下几种。 1 )线性定标( l i n e a r s c a l i n g ) 设原适应度函数 f ，定标后的适应度函数为 f ，则线性定标可采用下式表示: f = o f + b 式中，系数 a 和 b可以有多种途径设定，但要满足两个条件: ( 1 ) 原适应度平均值f 要等于定标后的适应度平均值。 第一章遗传算法综述 ( 2 )定 标 后适 应 度函 数的 最 大 值 f m a ， 要等于 原 适 应函 数 平 均值 f 、 的 指 定 倍数。 巨 口 f , m a x c m u u f a v g 其中，c m u 。 是为得到所期待的最优群体个体的复制数。 实验表明，对于一个典型的 不太大的群体而言( n = 5 0 - 1 0 0 ) , c m m 。 可在 1 . 2 - 2 .0 范围内取值。 2 ) 6 截断 ( s i g m a t r u n c a t i o n ) 6 截断是使用上述线性定 标前的一个预处理方法，目 的在于更有效地保证定标后的 适应度值不出现负值。这种方法主要利用了群体标准方差信息来对适应度进行预处理。 相应的表示式如下: f = f - ( f . , , - c 6 ) 式中，6 为群体中串的适应度的标准方差，c一 般为 1 , 3 之间的常数。 3 )乘幕定标 该定标方式可直接定义如下: f = f k 式中，幂指数k与求解问 题有关， 而且在算法过程中可按需要修正。 4 )指数定标 f = e x p ( - b f ) 这种机制是受模拟退火方法的发得出的。 此外，使用适应度定标技术还可处理那些无目 标函数组合优化问题，在此情况下， 我们只能获取个体性能之间相对好坏的概念，而不能计算或特别难以计算个体的目标函 数值，因而我们只能依据群体内个体性能的相对优劣，以一定的函数映射方法对个体性 能进行适应度定标， 当然， 解决无目 标函数组合优化问题还可选用后面提到的排序( r a n k ) 选择机制， 这实质上也是一种适应度定标方案。 3 . 适应度函数与问题约束条件: 处理有约束条 件问 题的一种十分自 然的方法是:在进化过程中， 迭代一次就设法检 测一下新的个体是否违背了约束条件。如果没有违背，则作为有效个体，反之，作为无 效个体被除去。这种方法对于弱约束问题求解还是有效的。但对于强约束问题，寻找一 个有效个体的难度不亚于寻找最优个体，所以此法不适用。 作为对策，可采取一种惩罚方法( p e n a l t y m e t h o d ) 。该方法的基本思想是设法对个 体违背约束条件的情况给予惩罚， 并将此惩罚体现在适应度函 数设计中。 这样一个有约 束优化问题就转换为一个附带考虑代价( c o s t ) 或惩罚( p e n a l t y ) 的非约束优化问题 i s l e 四. 遗传操作设计 遗传操作的任务就是对群体的个体按照它们对环境适应的程度 ( 适应度评估)施加 一定的操作，从而实现优胜劣汰的 进化过程。遗传算法包括三个基本遗传算子( g e n e t i c o p e r a t o r ) :选择( s e l e c t io n ) 、交叉 ( c r o s s o v e r ) 、变异( m u t a t i o n ) . 第 一 章遗 传 算 法 综 述 选择 选择是根据适应度， 从上一代产生的侯选解中选出一些解， 形成新一代的匹配集 ( 作 为后面进行交叉、变异等遗传操作中要用到的父母染色体)的操作。也称选择算子。在 决定具体采用哪种选择策略时应考虑两点: 1 )选出的接要有良 好的特征 ( 以 使产生优良的后代) 。 2 ) 在解空间中分散，以便能找到全局最优解而不是局部最优解。 目前常用的选择算子有以下几种: ， . 适应度比例方法: 适应度比例方法也叫 赌轮或蒙特卡罗( m o n t e c a r lo ) 选择。具体实现方法如下: !介扣 计算每个染色体v 的适应值f , ; 计算群体的适应值f = e f , ; 计算每个染色体v ; 的概率p j = f ;/ f ; 计算每个染色体v . 的累积概率 q l = 、.了、，户、，沙、卫少 a从曰c月以 e ) 重复 n次 ( n为群体规模) ，每次产生一个随机数，根据它选出一个染色 体作为父母。具体实现: 在【 。 ，1 区间产生一个随机浮点数 r ，若 r q l , 选染色体v i ， 若q i 1 实施局部化:把群体划分成若干子群体， 每个子群体独立地进行选择操作， 这样 可使 由 于出 现 不 适当 个 体 而产 生未 成 熟 收敛 的 现 象局 部化 。 ( 3 ) 实施单一化:把相同的个体单一化，目的是不允许群体中有若干个相同个 体出现。 ( 4 ) 增大配对个体距离:配对选择一般是随机进行的，其中缺少对个体间相似 度的判断，因此有可能使交叉结果未能产生新个体。作为改进，可用海明 距离测度来判断配对个体的相似度，并由此决定配对与否. 上述几种对策的效果各不相同。为了有效地克服未成熟收敛。这些对策也许要在进 化过程中分阶段使用或交替使用。 2 . 如何确保收效性 利用有限马尔柯夫链ee l 理论可以证明， 标准的遗传算法在任意初始化，任意交叉 算 子以及任意适应度函数下，都不能收敛到全局最优解。而通过改进遗传算法，即在选择 作用前 ( 或后) 保留最优解，则能保证收敛到群体最优解，但收敛到最优解所需的时间 却可能很长。 第四节 遗传算法的改进及发展 一 遗传算法的改进策略 八十年代以后， 遗传算法得到了迅猛地发展， 许多研究集中于遗传算法的性能改进， 即在保证全局收敛性的 前提下。 尽量提高收 敛速度，因而提出了许多改进策略，主要体 现在以下几个方面: 第一章遗传算法综述 改进选择复 制策略: 1 )静态友制:( s t e a d y - s t a t e r e p r o d u c t i o n ) 传统遗传算法是用子串替代父串，有些优质父串无法复制，而静态复制方法是用部 分优质的子串 代替部分父串并保留部分优质父串，而且大多数父串 被复制到下一代，这 样有利于提高算法的性能. 2 )无重申的静态复制: 无重串的静态复制是 对静态复制的一种改 进。在静态复制的基础上，将新产生的子 代个体同父代群体中的个体进行比较，如果己 有此个体则不被复制，否则将此个体复制 到下一代群体中，这就保持了群体的多样性。 2 . 棍合遗传算法: 遗传算法是一个通用的方法，但处理具有某些特征的具体问题时，如果能在遗传算 法中 插入与问题有关的知识，并与现有的一些 有效求解方法结合， 利用二者优点，可改 善求解效率。遗传算法与贪心算法求解电信网的布线问题，比单独采用二者的任何一个 的效率高。另外遗传算法与专家系统及传统的数学优化技术结合求解工程设计问题，也 可取得较好的效果。 3 . 自 适应遗传算法: 自 适应遗传算法是在算法中应用了自 适应策略。自 适应策略一般用于遗传操作及各 参数的选择。 对于不同的实际问题， 控制参数的值是不同的，即使对同一个问 题的不同 阶段， 它们的最优值也是不同的。 因此， 采用自 适应的方法控制参数值调整到各阶段的 最优值 ，能有效地提高算法的性能。 二. 遗传算法今后研究的主要课题 1 . 优化搜索方法的 研究: 一些对比实验还表明，如果兼顾收敛速度和解的品质两个指标，单纯的遗传算法方 法未必比其它搜索方法更优越闪 。为此，除了要进一步改进基本理论和方法外，还要采 用和神经网络、模拟退火或专家系统等其它方法相结合的策略间。 许多研究结果表明， 采用这种混合模型可有效提高遗传算法的局部搜索能力，从而一步改善其收敛速度和解 的品质。此外，探明 如何能充分发挥遗传算法优越性的问题性质和类型也是十分有意义 的工作 。 2 . 学习系统的 遗传算法研究: 以下是一些基于遗传算法的学习系统面临的课题冈; 第一章遗传算法综述 适合遗传算法的高层次知识的表示; 更通用的基于语义的操作; 搜索能力的分析: 更有效的体现和变动环境相互作用的