自适应交配限制概率的自组织多目标演化算法

Adaptive mating restriction probability-based self-organizing multiobjective evolutionary algorithm

摘要:

为平衡多目标演化算法求解不同优化问题以及求解同一优化问题时不同搜索阶段的勘探与开采能力,并考虑到减小聚类算法辅助演化算法时产生的计算开销,提出了一种基于自适应交配限制概率的自组织多目标演化算法（adaptive mating restriction probability based self-organizing multiobjective evolutionary algorithm, ASMEA）.首先,ASMEA在每一代利用自组织映射（self-organizing map, SOM）算法建立了演化种群个体间的邻居关系,基于此关系有利于算子实施恰当的重组操作,并在演化算法后期产生优质解,与此同时,为了节省利用SOM建立当前种群个体之间的邻居关系时引起的计算开销,将SOM与演化算法相融合,交替地进行SOM训练与种群演化.然后,运用交配限制概率控制交配父代来源于SOM发现的邻居种群或者是整个种群,以分别加强开采和勘探. 最后,根据采用不同父代来源的重组在过去一定代数产生后代个体的效用,自适应地调整算法的交配限制概率. 利用ASMEA和5种具有代表性的多目标演化算法对标准测试题进行求解,求解结果表明:ASMEA在搜索质量、搜索效率以及可视化方面优于其他5种算法,从而验证了ASMEA算法对多目标优化问题具有良好的求解性能.

Abstract:

To balance the exploration and exploitation in the searching process for different optimization problems and the same optimization problem in different search phases, as well as to reduce the computational cost, an adaptive mating restriction probability-based self-organizing multiobjective evolutionary algorithm (ASMEA) was proposed. Firstly, the self-organizing map (SOM) algorithm was used to establish the neighborhood relationships among the population individuals in ASMEA. The appropriate reproduction based on the above relationship is helpful to produce high quality solutions during the later period of the searching process. To reduce the computational cost of the cluster, the evolutionary algorithm was combined with SOM. At each generation, ASMEA alternately conducts the SOM training step and evolves the population. Secondly, the mating restriction probability was set to control the mating parents selected from both the neighbor population built by SOM and the whole population, so as to strengthen the exploitation and exploration respectively. Lastly, the mating restriction probability was self-adaptively updated in each generation by the utility of generation offspring based on different paternal sources in previous generations. ASMEA and five representative multiobjective evolutionary algorithms were experimented on a number of test instances. Results suggest that ASMEA performed better than the others on search quality, search efficiency, and visual comparison, which verified the ability of ASMEA to solve complicated multiobjective optimization problems.