张谋钊-2016.12.02组会-多目标进化算法MOEA/D-SAS

Mz..

标题：张谋钊-2016.12.02组会-多目标进化算法MOEA/D-SAS
报告人：张谋钊

摘要：
针对MOEA/D-STM的以下几个缺点，作者提出了MOEA/D-SAS。
1）当问题的Pareto Front不规则时，比如不连续，解的分布性便会收到影响。
2）STM的配对模型复杂度太高。每个子问题要排序所有解 ，每个解要排序所有子问题，复杂度O(NM log M)太高。

SAS(Sorting and Selectiong)作为进化过程中的选择算子,分为排序和选择两大部分。
排序：对于每个子问题，只排序离子问题最近的L个解，这样复杂度相比STM便会低很多。且收敛性不会受到太大的影响，因为L是随着程序的进展而变化的。算法一开始初始化为2N，这时强调收敛性，因为L越大收敛性越好。L会随着迭代自适应下降，放缓收敛，兼顾收敛性的同时增强分布性。
选择：在步骤1）中排序结果中，选择排名靠前，即收敛性好的解，作为种群的大部分解。并利用解与解之间的余弦距离信息，选出有利于提高分布性的解加入（ABS算法）。相对于其他提高分布性的算法，如niche-couting，ABS从解与解之间夹角信息去考虑多样性，是一种更加细粒度的算法。
在排完序后的选择过程中，并没有考虑解来自于哪个子问题，只考虑了解本身的收敛性和分布性，所以从另一个角度来看，就是子问题可以配对零个或多个解。这样的话，问题1）的分布性差问题就迎刃而解了。
       
参考论文：
[1]Cai X, Yang Z, Fan Z, et al. Decomposition-Based-Sorting and Angle-Based-Selection for Evolutionary Multiobjective and Many-Objective Optimization.[J]. IEEE Transactions on Cybernetics, 2016:1-14.
[2]Li K, Zhang Q, Kwong S, et al. Stable Matching Based Selection in Evolutionary Multiobjective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(6):909-923.