【摘要】 最短路问题是组合优化中的经典问题之一,对其设计有效的算法具有广泛的应用价值和重要的理论意义．为了减少对初始种群选取的限制,扩大种群的多样性,本文提出了一种新的杂交方式．根据一对染色体中不同位相同基因对的数目,设计了分类杂交．这种杂交不仅增加了种群的多样性,还避免了不可行解的出现．与杂交算子相对应设计了具有局部搜索功能的收缩—扩张式变异算子,使得本算法效率有了极大提高,并在理论上证明该算法以概率1收敛到全局最优解．最后的数值试验也表明此算法是十分有效的．更多还原

【Abstract】 The shortest path routing problem(SP for short)is a class of combinatorial optimization problems.It is of great importance in both theory and applications. To decrease the limitation of choosing the initial population and increase the di- versity of the population,a new crossover operator called classification crossover operator is proposed.It can improve the diversity of the population and can al- ways generate feasible offspring.Furthermore,a novel mutation operator called contraction-extension mutation operator is designed.It has the function of local search and can largely enhance exploration ability of the algorithm.Based on these,an effective evolutionary algorithm for SP is proposed and its convergence to global optimal solution with probability one is proved.At last,the numerical experiments are made and the results indicate the proposed algorithm is efficient.更多还原