（模式识别与智能系统专业论文）基于进化算法的约束处理技术研究.pdf

硕士学位论文摘要 摘要 约束优化问题( c 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 ，c o p s ) 是科 学和工程应用领域经常会遇到的一类数学规划问题，因而对其研究具 有十分重要的理论和实际意义。进化算法( e v o l u t i o n a r y a l g o r i t h m s ， e a s ) 是一种模拟自然进化过程的全局优化方法。近年来进化算法已 被广泛地应用于求解约束优化问题，并提出了大量的约束优化进化算 法( c o n s t r a i n e do p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s ，c o e a s ) 。 本文首先介绍了进化计算的起源、发展及其三个主要分支( 即遗 传算法、进化规划和进化策略) 。接着描述了约束优化问题和多目标 优化问题，并对约束优化进化算法的国内外研究现状进行了回顾。 然后在第四章和第五章提出了两种约束优化进化算法，它们都基 于多目标优化技术。 第一种算法首先阐述了一个重要的结论，即在约束优化中，非劣 个体代表了群体中最主要的信息。接着提出了非劣个体替换准则，并 将其与三个基于群体的算法发生器进行了结合。为了有效利用不可行 解，该算法提出了一种不可行解存档和替换机制。此外，通过克服两 种极端的情况，该算法可以直接处理等式约束条件。对1 3 个标准测 试函数的测试结果表明，该算法在优化性能上显著优于其它算法。 第二种算法将多目标优化技术与全局和局部搜索模型有机地结 合起来，提出了一种混合约束优化进化算法m c o e a 。该算法中，全 局搜索模型为一种基于联赛选择的小生态遗传算法。此外，该算法采 用一个并行的局部搜索操作对群体实施聚类分割和多父体交叉产生 子代群体。对1 3 个标准测试函数的测试结果表明，该算法在鲁棒性、 优化效率等方面显著优于其它约束优化进化算法。 本文最后在“结束语”中，提出了约束优化进化算法中值得进一 步研究的问题。 关键词进化算法，约束优化，多目标优化，非劣个体，全局搜索， 局部搜索 硕士学位论文a b s t r a c t a b s t r a c t c 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 ( c o p s ) b e l o n gt oak i n d o f m a t h e m a t i c a lp r o g r a m m i n gp r o b l e m s ，w h i c ha r ef r e q u e n t l ye n c o u n t e r e d i nt h ed i s c i p l i n e so fs c i e n c ea n de n g i n e e r i n ga p p l i c a t i o n e v o l u t i o n a r y a l g o r i t h m s ( e a s ) a r eak i n do fg l o b a lo p t i m i z a t i o nm e t h o d s ，w h i c h s i m u l a t e st h ep r o c e s so fn a t u r a le v o l u t i o n d u r i n gt h ep a s td e c a d e e a s h a v eb e e nb r o a d l ya p p l i e dt os o l v ec o p s ，a n dc o n s i d e r a b l ec o n s t r a i n e d o p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s ( c o e a s ) h a v eb e e np r o p o s e d f i r s t l y , t h i sd i s s e r t a t i o ni n t r o d u c e st h eo r i g i n 。a d v a n c ea n dt h r e e m a i nb r a n c h e s ( i e ，g e n e t i ca l g o r i t h m s ，e v o l u t i o n a r yp r o g r a m m i n ga n d e v o l u t i o n a r ys t r a t e g i e s ) o fe a s t h e n ，t h ed e s c r i p t i o no fc o n s t r a i n e d o p t i m i z a t i o np r o b l e m s ( c o p s ) a n dm u l t i - o b j e c t i v eo p t i m i z a t i o n p r o b l e m s ( m o p s ) i sg i v e n i na d d i t i o n ，t h ea d v a n c e so fc o e a sa th o m e a n da b r o a da r er e v i e w e d a f t e r w a r d ，t w oc o e a sp r o p o s e db yt h ea u t h o ra n db a s e do nm u l t i o b j e c t i v eo p t i m i z a t i o nt e c h n i q u e sa r ep r e s e n t e di nc h a p t e r s4a n d5 t h ef i r s ta l g o r i t h m ，f i r s to fa l l ，i l l u s t r a t e sa ni m p o r t a n tc o n c l u s i o n ， i e ，n o n d o m i n a t e di n d i v i d u a l sr e p r e s e n tt h em o s ti m p o r t a n ti n f o r m a t i o n o fap o p u l a t i o n i na d d i t i o n ，t h i sa l g o r i t h mp r o p o s e st h en o n - d o m i n a t e d i n d i v i d u a lr e p l a c e m e n ts c h e m e ，w h i c hi sc o m b i n e dw i t ht h r e em o d e l so f a p o p u l a t i o n b a s e da l g o r i t h m - g e n e r a t o r f u r t h e r m o r e ，a n i n f e a s i b l e s o l u t i o n s a r c h i v i n g a n d r e p l a c e m e n t m e c h a n i s mi si n t r o d u c e dt o e f f e c t i v e l ye x p l o i ti n f e a s i b l es o l u t i o n s b yo v e r c o m i n gt w oe x t r e m e c o n d i t i o n s ，t h i sa l g o r i t h md o e sn o tr e q u i r et h et r a n s f o r m a t i o no fe q u a l i t y c o n s t r a i n t si n t o i n e q u a l i t yc o n s t r a i n t s t h en e wa p p r o a c hi st e s t e d o n t h i r t e e nw e l l k n o w nb e n c h m a r kf u n c t i o n s ，a n dt h ee m p i r i c a le v i d e n c e s u g g e s t s t h a ti ti s r o b u s t ，e f f i c i e n t a n d g e n e r i c w h e n h a n d l i n g l i n e a r n o n l i n e a r e q u a l i t y i n e q u a l i t yc o n s t r a i n t s c o m p a r e dw i t hs o m e o t h e rs t a t e - o f - t h e a r ta l g o r i t h m s ，t h i sa l g o r i t h mr e m a r k a b l yo u t p e r f o r m s t h e mi nt e r m so f t h eo p t i m i z a t i o nc a p a b i l i t y t h es e c o n da l g o r i t h mn a m e dm e m e t i cc o n s t r a i n e d o p t i m i z a t i o n 硕士学位论文a b s t r a c t e v o l u t i o n a r ya l g o r i t h m ( m c o e a ) e f f e c t i v e l yc o m b i n e sm u l t i o b j e c t i v e o p t i m i z a t i o nw i t hg l o b a la n d l o c a ls e a r c hm o d e l s i np e r f o r m i n gt h e g l o b a ls e a r c h ，an i c h i n gg e n e t i ca l g o r i t h m ( n g a ) b a s e do nt o u r n a m e n t s e l e c t i o ni sp r o p o s e d a l s o ，m c o e ah a sa d o p t e dap a r a l l e ll o c a ls e a r c h o p e r a t o rt h a ti m p l e m e n t sac l u s t e r i n gp a r t i t i o no ft h ep o p u l a t i o n a n d m u l t i - p a r e n tc r o s s o v e rt og e n e r a t eo f f s p r i n gp o p u l a t i o n m c o e ai s t e s t e do nt h i r t e e nw e l l k n o w nb e n c h m a r kf u n c t i o n sa n dt h ee x p e r i m e n t a l r e s u l t ss u g g e s tt h a ti ti sm o r er o b u s t ，e f f i c i e n ta n dg e n e r i ct h a no t h e r s t a t e - - o f - t h e - - a r ta l g o r i t h m sf r o mt h el i t e r a t u r ei nt e r m so ft h es e l e c t e d p e r f o r m a n c em e t r i c s f i n a l l y , t h i sd i s s e r t a t i o np o i n t so u ts o m ed i r e c t i o n st h a ta r ew o r t h y t ob er e s e a r c h e df u r t h e rj nt h i sa r e a k e yw o r d se v o l u t i o n a r yc o m p u t a t i o n ，c o n s t r a i n e do p t i m i z a t i o n ， m u l t i o b j e c t i v eo p t i m i z a t i o n ，n o n d o m i n a t e di n d i v i d u a l ，g l o b a ls e a r c h ， l o c a ls e a r c h 1 1 i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名：兰夏日期：上二生年月日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：盟导师签名兰歪鱼堡日期：三竺堡年野丝日 硕士学位论文 第一章绪论 1 1课题研究背景 第一章绪论 许多的科学与工程问题都可以转化为优化问题，由于优化问题存在的普遍性 和重要性，几十年来得到了广泛和深入的研究。直到现在，仍有许多学者在对最 优化问题做更深入的工作，最优化问题也一直是人们感兴趣的一个问题。正是因 为这些持续的工作，才不断出现了新的理论和方法，以满足科学和技术发展的需 要。 约束优化问题是一类广泛存在于实际工程中但又较难求解的问题。传统的求 解该类问题的方法通常是基于梯度的局部搜索方法，如可行方向法、投影梯度法、 简约梯度法、各类外点罚函数法和内点法、l a g r a n g i a n 法和序y u - - 次规划法等。 这些方法存在的主要问题是求解需要设置很好的初值点和需要函数的梯度信息， 它们对于不可导、可行域不连通、甚至根本没有显式数学表达式等问题无能为力。 在2 0 世纪4 0 年代，生物模拟就成为了技术科学的一个组成部分。如早期的自 动机理论就是假设机械是由类似于神经元的基本单元组成的。后来，对人工神经 网络的研究也明显地得益于生物学理论与成果。关于人工生命的研究则与生物学 的关系更紧密。但所有这些工作都无法与进化计算( e v o l u t i o n a r yc o m p u t a t i o n ， e c ) 取得的成功相比。 自从生物进化的理论被人们接受之后，关于进化的研究得到了很大的发展。 虽然对于进化的机制还没有完全搞清楚，但进化的一些特征已经被人们所认识。 生物学上这样的一些进展和研究成果在优化问题上的渗透就是进化计算。 同传统优化方法相比，进化算法不需要梯度( 导数) 等信息，更适合于求解 约束优化问题。近十年来，利用进化算法求解约束优化问题已成为进化计算领域 的研究热点，并且已经涌现出大量的约束优化进化算法( c o n s t r a i n e do p t i m i z a t i o n e v o l u t i o n a r ya l g o r i t h m s ，c o e a s ) 【1 埘。 1 2现存技术及存在的问题 本质上，约束优化进化算法可以归纳为如下的形式： 约束优化进化算法= 约束处理技术+ 进化算法 硕士学位论文第一章绪论 也就是说，为了得到较好的优化性能，一种有效的约束处理技术应该与一种高效 的进化算法进行结合。 在约束处理方面，m i c h a l e w i c z 等【1 1 和c o e l l o l 2 1 对当前较为流行的基于进化算 法的约束处理技术进行了广泛的调查，并分别将它们划分为四类和五类。在文献 【1 忡，m i c h a l e w i c z 和s c h o e n a u e r 将约束处理技术划分为如下的四类：1 ) 保存可 行解方法：2 ) 惩罚函数法：3 ) 可行解优于不可行解方法；4 ) 其它混合方法。 在文献 2 l q b ，c o e l l o 将约束处理技术划分为如下的五类：1 ) 惩罚函数法；2 ) 特 殊的表示和操作；3 ) 修补算法；4 ) 目标函数和约束条件分离法；5 ) 混合算法。 进化算法作为搜索机制已被广泛地运用于处理约束优化问题。除进化算法外， 基于群智能的搜索方法( 例如粒子群优化【3 】、文化算法1 4 】、免疫算法【5 】等) 和模 拟退火算法【6 】也常常用于处理约束优化问题。 本文认为，在约束优化进化算法设计方面存在以下几个问题： 1 设计合理的个体选择和替换准则。约束优化进化算法具有两个明确的目 标：1 ) 快速靠近或进入可行域；2 ) 找到全局最优解。为了达到第一个目标，大 多数约束优化进化算法对可行解都存在着一定的偏好，即可行解在一定程度上优 于不可行解。本质上这类算法都属于惩罚函数法。值得注意的是，一旦对可行解 存在人为的偏好( 尽管这种偏好有时非常小) ，那么群体将很难维持可行解与不 可行解之间的平衡，此时算法容易陷入局部最优，因而难以达到第二个目标。尽 管通过提高算法的搜索性能或增加群体的多样性可以缓解这种情况，但不能从根 本上克服。 2 有效利用不可行解。在约束优化进化算法中，不可行解具有非常重要的 作用，特别是当全局最优解位于可行域边界时。目前，越来越多的研究者已经意 识到了不可行解的重要性。但是，他们大都认为不可行解在群体进化过程中的作 用仅仅是增加群体的多样性。事实上，在理想的情况下，不可行解应具有以下两 个特点：1 ) 当可行域在整个搜索空间中所占比例较小时，利用不可行解特别是 与边界距离较小的不可行解，群体可以从不同方向迅速向可行域靠近：2 ) 当全 局最优解位于可行域边界时，不可行解应辅助可行解找到全局最优解。 3 处理等式约束条件。为了找到可行解，现有的算法都是将等式约束条件 转换为不等式约束条件来处理。例如对于等式约束条件矗( i ) = 0 ，通常转换为不 等式约束条件 ( i ) 一6 o 和一h ( i ) 一6 s 0 ，其中占为一个很小的正数。值得注意 的是，上述转换使得可行域的拓扑结构发生了显著变化，而且这种变化随着万的 取值而改变。显然，当可行域发生变化时，全局最优解也可能发生变化，因而上 述转换对算法的性能存在着直接的影响。 4 设计高效的进化算法。如上所述，约束优化进化算法应由约束处理技术 硕士学位论文第一章绪论 和进化算法两部分组成。值得注意的是，这两部分并不能够随意的结合，也就是 说，两者应该精心设计，相互匹配才能使所设计的算法兼顾效率和有效性。当约 束处理技术确定之后，采用怎样的搜索机制显得尤为重要，特别是当适应值场景 和可行域拓扑结构非常复杂时。然而，现有的约束优化进化算法中所采用的进化 算法都较为简单。 1 3 本论文的主要工作 本章对利用进化算法处理约束优化问题进行了简要的叙述，并指出了其存在 的一些问题。本论文的研究内容主要围绕如何设计有效的约束处理技术和高效的 进化算法两方面展开，各章节的具体安排如下： 第二章对进化计算的起源、发展及三个主要分支作了简要回顾。进化计算是 一个多学科相融合、具有很高实用价值的研究领域。其它学科研究的深入为进化 计算的发展也带来了新的动力，分化出了许多新的研究分支，如概率进化计算、 免疫进化计算、克隆进化计算、协同进化计算等。 第三章对约束优化问题、多目标优化问题进行了描述，并对约束处理技术的 国内外研究现状进行了综述。 第四章提出了一种基于多目标优化技术的约束优化进化算法。该方法的主要 特点是利用多目标优化思想比较和选择个体，并将三个基于群体的算法发生器模 型与一个不可行解存档和替换机制相结合。此外，单形交叉作为惟一的重组算子 用来协调算法的勘探和开采能力。最后，通过1 3 个标准的测试函数对新算法的优 化性能进行了测试。仿真实验结果表明，新算法具有很强的鲁棒性和通用性。同 其它算法相比，新算法不仅能够搜索到所有测试函数的最优解，而且在解的质量 等方面均显著占优。值得一提的是，新算法可以直接用于处理等式约束条件，克 服了长期以来将等式约束条件转化为不等式约束条件处理所引发的一些问题。 第五章提出了一类求解约束优化问题的新方法混合约束优化进化算法 m c o e a 。它将多目标优化思想与全局搜索和局部搜索模型有机地结合起来。作 为全局搜索模型，基于联赛选择的小生态遗传算法，利用p a r e t o 优超关系接受具 有相似性的父代个体和子代个体中的优胜者进入下一代群体。此外，该算法采用 一个并行的局部搜索操作对群体实施聚类分割和多父体交叉产生子代群体。接 着，子代群体中的非劣个体用于淘汰父代群体中的劣于个体。最后，该算法还提 出了一个最好的不可行解替换机制。对1 3 个标准测试函数的实验结果表明，该算 法在鲁棒性、通用性、优化效率等方面显著优于其它约束优化进化算法。 最后对本论文的工作进行了总结，提出了进一步的研究方向。 硕士学位论文 第二章进化算法 第二章进化算法 进化算法( e v o l u t i o n a r ya l g o r i t h m s ，e a s ) 是一种模拟生物进化过程与机制 来求解问题的自适应人工智能技术。它的核心思想源于这样的基本认识：从简单 到复杂、从低级到高级的生物进化过程本身是一个自然的、并行发生的、稳健的 优化过程，这一过程的目标是对环境的适应性，生物种群通过“优胜劣汰”及遗 传变异来达到进化的目的。 进化算法就是基于这种思想发展起来的一类随机搜索技术，它们是模拟由个 体组成的群体的学习过程，其中每个个体表示给定问题搜索空间的一点。进化算 法从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最优解 或满意解。在进化过程中，从一组解出发，采用类似于自然选择和有性繁殖的方 式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群体。 采用进化算法求解优化问题的一般步骤为： 1 ) 随机给定一组初始解； 2 ) 评价当前这组解的性能； 3 ) 若当前解满足要求或进化过程达到一定代数，计算结束： 4 ) 根据2 ) 的评价结果，从当前解中选择一定数量的解作为基因操作对象； 5 ) 对所选择的解进行基因操作( 交叉和变异) ，得到一组新解，转到2 ) ； 目前搜索方法可以分成三类，即枚举法、解析法和随机法。枚举法是指枚举 出可行解集合内的所有可行解，以求精确最优解。对于连续函数，需对其进行离 散化处理。但许多实际问题所对应的搜索空间很大，因此该方法的求解效率非常 低。解析法在求解过程中主要使用目标函数的性质，如一阶导数、二阶导数等。 这一方法又可以分为直接法与间接法。直接法根据目标函数的梯度来确定下一步 搜索的方向，从而难于找到整体最优解，而间接法则从极值的必要条件出发导出 一组方程，然后求解方程组。但是导出的方程组一般是非线性的，它的求解是非 常困难的。随机法在搜索过程中对搜索方向引入随机的变化，使得算法在搜索过 程中以较大的概率跳出局部极值点。随机法又可分为盲目随机法和导向随机法。 前者在可行解空间中随机地选择不同的点进行检测，后者以一定的概率改变当前 的搜索方向，在其它方向上进行搜索。 进化算法是一种随机化搜索方法，在初始解生成以及选择、交叉与变异等遗 传操作过程中，均采用了随机处理方法。与传统搜索算法相比具有以下不同点： 1 ) 进化算法不是直接作用在解空间上，而是利用解的某种编码表示； 4 硕士学位论文第二章进化算法 2 ) 进化算法从一个群体即多个点而不是一个点开始搜索，这使它能以较大 概率找到整体最优解： 3 ) 进化算法只使用解的适应性信息( 即目标函数值) ，并在增加收益和减 少开销之间进行权衡，而传统搜索算法一般要使用导数等其它辅助信息； 4 ) 进化算法使用随机转移规则而不是确定性的转移规则。 进化算法和传统的算法相比最主要的特点体现在下述两个方面： 智能性 进化算法的智能性包括自组织、自适应和自学习等。应用进化算法求解问题 时，在确定了编码方案、适应值函数和遗传算子以后，算法将利用进化过程中获 得的信息自行组织搜索。进化算法的这种智能性特征同时赋予了它具有根据环境 的变化自动发现环境的特性和规律的能力。 本质并行性 进化算法的本质并行性表现在两个方面：一是进化算法是内在并行的，即进 化算法本身非常适合大规模并性。二是进化算法的内含并行性，由于进化算法采 用种群的方式组织搜索，因而它可以搜索解空间内的多个区域，并相互交流信息。 进化算法主要包括遗传算法( g e n e t i ca l g o r i t h m s ，g a s ) 、进化策略 ( e v o l u t i o n a r ys t r a t e g i e s ，e s ) 和进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，g p ) ， 它们的应用范围十分广泛，尤其适用于处理传统搜索方法解决不了的复杂问题和 非线性问题【7 1 。 2 1遗传算法 遗传算法可以说是最广为人知的进化算法，早在6 0 年代，美国m i c h i g a n 大 学的j h o l l a n d 在从事如何建立能学习的机器的研究中注意到，学习不仅可以通 过单个的生物体的适应而且通过一个种群的许多代进化适应也能发生。受达尔文 进化论适者生存的启发，他逐渐认识到在机器学习的研究中，为获得一个好的学 习算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策略的 群体的繁殖。考虑到其研究思想起源于遗传进化，h o l l a n d 就将这个研究领域取 名为遗传算法【引。d ej o n g 首先将遗传算法应用于函数优化，为这一应用技术奠 定了基础【9 1 。目前，人们对原来的遗传算法，或称为标准遗传算法进行了大量的 改进，使遗传算法应用于更广泛的领域。不过这些改进算法中有许多与下面将要 讨论的遗传算法有很大的差别，以至使它们与别的进化算法的界限变得模糊不 清。非标准的遗传算法主要有d w h i t l e y 的g e n i t o r 系统【”j 、j g r e f e n s t e t t e 的 s a m u e l 系统【l l 】、l d a v i s 的遗传算法【1 2 】、z m i c h a l e w i c z 的进化程序【1 3 i 、k o z a 的遗传编程【1 4 j 和l e s h e l m a n 的c h c 算法【1 5 j 。 硕士学位论文 第二章进化算法 ( 1 ) 表示法和适应值度量 标准遗传算法作用于确定长度的二进制位串上，即，= 0 ，1 ) 5 。对于伪布尔目 标函数，这种表示法可以直接采用。为了解决函数优化的问题 ，：丌： 虬，v ，】专r ( 1 ) 个个 体重组形成的一个子代替换掉变异后最差的父辈个体。s c h w e f e l 在此基础上提出 了( + 旯) e s 和( ，五) 一e s ，这两种策略( 尤其是后者) 在进化策略中占据着 重要地位【2 2 】，这里将描述它们最一般的形式。 ( 1 ) 表示法和适应值度量 在进化策略中，搜索点是朋维向量工r ”，个体的适应值等于其目标函数值， 即巾位) = f ( x ) ，其中x 是个体口的目标变量部分。此外，每个个体可以包括至 多n 个不同的方差c 。= 辞( f l ，h ) ) 和至多n 0 1 ) 2 个协方差 c 。( f 1 ，胛一1 ，j i + 1 ，”) ) ，从而至多w = ”- + 1 ) 2 个策略参数可以和目 标变量组合在一起构成一个个体口i = r “”。不过，一般只考虑方差，从而 口i = r “，有时甚至对所有目标变量只用一个共同的方差，这时口，= r ”1 。 ( 2 ) 变异 在进化策略中，全体口= ( x ，盯) 在变异算子作用下变为口= ( x ，盯) ，其中 盯。= q e x p ( r n ( 0 ，1 ) + r m ( 0 ，1 ) ) ， ( 2 - 1 0 ) 了。f 玉+ n ( 0 , c r ，) ，i = 】， 。 ( 2 1 1 ) 其中n ( 0 ，1 ) 表示具有期望值为0 ，标准偏差为1 个正态分布随机变量，r 和r 。是 算子集参数，分别定义整体和个体步长【2 ”。 ( 3 ) 重组 在进化策路中，重组算子，。：i u 斗，可以按下列方式产生一个个体： x “无重组 x s , i 或x 直接重组 ( 2 1 2 ) x s ，+ 口o 一x s j ) 加权平均重组 下标s 和r 指从p ( f ) 中随机选取的两个父辈个体，0 0 , i 】为均匀随机变量。 ( 4 ) 选择 在进化策略中，选择是按完全确定的方式进行。( ，a ) 一e s 是从a 个子代个 体集中选择( 1 a ) 个最好个体；( + 五) 一e s 是从父辈和子代个体的并集中 选择个最好的个体。虽然( a + 旯) 一e s 保留最优的个体能保证性能单调提高， 硕士学位论文 第二章进化算法 但这种策略不能处理变化的环境，因此，目前选用最多的还是( 从五) e s ，研究 表明比率五“1 7 是最优的2 3 1 。 从上面的讨论，我们可以得到( + 兄) 一e s 和o ，a ) 一e s 的形式描述： t = 0 ； 初始化p ( o ) = ( 0 ) ，瑾。( 0 ) ) i 一； 度量p ( o ) ： 巾( 口。( 0 ) ) ，巾( 口。( 0 ) ) ) ，其中m ( 口。( 0 ) ) = f ( x 。( o ) ) ： w h i l e ( ( p ( f ) ) r ) d o 重组：口+ 女( t ) = r ( p o ) ) ，v k ( 1 ，一，a ) ： 变异：口”t ( ，) = m 1 t ( ，) ) ，v k ( 1 ，a ) ； 度量：p ”( ，) = 口”- ( f ) ，一，口”，( ) ) 巾( 口。( f ) ) ，一，( 口”，( f ) ) ) ； 其中中 “t ( f ) ) = f ( x ” ( f ) ) ； 选择：p ( f + 1 ) = i f ，五) 一e s t h e n 5 ( p ，2 ) ( p ( f ) ) ； e l s e 5 ( p + ) ( p ( t ) up ”( f ) ) ； r = f + 1 ： e n d 1 0 硕士学位论文第三章约束优化问题、多目标优化问题及基于进化算法的约束处理技术 第三章约束优化问题、多目标优化问题及基于进化算法的 约束处理技术 3 1约束优化问题描述 约束优化问题( c 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 ，c o p s ) 是工程应用领域 经常会遇到的一类数学规划问题。不失一般性，一个非线性规划问题( n o n l i n e a r p r o g r a m m i n g ，n l p ) 可描述为： m i n i m i z e 厂( i ) i = ( x l ，x 2 ，一，x 。) 9 ” s u b j e c t t og ，( 叠) 0 ，= 1 ， h ( 王) = 0 ，= ，+ 1 ，m 这里，i q e s 为决策向量，q 为可行域，s 为决策空间。一般地，s 为吼”中 的r l 维长方体：1 ( i ) x ，u ( i ) ，l ( i ) ，u ( i ) 为常数，i = 1 ，n 。厂( i ) ，g ，( i ) ，h ，( i ) 均为吼“上的n 元函数，厂( i ) 为目标函数，g ，( 王) 0 为第_ ，个不等式约束条件， ，( 王) = 0 为第个等式约束条件。，表示不等式约束条件的个数，( m - i ) 表示等 式约束条件的个数。 图3 - 1 搜索空间s 及其可行域q 定义3 1q 为决策空间s 的可行域( f e a s i b l er e g i o n ) 当且仅当 q = 忙s l g ( i ，) o ，= 1 ，z ； ( i ) = o ，_ ，= ，+ 1 ，m 。 q 在s 上的补集即为不可行域，可行域内的点称为可行解，不可行域内的点 称为不可行解。如果任一不等式约束条件满足g ，( i ) = 0 ( ， 1 ，f ) ，则称 g ，( i ) 在i 处活跃( a c t i v e ) 。显然，所有的等式约束条件 ，( i ) ( ，= l + 1 ，m ) 硕士学位论文第三章约束优化问题、多目标优化问题及基于进化算法的约束处理技术 对于可行域q 中的任意点均活跃。 3 2多目标优化问题描述 因为本文中涉及到的许多算法都基于多目标优化技术，所以下面给出了多目 标优化问题的相关描述和多目标优化中的四个相关定义。不失一般性，考虑下列 n 个决策变量和m 个目标函数的多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o n p r o b l e m s ，m o p s ) m i n i m i z e y 一= ，( i ) = ( z ( i ) ，一，厶( i ) ) 其中，i = ( x l 一，x 。) j c 婀”为决策向量，z 为决策空间，歹y c9 t 为目标 向量，为目标空间。 定义3 2p a r e t o 优超( p a r e t od o m i n a n c e ) 向量厅= ( u l ，一，“。) p a r e t o 优超向量i = ( ”l ，一，v 。) ，记为厅 哥，当且仅当1 ) v i 1 , - - 7 m 满足u ，v l ：2 ) 可 1 ，m ) 满足“， v ，。 此时，也称向量舌劣于( d o m i n a t e d b y ) 向量厅。若向量i 与向量厅不存在p a r e t o 优超关系，则称它们非劣( n o n d o m i n a t e d ) 。 定义3 3p a r e t o 最优解( p a r e t oo p t i m a l i t y ) 向量元x 称为x 上的p a r e t o 最优解，当且仅当、j i ，x 使得哥 厅，这里， 厅= ，( i 。) = ( “。，一，“。) ，哥= ( i ，) = ( v 。，v 。) 。 定义3 4p a r e t o 最优解集( p a r e t oo p t i m a ls e t ) 对于给定的多目标优化问题厂( i ) ，p a r e t o 最优解集( p + ) 定义 为：p = i 。y l 、了i 。x ，i 孬) 。 p a r e t o 最优解集中的个体也称为非劣个体( n o n d o m i n t e di n d i v i d u a l ) 。 定义3 5p a