（控制理论与控制工程专业论文）遗传规划的基因内区改进及其在单机调度中的应用.pdf

浙江工业大学硕士学住论文 a b s t r a c t g e n e t i cp r o g r a m m 【n gi n t r o n si m p r o v e m e n t a n di t sa p p l i c a t i o nf o r0 n e m a c h d 匝 s c h e d u l i n gp r o b l e m s a b s t r a c t g e n e t i cp r o 目锄 1 1 m i n g ( g p ) i san e wt e c h n o i o g yf b r o p t i m i 撕o n ， w h i c hs i m u l a t ei n h e r i ta n de v o l u t i o ni 1 1t 1 1 en a t u r ea n d g e to 州m a | s 0 1 l n i o n s t h r o u 曲r e p r o d l l c t i o n ，c r o s s o v e ra n d m u t a t i o n o p e r a 吐o n 8 i nm i sp a p e r ，f i r s t l y ，也eb a s i ca l g o r 弛啦sa r l d 也e o 可a r ed e s c r i b e d ， t t l e nt h er e s e a r c hs t a t ea n da d v 甜i c e s 洫h o m ea r l da b r o a da r es y s t e m a t i c s l m 瑚a r i z e d s o m er l e w 仃e n d so f d e v e l o p m e m o f g e n i e t i cp r o 乎锄盥m g a r e i n d i c 酏e d t h e n ， i f l 缸。o na l n d c o n v e r | 蚕e n c e o fg e l 硎c p r o g 煳m i n ga o e s t u d i e db ym e a n so fs y 血b o l i cr e g r e s s i o na i mf o r i n _ u l ad i s c o v e r yi ng e n e t i c p r o g r a r n m 洒g f a l s ec o n v e 唱e n c ei sa n a l y z e d ，a l l d f o ri t sr 黜o na n dt h e w a y t o m i n i m i z i i l g i t se 珏b c t s a p r o p o s e d 醐n s a 饪b c t i o n so n c o n v e 唱e n c e o f g e n e 行cp r o 伊鲫如1 i i l ga r es t u d i e d b yt e 啦ag r e a t d e a lo f e x 锄p l e s ，t 王l e a f f b c t i o n so fr e p r o d u c t i o na n dc r o s v e ro ni n 口o na r e d i s c u s s e d t h e n ，a ni m p m v e dc r o s 8 0 v e rc a u e ds 妯g l e 巾a 删tc r o s s o v e ri s r e c o r 啷e n d e d ，a n d 柳oo fi 拓e m p l o y e d m e 觚sa 糟r e c o 彻嘲d e d p r o d u c t i o ns c h e d u l i n gp r o b l 嘲sh a v eb e c o m eam a j o ra p p l i c a t i o n f i e l df o re v o l u t i o n a 秽c o m p u t a t i o nm e m o d s i l l 也i sp 8 p e rn l ep o t e n t i a l u s a g eo fg e n e t i cp r o 擎a m m i n gf o r t l l e8 0 l u t i o no fm eo n e - m a c h i n et o t a l t a r d i n e s sp r o b l e mi sg t l l d i e d a tp r e s e n tn l e r ea r e 铆or e s e 甜c hm e m o d s ， f i r s t l y ，ac o m b i n a t i o nd i s p a t c h i n gr u l e i s 砸l i z e d 鹳a i li n d i r e c tw a yo f r e p r e s e n t i l l g ap e m l u 僦o nt h r o u 曲a 删i cp 她彰啪m i n g 奶吼e 、v o r k ； s e c o n d l y ，a 订a d i t i o n a lg e n e t i cp r o 鲈艇皿i n g 觑髓e w o r ka e m p l o y e d a sa b a s i sf o re v o l v m gaf b n i l u l ao fad i s p a t c h i i l gm l e f o rm eo i 璩_ n 埘h i n et o t a l t a r d i n e s s p r o b l e m a l t 1 0 u 曲g e n 鲥cp r o 黟觚n i n g f b r p r o d u c t i o n s c h e d u l i n gp r o b l e m s i sv e r ye l e m e m a r ya n dn e e dt 0b e 如曲e r 咖d i e d ，b m 也er e s e a r c hh a v eb e e ne x t e n s i v e l ye n l a r g e dm ef i e l do fa p p i i c a t i o no f 塑兰兰兰垄芏塑主兰竺丝圭 些! 翌竺堕 g e n e t i cp r o 铲a h n i n g k e y w o r d s ：g e n e t i cp r o g r 锄m i n g ，i 船o n ，e v o l u t i o n a r yc o m p u t a 廿o n ， o n e m a c h i n es c h e d u l i n g p r o b i e m ，p r o d u c t i o ns c h e d u l i n g 浙江工业大擘硕士学位论文 第一章鳍论 第一章绪论 1 1 引言 二十世纪后半叶的科学进入了相互交叉、相互融合、相互影响的时代，这随 着计算机科学的发展而得到了充分的证明。计算机的出现以及计算机科学的迅猛 发展，己经从根本上改变了人们的生活、学习和工作方式。并且随着人们对世界 认识的不断加深，人们希望计算机能够解决越来越困难的闯题，这就要求计算机 必须具有惊人的计算速度和一定的智能，而提高机器的速度由于会受到物理极限 的制约，因此可行的办法便是并行化。虽然目前的并行机较为普遍，但是缺乏有 效的并行算法，还是难以取得满意的效率。 近年来，随着人工智能应用领域的不断开拓，传统的基于符号处理机制的人 工智能的方法在知识表示，处理模式信息及解决组合爆炸等方面所碰到的问题己 越来越突出，这些困难甚至使某些学者对人工智能的可能性提出疑问。 大自然是我们解决各种问题时获得灵感的源泉，仿生学的成功为此提供了证 明。自然界所提供的答案是经过长期的进化过程而获得的，这给我们这样一个启 示：我们勿须非常明确地描述问题的全部特征，只需要根据自然法则来产生新的 更好解。进化计算方法就是基于上述思想发展起来的一类随机搜索技术【l ，2 】。它们 模拟了群体的进化过程。其中每个个体表示给定问题搜索空间中的一点，进化算 法从任初始的群体出发，通过随机选择、重组和变异过程，使群体进化到搜索 空间中越来越理想的区域。选择过程使群体中适应性强的个体比适应性弱的个体 有更多的复制机会，重组算子将父辈信息结合在一起传给予代个体。变异使群体 中产生新的变种。由于采用种群的方式组织搜索，这使得它可以同时搜索解空间 的多个区域。而且用种群组织搜索的方式使得进化算法特别适合予大规模并行工 作方式。在赋予进化计算自组织、自适应、自学习等特征韵同时，优胜劣汰的自 然选择和简单的遗传操作使进化计算具有不受其搜索空间限制条件( 如可微、连 续、单峰) 的约束及不需要其它辅助信息( 如导数) 的特点。这些特点使得进化 算法不仅能获得较高的效率而且具有简单、易于操作和通用的特性，这正是进化 计算越来越受到人们青睐的主要原因之一。 进化计算兴起于二十世纪五十年代末，但是在六、七十年代并来受到普遍的 重视。其主要原因一是因为当时这些方法还不够成熟；二是由于这些方法需要较 大的计算量，而当时的计算机还不够普及而且速度也跟不上要求，限制了它们的 应用：三是当时基于符号处理的人工智能方法正处于其顶峰状态，使得人们难以 认识到其它方法的有效性和适应性。到了八十年代，人们越来越清楚地认识到传 统人工智能方法的局限性，并且由于计算机速度的提高以及并行计算机的普及， 浙江工业大擘硕士学位论文 第一章鳍论 第一章绪论 1 1 引言 二十世纪后半叶的科学进入了相互交叉、相互融合、相互影响的时代，这随 着计算机科学的发展而得到了充分的证明。计算机的出现以及计算机科学的迅猛 发展，己经从根本上改变了人们的生活、学习和工作方式。并且随着人们对世界 认识的不断加深，人们希望计算机能够解决越来越困难的闯题，这就要求计算机 必须具有惊人的计算速度和一定的智能，而提高机器的速度由于会受到物理极限 的制约，因此可行的办法便是并行化。虽然目前的并行机较为普遍，但是缺乏有 效的并行算法，还是难以取得满意的效率。 近年来，随着人工智能应用领域的不断开拓，传统的基于符号处理机制的人 工智能的方法在知识表示，处理模式信息及解决组合爆炸等方面所碰到的问题己 越来越突出，这些困难甚至使某些学者对人工智能的可能性提出疑问。 大自然是我们解决各种问题时获得灵感的源泉，仿生学的成功为此提供了证 明。自然界所提供的答案是经过长期的进化过程而获得的，这给我们这样一个启 示：我们勿须非常明确地描述问题的全部特征，只需要根据自然法则来产生新的 更好解。进化计算方法就是基于上述思想发展起来的一类随机搜索技术【l ，2 】。它们 模拟了群体的进化过程。其中每个个体表示给定问题搜索空间中的一点，进化算 法从任初始的群体出发，通过随机选择、重组和变异过程，使群体进化到搜索 空间中越来越理想的区域。选择过程使群体中适应性强的个体比适应性弱的个体 有更多的复制机会，重组算子将父辈信息结合在一起传给予代个体。变异使群体 中产生新的变种。由于采用种群的方式组织搜索，这使得它可以同时搜索解空间 的多个区域。而且用种群组织搜索的方式使得进化算法特别适合予大规模并行工 作方式。在赋予进化计算自组织、自适应、自学习等特征韵同时，优胜劣汰的自 然选择和简单的遗传操作使进化计算具有不受其搜索空间限制条件( 如可微、连 续、单峰) 的约束及不需要其它辅助信息( 如导数) 的特点。这些特点使得进化 算法不仅能获得较高的效率而且具有简单、易于操作和通用的特性，这正是进化 计算越来越受到人们青睐的主要原因之一。 进化计算兴起于二十世纪五十年代末，但是在六、七十年代并来受到普遍的 重视。其主要原因一是因为当时这些方法还不够成熟；二是由于这些方法需要较 大的计算量，而当时的计算机还不够普及而且速度也跟不上要求，限制了它们的 应用：三是当时基于符号处理的人工智能方法正处于其顶峰状态，使得人们难以 认识到其它方法的有效性和适应性。到了八十年代，人们越来越清楚地认识到传 统人工智能方法的局限性，并且由于计算机速度的提高以及并行计算机的普及， 塑兰三! ! ! 兰塑主兰竺丝查 苎二主竺堡 使得进化计算对机器速度的要求己不再是制约其发展的因素。更由于它的不断发 展及其在一些应用领域内取得的成功，进化计算己表现出了良好的应用前景。 由于进化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成 功，引起了包括数学、物理学、化学、生物学、计算机科学、社会科学、经济学 及工程应用等领域科学家们的极大兴趣。自八十年代中期以来，世界上许多国家 都掀起了进化计算的研究热潮。目前，有数种以进化计算为主题的国际会议在世 界各地定期召开。有些学者声称，进化计算将与混沌理论和分形几何一道成为人 们研究非线性现象和复杂系统的新的三大方法，并将与神经网络一道成为人们研 究认知过程的重要工具1 3 j 。 1 2 进化计算的主要分支 进化计算方法有很多种，目前比较有代表性的典型算法有三种：遗传算法、 进化策略和进化规划。这三种方法是彼此独立发展起来的，有许多不同之处。二 十世纪九十年代初，在遗传算法的基础上又发展了一个分支：遗传规划。这几个 分支在算法实现方面有一些细微的差别，但都具有一个共同的特点，即借助于生 物进化的思想和原理来解决实际问题。 下面分别就这几个分支作一个简单的介绍。 1 2 1 遗传算法 早在五十年代后期及六十年代初期，一些生物学家就着手采用电子计算机模 拟生物的遗传系统。尽管这些工作纯粹是研究生物现象，但是他们已开始使用现 代遗传算法的一些标识方式。1 9 6 2 年，美犀m i c h i g 姐大学的j h o l l 越d 教授在研 究自适应系统时，提出系统本身与外部环境的相互作用与协调。涉及进化算法的 思想。1 9 6 8 年，他又提出模式理论，奠定了遗传算法的主要理论基础。1 9 7 5 年， j _ h o l l a n d 出版了其开创性的著作”a d a p t 啦o ni n n a 加：r a l 髓d 甜t i f i e i a l8 y 8 t e m s ”【4 l 。后 来，j h o l l 如d 与他的学生们将该算法加以推广并应用到优化及机器学习等问题之 中，并且正式定名为遗传算法。遗传算法的通用编码技术藏简单有效的遗传操作 为其广泛的应用和成功奠定了基础。 h o l l 她d 的遗传算法常被称为简单遗传算法( 简记为s e a ) 。s g a 的操作对象 是一群二进制串( 称为染色体、个体) ，即种群( p o p l _ l l a t i ) 。这里每个染色体对 应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种 群中选择个体，使用交换( 册s v 贸) 和变异( 瑚妇d o n ) 来产生下一代种群。如 此一代代进化下去，直到满足期望的终止条件。 遗传算法可以形式化的描述如下【i j ：g 爿= p ( o ) ，s ，g ，p ，f ) 。 这里： 塑兰三! ! ! 兰塑主兰竺丝查 苎二主竺堡 使得进化计算对机器速度的要求己不再是制约其发展的因素。更由于它的不断发 展及其在一些应用领域内取得的成功，进化计算己表现出了良好的应用前景。 由于进化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成 功，引起了包括数学、物理学、化学、生物学、计算机科学、社会科学、经济学 及工程应用等领域科学家们的极大兴趣。自八十年代中期以来，世界上许多国家 都掀起了进化计算的研究热潮。目前，有数种以进化计算为主题的国际会议在世 界各地定期召开。有些学者声称，进化计算将与混沌理论和分形几何一道成为人 们研究非线性现象和复杂系统的新的三大方法，并将与神经网络一道成为人们研 究认知过程的重要工具1 3 j 。 1 2 进化计算的主要分支 进化计算方法有很多种，目前比较有代表性的典型算法有三种：遗传算法、 进化策略和进化规划。这三种方法是彼此独立发展起来的，有许多不同之处。二 十世纪九十年代初，在遗传算法的基础上又发展了一个分支：遗传规划。这几个 分支在算法实现方面有一些细微的差别，但都具有一个共同的特点，即借助于生 物进化的思想和原理来解决实际问题。 下面分别就这几个分支作一个简单的介绍。 1 2 1 遗传算法 早在五十年代后期及六十年代初期，一些生物学家就着手采用电子计算机模 拟生物的遗传系统。尽管这些工作纯粹是研究生物现象，但是他们已开始使用现 代遗传算法的一些标识方式。1 9 6 2 年，美犀m i c h i g 姐大学的j h o l l 越d 教授在研 究自适应系统时，提出系统本身与外部环境的相互作用与协调。涉及进化算法的 思想。1 9 6 8 年，他又提出模式理论，奠定了遗传算法的主要理论基础。1 9 7 5 年， j _ h o l l a n d 出版了其开创性的著作”a d a p t 啦o ni n n a 加：r a l 髓d 甜t i f i e i a l8 y 8 t e m s ”【4 l 。后 来，j h o l l 如d 与他的学生们将该算法加以推广并应用到优化及机器学习等问题之 中，并且正式定名为遗传算法。遗传算法的通用编码技术藏简单有效的遗传操作 为其广泛的应用和成功奠定了基础。 h o l l 她d 的遗传算法常被称为简单遗传算法( 简记为s e a ) 。s g a 的操作对象 是一群二进制串( 称为染色体、个体) ，即种群( p o p l _ l l a t i ) 。这里每个染色体对 应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种 群中选择个体，使用交换( 册s v 贸) 和变异( 瑚妇d o n ) 来产生下一代种群。如 此一代代进化下去，直到满足期望的终止条件。 遗传算法可以形式化的描述如下【i j ：g 爿= p ( o ) ，s ，g ，p ，f ) 。 这里： 塑兰三! ! ! 兰塑主兰竺丝查 苎二主竺堡 使得进化计算对机器速度的要求己不再是制约其发展的因素。更由于它的不断发 展及其在一些应用领域内取得的成功，进化计算己表现出了良好的应用前景。 由于进化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成 功，引起了包括数学、物理学、化学、生物学、计算机科学、社会科学、经济学 及工程应用等领域科学家们的极大兴趣。自八十年代中期以来，世界上许多国家 都掀起了进化计算的研究热潮。目前，有数种以进化计算为主题的国际会议在世 界各地定期召开。有些学者声称，进化计算将与混沌理论和分形几何一道成为人 们研究非线性现象和复杂系统的新的三大方法，并将与神经网络一道成为人们研 究认知过程的重要工具1 3 j 。 1 2 进化计算的主要分支 进化计算方法有很多种，目前比较有代表性的典型算法有三种：遗传算法、 进化策略和进化规划。这三种方法是彼此独立发展起来的，有许多不同之处。二 十世纪九十年代初，在遗传算法的基础上又发展了一个分支：遗传规划。这几个 分支在算法实现方面有一些细微的差别，但都具有一个共同的特点，即借助于生 物进化的思想和原理来解决实际问题。 下面分别就这几个分支作一个简单的介绍。 1 2 1 遗传算法 早在五十年代后期及六十年代初期，一些生物学家就着手采用电子计算机模 拟生物的遗传系统。尽管这些工作纯粹是研究生物现象，但是他们已开始使用现 代遗传算法的一些标识方式。1 9 6 2 年，美犀m i c h i g 姐大学的j h o l l 越d 教授在研 究自适应系统时，提出系统本身与外部环境的相互作用与协调。涉及进化算法的 思想。1 9 6 8 年，他又提出模式理论，奠定了遗传算法的主要理论基础。1 9 7 5 年， j _ h o l l a n d 出版了其开创性的著作”a d a p t 啦o ni n n a 加：r a l 髓d 甜t i f i e i a l8 y 8 t e m s ”【4 l 。后 来，j h o l l 如d 与他的学生们将该算法加以推广并应用到优化及机器学习等问题之 中，并且正式定名为遗传算法。遗传算法的通用编码技术藏简单有效的遗传操作 为其广泛的应用和成功奠定了基础。 h o l l 她d 的遗传算法常被称为简单遗传算法( 简记为s e a ) 。s g a 的操作对象 是一群二进制串( 称为染色体、个体) ，即种群( p o p l _ l l a t i ) 。这里每个染色体对 应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种 群中选择个体，使用交换( 册s v 贸) 和变异( 瑚妇d o n ) 来产生下一代种群。如 此一代代进化下去，直到满足期望的终止条件。 遗传算法可以形式化的描述如下【i j ：g 爿= p ( o ) ，s ，g ，p ，f ) 。 这里： 浙江工业大学硕士学位论文 第一章绪论 p ( o ) = ( q ( 0 ) ，口：( o ) ，口。( 0 ) ) ，“，表示初始种群； ，= 口7 = ( o ，l 7 ，表示长度为l 的二迸制串全体，称为位串空间： n 表示种群中含有个体的个数； 1 表示二进制串的长度： 5 ：，“_ ，表示选择策略； g 表示遗传算子，通常包括复制算子d ，：，专，交换算子o c ； ，斗，和变异算子0 。：，一， p 表示遗传算子的操作概率，包括复制概率p r ，、交换概率p 。和变异概率p 。 厂：，_ 月+ 是适应度函数： f ：，”_ o ，1 ) 是终止准则。 值得注意的是：目前的遗传算法已不再局限于二进制编码。 1 2 2 进化策略 在2 0 世纪6 0 年代初，当时在柏林工业大学的i r e c h e n b c r g 和h p s c h w e f c l 等在进行风洞中的流体力学问题实验时，由于在设计中描述物体形状的参数难以 用传统的方法进行优化，他们利用生物变异的思想来随机地改变参数值并获得了 较好的结果。随后，他们便对这种方法进行了较深入的研究和发展，形成了进化 计算的另一个分支进化策略嘲。 早期进化策略的种群中只包含一个个体，而且只使用变异操作，用每一代变 异后的新个体与其父代个体进行比较再选择两者之优。这一选择策略目前称为( 1 + 1 ) 策略，它使用的变异算子是基于正态分布盼变异操作。( 1 + 1 ) 进化策略存 在很多弊端，如有时收敛不到全局最优解，效率较低等。它的改进方法是增加种 群内个体的数量，也就是( 肛+ d 进化策略。此时种群有h 个个体。随机地选取一个 个体进行变异，然后取代群体中最差的个体。( 一1 ) 进化策略与( i + 1 ) 进化策略 的相似之处是每次只产生一个后代，为了进一步提高效率，后来又形成了( “+ 九) 进化策略和( “，九) 进化策略，并且引进了重组( 哪b i n 砒i o n ) 操作，即由二个 个体按类似于杂交的方式生成一个个体。( 肛+ 九) 进化策略根据种群内的“个个体 产生九个个体( 用变异和重组) ，然后将“+ 九个个体进行比较再在其中选取个最 优者，( “，九) 进化策略是在新产生的九( ) 个个体中选取个最优者，这两种进 化策略中的选择方法分别被称为( + 九) 选择和( 斗a 选择。 进化策略和遗传算法的不同之处在于：遗传算法簧将原闷聪的解空间映射到 位串空间之中，然后再实行遗传操作。它强调个体基因结构的变化对其适应度的 影响，而进化策略则是直接在解空间上进行操作，它强调进化过程中从父代到后 代行为的自适应性和多样性。从搜索空间的角度来说，进化策略直接在解空间上 操作，它强调进化过程中搜索方向和步长的自适应调节。 浙江工业大学硕士学位论文 第一章绪论 p ( o ) = ( q ( 0 ) ，口：( o ) ，口。( 0 ) ) ，“，表示初始种群； ，= 口7 = ( o ，l 7 ，表示长度为l 的二迸制串全体，称为位串空间： n 表示种群中含有个体的个数； 1 表示二进制串的长度： 5 ：，“_ ，表示选择策略； g 表示遗传算子，通常包括复制算子d ，：，专，交换算子o c ； ，斗，和变异算子0 。：，一， p 表示遗传算子的操作概率，包括复制概率p r ，、交换概率p 。和变异概率p 。 厂：，_ 月+ 是适应度函数： f ：，”_ o ，1 ) 是终止准则。 值得注意的是：目前的遗传算法已不再局限于二进制编码。 1 2 2 进化策略 在2 0 世纪6 0 年代初，当时在柏林工业大学的i r e c h e n b c r g 和h p s c h w e f c l 等在进行风洞中的流体力学问题实验时，由于在设计中描述物体形状的参数难以 用传统的方法进行优化，他们利用生物变异的思想来随机地改变参数值并获得了 较好的结果。随后，他们便对这种方法进行了较深入的研究和发展，形成了进化 计算的另一个分支进化策略嘲。 早期进化策略的种群中只包含一个个体，而且只使用变异操作，用每一代变 异后的新个体与其父代个体进行比较再选择两者之优。这一选择策略目前称为( 1 + 1 ) 策略，它使用的变异算子是基于正态分布盼变异操作。( 1 + 1 ) 进化策略存 在很多弊端，如有时收敛不到全局最优解，效率较低等。它的改进方法是增加种 群内个体的数量，也就是( 肛+ d 进化策略。此时种群有h 个个体。随机地选取一个 个体进行变异，然后取代群体中最差的个体。( 一1 ) 进化策略与( i + 1 ) 进化策略 的相似之处是每次只产生一个后代，为了进一步提高效率，后来又形成了( “+ 九) 进化策略和( “，九) 进化策略，并且引进了重组( 哪b i n 砒i o n ) 操作，即由二个 个体按类似于杂交的方式生成一个个体。( 肛+ 九) 进化策略根据种群内的“个个体 产生九个个体( 用变异和重组) ，然后将“+ 九个个体进行比较再在其中选取个最 优者，( “，九) 进化策略是在新产生的九( ) 个个体中选取个最优者，这两种进 化策略中的选择方法分别被称为( + 九) 选择和( 斗a 选择。 进化策略和遗传算法的不同之处在于：遗传算法簧将原闷聪的解空间映射到 位串空间之中，然后再实行遗传操作。它强调个体基因结构的变化对其适应度的 影响，而进化策略则是直接在解空间上进行操作，它强调进化过程中从父代到后 代行为的自适应性和多样性。从搜索空间的角度来说，进化策略直接在解空间上 操作，它强调进化过程中搜索方向和步长的自适应调节。 浙江工业大学硕士学位论文 第一章绪论 进化策略主要用于求解数值优化问题。近年来，遗传算法也采用十进制编码 技术来求解数值优化问题。e s 与g a 的互相渗透使得它们已经没有很明显的界限。 1 2 3 进化规划 进化规划( e v o l u t i o n a r yp r o g r a 衄i n g ) 的方法最初是由l j f o g e l 等在2 0 世纪 6 0 年代提出的【6 】。他们在人工智能的研究中发现，智能行为即是要具有能预测其 所处环境的状态，并按照给定的目标作出适当响应的能力。在研究中，他们将模 拟环境描述成是由有限字符集中的符号组成的序列f s m 。于是问题转化为：怎样 根据当前观察到的符号序列做出响应以获得最大收益，这里收益的计算是按照环 境中将要出现的下一个符号及预先定义好的效益目标来确定的。进化规划中常用 有限态自动机( f h l i t es t a t em a c h i n e ，简称f s m ) 来表示这样的策略。这样，问题 便成为：如何设计出一个有效的f s m ? l j f o g e l 等借用进化的思想对一群f s m 进 化以获得较好的f s m ，并将此方法应用到数据诊断、模式识别和分类以及控制系 统的设计等问题之中，取得了较好的结果。后来，d b f o g e l 借助于进化策略方法 对进化规划进行了更深的发展，并应用到数值优化及神经网络的训练等问题之中 m 1 2 4 遗传规划 自计算机出现以来，计算机科学的一个重要目标即是让计算机自动进行程序 设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传 规划便是在该领域内的一种尝试。它采用遗传算法的基本思想，但使用一种更为 灵活的表示方式分层结构来表示解空间。这些分层结构的叶节点是问题的原 始变量，中间节点则是组合这些原始变量的函数，这样每一个分层结构对应问题 的一个解，也可以理解为求解该问题的一个计算机程序。遗传规螂即是使用一些 遗传操作动态地改变这些结构以获得解决该问题的可行船计算机程序。遗传规划 的思想是鼬m d f o r d 大学的j r k o 盟在2 0 世纪9 0 年代楞挺出的，l 雪9 2 年和1 9 9 4 年他又先后出版专著“a 蛔鲥c 舯驴猢啦i l 峪；o n 证呤p r o 鳓躺衄醪c o m p u t e r sb y m e a n so f n 矾瑚is e l e c t ”和“g 吼c t i cp r o 蓼蚴啦i i ，加哟m 舔cd 雠嗍o f 托i l s a b l e p r o g f a m s ”，又于1 9 9 9 年他又和f o r c s t 等人写了“g 髓e t i e p f o 鄹瑚戚崤m - d a 瑚i i l i 孤 h l v e 而o na n dp f o b l 锄s o l v m g ”，全面介绍了遗传规划的原理、实例和以及在各领 域内的应用，k d z a 因此被视为遗传规划的奠基人f 9 1 0 ，。 1 3 进化计算的主要特点 进化算法与传统的算法具有很多不同之处，但其最主要的特点体现在下述两 个方面。 浙江工业大学硕士学位论文 第一章绪论 进化策略主要用于求解数值优化问题。近年来，遗传算法也采用十进制编码 技术来求解数值优化问题。e s 与g a 的互相渗透使得它们已经没有很明显的界限。 1 2 3 进化规划 进化规划( e v o l u t i o n a r yp r o g r a 衄i n g ) 的方法最初是由l j f o g e l 等在2 0 世纪 6 0 年代提出的【6 】。他们在人工智能的研究中发现，智能行为即是要具有能预测其 所处环境的状态，并按照给定的目标作出适当响应的能力。在研究中，他们将模 拟环境描述成是由有限字符集中的符号组成的序列f s m 。于是问题转化为：怎样 根据当前观察到的符号序列做出响应以获得最大收益，这里收益的计算是按照环 境中将要出现的下一个符号及预先定义好的效益目标来确定的。进化规划中常用 有限态自动机( f h l i t es t a t em a c h i n e ，简称f s m ) 来表示这样的策略。这样，问题 便成为：如何设计出一个有效的f s m ? l j f o g e l 等借用进化的思想对一群f s m 进 化以获得较好的f s m ，并将此方法应用到数据诊断、模式识别和分类以及控制系 统的设计等问题之中，取得了较好的结果。后来，d b f o g e l 借助于进化策略方法 对进化规划进行了更深的发展，并应用到数值优化及神经网络的训练等问题之中 m 1 2 4 遗传规划 自计算机出现以来，计算机科学的一个重要目标即是让计算机自动进行程序 设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传 规划便是在该领域内的一种尝试。它采用遗传算法的基本思想，但使用一种更为 灵活的表示方式分层结构来表示解空间。这些分层结构的叶节点是问题的原 始变量，中间节点则是组合这些原始变量的函数，这样每一个分层结构对应问题 的一个解，也可以理解为求解该问题的一个计算机程序。遗传规螂即是使用一些 遗传操作动态地改变这些结构以获得解决该问题的可行船计算机程序。遗传规划 的思想是鼬m d f o r d 大学的j r k o 盟在2 0 世纪9 0 年代楞挺出的，l 雪9 2 年和1 9 9 4 年他又先后出版专著“a 蛔鲥c 舯驴猢啦i l 峪；o n 证呤p r o 鳓躺衄醪c o m p u t e r sb y m e a n so f n 矾瑚is e l e c t ”和“g 吼c t i cp r o 蓼蚴啦i i ，加哟m 舔cd 雠嗍o f 托i l s a b l e p r o g f a m s ”，又于1 9 9 9 年他又和f o r c s t 等人写了“g 髓e t i e p f o 鄹瑚戚崤m - d a 瑚i i l i 孤 h l v e 而o na n dp f o b l 锄s o l v m g ”，全面介绍了遗传规划的原理、实例和以及在各领 域内的应用，k d z a 因此被视为遗传规划的奠基人f 9 1 0 ，。 1 3 进化计算的主要特点 进化算法与传统的算法具有很多不同之处，但其最主要的特点体现在下述两 个方面。 浙江工业大学硕士学位论文 第一章绪论 1 3 1 智能性 进化计算的智能性包括自组织、自适应和自学习。应用进化计算求解问题时， 在确定了编码方案、适应度函数及遗传算予以后，算法将利用进化过程中获得的 信息自行组织搜索。由于基于自然选择的策略为：适者生存、不适者淘汰，故而 适应值大的个体具有较高的生存概率。通常适应值大的个体具有更适应环境的基 因结构，再通过交换和基因突变等遗传操作就可能产生与环境更适应的后代。进 化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境的变化自动发 现环境的特性和规律的能力。 自然选择消除了算法设计过程中的一个最大障碍：即需要事先描述问题的全 部特点，并说明针对问题的不同特点算法应采取的措施。于是，利用进化计算的 方法我们可以解决那些结构仍未知的复杂问题。 1 3 2 本质并行性 进化计算的本质并行性表现在两个方面：一是进化计算是内在并行的( i n h e r e i l t n a r a l l e i s m l ，即进化算法本身非常适合大规模并行。最简单的并行方式是让几百甚 至数干台计算机各自进行独立种群的进化计算，运行过程中甚至不进行任何通信 ( 独立的种群之间若有少量的通信一般会带来更好的结果) 。等到运算结束时才通 信比较，选取最佳个体，这种并行处理方式对并行系统结构也没有什么限制和要 求。可以说，进化计算适合在目前所有的并行机或分布系统上进行并行处理，而 且对其并行效率没有太大的影响。二是进化计算的内含并行性( i m p l i c i t 口缸a l l e l i s m ) ，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间 内的多个区域，并相互交流信息，这种搜索方式使得它虽然每次只执行与种群规 模成比例的计算，而实质上已进行了大约d ( 3 ) 次有效搜索。这使得进化计算能 以较少的计算获得较大的收益。 迸化计算的基本特征，除了其自组织、自适应和本质并行性外，还表现在 以下几个方面： 1 、过程性：进化计算通过自然选择和遗传操作等自组织行为来增强群体的 适应性。算法模拟的是一个过程，算法的实施也是一个过程。在这个过程中， 算法本身无法判定个体处在解空间的位置，因此需要人为干预( 即事先需确定终 止准则) 才能终止。 2 、多解性：进化计算的另一基本特征是采用群体的方式组织搜索。它从多 个点出发，通过这些点内部结构的调整和重组来形成新的点。因而，每次都得 提供多个近似解，这对多目标搜索或在需要多个近似解作为参数的情况下是非 常有用的。 3 、不确定性：进化计算的不确定性是伴随其随机性而来的。进化计算的主 浙江工业大学硕士学位论文 第一章绪论 1 3 1 智能性 进化计算的智能性包括自组织、自适应和自学习。应用进化计算求解问题时， 在确定了编码方案、适应度函数及遗传算予以后，算法将利用进化过程中获得的 信息自行组织搜索。由于基于自然选择的策略为：适者生存、不适者淘汰，故而 适应值大的个体具有较高的生存概率。通常适应值大的个体具有更适应环境的基 因结构，再通过交换和基因突变等遗传操作就可能产生与环境更适应的后代。进 化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境的变化自动发 现环境的特性和规律的能力。 自然选择消除了算法设计过程中的一个最大障碍：即需要事先描述问题的全 部特点，并说明针对问题的不同特点算法应采取的措施。于是，利用进化计算的 方法我们可以解决那些结构仍未知的复杂问题。 1 3 2 本质并行性 进化计算的本质并行性表现在两个方面：一是进化计算是内在并行的( i n h e r e i l t n a r a l l e i s m l ，即进化算法本身非常适合大规模并行。最简单的并行方式是让几百甚 至数干台计算机各自进行独立种群的进化计算，运行过程中甚至不进行任何通信 ( 独立的种群之间若有少量的通信一般会带来更好的结果) 。等到运算结束时才通 信比较，选取最佳个体，这种并行处理方式对并行系统结构也没有什么限制和要 求。可以说，进化计算适合在目前所有的并行机或分布系统上进行并行处理，而 且对其并行效率没有太大的影响。二是进化计算的内含并行性( i m p l i c i t 口缸a l l e l i s m ) ，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间 内的多个区域，并相互交流信息，这种搜索方式使得它虽然每次只执行与种群规 模成比例的计算，而实质上已进行了大约d ( 3 ) 次有效搜索。这使得进化计算能 以较少的计算获得较大的收益。 迸化计算的基本特征，除了其自组织、自适应和本质并行性外，还表现在 以下几个方面： 1 、过程性：进化计算通过自然选择和遗传操作等自组织行为来增强群体的 适应性。算法模拟的是一个过程，算法的实施也是一个过程。在这个过程中， 算法本身无法判定个体处在解空间的位置，因此需要人为干预( 即事先需确定终 止准则) 才能终止。 2 、多解性：进化计算的另一基本特征是采用群体的方式组织搜索。它从多 个点出发，通过这些点内部结构的调整和重组来形成新的点。因而，每次都得 提供多个近似解，这对多目标搜索或在需要多个近似解作为参数的情况下是非 常有用的。 3 、不确定性：进化计算的不确定性是伴随其随机性而来的。进化计算的主 浙江工业大学硕士学位论文 第一章绪论 要步骤都含有随机因素，从而在算法的进化过程中，事件发生的与否带有很大 的不确定性。 4 、非定向性：自然选择和生殖过程这种非定向机制是进化计算的关键。它 没有确定的迭代方程也不依靠梯度下降法似的爬山策略，而是用调整群体的内 部结构的方法来增强其对环境的适应度，使得问题得到解决。 5 、内在学习性：学习是有选择的保留行为。知识通过反复实践获得。学习是 进化过程自身所具有的不可与其分割的行为方式。与自然进化过程类似，它也 有三种不同的学习方式，而这些学习方式又内在地体现在进化计算的整个过程 中。 ( 1 ) 宗亲学习( p h y l o g e n e t i cl e 蛐i n g ) ：这种学习发生在整个进化过程中，祖 先的良好特征通过遗传传递给后代，后代通过家族成员“血缘”继承方式学习 其先辈的自适应行为。 ( 2 ) 社团学习( s o c i o g e n e t i c1 e 鼬i n g ) ：这种学习是一些经验和知识在某个社 团内的共享，体现在进化计算中即是独立群体内部知识或结构的共享。 ( 3 ) 个体学习( o m o g e n e t i cl e a r i l i n g ) ：这种学习是自然界中发生最为频繁的一 种行为。生物体为了生存，就必须进行学习。它通过不断实践来积累知识和经 验，以增强自已的适应性，进化计算的个体学习方式是通过改变个体的基因结 构来提高自己的适应性。 6 、统计性：进化计算的种群方式决定它是一个统计过程。在每进化代， 都要进行统计，以确定个体的优劣并驱动进化的进行。 7 、稳健性：算法的稳健性是指在不同的条件和环境下算法的适用性和有效性。 由于进化计算利用个体的适应值推动群体的进化，而不管求解问题本身的结构特 征。因而，用进化计算求解不同问题时，我们只需设计相应的适应性评价函数， 而无需修改算法的其它部分。同时，因为进化计算具有自然系统的自适应特征， 算法在效率和效益之间的权衡使得它能适用不同的环境并取得较好的结果。 8 、整体优化：传统的优化方法，一般采用的是梯度下降的爬山策略，从而使 得对多峰函数的情形往往容易陷入局部最优。而进化计算能同时在解空间的多个 区域内进行搜索，并且能以较大的概率跳出局部最优，以找出整体最优解。 1 4 调度问题的背景 组合优化中发展最迅速的领域之一是确定性调度问题一工件在机器上加工的 问题。使用一般的术语，这类问题可叙述如下，已给一个任务榘，要在已知的机 器集合上进行加工，在满足所有的加工条件下，使得某目标函数达到最小( 最大) 。 这里假定所有的任务参数都是以确定形式预先给出的。此假定对于某些问题是正 确的，并可以取得良好的调度效果。但是对于另外一些问题，任务参数在实践中 6 浙江工业大学硕士学位论文 第一章绪论 要步骤都含有随机因素，从而在算法的进化过程中，事件发生的与否带有很大 的不确定性。 4 、非定向性：自然选择和生殖过程这种非定向机制是进化计算的关键。它 没有确定的迭代方程也不依靠梯度下降法似的爬山策略，而是用调整群体的内 部结构的方法来增强其对环境的适应度，使得问题得到解决。 5 、内在学习性：学习是有选择的保留行为。知识通过反复实践获得。学习是 进化过程自身所具有的不可与其分割的行为方式。与自然进化过程类似，它也 有三种不同的学习方式，而这些学习方式又内在地体现在进化计算的整个过程 中。 ( 1 ) 宗亲学习( p h y l o g e n e t i cl e 蛐i n g ) ：这种学习发生在整个进化过程中，祖 先的良好特征通过遗传传递给后代，后代通过家族成员“血缘”继承方式学习 其先辈的自适应行为。 ( 2 ) 社团学习( s o c i o g e n e t i c1 e 鼬i n g ) ：这种学习是一些经验和知识在某个社 团内的共享，体现在进化计算中即是独立群体内部知识或结构的共享。 ( 3 ) 个体学习( o m o g e n e t i cl e