并行混合遗传算法及其在布局设计中的应用

A Parallel Hybrid Genetic Algorithm and Its Application to Layout Design

布局问题在理论上属于NPC问题，在工程实践上具有广泛的应用。为较好地求解该问题，该文以并行遗传算法(PGA)为基础，针对其早熟和收敛速度慢两大缺陷加以改进，给出了一种并行混合遗传算法(PHGA). PHGA采用该文提出的压力插值排序选择算子，起到了双重作用：一是在进化初期可以防止早熟；二是在进化后期有利于加快算法的收敛。算法利用混沌初始化可提高初始群体的质量，并依自适应交叉和变异概率值对子群体进行分类，与Powell法混合可以很好地改善算法的局部搜索性能。文中通过标准函数优化和布局设计的算例验证了该算法的可行性和有效性。

Packing and layout problems belong to NPC problem theoretically and they have extensive engineering applications practically. Parallel genetic algorithm (PGA) is relatively effective to solve this kind of problems. But there still exist two main defects, i.e. premature convergence and slow convergence rate. To overcome them, a parallel hybrid genetic algorithm (PHGA) is proposed based on PGA. In this paper, Interpolating rank-based selection operator with pressure is introduced into PHGA. And it has double functions. One is that this selection operator can prevent the algorithm from premature at the early stage of evolution. The other is that it can accelerate convergence rate at the late stage of evolution. To produce more high quality initial individuals, chaos initialization is adopted. And adaptive crossover and mutation operators are adopted as well. In this algorithm, subpopulations are classified as several types according to the values of crossover and mutation probability. Hybridized with Powell algorithm can improve local searching performance of the proposed algorithm considerably. Examples, including a typical function optimization problem and a layout design problem, show that PHGA is feasible and effective.