改进的进化算法解最短路问题

摘要：

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

关键词：最短路、进化算法、全局优化

所属期刊栏目：28

分类号：O1(数学)

在线出版日期：2007-04-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：47-55