多目标优化的求解方法与发展
多目标优化的求解方法与发展
耿玉磊 张翔
(福建农林大学机电工程学院,福州金山 350002)
摘要:本文首先介绍了传统多目标优化求解方法和改进;对遗传算法,模糊优化,神经网络等算法在多目标优化中的应用做了介绍;最后介绍了满意度。
关键词:多目标优化 遗传算法 神经网络
1前言
多目标优化(Multiobjective Optimization Problem,MOP)是数学规划的一个重要分支,是多于一个的数值目标函数在给定区域上的最优化问题,在工程设计、经济规划、计划管理等各领域有着广泛应用。近年来,传统多目标优化方法得到了很大发展,遗传算法、模糊优化、神经网络等现代技术也被应用到多目标优化中,使多目标优化方法取得很大进步。多目标问题中的各目标往往是冲突性的,其解不唯一,如何获得最优解即满意度问题成为多目标优化的一个难点,目前还没有非常成熟与实用性好的理论。
2传统方法应用与改进
2.1传统多目标优化方法
传统的多目标优化方法本质是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法[1][2]:
(1)评价函数法。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。评价函数法的实质,是通过构造评价函数式把多目标转化为单目标。对即有极小化模型又有极大化模型的混合优化问题,可把极大化问题转化为极小化处理,也可用分目标乘除法、功效函数法、选择法等方法解决。但不同的评价函数,表达了不同的评价意义。因此,评价函数法只可保证所求得的最优解为多目标优化的有效解,而很难准确地获取设计者认可的满意有效解,这使得评价函数法的应用,局限于要求不高或对多目标优化方法把握不深的应用者。
(2)交互规划法。不直接使用评价函数的表达式,而是使决策者参与到求解过程,控制优化的进行过程,使分析和决策交替进行,这种方法称为交互规划法。由于有决策者的参与,所得的结果易于趋近决策者主观要求,因此其解只能达到主观最优,尚缺客观性的评价,且不易于操作。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权和法等。
(3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。在要求获取的解是有效解的前提下,此种解法存在的问题为:
1)各目标的优先层次的不同选择,就得到具有不同优性的解,目标优性的差异与重要度的差异这两者的一致性难以调控与把握;2)对于非线性多目标优化,每个目标不可能在最优解上都存在等值线(面),因此往往难以优化到最后一层,从而失去了多目标优化的意义。
2.2传统求解方法的改进
张翔[3]针对评价函数存在的缺陷,建立多目标优化设计的评价准则,以此构造一种具有多目标优化数学意义的新型评价函数。
周美英等[4]针对决策结果往往带有一定程度的相对性和主观性,不能真实地反映客观事实,引入统一目标函数最小偏差法,其特点在于仅需要分析者和决策者的局部信息,即各个目标函数的最优解,而无需知道它们的相对重要性。
雷昕[5]提出了参数化方法,将多目标评价函数的权系数看作是参数,指出最优解连续依赖参数的变化,并根据需要给出参数,使所得解更为有效。
在确定权重系数时模糊方法也被用广泛应用。李登峰[6]研究了权重系数未事先给定的多目标优化问题,提出综合加权距离,综合加权距离小的方案为优,通过求解综合加权方案的最优值可确定加权系数和方案的综合优属度。关志华等[7]介绍了一种基于模糊偏好方法,通过使用模糊偏好来确定各个目标函数的权重。张延辉等[8]对目标的重要度进行了模糊性描述,使权重系数的选取建立在重要度这个模糊概念之上。 105
3遗传算法在多目标优化中的应用与改进
1985年Schafferrg提出了第一个多目标进化算法(Multiobjective Evolutionary algorithm,MOEA),创
[9][10]了应用MOEA解决MOP问题的先河。目前进化算法中,使用遗传算法是其他算法的9倍。
3.1遗传算法的应用
遗传算法(GA)能对整个搜索空间的大量可行解同时并行搜索,这样就克服了传统方法可能陷入收敛于局部最优的困境。由于遗传算法是对整个群体所进行的进化运算,那么利用其这一特性求解多目标优化问题的有效解集合是一个有效手段。目前常用的基于遗传算法的求解方法有[11][12]:
(1)权重系数法,此方法在实质上与线性加权和法并无本质区别,只是采用了遗传算法的搜索方法。
(2)并列选择法,先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体,再把目标函数分配到这些子群体,各子目标函数在相应的子群体中独立进行选择运算以形成新的子群体,然后子群体合并为一个完整的群体,在这个完整的群体内进行交叉、变异运算,生成下一代完整群体,如此执行“分割-并列选择-合并”过程,最终可求出最优解。但易陷入单个目标函数的局部最优解,可考虑改变适应度的计算方法,使满意度高的个体得以保存。
(3)排序选择法,在此法中选择运算是依据“有效解最优个体”的概念来对群体中的各个个体进行排序,使排在前面的个体有更多机会遗传到下一代中,这样经过一定代数后,可求出多目标的有效解。
(4)小生境Pareto遗传法,它将共享函数的概念引入到求解中,并运用联赛选择机制来选择优良个体遗传到下一代群体中,这样可使解分散在整个Pareto最优解集中。
在实际应用中也可把以上各种方法混合使用以期得到满意效果。
3.2遗传算法改进
近年来,随着遗传算法的广泛应用,对遗传算法的改进也取得了很大成果。
为防止收敛于局部,用遗传算法进行全局搜索取得近似最优点,然后以近似最优点为初值,采用局部
[14]搜索能力强的单纯形法进行局部搜索[13];也可采用对适应度高的个体采取保护的“杰出个体保护策略”;
[15]。 或将模拟退火算法引入,实现适应度共享,以克服未成熟收敛
在适应度方面,可利用各个个体的相对优属度值作为适应度,这样就可以直接利用相对优属度进行轮盘赌选择,能有效的搜索到有效解[16];可将免疫原理中的浓度机制引入多目标进化的适应度函数设计,保持了群体的多样性,防止了收敛于个别解而丢失其他有效解[17];
在遗传算子改进方面,朱学军等 [18]提出多个体参与交叉的Pareto多目标遗传算法,群体中的个体采用真实值表示。使该算法的速度大大提高。杨金明等[19]采用生物界中存在的“杂交”优势,提出多种群变异算法,克服了寻优速度慢,存在“封闭竞争”等问题;于歆杰等[20]提出在选择阶段之前,利用适应值共享的思想进行适应值调整,而在替换阶段,则采用确定性拥挤的思想,可能使遗传算法既保证收敛又能找到多个峰。
目前遗传算法在多目标优化中的应用很多,但大多只是作为一种新的搜索算法,所做改进也集中在遗传算法本身,在多目标优化策略方面并没有很大的突破。即在如何保证所得解为有效解,如何最终确定最优解方面还有待进一步研究。
4模糊理论的应用
多目标最优解同各子目标最优解密切相关,但子目标之间,各子目标最优解同多目标最优解之间的关系是模糊的,所以用模糊优化方法能得到某种意义下的满意结果。模糊方法应用于多目标优化主要有以下途径:
其一是构造模糊性的多目标优化算法。模糊性多目标优化算法的基本原理为在各单目标最优解的模糊集中寻求使各个目标都尽可能优的满意解。其基本步骤为:先求出各个单目标的约束最优解再将各最优解模糊化,然后求能使各模糊最优解交集的隶属函数取最大值的解,此解便为最优解[21]。为了通过赋予权数来反映各目标的重要程度,可按照各目标的重要程度,选择不同的隶属度函数类型和调整隶属度函数的参数,来调整各单目标最优解的模糊集的分布状态,从而可得出不同权重分配下的多目标最优解。但隶属度函数在本质上,也是一种评价函数,所以笔者认为仍存在其评价意义的准确性,多目标最优的真实性。
其二用于最优解的评价。将在下文介绍。
106
5人工神经网络的应用
人工神经网络模拟人脑处理机制 ,实现了大规模并行处理和分布式存储,并具有容错性、自适应性和自组织性。目前神经网络在多目标优化中的应用多为和其它优化方法的结合,如和模糊理论结合构造评价准则、取代单目标优化方法。并不是在多目标优化策略方面的应用。
关秦川[22]提出一种解决工程结构多目标模糊优化的新方法,以目标函数值的满意程度作为学习样本,采用神经网络取代传统的隶属度函数,解决了确定隶属度函数显式表达式困难,人为确定理由不充分的问题。
彭观等[23] 采用神经网络方法求解切削加工多目标优化问题,给出了Boltzmann机神经网络模型和算法,证明了神经网络的可行性。
朱学军[24]用Kolmogorov多层神经网络映射存在定理的基础上导出的用神经网络进行结构近似分析的方法,用均匀试验设计方法选取特征样本点供神经网络训练,将神经网络与Pareto遗传算法有机地结合,使多目标优化的计算效率进一步提高。
神经网络在多目标优化中还可有其它应用。如可用均匀设计和正交设计的方法选取权重系数,并将权系数和优化结果作为训练样本,建立函数关系,这样改变权系数后,可用网络结构求出最优解。也可根据神经网络有很强的并行计算能力的特点,应用在分层优化中,或和遗传算法结合,从有效解集中选择最优解。另外,也可把模糊理论和神经网络结合起来,形成即能处理模糊信息,又有并行处理、进行学习的特点。这些都可作为研究方向。
6满意度问题
多目标优化一般难以找到一个绝对最优解,大多是在权衡协调各个目标的基础上,依据问题要求,寻
[1][3][25]求既有一定精确度又有实际意义的满意解。 如何从有效解集中选择满意度最高的有效解,即最优解
的评价问题是一个难点,目前大体上可归纳为以下几种:
第一种通过一定方式将多目标问题单目标化,形成多目标非劣解的基础,然后运用多目标决策理论在非劣解集中通过构造效用函数或加权平均等方法进行方案优选[25] [26]。
另一类是利用模糊数学的方法认为各非劣解之间及非劣解和理想解之间的关系具有模糊性的前提下,用模糊数学方法来确定最优解。模糊数学解决这一问题较成熟的方法有:相似优先比法和贴近度法[27] [28]的关联程度而确定最优解[30]。还可将模糊理论和神经网络结合,构成模糊优选神经网络[31] 。 ,还有用综合评判法根据主观需要从非劣解中评判出最优解[29],也有用灰色关联度得出非劣解与理想解之间
7问题与展望
多目标优化的理论和求解方法是一个长期的研究课题,目前存在着理论不完善、算法不成熟等问题。在理论方面,对最优解质量或满意度的客观度量还没有一个非常成熟的理论与与实用性好的方法;在多目标优化算法中,其收敛性的数学证明还存在不足;在计算精度方面,数值计算本身的误差也常导致结果的误差,产生伪有效解;进化算法中进化算子的误差也会导致过早收敛于单个解,即产生漂移现象。另外,算法计算速度的提高、高维多目标优化等,也是值得研究的问题,这些都可作为进一步研究的方向。 参考文献
[1] 胡毓达.实用多目标最优化[M].上海:上海科学技术出版社,1990
[2] 张翔.优化设计方法及编程[M].北京:中国农业大学出版社,2001
[3] 张翔.多目标优化设计的评价函数[J].福建农业大学学报(自然科学版).1994,23(4):465-470
[4] 周美英,李典庆.多目标优化设计的最小偏差法[J].机械设计.2002,l2
[5] 雷昕.参数化方法在解多目标优化中的应用[J].数学杂志.1998,18(2)
[6] 李登峰,陈守煜.多目标优化问题的模糊交叉算法与收敛性[J].应用数学.1997,10(3):107-109
[7] 关志华,寇纪淞,李敏强.基于模糊偏好的多目标进化优化算法[J].天津大学学报.2002,35(3)
[8] 张延辉,李为吉.一种基于模糊重要度的多目标优化设计方法[J].航空学学报.1999,20(4)
[9] 崔逊学等.多目标进化算法的研究[J].中国科学基金.2002,1
[10] 关志华.多目标进化算法研究初步[J].石家庄经济学院学报.2002,25(2)
[11] 周明,孙树栋.遗传算法原理及应用[M].北京:国防大学出版社,1999
[12] 崔逊学.基于多目标优化的进化算法研究[D].中国科学技术大学博士学位论文.2001,10
[13] 文瑛,蒋华,雷鸿.一类基于混合遗传算法的多目标优化方法[J].广西师范学院学报(自然科学版) 107
2003,20(1)
[14] 朱文坚,陈东,刘建素.遗传算法在多目标优化设计中的应用研究[J].机械工程师.2001,12
[15] 胡静,李金龙,曹先彬.模拟退火算法与遗传算法结合及多目标优化求解研究[J].计算机应用与软 件.2000,17(11):19-23,54
[16] 郝聚民,纪卓尚,戴寅生等.基于模糊优选技术的多目标混合优化遗传算法[J].系统工程理论方法 应用.1999,8(1)
[17] 崔逊学,李淼,方廷健.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能. 2001,14(3)
[18] 朱学军,陈彤,薛量等.多个体参与交叉的Pareto多目标遗传算法[J].电子学报.2001,1
[19] 杨金明,吴捷,钟丹虹.多目标优化问题中一种改进的遗传算法[J].华南理工大学学报(自然科学 版)2001,29(12)
[20] 于歆杰,王赞基.适应值共享拥挤遗传算法[J].控制与决策.2001,16(6)
[21] 陈一君.多目标模糊优化理论及其在制造系统中的应用[J].四川轻化工学院学报.2002,15(3)
[22] 关秦川.多目标优化问题的神经网络解法[J].西南交通大学学报,2002,37(3)
[23] 彭观,陈统坚,张俊.切削加工参数多目标优化的神经网络方法[J].机械工艺师.1999,2
[24] 朱学军,薛量,王安麟等.利用神经网络实现复杂结构的多目标优化设计[J].机械科学与技术.2000, 19(3)
[25] 张翔.一种基于最优解定义的多目标优化数值解法[J].机械设计.2001,18(7)
[26] 白广忱,王荣桥.机械零件可靠性多目标优化设计的满意解[J].中国机械工程.2001,12(3)
[27] 秦惠芳,孙家林.行星齿轮传动的模糊优化设计[J].模糊系统与数学.2000,14(4)
[28] 张志远,夏新涛,李晓滨.多目标优化最优解模糊评价方法的改进[J].洛阳工学院学报.1999,20
(4)
[29] 陈新,吴琦,郭三学等.模糊综合评判在多目标优化设计中的应用[J].西安矿业学院学报.1999, 19(4)
[30] 张鹏.用相似接近度法从多目标优化非劣解中求最优解[J].计算结构力学及其应用.1992,9(2)
[31] 陈守煜.模糊优选神经网络多目标决策理论[J].大连理工大学学报.1997,37(6)
作者简介
耿玉磊,1981年3月出生,福建农林大学机电工程学院硕士研究生,研究方向:现代设计理论与方法。
108