多目标优化方法研究

第38卷第4期西南民族大学学报.自然科学版Jul. 2012Journal of Southwest University for Nationalities.Natural Science Edition文章编号: 1003-2843(2012)04-065804多目标优化方法研究方诗虹,丁可伟,陈雅茜1(I.西南民族大学计算机科学与技术学院,四川成都610041;2. 西南民族大学预科教育学院,四川咸都610041)摘要:阐述了多目标优化问题的特点,给出了该问题的数学模型及Pareto 最优解的定义,介绍了用于解决多目标问题的传统优化方法和进化优化方法，并着重介绍了基于遗传算法的多目标优化方法.最后对传统方法和进化方法进行了比较.关键字:多目标优化问题;单目标优化问题; Pareto最优解;遣传算法中图分类号: TP301.6文献标识码: Adoi: 0.396/j.ssm.1003-2483 2012.04.341引言现代社会各行各业的应用中，常常遇到需要使多个目标在给定区域上尽可能最优的决策问题.例如在进行网络设计时，在希望成本尽可能低的同时，网络带宽尽可能高,此外可能还需要考虑可靠性和可维护性等.这些目标的改善可能相互抵触,在提高其中某个目标时，会导致其他目标效果的下降.例如低成本难以满足高带宽而好的可维修性会降低可靠性.所以，实际应用中必须在多个期望目标之间取得平衡，从而获得-一个相对优化的结果.这种多个数值目标在给定区域上的最优化问题即多目标优化问题(Muti-bjective Optimization Problem,MOP).2问题 的描述2.1多 目标优化问题的数学模型单目标优化问题(Single objective Optimization Problem, SOP)往往只有一个解存在，求得该解即得到了最优解.而多目标优化问题MOP与单目标优化问题SOP相比，有着本质的区别".多目标优化问题MOP可作如下数学描述:定义1一般由n个决策变量参数、k 个目标函数和m个约束条件组成的MOP问题,最优化目标如下:maxy= f(x)=(f(x),&(x).f(x))x=(x,+x,-.x.)eX(1)y-=(y>2.-.y.)cYs4. e;(x)≤0， i=,..,m .其中x表示决策向量，X表示决策空间, y,表示目标向量, Y表示目标空间，e(x)为约束函数.最大化与最小化问题可以相互转化,本文以最大化多目标为例2.2 Pareto 最优解中国煤化工收稿日期: 2012-04-24作者简介:方诗虹(1980-), 女讲师.YHCNMHG.基金项目:中央高校基本科研业务费专项资金(12NZYQN16)资助..第4期方诗虹等:多目标优化方法研究659Francis Ysidro Edgeworth 于1881 年提出多目标问题“最优解”的概念即解决多目标问题，实际上是求解- -组均衡解,而非单个目标全局最优解.法国经济学家和社会学家Vilfredo Pareto在1896年推广了这个概念1, 他提出向量化概念从经济学角度将本质上不可比较的多个目标转化成单个指标进行优化求解.定义2对于集合AS X,当且仅当决策向量x∈X;为非劣,有不3a∈A:a>x.(2)即当且仅当x在X,中是非劣的，决策向量x才是Pareto 最优解.其中,对于决策向量a、x,当且仅当f(a)>f(x)时，有a>x,即a优于x.2.3 Pareto 最优解集的评价准则由于多目标优化问题的结果并不是唯- - 确定的，所以对其非劣解集质量评价也相对困难的. - -般来说，- 一个比较理想的非劣解集应包括以下几个方面以:(1)获得的非劣解集与真实非劣解集的距离应尽可能小;(2)获得的非劣解集应均匀分布;(3)获得非劣解集应具有良好的扩展性,即非劣前沿的端点应尽可能接近单目标极值.为了方便对多目标优化问题非劣解集质量进行评价,在随后的研究中，人们采用一-些度量方法量化以上3个衡量标准，对算法的性能进行评价,主要有U-度量法+、宽广性度量法(Maximum Spread-measure)5、 C-度量法'和S-度量法!"!3进化的多 目标优化方法多目标进化算法(Multi-objective Evolutionary Algorithms, MOEAs)在处理大规模的搜索空间、在单轮优化期间可以产生多个均衡解，且对目标最优均衡面的形状和连续性不敏感，可 以很好地逼近非凸或不连续的均衡面,能够有效克服传统方法局限性.Vanveldhuizen"2)按求解和决策的关系把多目标优化求解方法分为三类:(1)先决策再搜索解:决策者先给出目标优先等级，将多目标合成数量成本函数,再由算法搜索最优解,如评价函数法;(2)边决策边搜索解:决策者和算法互动，前者提供目标优先关系，后者提供最新解,根据最新解产生更好的目标优先关系，交互求解;(3)先搜索解再决策:算法搜索到解集后，再由决策者确定或选择解,如理想点法.在众多的方法中，先搜索再决策的方法较多,而使用遗传算法作为进化方法的算法在MOEAs设计和应用中占主要地位.3.1 多目标遗传算法对于如何求解多目标问题的Pareto 最优解,目前已提出了多种基于遗传算法的求解方法，主要有并列选择法、权重系数变化法、排序选择法、共享函数法和外部辅助选择法等"!.3.2 权重系数变化法这是基于目标加权法的遗传算法,例如Hajela和Lin提出的“可变目标权重聚合法”.在这种非Pareto方法中,每个目标均有一一个权重,但权重本身并不固定,为了搜索多个解,问题解和权重会动态变化，同时进化.这种方法计算效率较高，但在没有足够的信息时，无法确定合适的权重系数，只能通过权重系数组合函数的优化结果来获得最优解.3.3排序选择法Srinivas和Deb提出的“非劣分层遗传算法(NSGA)”即属于中国煤化工寿Pareto最优个体的概念来对群体中的所有个体进行排序,由这个排序结果来实施MHC N MH G在前面的Pareto 最优个体有更多机会遗传到下一-代群体.经过数代循环后，最终得到Pareto 最优解.其中,最优个体排序方法如660西南民族大学学报.自然科学版第38卷下:StepI设置初始序号r=1;Step2确定群体中的Pareto最优个体,定义其序号为r;Step3从群体中去掉最优个体,并更改序号r=r+1;Step4回到Step2,直至将所有个体排序.Deb等人在2002年提出了NSGA-II,主要思想是对种群中的个体按Pareto进行排序,按照排序顺序从小到大选择个体,若遇相同序值的个体,则偏好位于目标空间中稀疏区域的个体.排序选择法仅度量了各个个体之间的优越次序,而未度量分散程度，故容易产生多个相似的Pareto 最优解,难以生成分布较广的解集..4 共享函数法这类算法的典型代表是Horm等人提出的“小生境Pareto遗传算法".对某个个体而言,度量其附近存在多少种、多大程度相似个体的度量值,即小生境数(Niche Count).在进化算法中引入小生境方法后,对相同或相似个体数量加以限制，以便产生种类较多的不同最优解共享函数法的过程如下:StepI从群体中随机选取k个个体组成个体比较集合C ;Step 2从群体中随机选择两个个体组成个体联赛集合T ;Step 3比较集合T和C中各个个体的优胜关系，如果T中的一个个体x比C中的所有个体都优越，且T中的另-一个个体不比C中的所有个体优越,则个体x遗传到下一代群体中;如果无法获得这样的个体x,则从T中选择小生境数较小的个体遗传到下一代群体中.共享函数法能得到多种不同的Pareto最优解但大量的评价和比较运算使其搜索效率较低.3.5外部辅助选择法Zitzler和Thiele'提出的“强度Pareto进化算法‘及Cello和Toscano Pulido0提出的“微遗传算法(Micro-GA)”等都属于外部辅助选择法,主要流程如下:StepI产生初始群体P和一个外部辅助非劣空的集合P';Step2将P中的非劣个体复制到P',将P'中的劣解剿除(第- -代无劣解);Step3对P'进行聚类处理,控制其规模不超过预定数N';Step4计算P和P'中个体适应度;Step5从PUP'中使用联赛选择机制进行选择操作,直到配对池满;Step 6交叉和变异;Step 7达到最大进化代数则停止否则转到Step 2.外部辅助选择法可以保持群体多样性,聚类方法也可以保证外部集合的非劣个体数目不超过规定范围，且不破坏其分布特征4结论传统算法在处理多目标优化问题上,主要优点在于其计算量小、计算速度快;设计简单,数学建模容易;具有充分的理论支持.进化算法尽管理论基础还不完善，但由于其适应性、通用性、并行性和扩展性等优点，已被广泛应用于多目标问题求解,并取得了良好效果.实际问题往往由多个互相冲突的目标组成,传统算法将各目标聚合成单目标函数求解,对Pareto 最优解前端形状敏感,不能很好处理前端凹部,对于大规模问题也很少真正被使用传统方法存在着很大的局限性.进化算法能处理大规模搜索空间、在单轮优化期间产生多个均衡解,有地直肥了件运古比的易四性但进化算法例如遗传算法，也存在早熟和欺骗的问题，觖少完整的收敛性证明等中国煤化工在解决多目标问题时，并不存在一-种统-的最佳算法， 也MHC N M H G于其他算法的算法.正所谓“具体问题，具体分析”,在解决具体的多目标问题时，往往需要对已有算法进行设计和调整,使得它只在第4期方诗虹等:多目标优化方法研究661求解该类问题时具有其他算法不能达到的最佳性能结构.参考文献:[1]姚新胜. 满意优化原理及其在机械工程领域中的应用研究[D].成都:西南交通大学, 2002.[2PARETO V. Cours DEconomie Politique[M]. Lausanne: F Rouge, 1896.[3] ZITZLER E, DEB K, THIELE L.Comparison of Multi- objective Evolutionary Algorithm: Empirical Results[J. EvolutionaryComputation, 2000, 8(2): 173-195.[4} LEUNG Y W, WANG Y E. U-measure: A qualiy measure for muliobjecive programming U IEEE Transactions Oil Systems Manand Cybemetics. Part A:Systems and Humans, 2003, 3(33) 337-343.[5] K DEB. Multi objecive opimization using evolutionary algorithm[M. New York: John Wiley&Sons, Lid, 2001.6) 郑金华多目标进化算法及其应用[M].北京:科学出版社，2007.[7] SCHOA 1. Fault tolerant design using single and multi-iteria genetic aigorithms[D]. Canbridge: Depatnent of Acronautics andAstronautics, Massachusetts Institute of Technology, 1995.Research on methods of multi-objective optimizationFANG Shi-hong, DING Ke-wei, CHEN Ya-xi(Soubwest University for Nationalitis Chengdu 610041, P.R.C.)Abstract: This paper expounds the features of multi-objective optimization problem, and presents the mathematical model ofMOP and the theory of Pareto optimal solution. It introduces the classical optimization and evolutionary optimization,especially the mouti-objctive evolutionary optimization based on genetic algorithm. Finally, it compares these two mcthods.Key words: multi- objective optimization problem; single- objective optimization problem; Pareto optimal solution; geneticalgorithm中国煤化工MHCNMHG