多目标优化笔记

 多目标的优化问题的一般公式可以如下：

在两个目标函数中，它们之间可能是存在着一定的矛盾，也就是说，当一个目标函数的提高需要以另外一个目标函数的降低作为代价。在这个时候，我们就称，这样的两个解是非劣解，也就是长说的Pareto最优解。多目标优化算法就是要找到这些Pareto最优解。 

在单目标优化问题中，通常最优解只有一个，而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中，各个目标之间相互制约，可能使得一个目标性能的改善往往是以损失其它目标性能为代价，不可能存在一个使所有目标性能都达到最优的解，所以对于多目标优化问题，其解通常是一个非劣解的集合——Pareto解集。   在存在多个Pareto最优解的情况下，如果没有关于问题的更多的信息，那么很难选择哪个解更可取，因此所有的Pareto最优解都可以被认为是同等重要的。由此可知，对于多目标优化问题，最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而，在多目标优化中主要完成以下两个任务：

1)找到一组尽可能接近Pareto最优域的解。 2)找到一组尽可能不同的解。

  第一个任务是在任何优化工作中都必须的做到的，收敛不到接近真正Pareto最优解集的解是不可取的，只有当一组解收敛到接近真正Pareto最优解，才能确保该组解近似最优的这一特性。   除了要求优化问题的解要收敛到近似Pareto最优域，求得的解也必须均匀稀疏地分布在Pareto最优域上。一组在多个目标之间好的协议解是建立在一组多样解的基础之上。因为在多目标进化算法中，决策者一般需要处理两个空间——决策变量空间和目标空间，所以解(个体)之间的多样性可以分别在这两个空间定义。例如，若两个个体在决策变量空间中的欧拉距离大，那么就说这两个解在决策变量空间中互异；同理，若两个个体在目标空间中的欧拉距离大，则说它们在目标空间中互异。尽管对于大多数问题而言，在一个空间中的多样性通常意味着在另一个空间中的多样性，但是此结论并不是对所有的问题都是成立的。对于这样复杂的非线性优化问题，要找到在要求的空间中有好的多样性的一组解也是一项非常重要的任务。  

最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。

使多个目标在给定区域同时尽可能最佳，多目标优化的解通常是一组均衡解(即一组由众多 Pareto最优解组成的最优解集合 ,集合中的各个元素称为 Pareto最优解或非劣最优解)。

①非劣解——多目标优化问题并不存在一个最优解，所有可能的解都称为非劣解，也称为Pareto解。 ②Pareto最优解——无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解。

 如何实现多目标优化？有哪些方法？

多目标优化问题不存在唯一的全局最优解 ,过多的非劣解是无法直接应用的 ,所以在求解时就是要寻找一个最终解。

（1）求最终解主要有三类方法：

一是求非劣解的生成法，即先求出大量的非劣解，构成非劣解的一个子集，然后按照决策者的意图找出最终解；（生成法主要有加权法﹑约束法﹑加权法和约束法结合的混合法以及多目标遗传算法）

二为交互法，不先求出很多的非劣解，而是通过分析者与决策者对话的方式，逐步求出最终解；

三是事先要求决策者提供目标之间的相对重要程度，算法以此为依据，将多目标问题转化为单目标问题进行求解。

（2）多目标优化算法归结起来有传统优化算法和智能优化算法两大类。

传统优化算法包括加权法、约束法和线性规划法等，实质上就是将多目标函数转化为单目标函数，通过采用单目标优化的方法达到对多目标函数的求解。

线性加权求和法——对多目标优化问题中的N个目标按其重要程度赋以适当的权系数，其乘积和作新的目标函数，再求最优解。

智能优化算法包括进化算法（Evolutionary Algorithm, 简称EA）、粒子群算法（Particle Swarm Optimization, PSO）等。

两者的区别——传统优化技术一般每次能得到Pareo解集中的一个，而用智能算法来求解，可以得到更多的Pareto解，这些解构成了一个最优解集，称为Pareto最优解（任一个目标函数值的提高都必须以牺牲其他目标函数值为代价的解集）。

多目标进化算法 (MOEA ) ①MOEA通过对种群 X ( t)执行选择、交叉和变异等操作产生下一代种群 X ( t + 1) ； ②在每一代进化过程中 ,首先将种群 X ( t)中的所有非劣解个体都复制到外部集 A ( t)中； ③然后运用小生境截断算子剔除A ( t)中的劣解和一些距离较近的非劣解个体 ,以得到个体分布更为均匀的下一代外部集 A ( t + 1) ； ④并且按照概率 pe从 A ( t + 1)中选择一定数量的优秀个体进入下代种群； ⑤在进化结束时 ,将外部集中的非劣解个体作为最优解输出。