多目标演化算法及在优化问题中的应用

解决现实世界中的许多问题会遇到两种类型的难度：Ⅰ)多个相互冲突的目标，Ⅱ)高维复杂的搜索空间。就第一点而言，与单目标优化不同的是多个相互竞争目标的优化结果是得到一组可行解，一般被称作Pareto最优解集。由于缺少喜好信息，在折中解中找不到一个解比另一个解更好。就第二点而言，若使用精确的方法解决多目标优化问题，搜索空间太大而且很复杂。因此，需要设计高效的优化策略来解决这两个问题。 演化算法所具有的几个特征很适合解决这类问题，相对于经典的优化方法而言，演化算法更受欢迎。实际上，自从1985年以来，研究者们已经提出了许多基于演化计算的多目标优化算法，这些算法能够在一次独立的运行中同时搜索到多个Pareto最优解。SPEA2算法就是其中一种优秀的算法。SPEA2算法是一种新的使用了精英机制的多目标优化演化算法，它采用了细粒度赋值策略和密度估计技术，整个算法可以快速收敛到Pareto最优解，并且可以获得很好的分布性和延展性。 遗传算法(GAs)是一类基于自然选择和遗传学原理的有效搜索方法，虽然GAs通常能在合理的时间内找到问题的满意解，但随着求解问题的复杂性及难度的增加，提高GAs的运行速度便显得尤为突出。GAs具有天然的并行性，非常适合于在大规模并行计算机上实现，把串行GAs中的单一群体分成多个子群体，各子群体之间相互交换信息的粗粒度并行是将GAs并行化的最直接方式。 本文结合SPEA2算法，设计了一个有效的并行增强Pareto多目标演化算法(PSPMEA)。该算法同时采用了全局并行模型和粗粒度并行岛模型。在岛模型中，首先将整个群体划分成若干个子群体，在每个子群体中执行遗传算法的各步骤，并每隔一定的代数交换各子群中的精英个体；在每个子群体中，个体的评价和遗传操作使用多线程程序设计，各操作是并发进行的，这是全局并行模型。在演化过程的最后阶段，就能够找到最优个体。在做了这两种方式的并行化以后不仅可以获得更好的计算性能，在Pareto最优解集的优化效果上有更显着的改进。 通过连续测试问题和组合测试问题的实验数据对比与分析，精英机制， 群体规模以及子群个体迁移都是影响PSPMEA算法的关键因素。实验的结 果也表明了PSPMEA算法是一个高效的并行多目标优化演化算法。