多目标群体智能算法的历史

2023-11-26 理论教育版权反馈

【摘要】：鉴于多目标优化问题在科学研究和实际应用中普遍存在，因此，研究MOP问题的求解具有重要的现实意义。多目标优化这一概念在早期的研究文献中也被称为多准则决策或多属性决策。意大利经济学家L.Pareto[8]于1896年在其关于经济福利的著作中最早提了到多目标优化问题以及后来被称为Pareto最优的均衡状态。因此，ε约束法实质上是将MOP问题转化为带约束的单目标优化问题进行求解。

现实中存在大量需要同时优化多个目标的问题[1]，例如在设计一种新型产品时，既要考虑使用性能，又要考虑制造成本，同时还要考虑产品的可制造性、可靠性和可维护性等。这些设计目标的改善可能相互抵触，譬如，好的可维护性会引起可靠性的降低，因而需要在这些设计目标之间进行折中。还有，人们在购买汽车时通常会考虑性能和价格这两个因素，希望能够买到性能高而价格低的产品。实际上，这是一个包含两个目标的决策问题，它要求在最大化性能的同时最小化产品价格。一般说来，使用了新技术和新材料的汽车，性能会比较高，但同时价格也比较高；相反，价格低的汽车在选材和技术上就会降低标准，从而性能也会有所下降。因此，人们实际上无法以最低的价格买到性能最好的汽车，他们只能在性能和价格之间做一个折中选择。类似的问题还有很多，在投资管理问题中，希望在最小化风险的同时最大化收益回报；建造桥梁时，通常要求总的重量轻、硬度高，同时花费也尽可能低；在车辆路径问题中，要求有最短的行驶路径与最少的用车数量[2]；在机器学习中，有监督学习问题要求有最小的训练误差和最低的模型复杂度[3]，聚类问题要求有最大的类内紧密度和最小的类间紧密度[4]，模式挖掘问题要求寻找最频繁且最完整的模式[5]等。鉴于多目标优化问题(Multi-objective Optimization Problem，MOP)在科学研究和实际应用中普遍存在，因此，研究MOP问题的求解具有重要的现实意义。

多目标优化问题最早在经济和管理科学中得以研究。多目标优化这一概念在早期的研究文献中也被称为多准则决策或多属性决策。多目标优化的起源可以追溯到经济学家A.Smith[6]关于经济平衡和F.Y.Edgeworth[7]对均衡竞争的研究。意大利经济学家L.Pareto[8]于1896年在其关于经济福利的著作中最早提了到多目标优化问题以及后来被称为Pareto最优的均衡状态。

为了获得多目标优化问题的解，一些研究者提出了多种方法，这些方法概括起来可以分成两大类:直接搜索方法和群体搜索方法。(www.chuimin.cn)

在多目标优化研究的早期，即从20世纪50年代初到20世纪80年代中期，主要采用直接搜索方法，它们是源自运筹学和数学上的理论和方法。这一时期处理多目标优化问题的方法主要有加权求和法、ε约束法、最小-最大法等。加权求和法最早由Zadeh[9]提出，该方法将各目标函数乘以预设的权值后相加，把多目标优化问题转换为单目标优化问题，然后再采用单目标问题的方法求解。加权求和方法的优点是简单，而且对于凸MOP问题，通过一组权值可以保证获得一个Pareto最优解。但加权求和方法的缺点也十分明显，即各目标函数的权重不易设定，只有通过使用多组权值才能获得多个解，而且对于非凸MOP问题，很难求得其Pareto最优解。ε约束法由Marglin[10]于1967年提出，它是一种局限于优化Pareto最优前沿为凸的方法，即它指定一个优化目标，而将其他的目标视为约束条件，然后再用单目标优化方法求解。因此，ε约束法实质上是将MOP问题转化为带约束的单目标优化问题进行求解。这种方法的优点是，可以通过设置不同的ε值获得不同的Pareto最优解，可以用于非凸问题的求解。但该方法的缺点是获得的解对ε的取值依赖较大，并且随着目标数目的增加，需要更多的信息来帮助用户选择合适的ε值。最小-最大法[11]则是通过最小化各目标值与预设的目标值之间的最大偏差来求解MOP问题。

上述直接搜索方法的优点是它们具有数学理论基础，是一种确定性算法，算法获得的结果是稳定的，但它们亦存在明显的缺陷。首先，直接搜索方法通常需要梯度信息来支持，要求问题满足某些数学特征如连续、可微等，但并非所有的问题都具备这些特征。其次，直接搜索方法一般没有同时考虑所有的目标。大多数直接搜索方法将多目标优化问题转换为一个单目标优化问题，从而可以利用单目标优化方法求解。但这种方法一次执行只能得到一个解。尽管也可以通过多次运行算法获得多个解，但不能保证这些解在目标空间上均匀分布，而且在非凸问题中不能保证得到Pareto最优解[12]。

多目标群体智能算法的历史

相关推荐