求解度约束最小生成树问题的自适应遗传算法

An Adaptive Genetic Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

在遗传算法中一个关键问题是必须采取措施保持种群多样性,防止算法出现早熟收敛。本文提出了一种基于父个体相似度的自适应遗传算法,使用新的自适应遗传操作策略以保持种群多样性。将新算法用于求解图的度约束最小生成树问题,实验结果表明本方法到比不使用父个体相似度信息的普通遗传算法权值更低的度约束最小生成树。

In Genetic Algorithm, the key question is to reserve population's diversity by using some methods in order to prevent premature convergence. This paper proposes a new adaptive genetic algorithm based on parents' similarity(AGABPS). To keep population's diversity, it employs new adaptive genetic operation strategy which modifies crossover and mutation strategy of Simple Genetic Algorithm (SGA). We use this algorithm to construct degree-constrained minimum spanning tree(d-MST) of a graph. Our experimental results provide strong evidence that the genetic algorithm employing parents' similarity information to decide crossover or mutation finds significantly lower-cost solutions to random graph d-MST problems than rival method.