大家好，我是讯享网，很高兴认识大家。

注释：是学习之余整理的资料，如有不足的地方还请指教，十分感谢！

目录

1、多目标进化算法

1.1 多目标优化算法的简介

1.2 多目标优化算法的简介

2、SPEA算法的步骤

2.１ SPEA算法的特征

2.2 强度Pareto进化算法具体步骤

2.3 适应度赋值

2.4 聚类分析

2.5 SPEA算法存在着如下缺点：

3、SPEA2算法的步骤

3.1 强度Pareto进化算法2

 3.2 适应度赋值

3.3 外部档案维护 

4、SPEA2算法的应用举例

---

1、多目标进化算法

1.1 多目标优化算法的简介

强度Pareto进化算法(SPEA)是1999年由Zitzler以及Thiele提出的，之后许多研究人员开始把外部档案或外部种群结合到他们的MOEA中，精英保留策略成了第二阶段MOEA设计的基本步骤，算法搜索效率也得到明显改善。第二代算法的代表有NSGA2、Pareto档案进化策略(PAES)、Pareto包络选择算法(PESA)以及SPEA2等。

1.2 多目标优化算法的简介

MOEA必须包括:

①-组数量尽可能大的非劣解

②要求这组解逼近问题的全局Pareto最优前端

③尽可能均匀地分布在整个全局最优前端上。

大多数MOEA的设计都是围绕如何有效地实现上述3个目的，每种算法都是实现这些目的的特定方法的组合。

2、SPEA算法的步骤

2.１ SPEA算法的特征

(1)将非支配解存储在另一个不断更新的种群中

(2)根据一个个体独自地支配它的非支配解的个数计算适应度值

(3)使用Pareto支配关系保存种群多样性

(4)为了减少非支配解集并不破坏它的特征，加入了聚类分析过程

2.2 强度Pareto进化算法具体步骤

1)初始种群P、空的外部非劣解集NP；
2)将种群P中的非劣个体复制到非劣解集NP；

3)剔除集合NP中受种群P中个体支配的解，保留不受支配的解；

4)集合NP中的非劣解的个数＞事先给定的最大值，则通过聚类分析对集合NP进行修剪；

5)计算P、NP中的每个个体的适应度值；

6)利用二元锦标赛方法从P∪NP中选择个体进入下一代；

7）对个体实施交叉和变异操作；

8）如果最大代数达到，停止搜索；否则，转到步骤（2）

二元锦标赛方法

1、确定每次选择的个体数量N=2。

2、从种群中随机选择2个个体(每个个体被选择的概率相同) ，根据每个个体的适应度值，选择其中适应度值最好的个体进入下一代种群。

3、重复步骤(2)多次（重复次数为种群的大小），直到新的种群规模达到原来的种群规模。

2.3 适应度赋值

讯享网

三个非劣解所覆盖的目标空间分成了很多长方形区域，其中亮灰**域内的个体受到NP中较少的解支配，而暗灰**域的个体受到较多NP中的解支配。

                                                               适应度值计算

2.4 聚类分析

非劣解集大小必须受限，必须为保留在其中的解的最大个数，原因如下：

(1)MOP的非劣解集大小可能非常大，甚至是无穷大。

(2)实现算法的计算资源是有限的。

(3)档案维护的复杂性会随档案规模变大而显著增加。

(4)遗传漂移可能出现，因为在均匀采样过程中搜索空间中过度代表的区域总是优先被选择。

前三点意味着必须限制档案大小，而第四点表示对档案进行修剪可能对算法性能有利。

 SPEA采用如下聚类分析对非劣解集进行修剪：

1)初始化一个由非劣解集NP的解构成的聚类集C，每个解对应一个聚类；

(2)如果|C|< `N，转到(5);否则.转到(3)；（`N为外部非劣解集的最大值）
(3)计算所有聚类之间的距离，两个聚类C1和C2∈C之间的距离；

4)确定具有最小距离的两个聚类c1和c2∈C，然后调整聚类集 

 

 (5)确定每个聚类的代表个体。通常选择和同一聚类的其他个体之间的平均距离最小的个体作为该聚类的代表。

2.5 SPEA算法存在着如下缺点：

(1)SPEA的适应度赋值过程中，被相同档案成员支配的种群个体适应度相同，这意味着当外部档案只包含一个成员时,无论种群个体之间是否存在支配关系，所有种群个体都具有相同的适应度值，这种情况下,SPEA与随机搜索类似（随机搜索算法）;

(2)聚类分析能够减少非劣解集的大小，但它可能错误地删掉一些必须保存在非劣解集中的个体，影响算法的多样性。

3、SPEA2算法的步骤

3.1 强度Pareto进化算法2

(1)初始种群P0、空的外部档案A0，令t=0;
(2)计算Pt、At个体的适应度值;

At+1的大小＞`N，则修剪At+1；

如果At+1的大小＜`N，则将Pt和At中的受支配解加入到At+1中直到它的大小等于`N;

(4)如果t> T，则输出外部档案At+1并停止搜索。
(5)对外部档案At+1采用带替代的二元锦标赛方法选择个体进入交配池。

(6)对交配池和种群Pt+1实施交叉和变异操作,t = t+1，转到(2)。

 3.2 适应度赋值

为了避免被同样的外部档案成员支配的个体具有相同的适应度值，在SPEA2中，每个个体所支配的解和支配它的解都被考虑在内。

    种群和外部档案中的个体i都被赋予一个强度值S(i)，表示受该个体支配的解的数量。

在S(i)的基础上，个体i的原始适应度值R(i)等于支配该个体的所有个体的强度值之和，即：

 与SPEA不同，计算R(i)时，种群和外部档案内的个体都考虑在内，而且原始适应度值越小，说明支配该个体的个体少，R(i)=0表示个体i为非劣解。

原始适应度赋值过程引入密度信息以区分具有相同原始适应度值的个体。SPEA2采用k紧邻方法来计算个体i的密度值D（i）

以上式子中，ski为个体i与第k个近邻个体在目标空间上的距离，

最终，个体i的适应度值F(i)为原始适应度值与密度值之和。

K紧邻算法：

    在特征空间中，如果一个样本附近的k个最近（即特征空间中最邻近）样本的大多数属于某一类别，则该样本也属于这个类别。

3.3 外部档案维护 

SPEA2的档案维护过程与SPEA存在两点差异：

    (1)档案大小始终是一个常数；

    (2)档案维护避免了边界解从档案中移出。

外部档案维护

(1)将种群Pt和外部档案At的所有非劣解拷贝到At+1中，如果At+1的大小＝`N,则接受。

(2)如果|At+1|＜`N，则将Pt和At最好的`N-|At+1|个受支配解加入到At+1中。

(3)如果|At+1|＞`N，则不断地将档案At+1中的解移出直到|At+1|=`N 在修建档案过程中

在修建档案过程中，根据如下原则决定哪个解从档案中移出，如果个体i满足如下条件则从At+1中剔除。

对所有个体j，i＜dj,其中，i＜dj当且仅当对于

4、SPEA2算法的应用举例

(1)SPEA2算法在机器人路径中的应用

基于局部搜索的改进SPEA2算法应用在移动机器人的路径规划之中，针对同时存在多个静态障碍物的复杂环境下路径规划问题,进行环境建模和算法应用设计,并利用传统混合目标法和基于局部搜索的改进SPEA2算法进行路径规划仿真。

(2)基于改进SPEA2算法的火力分配问题

针对传统方法在求解火力分配多目标优化问题时收殓效果差以及Pareto前端分配不均匀等不足，将近邻传播算法传播到SPEA2算法中，改进了SPEA2算法的多样性保证策略，优化了算法性能。

(3) SPEA2多目标进化算法及其在车间调度中的应用

针对多目标优化问题，使用一种基于自适应选择进化算子的SPEA2算法对其进行求解。改进的算法将 SPEA2算法与具有很强局部搜索能力的DE算法融合，克服了 SPEA2算法由于采用固定的进化策略、进化过程中使用单一的进化算子，导致解的分布性不佳和易陷入局部最优解的问题，改进算法获得的非劣解集具有更好的收敛性和分布性。