多目标优化快速入门
前言
多目标优化算法是一种用于同时考虑多个目标函数的优化算法。它与单目标优化算法的不同之处在于,多目标优化算法需要同时兼顾多个目标,并在保证每个目标的一定程度满足的前提下尽可能使得每个目标的满足程度都达到最优。多目标优化算法通常应有于解决冲突和复杂的优化问题。
例如,在数学学习中,求函数f1(x1,x2, x3,…,xn)=$x_12$+$x_22+x_32+...+x_n2$和函数f2(x1,x2, x3,…,xn)=(x1+1)2+(x2+1)2+(x3+1)2+…+(xn+1)2,同时达到最小,这是x的取值分别是多少,不存在这样一组的x的取值使得f1和f2同时达到最小值,我们要怎么做?在生活中,想买一栋房子,想要房子的面积大,地段好,价格还比较低,同时满足这三个条件,我们要怎么考虑?
帕累托最优
帕累托最优状态就是不可能再有更多的帕累托改进的余地;换句话说,帕累托改进是达到帕累托最优的路径和方法。 帕累托最优是公平与效率的“理想王国”。为了易于理解,引用B站up寒风csj举的一个例子。
首先需要明确帕累托最优并不是给你一个最优的解,而是给你一个解集,你需要根据你的限制条件来决定要哪一个解。
如果你的导师需要你学习:唱、跳、rap和篮球,这四个作为你的目标,但是你的老师只给了你1年的时间,很显然由于你的练习时长不足两年半,你无法使这四个目标都达到最优。
上面的引例可以总结为:
(1)目标={唱,跳,rap,篮球}
(2)约束={练习时长 <= 一年}
1、视频中关于定义一[1]的解释:
你使用两种方法v和w进行练习,得到的结果是:
v = {唱的优,跳的优,rap说的优,篮球打的优},w = {唱的良,跳的优,rap说的良,篮球打的良}
很显然v这种练习方式要比w这种练习方式要好,就可以认为v支配w
2、视频中关于定义二[2]的解释:
你使用两种练习方式x和y,得到的结果为:
x = {唱的优,跳的良,rap说的良,篮球打的良}, y = {唱的良,跳的优,rap说的良,篮球打的良}
很显然x这种练习方式使你唱功要比y的好,但是y这种练习方式使得你跳舞的能力比x好。
我们就认为这两种练习方式各有千秋,谁也不支配谁。那么x和y的练习方式就会被放入到帕累托最优集中,既
P = {x,y,....}
3、视频中关于定义三[3]的解释:
F(x)是我们的目标函数
将我们的解决方案带入就可以计算了。
最后我们就可以根据我们其他的要求来选择更好的解了,比如我们马上要参加《我是歌手》,那么我们就会选择x这种练习方式
多目标优化问题的数学一般描述
在右图中求最小值,可以看出,B支配C,D两点,在A点,B是被支配的,其余空间则是非支配
1.想要求得多目标问题的最优解,我们利用计算机强大的计算能力,在决策空间中随机产生大量个体,并找出其中最好的(不被支配的)个体。也就是不断地“试”,来找到越来越好的个体。随机寻找个体的过程称为搜索
2.但无法做到遍历决策空间中每一个个体,我们需要在更短的时间里利用随机的方法找到更好的个体
3.利用进化算法的策略,可以朝着越来越好的方向随机产生个体,而不是在决策空间中完全盲目地产生个体。
GA算法步骤
·(1种群中个体随机初始化.
·(2)每个个体通过评价得到一个适应度值.·(3)适应度值大的个体有更大的概率保留下来.
·(4)通过对适应度值大的个体交叉变异产生新的个体.
·不断的迭代第(2)-(4)步骤,经过足够多的迭代次后,最终能得到好的解.
评价性能
在对多目标优化算法的性能进行评价时,主要有两个评价标准:多样性和收敛性。
IGD: 该指标用于计算真实帕累托前沿中所有解与求解算法获得的非占优解的平均欧式距离。IGD值越小,表明非占优解集越逼近真实帕累托前沿并且分布更均匀,解集的收敛性和多样性更好。记算法求解算例获取的解集为X,P*为真实帕累托前沿上均匀分布的点集,则×的IGD值计算公式如下: