融合空间信息的高效约束优化演化算法及其应用研究

At the same time in search,using the feasible information of population can be considered as an effective way for improving solutions'' quality of the constrained optimization evolutionary algorithm. In the current times, the decision space information of feasible solutions is only used by algorithms based on regional reduction, while the objective space information of infeasible solutions is used by algorithms based on multi-objective techniques in which non-dominated sorting is the main reason of large computation cost. At this foundation, some “potential” feasible information respectively in the decision space or objective space is fused. Our project from the fusion point of view proposes a method to improve solutions’ quality and computational efficiency of constrained optimization evolutionary algorithms. On the one hand, an relative feasible component model is set to collect relative feasible information of each dimensional component of infeasible solutions in decision space, then a feasible component constrained operator with the above relative feasible information is designed to improve feasible quality of new generated solutions. On the other hand, the project introduces some geometric elements (such as angle, distance) to evaluate the quality of solutions, and designs an efficient geometric sorting mechanism to maintain the diversity of “high quality” infeasible solutions in population. The goal of this sorting mechanism is that the algorithm not only successfully integrates non-dominated information of infeasible solutions in objective space to guide the population into the feasible region, but also avoids the high cost of non-dominated sorting in order to effectively improve the computational efficiency.

在搜索的同时利用种群的可行信息是提高约束优化演化算法求解质量的有效途径。目前基于区域缩减的算法仅利用了可行解在决策空间中的信息，而基于多目标技术的算法虽然利用了不可行解在目标空间中的信息，但耗时的非劣排序导致其计算开销较大。本项目从融合不可行解在决策空间与目标空间中的“潜在”可行信息的独特视角研究提高约束优化演化算法求解质量和计算效率的方法。本项目一方面建立相对可行分量模型来收集不可行解在决策空间上各维分量的相对可行区间信息，并设计可行分量约束算子有效利用不可行解在决策空间中的可行信息提高新生成解的可行质量。另一方面,本项目在二维目标空间上引入角度、距离等几何元素评价解个体的质量，设计一种高效的几何排序机制保持种群中“高质量”不可行解的多样性，使得演化算法既能成功融合不可行解在目标空间中的非劣信息引导种群从不可行域搜索到可行域，又避免了高成本的非劣排序从而有效提高算法的计算效率。

基于大多数待求解的带稀疏约束的约束优化问题中普遍存在着各约束条件仅关联部分决策分量的现象，本项目从各约束条件满足自身约束要求的相对可行域、约束优化问题的真实可行域和不可行域三者之间的空间关系出发，分析了决策变量中各维分量与约束条件之间的内部对应关系，利用该关系建立了相对可行分量模型来描述不可行解在决策空间上各维分量的相对可行区间信息，提出了约束优化问题的一种稀疏性度量，并针对带稀疏约束的优化问题设计了基于可行分量的排序策略有效利用不可行解在决策空间中的可行信息引导不可行解向可行解的转化，实验表明在比较稀疏的约束优化问题上基于分量的排序策略通常具有较好的性能。此外，已有的基于多目标技术算法虽然利用了不可行解在目标空间中的信息，但耗时的非劣排序导致其计算开销较大。为了以较低计算成本来度量二维目标空间中解个体的质量，本项目借助了多种几何概念来衡量解个体的目标优化逼近程度与约束违反程度，实现了利用不可行解的非劣信息引导种群搜索，有效避免了高成本的非劣排序并充分利用了不可行解的“有效”信息提高搜索过程中的解质量及算法的计算效率。