（控制理论与控制工程专业论文）复杂优化问题中智能算法的分析与集成.pdf

摘要 本学位论文针对优化问题求解过程中存在的收敛速度与局部极小的两雉问 题，对橱能优化算法的内程机理、优化策略、流程、参数和操作进行了深入的系 统分捉，总结了不霹应用场合各秘算法鳃谯缺点，改进了舞能算法求鲻缀台後豫 问题和函数优化问题的离散与连续寻优设计方案；归纳了镏能全局优化算法和局 帮攘索葵法熬一般纛律彝纛耱筑律，蓄次霹智能饶纯算法进行了系统集成，褥鹫 现代肩发式全局邻域智能优化集成算法i m h g n i o a ( i n t e g r a t e dm e t a h e u r i s t i e g l o b a ln e i g h b o r h o o di n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，并给密其一般 缡构和要素设计原则，建立了该冀法的性能攒标评价体系。经过对不同算法的具 体集成和典型算例的数值实验，说明i m h g n i o a 类算法能够黼效率地获得全局戡优 鼹，是一耱袁敷的鲤毙往豫集成葵法，同时也验涯了本文嶷成方法靛受确性。 本、论文所做的主要工作是： 1 分鬟对模接邋火算法s a 、逶传算法g 矗、蔡忌接索冀法t s a 窝蚊瓣算法a c a 等的内在机理、优化策略、流程、参数和操作进行了系统分析，比较了它们程求 解不同筑纯问遂靖的优缺点，改进了这些算法求解缀台优纯溺蘧和函数优纯阀题 的离散与连续寻优设计方鬃，还研究了禁忌搜索算法的收效性和并行模拟退火算 法p s a 、并行遗传算法p g a 。该部分内容的研究，不缎为后续部分进行智能优化算 法的系缓集成抒下了厚实鲍理论基础、掇供了谨实的设计经验帮事富黪技术素枣葶， 还对现有智能算法做了一姥有益的改进工作，并且探讨了提高智能优化算法性能 懿并嚣纯途径。 2 智能优化算法的系统集成。以“从定性到定量的综合集成”的系统思想 为方法论，穰辖对智髓优纯算法静分帮子结采，提炼崮智能筑住算法在结掏上的一 般模式葶本质，h 的共同机制，综念运用赝掌攒的系统、智能、优化、复杂性等方 筒的知识和技术手段，首次提出了智能优化冀法系统集成的概念，并进步针对 拨位闽题求群过程中毒在黪收敛遮度与局部极小静鼹难问题，设计了一类先进磐 能优化算法集成的统一结构( 包括规范流程) 现代启发式全局邻域智能优化集 成算法i m h g n i o a 握絮。i 麓h g n i o a 统一框架载建立，整褥餐g l 饯诧算法褥潋实凌 真正意义上的系统集成，为算法之间的互补和增效开辟了有机结合的新途径，而 且为智麓优讫算法鬃成静突际操作提供了其育高适掰往豹麓范流程。 3 在i m h g n i o a 的统一框架下，实际设计了多种智能集成算法：g a s a 、i g a 以及m a 等，通过这些集成算法求解t s p 实例的数值仿真实验，得到明显优予其它 葵法躬求勰效率积求解质量，验谖了在i m h g n i o a 统一框架魏勰范流程下设计的垅 华南理工大学工学博士学位论文 化算法县有很高的效黼和适用性，说明i m h g n i o a 是一种具有一般意义的成功的智 能优化算法集成框架。 关键词：智能优化算法，系统集成，局部搜索，全局最优，复杂性 1 1 a b s t r a c t s i nt h ed i s s e r t a t i o n ，a i m i n ga tg e t t i n go u to fd i l e m m ao fc o n v e r g e n c e e f f i c i e n c ya n dl o c a lm i n i m u mw h i c he x i s t si ns o l v i n go p t i m i z a t i o np r o b l e m s ， w es y s t e m i c a l l ya n a l y z ei n h e r e n tm e c h a n i s m ，o p t i m i z a t i o np o l i c i e s ，f l e w ， p a r a m e t e r sa n do p e r a t i o no fi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ，a n ds u m u pr e l a t i v em e t i t so fv a r i o u sa l g o r i t h m su s e di nd i f f e r e n ta p p l i c a t i o n a r e a s ，a n di m p r o v ed i s c r e t ea n dc o n t i n u o u sd e s i g ns c h e m e st h a tu s e i n t e l l i g e n ta l g o r i t h m s t os o l v ec o m b i n a t i o n o p t i m i z a t i o na n df u n c t i o n o p t i m i z a t i o np r o b l e m s c o n c l u d i n gg e n e r a lr e g u l a t i o na n dc o m p l e m e n t a r y r e g u l a t i o no fi n t e l l i g e n tg l o b a lo p t i m i z a t i o na l g o r i t h m sa n dl o c a ls e a r c h a l g o r i t h m s ，f o rt h ef i r s tt i m e ，w ei n t e g r a t ei n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m si n t oi m h g n i o a ( i n t e g r a t e dm e t a h e u r i s t i cg 1 0 b a ln e i g h b o r h o o d i n t e l li g e n to p t i m i z a t i o na l g o r i t h m s ) b ys y s t e m i cm e t h o d s 。a n dt h e ni n f e r i t sg e n e r a ls t r u c t u r ea n de s s e n t i a l d e s i g np r i n c i p l ea n de s t a b l i s hi t s p e r f o r m a n c e e v a l u a t i o n s y s t e m b yc o n c r e t e l yi n t e g r a t i n g v a r i o u s a l g o r i t b m sa n dh u m e r i c a l l yt e s t i n gt ot y p i co p t i m i z a t i o np r o b l e m ss a m p l e ， w es e et h a t b e i n gaa l a s so fv a l i di n t e g r a t e di n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s ，t h ei m h g n i o a c a nh i g he f f i c i e n t l yg e t g l o b a lo p t i m i z a t i o n s o l u t i o n sa n dt h i s i n t e g r a t i o nm e t h o di n t h ed i s s e r t a t i o ni sa c c u r a t e m a i nj o b si nt h ed i s s e r t a t i o n ，a sf o l l o w s ： 1 w es y s t e m i c a l l ya n a l y z ei n h e r e n tm e c h a n i s m ，o p t i m i z a t i o np o l i c i e s ， f l o w ，p a r a m e t e r sa n do p e r a t i o no fs a ( s i m u l a t e da n n e a l i n g ) ，g a ( g e n e t i c a l g o r i t h m ) ，t s ( t a b o oo rt a b us e a r c h ) ，a c a ( a n tc o l o n i e sa l g o r i t h m s ) ，e t c r e s p e c t i v e l y ，a n dc o m p a r er e l a t i v em e r i t so ft h o s ea l g o r i t h m su s e di n d i f f e r e n tu t i l i z a t i o nf i e i d s ，a n di m p r o v ed i s o r e t ea n dc o n t i n u o u sd e s i g n s c h e m e st h a tu s et h o s ea l g o r i t h m st os o l v ec o m b i n a t i o no p t i m i z a t i o na n d f u n c ti o no p t i m i z a t i o np r o b l e m s f a r t h e rm o r e ，w er e s e a r c hp a r a ll e l s a ， p a r a l l e lg aa n dc o n v e r g e n c eo ft s t h i sp a r to fr e s e a r c hd o e s n to n l y e s t a b l i s hs o l i d t h e o r yf o u n d a t i o n ，s u p p l yn e c e s s a r yd e s i g ne x p e r i e n c e sa n d r i c ht e c h n i q u em a t e r i a l sf o rf o l l o w i n g s y s t e m i ci n t e g r a t i o no fi n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ，b u ta l s oi m p r o v e si n t e l l i g e n ta l g o r i t h m si n e x i s t e n c es o m e w h e r ea n dp r o b e si n t op a r a l l e l i z a t i o n a p p r o a c h e st oe n h a n c e i i i t h e i rp e r f o r m a n c e 2 i n t e g r a t i o n o fi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s b a s e d o n “m e t a s y n t h e s i s ”s y s t e m i cm e t h o d o l o g y a n d a n a l y z i n g r e s u l t st o i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ，w ea b s t r a c ti n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m st og e n e r a lp a t t e r no fs t r u c t u r ea n d c o m m o nm e c h a n i s m 。b yt a k i n g a d v a n t a g e o f c o m p r e b e n s i v ek n o w l e d g e a n d t e c h n i q u e a b o u t s y s t e m ， i n t e l l i g e n c e ，o p t i m i z a t i o na n dc o m p l e x i t y ，w e f i r s tb r i n gf o r w a r dt h e c o n c e p to fs y s t e m i c a l l yi n t e g r a t i n gi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ， a n dt h e n ，a i m i n ga tg e t t i n go u to fd i l e m m ao fc o n v e r g e n c ee f f i c i e n c ya n d l o c a lm i n i m u mw h i c he x i s t si ns o l v i n go p t i m i z a t i o np r o b l e m s 。w ed e s i g na c l a s so fu n i f i e ds t r u c t u r e ( i n c l u d i n g s t a n d a r df l o w ) o fi n t e g r a t e d i n t e l l i g e n to p t i m i z a t i o n a d v a n c e d a l g o r i t h m s “f r a m e o fi m h g n i o a b e c a u s eo fe s t a b l i s h 整e n t o fi m h g n i o au n i f l e df r a m e ，i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m sf i r s tr e a l l yc a nb es y s t e m i c a l l yi n t e g r a t e d t h e s y s t e m i ci n t e g r a t i o no p e n su pan e wa v e n u eo fo r g a n i cb i n d i n gf o rg e t t i n g c o m p l e m e n t a t i o na n di n c r e a s i n g e f f i c i e r i c i e sa m o n ga l g o r i t h m s a n dt h e u n i f i e df r a m es u p p l i e sah i g hr e l i a b l es t a n d a r df l o wc h a r tf o ra c t u a l i z i n g o p e r a t i o no fi n t e g r a t i n gi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s 3 。b a s e do nt h ei m h g n i o au n i f i e df r a m e ，w ed e s i g ns e v e r a li n t e g r a t e d i n t e l l i g e n ta l g o r i t h m s ：g a s a ，i g a ，m aa n de t c b y c o m p u t e r s i m u l a t i o n t e s t i n gt h a t t h o s ea l g e r i t h m ss o l v et s ps a m p l e s ，w eg e tb e t t e rr e s u l t s o b v i o u s l ye x c e e d i n go t h e rr o u t i n ea l g o r i t h m s0 1 1 s o l v i n ge f f i c i e n c y a n d s o l v i n gq u a l i t y t h o s er e s u l t si n d i c a t et h a ta l g o r i t h m sd e s i g n e db a s e d o n t h ei m h g n i o au n i f i e df r a m ea n ds t a n d a r df l o wc h a r ta r ep r o v i d e dw i t hh i g h e f f i c i e n c y a n d a d a p t a b i l i t y s o ，i m h g n i o a i sac l a s so f + s u c c e s s f u l i n t e g r a t e da l g o r i t h m sb e i n go fg e n e r a l i z a t i o n s e n s e - k e y w o r d s ：i n t e l li g e n to p t i m i z a t i o n a l g o r i t h m s ，s y s t e m i c i n t e g r a t i o n ， l o c a ls e a r c h ，g l o b a lo p t i m i z a t i o n ，c o m p l e x i t y 华南理工大学 学位论文原创性声明 本人郑重声明：所里交的论文是本人在导师的指导下独立 进行研究所取褥的磷究戚果。除了文中特别加戳标注葶 震麓蠹 容外，本论文不包含任何其他个人或集体已经发表或撰写的成 果俸晶。对本文的衙究做出羹要贡献的个人帮集体，沟己在文 中以明确方式标明。本人完全意识到本声明的法律后熙由本人 承担。 作者签名：奄弧善 日期： 吵年7 月7 日 学位论文版权使用授权书 本学位论文作者完全了勰学校有关保留、使用学位论文的 规定，同懑学校保留并向国家有关部门或机构送交论文的笈印 件和电子舨，允许论文被查阅和借阅。本人授奴华南理工大学 可以将本学位论文的全部或部分内容编入有关数据库进行检 索，霉数采震影印、缩印或撼搓等复裂手段僳存蠢汇编本学位 论文。 保密口在年解密赢适焉本授寝书。 本学位论文属于 不保密口。 ( 请在以上摆应方糕走打“”) 作者签名：专弧争 导窭纂签名：声2 也芝 e t 麓：游7 嚣7 e l e t 期：翮；年7 胃7 日 第一章绪论 1 1 引言 第一章绪论 系统工程的重要意义之一体现于整体与局部的最优协调。而智能方法正是基 于这个出发点，为解决复杂系统优化问题开辟了寻求次优解、有用解( 或可行解) 的新途径。在人类有了发达大脑后的短短几千年历史中，文明得到空前发展，形 成了复杂的社会体系，在生物界人类主宰了地球，这说明智能对复杂系统具有很 强的优化能力。似然地，智能算法作为处理复杂的、非线性优化问题的先进工具， 在各个学科得到了广泛的应用、取得了空前的发展。作为非导数优化方法，智能 方法相比于传统的导数优化法n ，算得上是处理复杂优化问题的一种先进现代技 术手段，但是智能技术还处于非常初始的发展阶段，智能方法还未能形成一个有 机集成的方法体系，使得人们还无法很好地做到系统使用智能方法，系统工程的 综合集成的整体思想在这里无法很好体现。各种智能方法的孤立使用，也使得智 能方法不能得到更有效的利用。 孤立地使用现有各种智能方法已经不能满足复杂系统优化给工程技术人员 提出的更高要求，随之，近年来出现了一些对智能算法的混合研究，试图通过对 各种智能算法的结合，增强智能算法的功效。这种混合研究是有益的，它确实使 得原有的算法得到改进，但这种研究只是局部的、针对某些特例的，它的初衷只 是提高智能算法的优化性能，没有提升到综合集成( 即系统地进行集成) 的高度上 来。本学科专业方向是系统工程，研究学习所在的单位也是系统工程研究所，所 以想从系统角度对智能优化方法进行研究。近年来，智能算法的混合研究已经渐 趋活跃，但还未见到国内外有关文献提出智能算法的综合集成。基于这种想法， 本文首先剖析了智能算法的优化机理、比较分析了各种智能算法的优缺点，进而 对智能算法进行了综合集成的研究。 1 2 智能算法的演进历程 所谓智能，我们指的是a r t i f i c i a li n t e l l i g e n c e 人工智能a i 。人工智 能应具备的特点是：由人工设计或创造的，能模拟人的思考、具备一定的学习功 能，能进行归纳演绎等逻辑推理，具有一定的自主性，能够独立完成人们交给的 在变化条件或环境下的某项任务。 经典人工智能的研究起始于1 9 5 6 年，其主要目标是应用符号逻辑的方法模 拟人的问题求解、推理、学习等方面的能力。 华南理工大学工学博士学位论文 问题求解鼹经典人工智能的核心问题，当机器有了对某些问题的求解能力以 后，在皮用场合遇到这类问题肘，便会自动找崽正确的解决簸略。这辨问题求解 能力是蕊于规剃的。怒能够举一反三的。有了问题求解能力驹机器就能比普通祝 器更灵巧地分析问题、处理问题，从而适应于更加复杂多变的应用场合。 稚疆是入的思维的霪要方灏，稚瓒的三种主要形斌是归纳推理、演绎推理和 模糊推理。经典人工智能中推理的研究就是要模拟这三种推理形式，实现诸如故 障诊断、数学定理证瞬、模糊闷题翔断等功髓。 在缀典人工智能中，“学习”一铡有多种含义。在专家系统等应用中，宦指 静是知识的舀动积累；在问题求解孛，它指静是裉箨执行情褫修改计翔；在数学 推理系统中，它指的是根据一热简单的数学概念和公理形成较复杂的概念，做出 数学猜怒等等。 人工智能的问题求解是建立在知识表示的基础上的，而知识表示基于符号逻 辑，掰骏经典人工瞽煞毽称为耱号智麓。淀麓裘解豹雅理是遴过在躲空瘸申遴彳亍 最优解搜索来实现的，所以除知识表示外，人工智能的另一个重要研究内容熄搜 索算法。 经媳人工智能是基于知识的，而知识通过符号进行表示和运算，被具体化为 撬爨。稼是，聚识莠不舔韪爱簿号表示为援掰，餐麓瞧不罄爨莲予翔谈兹。人秘 相信，自然智能的物质机构神经网络的智能是基于结构演化的。因此2 0 世纪 8 0 每饯在经典人工餐戆理论发展逛璜停顿，露人工毒枣经网络理论出壤囊鳇突破 时，基于结构演化的人工智能理论计算智麓迅速成为人工智能研究的主流。 计黧智能怒以生物进化载淡点认识积模拟餐能。按照这点，餐能是在生物 的遗传、变异、生长以及外部环境的自然选择中产生的。在用进废退、优胜劣汰 的过程e = l ，适应度高的( 头脑) 终梅被保罄下来，智能出平也髓之提毫。因此说诗 算智能就是结构演化的智能。 计算智能的主要方法青人二 神经嬲终、遗传算法、演化稳序、局部搜索、模 拟退火等等。这些方法艇有以下共同的要素：自适应的结构、随机产生的或指定 灼初始状态、邋应度的评测函数、修改结构的操作、系统状态存储器、终止计算 的条件、指示缩果的方法、控制过程的参数。计算智熊的这燕方法其有自学习、 自组织、自适成的简单特征和简单、通用、鲁棒性强、适于并行处理的优点，在 并行搜索、联憝记忆、模式识剐、知谈自动获敬等方灏得刮广泛的应糟。 近年来，随着系统工程的系统思想在各个学科中的不断深化，学科交叉现象 更加普邂。智麓理论星现高学科内井两时交叉的活跃祭观，觚内部看，2 0 整绍9 0 年代以来，经典的人工智能和计算智能方法在某些热点智能研究领域形成结合， 鲡数据漾掘帮翔识发璃( 所谓数据采箍帮知识教溪是以数据仓痒为基秣，通过综合 运用统计学、横糊数学、神经网络、机器学习和专家舔统等方法，从大量的数据 2 第一章绪论 中提炼出抽象的知识，揭示出蕴含在数据背后的客观世界的内在联系和本质规律， 实现知识的自动获取) ；从外部看：智能方法与诸多复杂系统理论、非线性理论、 信息科学等相融合，如混沌理论、模糊理论、灰色理论、信息熵理论与智能算法 的结合。近年来出现的所谓“高级人工智能”，就是通过学科的这种内外部交叉形 成的n ，。 实际上，近年来蓬勃发展的先进智能算法，大多数都是通过经典智能算法在 智能学科领域内外借鉴、融合其它处理复杂问题的先进方法形成的。 优化理论也是如此，优化方法的广泛应用和研究上的空前活跃以及优化问题 本身的复杂性、多样性，使它成为学科交叉的热点，更成为检验新理论、新方法 的“实验室”。 智能算法与优化理论在学科内外普遍融和交叉的相似发展方式，使两个学科 处于胶着状态，成为互相促进、相辅相成的关联学科。学科间的密切关联发展模 式以及系统思想的能动性指导，为我们第一次正式提出和系统研究智能算法的综 合集成，提供了前提条件。正是智能方法和优化理论的多方位交叉融合，为我们 为培育智能集成算法提供了温床。 1 3 复杂优化问题概述 优化技术是一种以数学为基础，用于求解各种寻优问题优化解的应用技术。 作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到 迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、v l s i 技术和计 算机工程等。 优化方法涉及的应用领域很广，问题种类与性质繁多。归纳而言，最优化问 题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间 内的连续变量，而组合优化的对象则是解空间中的离散状态。 1 3 1 复杂函数优化问题 函数优化问题通常可描述为：令s 为彤上的有界子集( 即变量的定义域) ， ，：s 斗r 为n 维实值函数，所谓函数厂在s 域上全局最小化就是寻求点置。e s 使 得厂( j 。) 在s 域上全局最小，即s ：，( 工。) f ( x ) 。 算法的性能比较通常是基于一些称为b e n c h m a r k 的典型问题展开的。就无约 束函数优化问题而言，目前常用的b e n c h m a r k 问题如下： s p h e r em o d e l 其最优状态和最优值为 z ( 爿) =蚓1 0 0 ( 卜l a ) m i n ( f ( x ) ) = z ( 0 ，u ，0 一，0 ) = 0 ( 卜l h ) 华南理工大学工学博士学位论文 s c h w e f e l 。sp r o b l e m2 2 2 3 0 3 0 f d x ) = k | + k 同l ( 1 2 a ) f = 1i = 1 冀最优状态和最德值为 m i n ( f d x + ) ) = l ( o ，o ，0 ) = 0 ( 卜2 b ) s c h w e f e lsp r o b l e ml ，2 3 0f 六( j ) = ( x j ) 2 ，蚓1 0 0 ( 1 3 a ) i = li = i 冀最优状态和最优值为 m i n ( f 3 ( x ) ) = ( 嘎o ，0 ) = 0 ( 1 3 b ) s c h w e f e lsp r o b l e m2 2 l 五( 舅) = 鼍3 擎o 如良如l - 1 0 0 ( 1 - 巍) 其最优状态和最优值为 m i n ( f 4 ( x + ) ) = a ( o 。 o ) = 0 g e n e r a liz e dr o s e n b r o c k sf u n c t io n 五( x ) ：至i o o ( + ，一砰) 2 + ( 1 墨) 2 】，i x ，l - 3 0 i = 1 獒最甓状态霹最傻藿为 m i n ( a ( x + ) ) = a ( 1 ，1 ，1 ) = 0 s t e pf u n c t i o n 兀晤) = ( t + o 5 1 ) 2 ，h _ l o o 奠晟优状态和最优值为 m i n ( a ( x + ) ) = 五( o ，嚷- - 2 ) = 0 o u a r t i cf u n c t i o ni e n i o s e 五( 司= 霹+ r a n d o m o ，| ) ，吲s l 。2 8 其最优状态和最忧值为 m i n ( l ( x ) ) = 五( o ，o ，o ) = 0 g e n e r a l i z e ds c h w e f e l sp r o b l e m2 2 6 3 0 一 ( x ) = 一( ts 协( 批慨 1 x ；l n5 0 0 i = 1 奠最优状态和最伉值为 m i n ( a ( x ) ) = a ( 4 2 0 9 6 8 7 ，4 2 0 9 6 8 7 , , 4 2 0 9 6 8 7 ) = 1 2 5 6 9 5 4 1 - 4 b ) ( 1 5 a ) ( 1 5 b ) ( 卜6 a ) l 一6 b ) ( 1 7 8 ) ( 卜7 b ) ( 1 - s a ) ( 1 - s b ) 第一鬻绪论 g e n e r a l i z e dr a s t r i g i nsf u n c t i o n 磊( ；兰离一1 0 e o s ( 2 n x ，) + 1 0 ，i 蕾1 - 5 。1 2 ( 1 - a ) 冀最优状态和最忧值为 m i n ( a ( x ) ) = l ( o , o ， o ) = o ( 1 9 b ) a c k l e y sf u n c t i o n ( 司= - 2 0 e x p l n 2 j 善# ”oj _ e x p ( 萎3 0 c o “2 矾) 3 0 ) + 2 0 + 岛 f】3 0、 m 3 2 焚最优状悫和最伉值为 m i n ( a 。( ) ) = 厶( q o - - - , 0 ) = 0 g e n e r a l i z e dg r i e w a n kf u n e t i o n 熊玲志霎娶c o s ( 荆托小 冀最优状态和最优值为 m i n ( a ，盖) ) = z ，f 辑0 ，碧一0 g e n e r a l i z e dp e n a l i z e df u n c t i o n 似耻新躐n 2 ( 硼+ 酗2 0 卅+ l o s i n 2 ( n y ，+ , ) m ”叫 ( 1 - 1 l a ) ( 1 一l l b ) + “( t ，1 0 ，1 0 0 ，4 ) ，l x f t - 0(1-20) lh ( x ) = 0 4 lx s 转化为无约束问题来处理，常用的途径有： ( 1 ) 把问题的约束在状态的表达形式中体现出来，并设计专门的算子，使状态 所表示的解在搜索过程中始终保持可行性。这种方法最直接，但适用领域有限， 算子的设计也较困难。 7 华南理工大学工学博士学位论文 ( 2 ) 在编码过程中不考虑约束，而在搜索过程中通过检验解的可行性来决定解 的弃用。这种方法一般只适用于简单的约束问题。 ( 3 ) 采用惩罚的方法来处理约束越界问题。这种方法比较通用，适当选择惩罚 函数的形式可得到较好的结果。譬如采用罚函数。 j m i n f ( x ) + 舶2 + p m m o g ( 鼻) 坪 r 1 - 9 1 、 1j s ”7 复杂函数优化问题主要是指包含带有非线性约束的函数、非凸函数、不连续 函数、不可微或不可积函数、带有随机性的函数和高维函数等优化问题。 1 3 2 复杂组合优化问题 组合优化问题通常可描述为：令q = h ，是，矗 为所有状态构成的解空间， c ( s ) 为状态s ，对应的目标函数值，要求寻找最优解s ，使得 v s i q ，c ( s ) = m i n c ( s i ) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹 学的一个重要分支。 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) 、加工调 度问题( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b s h o p ) 、o - 1 背包问题( k n a p s a c k p r o b l e m ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、 聚类问题( c l u s t e r i n gp r o b l e m ) 等。 1 旅行商问题给定”个城市和两两城市之间的距离，要求确定一条经过各 城市当且仅当一次的最短路线。其图论描述为：给定图g = ，刎，其中v 为顶 点集，a 为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一 条长度最短的h a m i l t o n 回路，即遍历所有顶点当且仅当一次的最短回路。 2 加工调度问题5 0 b s h o p 问题是一类较t s p 更为复杂的典型加工调度问 题，是许多实际问题的简化模型。一个j o b s h o p 可描述为：n 个工件在t n 台机器 上加工，0 表示第i 个工件在第，台机器上的操作，相应的操作时间z ，为已知， 事先给定各工件在各机器上的加工次序( 称为技术约束条件) ，要求确定与技术约 束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优。在 j o b s h o p 问题中，除技术约束外，通常还假定每一时刻每台机器只能加工一个工 件，且每个工件只能被一台机器所加工，同时加工过程为不问断。若各工件的技 术约束条件相同，一个j o b s h o p 问题变转化为较简单的f l o w s h o p 问题。进而， 若各机器上各工件的加工次序也相同，则问题可进一步转化为置换f l o w s h o p 问 题。 3 0 1 背包问题对于n 个体积分别为a 、价值分别为c ；的物品，如何将它们 装入总体积为b 的背包中，使得所选物品的总价值最大。 4 装箱问题即如何以个数最少的尺寸为1 的箱子装入h 个尺寸不超过1 的 繁一章绪论 戆晶。 5 。豳着色闷题对子弹个顶点的笼环图g ，要求对其各个溪点逃簿羞热，使 得任意褥个福邻静顶点都有不黼静藤瞧，蕊骈稻颜色释类最少。 6 聚类问题搬缎空阙上的挥个模式 并出= 1 ，2 ，舟 ，要浓聚成k 类，使得各 类本身内的点最榴近，譬如要求 ，= 降l ( 1 2 2 ) 4 # 襞，l 、。其中最。为黎p 类麓孛心，馨 。 = 霹蚶7 b l ”2 3 ) a l 其中，p 2 | ，2 ，蠹，撵，海篇尹粪中静煮数。 笺杂缀合德毒乏簿鬟孛运魏a 程嚣至要燕多誉舔鞠鼹、萄部鹚窝鬃、邃台瀑簿 问题等。上述问题均属簸杂组优化问题，求其最优解很困难，其中主要原因之 一载蕊驻潺憋“懑套鬃炸”。謦辩，聚豢海题筑霉熬然分方式煮k 8 k 个，j o b * 娃印 的可能排列方式村( 剐) 卅个，熬予置换排列描述的h 城市t s p 问题脊剐种可行排 捌，耀使对爰方惫牲霉i 键琴蛙瓣乎瑟游题仍鸯溶一1 ) ，2 秘不秘接裂，显然状态数 基随问题规模璺超指数域长。瓣计算机每秒能处理l 识手申担 列，则穷举2 0 域樽闽 瑟敦2 01 耱毅 列终赘死露年，囊羹藏巨大豹落+ 冀量爨无法承受瓣，更不愆谈更大燕 摸阉题戆求解。嚣魏，熬决这憋闷题瓣关键毯子影求爨效豹蠛纯算淤，逛夔涎阂 题豹投凌性_ j 鞋笈杂牲激怒了人稍馒建罄能冀法对缀合饯谯理捻遴嚣磅究靛热情。 缀濂然，一耱算法鹣不麓靛虱优纯解愚譬要豹，穗辩多多辩阉、潴耗多少资 源、能褥到俺琴孛准确稷鹰鼹优化织，却是算法蘧喙的受实际熟阕题。因此，镑对 组合优化，入f f j 也构造了大量测试算法的b e n c h m a r k 罨优简灏，来测试算法的效 率、精发等牲畿。 1 4 撬化算法 所谓优蕾艺算法，冀实就是种搜索过程藏规则，它是基于菜种思想和机制， 通过一定鹣途径或烧瑟越来褥至l 瀚足焉户溪求戆阔蘸豹解。 就筑化机制与行为弼分，飘前实黼寻优避程中鬻用鹃优纯算法主鬃可分为： 经典舞法、构造型葬法、敬进型算法、基于系统动态演化的算法和混合型算法等。 、经典冀法毽摇线桎援潮、动态耀翅、整数蕊潮耧分鼗邂赛等抟统运簿学 中的辣泌，其算法计算艇杂性般很大，只适于求解小规模问题，程复杂优化问 题中茗量程不安嬲。 2 构造烈算法用构造的方法快遴建立问题的解，通常算法的优化质量憩， 9 华南理工大学工学博士学位论文 难以满足工程需要。譬如，调度问题中的典型构造方法有j o h n s o n 法、p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、n e h 法等。 3 改进型算法改进型算法，或称邻域搜索算法，即从任意一个解出发，对 其邻域的不断搜索和对当前解的替换来实现优化。根据搜索行为，它又可分为局 部搜索法和指导性搜索法： 局部搜索法 以局部优化策略在当前解的邻域中按照贪婪原则搜索，如只接受优于当前解 的状态作为下一当前解的爬山法；接受当前解邻域中的最好解作为下一当前解的 最陡下降法等。 指导性搜索法 利用一些指导规则来指导整个解空间中对全局优良解的探索，如s a 、g a 、e p 、 e s 、t s 、a c a 等。 4 基于系统动态演化的方法将优化过程转化为系统动态的演化过程，基于 系统动态的演化来实现优化，如神经网络和混沌搜索等。 5 混合型算法针对具体优化问题，将上述各种算法进行交叉、融合、组合 而形成的各类杂交算法。 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法， 局部优化算法和全局优化算法等。 科学技术正处于多学科相互交叉和渗透的时代，随着人类生存空间的扩大以 及认识与改造世界范围的拓宽，人们对科学技术提出了新的和更高的要求，其中 对高效的优化技术和智能计算的要求日益迫切。 鉴于实际优化问题的复杂性、约束性、非线性、多极小、建模困难等特点， 寻求适合于大规模并行且具有智能特征的算法己成为有关学科的一个主要研究目 标和引人注目的研究方向。优化方法的理论研究对改进算法性能、拓宽算法应用 领域、完善算法体系同样具有重要作用。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传 算法、进化规划、模拟退火、禁忌搜索、蚁群算法及其混合优化策略等，通过模 拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生 物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思 路和手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了 该领域的研究热潮，且在诸多领域得到了成功应用。在优化领域，由于这些算法 构造的直观性与自然机理，因而通常被称作智能优化算法( i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ) ，或称现代启发式算法( m e t a h e u r is t i c a l g o r i t h m s ) 。我们进行集成研究的对象就是智能优化算法，即现代启发式算法。 对于复杂优化问题的求解，智能算法较传统优化