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

来源：计算机技术与发展杂志2017年第04期北京时间：

作者：赵礼峰;纪亚宝

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

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