（计算机应用技术专业论文）混合遗传算法在布尔方程求解中的应用.pdf

北京：i = 商大学硕士学位论文 v9 4 1 5 2 4 摘要 遗传算法( g e n e t i ca l g o r i t h i n s ，g a ) 是一种借鉴生物界自然选择和自然遗传 机制的随机优化搜索算法。由于它简单易行，尤其是其不需要专门的领域知识而仅 用适应度函数作为问题的评价来指导搜索过程，能够有效地求解n p 完全问题，从 而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，取得了许多令人 瞩目的成果，引起了广大学者和工程人员的关注。 布尔函数在数字逻辑电路的分析与综合、多值逻辑、数字系统故障检测、纠错 编码、计算机密码学等领域中有着广泛的应用背景。在实际工作中，布尔方程组的 求解，传统算法本质上都是基于穷尽解空间来求解的，是具有n p 难度的问题。利 于较大维数的方程组求解问题，利用现有的计算条件，在工程实现上往往无法实现。 本文将遗传算法应用到求解线性布尔方程组的问题中，给出了一种关于较大规 模布尔方程组的可行解法；并且针对基本遗传算法存在的缺陷，提出了关于背景知 识的多项改进策略，并通过实验，得到了较好的求解效果；对利用混合遗传算法求 解线性布尔方程组的适应性及收敛性问题进行了讨论。 本文主要从以下几个方面对遗传算法在布尔函数中的应用进行了阐述。 一、绪论部分，描述了遗传算法的生物学特征，算法特点，发展和研究现：状， 指出本课题研究的目的和意义。 二、遗传算法的概念、构成要素、方法、步骤以及理论基础。 三、将基本遗传算法应用于求解线性布尔方程组问题中，与传统求解方法相比， 取得了较好的求解成功率。 列、针对遗传算法易早熟、局部搜索能力较差、收敛速度慢等特点，提出了若 干改进策备：将种群概念细分；引入局部搜索策略：引入小生境技术等。通过大量 实验，获得了使求解线性布尔方程组问题有较高成功率及较快收敛速度的混合遗传 混台遗传算法在布尔方程求解中的应用 算法。 五、对遗传算法求解布尔方程组的适用性及邻域解的存在性问题进行了初步的 讨论。提出了利用方程系数向量的重量提取出方程，再通过混合遗传算法求解一般 类型布尔函数的思路。 关键词混合遗传算法布尔函数群体局域搜索小生境 堕塑堡生壁塑主堂垡笙苎 a b s t r a c t g e n e t i ca i g o r i t h m si sak i n d 。fr a n d o ms e a r c h i n gm e t h 。du s i n gl i y e s ， “a t “。8 l8 。l 。t i o n8 n dg e n e t i cm e c h a n i s m i ti ss i m p l ea n d e a s yt oi m p l e m e n t 。8 p 。i 8 l l yi td 。n 。tn e e dt h es p e c i a lf i e i dk n o w l e d g e ，s 。i th a sb e e n u s i n g i “”。r yb r o a df i e l d s n o wt h eg e n e t i ca i g o r i t h m s h a sg o tal 。t o ff r u i t s a n dm o r es c h o l a r s b e g i nt op a ya t t e n t i o nt oi t t h eb o o l e a nf u n c ti o nh a st h e n u m e r a 1 0 9 cc jr c u i ta n a l y s i s w i d e s p r e a da p p i c a t i o nb a c k g r o u n dj n t h e t h em u l t i v a l u e dl o g i c ，n u m b e rs y s t e m d o m a i na n ds oor ) i nf a i t u r ed e t e c t i o n ， e r r o rc o r r e c t o n c o d e ， c r y p t o l o g v e t c b u ti nt h ep r a c t i c a lw o r k ，i t sv e r yd i f f i c u l tt o s 0 1 v et h eb i gj c a l e b o o l e a nf u n c t i o ns y s t e mo fe q u a t i o n sw i t ht h e t r a d i t i o n a lm e t h o d s i nt 九l sp a p e rt h eg e n e t i ca i g o r i t h m sw i1 1 a p p l yt os o l v i n gt h el i n e a r b 0 0 1 e a nf u n c t i o ns y s t e mo fe q u a t i o n s t h ea y t i c l eh a sp r o d u c e d al e a s i b l e s o l u t i o na b o u tt h eb i gs c a l eb o o l e a nf u n c t i o n s y s t e mo fe q u a t i o n s ， a n d p r o p o s e dm a n yi m p r o v e m e n t ss t r a t e g yt ot h es i m p l eg e n e t i ca i g o r i t h m sa b o u t t h 。b a c k g r o u n dk n o w l e d g e ，o b t a i n e dt h eg o o d s o l u t i 。ne f f e c t t h i sa r t l c l em a i n l yh a sc a r r i e do n t h ee l a b o r a t i o nf r o mf o i i o w i n 口 s e v e r a l8 8 p 。t 8t ot h eg e n e t i ca l g o r i t h m s i nt h eb o o l e a nf u n c t i o n a p p l i c a t i o n f i r s t , t h ei n t r 。d u c t i 。nd e s c r i b e st h eb i 。l 。g yc h a r a c t e r i s t i c 。f g e n e t i c 8 l g 。i h ”5 ，t h 。a i g o r i t h mc h a r a c t e r i s t i c ，d e v e l 。p m 。n ta n dr e s e a r c hp r e s e n t s i t u a t i o n , p 。i n t e d 。u tt h eg 。a a n dt h es i g n i f i c a n c e 。ft h i s t 。p i c s e c o n d , g e n e t i ca i g o r i t h m sc 。n c e p t ，j n e g r a n p a r t ，f l e t h 。d ，s t e p a sw e i 混合遗传算法在布尔方稗求解中的府h a sr a t i o n a e t h i r d ，a p p l i e st h es i m p l eg e n e t i ca l g o r i t h m si n t h es o l u t i o no f e q u a t i o n sf o rl i n e a rb o o l e a nf u n c t i o ns y s t e m ，c o m p a r e dw i t ht h et r a d i t l o n a l s o l u t i o nm e t h o d ，h a so b t a i n e dt h eb e t t e rs o lu t i o ne f f e c ta n dt h eh i g h e r s u c c e s sr a t i 0 f o u r t h i nv i e wo ft h ep r e m a t u r ec o n v e r g e n c e ，t h ep a r t i a ls e a r c ha b i l i t y m i s s e s ，t h ec o n v e r g e n c er a t ei ss l o wa n ds oo nt h ec h a r a c t e r i s t i cf o rg e n e t i c a l g o r i t h m s ，p r o p o s e dc e r t a i ni m p r o v e m e n ts t r a t e g i e s ：d i v i d e st h ep o p u l a t i o n i n t r o d u c e st h ep a r t i a ls e a r c hs t r a t e g y ：i n t r o d u c e st h en i c h et e c h n o l o g y u s e st h ea u t o a d a p t e dv a r i a t i o np r o b a b i l i t ya n ds oo n t h r o u g ht h em a s s i v e e x p e r i m e n t s ，o b t a i n e dt h eh y b r i dg e n e t i ca l g o r it h m st oh a v et h eh i g h e r s u c c e s sr a t i oa n dt h em u c hr a p i d l yc o n v e r g e n c es p e e do fs o l v i n gt h eli n e a r b o o l e a nf u n c t i o ns y s t e mo fe q u a t i o n st oc o m p a r ew i t ht h es i m p l eg e n e t i c a l g o r i t h m s f if t h ，c a r r y a s t r l n g e n c yq u e s t e q u a t i o n s p r o p o s c o e f f i c i e n tv e c t o f u n c t i o ne q u a t i o n o nt h ep r e l i m i n a r yd i i o nf o rs o l v i n gt h eb e dt h em e n t a l i t yo fw rw e i g h t ，a n da g a i ns st h r o u g ht h eh y b r i d s c u s s i o no ft h ec o m p a t i b l ea n dt h e o o l e a nf u n c t i o ns y s t e mo f i t h d r a w i n gt h ee q u a t i o n su s i n gt h e o l v i n gt h eg e n e r a lt y p eb o o l e a n g e n e t i ca 1 9 0 r jt h m s k e yw o r d sh y b r i dg e n e t i ca l g o r i t h m s ；，p o p u l a t i o n b o o l e a nf u n o t i o n s ；l o c a ls e a r c h i n g ；n i c h e v 北京：c 商大学硕士学位论文 第一章绪论 1 1 遗传算法概述 自然界中的生物不断繁衍生息，在漫长的进化过程中，生命从低级到高级，从 简单到复杂，从单一适应到多种适应，并沿着物种数目日益增多的方向发展进化。 生物进化的动力和机制在于自然选择。凡是具有适应环境的有利变异的个体，在生 存斗争中将有更多机会生存和繁殖后代，而适应性较差的个体将被淘汰。生物进化 便是“物竞天泽，适者生存”的过程。达尔文( d a r w i n ) 用自然选择( n a t u r a l s e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括三方面核心内 容： ( 1 ) 遗传( h e r e d i t y ) 。所谓“种瓜得瓜，种豆得豆”，生物在繁殖时，通 过细胞分裂，染色体的交叉( c r o s s o v e r ) 重组将遗传物质复制( r e p r o d u c t i o n ) 到子代中，子代继承了父代的遗传基因发育分化，所以总是表现出与父代具有相同 或相似的性状特征。生物有了这个特征，物种才能稳定存在。 ( 2 ) 变异( m u t a t i o n ) 。生物繁殖进行细胞复制时，虽然概率很小，但也有 可能产生某些复制差错，从而使遗传物质d n a 发生某种变异，产生出新的染色体， 这些新的染色体使子代和父代之间以及子代的不同个体之间表现出或多或少的差 异，这种变异现象是随机发生的，变异的选择和积累是生物物种多样性的根源。 ( 3 ) 生存斗争和适者生存。生物的进化( e v o l u t i o n ) 是以集团的形式共同进 行的，这样的一个团体称为种群( p o p u l a t i o n ) ，组成种群的单个生物称为个体 ( i n d i v i d u a l ) ，每个个体对其生存环境都有不同的适应能力，这种适应能力称为 个体的适应度( f i t n e s s ) 。由于弱肉强食的生存斗争不断的进行，其结果是适者 生存，具有高适应度的个体存活下来，获得更多的生存与繁殖机会，相反，低适应 度的个体被淘汰。通过一代代的生存环境的选择作用，物种将逐渐向适应于生存环 混合遗传算法在布尔方程求解中的应川 境的方向进化，从而产生出更优良的物种。 1 8 6 6 年，孟德尔提出了遗传学的两个基本规律分离律和自由组合律，奠定 了现代遗传学的基础。他认为遗传以密码方式存在细胞中，并以基因形式包含在染 色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体 对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存 优去劣的自然淘汰，适应性高的基因结构得以保存下来。 尽管人类还不能完全揭示生物进化的机制，但遗传与进化的一般特征已广为人 们所接受。自然界生物体通过自身的演化就能使问题得到完美的解决。这种才能让 最好的计算机程序也相形见拙。计算机科学家为了某个算法可能要耗费数月甚至几 年的努力，而生物体通过进化和自然选择这种非定向机制就完美地达到这个目的。 受生物进化和遗传的启发，学者们模仿生命进化的过程，提出了一种宏观意义 上的仿生算法遗传算法。它通过模拟达尔文“适者生存，优胜劣汰”的原理激 励好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻 找更好的结构。 遗传算法是从一组随机产生的初始种群开始搜索过程，种群中的每个染色体是 问题的一个解，这些染色体通过交叉或变异后产生子代，在新生代中，适应度好的 个体将获得更多生存与繁殖的机会，适应度差的个体很可能被淘汰。这样，经过若 干代后，算法收敛于适应度最高的那个染色体，它很可能就是问题的最优解或次优 解。 与其它一些智能优化算法相比，遗传算法主要有以下几个特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。它直接处理的对象是参数编 码集而不是问题参数本身。这种对决策变量的编码处理方式具有良好的可操作性和 简单性。 ( 2 ) 遗传算法直接以适应度函数值作为搜索信息。搜索过程不受目标函数连 续性和可微性的约束。通过对适应度高的染色体基因的重组，可以有效地处理复杂 函数的求解问题，适用于许多大规模、高度非线性的不连续多峰函数的优化及无解 北京：i 二商大学硕士学位论文 析表达式的目标函数的优化，具有很强的通用性。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。在对每一代种群规模为n 的 个体进行操作时，实际上处理了大约0 ( n ：1 ) 个模式。其操作对象是一组解，而非单 个解：搜索轨道有多条，而非单条。在每一代的进化过程中，实际上包含了群体中 多个个体的信息，这使遗传算法具有很高的并行性，因而有显著的搜索效率。 ( 4 ) 遗传算法在全局解空间中使用概率搜索技术。其择优机制是一种“软” 选择，其选择、交叉、变异等运算都是以一种概率方式进行的，从而增加了其搜索 过程的灵活性，使它具有良好的全局优化性和稳健性。 ( 5 ) 遗传算法对函数的性态无要求，针对某一问题的遗传算法经简单修改即 可适应于其它问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够 较好地解决复杂问题，因而具有较好的普适性和易扩充性口1 。 1 2 遗传算法的发展与研究现状 早在2 0 世纪4 0 年代，就有学者开始研究如何利用计算机进行生物模拟的技术， 他们从生物学的角度进行了生物进化过程模拟、遗传过程模拟等研究工作。但遗传 算法真正意义上的开创性工作，始于6 0 年代h o l l a n d 教授与他的学生们的研究。 h o l l a n d 认识到生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生 物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系， 提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进 行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。 7 0 年代初，他提出了遗传算法的基本定理模式定理( s c h e m at h e o r e m ) ，从而 奠定了遗传算法的理论基础。模式定理揭示出了种群中的优良个体( 较好的模式) 的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻求 最优可行解的优化过程。1 9 7 5 年h o l l a n d 出版了其开创性著作“a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e s m ”( 自然系统和人工系统的自适应性) 。“。 1 9 6 7 年，h o l l a n d 的学生b a g l e y 在他的博士论文中首次提出了“遗传算法” 混合遗传算法在布尔方程求解中的应用 ( g e n e t i ca l g o r i t h m s ) 这一术语，并发表了遗传算法应用方面的第一篇论文n 1 。 他讨论了遗传算法在自动博弈中的应用，并发展了复制、交叉、变异、显性、倒位 等遗传算子，在个体编码上使用了双位体的编码方法。这些都与目前遗传算法中所 使用的算子和方法相类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使 用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算 法的概念。遗传算法的通用编码技术和简单有效的遗传操作，为其广泛、成功的应 用奠定了基础。 1 9 7 5 年，h o l l a n d 的另一位学生d ej o n g 完成了其博士论文a na n a l y s i s o f t h e b e h a v i or o fac l a s so fg e n e t i ca d a p t i v es y s t e m s 瞄3 j 他结合h o l l a n d 的 模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架。他 设计了一系列遗传算法的执行策略和性能评价指标，对遗传算法性能做了大量的分 析。他推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的d e j o n g 五函数测试平台，定义了评价遗传算法性能的在线( o n - 1 i n e ) 指标和离线 ( o f f l i n e ) 指标。他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的 基础。 在h o l l a n d 和他的团队的工作之后，遗传算法经历了一个相对平稳的发展时期。 随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习 和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。2 0 世纪8 0 年 代中期以来，是遗传算法和进化计算的蓬勃发展期，并且延续至今。g o l d b e r g 在遗 传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士论文中第一次把遗传算法 用于实际的工程系统煤气管道的优化，从此，遗传算法的理论研究更为深入和 丰富，应用研究也更为广泛和完善。1 9 8 9 年，g 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 d m a c h i n el e a r n n g ) 1 。该书总结了遗传算法的主要研究成果，全面而完整地论述了 遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为 众多研究和发展遗传算法的研究者所瞩目。 自1 9 8 5 年起，遗传算法及其应用国际会议每二年召开一次，与之平行进行的 4 北京工商大学硕士学位论文 国际会议也很多，有关人工智能的会议和刊物上大多有遗传算法、进化计算的专题。 遗传算法的基础理论研究和工程应用研究都十分活跃。 9 0 年代以后，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的 科学新范式得到学术界普遍认同。由于遗传算法能有效地求解n p 类型的组合优化 问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视，一 些学者也认识到求解复杂问题最优解是不现实的，故而寻求满意解，而遗传算法是 最佳工具之一。生物进化的历史比任何数学证明都强有力，遗传算法在吸收遗传学、 进化论及分子生物学最新成果和在实验得到证明和证伪的同时本身也在进化。人们 也开始重视遗传算法的一些基本问题，d ej o n g 称之为“重访基本的假设”，这方 面的研究内容主要有：表示和形态发生学，拉马克算子等的引入，非随机配对和物 种形成，分散的高度并行的模型，自适应系统，共同进化系统等。同时由于遗传算 法在应用研究方面的长处主要得益于其求解的有效性、现有仿真环境下易于实现、 可扩充性和易于与其他方法相结合等。 目前，遗传算法已在机器学习、过程控制、经济预测、工程优化等多领域取得 成功的应用。遗传算法引起包括数学、物理、化学、生物学、计算机科学等领域的 科学家的极大兴趣。遗传算法的研究领域和内容也越来越广泛，可以预见，随着理 论的深入研究和应用领域的不断拓展，遗传算法必将取得更大的发展。 1 3 课题意义和目的 人们对遗传算法兴趣的日益增长有两个背景：其一是工程领域，特别是人工智 能与控制领域，不断涌现出超大规模的非线性系统，在这些系统的研究中存在着大 量的经典优化方法所不能有效求解的优化问题。其二，遗传算法本身就是- , e e 模拟 自然演化这一学习过程的求解问题方法，它能以独立的或与其它方法相结合的形式 用于智能机器学习系统的设计中。 一般来说，任何难解的任务都可被看成是要解决的一个问题，反过来，它也可 以被看成是对潜在解空间的一种搜索。因为我们最终的目的是要获得最优解，所以 混合遗传算法在布尔方程求解中的应川 可以把这种任务看成是一个优化过程。对小空间，经典的穷举法就足够用了；而对 大空间，则需使用特殊的人工智能技术盯3 。 在工程实现中，我们遇到了大规模布尔方程组求解的课题。利用传统的本质上 基于穷尽思想的求解方法，问题往往难以在可接受的时间范围内实现，因而迫切地 需要寻求新的优化求解方法。而遗传算法作为一种非数值计算方法，特别是其对问 题求解空间的可行解采用二进制编码，恰好与布尔函数二值性一致，并且布尔方程 组的确定取值也满足了遗传算法对目标函数适应度的要求。于是，我们用遗传算法 及对其改进后的混合遗传算法对布尔函数问题的求解作了新的尝试。 在用基本遗传算法对背景问题进行求解时，我们高兴地发现遗传算法确实可以 作为一种求解方案对布尔方程组问题在一定条件下取得满意的结果，具有一定的求 解成功率。而对于方程组求解问题，在可接受的时间范围内，只要有成功率，求解 就可以认为完全实现了。 另一方面，和其他的优化算法一样，遗传算法自身存在着一定的局限性。主要 表现在以下几个方面： ( 1 ) 全局搜索能力相对较强而局部寻优能力较差。 ( 2 ) 对搜索空间变化的适应能力较差。 ( 3 ) 因为种群中的多样性过早地减少，易出现早熟现象。 ( 4 ) 算法在交叉、变异的进化过程中随机性较强，到目前为止有关遗传算子 控制参数值的选择还没有理论上的指导，往往靠实验或经验来确定。 作者在应用遗传算法求解时，也遇到了一些问题，如算子参数很难确定，容易 陷入局部最优，收敛速度不尽如人意等问题。因而迫切地需要对基本遗传算法作有 。 针对性的改进。 经过大量研究和试算实验证明，在一定条件下，遗传算法，特别是在对基本遗 传算法作了一定的改进，如将群体概念细分，引入局部搜索策略，引入小生境技术 等策略后形成的混合遗传算法，对布尔方程组问题的求解可以取得较好的求解效 6 北京工商大学硕士学位论文 果。 遗传算法的引入，为二元域布尔函数问题提供了新的求解思路，开拓了更为有 效的一类求解手段。 另外，既然遗传算法可以作为布尔函数的一种求解算法，那么它究竟适用于什 么样的布尔方程组求解，对于一般类型问题，是否具有通用性，需要什么条件，其 求解成功率如何，收敛速度怎样，都将是我们密切关心的问题。 1 4 论文的主要内容 本文针对背景数学模型实际求解需求，考虑到经典遗传算法的不足与缺陷，对 大量的相关资料进行研究，结合其他智能优化算法的思想，对遗传算法进行了改进。 首先，将传统遗传算法中的种群概念细分，提出新物种、竞争群体和适应性群 体等不同的群体概念，并将遗传操作算子的功能分开。这样，既保证了优选的原则， 又保证了种群的多样性，在一定程度上减少早熟的现象。 其次，在每一代的进化操作中，对父代适应度较高的那部分个体，在其一定的 邻域范围内，进行局部的全范围搜索，并计算邻域内每一个体的适应度函数，参与 群体的择优进入下一代。父代竞争力较强的个体，经过邻域搜索策略，能在其一定 的邻域范围内找到适应度高的个体同时进入子代。这样，可以大大提高算法的局部 寻优能力。特别是对于连续性较好的模型函数，能极大地缩短算法收敛的代数。 另外，在实验中，发现在进化的后期，种群的个体间表现出极大的相似性( 大 同小异) ，即此时种群的个体全部集中在某个局部最优解附近，使得它们的后代造 成了近亲繁殖。故引入小生境技术，将每代个体划分为若干类，每个类中选出若 干适应度较大的个体作为一个类的优秀代表组成一个种群。基于这种小生境技术的 遗传算法，可以更好地保持解的多样性，同时具有很高的全局寻优能力和更高的收 敛速度。 经过大量实际运算，采用经多种改进技术后的遗传算法，与传统的二元域求解 混合遗传算法在布尔方程求解中的应刚 算法及标准遗传算法相比较，无论从运算成功率与速度上都验证了算法的有效性。 同时通过大量的计算实验，本文还初步讨论了遗传算法求解布尔方程组的适用性和 收敛性问题，提出了对于一般类型方程组根据系数向量重量选取方程再用遗传算法 求解的方案。 、本文的内容安排如下： 第一章简要介绍了遗传算法的生物学基础，基本概念和特点，并概述了遗传算 法的发展现状，阐述了本文课题背景、研究的目的和意义。 第二章介绍了遗传算法的基本原理。它包括方法步骤、计算机理和各种算子， 其中模式定理和基因块假说是遗传算法的理论基础。 第三章将遗传算法引入布尔方程组的求解问题中，并利用基本遗传算法给出一 种可行的求解方法，给出实验结果。 第四章详细叙述了针对背景问题对遗传算法提出的若干改进策略：将种群概念 细分，采用基于汉明距离的局域搜索技术，采用小生境技术等，并给出具体的求解 结果，验证了混合遗传算法求解布尔方程组的切实可行性。 第五章对混合遗传算法在布尔方程组求解中的适用性和邻域解的存在性进行 了讨论，提出了根据系数向量重量选取方程求解的思路。 第二章遗传算法的基本原理与方法 在对各领域的不同问题进行求解研究时，很多学者设计了不同的编码方法来表 示问题的可行解，开发出许多种不同的遗传算子来模仿不同环境下的生物遗传特 性。这些遗传算法有着共同的特点，即通过对生物遗传和进化过程中选择、交叉、 变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点， g o l d b r e g 总结出了一种统一的最基本的遗传算法基本遗传算法( s i m p l e g e n e t i ca l g o r i t h m s ，简称s g a ) 。基本遗传算法只使用选择算子、交叉算子和变 异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗 北京：l 二商大学硕士学位论文 传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一 定的应用价值。 2 1 遗传算法的基本思想 如图2 1 所示，遗传算法把问题的解表示成“染色体”( c h r o m o s o m e ) ，在算 问题域( 表现型) 图2 1 遗传算法的过程 混合遗传算法在布尔方程求解中的应用 法中也就是按一定规则编码( c o d i n g ) 的串。在执行算法之前，先随机给出一群“染 色体”，也就是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生 存的原则，从中选择出较适应环境的“染色体”，并借助于自然遗传学的遗传算子 ( g e n e t i co p e r a t o r s ) 进行选择、交叉、变异过程，产生出更适应环境的新一代 “染色体”群。这个过程将导致种群像自然进化一样，使后生代种群比其父代更加 适应于环境。这样，经过一代代( g e n e r a t i o n ) 的进化，最适应环境的染色体被保 留下来，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为问题的近似最优 解。 2 2 遗传算法的构成要素 遗传算法是通过对群体生物遗传和进化过程中的选择、交叉、变异机制的模仿 来完成对问题最优解的自适应搜索过程的优化算法。根据生物的进化过程和其基本 要素来构成遗传算法的基本要素n 。 2 2 1 染色体的编码方法 遗传算法需要一个对参数空间编码的符号串表示。 染色体的编码是根据问题的本身特性来进行的，不同问题可有不同的编码方 法。它是遗传算法的第一要素，往往由于编码的不同，会带来问题最优解的搜索过 程与结果不同。不同的编码也会导致遗传算法采用不同的遗传算子，从而也构成不 同的遗传算法。 2 2 2 个体适应度评价 遗传算法需要个评价符号串的适应度函数。 遗传算法在优化搜索中仅用适应度函数来作为唯一的寻优依据。根据不同种类 的问题，预先确定好由目标函数值到个体适应度之间的转换规则。完成这种转换就 l o 北京：i = = 商大学硕士学位论文 是对个体适应度的具体描述。 2 2 3 遗传算子 遗传算法需要一组产生新的符号串的遗传操作。 遗传算子是遗传算法的核心，基本遗传算法使用下述三种遗传算子：选择算子， 交叉算子，变异算子。 数： 2 2 4 运行参数 遗传算法需要一组控制遗传操作的概率参数。 根据遗传算法不同，其运行参数也会随之略有不同。基本遗传算法有4 运行参 n ： 种群大小，即种群中所含个体的总数量 m d ： 遗传算法终止进化的代数 见：交叉概率 见，：变异概率 遗传算法的四个参数对遗传算法的求解结果和求解效率都有一定的影响，但目 前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理取值大小或取值范围。 2 3 遗传算法的描述 2 3 1 基本概念与定义 定义2 1 ( 个体和个体空间) 经编码后的染色体z ，称为个体，例如，二进 制编码，长度为，的个体即为长度为，的0 和l 字符串；，称作个体的链长，一个体 混合遗传算法在布尔方程求解中的应用 的全体记作s = 0 ，1 ) 7 ，称作个体空间。 例2 1 在 0 ，13 1 的整数上求f ( y ) = y 2 的最大值。 用整数的二进制进行编码，用5 维二进制即可表示 0 ，3 1 之间的任一整数， 如：染色体x = ( 1 0 l1 1 ) 表示整数2 3 ，链长，= 5 ，个体空间s = 0 ，l 5 。 定义2 2 ( 种群和种群空间) 所谓一种群是个个体组成的集合，简称种 群。称作种群规模，称 s = x = ( _ ，x 2 ，x ) ，薯s ( f ) ) 为一种群空间。一 例2 2 ( 续上例) 一个个体表示一个整数，则 五= ( 0 11 0 1 ) x 2 = ( 11 0 0 0 ) x 3 = ( 0 1 0 0 0 ) 心= ( 1 0 0 11 ) 表示4 个整数，于是x = ( 葺，叠，x 3 ，_ ) 为规模n = 4 的种群。 定义2 3 ( 目标函数)对于给定非空集合s 作为个体空间，目标函数是个体空 间s 到实数空间r 的映射，即目标函数g 为 g ：sj r 。 例2 ：3 ( 续上例) 上述问题的目标函数为m a x f ( x ) ，x s = 0 ，1 ) 5 ) 定义2 4 ( 适应度函数) 对于一个体产生的效益称为适应度。适应度函数是个 体空间到正实数空间的映射，即适应度函数厂为 。 f ：s 寸r + 。 1 ) 对于最小化问题建立如下适应度函数厂( x ) 和目标函数g ( x ) 的映射关系： 北京二c 商大学硕士学位论文 f c ，。a x g ( x ) ( x ) = 【o 若g ( x ) c m i n 0 否则 其中c 而。可以是一个输入值或是理论上的最小值。或是到当前所有代或最近k 代中 例2 4 ( 续上例) 上述问题的适应度函数即为f ( y ) = y 2 z ：s 一s 。 p r ( x ) ：_ ) ：掣， f 。( 坼) 其中厂( 葺) 表示种群x 中的个体x i 的适应度，0 a s 。 其作用方式以概率成交换一对母体中两个个体的相应分量，p c 称作交叉概率。 交叉算子主要包括单点( 随机) 交叉算子、双点( 随机) 交叉算子和均匀随机 交叉算子。 以下用二进制编码说明不同的交叉算子： ( 1 ) 单点交叉算子：等概率的随机确定一个基因位置作为交叉点，再把一对 母体两个个体从交叉点分成前后两个部分，交换两个个体的后半部分得到两个新的 个体，取第一个个体为交叉结果。 ? 例2 6 选择( 葺，x ：) 为母体，随机设定交叉点4 ，通过交叉得到两个新个体： ( 0 11o i1 )( 0 11 0 0 ) ( 11 0 0 1 0 )( 11 0 0 1 ) 北京工商大学硕士学位论文 交叉结果为( 0 1 1 0 0 ) 。 ( 2 ) 单点随机交叉算子：等概率的随机确定一个基因位置作为交叉点，再把 一个母体的两个个体从交叉点分为前后两个部分，以概率p 。交换两个个体的后半部 分，得到两个个体，取第一个个体为交叉结果，称成为交叉概率。 例2 7 ( 续上例) 交叉点仍为4 ，若见= 0 5 ，则各有0 5 的概率使结果为从交 叉点4 处交叉后得( 0 1 l o o ) ，或保留一( 未交叉) 即( 0 1 1 0 1 ) 。 ( 3 ) 均匀随机交叉算子：独立地以概率p 。把母体的第一个个体t j 勺i e t 应分量换 为第二母体的相应分量，从而得到交叉结果。 例2 8 ( 续上例) 若p 。= 0 2 ，则表示第一个母体( o l t 0 1 ) 将有1 个分量随机地变 为第二个母体的相应分量，此时交叉结果可能出现以下情形： ( 1 1 1 0 1 ) ( 0 1 1 0 1 ) ( 0 1 0 0 1 ) ( 0 1 1 0 1 ) ( 0 1 1 0 0 ) 。 定义2 9 ( 变异算子)变异算子是个体空间到个体空间的随机映射瓦，：s 寸s ， 其作用方式为独立地以概率p 。改变个体分量取值。p 。称作变异概率。 例2 9 ：以个体4 为例进行变异，变异概率p 。= 0 2 ，即1 个分量变异，若变 异位3 ， = ( 1 0 0 1 1 ) 一( 1 0 1 1 1 ) 。 2 3 2 遗传算法的基本步骤 在确定问题的编码、目标函数、适应度函数以及控制参数及各种算子的产生规 则后，即可执行遗传算法。标准遗传算法的主要步骤如下( 如图2 2 ) ： ( 1 ) 随机产生一组初始个体构成初始种群，并计算出其各自的适应度函数。 混合遗传算法在布尔方程求解中的应用 ( 2 ) 判断算法的收敛准则是否得到满足。若满足则输出最佳个体，算法结束； 否则执行( 3 ) 。 ( 3 ) 依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低 的可能被淘汰。 ( 4 ) 按交叉概率段执行交叉操作。 ( 5 ) 按变异概率成，执行变异操作。 ( 6 ) 由交叉和变异产生新一代种群，返回步骤( 2 ) 。 图2 2 遗传算法的： 作流秽 6 北京工商大学硕士学位论文 设x ( t ) 为第t 代的种群，遗传算法的伪语言描述为： 遗传算法过程 b e g i n t 一0 ： 初始化x ( t ) 计算x ( t ) 的适应度 w h il e 不满足停止准则d o 对x ( t ) 执行交叉变异获得x ( t + 1 ) 计算x ( t + 1 ) 的适应度 从x ( t ) 和x ( ，+ 1 ) 中选择构成新的x ( t + 1 ) t t 十1 算法中的停止准则1 ，一般依据问题的不同有不同的确定方式。例如，可以采 用以下的准则之一作为判断条件： ( 1 ) 种群中个体的最大适应度超过预先设定值。 ( 2 ) 种群中个体的平均适应度超过预先设定值。 ( 3 ) 遗传代数超过预先设定值。 j ure j u ne 混合遗传算法在布尔方程求解中的应用 2 4 1 模式定理 2 4 遗传算法的理论基础 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串描述了染色体之间的某 些位置上存在相似性。不失一般性，以二进制编码为例，个体由由二元字符集 0 ， 1 ) 中的元素排列所组成的一个编码串。现在我们增加一个符号“术”，称其为通配 符，它既可被当作“0 ”，又可被当作“l ”。这样，二元字符集 0 ，1 ) 就扩展为三 值字符集 o ，1 ，术) ，由此可以产生诸如o l o l ，0 i * 0 ，0 0 1 * 0 等字符串。 定义2 1 0 ( 模式)基于三值字符集 0 ，1 ，术) 所产生的能描述具有某些结构 相似性的字符串称作模式。 例如，模式“* 0 1 il o ”描述了在第1 、4 位上不确定，在2 、3 、5 、6 、7 位上 具有形式“0 1 1 1 0 的所有字符串，即： q 0 1 , 0 , 1 1 0 ，羹0 1 薹1 1 0 ，覆0 1 囊1 1 0 ，薹0 1 薹1 1 0 ) 。 模式简洁地描述了在某些位置上具有结构相似的字符串集合。然而，模式概念 的引入并不是仅仅为了描述上的方便。从表面上看，遗传过程中父代n 个互不相同 的个体经过选择、交叉、变异等算子的作用产生子代n 个互不相同的个体，两代之 间究竟保留了什么性质，破坏了什么性质，我们无从得知，因为我们看到的串是相 互独立的，互不联系的。而引入模式的概念后，我们看到一个串实际上隐含了多个 模式( 长度为的串隐含着37 个模式) 。，一个模式可以隐含在多个串中，不同的串 之间通过模式而相互联系。遗传算法中串的运算实际上就是模式的运算。因此，通 过分析模式在遗传操作下的变化，从而把握遗传算法的实质正是模式定理所要揭示 的内容。 定义2 11 ( 模式阶) 模式h 中确定位置的个数称作该模式的模式阶。记为0 ( h )。 例如，模式“0 1 1 术0 料o ”的模式阶为5 ，而模式“木木木木冰1 料”的模式阶为1 。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 北京：i ：= 商大学硕士学位论文 定义2 1 2 ( 模式的定义距)模式h 第一个确定位置和最后一个确定位置之间 的距离称作该模式的定义距，记为6 ( h ) 。 例如，模式“0 1 l 术o 料0 ”的定义距为7 ，而模式“：i c ：i c 料木1 木冰”的定义距为0 。 假定一个特定的模式h 在( ，) 中有m 个代表串，记为聊= m ( h ，f ) ，则这个模 式何在下一代中期望出现的次数可近似表示为： m ( 脚+ 1 ) 圳h 小竽 1 他。等_ d ( 砂 其中f ( h ) 为模式h 的平均适应值，夕为种群x ( ，) 的平均适应值。 定理2 1 ( 模式定理) 在遗传算子选择、交叉和变异的作用下，具有低阶、短 定义距及平均适应值高于种群平均适应度的模式在子代中将以指数级增长n h l 0 1 。 2 4 2 ( 积木块) 基因块假说 由上一节的模式定理可知，具有低阶、短定义距以及平均适应值高于群体平均 适应值的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要，我们给 它一个特别的名字积木块( b u i i d i n gb l o c k ) 定义2 1 3 ( 积木块) 具