Pareto最优解在数学中应用

多目标优化

目标优化问题一般地就是指通过一定的优化算法获得目标函数的最优化解。当优化的目标函数为一个时称之为单目标优化(Single-objective Optimization Problem, SOP)。当优化的目标函数有两个或两个以上时称为多目标优化(Multi-objective Optimization Problem, MOP)。不同于单目标优化的解为有限解，多目标优化的解通常是一组均衡解。

对于一个多目标优化问题，我们通常会选用Pareto最优解的方法。

Pareto最优解

Pareto最优解，也称为帕累托效率（Pareto efficiency），是指资源分配的一种理想状态，假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。帕累托最优状态就是不可能再有更多的帕累托改进的余地；换句话说，帕累托改进是达到帕累托最优的路径和方法。 帕累托最优是公平与效率的“理想王国”。

Pareto最优解：若x∈C,且在C中不存在比x更优越的解x，则称x*是多目标最优化模型式的Pareto最优解，又称为有效解。

一般来说，多目标优化问题并不存在一个最优解，所有可能的解都称为非劣解，也称为Pareto解。传统优化技术一般每次能得到Pareto解集中的一个，而用智能算法来求解，可以得到更多的Pareto解，这些解构成了一个最优解集，称为Pareto最优解。它是由那些任一个目标函数值的提高都必须以牺牲其他目标函数值为代价的解组成的集合,称为Pareto最优域，简称Pareto集。Pareto有效(最优)解非劣解集是指由这样一些解组成的集合：与集合之外的任何解相比它们至少有一个目标函数比集合之外的解好。

Pareto实例

首先我们生成两个函数，简化起见，我们将sqrt(1+x^2)函数通过移位和缩放变成两个不同的函数

function f = simple_mult(x)

f(:,1) = sqrt(1+x.^2);
f(:,2) = 4 + 2*sqrt(1+(x-1).^2);

如下代码所示x在-0.5到1.5之间，两个函数变化曲线，当x减小到0以下时，两个分量都在增加。在0和1之间，f_1(x)增加，f_2(x)减小，所以有一个权衡区域。

t = linspace(-0.5,1.5);
F = simple_mult(t);
plot(t,F,'LineWidth',2)
hold on
plot([0,0],[0,8],'g--');
plot([1,1],[0,8],'g--');
plot([0,1],[1,6],'k.','MarkerSize',15);
text(-0.25,1.5,'Minimum(f_1(x))')
text(.75,5.5,'Minimum(f_2(x))')
hold off
legend('f_1(x)','f_2(x)')
xlabel({'x';'Tradeoff region between the green lines'})

要找到帕累托前线，首先找出这两个函数的无约束最小值。 在这种情况下，可以通过检查看到f_1(x)的最小值为1，f_2(x)的最小值为6，但一般情况下，可能需要使用优化程序。 一般来说，写一个返回多对象函数的特定组件的函数。

function z = pickindex(x,k)
z = simple_mult(x); % evaluate both objectives
z = z(k); % return objective k

然后使用优化求解器找到每个组件的最小值。在这种情况下可以使用fminbnd，或者对于更高维的问题，可以使用fminunc。

k = 1;
[min1,minfn1] = fminbnd(@(x)pickindex(x,k),-1,2);
k = 2;
[min2,minfn2] = fminbnd(@(x)pickindex(x,k),-1,2);

设置每个组件的无约束最优的目标。在没有权衡的条件下，只有当多目标函数不相互干扰时，才能同时实现这些目标。

goal = [minfn1,minfn2];

要计算帕累托前沿，从0到1取一个权重向量[a，1-a]。解决目标达成问题，要将权重设置为各种值。

nf = 2; % number of objective functions
N = 50; % number of points for plotting
onen = 1/N;
x = zeros(N+1,1);
f = zeros(N+1,nf);
fun = @simple_mult;
x0 = 0.5;
options = optimoptions('fgoalattain','Display','off');
for r = 0:N
    t = onen*r; % 0 through 1
    weight = [t,1-t];
    [x(r+1,:),f(r+1,:)] = fgoalattain(fun,x0,goal,weight,...
        [],[],[],[],[],[],[],options);
end

figure
plot(f(:,1),f(:,2),'k.');
xlabel('f_1')
ylabel('f_2')

结果如下图所示

在代码中，optimoptions是R2013a版新引入的函数,用于设置除fminbnd、fminsearch、fzero和lsqnonneg这四个函数之外的其它优化函数的选项.

options = optimoptions('fgoalattain','Display','off');

上述代码也可以分开写，作用完全相同

options = optimoptions('fgoalattain');
options = optimoptions(options,'Display', 'off');

本代码中，比较重要的函数是fgoalattain()函数，MATLAB中fgoalattain()函数用来解决多目标规划的问题，多目标规划可以归结为

其中x,weight,goal,b,lb和ub是向量,A和Aeq是矩阵C(x),ceq(x)和f(x)是向量函数，他们可以是非线性函数。 F(x)是所考虑的目标函数，goal是欲达到的目标，多目标规划的Matlab 函数fgoalattain的用法为

［x,fval］= fgoalattain('fun',x0,goal,weight) 
［x,fval］= fgoalattain('fun',x0,goal,weight,A,b) 
［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq) 
［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) 

其中fun是用M文件定义的目标向量函数，x0是初值，weight是权重。A,b定义不等式约束A*x ≤ b ，Aeq,beq定义等式约束 Aeq*x=Beq ，nonlcon是用M文件定义的非线性约束c(x)≤0，ceq(x)=0 。返回值fval是目标向量函数的值。