INCORPORATION OF A DECISION SPACE DIVERSITY MAINTENANCE MECHANISM INTO EVOLUTIONARY MULTI-OBJECTIVE OPTIMIZATION ALGORITHMS

多目标演化优化算法的决策空间多样性维护机制研究

胡晨旭

11849247

硕士

计算机科学与技术

Hisao Ishibuchi

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

In recent years, multi-modal multi-objective optimization has received extensive attention. A lot of scholars have researched it. In a multi-modal multi-objective opti- mization problem, all Pareto optimal solutions that have the same objective vector but distribute differently in the decision space are required to be found. This thesis studies the performance of several representative evolutionary multi- objective optimization algorithms on a multi-modal multi-objective optimization problem. The experimental results suggest that since there lacks the mechanism to maintain diversity, the diversity of solutions in the decision space becomes worse and worse during algorithm execution. In order to handle this issue, we proposes two mechanisms to maintain the diversity of solutions in the decision space. The main contributions of this thesis are as follows: (1) We propose a subpopulation searching method to solve multi-modal multi- objective optimization problems. The method divides the population into several subpopu- lations. The environmental selection and reproduction procedures perform independently in each subpopulation. Two metrics are designed to make solutions form niches in the decision space. The first metric is the distance between a solution and the center of the subpopulation where it exists. The second metric is the distance between a solution and the center of another nearest subpopulation. The two metrics make the subpopulations away from each other, thus to form niches in the decision space. We apply the subpop- ulation searching method to SPEA2 and IBEA. The experimental results show that the subpopulation searching method can significantly improve the decision space diversity for the two algorithms. (2) We propose the neighborhood anchor method to solve multi-modal multi-objective optimization problems. In each generation, the method finds 𝑁𝑛𝑠 nearest neighbors in the archive for each solution in the population. Then, the method selects the worst neighbor based on fitness function values. If the fitness function value of the solution 𝒔 is better than the fitness function value of its worst neighbor 𝒘, solution 𝒔 will replace the worst neighbor 𝒘. The offspring solutions are generated by the solutions in the archive. We apply the neighborhood anchor method to SPEA2 and IBEA. The experimental results show that the neighborhood anchor method can also improve the decision space diversity for the two algorithms.

多模态多目标优化问题在学术研究和工业应用中广泛存在，比如航天发射任务设计、汽车发动机设计等等。近年来，多模态多目标优化受到越来越多的关注, 许多学者对此进行了研究。在多模态多目标优化问题中，优化目标是找到所有具有相同目标向量但在决策空间中分布不同的帕累托最优解。 本论文研究了几种具有代表性的多目标演化优化算法在多模态多目标优化问题上的表现。实验结果表明，随着算法的执行，由于没有解的多样性的保护机制， 决策空间中解的多样性会变得越来越差。为了解决该问题，本论文提出了两种决策空间中解的多样性的维护机制。 本论文的主要工作包括： （1） 提出了一种子种群搜索方法来求解多模态多目标优化问题。首先，将一个种群分为几个子种群；之后，在优化过程中，每个子种群对应一个帕累托最优解集。配对、杂交、变异、环境选择等优化过程在每个子种群中独立进行。为了使子种群互相远离，使用了两个指标来使得解在决策空间中形成小环境。第一个指标是解与其所处的子种群的中心之间的距离。第二个指标是解与另一个最近的子种群的中心之间的距离。将这种方法应用到 SPEA2 和 IBEA 两种具有代表性的多目标演化优化算法上。实验结果表明对于大多数多模态多目标优化问题，子种群搜索方法能够显著提高决策空间中解的多样性。 （2） 提出邻近锚方法来求解多模态多目标优化问题。该方法使用了一个额外的种群 𝑃𝑎 来保存搜索到的解。在算法运行的每一代中，对于每个在原有种群 𝑃𝑠 中的个体 𝒔，该方法在 𝑃𝑎 中找出在决策空间中距离 𝒔 最近的 𝑘 个个体并比较 𝒔 是否比找到的 𝑘 个个体中最差的那个好。如果 𝒔 比最差的那个个体好，该方法就用 𝒔 来替代那个最差的个体。将这种方法应用到 SPEA2 和 IBEA 两种多目标演化优化算法上。实验结果表明对于大多数多模态多目标优化问题，邻近锚方法能够显著提高决策空间中解的多样性。

Evolutionary algorithms Multi-modal multi-objective optimization Decision space diversity

演化算法 多模态多目标优化 决策空间多样性

英语

联合培养

南方科技大学

Hu CX. INCORPORATION OF A DECISION SPACE DIVERSITY MAINTENANCE MECHANISM INTO EVOLUTIONARY MULTI-OBJECTIVE OPTIMIZATION ALGORITHMS[D]. 深圳. 哈尔滨工业大学,2020.