演化多目标优化中的几何热力学选择

Geometric Thermodynamical Selection for Evolutionary Multi-Objective Optimization

热力学遗传算法(Thermodynamical Genetic Algorithms,TDGAs)借鉴热力学中的自由能极小过程来统一处理多目标优化在逼近性和多样性两方面的任务.为提高TDGA的运行效率和解集分布均匀性,提出了一种几何热力学选择.在该选择中首先定义角度熵通过扇形采样来度量种群逼近方向的多样性.然后利用距离精英定义距离能量来度量种群的逼近程度,避免了耗时的非劣分层操作.此外,引入分量热力学替换规则以较低计算代价驱动种群的几何自由能快速下降.在多目标0/1背包问题上的实验结果表明,几何热力学选择极大地提高了TDGA的运行效率和解集分布均匀性;采用该选择的TDGA算法可生成与NSGA-II在逼近性和分布多样性上性能相当的解,但在运行效率上明显优于NSGA-II.

Thermodynamical genetic algorithms （TDGAs） simulate the minimization of free energy in thermodynamics to deal simultaneously with both convergence and diversity in multi-objective optimization.A geometric thermodynamical selection （GTS） is proposed to improve the running efficiency and the distribution uniformity of solutions of TDGA.In GTS,an angle entropy is introduced to measure the diversity of convergent directions by sector sampling and then a distance energy is presented to measure the extent of convergence by distance elitist rather than the expensive non-dominated sorting.In addition,a component thermodynamical replacement rule is used to force the geometric free energy of population to steeply descend with low computational costs.Experimental results on multi-objective 0/1 knapsack problems show that GTS remarkably improves the running efficiency and the distribution uniformity of solutions of TDGA.At the same time,TDGA with GTS produces a perfect convergence and spread of solutions as well as NSGA-II,while its running efficiency is much higher than that of NSGA-II.