最大流最小截问题的遗传算法研究

摘要：

遗传算法在众多领域中均有重要应用,运用遗传算法同样可以求解最大流最小截问题.遗传算法解决最大流最小截问题可以有效地解决对于网络规模增长,传统算法计算量呈指数级增长的局限性.根据最大流最小截问题的相关理论和遗传算法的原理,设计出最大流最小截问题的遗传算法,根据最大流最小截问题的定义设计了遗传算法中的编码方法、解码方法以及群体初始化方法,形成算法的初始个体.设计适应度函数计算个体适应度,根据个体适应度设计算法的选择算子选择个体,设计了交叉算子和变异算子,将选择的个体进行交叉变异产生新的个体,并且设计了具体的算法步骤.通过仿真实验发现,对于小型网络和大型网络,该算法均能稳定求解,并且随着算法迭代次数的增加,算法求得最优解就越接近于真实解.

关键词：最大流最小截、遗传算法、选择、交叉、变异

所属期刊栏目：27

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金青年基金项目61304169

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

页数：共4页

页码：69-72