求解矩形放置问题的亲属帮助遗传算法

用基于几何位置的方法求解矩形放置问题,解空间有限,且包含最优放置,但解空间太大。为了解决这个问题,将基于几何位置的序列对算法作为遗传算法的编解码过程,同时根据序列对编码空间中局部最优解相互间保持一定距离的特点,从父代中随机地选出一定比例的个体,用这些个体作为排斥体,使子代个体与排斥体都保持一定的距离,有效地避免了种群过早收敛到局部最优解。3组试验表明:这种算法在问题规模小时能有效地搜索到全局最优解;在问题规模较大时,能得到较好的结果。

Relatives assist genetic algorithm for the rectangle packing problem

When the rectangle packing problem(RPP) is solved using the geometry position-based method,the solution space contains the best placement but the space is very large.An algorithm combining the geometry position-based method with a genetic algorithm was developed to search in this large space.The local solution space characteristics are used to design the relatives assist genetic algorithms(RAGA),in which a certain ratio of individuals are chosen from the parents' generation for using as the excluders to keep the offspring further away.Three experiments show that RAGA is good for finding the global best for small problems and keeps the population evolving for large problems.