演化多目标优化的锥束分解机理与高效算法研究

Two major development trends of multiobjective evolutiaonary algorithms (MOEAs) are hypervolume and decomposition. MOEAs based on decomposition attain much higher computational efficiencies, but the qualities of the approximate Pareto sets achieved by these algorithms are vulnerable to the facts such as the geometrical shapes of the Pareto frontiers (PFs). The hypervolume indicator is the only single set quality measure that is known to be strictly monotonic with regard to Pareto dominance. However, the high computational effort required for hypervolume.calculation has so far prevented to fully exploit the potential of this indicator. This project will study the mechanisms and methods to improve both the computaitonal efficiency and the solution set quality of MOEAs by combining the advantages of decomposition and hypervolume from the unique geometrical perspective of conical-beam partition of the objective space. This project includes the following research contents. First the objective space will be divided into a series of conical subrgions by introducing the concepts such as the utopian point and observation vectors and the disorder and unstructured population will be transformed into the orderly one with the conical neighborhood structures. Then the conical-beam partition of the objective space is used to explore more perfect conical-beam decomposition mechanisms, which will further improve the efficiency of MOEAs based on decomposition by assigning each scalar subproblem an exclusive conical subregion at the same time of decomposition. Next a conical hypervolume indicator will be proposed in order to successfully integrate the information about hypervolume into the scalar subproblems at the same time of conical-team decompostion. In this way, MOEAs can not only exploit the highly desirable mathematical characteristics of hypervolume to guide the population to search a high quality solution set, but also avoid the expensive hypervolume calculation by decomposition. This project will significantly improve both the computational efficiency and the solution set quality of MOEAs.

分解和超体积是当前多目标演化算法的两个主流发展方向，基于分解的算法虽具有较高的计算效率，但所求解集质量易受Pareto前沿形状的影响；超体积是已知的唯一一个关于Pareto占优严格单调的解集评价指标，但其极高计算成本阻碍了在算法中充分利用这一指标。本项目从锥束划分目标空间的独特几何视角结合分解与超体积的优点研究提高多目标演化算法计算效率和解集质量的方法。研究内容包括：引入理想点、观察向量等将目标空间划分为一系列锥形子区域，为无序无结构的种群赋予有序的锥形邻域结构；基于锥束划分探索更完善的锥束分解机理，在分解的同时给每个子问题分配一个独占的锥形子区域，进一步提高基于分解的算法的效率；通过引入锥超体积指标在锥束分解的同时成功融合超体积信息，使算法既能利用到超体积的理想数学特性引导种群搜索高质量的解集，又可通过分解避免高成本的超体积计算。本项目的研究将显著提高多目标演化算法的计算效率和解集质量。

分解和超体积是当前多目标演化算法的两个主流发展方向，基于分解的算法虽具有较高的计算效率，但所求解集质量易受Pareto 前沿形状的影响；超体积是已知的唯一一个关于Pareto 占优严格单调的解集评价指标，但其极高计算成本阻碍了在算法中充分利用这一指标。本项目从锥束划分目标空间的独特几何视角结合分解与超体积的优点探索了提高多目标演化算法计算效率和解集质量的方法。本项目主要研究内容和重要结果包括：通过引入理想点、观察向量等将目标空间划分为一系列锥形子区域，为无序无结构的种群赋予了有序的锥形邻域结构；建立了目标空间中每个锥形子区域只保留一个精英个体的锥束存档体系，为锥束存档体系设计了高维目标空间中锥形子区域的快速索引计算方法；提出了计算成本较小的基于惩罚的距离指标(PDI)作为分解后每个子问题的标量目标函数，可描述每个子区域中个体逼近前沿的程度和方向,设计使用PDI指标的锥束分解演化算法CDEA-PDI提高了多目标演化算法的效率; 进一步通过引入锥超体积指标在锥束分解的同时成功融合超体积信息，使算法既能利用到超体积的理想数学特性引导种群搜索高质量的解集，又可通过分解避免高成本的超体积计算；最后设计了锥超体积演化算法，在分解时不仅将多目标优化问题分解为一定数量的标量目标优化子问题，而且给每个子问题分配一个独占的锥形子区域, 每个新个体只需与其所在锥形子区域的精英个体进行一次锥超体积指标比较。在标准测试例和三杆桁架结构设计等工程问题上的实验结果表明，锥超体积演化算法显著提高了多目标演化算法的计算效率和解集质量。