自收缩性的演化算法及其在布局优化问题中的应用

Self-Contractile Evolutionary Algorithm and Its Application in Layout Optimization

布局优化问题是现代工程应用中广泛存在的一类组合优化问题,但在理论上它却属于NPC(NP-Complete)问题,如果需考虑性能约束,则问题将更难于求解。论文基于演化算法自适应,自组织,自学习的特性,针对布局优化问题自身的特点,提出了一种自收缩性的演化算法(SCEA)。该算法采用浮点编码方式,定义了二元实向量类型的适应值及适应值间的严格偏序关系。算法借鉴日常生活中的一个简单事实—振动容器则装物更多,引入了三类自适应性的收缩算子(其中第三类特别适用于带性能约束的布局优化问题)。此外,文中使用了对带约束的函数优化问题特别有效的多父体杂交算子,并且针对带性能约束的布局优化问题,提出了“零性能约束初始化”过程。文后,引用了两个带性能约束的布局优化问题的已知例子和一个作者构造的较大规模布局优化问题的例子,实验结果表明,前两个问题对比目前已知最好结果无论在求解时间或结果的精度上均有较大突破,后一个问题也获得了相当好的结果,从而充分验证了算法的有效性和可行性。

Layout optimization problems arise widely in modern engineering applications and are now recognized as an important category of combinatorial optimization problems.However most unconstrained layout optimization problems are NP-Complete.The constrained layout optimization problems which typically arise in practice are usually equally difficult.This paper proposes a self-contractile evolutionary algorithm(SCEA),aimed at layout optimization problems ,and taking advantage of the self-adaptation and self-organization properties of evolutionary algorithms (EAs ).The system uses real-number encoding,and defines the fitness value by a two-dimensional vector,inducing a strict partial ordering on the population individuals.The algorithm borrows an idea from our daily lives-the authors shake a container in order settle its contents-suggesting three self-adaptive contraction operators(one in particular being especially applicable to con-strained layout optimization problems ).The authors also adopt the multi-parent crossover operator,which has been previ-ously shown to be very effective in solving constrained function optimization problems.That system in this paper also makes use of a specific initialization procedure,“zero-constraint initialization”,which the authors believe to be especially suited for constrained layout optimization.They compare the performance of the system on two constrained layout opti-mization benchmarks and on a large-scale unconstrained test case.Experimental results demonstrate a dramatic improve-ment on the constrained layout problems ,whether measured in time efficiency or in precision.The results on the large-scale unsconstrained problem are also good.Their algorithm has been demonstrated to be both feasible and efficient.