（信号与信息处理专业论文）一种优化混合策略遗传算法的研究与实现.pdf

山东大学硕士学位论文 - _ _ _ - 量_ 一ii i | 自目自_ _ 目_ _ _ _ 目自l _ _ _ _ - _ - _ l l l - _ _ _ _ l - l 一 中文摘要 遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适 应搜索方法，作为优化方法具有明显的优势。它在搜索优化问题的全局最优解上 具有良好的优势条件。遗传算法以编码形式工作，只使用目标函数信息，用概率 传递规则代替确定性规则，具有运算并行性，关心每次进化群体中个体的质量， 即问题解的质量。所以，被广泛应用于许多领域，成为求解全局优化问题的有力 工具之一。尽管遗传算法存在诸多优越的特点，但作为一种优化方法它仍存在着 自身的局限性，特别是存在着早熟、收敛速度缓慢和局部搜索能力不足的现象， 这都影响了遗产算法的性能。为了克服遗传算法的不足，提高g a 效率和收敛速 度，本文提出了一种改进交叉算子来改进g a 来求解函数最优化的问题的收敛速 度的新的改进型遗传算法一优化混合策略的遗传算法( o p t i m i z a t i o n a lm i x e d s t r a t e g i e sg e n e t i ca l g o r i t h m ，以下简称o m s g a ) 。本文中提出了两种新的交叉算 子单亲单对单子交叉和单亲双对单子交叉，这两种交叉算子的特点是在子代群体 生成过程中只有一个母体生成一个子体，通过对母体随机执行交叉算子产生出具 有不同形状的新个体。单亲交叉算子既可保证新一代个体具有成为可行解的基本 特性，提高个体的多样性，又可提高对解空间的搜索能力。单亲交叉算子能使任 何一个母体通过有限次的遗传交叉生成另一个新个体。 该算法通过混合概率的增强策略和减弱策略，实现自动地调整每代种群的交 叉策略的混合概率。在进化的初始，算法为每代种群设置相同的纯交叉策略选择 的概率，这种各个纯交叉策略的概率随种群的进化而不断发生变化，即增强和减 弱策略，这使得种群在每代进化时都要选择具有较大概率的交叉策略，使得种群 在每一代中选择混合概率较高的交叉策略的可能性提高，这种具有较高混合概率 的交叉策略就是能生成较好个体的交叉策略，而这种较大概率的交叉策略能够在 前几代进化过程中产生较好的子代种群，从而使算法提高收敛速度。更重要的意 义是提出新的改进策略，能够使g a 高效的处理优化问题，使g a 的应用更加深入。 算法在m a t l a b 上编程，并采用6 个经典函数进行测试，通过比较本文算法和纯 山东大学硕士学位论文 交叉策略遗传算法、正点交叉策略遗传算法，得出该算法在收敛速度上是优于纯 交叉策略的遗传算法和多点正交交叉遗传算法( m u l t i - p o i n to r t h o g o n a lc r o s s o v e r o p e l a t i o l lg e n e t i ca l g o r i t h m ，这里简称为m p o c g a ) 的。即该算法能够提高遗传 算法的收敛性，有效的改善了遗传算法在求解最优化问题的收敛性能。 2 关键词：遗传算法；优化策略：单亲单对单子交叉；单亲双对单子交叉 山东大学硕士学位论文 a b s t r a c t a sa no p t i m a lm e t h o d , g e n e t i ca l g o r i t h mh a so b v i o u sa d v a n t a g e s , w h i c hi sb a s e d o nt h en a t u r es e l e c t i o na n dg e n e t i ct r a n s m i s s i o nm e c h a n i s m ss u c h 弱l l i g hc o n a t e 础 s t o c h a s t i c ，s e l f - r e l i a n c e i th a sg o o da d v a n t a g e si nf i n d i n gt h eb e s to o b a la l l b 阳，j e l o f o p t i m i z a t i o np r o b l e m g e n e t i ca l g o r i t h mw o r k sw i t hc o d i n gf o r m , u s e so n l yo b j e c t f u n c t i o ni n f o r m a t i o na n du s e sp r o b a b i l i s t i ct r a n s f e rr e g u l a r , g e n e t i ca l g o r i t h mh a s o p e r a t i o n a lp a r a l l e l i s m a n de a l e sf o r e v e r yi n d i v i d u a lq u a n t i t yi ne v o l u t i o n a r y p o p u l a t i o n sn a m e l yt h eq u a n l i t yo fp r o b l e ms o l u t i o n t h e r e f o r e , g e n e t i ca l o g r i t h mi s u s e do ns e v e r a lf i e l d sa n db e c o m e so n eo fp o w e r f u lt o o l st os o l v et h eg l o b a l o p t i m i z a t i o nq u e s t i o n s a l t h o u g hg e n e t i ca l g o r i t h m h a ss e v e r a l c h a r a c t e r , a s a o p t i m i z a t i o nm e t h o d ，i te x i s t ss t i l li t sl i m i t a t i o n ，e s p e c i a l l ye x i s t e dt h ep h e n o m e n o no f p r e m a t u r e ，s l o wr a t eo fc o n v e r g e n c ea n dt h ed e f i c i e n c yo fl o c a ls e a r c ha b i l i t y , w h i c h a f f e e tt h ep e r f o r m a n c eo fg e n e t i ca l g o r i t h m i no r d e rt oo v e r c o m et h el i m i t a t i o no f g e n e t i ca l g o r i t h ma n dt oi m p r o v et h ee f f i c i e n c ya n dc o n v e r g e n c er a t eo fg e n e t i c a l g o r i t h ms o l v i n g f u n c t i o n o p t i m i z a t i o nq u e s t i o n s ，a n e wi m p r o v e d g e n e t i c a l g o r i t h m - o p t i m i z a t i o n a lm i x e ds t r a t e g i e sg e n e t i ca l g o r i t h m ( a b b r e v i a t e dt oo m s g a ) i sp r o p o s e db yi m p r o v i n gc r o s s o v e ro p e r a t o nt w o t y p eo fc r o s s o v e ro p e r a t o r s i i l 酉e p a r e n ts i n g l ep a i rs i n g l eo f f s p r i n gc l o s s o v e ro p e r a t o r ( s p s p c ) a n ds i n g l ep a r e n tt w o p a i r so fs i n g l eo f f s p r i n gc r o s s o v e ro p e r a t o r ( s p t p c ) a l ep r e s e n t e di nt h ep a p e r t h e c h a r a c t e ro ft w oc r o s s o v e ro p e r a t o r si st h a to n l ys i n g l ep a r e n tg e n e r a t e so n eo f f s p r i n gi n p r o c e d u r eo fg e n e r a t i n go f f s p r i n gp o p u l a t i o n , a n dg e n e r a t e sd i f f e r e n ts h a p en e w i n d i v i d u a lb yp e r f o r m i n gr a n d o m l yc l x ) $ s o v e ro p e r a t o rt os i n g l ep a r e n t s i n g l ep a r e n t c r o s s o v e re n s u r e st h a tan e wg e n e r a t i o nh a st h eb a s i cc h a r a t e ro ff e a s i b l es o l u t i o n , a n d i m p r o v e sd i v e r s i t yo fi n d i v i d u a la n ds e a r c ha b i l i t yt os o l u t i o nf i e l d s s i n g l ec i o s s o v e r o p e r a t o rc a nm a k ea n yo n ep a r e n tt og e n e r a t ea n o t h e rn e wi n d i v i d u a lb yf i n i t eo r d e r g e n e t i cc r o s s o v e r t h ea l g o r i t h mi m p l e m e n t sa u t o m a t i c a l l yt oa d j u s tm i x e dp r o b a b i l i t yo fc r o s s o v e r s t r a t e s yf o re v e r yg e n e r a t i o np o p u l a t i o nb yt h es t r e n g t h e na n dw e a k e ns t r a t e g yo f m i x e d p r o b a b i l i t y t h ei n t i l i z a t i o no fe v o l u t i o n , t h ea l g o r i t h ms e t st h eg a m em i x e dp r o b a b i l i t y 3 山东大学硕士学位论文 i 一 一 i 置e 鼍皇 o f p u r ec r o s s o v e rs t r a t e g yf o re v e r yg e n e r a t i o np o p u l a t i o n , w h i c hh a p p e n s t oc o n t i n u o u s c h a n g e sw i t he v o l u t i o no fp o p u l a t i o n t h eb 咖e i l g t h e l la n dw e a k e ns t r a t e g yo fm i x e d p r o b a b i l i t ym a k e sp o p u l a t i o ni ne v o l u t i o np r o c e d u r e t os e l e c tt h ec r o s s o v e rs t r a t e g y w i mm o r eh i g h e rp r o b a b i l i t y , a n di tm a k e st h ep o s s i b i l i t yb o o s t e dt h a tt h ea l g o r i t h m s e l e c t sc r o s s o v e rs t r a t e g yw i t hm o r eh i g h e rm i x e dp r o b a b i l i t yf o rp o p u l a t i o ni ne v e r y g e n e r a t i o n , a n dc r o s s o v e rs t r a t e g yw i t hm o l eh i g h e rm i x e dp r o b a b i l i t yi st h ec r o s s o v e r s t r a t e g yc a l lg e n e r a t em o r eb e t t e ri n d i v i d u a l si np r e v i o u se v o l u t i o np r o c e d u r e , s ot h a ti t i m p r o v e st h er a t eo fc o n v e r e n c eo ft h ea l g o r i t h m 这t h em o r ei m p o r t a n ts i g n i f i c a n c e i s t op r o p o s ean e w i m p r o v e ds t r a t e g ya n dm a k eg e n e t i ca l g o r i t h mt od e a le f f e c i e n t l y 、) l ，i t l l o p t i m i z a t i o nq u e s t i o n s ，a n dm a k et h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mm o r ed e e p e r b y p r o g r a m m i n gb ym a t l a bl a n g u a g ea n dg o m gt h et e s t t h a ti sc a r r i e do u tt os i x t r a d i t i o n a lf u n c t i o n s , t h er e s u l t so ft e s ts h o w st h ea l g o r i t h mi se x c e l l e n tt ot h es i n g l e c r o s s o v e rs t r a t e g yo fg e n e t i ca l g o r i t h ma n dm u l t i - p o i n to r t h o g o n a lc r o s s o v e ro p e r a t i o n g e n e t i ca l g o r i t h m ( m p o c g a ) i nr a t eo fc o n v e r e n c 宅f o rd e a l i n gw i t hf u n c t i o n o p t i m i z a t i o nq u e s t i o n s k e yw o r d s ：g e n e t i ca l o r i t n m ；o p t i m i z a t i o n a ls t r a t e g i e s ；s i n g l ep a r e n ts i n g l ep a i r s i n g | eo f f s p r i n gc r o s s o v e r , s i n g l ep a r e n tt w op a i rs i n g l eo f f s p r i n g ( ；l o s s o v e r 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：避日期：砌移f o - 劫 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盘越导师签名：宝必 日 期：搜翌：丝：p 山东大学硕士学位论文 第一章前言 遗传算法( g e n e t i ca l g o r i t h m s ，简称为g a ) 的基本思想就是基于上述进化论 和遗传学的思想，并引用了随机统计理论而产生的。g a 是强调目的性算法化的进 化过程，是一种基于优胜劣汰、自然选择的进化方法。适者生存和物种遗传思想 的搜索算法，它通过模拟生物在自然界中遗传变异与生存竞争等遗传行为，让问 题的解在竞争中得以进化，以求得到问题的满意解或最优解。 1 1 课题提出的来源、背景和目的 遗传算法基于达尔文适者生存优胜劣汰的进化原则对包含可能解的群体反复 使用遗传学的基本操作，不断生成新的群体，使种群不断进化，同时以全局并行 搜索技术来搜索优化群体中的最优个体，以求得满足要求的最优解。遗传算法尤 其适合不确定问题或非线性复杂问题的求解。近年来，g a 在组合优化求解、机器 学习、人工生命等领域已显示了它的应用前景和潜力，因而已成为国内外十分热 门的研究课题。 尽管遗传算法存在诸多优越的特点，但作为一种优化方法它仍存在着自身的 局限性，特别是存在着早熟收敛、收敛速度缓慢和局部搜索能力不足的现象。为 了克服遗传算法的以上不足使其性能得以提升，针对交叉和变异这两个遗传算法 的核心遗传操作。但主要的方法是对遗传操作算子的改进，尤其对交叉算子的改 进。本文正是为了提高g a 效率和收敛速度，针对交叉算子研究了一种通过改进交 叉算子来改进g a 来求解函数最优化的问题的收敛速度的新的改进型遗传算法一 混合交叉策略的遗传算法。 1 2 课题研究发展状况 1 2 1 遗传算法的研究历史 遗传算法研究的兴起是在8 0 年代末9 0 年代初期，但它的历史起源可追溯到6 0 年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法 的研究特点侧重于对一些复杂的操作的研究。1 9 6 5 年，h o l l a n d 教授首次提出了人 5 山东大学硕士学位论文 工遗传操作的重要性并将这些应用于自然系统和人工系统中。1 9 6 7 年，b a g l e y 在他的论文中首次提出遗传算法这一术语，发展了复制、交叉、变异、显性、倒 位等遗传算子，在个体编码上使用了双倍体的编码方法，首次提出了遗传算法的 自我调整概念，引入了适应度定标技术，创立了自适应遗传算法的概念，并讨论 了遗传算法在自动博弈中的应用。 在同一时期，r o s e n b e r g 也对一遗传算法进行了研究，他的研究依然是以模拟 生物进化为主，但他在遗传操作方面提出了不少独特的设想。1 9 7 0 年c a v i c c h i o 把 遗传算法应用于模式识别中。1 9 7 1 年w e i n b e r g 发表了题为活细胞的计算机模拟 的论文，提出了多级遗传算法。1 9 7 1 年h o l l s t i e n 在论文计算机控制系统中的人工 遗传自适应方法中阐述了遗传算法用于数学反馈控制的方法，第一个把遗传算 法用于函数优化。1 9 7 5 年h o l l a n d 出版了著名专著自然系统和人工系统的适配。 该书系统地阐述了遗传算法的基本理论和方法，提出了模式理论。同年，d ej o n g 在其论文遗传自适应系统的行为分析中，树立了遗传算法的工作框架。他提 出了诸如代沟等的新的遗传操作技术，推荐了在大多数优化问题中都较适用的遗 传算法的参数，还建立了著名的d ej o n g i 函数测试平台，定义了评价遗传算法性能 的在线指标和离线指标。 进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究 都成了十分热门的课题。b e t h k e 的博士论文提出了用w a l s h 函数来研究g a 的方法。 a l b e r t a 大学的b r i n d l e 在博士论文中( 1 9 8 1 ) 对选择策略进行了研究。这一时期的 研究成果主要在回答了g a 到底有何意义，有何价值。h o l l a n d 教授实现了第一个基 于遗传算法的机器学习系统一分类器系统，开创了基于遗传算法的机器学习的新 概念。1 9 8 5 年召开了第一届g a 的国际会议，以后每两年召开一次。 8 0 年代中期以后，随着g a 在经济预测方面的成功，掀起了一轮g a 发展的热潮。 特别是神经网络理论的发展，模糊逻辑研究的进步，给g a 的发展注入了活力和空 间。1 9 8 9 年，g o l d b e r g 出版了专著搜索、优化和机器学习中的遗传算法 ，奠定 了现代遗传算法的科学基础。g a 的文章从八十年代中期往后也逐年增加，现在每 年和g a 有关的文章近千篇。 进入9 0 年代，以不确定性、高度非线性、时间不可逆为内涵，以复杂问题为 对象的科学新范式得到了学术界普遍认同，由于遗传算法能有效地求解属于 6 山东大学硕士学位论文 n p h a r d 类型的组合优化问题，及非线性多模型、多目标的函数优化问题，从而得 到了多学科的广泛重视。1 9 9 1 年，d a v i s 出版了遗传算法手册，推广和普及了 遗传算法的应用。1 9 9 2 年，k o z a 艚j ：遗传算法应用于计算机程序的优化设计及自动 生成，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能等方 面。直到9 0 年代初，首次把遗传算法应用于电磁场的优化计算中针对遗传算法 求解效率和求解精度较低等缺点，不少人提出了改进方法。这方面的工作包括编 码技术的改进，初始化方法的设计，自适应算子的引入，进化方向算子的提出， 交叉策略、变异技术、选择机制的改进，适应度函数的选择、定标和约束条件的 处理，收敛准则的研究，表征群体多样性的指标的提出，并行遗传算法的实现和 混合遗传算法的发展等。目前g a 的研究已构成与神经网络，模糊控制并驾齐驱的 一大领域。 1 2 2 速传算法的研究现状 人们主要研究g a 算法的下面三个方面： 一是g a 改进。针对一些问题，研究者们提出了不同的选择策略和复制策略 ( b r i n d l e 、b a k e r 、g o l d b e r g 和d e j o n g ) 。还有一类改进是对种群中的适应度的分 布进行变换。对g a 的行为有实质影响的改进研究主要在这两方面，此外还有很多 与问题有关的g a 的变种。 第二个方面是g a 的收敛性研究。 第三方面就是g a 性能研究，包括与其它算法的比较研究。 遗传算法现阶段的研究重点是基本理论的开拓和深化及更通用、有效的操作 技术和方法的研究。 1 优化搜索方法的研究 一些对比试验还表明，单纯的遗传算法未必优于其它搜索方法。为此，需要 进一步改进基本理论和方法。另外，提高遗传操作的效率，充分发挥遗传算法优 越性也需进一步研究。 2 学习系统的遗传算法研究 基于遗传算法的学习系统现今面临的课题有： ( 1 ) 适合遗传算法的高层次知识的表示： 7 山东大学硕士学位论文 ( 2 ) 更通用的基于语义的操作； ( 3 ) 搜索能力的分析： ( 4 ) 更有效的体现和变动环境相互作用的适应度函数的导入等。 3 生物进化与遗传算法的研究 从生物进化角度看，模拟r n a 向d n a ( 脱氧核糖核酸) 的进化过程和机制， 从而完善和提高遗传算法的性能是值得注意的研究课题。 4 遗传算法的并行分布处理 注意到建立在全局统计处理基础上的遗传操作所引起的计算开销不可忽视， 设计有效的并行遗传算法及相应的实现系统对遗传算法的理论研究和应用研究都 是十分重要而迫切的任务。 5 人工生命与遗传算法的研究 遗传算法在实现人工生命中的基本地位和能力需要进一步的研究。 1 2 3 遥传算法的发展趋势 今后研究的重点： 1 急需引入新的数学工具建立新体系来分析g a 的实现机理，特别是收敛性的分析 理论、搜索效率和时间复杂性分析的理论； 2 需要新的评价标准确定g a s 的性能指标及建立规则来选取控制参数； 3 g a 不是传统的确定性的工具，它作为一种适应于与多学科结合通用方法，溶入 新知识后应用价值更大，需要引入更高级、有效的操作算子提高g a s 的应用价值； 4 g a s 在大规模的复杂优化问题上取得了令人注目的成绩，但仍需要对g a s 的有效 性和适用性做进一步的研究。 当前一个特别值得重视的趋势是一些面向对象的智能技术，其中主要是模糊 逻辑( f u z z yl o g i c ，f l ) 、神经网络( n e u r a ln e t w o r k ，n n ) 以及g a 等的综合 应用【1 1 。例如，清华大学李衍达院士领导的研究集体开展了这一重要方向的研究【2 1 。 1 9 9 5 年，z a d e h 在i f s a 的第六届世界会议上再次强调了这一方向的重要性【3 1 。 近几年，不断对交叉算子进行改进以提高遗传算法在解决相应问题的效率， 如：许镇琳、汪剑鸣【4 】提出的代间杂交交叉算子，提高了g a 在处理优化问题的能 力；龚道雄、阮晓钢提出了随机多父辈适应度值加权交叉算子 s l ；张春涛、应宏提 8 山东大学硕士学位论文 出的均匀块交叉f 6 】；刘清、廖忠、沈祖诒、王柏林的多点正交交叉【7 】等等。 1 3 本文的研究内容及安排 本课题主要是对传统的遗传算法中的交叉算子进行改进，并针对传统的双亲 双子的交叉操作的方式做了改进，采用了单亲单对单子( 即一个父代个体一对交 叉点生成一个子代个体) 和单亲双对单子( 即一个父代个体两对交叉点生成一个 子代个体) 的方法，并利用博弈论中混合策略的基本思想使得这两种新的交叉算 子发挥各自优势从而求解函数最优化问题。近年来，随着遗传算法的蓬勃发展， 其在寻找最优解方面受到了越来越多的关注。本文以6 个经典函数为主要研究对 象，测试优化混合交叉算子的性能。在收敛速度上，将新算法分别与采用上述两 种纯交叉算子的遗传算法、多点正交交叉遗传算法进行比较。通过对实验结果分 析得出，该算法能够提高遗传算法的收敛性，有效的改善了遗传算法在求解最优 化问题的收敛性能。 本论文提出优化混合策略遗传算法求解函数最优化问题( 最小值) ，使遗传算 法在函数最优化问题上的应用更前进一步。 本文按以下方式编排： 第一章前言 第二章理论概述 第三章基于优化混合策略的遗传算法 第四章实验结果分析 9 山东大学硕士学位论文 第二章理论概述 为了更好的理解和阐释算法，本章将分别介绍遗传算法、博弈论及函数优化 方面的基本知识。 2 1 进化计算的基本理论 2 1 1 进化计算初步 进化计算又称为进化算法( e a s ) ，仿效生物学中进化和遗传的过程【8 】，遵从 “生存竞争，优胜劣汰”的原则，从一组随机生成的初始可行群体出发，借助复 制、交换( 重组) 、突变等遗传操作，逐步逼近所研究问题的最优解。 进化计算实质上是自适应的机器学习方法，它的核心思想是利用进化历史中 获得的信息指导搜索或计算。进化计算与自然进化类似，一般不提供简洁的求解 方法。进化计算的主要优点是简单、通用、鲁棒性强和适用于并行处理。它比盲 目的搜索效率高得多，又比专门的针对特定问题的算法通用性强，是一种与问题 无关的求解模式。 1 进化计算的组成 进化计算是计算智能的关键技术之一，它具有模拟生物进化的强大的优化能 力。通常，进化计算( 又称演化计算) 又分为遗传算法( g e n e t i c a l g o r i t h m s ，g a s ) ， 模仿生物通过染色体的交配及其基因的遗传变异机制来达到优化的目的；遗传程 序设计( g e n e t i cp r o g r a m m i n g ，g p ) 、进化策略( e v o l u t i o ns t r a t e g i e s ，e s ) ，两者 是受到达尔文进化论的启示，模仿自然界“物竞天择”的物种优化机制以达到优 化的目的；进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 4 种典型方法，其中最广泛 被应用的就是遗传算法。它们在进化原则上是一致的，但是在实施进化的手段上 却各有特点，互不相同。e p 和e s 在算法上可谓大同小异，只是前者发源于美国， 着眼于不同种群间的竞争；而后者则发源于德国，着眼于种群内个体问的竞争。 2 进化理论与进化计算的研究 随着进化计算的发展，国内外许多学者也纷纷把它应用到各自的研究领域， 1 0 山东大学硕士学位论文 取得了许多引入注目的成绩，例如g o l d b e r g 利用该算法设计了一个输气管道的控制 系统，模拟了美国从西南向东北输送天然气的输气管道；l a w r e n c ed a v i s 利用同样 的技术设计了通讯网，使其在用最少的线路和最少的线路交换机传输尽可能多的 数据。在聚类分析的领域内利用进化计算来降低传统聚类算法对初始化的要求。 1 9 8 9 年许雷提出采用模拟退火算法对硬k 均值算法的硬分类矩阵w 进行退火 优化计算【9 】，r w k l e i n 等人在同一时期也提出了采用模拟退火进行聚类分析，并 与硬k 均值聚类算法进行了比较o l ，s z s e l i m 等人提出对模糊k 均值算法中的模糊 隶属度矩阵w 进行模拟退火处理的模糊聚类算法f l l l ，李文化等人提出对聚类中心 矩阵p 进行退火处理，i l i i w 矩阵按f k m 算法中的迭代公式求解【1 2 】。 1 9 9 4 年i c s a l - s u l t a n 提出用t a b u 搜索算法求解硬k - 均值聚类问题，它通过对w 矩阵的随机搜索以获得全局最优解【1 3 】。1 9 9 2 年刘健庄、谢维信等人得出了基于遗 传算法的h k m 算法和f k m 算法【1 4 l ，同时b e z d e k 等也提出用遗传算法指导聚类的算 法【1 5 】。 3 进化计算的基本特征 进化计算的基本特征，除了其自组织、自适应性和本质并行性以外，还表现 在以下几个方面。 ( 1 ) 过程性。算法模拟的是一个过程，算法的实施也是一个过程。 ( 2 ) 多解性。 ( 3 ) 不确定性。演化计算的不确定性是伴随其随机性而来的。 ( 4 ) 非定向性。自然选择和生殖过程这种非定向机制是演化计算的关键。 ( 5 ) 内在学习性。学习是演化过程自身所具有的不可与其分割的行为方式。 学习可分为三类：宗亲学习、社团学习和各体学习。 ( 6 ) 统计性。在每一演化代都要进行统计，以确定个体的优劣并推动演化的 进行。 ( 7 ) 稳健性( r o b u s t n e s s ) 。在不同条件和环境下算法的适用性和有效性。 ( 8 ) 整体优化。演化计算同时在解空间的多个区域内进行搜索，并且能以较 大的概率跳出局部最优，以找出整体最优解。 4 进化计算的研究展望 在生物技术与计算机科学高度发展的二十一世纪，进化计算将在以下几个关 山东大学硕士学位论文 - - l _ _ _ _ _ _ _ _ 皇皇量 键问题上获得进展。 ( 1 ) 遗传算法的早熟问题 遗传算法的早熟问题严重影响了遗传算法的应用，目前，还没有一种通用的 解决方法。随着其他技术的发展，早熟问题也必将从遗传算法的遗留问题中销声 匿迹。 ( 2 ) 进化计算在人工智能中的应用 人工智能中存在着大量的复杂优化问题，单凭传统的优化技术是无能为力的。 作为新颖的智能优化技术，进化计算必将在未来的人工智能中起到核心的优化技 术作用。 ( 3 ) 进化计算在人工生命研究中的应用 人工生命是研究用人工的方法模拟自然生命的特有行为，而基于进化计算的 模型是研究人工生命的主要基础理论之一进化计算的进展必然也促进人工牛命 的研究。 ( 4 ) 进化计算与进化硬件 进化计算的发展已经和计算机硬件结合起来，近年来，已经出现了可进化的 硬件( e v o l v a b l eh a r d w a r e ，简称e h w ) 。不过，进化硬件仍处于研究的“婴儿” 时期。所以进化硬件的发展空间仍然很大，需要硬件、软件和进化计算界的学者 共同努力。 现在，进化计算已经成为一门较独立的新的计算技术学科，它主要研究模拟 生物的进化规律来解决实际工程中的复杂优化问题。以遗传算法为核心的进化计 算将二十一世纪的计算智能推向一个个崭新的应用领略。 2 1 2 遗传算法简介 遗传算法是由美国m i 出g 锄大学的j o h n h o l l a n d 教授于2 0 世纪6 0 年代末期创建 的【1 6 1 。在进化论中，自然界中生物的不同归结于决定其遗传特性的染色体的不同， 染色体的差异通过生物体在环境中的结构与行为表现出来，而结构与行为的差异 反过来有影响生物体存活与繁殖的能力。适应环境性好( 适应度高) 的生物能在 激烈的生存竞争中能以较高的概率生存下来，即达尔文的进化论中适者生存和自 然选择的观点。在遗传学中，遗传基因的形式包含在染色体中，每个基因有特殊 1 2 山东大学硕士学位论文 - _ _ _ 皇皇皇置墨| 1 1 _i ij 一| 皇_ 詈置_ 目一 的位置并控制某个特殊的性质，每个基因产生对环境有一定的适应性，基因杂交 和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值 高的基因结构就保存下来。 遗传算法( 简称为g a ) 的基本思想就是基于上述进化论和遗传学的思想，并 引用了随机统计理论而产生的。g a 是强调目的性算法化的进化过程，是一种基于 优胜劣汰、自然选择的进化方法。它通过模拟生物在自然界中遗传变异与生存竞 争等遗传行为，让问题的解在竞争中得以进化，以求得到问题的满意解或最优解。 1 遗传算法计算流程 j o h nh o l l a n d 教授通过模拟生物进化过程设计了最初的遗传算法，我们称之为 基本遗传算法( 标准遗传算法或简单遗传算法) 。基本遗传算法( s g a ) 给出了遗 传算法的基本框架，以后对于遗传算法的改进都是基于此种算法。经典遗传算法 的计算流程如图2 1 所示。具体求解步骤如下【1 7 】： ( 1 ) 参数编码：遗传算法将待优化的参数集进行编码，一般用二进制编码， 将参数集表示成有限长度的字符串。 ( 2 ) 初始种群的生成：随机地产生1 1 个体组成一个群体，该群体代表一些可能 解的集合。 ( 3 ) 适应度函数的设计：遗传算法在运行中基本上不需要外部信息，只需依 据适应度函数来控制种群的更新。设计适应度函数的主要方法是把问题的目标函 数转换成适合的适应度函数。 ( 4 ) 选择复制：按一定概率从群体中选择m 对个体，作为双亲用于繁殖后代， 产生新的个体加入下一代群体。选择是遗传算法的关键，它体现了自然界中适者 生存的思想。 ( 5 ) 交叉：对于选中的用于繁殖的每一对个体，随机地选择同一整数1 1 ，将双 亲的基因码链在此位置相互交换。交叉体现了自然界中信息交换的思想。 ( 6 ) 变异：按一定的概率从群体中选择若干个个体。对于选中的个体，随机 选择某一位进行取反操作。变异模拟了生物进化过程中的偶然基因突变现象。 对产生的新一代群体进行重新评价、选择、杂交和变异。如此循环往复，使 群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某 一界限或最优个体的适应度和平均适应度不再提高，则迭代过程收敛，算法结束。 在g a 中，搜索能力主要是由选择和杂交赋予的，变异算子则保证了算法能搜索到 问题解空间的每一点，从而使算法达到全局最优。 图2 - 1 经典遗传算法的流程图 2 遗传算法的特点 遗传算法是不同于枚举法、启发式算法、搜索算法等传统的搜索和优化方法， 主要有以下特点【1 8 j ： ( 1 ) 自组织、自适应和学习性( 智能性) 。 ( 2 ) 对可行解表示的广泛性。遗传算法处理的对象是针对那些通过参数集进 行编码得到的基因个体。 ( 3 ) 群体搜索特性。搜索种群中的点是并行的，而不是单点的。 ( 4 ) 不需要辅助信息。只需要目标函数和相对应的适应度。 ( 5 )内在启发式随机搜索特性。采用概率变迁规则引导搜索方向。 ( 6 ) 在搜索过程中不容易陷入局部最优。 ( 7 ) 采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解困难的 问题。 1 4 山东大学硕士学位论文 _ _ l 目目_ m e g 一 - - _ = _ _ ( 8 ) 具有固有的并行性和并行计算的能力。 ( 9 ) 具有可扩展性。形式上简单明了，易于同别的技术混合。 3 遗传算法与其它传统的搜索算法的区别 遗传算法与传统的搜索算法之间有很多差别，归纳为： ( 1 ) 遗传算法以编码形式工作而不是对参数本身进行求解。 ( 2 )遗传算法用概率传递规则代替确定性规则。 ( 3 ) 遗传算法只使用目标函数信息不使用推导过程或其他辅助知识。 ( 4 ) 遗传算法的每一步是从解空间中的一个解群向另一个解群搜索而不是 从一个解点向另一个解点搜索。 ( 5 ) 遗传算法具有运算并行性。 ( 6 ) 遗传算法关心每次进化群体中个体的质量，即问题解的质量。 2 1 3 遗传算法的基本理论研究 g a 理论研究的内容主要有分析g a 的编码方法、适应值函数、g a 的三个算子、 g a 参数的选择、全局收敛性和搜索效率的数学基础、欺骗问题、收敛性分析、 并行计算、g a 的局部改进及混合g a 等。 1 编码方法 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转 换到遗传算法所能处理的搜索空间的转换方法就称为编码。编码是由问题空间向 g a 空间的映射，它是应用遗传算法求解问题的第一步，也是设计遗传算法时的一 个关键步骤。 ( 1 ) 编码方法的研究 迄今为止人们已经提出了许多种不同的编码方法，像一维染色体编码( 包括 二进制编码、实数、格雷编码等) 、二维染色体编码、多参数级联编码、d n a 编 码等。总的来说，可分为四大类：二进制编码方法、符号编码方法、浮点数编码 和序值编码f 1 明方法。 h o l l a n d 模式定理建议采用二进制编码，这得到许多学者【2 0 1 的支持。早期g a 研 究口1 1 多考虑了双倍体表达，g o l d b c r g a * ：t i s m i t h 2 2 1 用动态k n a p s a c k 问题进行了比较研 究，实验表明双倍体比单倍体的动态跟踪能力强。由于浮点数编码有精度高、便 1 5 山东大学硕士学位论文 于大空间搜索的优点，浮点数编码越来越受到重视脚，2 4 ，m i c h a l e w i c z l 2 5 】比较了两 种编码法的优缺点。最近q i 和p a k n i 丽【2 6 1 对浮点数编码的遗传算法进行了严密的数 学分析，进行了全局收敛性分析。另外，k o 盈【2 7 l 还发展了用计算机程序来编码， 从而开辟了新的应用领域。动态参数编码的提出是为了克服搜索效率与表示精度 问的矛盾，同时对克服过早收敛现象也有所帮助。多值编码、实值编码、区间值 编码、d e l t a 编码、对称编码以及将以往的合成编码分解成多个相对独立编码的独 立编码策略等多种编码方法也都被证明各有优缺点。为了缓解二进制编码带来的 。组合爆炸一和g a 的早熟收敛问题，提出了十进制编码 2 8 1 张晓绩等【2 9 l 研究结 果表明二进制编码比十进制编码的搜索能力强，但前者不能保持群体稳定性。 v o s e ，b a t t l e 和l i e p i n s 3 0 1 等扩张了h o l l 锄d 的模式概念，揭示了不同编码之间的同构 性。 ( 2 ) 编码评价规则 编码方法决定了基因型和表现型之间的转换方法，编码的好坏在很大程度上 决定了算法的优劣。编码方案取决于具体的问题，因此目前尚没有一定的理论和 评价原则。评价编码策略常采用以下三个规范：完备性( c o m p l e t e n e s ) ；健全性 ( s o u n d n e s s ) ；非冗余性( n o n - r e d u n d a n c y ) 。 上述的三个策略虽然具有普遍意义，但是缺乏具体的指导思想。d ej o n g 3 1 1 提 出较为客观明确的编码评价准则，它包括两条规则： 有意义积木块编码规则：所定编码应当易于生成与所求问题相关的短距和 低阶的积木块； 最小字符集编码规则：所定编码应采