（化学工程专业论文）基于正态分布的连续多蚁群算法及其化工应用.pdf

浙江犬学硕 学位论文 摘要 进入2 l 世纪以来，化学工业面临着经济、能源、环境以及社会等多方面的 挑战，优化技术是迎接这些挑战的有效手段，能够应用于化工全价值链的各个 环节。化工系统是一类典型的复杂系统，随着目标问题的规模越来越大，模型 结构也越来越复杂，经典的优化方法已显乏力，对高效的智能化的优化技术的 需求日益迫切。 蚁群算法是新近提出来的一种群智能优化方法。由于其优越的问题分布式 求解模式，在离散优化问题的求解中取得了极大成功，引起了相关领域学者的 广泛关注。但很多实际问题通常被表达成连续优化问题。如何有效地将全局优 化性能优越但本质离散的蚁群算法用于优化连续空间的问题，此为亟待应对的 挑战，这也是本文的主要研究内容。 蚁群算法在本质是一种基于解空间参数化的概率分布模型的搜索算法框 架，这些参数就是信息素，而蚂蚁生成的解集合则可看作是用来更新概率分布 参数的样本。因此信息素分布模型是影响蚁群算法最关键的因素，它决定了蚂 蚁的行为与分布，设计一种好的信息素分布模型是构造高性能连续蚁群算法的 关键。 基于此，本文通过对蚁群觅食的生物学模型中信息素分布的分析，用多元 正态分布函数来模拟信息素的分布，提出了一种信息素呈多元正态分布的连续 多蚁群算法( c m a c 0 ) 。该算法通过对信息素分布函数的随机抽样来指导蚂蚁 完成状态转移，信息素分布函数又随着蚂蚁的移动而被调整，实施信息素更新， 进而引导蚂蚁在可行域中逐步向最优食物源聚集。为了提高算法的寻优性能， 基于蚁群的成群募集机制，本文构建出多蚁群策略来有效地调配蚁群的行为以 平衡其全局探索能力和局部挖掘能力。经多个经典函数的测试，表明c m a c o 适用于连续优化问题，具有良好的全局寻优性能。 对于终端时间给定、终端状态无约束的动态优化问题，本文通过控制变量 参数化方法将其转换成静态优化问题，然后使用c m a c o 进行优化。按照该思 一卜一 浙江大学颂t 学位论文 路，将c m a c o 用于生产分泌蛋白的p a r k - r a m i r e z 生物反应器以及生产外源蛋 白的l e e g a m i r c z 生物反应器的补料流率优化问题。结果表明，c m a c o 在优 化结果和计算代价上都有较好的性能。 复杂相平衡体系的g i b b s 自由能函数存在多个局部解，应用局部优化算法 易陷入局部解或者平凡解而难以得到全局解。本文采用c m a c o 直接最小化系 统g i b b s 自由能函数，无需考虑体系实际存在的相态，计算不依赖函数导数， 能以较高概率收敛至全局解。 总之，论文对蚁群算法做了较为全面深入的分析和讨论，不仅提出了一种 连续多蚁群算法，而且将其用于化工动态优化以及相平衡计算中。论文最后对 所做工作进行了总结，并且对未来研究提出展望。 关键词：蚁群优化，信息素模型，化工过程，随机优化算法，连续优化，全局 优化，动态优化，正态分布，流加式生物反应器，相平衡 一i i 浙江大学硕l 学位论文 a b s t r a c t s i n c ee n t e r i n gt h e2 1 s tc e n t u r y , c h e m i c a li n d u s t r yi sf a c e dw i t hp r e s s u r e sf r o m e c o n o m i c ，e n e r g y , e n v i r o n m e n ta n dm a n yo t h e rp r o b l e m s o p t i m i z a t i o nt e c h n i q u e t o m e e tt h e s ec h a l l e n g e si sa l le f f e c t i v ea p p r o a c h , w h i c hc a nb ea p p l i e do na n ys c a l e s o ft h ee n t i r ev a l u ec h a i ni nc h e m i c a li n d u s t r y b u tc h e m i c a ls y s t e mi sat y p i c a l c o m p l e xs y s t e m a st h es c a l eo fo b j e c tp r o b l e mb e c o m e sm o r ea n dm o r el a r g e ，o f w h i c ht h em o d e ls t r u c t u r eb e c o m e sm o r ea n dm o r ec o m p l i c a t e dt o o ，c l a s s i c a l o p t i m i z a t i o nm e t h o dc a l l tm e e tt h ed e m a n d so fm a n yp r a c t i c a lp r o b l e m s s ot h e r e q m r e m e m f o rr i g h te f f i c i e n t i n t e l l i g e n to p t i m i z a t i o n m e t h o d sh a sb e c o m e i n c r e a s i n 舀yu r g e n t a n tc o l o n yo p t i m i z a t i o n ( a c o ) i sr e c e n t l yp r o p o s e da sac l a s so fi n t e l l i g e n t o p t i m i z a t i o nm e t h o d s i t sp r e d o m i n a n td i s t r i b u t e dp a t t e r no fp r o b l e ms o l v i n g a c h i e v e sg r e a ts u c c e s si nc o m b i n a t i o n a lp r o b l e m s ，a n db r i n g se x t e n s i v e l ya t t e n t i o n s o fr e l a t e dr e s e a r c ha r e a b u tt om a n yp r a c t i c a le n g i n e e r i n gp r o b l e m s ，t h e ya r e u s u a l l ye x p r e s s e da sc o n t i n u o u so p t i m i z a t i o np r o b l e m s s o ，i ti s a ni m p e r a t i v e c h a l l e n g eo nh o w t oa p p l yt h eb a s i ca n tc o l o n yo p t i m i z a t i o ns t r a t e g yt ot h ep r o b l e m s s o l v i n gi nc o n t i n u o u ss p a c e ，w h i c h i st h em a j o rw o r ko f t h i st h e s i s i nn a t u r e ，a n tc o l o n yo p t i m i z a t i o ni sau n i f i e d a r c h i n ga l g o r i t h mf r a m e w o r k b a s e do nt h ep r o b a b i l i t yd i s t r i b u t i o nm o d e lo fs o l u t i o ns p a c ep a r a m e t e r i z a t i o n ，t h e p a r a m e t e ri sp h e r o m o n e ，a n dt h es o l u t i o ns e tp r o d u c i n gb ya n t sc a nb ec o n s i d e r e da s t h es a m p l e sf o ru p d a t i n gt h ep r o b a b i l i t yd i s t r i b u t i o np a r a m e t e r h e n c e ，t h em o d e lo f p h e r o m o n e d i s t r i b u t i o ni st h ek e yf a c t o ri na n tc o l o n ya l g o r i t h m , w h i c hc a n t h o r o u g h l yd e t e r m i n et h eb e h a v i o ra n dd i s t r i b u t i o no fa n t s t h e r e f o r e ，t h ek e y i s s u e f o rc o n s t r u c t i n gh i g h - p e r f o m m c ec o n t i n u o u sa n tc o l o n yo p t i m i z a t i o ni st od e s i g n r e a s o n a b l ep h e r o m o n ed i s t r i b u t i o nm o d e l a n a l y z i n gt h ep h e r o m o n ed i s t r i b u t i o n i nb i o l o g i c a lm o d e lo fa n tc o l o n y f o r a g i n g , w eu s en o r m a ld i s t r i b u t i o nt o s i m u l a t e p h e r o m o n ed i s t r i b u t i o n a n d i i i - - 浙江大学硕 学位论文 p r o p o s e dan o r m a ld i s t r i b u t i o no fp h e r o m o n eb a s e dc o n t i n u o u sm u l t ia n t c o l o n y a l g o r i t h m ，c m a c o f i r s t l y , s t a t e t r a n s i t i o no fa n tc o l o n yi s i m p l e m e n t e db y s t o c h a s t i c s a m p l i n gb a s e do np h e r o m o n ed i s t r i b u t i o nf i l n c t i o n s e c o n d l y t h e d i s t r i b u t i o nf u n c t i o ni su p d a t e da c c o r d i n gt ot h eq u a l i t yo f f o o ds o u r c e ，b yw h i c ht h e p h e r o m o n ei su p d a t e d t h ei t e r a t i v ei m p l e m e n t a t i o nc a nl e a dt h ea n t st og l o b a l o p t i m a ls o l u t i o n m o r e o v e r , t oi m p r o v eo p t i m i z a t i o np e r f o r m a n c e ，m u l t i - c o l o n i e s s t r a t e g yi si n t r o d u c e dt ob a l a n c et h ew a d e - o f fb e t w e e ng l o b a le x p l o r a t i o na n dl o c a l e x p l o i t a t i o na b i l i t yb a s e do ng r o u pr e c r u i t m e n tm e c h a n i s m f i n a l l y , c m a c ow a s a p p l i e dt os e v e r a lb e n c h m a r kp r o b l e m s ，a n dt h er e s u l t si l l u s t r a t ec m a c o h a sw e l l g l o b a lo p t i m i z a t i o np e r f o r m a n c e t os o l v e d y n a m i co p t i m i z a t i o np r o b l e m se f f i c i e n t l y , c o n t r o l v e c t o r p a r a m e t e r i z a t i o na p p r o a c h i si n t r o d u c e dt ot r a n s f o r mt h eo r i g i n a l d y n a m i c o p t i m i z a t i o nt os t a t i co p t i m i z a t i o np r o b l e m s ，w h i c hi sd i r e c t l ys o l v e db yc m a c o t h ee f f i c i e n c yo ft h i sm e t h o dw a si l l u s t r a t e d 、丽t l lt w oc h a l l e n g i n gp r o b l e m sf o r o p t i m i z i n gf e e d - r a t eo ff e d b a t c hb i o r e a c t o r s ，a n dt h er e s u l t ss h o wc m a c o h a s w e l lg l o b a lo p t i m i z a t i o na b i l i t ya n df a s tc o n v e r g e n c es p e e d f o rc o m p l e xp h a s ee q u i l i b r i u ms y s t e m ，t h eg i b b se n e r g yf u n c t i o nh a ss e v e r a l l o c a lm i n i m a , s oi t sd i f f i c u l tt og e tt h eg l o b a lm i n i m u mb yt h el o c a lo p t i m i z a t i o n a l g o r i t h m s c m a c ow a su t i l i z e dt os o l v et h ep h a s ee q u i l i b r i u mw i t h o u tl e a c t i o n s ， a n di tn e e dn o tc o n s i d e r i n gt h ea c t u a ln u m b e ra n dt y p eo fp h a s e sa n dn c e d n tt h e d e r i v a t i v e t h er e s u l t ss h o wc m a c oc a nf i n dt h eg l o b a ls o l u t i o nw i ml l i 曲 p r o b a b i l i t y i ns h 吼a c ow a sa d a p t e de l a b o m t e l yf o rc o n t i n u o u so p t i m i z a t i o ni nt h i sw o r k , a n dp r o p o s e dan o r m a ld i s t r i b u t i o nb a s e dc o n t i n u o u sm u l t ia n t - c o l o n yo p t i m i z a t i o n , w h i c hw a sa p p l i e do nd y n a m i co p t i m i z a t i o np r o b l e m so fc h e m i c a lp r o c e s s e sa n d c o m p l e xp h a s ee q u i l i b r i u mc a l c u l a t i o n k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n , p h e r o m o n em o d e l ，c h e m i c a lp r o c e s s e s ， s t o c h a s t i co p t i m i z a t i o na l g o r i t h m , c o n t i n u o u so p t i m i z a t i o n , g l o b a lo p t i m i z a t i o n , d y n a m i co p t i m i z a t i o n , n o r m a ld i s t r i b u t i o n , f e d - b a t c hb i o m a c t o r , p h a s ee q u i l i b r i u m 一一 浙江大学硕士学位论文 第1 章绪论 2 0 世纪是化学工业蓬勃发展并对人类文明进程产生重大影响的一百年0 , 2 1 ： 合成氨化肥工业的兴起是世界粮食产量增产的主要原因；催化裂解技术的出现创 造了石油化工的辉煌；各种抗生素和新药的发明延长了人类的平均寿命。进入 2 1 世纪，化学工业面临着来自经济、能源、环境以及社会等多方面的挑战，具 体表现在：由于信息技术的高度发展和经济全球化趋势的加速，化工企业正朝着 数字化、网络化过渡，以制造过程为核心的计算机集成制造系统正朝着全价值链 的自动化和优化方向发展；大宗化学品的赢利空间持续下降，迫使化学工业转向 精细化工，生产方式也正朝着个性化定制模式转变；可持续发展已经成为时代主 题，这将促使化工企业由单纯追求利润最大化转向节约资源，开发环境友好的过 程、产品以及兼顾经济效益的多目标追求，“绿色化工”应运而生【3 】。 为了迎接这些挑战，化学工业势必更加依赖于过程系统工程( 或称为化工过 程系统工程 4 1 ) 的发展，从化工系统的整体目标出发，充分利用系统工程、化学 工程、过程控制、计算数学、信息技术等学科的研究成果，达到系统最优设计、 最优控制和最优管理的目标，从而满足来自社会、环境以及企业的可持续发展要 求。过程系统工程的基础是模拟，但其核心内容为过程系统的最优化 5 1 。一个系 统只有通过设计上的最优化和操作上的最优化，才能充分发挥它的产品增值的特 性，才能在经济全球化的激烈竞争中处于不败之地。因此，研究化工过程优化技 术具有重要的现实意义。 本文在这方面作了初步的探索，提出了一种基于信息素正态分布的连续多蚁 群算法，并将其用到化工动态优化以及复杂相平衡计算中。在本章中将阐述本文 的研究基础和研究背景：首先概述了化工过程优化；然后综述了最优化问题和最 优化方法，其中重点介绍现代启发式算法，接着评述了蚁群算法在化工过程优化 中的应用，最后给出用于测试算法的标准测试函数以及全文结构。 浙江大学硕t 学位论文 1 1 化工过程优化 化工过程优化就是在化工过程性能、特点所给定的约束条件下，找出使过程 系统的性能指标( p e r f o r m a n c ei n d e x ) 或称目标函数( o b j e c t i v ef u n c t i o n ) 达到最 大( 或最小) 的设备参数或工艺变量【6 】。一般而言，其体现在以下几个方面【7 母】：数 学模型中的待定参数的优化、过程运行工艺条件的优化、工艺输入变量和其它参 数的优化、动态系统的最优控制、过程体系结构变量的优化以及生产计划的优化 等。无论是以上哪一方面的问题，都包含了三个要素：目标函数、决策变量和约 束条件。 这三个要素的确定过程也就是过程优化问题的确立过程，其步骤如下【3 ，9 l ： ( 1 ) 分析问题对过程本身进行分析，建立全部变量的列表。 ( 2 ) 建立优化数学模型确定和选择决策变量，建立目标函数和约束条件 的数学模型。 ( 3 ) 模型的分解和简化若优化问题模型过大，可依据工程经验或过程模 拟分析，将优化模型进行分解或者简化。 ( 4 ) 求解优化问题根据工程实际的需要、计算工具的性能、数学模型的 状况确定计算要求的精度和终止条件，选择合适的最优化方法，求解 优化问题。 ( 5 ) 优化结果分析根据最优目标值和最优解，采用工程技术知识分析最 优值和最优解的合理性和可行性。 ( 6 ) 优化结果的验证对于一些大型和复杂的问题，还应进行灵敏度分析， 实施过程中进行必要的监控，实旌后进行验证和分析，以保证最优化 效果的实现。 在化工过程优化中，没有一种通用的最优化方法适合于所有的过程优化问 题。需要根据优化问题的目标函数、约束条件的特点以及决策变量和状态变量的 数目来选择优化方法。由于化工过程通常结构复杂，包含的变量维数多，约束条 件也较为严格，其优化计算十分费事。并且，现代化工技术呈现出了以下几个特 点 7 1 ：为了追求规模效益，单个装置的产量日益扩大；为了适应市场多样化需求， 在同一工厂内，利用少数几种通用设备，经过不同的组合，并使用不同的工艺条 件，生产多种产品；随着理论和经验知识的积累，更加重视生产条件和操作条件 - - 2 浙江大学硕士学位论文 的优化；过程的自动化程度不断提高。 这些特点对化工过程技术提出了挑战：越来越需要更准确的定量描述化工过 程各影响因素与生产结果间的依赖关系；需要包括尽可能多的变量以对化工过程 的行为做出更加全面的分析；希望对不同的原料和不同的操作条件下作更为细致 的研究。因此，现代化工过程通常较为复杂，具有：规模大、范围大、变量多、 约束条件多，系统结构复杂，系统的目标和功能多样，影响因素多，数学模型难 于建立或较为复杂，模型求解困难等复杂系统的所有特征。 正是由于这些特征，化工过程实现最优化的困难很大，对现有的优化算法提 出了极大的挑战i l o 】。鉴于此，本文将以化工过程作为应用背景，对有很好的全局 寻优能力的蚁群算法进行深入研究，对其进行连续化改造，以期获得一种更有效 的、通用的连续优化算法。 1 2 最优化问题 最优化问题的一般形式为： = 2 - ， 其中x = ( 而，x ：，) 7 r ”是决策变量，厂( x ) 为目标函数，d c r ”为约束 条件所限制的可行域。特别地，如果可行域d = r ”，则最优化问题1 1 称为无约 束最优化问题。对于以m a x f ( x ) 形式出现的最优化问题可以通过n f l n f c x ) 的形 式来进行求解。 最优化问题通常可分为连续优化问题和离散优化问题两大类。离散优化问题 的对象是离散状态的解空间，而优化的对象是一定区间内的连续解空白j 。由于本 文主要研究连续多蚁群算法，并将其用于化工中的连续优化问题，因此下文仅介 绍连续优化中的若干问题。 定义1 1 若有矿d ”，其邻域为b = h 忙一x i i o l ，使得任意 x b c d ，均有厂( 妒) ，( x ) ，则称x 为问题1 1 的局部最优解。 定义1 2 若有矿d ”，使得任意工d ”，均有f ( x ) f ( x ) ，则称x 为问 题1 1 的全局最优解。 一3 一 浙江大学顾上学位论文 1 3 最优化方法 优化是个古老的课题，它所研究的问题是从所有可能的方案中选择最合理的 一种以达到最优目标口1 卜1 3 1 。早在1 7 世纪，英国n e w t o n 和德国l e i b n i t z 发明的 微积分就蕴含了优化的内容。而法国数学家c a u c h y 则首次采用最速梯度下降法 解决无约束优化问题，后来针对约束优化问题又提出了l a g r a n g e 乘数法【1 3 】。并 且1 9 4 7 年d a n t z i g 提出了求解一般线性规划的单纯形法，奠定了最优化技术作 为- j l 现代学科的基础【1 4 】。第二次世界大战后，由于经济、军事、科技等领域的 迫切需要推动了最优化技术的迅速发展，特别是运筹学、控制论、系统工程、计 算机技术等学科的研究成果，为其发展提供了理论上和手段上的基础条件。新的 优化方法不断问世的同时，最优化理论逐渐成熟，实际应用日益广泛，最优化已 成为一门十分活跃的学科。 近2 0 年来，优化领域出现了新的重大的变化，人工智能和人工生命技术为 优化领域注入了新的活力。一系列基于仿生思想、通过模拟自然现象的现代启发 式优化方法相继提出，在经典优化方法不能或者难以求解的复杂问题上取得了令 人瞩目的成就。 1 3 1 经典优化算法 经典优化方法根据问题性质的不同，通常将其分为线性规划、非线性规划以 及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，相应的有一些 较成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的 n e w t o n 法、共轭梯度法、序列二次规划法( s q p ) ，以及应用于整数规划问题的分 支定界法、割平面法和动态规划法等。这些方法一般有较严格的数学理论，但当 模型复杂的时候，如变量的维数多、约束方程数多、非线性强等，或模型结构复 杂，不能用显式的方程来表达时，这些方法往往不能进行有效求解，或者求解的 时间过长，如组合优化问题中的组合爆炸；或者求解的效果差，如陷入局部极值、 初始值直接影响寻优的结果【1 0 1 。 1 3 2 启发式算法 对优化算法的早期研究着重于问题的最优算法，通过最优算法求得问题每个 实例的最优解，它是问题求解的一种理想方法。然而，在求解实际问题时，最优 - - 4 - - 浙江大学硕上学位论文 算法的计算时自j 常常让人无法忍受，或者在求解较难的问题时计算时间随着问题 规模的增加以指数速度增加| 1 5 1 。鉴于此，2 0 世纪4 0 年代末期，人们提出了相对 于最优算法的启发式算法( h e u r i s t i ca l g o r i t h m ) 。刑文训等这样定义启发式算法： 启发式算法是一个基于直观或经验构造的算法，在可接受的计算耗费( 指计 算时间、占用空间等) 下给出待求解问题的一个可行解，该可行解与最优解的偏 离程度不一定事先可以预计。 并指出另一种定义：启发式算法是这样一种技术，这种技术使得在可接受的 计算耗费内去寻找最好的解，但不一定能保证所得到的解的可行性和最优性，甚 至在多数情况下，无法阐述所得到的解同最优解的近似程度。 上述两个定义同时强调了问题的求解必须是在可接受的计算耗费下，而没有 考虑算法所得到解与最优解的偏离程度。虽然早在1 9 4 8 年p o l y a 就发表了有影 响力的著作，但随着2 0 世纪6 0 7 0 年代对数学模型及最优解算法的重视，启发 式算法被称为“快速与丑陋( q u i c ka n dd i r t y ) ”的方法。直到2 0 世纪7 0 年代， 算法复杂性理论逐渐完善，不再强调一定要到达最优解，这促使了8 0 年代后现 代启发式优化算法的迅速发展。 1 4 现代启发式算法 2 0 世纪8 0 年代以来，人们通过模拟自然现象或过程，基于仿生的思想，提 出了一系列新颖的启发式优化算法- m e m - h e u r i s t i c ，有人称之为自然启发式算 法，直译为元启发式算法，文献中更多的将其称为现代启发式算法，在本文中将 用现代启发式算法来表述m e t a - h e u r i s t i e1 1 0 l 。现代启发式算法是一类随机搜索算 法，因其只需要适应度信息而无需问题其他特殊信息，以及算法表现出的高效的 全局优化性能等优点，为解决复杂问题的全局最优解提供了新的思路和手段，在 诸多领域得到广泛的关注和应用。 现代启发式算法包括进化算法、模拟退火、禁忌搜索、免疫算法、群智能优 化算法等。算法思想和内容涉及数学、物理学、生物进化、统计力学、人工智能 等。以自口通常将模拟退火、遗传算法、禁忌搜索以及人工神经网络统称为四大现 代启发式算法。随着新型算法的相继提出，现代启发式算法的范围也在不断扩大。 一5 一 浙江大学硕 学位论文 1 4 1 模拟退火 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 的思想来源于固体( 晶体) 的物理退 火过程。在物理上的退火过程中，一个固体首先被熔化，然后缓慢地冷却，随着 温度的降低，该物体最终获得处于最小能量状态的完美晶体结构。s a 把这个物 理过程转换为针对组合优化问题的搜索算法，它把问题的解集关联到物理系统的 状态上，把目标函数对应固体的物理能量，而最优解对应最小能量状态【1 6 l 。 按照热力学分子运动理论，粒子做无规则运动时，它具有的能量带有随机性。 温度较高时，系统的内能较大，但是对某个粒子而占，它所具有的能量可能较小。 因此，s a 算法要记录整个退火过程中出现的能量较小的点。其基本过程如下 1 0 l ： ( 1 ) 给定初始温度瓦及初始可行点，计算该处函数值f ( x 。) ； ( 2 ) 产生一随机可行点工，计算a f = f ( x ) 一厂( x 。) ； ( 3 ) 若a f 0 ，则接受可行点工作为下一次模拟的初始点； ( 4 ) 若鲈 o ，则计算接受概率：名叩( = e x p ( 一等) ，并以此概率接受 x 点作为新一轮模拟的初始点，否则放弃x 点，仍以作为初始点。 此即为m e t r o p o l i s 过程。按照一定的方式逐渐降低温度，重复m e t r o p o l i s 过 程，就构成了模拟退火优化算法。当系统的温度足够低时，认为达到了全局最优 状态。s a 的思想最早由m e t r o p o l i s 等于1 9 5 3 年提出，并且1 9 8 3 年k i r k p a t r i c k 等 将其用于组合优化。由于其良好的寻优性能，并且可以证明在某些条件下算法能 够收敛到一个最优解上，s a 受到广泛关注，并被用于大量不同类型的问题【”j 。 1 4 2 禁忌搜索 禁忌搜索( t a b us e a r c h ，t s ) 由g l o v e r ( 1 9 8 6 ) 提出1 1 7 1 ，其思想起源于对人 类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁忌准 则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多 样化的有效探索以最终实现全局优化。简单禁忌搜索算法的步骤可描述如下： ( 1 ) 给定算法参数，随机产生初始解，置禁忌表为空： ( 2 ) 判断算法终止条件是否满足? 若是，则结束运行并输出优化结果；否 则，继续以下步骤： - - 6 - - 浙江大学颂士学位论文 ( 3 ) 利用当i j 解x 的邻域函数产生其所有( 或若干) 邻域解，并从中确定 若干候选解； ( 4 ) 对候选解判断藐视准则是否满足? 若成立，则用满足藐视准则的最佳 状态y 替代x 成为新的当i i i 解，即f y ，并用与j ，对应的禁忌对象替换最早进入 禁忌表的禁忌对象，同时用j ，替换“b e s ts of a r ”状态，然后转步骤6 ；否则，继 续下一步骤； ( 5 ) 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对 应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的 禁忌对象元素； ( 6 ) 转步骤( 2 ) 。 迄今为止，t s 算法在组合优化、生产调度、机器学习、电路设计和神经网 络等领域取得了很大的成功，近年来又在函数全局优化方面得到了较多的研究， 得到了如活性t s ( r e a c t i v et s ) 等更具鲁棒性的算法变种。在理论研究方面，f a i g l e 和k e r n 提出了一个针对概率t s 的收敛性证明：h a n a f i 和g l o v e r 证明了几种确 定性版本的t s 隐式枚举了搜索空间，同样保证了在有限时间内找到最优解的可 能性。 1 4 3 进化计算 达尔文的生物进化学说告诉我们，自然界中丰富多彩的生物是自然选择和进 化的结果。虽然进化的结果非常复杂，但进化的过程却很简单：繁殖、变异、竞 争、选择。在自然界的启示下，一些学者希望通过模拟自然界的生物进化过程来 解决实际问题，这就导致了进化计算的诞生。进化计算是一种通用的问题求解方 法，它采用某种编码技术来表示问题的解的结构，每个这样的编码成为一个个体， 个体又称为染色体。算法维持一定数量的个体集合，称为种群。通过对种群中的 每个个体进行某些进化操作来模拟进化过程，最终获得一些具有较高性能指标的 个体。进化计算中常用的进化操作算子有选择、交叉和变异。其中选择是模拟自 然界的优胜劣汰过程，交叉是模拟有性生殖过程中的染色体交换过程，而变异是 模拟自然界中生物遗传物质的变异【1 8 l 。 进化计算的研究起源于2 0 世纪5 0 年代末，成熟于2 0 世纪8 0 年代。在2 0 世纪6 0 年代，h o l l a n d 提出的遗传算法、r e c h e n b e r g 和s c h w e f e l 提出的进化策 7 - - 浙江大学硕上学位论文 略以及f o g e l 提出的进化规划是进化算法的三大分支。这三种算法在利用进化机 制提高计算机求解问题能力的目标和基本思路上是一致的，但是在具体做法上则 有所区别，甚至对于一些基本问题的观点有根本上的分歧。 遗传算法强调染色体的操作，进化策略强调个体级的行为变化，而进化规划 在强调种群级上的行为变化。这三种算法是彼此独立发展起来的，可以用来解决 优化和机器学习等问题。 进化算法的两个主要特点是群体搜索策略及群体中个体之间的信息交换，其 优越性主要表现在：首先，进化算法有较好的全局寻优性能，能以很大的概率找 到全局最优解；其次，由于算法固有的并行性，进化算法非常适合于并行计算； 再者，进化算法采用自然进化原理的启发机制，能够在有限的时间内得到问题合 理的解；此外，算法的可扩展性好，且易于同其他技术混合等因素。进化算法已 经在最优化、机器学习和并行处理等领域得到了越来越广泛的应用。 1 4 3 1 遗传算法 进化计算中最广为人知是h o l l a n d 提出的遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 。 h o l l a n d 早期的工作集中在认知系统的研究，借助最优化方法获得学习规则，正 是这种需求推动了g a 的诞生【1 9 , 2 0 l 。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 m s ) ，书中h o l l a n d 为所有的适应系统建立了一种通用 理论框架，并展示了如何将自然界的进化过程应用到人工系统中去。 h o l l a n d 的遗传算法常被称为简单遗传算法( s g a ) ，s g a 的操作对象是一 群二进制串( 称为染色体、个体) ，即种群( p o p u l a t i o n ) 。这里每个染色体都对 应于问题的一个解。从初始种群出发，采用基于适应性比例的选择策略在当前种 群中选择个体，使用交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 来产生下一代种群。 如此一代一代进化下去，直到满足期望的终止条件。经过多年的发展，遗传算法 已经发展成为了一大类算法，这些算法使用了不同的染色体编码方法、不同的交 叉和变异算子，引入特殊算子，以及采用不同的再生和选择方法，他们与h o l l a n d 最初提出的算法应少有雷同之处。g a 在理论上和实际应用中都取得了很大的进 展b s - 2 0 l 。 一8 一 浙江大学硕b 学位论文 1 4 3 2 进化策略 在2 0 世纪6 0 年代初，柏林工业大学的lr e c h e n b e r g 和h p s c h w e f e l 等为 了对风洞试验设计中优化描述物体形状的参数提出了进化策略( e v o l u t i o n a r y s t r a t e g y ，e s ) 2 0 l 。e s 利用变异和重组操作，使搜索空自j 和策略参数空间的寻优 同时进行。 早期进化策略的种群中只包含一个个体，而且只使用变异操作。在每一进化 代，变异后的个体与父体进行比较，再选择两者之优。它使用的变异算子是基于 正态分布的变异操作，这种进化策略成为( 1 + 1 ) 进化策略。由于( 1 + 1 ) 进化 策略存在诸多弊端，如收敛速度慢、容易陷入局部极小等。一种改进的方法是增 加种群内个体的数量，从而演化为( p + 1 ) 进化策略。为进一步提高效率，后来 又发展成为( i l + 九) 进化策略和( p ，九) 进化策略，并且引进了重组操作。 进化策略与遗传算法的另一不同之处在于：遗传算法要将原问题的解空间映 射到位空间之中，然后再施行遗传操作。它强调个体基因结构的变化对其适应度 的影响。而进化策略则是直接在解空间上进行操作，它强调进化过程中从父辈到 后代行为的自适应性和多样性。从搜索空间的角度来说，进化策略强调的策略是 直接在解空间上进行操作，它强调进化过程中搜索方向和步长的自适应调节。 进化策略主要用于求解数值优化问题。近年来，遗传算法也采用实数编码技 术来求解数值优化问题。e s 和g a 的互相渗透已使得它们没有很明显的界限。 1 4 3 3 进化规划 2 0 世纪6 0 年代中期，l j f o g e l 等人为有限状态机的演化提出了进化规划 来求解预测问题。通过在与这些有限状态机对应的离散、有界集上进行一致随机 变异来修改它们的状态变化表。进化规划根据被正确预测的符号数来度量适应 值。通过变异，父辈群体中的每个机器产生一个子代，父辈和子代中最好的那一 半被选择生存下来。 基于正态分布变异，d b f o g e l 将进化规划扩展到解实值问题1 1 0 1 。随机产生 规模为 l 。的初始种群，对各个体分别变异，然后在所有父代个体和变异体中选 择疗，个个体进入下一代。变异操作将p 维个体( 五，x ：，x ，) 7 变异为 ( 而。，x 2 ，”，x 。) 7 ，如下式所示： 9 浙江大学硕l 学位论文 t = x ，+ m ( o ，1 ) ，i = 1 , 2 ，p 式中，( o ，1 ) 为标准正态分布的独立随机变量，丑为步长，变异可连续进行m 次。 丑的选值将影响寻优性能，五。值较大时全局寻优能力较强，而其值较小时有利 于局部寻优，常将z 设计为进化代数的递减函数。 1 4 4 群智能优化算法 群智能( s w a r mi n t e l l i g e n c e ) 优化算法于2 0 世纪9 0 年代初提出，包括蚁群 算法、粒子群算法以及鱼群算法等。人们在研究社会性生物群体的行为时发现， 群体中个体的行为很简单，随机性较大，但是整个群体在整体上呈现出高度的组 织性，比如蚁群能有效地寻找巢穴到食物源的最短路径。 正如b o n a b e a u 等所述：任何一种由昆虫群体或其它动物社会行为机制而激 发设计出的算法或分布式解决问题的策略均属于群智能【2 ”，所谓群智能是指通过 大量数目的智能体群来实现的智能方式。作为实现群体智能的单个的智能体，其 功能相对于整个问题求解来说是有限的。并且在没有得到智能体群的总体信息反 馈的时候，在解空间中的运动是完全没有规律的。但是，研究社会性生物群体的 科学家发现群体中个体之间存在高度自组织的协作行为，它们的协调行为通过个 体之间的交互行为直接实现，或者通过个体与环境的交互行为间接实现。虽然这 些交互行为非常简单，但是他们聚在一起却能快速有效地解决一些难题。这种潜 在方式的集群智能已经逐渐为人们所认识，并得到广泛应用1 10 ，捌。 1 4 4 1 粒子群算法 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n , p s o ) 模拟鸟集群飞行觅食的行为， 由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出】。它同遗传算法类似，通过个体间的协 作和竞争实现全局搜索。系统初始化为一组随机解，称之为粒子。通过粒子在搜 索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉以及变 异算子，而是粒子在解空间追随最优的粒子进行搜索。由于p s o 流程简单易于 实现，算法参数简洁，无需复杂的调整，因此p s o 被迅速地应用于函数优化、 神经网络训练、模糊系统控制、数据聚类以及原有的一些遗传算法应用领域。作 为一种新兴的算法，p s o 算法本身以及拓扑结构、参数选取、与其他进化技术的 融合及应用等方面得到了广泛研慰1 3 1 。 一1 0 浙江大学硕k 学位论文 起初，p s