【作者】 李锋；

【导师】 熊盛武；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2004， 硕士

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

【Abstract】 Many real-world problems involve two types of problem difficulty: i) multiple, conflicting objectives and ii) a highly complex search space. On the one hand, instead of a single optimal solution competing goals give rise to a set of compromise solutions, generally denoted as Pareto-optimal. In the absence of preference information, none of the corresponding trade-offs can be said to be better than the others. On the other hand, the search space can be too large and too complex to be solved by exact method. Thus, efficient optimization strategies are required that are able to deal with both difficulties.Evolutionary algorithms possess several characteristics that are desirable for this kind of problem and make them preferable to multi-objective optimization methods. In fact, various evolutionary approaches to multi-objective optimization have been proposed since 1985, capable of searching for multiple Pareto optimal solutions concurrently in a single simulation run. SPEA2 is one of the art of the date algorithms. The algorithm is a new multi-objective optimization evolutionary algorithm using elitism, in which fine-grained fitness assignment strategy, a density estimation technique, and an enhanced archive truncation method are used. The algorithm can converge to the Pareto optimal solutions rapidly and the non-dominated solutions gain better distribution and spread.Genetic algorithm is a class of effective algorithms based on natural selection and principle of genetics. Though GAs can find the compromise solutions in limited time, improving the speed of GA is an important issue when the problem is more complex and difficult. GA poses implicit parallelism and is suitable for implementation on large scale parallel computers. Dividing the whole population into sub-populations and coarse-grained island model of exchanging information among sub-populations are the most direct parallel method.A Parallel Strength Pareto Multi-objective Evolutionary Algorithm (PSPMEA) is proposed. PSPMEA is a parallel computing model designed for solving Pareto-based multi-objective optimization problems by using an evolutionary procedure. In this procedure, both global parallelization and island parallel evolutionary algorithm models are used. Each sub-population evolves separately with different crossover and mutation probability, but they exchange individuals in the elitist archive. In each sub-population, breeding and evaluation are implemented using multi-threaded mechanism. The benchmark problems numerical experiment results demonstrate that the proposed method can rapidly converge to the Pareto optimal front and spread widely along the front.Using the continuous test problems and the combinational test problems we compare the two algorithms: PSPMEA and SPEA2. Elitism, size of the population and exchanging among sub-populations are the key issues in PSPMEA. The results also show the PSPMEA is a promising parallel multi-objective evolutionary algorithm.更多还原