NSGA-2多目标遗传算法.有人能给我一个"简单的解释"吗？

Question

我正在研究遗传算法.

有两个目标,每个目标都有自己的适应值(fv1,fv2).

我知道世代(SGE)和稳态(SS)遗传算法是如何工作的.

我试图了解NSGA-2和SPEA-2(我正在使用Java库JCLEC的实现)如何工作,特别是:

• 什么是"外部人口",应该如何规模
• SS和SGE单目标算法的区别是什么(每个人只有一个健身值的事实部分)

如果有人正在使用JCLEC库,这些是我设置的参数:

• 外部人口:1000
• k值:10
• 其他属性与SS和SGE相同(人口规模:100,交叉:MPX交叉等...)

Answer 1

这是NSGA-II的解释

1. 首先,它随机初始化人口.
2. 根据Pareto非支配集对染色体进行分类并放入前沿.在帕累托前沿,染色体的排序基于溶液之间的欧几里德或I-dist(NSGA-II中使用的术语).通常,远离(不拥挤)其他解决方案的解决方案在选择时被赋予更高的偏好.这样做是为了设置多样化的解决方案并避免拥挤的解决方案集.
3. 从当前群体中挑选出最好的N(群体)染色体并将其放入交配池中
4. 在交配池中,锦标赛选择,交叉和交配完成.
5. 交配池和当前人口相结合.对得到的集进行排序,最好的N染色体进入新的群体.
6. 转到步骤2,除非已达到最大代数.
7. 解决方案集是最新人口中排名最高的帕累托非支配集.

Answer 2

我建议阅读有关这些算法的论文，它们很好地解释了功能：

• 黛布、普拉塔布、阿加瓦尔、梅亚里文。一种快速的精英多目标遗传算法：NSGA-II。IEEE Transactions on Evolutionary Computation 6(2), pp. 182-197, 2002。
• 齐茨勒，劳曼斯，蒂勒。SPEA2：改进强度帕累托进化算法。技术报告 (TIK-103)，瑞士联邦理工学院 (ETH)，2001 年。

我相信您可以在网上找到这些出版物的 PDF。

关于稳态遗传算法和世代遗传算法之间的区别：在代代替换中，您只使用旧种群中的基因创建一个与旧种群大小相同的全新种群，然后将其作为一个整体进行替换。在稳态替换中，您只创建一个新个体，然后只替换种群中的一个个体。稳态 GA 通常收敛得更快，但它们不太可能找到好的局部最优解，因为它们不像使用代代替换那样探索适应度景观。当然，这取决于问题，有时您可以选择要替换多少旧代，这允许您在这两者之间具有任意比例。

还有更多的多目标算法，例如AbYSS和PAES。