（计算机应用技术专业论文）求解多目标优化问题的粒子群算法改进及应用.pdf

求解多目标优化问题的粒子群优化算法改进及应用 摘要 工程设计问题一般都具有多个设计目标，这些相关联的目标之间通常存在着内在冲突。近年 来多学科优化技术蓬勃发展，在理论和实际应用中都取得了很大的成功，其核心之一就是多目标 优化技术。因此开展多目标优化技术研究在学术上和工程实际中都具有重大意义。 本文主要是将多且标优化问题和粒子群优化算法、混淹优化算法相结合，提出了2 个比较有 效的求解多目标优化算法和一个尝试性的应用：一是提出了基于双混沌优化搜索的混台粒子群优 化算法，能够更好地处理多目标优化适应度函数的选取问题，能够避免算法在搜索空间中所进行 的盲目收缩有利于算法向p a r e t o 最优解方向进化：二是提出了基于多目标决策协调模型的粒子 群算法，在高维空问的搜索过程中，它能够克服在有限规模的粒子群体之间很难进行p a r e t o 排序 比较或者克服出现所有个体皆有p a r e t o 最优解而导致后代个体无法实施正常选优的缺点；这些改 进粒子群优化算法适合解挟复杂的大规模多目标优化问题，为大中型多目标优化问题提供了有效 的解决方案。三是尝试性将粒子群优化算法应用到油气混输管褐多目标参数优化设计中并结合 一个实际的例子，采用基于双混沌优化机制算法进行优化，和已有的算法得到的结论进行比较， 取得了比较满意的结果。 粒子群优化算法是一种新兴的优化工具，能够大大减轻复杂的大规模多目标优化问题的计算 负担，便于实际应用，可以得到许多比较好的p a r e t o 最优解，并能够很方便地处理大型多目标优 化设计问题。通过数值仿真实验验证了改进粒子群优化算法的正确性和有效性。 关键宇：粒子群算法；双混沌优化；多目标决策协调模型；混沌优化；多目标优化 n t h ep a r t i c l es w a r mo p t i m i z a t i o n sa m e l i o r a t i o no ft r a n s a c t i n g m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m a n di t sa p p l i c a t i o n a b s t r a c t e n g i n e e r i n gd e s i g np r o b l e m sg e n e r a l l yi n v o l v es e v e r a ld e s i g no b j e c t i v e s a m o n gt h e s er e l a t e d o b j e e t i v e ，i t sp o t e n t i a l l yc o n f l i c t i n gi ne t a t u r e m u l t i d i s c i p l i n a r yd e s i g no p t i m i z a t i o n ( m i x ) ) h a s g r o w nt ot h ep o i n to f g a i n i n gn e a ru n i v e r s a lr e c o g n i t i o ni ni t sa b i l i t yt ol e a dt ob e t t e rd e s i g n s ，b o t hi nt h e a r e a so fa c a d e m i cr e s e a r c ha n dp r a t i c a la p p l i c a t i o n a tt i h e a r to fm d op r o b l e mi sam u l t i - o b j e c t i v e o p t i m i z a t i o np r o b l e m t h e r e f o r e ，i ti sr e a l l yv a l u a b l et or e s e a r c hm u l t i - o b j e c t i v eo p t i m i z a t i o nt h e o r y a n dt e c h n o l o g i e s t h i sr e s e a r c hf o c u s e so ns y n t h e s i z i n gm u l t i - o b j e c t i v eo p t i m i z a t i o nw i t hp a r e = t op a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) a n dc h a o so p t i m i z a t i o nt od e v e l o pt w om o r ee f f e c t i v em u l t i - o b j e c t i v eo p t i m i z a t i o n m e t h o & a n do n e 仃y i n ga p p l i c a t i o n ：f i r s td e v e l o p e da l le f f e c t i v eh y b r i dp s ob a s e do nt w o c h a o s o p t i m i z a t i o f l w h i c hc o u l dd e a lw i t hs e l e c t i o no ff i t n e s s v a l u e o fm u l t i o b j e c t i v ef u n c t i o n ，a v o i d i n g b l i n d n e s ss e a r c hi nt h er e s e a r c hs p a c ea n di ti sp r o p i t i o u st oa r i t h m e t i ce v o l v et o w a r d st h eb e s ta r l s w e r o fp a r e t o ；n e x td e v e l o p e da ne f f e c t i v eh y b r i dp s ob a s e do i lh a r m o n i o u sm o d e lo fm u i t i - o b j e c t i v e d e c i s i o n - m a k i n g , w h t c hc o u l dc o n q u e rt h ed e f e c t ：t h es c a l e - l i m i t e dp a r t i c l es w a r md i t y r e u l t i l yp r o c e s s p a r e t oc o m o s i t o r sc o m p a r t i o ni nt h eh i g h - d i m e n s i o ns p a c ea m o n gt h e mo ra l lt h ei n d i v i d u a lh a v et h e b e s ta l s w e ro fp a r e t o ，a tl a s tn om e a s u r ep r o c e s s e sn a t u r a l l ys e l e c t i o no fn e x ti n d i v i d u a l t h em o d i f i e d a r i t h m e t i ci sa p p l i c a b l ea n de f f e c t i v ei nt h es c a l ec o m p l e xe n g i n e e r i n gm 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 ；p r o v i d i n gam o r ee f f e c t i v es o l u t i o nf o rt h eb i g s c a l em u f t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m s t h i r d l y , w et r yt os o l v et h eo p t i m a ld e s i g no f t h eo i l g a sg a t h e r i n gn e t w o r kp a r a m e t e rb yu s i n gp a r t i c l e s w a r mo p t i m i z a t i o n t h e ns o l v ea l la c t u a le x a m p l eb yu s i n gp a r t i c l es w a l i l lo p t i m i z a t i o nw i t hd o u b l e - c h a o so p t i m i z a t i o n n u m e r i c a lr e s u l t ss h o wt h a tt h i sa l g r i t h mi sf e a s i b l ea n dc a ng e tm o r ep r e c i s e r e s u l t st h a no t h e rm e t h o d s p s oi sar i s i n go p t i m i z a t i o nt o o l ，w h i c hc o u l d r e d u c ec a l c u l a f i v eb u r t h e nf o r b i gs c a l e m u t i l - o b j e c t i v eo p t i m i z a t i o np r o b l e m sa n dd e a lw i t hi t , i tg e tm o r ep e r f e c tb e t t e ra n s w e l - o f p a r e t oa n d e x p e d i e n t l ya c t u a la p p l y t h er e s u l t so f t e s ts h o wt h a tt h eh y b r i dp a r t i c l es w a m io p t i m a z i t o n i se f f e c t i v e a n dc o r r e c t k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；d o u b l e - c h a o so p t i m i z a t i o n ；h a r m o n i o u sm o d e lo f m u i t i - o b j e c t i v ed e c i s i o n - m a k i n g ；c h a o so 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 1 1 1 学位论文独创性声明 本人所呈交的学位论文是我在指导教师的指导下进行的研究工作及取得的 研究成果据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已 经发表或撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名：壹生墨日期：垒幽丝日 学位论文使用授权声明 本人完全了解大庆石油学院有关保留、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容 编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版。保密的学位论文 在解密后适用本规定。 学位论文作者张卉鑫翠 日期：2 眇7 缉歹目，2 目 导师签名：剖罕莽 日期： 洳7 弓t 2 刨额点摘要 本文擞嚣是将多目标优化问题和粒予群优化算法、决策的协调模型理论、混沌优化算法相结 合。提出了2 个较有效的求解多目标优化算法和一个尝试性应用： 1 ) 撵掇了基于双混建撬琵授索豹游会粒子嚣优纯算法，能够较好薅缝理多曩标钱像适痘度蠡 数的选取闷题，避免算法在援索空间中所进行的盲目收缩，有利于算法向p a r e t o 最优解方向进化； ( 2 ) 提出了基于多目标决策协调模型的粒子群算法能够克服问题空间的维数高而谯安际操作对 有限规模的粒子群俸个体之闻撮难进行搀序比较戴孝克骚出现掰窍个体皆有p a r e t o 最优解，最 终无法实施芷常魏盖代令俸建优豹缺点； ( 3 ) 娥盾将改进的粒予群优化算法和标准粒子群算法尝试性地应用到油气混输管嘲多目标参 数优化设计巾，并结合一个实际的例子，采用这2 种算法进行优化，和已有的算法得到的结论进 行笼较，敬褥7 毙较满纛戆维莱。 l v 大庆 j 油学院硕十研究生学位论文 引言 群体智能算法是人工智能的一个重要的分支，是一个多学科交叉的领域，吸引着 大批包括生物、物理、数学以及计算机科学等许多学科的研究人员运用不同的技术手 段对之进行深入研究，并且群体智能优化算法在许多领域有着广阔的应用前景。因此， 对群体智能算法进行研究不仅具有重要的理论意义，而且还具有重要的实用价值。 优化技术是一种以数学为基础，用于求解各种工程问题最优解的应用技术。它广 泛应用于工业、农业、国防、工程、交通、化工、能源、通信等许多领域。国内外的 应用实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降 低、资源的合理利用及经济效益的提高等均有显著的效果，而且随着处理对象规模的 增大，这种效果也更加显著，这对国民经济的各个领域来说，其应用前景无疑是巨大 的。粒子群优化算法是一种较新的群体智能优化算法，类似于遗传算法，但没有交叉 和变异等遗传操作，也无需二进制编码，只有位置更新和速度更新算子，而且对目标 函数没有连续、可微等要求，算法简单，易于实现，因此具有广阔的应用前景。 很多实际的工程问题进行数学建模后，都可将其抽象为一个数值函数优化问题。 由于问题种类的繁多，影响因素的复杂，所要优化的函数会显示出不同的数学牲征， 如有的是连续的，而有的是离散的，有的是凸函数，有的是凹函数，有的是单峰值的， 有的是多峰值的，而更多的情况则是不同数学特征的组合。尽管粒子群优化算法是数 值优化的一强有力的工具，但它也不是万能的，当多目标目标优化函数规模大且较复 杂时，算法也易于陷入局部极小，且收敛速度慢，求解精度不高，这些问题都有待于 进一步的研究。 根据以上两个方面，本文主要研究粒子群优化算法在多目标优化中的2 个改进及 一个尝试性地应用。下面是本文研究的三个主要内容： 第一个改进是针对粒子群优化算法在整个多目标优化搜索过程中存在盲目搜索、 计算量大、易陷入“早熟”收敛以及得到较少p a r e t o 最优解或得到的p a r e t o 最优解分 布不均匀的缺点，提出了基于双混沌优化搜索机制的混合粒子群优化算法。新算法的 核心思想包括3 个部分：最佳进化方向策略、p a r e t o 最优解更新策略和基于双混沌优 化机制搜索策略。最佳进化方向策略是指根据生物总是向着有利于自己的方向进化而 给出在多目标优化中适应度函数的选取策略，能够保证最终解在p a r e t o 最优解前端分 布的均匀性和多样性；p a r e t o 最优解更新策略是指在多目标优化搜索过程中，采用了 p a r e t o 最优解作为选择解的判定条件，使得到的p a r e t o 最优解在迭代过程中不断更新， 以便得到更好的p a r e t o 最优解或者得到的解接近p a r e t o 最优解前端，有利于算法向 p a r e t o 最优解进化：基于双混沌优化机制策略是指为了克服优化方法在缩小优化变量 引言 的搜索空间前所进行的盲目收缩而提出的，该方法利用两种不同的混沌机制同时在搜 索空间进行独立搜索，根据两者搜索最优点的距离情况来缩小搜索空间，同时算法也 给出了混合粒子群算法搜索结束的条件，避免了针对不同的优化函数选择不同搜索 参数和算法克服盲目搜索的缺点，从而得到更多的p a r e t o 最优解，也减少了计算量， 提高了搜索效率，使算法具有更好的通用性，仿真实验验证混合算法不仅能够求得多 目标优化问题的数目较多、分布较广泛的p a r e t o 最优解，而且具有较好的收敛速度， 能克服经典多目标优化算法的缺陷。 第二个改进是针对单纯p a r e t o 粒子群优化算法很难解决目标数目很多的高维多目 标优化问题，提出了基于多目标决策的协调模型粒子群优化算法，它使进化群体按协调 模型进行偏好排序，即将运筹学多目标决策的协调模型引入粒子群迭代过程中。算法的 特点在于当代群体进行个体排序时，采用一种比p a r e t o 优于关系要弱的级别不劣于关 系，改变了传统的基于p a r e t o 优于关系来比较个体的优劣。实验结果表明提出的算法 对解决高维多目标问题是行之有效的。另外，从理论上通过数学解析方法和计算机模拟 验证了其具有较快的收敛速度。 最后，将标准粒子群优化算法和基于双混沌优化搜索机制的混合粒子群优化算法 尝试性地应用到了集输管网参数优化中。首先对集输管网建立正确的优化模型，然后 采用这2 种算法对其进行优化，并和已有的算法所得结论进行比较，得到了较为满意 的结果。 综上所述，本文提出的2 个改进的算法和一个尝试性应用具有一定的理论意义和 实用价值。 2 大庆右油学院硕上研究生学位论文 第一章群体智能优化算法 随着人类生存空间的扩大以及认识与改造世界范围的拓宽，人们对科学技术提出 更新和更高的要求，尤其是在多目标优化的人工智能与控制领域，不断涌现出非线性、 不可微甚至混杂的系统体系，经典的多目标优化方法已无能为力，群体智能优化算法 正是在这种背景下产生的，它的最大特点就是不需要建立问题本身精确的数学模型， 适合于解决那些很难建立有效的形式化模型和用传统人工智能技术难以有效解决甚 至无法解决的问题。目前，国内外相继涌现出大量与之相关的文献，介绍了各种基于 群体智能优化算法的机理、实现模型以及相关的理论研究。 1 1 群体智能优化算法的研究及发展现状 群体智能是指众多无智能的简单个体组成的群体，通过相互间的简单合作表现出 智能行为的特性。自然界中动物、昆虫常以集体的力量进行觅食生存，在这些群落中 单个个体所表现出的行为是简单缺乏智能的，而且各个个体的行为是相同的，但由个 体组成的群体则表现出一种有效的、复杂的智能行为，这是个体难以做到的。群体智 能以群体为主要载体，通过它们之间的间接或者直接合作进行并行式问题求解。 目前研究群体智能的方法多是从多a g e n t 系统的观点来进行的。该观点假定多 a g e n t 系统中的每个个体能够感知环境，包括自身和其它a g e n t 对环境的改变，a g e n t 问通过环境变化来彼此间接通讯。而且在一些研究中将人类社会中的一些智能行为移 植到群体智能中去。文献 1 从多a g e n t 系统的观点研究讨论了群体智能的性能特点， 认为群体智能是由一组可相互通讯、相互影响、可移动的a g e n t 组成，每个a g e n t 只 能存取局部信息，而没有中心控制和具有全局观点的个体，是一种分布式的计算环境。 当前最典型的群体智能优化算法有遗传算法、蚁群算法和粒子群算法，为解决优 化问题提供了新的思维模式，这里根据课题的需要对两种群体智能算法做简单介绍。 1 1 1 遗传算法 遗传算法起源于对生物系统行为特征的计算机模拟研究。2 0 世纪6 0 年代，美国 密执安大学的h o l l a n d 教授及其学生们受到生物模拟技术的启发，提出了一种基于生 物进化机制的适合于复杂系统优化计算的遗传算法。 2 0 世纪6 0 年代h o l l a n d 教授提出了遗传算法的基本定理模式定理( s c h e m a t h e o r e m ) ，奠定了遗传算法的理论基础。 2 0 世纪7 0 年代h o l l a n d 教授又提出了基于遗传算法的机器学习的新概念，并实 3 第1 章群体智能优化算法 现了第一个基于遗传算法的机器学习系统一分类器系统( c l a s s i f i e rs y s t e m s ) ，为分类 器系统构造出了一个完整的框架”1 。 1 9 6 7 年，h o l l a n d 教授的学生b a g l e y 在其博士论文中首次提出了“遗传算法”一 词0 1 ，他发展了复制、杂交、变异、显性、倒位等遗传算子，在编码上使用了双倍体 的编码方法。 1 9 7 5 年，d ej o n g 建立了遗传算法的工作框架，得到了一些重要且具有指导意义 的结论“1 ，同时，他还建立了著名的d ej o n g 五函数测试平台，定义了遗传算法性能 的在线指标和离线指标。1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计及 自动生成，提出了遗传编程( g e n e t i cp r o g r a m m i n g ) 的概念0 1 。 9 0 年代，j o h n r k o z a 出版了专著遗传编程，提出了遗传编程的概念，并成功 地把遗传编程的方法应用于人工智能、机器学习等领域。从而进一步发展了遗传算法。 我国有关遗传算法的研究起步较晚，但从2 0 世纪9 0 年代以来一直处于不断上升的时 期，特别是近年来，对遗传算法的研究也取得了令人瞩目的成果“”。 1 1 2 粒子群优化算法 粒子群优化算法【1 6 】( p a r t i c l es w a r mo p t i m i z a t i o n ) 是1 9 9 5 年由美国的k e n n e d y 和e b e r h a r t 受鸟群觅食行为的启发而提出的。由于粒子群算法概念简单，易于实现， 在近十年内，得到了很大的发展，目前已被“国际演化计算会议”列为讨论专题之一。 但由于粒子群优化算法建立在对社会模型仿真的基础上，因而在方法提出初期并没有 严格的数学基础，随着c l e r c 和v a n d e n b e r g h 等人研究成果1 1 7 的公开发表，粒子群优 化算法的严格数学基础正在逐步建立。 基本粒予群优化算法是函数优化的有力工具，其优点是收敛速度快且需设置的参 数较少；缺点是易陷入局部极小点，搜索精度不高。据此当前典型的改进算法有：自 适应粒子群优化算法、模糊粒子群优化算法【1 8 l 、杂交粒子群优化算法、混合粒子群优 化算法【19 】等等。但是基本粒子群优化算法对离散问题优化却无能为力。1 9 9 5 年k e n n d y 和e b e r h a r t 提出了离散型粒子群优化算法【2 0 1 ，并成功地解决了旅行商问题，从而扩 展了基本粒子群优化算法的应用领域。 目前粒子群优化算法已广泛应用于函数优化、神经网络训练等许多领域。尽管国 内对这一算法研究较晚，但也取得了一系列成果，如文献 2 1 提出了带变异算子的粒 子群优化算法；文献 2 2 结合免疫算法的特点，提出了免疫粒子群算法；文献 2 3 提 出引入梯度信息来影响粒子速度的更新，构造了一种带有梯度加速度的粒子群算法。 4 大庆石油学院硕士研究生学位论文 1 2 两种算法的特点与比较 1 2 1 遗传算法的特点 遗传算法作为一种快捷、简便、容错性强的算法，具有如下特点： 1 、搜索过程不直接作用在变量上，而是作用在对参数集进行编码的个体上。编 码操作使得遗传算法可直接对结构对象( 集合、序列、矩阵、树、图) 进行操作； 2 、搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法， 具有本质的并行性； 3 、遗传算法利用概率转移规则，可以在一个具有不确定性的空间上寻优。与一 般的随机优化方法相比，遗传算法不是从一点出发沿一条线寻优，而是在整个解空间 同时开始寻优搜索，因此可以有效地避免陷入局部极小点，具备全局最优搜索性； 4 、对搜索空间没有任何特殊要求( 如连通性、凸性等) ，只以决策变量的编码作 为运算对象。在优化过程模拟自然界中生物的遗传和进化机理，应用遗传操作，不需 要导数等其他辅助信息，可用于求解无数值概念或很难有数值概念的优化问题； 5 、遗传算法有极强的容错能力。遗传算法的初始串集本身就带有大量的与最优 解相离很远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串： 6 、遗传算法中选择、交叉和变异都是随机操作，而不是确定的规则。因此它是 采用随机方法进行最优解搜索。 除上述特点之外，遗传算法还有一些问题亟待解决： 1 、算法本身的参数优化问题； 2 、如何避免过早收敛； 3 、如何改进操作手段或引入新的操作来提高算法的效率； 4 、遗传算法与其它优化算法的融合问题。 1 2 2 粒子群优化算法的特点 1 、和遗传算法相似，搜索过程也是从一组解迭代到另一组解，采用同时处理群 体中多个个体的方法，具有本质的并行性； 2 、采用实数进行编码，直接在问题域上进行处理，无需转换，因此算法简单， 易于实现； 3 、在优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习的功 能； 4 、是解决连续型优化问题的一个强有力的工具。 算法的缺点是： 第1 章群体智能优化算法 1 、在处理高维的复杂问题时，算法易陷入局部最优； 2 、当问题的规模较大时，算法收敛的速度较慢，且精度不高。 1 2 3 两种算法共同的特点和优点 根据上述，总结两种算法的共同的特点和优点如下： l 、群体中相互合作的个体是分布的( d i s t r i b u t e d ) ，这样更能够适应当前网络环境 下的工作状态； 2 、没有中心的控制，这样的系统具有较强的鲁棒性( r o b u s t ) ，不会由于某一个 或者某几个个体的故障而影响整个问题的求解； 3 、可以不通过个体之间直接通信而是通过非直接通信( s t i m e r g y ) 进行合作，这样 的系统具有更好的可扩充性( s e a l a b i l i t y ) 。不会因为系统中个体的增加而增加系统的通 信开销： 4 、对算法模型稍加修改，就可以应用于其他问题中，具有简单性( s i m p l i c i t y ) ： 5 、易于与其他方法融合。三种算法可以互相借鉴，且很容易与多种启发式算法 融合以改善算法的性能。 1 3 群体智能优化算法的未来发展方向 群体智能优化算法是一类新型进化算法，其主要特点是群体搜索策略和群体之间 的信息交换。这类算法对目标函数没有特殊要求，在求解时不依赖于梯度信息，因而 特别适用于传统方法解决不了的大规模复杂问题，具有广泛的应用范围。目前，虽然 群体智能算法已经有了很大的发展，但有很多方面并不完善，从当前发展来看，其未 来的发展方向可归纳为如下几个方面： 1 、算法理论基础的研究。目前除了遗传算法具有一定的数学理论基础和比较完 善的分析方法外，其余算法均是在仿真阶段，尚未提出完善的理论分析和严格的数学 解释，因此学者们将进行深入的理论分析与研究，从而进一步完善发展各算法的性能； 2 、系统框架的构建。几种算法均是基于仿生机理，且具有许多相似的特征。因 此建立统一的系统的算法框架有利于该领域的发展，提高了算法的性能； 3 、各种算法适用范围的研究。任何算法都不是万能的，都有其适用的范围。对 各群体智能算法适用范围的研究，可使算法得到更广泛的应用； 4 、算法的改进。这几种算法都是开放的，可以很好地与其它算法相结合、取长 补短，从而使算法性能得到改善，所以如何构造出高效的混合算法也是一个发展方向。 6 入庆也油学碗顾 研究生学位论文 1 4 小结 本章主要介绍了群体智能算法中的两种典型算法的理论研究及发展情况，并总结 了各自的特点及今后的发展趋势。 7 第2 章多目标最优化问题 第2 章多目标最优化问题 一般说来，科学研究和工程实践中许多优化问题大都是多目标优化问题，多目标 优化问题在很多情况下，各个子目标是相互冲突的，一个子目标的改善有可能会引起 另一个子目标的降低，也就是说，要同时使这多个子目标一起达到最优值是不可能的， 而只能是在它们中间进行协调和折衷处理，使各个子目标都尽可能地达到最优。而且 各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标 优化问题的本质区别在于，多目标优化问题的解并非唯一，而是存在一个最优解集合， 集合中元素称为p a r e t o 最优解或非劣最优解。所谓p a r e t o 最优解，就是不存在比其中 至少一个目标好而其它目标也不劣的更好解，也就是不可能通过优化其中部分目标而 其它目标不至劣化。p a r c t o 最优解集内的元素就所有目标而言是彼此不可比较的。 由于本课题主要研究粒子群优化算法的改进及在多目标优化方面的应用，所以在 本章中，首先给出多目标最优化问题所涉及的一些概念及相应的理论做简单的介绍， 然后是对求解近似p a r e t o 最优解集的一些传统方法的讨论，尤其是它们潜在的缺点， 最后演化方法作为一种现代的优化方法被引出来，它拥有的潜在特性特别适合解决这 一类问题。 2 1 多目标约束优化问题的基本概念及数学形式 顾名思义，多目标优化问题就是同时对多个目标进行优化。它是一类很普遍的问 题，举个例子，考虑移动电话或汽车中复杂的硬件和软件的设计问题，通常，我们要 求系统的开销要最小化，而系统的性能最大化。依赖于这类应用，其他目标例如：可 靠性、能源消耗有时候显得更重要一些。这些问题可以被显示的定义为单独的优化问 题，或是公式化约束，也就是系统的大小不能超过给定的维数。在这里根据课题需要 介绍多目标优化问题的几个概念： 多目标约束优化问题数学形式可以描述为嘲： m i n y = 厂( x ) = ( 厂( ) ，f ( x ：) ，f ( x ，) “p ( 功= x ie j ( x ) o ，= 1 , 2 ，p ( 2 一1 ) 工= ( z l ，x 2 c 矗) x ，y = ( y i ，y 2 ，y 。) y 式中x 为决策向量，y 为目标向量，e j “) 为第，个约束，z 是自变量空间，y 是目 标空问。e ，( x ) s 0 确定了可行解集。 定义1 ( 可行集) 可行集z 定义为自变量工的集合，满足约束 8 大庆石油学院硕叶研究生学位论文 e ( x ) ：x ，= 仁x lf ( j ) 0 ，x ，的相也就是在目标空间的可行域，被称作 巧= f ( x i ) = u 一， ( x ) ) 。 为了不失一般性，这里我们考虑的是最大化问题，对于最小化或是混合的最大最 小问题有着相似的定义。再考虑上面的例子，假设两个目标函数一个是性能 p e r f o r m a n c e ( 石) r 另一个是开销的倒数c h e a p n e s s ( ) ，这两者都需要在尺寸大 小约束( e ) 下被最大化。那么一种最优设计可能是能够达到最优性能而开销又最小 并且没有违反尺寸大小约束的设计方案。如果这样一个解存在，实际上是要解决一个 单目标问题，对于任意一个目标的最优解对另一个目标也是最优的。然而，相应于不 同目标函数的单独优化却是大不相同的，这正是多目标优化问题困难所在。因为这多 个目标是相互冲突的并且不能够被同时优化。相反，必须找到满意的折衷解。在这个 例子中，p e r f o r m a n c e 和c h e a p n e s s 是两个相互冲突的目标：高性能的体系结构潜在的 会增加开销，而廉价的体系结构通常只能提供较底的性能。依赖于市场需求，一个中 间解( 中间性能，中间开销) 可能是合适的折衷解。显然，对于多目标优化问题，最 优的概念需要重新定义。 在单目标优化问题中，按照目标函数可行集是全序的：对于两个解a , b x ，或者 厂 ) 歹( 6 ) 或f ( b ) 2 f ( a ) 。求解的目标是找到函数，的最大值所对应的解。然而，当 考虑几个目标的时候，情况又发生了变化：一般而言，x ，不是全序而是偏序的，这 一点可以用图2 - 1 左边的图解释。由b 点所代表的解要优于由c 点所代表的解：因 为它表示更高的性能和更低的开销。如果仅仅是在一个目标上进行优化那是很容易的 事情，例如c 点和d 点，尽管开销相等，c 点比d 点有更好的性能。为了在数学上 表达这种状况，大小关系= ，2 ， 与单目标问题类似的，也被扩展到多目标向量的方 式上。 定义2 对于任意两个目标向量“和v ， 甜= v 矿v j 1 ，2 ，k ：“，= v v i f v i l ，2 ，k ：“j v f uv矿u v a “v s 和 c ，c d ，b d 。然而当我 们比较b 和e 时，我们不能说哪一个更优，因此b ! ) e ，e ! b 。尽管与点e 关联的解 第2 章多目标最优化问题 更廉价，但是它的性能要比由b 点所表示的解的性能更高。因此，在多目标优化问题 中，按照关系，自变量向量a ，b 有三种可能的关系：f ( a ) ，( 6 ) ，f ( b ) f ( a ) ， 八口) ! ( 6 ) ，( 6 ) ! ( 口) 。在这里，我们用下面的符号和术语来区别不同的情况。 定义3 ( p a r e t o d o m i n a n c e ) 对于任意两个自变量8 和b 。 a 6 ( 口d o m i n a t e s6 ) i ff ( 口) ( 6 ) a b ( 口w e a k l y d o m j n a t e s6 ) i ff ( a ) 厂( 6 ) 4 b ( 口i si n d i f f e r e n tt o6 ) i f ( 口) ! j r ( 6 ) ，( ! 厂( 口) 基于p a r e t o 大小的概念，我们引出了多目标优化问题的最优标准。参考图2 - 1 右边， 在b ，c ，d ，e 之间a 点是唯一的：它相应的自变量a 没有被任何其他的自变量所支配。 这也就意味着在某种意义上口是最优的，在任何一个目标上它都不能继续得到优化而并 没有引起任何其他任何一维目标上的劣化。这些解被称为p a r e t o 最优解，有时也称为非 劣最优解。 i - t - f - i i ； - 图2 - l 定义4 ( p a r e t o o p t i m a l i t y ) 一个自变量向量工x i ，考虑x ，的一个子集a ，如 果1 3 a a ：a x , x 被称作是p a r e t o 最优的。 在图2 1 右边中白色的点表示p a r e t o 最优解。它们彼此不同，这一点和单目标问 题大不相同的：它没有一个单独的最优解而是一个最优折衷解的集合。在这些解中， 没有一个解比另一个更好，除非加入一些喜好信息( 例如目标的排序) 。 p a r e t o 最优解的全体被称作p a r e t o 最优解集，相应的目标向量构成了p a r e t o 最优 阵面。p a r e t o 最优解构成了全局最优解。然而，与单目标一样也存在局部最优，在某 个领域范围内，多个局部最优解构成了未被支配解集。这个概念与d e b 所提出的全局 和局部的p a r e t o 最优解相适应。 定义5 考虑一个自变量向量集合a x ，集合 被称为一个局部p a r e t o 最优解 集： 1 0 大庆b 油学院硕士研究生学位论文 如果v a a ：! x 肖，：x a l l x - a l 0 ，集合a 被称作是全局最优解集：如果 c a 爿：! x z ，：x ) 口，局部最 优和全局最优的区别可以用图2 - 2 解释。虚线构成一个全局p a r e t o 最优阵面，而实线 构成了局部p a r e t o 最优阵面。与后者相关的自变量就局部而言互不支配的，因为与a 点相关联的解支配它们中的任何一个。最后，一个全局的p a r e t o 最优解集不一定包含 所有的p a r e t o 最优解并且每一个p a r e t o 最优解集也是一个局部最优解。 2 2 搜索和决策 图2 2 o - o p t i 髓lf r e t 解决一个多目标优化问题，有两个重要的方面：搜索和决策。第一方面指的是优化 过程中可行解集被求解出来称作p a r e t o 最优解集。就单目标优化而言，高维并且复杂 的搜索空间使得搜索困难，并且不能使用精确的优化方法。第二方面强调的是从p a r e t o 最优解集中选择合适的解。在相互冲突的目标之间做出困难的折衷需要人为的决策。 依赖于优化和决策这两个过程是如何组合的，多目标优化方法可以分为三类： 在搜索前决策；多目标优化的问题被合成一个单目标问题，它隐式的包含决策者 的喜好信息。 在决策前搜索：在没有任何喜好信息的情况下进行优化。搜索过程的结果是候选 解的集合( 理想的是p a r e t o 最优解集) ，然后由决策者最终做出选择。 在搜索的过程中进行决策：在交互优化的过程中，决策者给出一些喜好信息。在 优化过程的第一步，求得大量的折衷方案，在此基础上，决策者给出更深层的喜好信 息以导向更深层的搜索。 将多个优化目标组合成一个目标的方法的优点：可以使用经典的单目标优化策略 而不需要大的修改。然而，它要求更深层领域的知识，但这些知识的获取很困难。第 三类算法是可视化和高维多目标优化问题最优解集展示的问题。将搜索和决策结合起 来是一个很有前景的方法，因为它兼有两种方法的优点。在本文中，我们所说的多目 标优化方法有以下特征： 第2 章多目标晟优化问题 1 、能够搜索高维复杂的空间，2 、能够产生确切的p a r e t o 最优解集或是它的近似 解集，这是在搜索的过程中进行决策的第一步，它也是多目标优化领域内更深层研究 的基础。 2 3 传统方法 求解p a r e t o 最优解集的传统办法：在搜索之前，通过决策模拟，把目标参数化，将 多目标优化问题转化为单目标优化问题，求解单目标优化问题得出最优解；然后，优 化器系统地改变决策，对应着不同的参数设置，多次运行单目标优化过程，就可以得 到一个解集，这个解集逼近于p a r e t o 最优解集。这类方法的几个典型技术有线性加权法 1 2 5 1 、约束方法、目标规划、最小最大方法，这些方法的魅力，在于它们利用了成熟的 单目标优化方法。对于大型现实的多目标优化问题，这些经典方法无能为力。因此这 些计算方法基本上不是求p a r e t o 最优解集的优化方法。下面主要介绍前两种方法。 2 3 1 线性加权法 线性加权法是将多目标河题的各个目标函数按箕重要程度分别赋予它们一个权重， 然后多个目标函数加权运算来构造评价函数。 具体地表达为 m i n y = 厂( x ) = w l z ( z ) 十w 2 ( x ) + + x 五( 五) ( 2 2 ) s 1 x x ， t 式中：w j 为权重，一般取= l ，z ( 工) 为目标函数( 其中i - - i ，2 ，k ；七为目标函数 l = 1 个数：乃表示可行域：蕈为决策变量向量若以这个线性加权和作为多目标优化问题的 评价函数，则多目标优化问题就可以转化为单目标优化问题。该方法的主要缺点是对 非凸折衷p a r e t o 阵面，它不能找到所有的p a r e t o 最优解。这可以用图2 3 解释。对于固定 钓权值w l ，心，最大化函数y 2 z ( x ) + w 2 石( z ) 变形得到五( x ) = 一薏石( x ) + y w 2 ， 在目标空间它实际是一条斜率为一盟和截距为上的直线。从图形上而言，优化的过程 嵫 对应于向上移动这条直线直到没有可行的目标向量( 在这里是a 点和d 点) 。点b 和c 从 未达到最大化函数f 。如果斜率增加，d 点获得更大的函数值( 上面的虚线) ；如果 1 2 大庆石油学院硕十研究生学位论文 斜率减小，a 点比b 点和d 点有更大的函数值( 下面的虚线) 。 2 3 2 约束方法 这种方法对于凸的p a r e t o 最优阵面，它将k 个目标中的k 1 个目标转换成约束。剩 下的目标可以任意选择，这样就转化成一个单目标问题。 m i n y = f ( x ) = ( 工) ( 2 3 ) s i e l ( x ) = f a x ) e ，( 1 j ，i h ) x x f 在图2 3 的右侧，约束方法能够获得于折衷阵面非凸部分相关联的解。假设h = l 并 且岛= ，( 实线) ，考虑扩展约束集的情况下使得由a 点所表示的解不可行，而b 点所 表示的自变量向量在余下的解中最大化了。图2 3 也给出了使用这种方法带来的问 题。如果没有恰当的选取下界( 岛= ，+ ) ，所获得新的可行解可能为空，为了避免这 种状况，e 的取值需要事先知道。 2 4 经典方法的讨论 传统方法更具吸引力的主要原因是可以使用研究得较为深入的一些单目标优化 算法。对于规模较大的问题，几乎没有一个多目标优化方法可以使用。与此相对应的 是：在单目标优化问题中有许多启发式方法能够处理这种问题，例如随机搜索算法， 模拟退火算法，禁忌搜索算法等等，并且这些方法的使用也是受约束的。经典的优化 方法通常需要多次运行才能获得近似的p a r e t o 最优解集。每次独立运行的时候，由于 不能相互协调而引起很高的计算开销。 最近几年来，演化算法逐渐替代了经典的方法：1 ) 它能够搜索较大的空间并且2 ) 在一次单独的运行中可以得到多个折衷解。而且使用演化算法也比较容易实现。 2 5 小结 本章根据课题研究的需要，介绍多目标约束最优化问题所涉及的基本概念、定义、 搜索策略、几种具有代表性韵传统优化方法和它们的缺点，最后引出演化算法。 第