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

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

最大流问题的改进最短增广链算法

在最大流问题中,由于Ford-Fulkerson算法中增广链选取的任意性,导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链,从而排除增广链选取的任意性。但计算过程中为寻找最短增广链,需要根据原网络循环地构建剩余网络和剩余分层网络,步骤非常繁杂。为改善以上不足,基于经典最短增广链算法,提出改进最短增广链算法。该算法的思想是:若在增广剩余分层网络中流值的过程中得到饱和弧,则删除该弧对应于原网络中的弧,使原网络得以简化,以此可降低构建剩余网络和剩余分层网络的复杂性,从而优化最短增广链算法。理论和仿真实验都表明,改进算法不仅正确,而且比原算法效率更高。