Strength Pareto Evolutionary Algorithm (SPEA)
算法步骤：
Step1：初始化种群P(大小为N)和空的外部储备集P‘(大小为N’)
Step2：将P中的非支配解复制到P’
Sep3：如果P’大小超过N’,通过聚类的方法移除
Step4：计算P和P’中的所有个体适应值
Step5：从P+P’中进行选择操作，直到交配池填满
Step6：交配池中个体进行变异和交叉操作
Step7：是否达到最大迭代次数，if 停止， else Step2.
关于适应值分配
对于P’来说， f i = s i = n N + 1 f_i=s_i=\frac{n}{N+1} fi=si=N+1n 其中 s i ∈ [ 0 , 1 ) s_i\in[0,1) si∈[0,1),n是P’中每个个体i支配P中的解的个数,加1保证取值在0到1区间内
对于P来说， f j f_j fj=1+ ∑ i , j ≺ ‾ i s i \sum_{i,j\underline{\prec}{i}}s_i ∑i,j≺isi w h e r e f j ∈ [ 1 , N ) where f_j\in[1,N) wherefj∈[1,N), s i s_i si表示中种群P中的个体j被非支配解集P’中个体i支配。即P中所有支配j的个体。加1保证P’中的适应度均比P好（适应度值越小，具体有更高的保留到下一代的概率）。如下图所示，
文献中提到的聚类方法
当非支配解集增加导致选择压力减小，减慢搜索速度。
聚类步骤：
Step1：初始化聚类集合C,P’中的每个个体构成一个聚类。 C = ∪ i { { i } } C=\cup_i\{\{i\}\} C=∪i{{i}}
Step2：if |C| ≤ \leq ≤N’ (即簇的所有个体小于给定的最大值), go step5, else Step3.
Step3：计算不同簇间两个个体的距离
d = 1 ∣ c 1 ∣ ⋅ ∣ c 2 ∣ ⋅ ∑ i 1 ∈ c 1 , i 2 ∈ c 2 ∣ ∣ i 1 − i 2 ∣ ∣ d=\frac{1}{|c_1|\cdot|c_2|}\cdot\sum_{i_1\in{c_1},i_2\in{c_2}}\lvert\vert{i_1-i_2}\vert\vert d=∣c1∣⋅∣c2∣1⋅i1∈c1,i2∈c2∑∣∣i1−i2∣∣
Step4：将存在最小距离d的两个簇合并，go to Step2。
Step5：从每个簇中选择一个具有代表个体。（簇内某个个体到其他个体的平均距离最小的个体）作为代表解。
参考文献：Multiobjective Evolutionary Algorithms:A Comparative Case Study and the Strength Pareto Approach
算法升级SPEA2-----Improving the Strength Pareto Evolutionary Algorithm
SPEA缺点：
1.当archive中只有一个，多个个体具有相同适应值。选择压力减小，退化成随机搜索算法
2.聚类只用在储备集archive而为用在中种群所有个体中，丢失外部解集。
3.
与SPEA不同之处：
- 适应度计算
- 邻近估计，更加精准搜索
- 新的存档截断方法，保证边界值的保留
-
archive大小固定
算法步骤：
N N N（种群大小）, N ‾ ( a r c h i v e 大 小 ) \overline{N}(archive大小) N(archive大小)， T ( 最 大 迭 代 次 数 ) T(最大迭代次数) T(最大迭代次数)
Step1：初始化，种群 P 0 P_0 P0,空的archive P ‾ 0 \overline{P}_0 P0, t = 0 t=0 t=0
Step2：计算适应度
Step3：环境选择：将 P t P_t Pt和 P ‾ t \overline{P}_t Pt中的所有非支配解集复制到 P ‾ t + 1 \overline{P}_{t+1} Pt+1
如果 P ‾ t + 1 \overline{P}_{t+1} Pt+1个数> N ‾ \overline{N} N,进行剪枝操作
否则，选择 P t P_t Pt和 P ‾ t \overline{P}_t Pt中的支配解集添加到 P ‾ t + 1 \overline{P}_{t+1} Pt+1中,具体下方的环境选择
Step4：t>T的或者满足其他的终止条件，将A作为PT+1中非支配解所代表的决策变量集合输出
Step5：选择操作，对 P ‾ t + 1 \overline{P}_{t+1} Pt+1进行锦标赛选择放入交配池
Step6：交配池中的个体进行重组和变异，,将结果存入集合 P ‾ t + 1 \overline{P}_{t+1} Pt+1，迭代次数+1回到Step2.
适应度计算：
S ( i ) = ∣ { j ∣ j ∈ P t + P ‾ t ∧ j ≺ i } ∣ S(i)=|\{j|j\in{P_t+\overline{P}_t}\land{}j\prec{i}\}| S(i)=∣{j∣j∈Pt+Pt∧j≺i}∣
R ( i ) = ∑ j ∈ P t + P ‾ t , i ≺ j S ( j ) R(i)=\sum_{j\in{}P_t+\overline{P}_t,i\prec{j}}{S(j)} R(i)=∑j∈Pt+Pt,i≺jS(j)
其中 s ( i ) s(i) s(i)表示个体i支配的个体数。R(i)表示原始适应值，表示个体i，支配i的每个个体j支配的所有个体数之和
多目标优化算法之SPEA2 当多个个体不相互支配时，R(i)难以实现其作用，因此，在SPEA2中。选k邻近估算密度。计算每个个体到储备集和种群中所有个体的距离，按照递增排序，选第k个作为 σ i k \sigma^k_i σik
D ( i ) = 1 σ i k + 2 D(i)=\frac{1}{\sigma^k_i+2} D(i)=σik+21其中 k = N + N ‾ k=\sqrt{N+\overline{N}} k=N+N
,分母加2保证值(0,1)
F ( i ) = R ( i ) + D ( i ) F(i)=R(i)+D(i) F(i)=R(i)+D(i)
环境选择
（1） ∣ p ‾ t + 1 ∣ < ∣ N ‾ ∣ |\overline{p}_{t+1}|<|\overline{N}| ∣pt+1∣<∣N∣, P t + P ‾ t P_t+\overline{P}_t Pt+Pt中所有个体根据适应度排序选择前 N ‾ − ∣ p ‾ t + 1 ∣ \overline{N}-|\overline{p}_{t+1}| N−∣pt+1∣个
（2） ∣ p ‾ t + 1 ∣ > ∣ N ‾ ∣ |\overline{p}_{t+1}|>|\overline{N}| ∣pt+1∣>∣N∣，其中 j ∈ P ‾ t + 1 j\in\overline{P}_{t+1} j∈Pt+1.每次迭代中淘汰个体i，其中i满足
i ≤ d j : ⟺ ∀ 0 < k < ∣ P ‾ t + 1 ∣ ： σ i k = σ j k ∨ ∃ 0 < k < ∣ P ‾ t + 1 ∣ : [ ( ∀ 0 < l < k : σ i l = σ j l ) ∧ σ i k < σ j k ] i\leq_dj:\iff \forall0<k<|\overline{P}_{t+1}|：\sigma_i^k=\sigma_j^k\lor\exist 0<k<|\overline{P}_{t+1}|:[(\forall 0<l<k:\sigma_i^l=\sigma_j^l)\land\sigma_i^k<\sigma_j^k] i≤dj:⟺∀0<k<∣Pt+1∣：σik=σjk∨∃0<k<∣Pt+1∣:[(∀0<l<k:σil=σjl)∧σik<σjk]其中 σ i k \sigma_i^k σik
代表个体i与第k个邻居的距离，上面公式表示具有最小距离的个体被选中删除，如果有多个个体都是距离最小值，则考虑第二个最小距离值，以此类推.具体情况如下图：
多目标优化算法之SPEA2
参考文献：SPEA2: Improving the Strength Pareto Evolutionary Algorithm