（计算机应用技术专业论文）文化算法及其在优化调度中的应用研究.pdf

中文摘要 文化算法提供了一种明确的机制来表示、存储和整合进化过程中的知识。其主 要思想：在进化过程中，从进化的种群中获取待解决问题的经验知识，将这些经验 知识存储在信念空间中，并用这些知识来指导种群进化过程，从而提高搜索效率。 因此在一些问题上取得了比传统进化算法更好的结果，特别是在求解约束优化问题 方面，全局优化能力和计算效率明显优于传统进化算法。目前文化算法应用于机器 学习、自动控制、语义网络、生产调度等广泛领域。对于每一特定问题，文化算法 的难点及其关键在于信念空间模型的设计和影响函数的实现。 本文在深入研究文化算法基础上，将进化规划和差分算法纳入文化算法框架， 并用改进的文化算法求解约束优化问题和f l o ws h o p 调度优化问题。本文主要工作如 下： ( 1 ) 首先对文化算法的来源、基本原理、机制、特点及应用等进行了系统研究和 详细阐述； ( 2 ) 提出了一种基于进化规划的文化算法，该算法在基于自适应的文化算法中引 入进化规划，有效利用进化过程中相关知识引导种群进化，在很大程度上提高了收 敛速度。 ( 3 ) 提出一种基于文化算法和改进差分进化算法的混合优化算法，该算法将改进 差分进化算法引入种群空间的进化操作，从而实现改进差分进化算法在进化过程中 知识的动态获取和知识对改进差分进化种群空间进化的有效指导，保证了种群的多 样性和收敛速度。 ( 4 ) 用b e n c h m a r k 函数对上述两种优化算法进行仿真，试验结果表明两种算法均优 于传统的进化算法。 ( 5 ) 用c a e p 和c a m d e 算法求解丁烯烷化生产过程的约束优化问题，并用 c a m d e 算法求解f l o ws h o p 调度优化问题。经仿真测试，两种算法都具有很好的搜 索性能，同时证实了文化算法求解生产调度问题的可行性。 关键词：文化算法；进化规划；差分进化算法；信念空间；约束优化；优化调度 a b s t r a c t c u l t u r a la l g o r i t h m ( c a ) p r o v i d e sa ne x p l i c i tm e c h a n i s mf o ra c q u i s i t i o n ， s t o r a g ea n di n t e g r a t i o no fi n d i v i d u a la n dg r o u p sp r o b l e ms o l v i n ge x p e r i e n c e a n db e h a v i o r t h em a i ni d e ao fc ai si n d i v i d u a l sf r o mt h ep o p u l a t i o n c o m p o n e n ti n t e r a c tw i t hk n o w l e d g ei nt h e b e l i e fs p a c ed u r i n gt h es e a r c h p r o c e s s ，i n d i v i d u a le x p e r i e n c ec a nm o d i f yk n o w l e d g es t o r e di nt h eb e l i e f s p a c ea n dt h a tk n o w l e d g ec a r ll i k e w i s eb eu s e dt oi n f l u e n c ei n d i v i d u a l si nt h e p o p u l a t i o n t h i sc a ni m p r o v et h er a t eo fs e a r c ha n dc o n v e r g e n c e t h e r e f o r e c ap e r f o r m sb e t t e ro ns o m ep r o b l e m st h a nt h et r a d i t i o n a le v o l u t i o n a r y a l g o r i t h m s ，e s p e c i a l l yi ns o l v i n gc o n s t r a i n e do p t i m i z a t i o np r o b l e m s ，t h e g l o b a lo p t i m i z a t i o na b i l i t y a n dc o m p u t a t i o n a le f f i c i e n c yi sb e t t e rt h a n t r a d i t i o n a le v o l u t i o n a r ya l g o r i t h m s s of a r , c ah a sb e e ns u c c e s s f u l l ya p p l i e d t o m a n ya r e a s ，s u c h a sm a c h i n el e a m i n g ，a u t o m a t i cc o n t r o l ，s e m a n t i c n e t w o r k s ，p r o d u c t i o ns c h e d u l i n g f o re a c hs p e c i f i cp r o b l e m ，t h ed i f f i c u l t i e s o fc aa r et h ed e s i g no fb e l i e fs p a c ea n dt h ei m p l e m e n t a t i o no fi n f l u e n t f u n c t i o n t h i s p a p e rp r o p o s e s t h ec u l t u r a l a l g o r i t h mb a s e d o ne v o l u t i o n a r y p r o g r a m m i n ga n dh y b r i da l g o r i t h m b a s e do nc u l t u r a la l g o r i t h ma n dm o d i f i e d d i f f e r e n t i a le v o l m i o na f t e rw e l ls t u d yc a u s i n gi m p r o v e dc at os o l v e c o n s t r m n e d o p t i m i z a t i o np r o b l e m sa n df l o ws h o pp r o b l e m t h e m a i n r e s e a r c hw o r ki sa sf o ll o w s ： ( 1 ) t h ep a p e re l a b o r a t e st h es o u r c e s ，t h eb a s i cp r i n c i p l e s ，m e c h a n i s m s ， f e a t u r e sa n da p p l i c a t i o no fc ai nd e t a i l ( 2 ) c u l t u r a la l g o r i t h mb a s e do ne v o l u t i o n a r yp r o g r a m m i n g ( c a e p ) i s p r o p o s e di nt h i sp a p e r t h i sa l g o r i t h me m b e d se v o l u t i o n a r yp r o g r a m m i n g i n t ot h ec af r a m e w o r k ，w h i c hu t i l i z e sk n o w l e d g ee x t r a c t e dd u r i n ge v o l u t i o n t o g u i d et h ee v o l u t i o no fp o p u l a t i o ns p a c e i nt h i sw a y ，i ts p e e d su pt h e e v o l u t i o n a r yp r o c e s s ( 3 ) an e wh y b r i da l g o r i t h mb a s e do nc u l t u r a la l g o r i t h ma n dm o d i f i e d d i f f e r e n t i a le v o l u t i o n ( c a m d e ) i sp u tf o r w a r d ，w h i c he m b e d sm o d i f i e d t t t d i f f e r e n t i a le v o l u t i o ni n t ot h ec af r a m e w o r k t h ea l g o r i t h mi m p l e m e n t st h e a c q u i s i t i o no fk n o w l e d g ea n dg u i d e st h ee v o l u t i o no fp o p u l a t i o ns p a c eb a s e d o nm o d i f i e dd i f f e r e n t i a le v o l u t i o n i nt h ew a y i ta s s u r e st h ed i v e r s i t yo f p o p u l a t i o ns p a c ea n dt h es p e e do fc o n v e r g e n c e ( 4 ) s i m u l a t i o nt e s t sa r ep e r f o r m e db a s e do nb e n c h m a r kf u n c t i o n sa n d t h er e s u l t si n d i c a t et h a tt h et w oa l g o r i t h m sp r o p o s e dp e r f o r mb e t t e rt h a n t r a d i t i o n a le v o l u t i o n a r ya l g o r i t h m s ( 5 ) c a e pa n dc a m d ew e r eu s e dt os o l v et h ep r o d u c t i o ns c h e d u l i n g p r o b l e mo fb u t e n ea l k y l a t i o n a n dc a ew a su s e dt os o l v ef l o ws h o p p r o b l e m t h er e s u l t ss u g g e s tt h a tt h et w oa l g o r i t h m sc a ni m p r o v et h er a t eo f s e a r c h ，a n dc o n f i r mt h ef e a s i b i l i t yo fu s i n gc at os o l v ep 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 k e yw o r d s ：c u l t u r a la l g o r i t h m ；e v o l u t i o n a r yp r o g r a m m i n g ；d i f f e r e n t i a l e v o l u t i o n ；b e l i e fs p a c e ；c o n s t r a i n e d o p t i m i z a t i o n ；o p t i m i z a t i o n a n d s c h e d u l i n g i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：盔盔金 日期：2 磋皇孽垒盈 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) o 作者签名：鲞复昌金日期：2 篮纽垒望 勒孙蒸鍪丛隰避幽 第一章绪论 1 1 课题研究的背景及意义 第一章绪论 1 1 1 课题研究的背景 神秘的大自然给人们带来了惊喜的同时，也启迪了无数的科学发明，帮人们解 决了很多实际问题，例如很多的进化算法，不依赖于具体问题并且对问题的知识所 需较少，在解决工程实践问题上取得了很好成绩。因此，进化算法引起很多研究人 员的兴趣，目前进化算法的许多研究还只是集中在生物自然选择这一层面上，( 也可 以说是基因) 。然而很多情况表明，文化能使种群以一定的速度进化和适应环境，而 这个速度是超越单纯依靠基因遗传生物进化速度的。在进化种群中，个体经验知识 的积累以及群体内部知识的交流在另外一个层面促进群体的进化，只注重知识在此 称为文化。文化被d u r h a m i l l 定义为“一个通过符号编码表示众多概念的系统，而这 些概念是在群体内部以及不同群体之间被广泛和历史般长久传播的”。学者r e n f r e w 2 】 指出，随着时间的迁移人类在进化过程中渐渐掌握了提取，编码，和传播信息知识 的能力，这种能力是区别其他物种人类所特有的能力。正是这种能力使人类形成， 积累和传递经验，可以加快和指导发展的速度和方向。所以说人类社会的进化不仅 仅是自然选择的结果而是超越了自然选择的水平。人类文化的发展对其产生巨大的 影响，甚至可以说人类发展到今天这个阶段，文化对其未来的发展将起到主要作用。 文化进化的优点是明显的。人类拥有当今如此发达的文明成果，文化进化“功 不可没”。较之生物进化，文化进化以其特有的机制和特征推动着人类社会以日益 倍增的速度向前发展，以至于达到今天这种高度发达的社会。尽管文化的产生最初 是生物进化的结果，是生存和繁衍的需要，但是文化进化有着更为丰富、复杂的内 涵。文化进化的适应性结果，不仅仅促进了人类的生存和繁殖，更促进了文化形式 自身及其载体的扩张、繁衍。显然，在文化进化过程中必定存在着非常重要的进化 机制，这种进化机制必然有其非常有效的成分。如何找到这种进化机制的本质，并 利用其为人类服务便成为一个非常重要的任务。 文化的定义假定文化的内容存在一般的智力知识。在人类社会中，文化被看成 是保存信息的载体，这些信息可以被社会的所有成员获得并用来知道他们的行为。 1 文化算法及其在优化调度中的应用研究 换句话说，文化的继承给社会的新一代成员提供信息和指导来帮助他们适应环境。 没有这些信息，个体人适应环境的唯一方法就是通过试验和犯错误来获得经验。 单从文化这一概念上来看，我们就知道可以用它来记录了一些有用的知识与经 验，将知识与经验形成结论模型，并通过结论模型来组织世界。1 9 世纪6 0 年代，信 息论和系统论的研究将文化看成人与环境相交互的系统，能够对系统中的人产生正 向或负向的影响，社会学研究人员认为文化是一种将人的经验保存在知识库中，其 他人可以在知识库中学到他没有直接经历得经验知识。与之相似，当面对一种新的 计算问题时，我们就会有一些与之相似问题的结论，可以利用这些结论来指导解决 新的问题。我们可以利用文化的这一属性来建立一知识群，这一知识群含有很多“共 识 。知识群与计算科学之间就建立了一种新的桥梁与模式。例如：可以基于这样 的假设，在某一进化算法个体可以有更好的学习机率加入到进化的要素中，这些加 入的要素可以叫做信念空间( b e l i e f s p a c e ) ，利用这一信念空间可以用来加快和引导 个体( 或是种群) 发展的方向和速度。从而更好的处理大量问题。受到这一启发， r e y n o l d s 提出了文化系统的演化模型，用它对演化计算系统的经验积累建模。文化算 法( ( c u l t u r a la l g o r i t h m ，简称c a ) ) 是r e y n o l d s t 3 】于1 9 9 4 年提出的一种新的进化模型， 它是从模拟文化进化过程提出来的。近几年这一算法引起人们关注，但国内研究的 还比较少。 1 1 2 课题研究的意义 在传统进化算法中，起到关键作用的交叉和变异两个算子都是在一定发生概率 的条件下，随机地、没有指导地迭代搜索。因此，种群空间中的个体在进化的同时， 有可能产生退化现象。在某些情况下，这种退化现象还相当明显。此外，每一个待 求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法 的交叉和变异算子却相对固定，在求解问题时，缺乏对这些特征信息和知识的有效 利用，从而减缓了进化速度。特别是在求解一些复杂问题时，对他特征信息和知识 的忽视所带来的损失往往就比较明显。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 、免疫算法( i m m u n ea l g o r i t h m ，简称i a ) 、 微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，简称p s o ) 等进化计算方法， 不依赖于具体问题，对问题的知识所需较少，甚至不需要，在解决工程实践问题上 取得了很好的成绩。但目前进化计算的许多研究还只是集中在生物( 或者说是基因) 自然选择( 竞争) 这一层面上。然而许多情况表明，文化能使种群以一定的速度进化 和适应环境，而这个速度是超越单纯依靠基因遗传生物进化速度的。 2 第一章绪论 传统的进化算法，实际上是一种盲目启发式搜索算法，并没有提供一种明确的 机制来表示、存储和整合进化过程中的知识，而文化算法则提供了一种非常明确的 机制来获取、储存和整合个体以及种群在解决问题时所得到的经验知识，并利用这 些经验知识来引导种群的进化，正是由于对经验知识的充分利用，使得文化算法在 一些问题上取得了比传统进化算法更好的结果。特别是在求解约束优化问题方面， 全局优化能力和计算效率明显优于传统进化算法，并在动态环境优化、数据挖掘、 多目标优化等方面都有成功的应用。 文化算法超越传统的进化算法，通过模拟微观、宏观两个层面的进化，更加准 确地反映了物种的进化过程。但由于对文化算法的研究才刚刚开始，还远没有像遗 传算法和免疫算法那样形成系统的分析方法和一定的数学基础，有许多问题还需要 进一步研究。因此有必要对文化算法进行深入研究和分析，对其来源、基本原理、 特点，应用等方面展开系统全面的研究，为后续学者开展相关研究提供方便。文化 算法是在深入分析原有进化理论的优越性与不足的基础上，借鉴社会科学中的社会 ( 文化) 进化理论与已取得广泛共识的研究成果，而提出的一种新的进化算法。本文 将对文化算法的框架和算子的设计加以讨论，并应用于解决约束优化问题和生产调 度问题。 生产调度问题是一个n p h a r d 问题，该问题是实现制造系统运筹技术，交通运输 及邮电通讯技术，管理技术与组合优化技术发展的核心。随着现代工业的发展，企 业的生产正朝着多类型、小批量、有着不同完工时间和产品要求的方向发展，从而 使得企业的生产作业计划安排工作难度加大。 生产调度传统精确的方法，如枚举法、分支定界法、动态规划法等，由于计算 量大，仅适合小规模问题，对较大规模的生产调度问题将无能为力，而且，解决生 产调度问题的经济性要求也不允许用这类方法来求解。 启发式算法成为了人们解决实际调度问题的一类重要方法，能为多数调度问题 找到近似最优解。启发式算法成为了人们解决实际调度问题的一类重要方法，能为 多数调度问题找到近似最优解。但是启发式搜索方法都面临的难题是如何提高全局 搜索能力，如何提高收敛速度和稳定性。目前许多研究都设法吸取和融合更多的进 化思想，对算法进行改进，提高其搜索性能。近几年来，遗传算法在生产调度问题 中的应用已形成一股研究热潮。但单纯的用遗传算法有可能导致陷入局部最优解， 并且在种群规模比较大的时候收敛的速度比较慢。禁忌搜索是一个效率较好的启发 3 文化算法及其在优化调度中的应用研究 式算法，它能找到调度问题不少算例的最优解。但禁忌搜索要面对很多的问题，如 初始解问题、邻域结构问题、搜索策略和禁忌表的长度问题等等。只有很好地解决 了这些问题，禁忌搜索算法才能表现得更好。 因此，只有寻找高效的调度算法，才能提高生产效益和资源利用率，进而增强 企业的竞争能力，所以对该问题的研究具有重要的理论和实用价值。因此，生产调度 问题一直是生产及组合优化等领域研究的热点之一。 1 2 国内外研究现状 1 2 1 文化算法的发展以及现状 文化算法自提出以来，在计算智能领域备受关注，已经被成功地应用于解决约 束单目标优化、多目标优化、图象分割等问题，并在工程领域、工业、语义网络、 作业调度中也取得较好的效果。文化算法使用的关键问题就是根据不同问题的特点 来设计算法知识空间、种群空间、接受和影响函数的实现方法。 最初的文化算法在种群空间中使用遗传算法，在信念空间采用机器学习，并被 用来求解实数优化问题。这两个部分互相通信互相合作，从而产生出一些与种群进 化相关的高层推理。 1 9 9 5 年，r e y n o l d s 等和c h u n g 、r e y n o l d s 成功地将文化算法用于全局最优化问题 并取得了很好的实验结果【4 】。c h u n g 矛e i r e y n o l d s 使用了一种将进化规划( e v o l u t i o n a r y p r o g r a m m i n g ，简称e p ) 和g e n o c o p 相结合的混合结构，并用区间约束网格( i n t e r v a l c o n s t r a i n t n e t w o r k ) 来表示问题的约束条件，当个体满足所有的约束条件时，就称为 “可接受的”( a c c e p t a b l e ) ，否则，调整信念空间中与约束有关的区间。这种方法通 过将一个不可行解的基因替换成一个介于上边界和下边界的值的方法将其变为可行 解。g e n o c o p 假设搜索空间是一个凸空间，因此在设计确定搜索方向的算子时相对 容易一些。 1 9 9 7 年，r e v n o l d s 将文化算法成功应用于大规模时空数据库的数据挖掘【6 ，。同 年，r e y n o l d s 对进化规划中的自适应使用文化算法的框架【6 j ，并用来解决函数优化问 题，结果证明比自适应e p 在性能上有很大提高。特别是使用知识引导e p 中的变异算 子，不仅提高了效率，也提高了精确度。知识空间的知识对变异操作的影响有两种 方式：一是决定步长；二是决定变化的方向。根据知识空间知识的不同种类和影响， 变异操作的方式有四种文化e p 版本。在大多数情况下，使用n s d 髓。, 产生较好的性能： 4 第一章绪论 ( 1 ) c a e p ( n s ) ：对种群空间的个体仅使用标准化知识决定变异的步长； ( 2 ) c a e p ( n s + s d ) ：使用标准化知识决定变异的步长，并使用形势知识决定变异方 向； ( 3 ) c a e p ( n s d ) ：只使用标准化知识决定变异的步长和方向； ( 4 ) c a e p ( s d ) ：使用形势知识决定变异的方向。 r e y n o l d s 币l c h u n gc h a nj i n 在文化算法中使用模糊的方法。种群空间使用进化规 划的方法，知识空间使用标准化知识和形势知识，而接受功能的评价使用模糊推理 引擎。研究表明，有两种基本种类的信息对指导个体选择非常有效：一种是世代数， 另一种是当前群体的性能。这里用个体的成功率以及当前的世代数作为模糊推理引 擎的输入，从而决定可接收的个体数。通过3 4 个函数实例的测试证明，使用模糊接 受函数比使用其他函数为接受函数令c a e p 的性能有更大提高，并且模糊接受函数结 合c a e p 洲s d ) 能产生最优效果。但与c a e p ( n s ) 矛i c a e p ( n s + s d ) 的结合效果一般。 1 9 9 8 年，r e y n o l d s 和a 1 s h e h r i 使用以文化算法为框架的进化规划指导决策树 7 1 ， 在种群空间使用进化规划方法，产生变量的候选子集作为i t i 的输入，并且提取概括 社会种群空间中成功子集的性质存储在知识空间，这些知识用于指导在下一世代中 产生新的选择子集。在大型时空数据库中挖掘的结果证明，i t i 不能在任何环境下都 产生最优树。当数据较小时，i t i 方法和使用文化算法指导i t i 的方法都能产生最优树； 当数据复杂时，后者比前者能产生更加稳定精确的树，并且树的节点减少，不仅容 易理解，而且包含重要信息变量的含量更高。 1 9 9 9 年，j i n 和r e y n o l d s 提出了一种在信念空间中采用，2 维地形图( r e g i o n a l b a s e d s c h e m a t a ) 9 】，也称为信念单元( b e l i e f - c e l l ) ，在种群空间中采用进化规划的文化算法来 求解非线性约束问题。信念空间通过删除不可行解，增强对搜索空间中有望得到最 优解的区域的开发来指导整个搜索过程。关键的问题是如何表示、保存与问题有关 的知识。j i n 和r e y n o l d s 的方法是构造一张搜索空间的地图，这种方法类似于确定机 器人移动方向的“d i v i d e a n d - l a b e l ”方法。在构造该地图时，主要利用评价个体时 所获取的知识，利用该地图我们可以获取到指导进化算法搜索过程的规则，从而更 有效地避开不可行区域，充分开发可行区域。 2 0 0 0 年，s a l e e m 同样使用进化规划作为文化算法的种群空间来求解动态环境优 化问题【1 0 , 1 1 】。并对文化算法和自适应e p 的性能进行了比较，显示出文化算法在所有 的实验中性能优于自适应e p 。 5 文化算法及其在优化调度中的直用研究 2 0 0 1 年，r e y n o l d s 和z h us h i n i n 使用完全模糊文化算法解决非线性实值函数优化 问题【1 2 】，即在文化算法的每个部分都使用模糊数学模型。使用模糊接受函数能伎系 统有较高的成功率，并且单独使用模糊接受函数比单独使用模糊知识空间和模糊影 响函数有更大的性能改善。模糊使得知识获取过程更灵活，这种文化框架在解决特 定问题上比其他文化框架更出色。 2 0 0 3 年，r i c a r d ol a n d ab e c e r r a $ l l c a r l o sa c o e l l oc o e l l o 首次提出用文化算法来 求解多目标优化问题【1 3 】，并取得了不错的结果。 s t e r b e r g 将文化算法用于a a a 汽车保险公司保险索赔的欺骗检测【l4 】，目的是降 低欺骗检测专家系统的维护成本。系统的目标是确定欺骗索赔、非欺骗索赔的特征。 基于规则的欺骗检测专家集成于文化算法的框架内为索赔评估提供必要信息。 2 0 0 6 年，r e y n o l d s 等使用文化算法的框架，使用比较流行的机器学习技术集成学 习到进化过程中【”】。集成学习天然适用于文化算法的框架，知识空间中的五种知识 源是文化算法框架中集成进化的依据。实验证明，这种方法在优化应用方面有优势。 对于文化算法，国内研究方兴未艾。2 0 0 5 年，杜琼等【16 j 首次对文化算法进行了 很详尽的阐述，讲述了该算法的基本原理和不同版本，并给出了一些成功应用的实 例。杨海英等将文化算法应用到对服务器性能权值的进化计算中，通过评价服务器 的负载状况，获得优化的性能权值，并自适应地转换到集群的分配器中，使事务在 集群系统中得到合理分配。 2 0 0 6 年，刘纯青等提出了基于文化算法的新聚类算法【1 7 】，并给出该算法的两个 实现版本：c a v e r s i o n l 利用规范知识调整变量变化步长，形势知识调整其变化方向； c a v e r s i o n 2 矛1 用规范知识调整变量变化步长及变化方向，并通过实验证明了这两个 版本的文化算法均能有效地克服传统的k 一均值算法的缺点，而且全局收敛性能优于 基于遗传算法的k 一均值聚类算法，而且第二个版本的文化算法更适于求解聚类问题。 2 0 0 7 年，黄海燕等【1 8 】提出一种基于多层信念空间的文化算法，并用于求解约束 优化问题。 2 0 0 7 年王奕首等【1 9 1 提出了文化粒子群优化算法，该算法模型将p s o 纳入文化算 法框架，组成基于p s o 的种群空间和信念空间，两空间群体能独立并行进化。 下层 主种群空间定期贡献精英个体给上层知识空间，上层知识空间经演化后，定期贡献 精英个体给下层主种群空间，于是形成“双演化双促进机制，从而实现增) j n p s o 的群体多样性在以卫星舱和印刷电路板布局设计为背景的算例中进行了数值验证， 结果表明对于该算例，该方法的计算精度和计算效率比g a 算法、p s o 算法高。 6 第一章绪论 艾景波【2 0 】将文化粒子群算法应用于布局设计问题，并以卫星舱布局和集成电路 设计为应用背景，验证了算法的可行性和有效性。 2 0 0 8 年张颖【2 1 1 首次将文化算法应用到经济领域的投资组合问题中。针对非线性 投资组合模型设计了基于投资组合模型的文化算法实现步骤并进行仿真实验，经过 实际数值运算，得到了良好的效果，这也说明应用文化算法求解模型具有实际有效 性，可以为不同风险偏好的投资者提供明确的投资决策。 目前对于文化算法的研究还没有形成系统的分析方法和一定的数学基础，有很 多问题还需要进一步研究： ( 1 ) 并行计算方面。并行化研究可以为其拓展更广阔的应用领域。 ( 2 ) 空间参数设计与选择。 ( 3 ) 算法的基础理论研究。文化算法很大程度上依赖于问题知识的表达、提取 与演化。对于如何将知识有效的在计算机中进行获取与处理，一直是人工智能领域 的一项难题。因此人工智能等相关领域的发展会带动文化算法基础理论研究的发展。 ( 4 ) 算法计算复杂度的研究。 ( 5 ) 文化算法在各种生产调度问题中的具体应用，相关算法与模型。现在文化 算法在生产调度的应用在国内研究较少。 1 2 2 生产调度优化问题的发展及现状 生产调度优化问题在实际生产计划中非常普遍，也是典型的n p h a r d 问题，其研 究具有重要的理论意义和工程价值，科学制定生产调度方案对提高企业生产效率起 着至关重要的作用。因此，车间作业调度一直是生产及组合优化等领域研究的热点之 一。生产调度传统精确的方法，如枚举法、分支定界法、动态规划法等，由于计算 量大，仅适合小规模问题，对较大规模的生产调度问题将无能为力，而且，解决生 产调度问题的经济性要求也不允许用这类方法来求解。 流水车间( f l o ws h o p ) 作业调度问题，也被称为同序作业调度问题，使许多实 际流水线生产调度问题的简化模型。它无论是在离散制造工业还是在流程工业中多 具有广泛的应用。因此对这些企业而言，研究和解决好调度问题无疑能提高他们的 生产效率，从而提高这些企业的竞争力。因此对此类问题的研究具有极高的理论价 值和实用价值。 尽管相对j o bs h o p 调度问题而言，f l o ws h o p 调度问题的工艺约束比较简单，但 它仍旧是一个非常复杂和困难的组合最优化问题，其n p h a r d 的特性和强大的工程背 7 文化算法及其在优化调度中的声用研究 景一直成为理论界和工程领域研究的热点问题。 自从j o h n s o n1 9 5 4 年发表了第一篇关于f l o ws h o p 调度问题的文章以来，f l o w s h o p 调度问题引起了许多学者的关注，提出了许多解决的方法，整数规划和分枝定 界法是寻求最优解的常用方法，但f l o ws h o p 调度问题是n p 完全问题，对一些大规模 甚至中等规模的问题，整数规划和分枝定界法不是很有效。因此又相继提出一些启 发式方法，如遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、人工免疫算法、 神经网络算法等。 d a v i s 2 3 】首次将遗传算法( g a ) 用于解决调度问题。它将问题的求解表示成染色 体的适者生存过程，通过染色体群的不断进化，包括选择、交叉和变异等操作，最 终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 苏子林【2 4 】提出了采用海明距离的概念对种群进行修正，在进化过程中，不断淘 汰较差的个体，不断引入修正种群，保持了种群的多样性。 李钢等【2 5 】提出的是混合的遗传算法，通过与其它算法的结合弥补在局部搜索和 早熟方面的缺陷。 许晓栋等【2 6 】提出一种基于免疫原理的遗传算法。当前使用的编码方法主要有9 种，研究者们通过对遗传算子进行设计来不断改进。g a 原理和操作简单，通用性强， 不受限制性条件的约束，且具有隐含并行性和全局解空间搜索能力，但g a 的早熟和 搜索效率低问题是它的主要缺陷。 赵良辉等【2 7 1 对模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m s ，简称s a ) 进行了改 进，提出了记忆回火和快速退火的模拟退火算法，分别适合于求解精度要求较高的调 度和大规模的调度，同时还与遗传算法相结合组成遗传退火算法。但如果要得到一 个高质量的近似解，需要花很长时间进行退火，s a 能较好地避免局部最优，但算法 的收敛速度很慢，搜索空间过于庞大下降温度难以掌握。这成为进一步应用的阻力。 b a r n e s 等对禁忌算法( t a b us e a r c h ，简称t s ) 的作了改进【2 8 】【2 9 l ，并用该算法求解 j o bs h o p 生产调度问题。禁忌搜索是一个效率较好的启发式算法，它能找到调度问 题不少算例的最优解。但禁忌搜索要面对很多的问题，如初始解问题、邻域结构问 题、搜索策略和禁忌表的长度问题等等。 2 0 0 8 年张慧霞等提出求解作业车间调度同题的新的混合粒子群优化算法【3 ，通 过评价粒子聚焦的程度，从而引入差异演化变异机制，增加了粒子群的多样性，改 善了搜索全局最优解的能力。 8 第一章绪论 1 3 本文的主要工作 本文主要工作如下： 1 在查阅大量文献资料的基础上，对文化算法的来源、基本原理、机制、特点及 应用等进行了系统研究和详细阐述。 2 提出了一种基于进化规划的文化算法，该算法采用进化规划为文化算法的种 群空间提供种群，种群空间在进化过程中定期组织群个体向信念空间提供的种群最 优个体学习，从而充分利用了优秀个体所包含的特征信息，在很大程度上提高了收 敛速度。 3 提出一种基于文化算法和改进差分进化算法的混合优化算法，该算法将改进 差分进化算法引入种群空间的进化操作，从而实现改进差分进化算法在进化过程中 知识的动态获取和知识对改进差分进化种群空间进化的有效指导，保证了种群的多 样性和收敛速度，并减少计算量。 4 用b e n c h m a r k 函数对上述两种优化算法进行仿真，试验结果表明两种算法均优 于传统的优化算法。 5 用c a e p 和c a m d e 算法求解丁烯烷化生产过程的约束优化问题，并用c a m d e 算法求解f l o ws h o p 调度优化问题。经仿真测试，两种算法都具有很好的搜索性能， 同时证实了文化算法求解生产调度问题的可行性。 1 4 小结 这一章主要介绍了课题研究的背景和意义、目前文化算法和f l o ws h o p 生产调度 优化问题的国内外研究现状以及本文所做的主要工作。 9 第二章文化算法简介 第二章文化算法简介 2 1 文化算法的起源 随着时间的迁移人类在进化过程中渐渐掌握了提取，编码，和传播信息知识的 能力，这种能力是区别其他物种人类所特有的能力。正是这种能力使人类形成，积 累和传递经验，可以加快和指导发展的速度和方向。人类进化是以文化进化为其主 要特征的。这种特征是人类之外的所有动物所不具有的一个十分重要的进化特征。 因此在人类的进化( 特别是当代人类的进化) 过程中，生物进化并不是起主导作用， 而只有文化进化才能说明这一切，人类的进化集中反映在文化进化上。 对文化进化的研究以英国人类学家泰勒发表的原始文化为标志，文化进化 论的诞生已有一百多年的历史了，在这期间文化进化论存在多种争论的学派。早期 受达尔文生物进化论的影响，一些人类学家用进化论的观点来探讨诸如社会的起源 文化的发展等问题，从而形成了所谓的古典文化进化论。其主要代表人物是哲学家 斯宾塞、文化学家摩尔根和人类学家泰勒，他们主张文化的单线进化论，认为所有 的社会和文化形态都要按同样次序进化，每个阶段都有普遍性特征。但是古典文化 进化论具有浓厚的生物进化论色彩，而且对许多现象又不能做出合理的解释，因此 受到了许多人类学家的批判。在这批判的过程中，逐步形成了文化相对论。文化相 对论的形成是以美国人类学家梅尔维尔赫斯科维茨发表人类及其创造为标志， 其主要代表人物包括德国的社会学家韦伯、哲学家斯宾格勒、英国历史学家汤因比 和美国人类学家本尼迪克特等。该学派认为，文化发展是多元的，批判进化论的单 线论，提出文化模式理论等，并认为绝对的、普遍的价值标准是不存在的，没有哪 一种文化模式比另一种更优，多种文化模式相互作用、相互影响而共同发展。与此 同时，对文化相对论的评判也逐步形成，这就是新文化进化。 人们由达尔文生物进化得到启迪，提出了进化计算理论一较之生物进化。文化进 化以其特有的机制和特征推动着人类社会以日益倍增的速度向前发展，以至于达到 今天这种高度发达的社会。显然，在文化进化过程中同样存在着非常重要的进化机 制，这种进化机制必然有其非常有效的成分。 研究表明，文化能使种群以一定的速度进化和适应环境，而这个速度是超越单 1 】 文化算法及其在优化调度中的应用研究 纯依靠基因遗传生物进化速度的。种群在进化过程中，个体知识的积累以及种群内 部知识的交流在另外一个层面促进群体的进化，受这些思想的启发，r e y n o l d s 于1 9 9 4 年提出文化算法( c a ) ，近年来引起国外众多学者关注，目前国内研究较少。文化算 法是从文化进化过程抽取出来的一个新的进化计算框架，由种群空间和信念空间两 大部分组成，其重要思想就在于从进化的种群中获取待解决问题的经验知识，并反 馈这些经验知识来指导搜索过程，从而提高搜索效率。 2 2 文化算法的介绍 文化算法是一个多进化过程的算法，它分别从微观和宏观不同层次上进行进化。 微观上主要是种群间和种群内部的进化；而宏观上是指它具有一个信念空间，在这 一层上的进化就是指信念空间的进化。也就是说文化算法是一个双层进化系统，它 包含两个进化空间：一个是由具体个体组成的种群空间，另一个是由在进化过程中 获取的经验和知识组成的信念空间。种群空间和信念空间之间有一通讯渠道，两者 之间就是通过通讯渠道相互作用的，从而相互指导达到共同进化的目的。 为了求解各种优化问题，人们已经发展了各种各样的优化算法，如神经网络算 法、遗传算法( g a ) 、蚁群算法( a n tc o l o n ya l g o r i t h m ，简称a c a ) 、粒子群法p s o ) 、 禁忌搜索法( t s ) 、差分进化法( d i f f e r e n t i a le v o l u t i o n ，简称d e ) 、模拟退火( s a ) 等等。 其它进化算法相比文化算法具有下面的特点： ( 1 ) 双重进化结构( 种群空间和知识空间) ； ( 2 ) 用信念空间中保存的知识来指导种群空间进化； ( 3 ) 支持种群和信念空间的分层结构； ( 4 ) 在不同层次上支持自适应； ( 5 ) 不同层次上以不同速度进行进化； ( 6 ) 支持混合求解问题； ( 7 ) 在一个计算框架内可以有多个不同的“文化”变化模型。 应用文化算法求解问题包括： ( 1 ) 有比较多领域知识的问题( 约束优化问题) ： ( 2 ) 在种群空间和信念空间上以不同速率发生自适应的复杂系统； ( 3 ) 知识形态不同，并且推导方式不同； ( 4 ) 搜索和基于框架知识相结合的混合系统； ( 5 ) 需要多个种群空间和多个信念空间的问题； 12 第二章文化算法简介 ( 6 ) 分层结构问题环境，有种群空间和信念空间分层结构的问题。 2 3 文化算法的基本理论 2 3 1 文化算法的基本框架 文化算法用于建立进化模型，这一进化模型是一个进化计算系统中的文化组成 部分，随着时间的推移它不断积累个体( 或是种群) 解决给定问题的经验和行为。 它的主要思想就是：种群空间是由给定问题的解集构成，它可以用基于种群的任何 计算模型来进行自身的进化，( 例如：遗传算法、进化规划) ，信念空间是个体用来 存储行为和经验的知识库，种群空间中的个体在整个搜索过程中学习这些知识，个 体的经验和行为可以修改储存在信念空间的知识，同样，知识也可以指导种群中个 体的进化。所以，用文化算法解决全局优化问题，就是利用可