生成树编码遗传算法种群退化分析及抑制方法

Population degeneracy analysis and suppressing algorithm for GA based on spanning tree code

种群退化现象导致了遗传算法对解空间区域进行重复搜索,从而降低了算法的搜索效率和延缓了算法的收敛,这源于重组算子、采样误差和变异算子的反作用力。通过对生成树编码遗传算法的研究,分析了重组算子的种群退化现象。证明了在解决固定费用运输问题时,重组算子发生种群退化现象的一个充分条件及其概率。针对种群退化现象提出了基于概率选择模型抑制算法(Probabilistic Selection Model Crossover,PSDC),对其有效性进行了分析证明。与小生境技术相比,它具有可以通过控制选择概率来抑制种群退化和不需要额外的时间开销两大优势,这为遗传算法的设计和应用提供了理论研究依据。

Population degeneracy in genetic algorithms,which results in the recombination operator,sampling error and function of mutation operator,delays the convergence rate and debases the capacity of searching since it searches repeatedly the visited solution region.An analysis for the GA based on spanning tree code is presented.It is strictly proved that the crossover operator results in population degeneracy in fixed charge transportation problem.Moreover,a sufficient condition for population degeneracy together with its probability is also developed.To overcome population degeneracy,an effective Probabilistic Selection Model Crossover（PSDC） is provided.Compared with the famous niching method,the PSDC is advantageous in two main aspects.Firstly,it can suppress degeneracy by controlling the probability of parameter instead of checking the population;Secondly,it does not increase the time complexity,while the niching algorithms need extra polynomial time in each iteration,which provides theory basis for the design and application of the genetic algorithm.