-
题名最大流最小截问题的遗传算法研究
被引量:7
- 1
-
-
作者
赵礼峰
纪亚宝
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2017年第4期69-72,共4页
-
基金
国家自然科学基金青年基金项目(61304169)
-
文摘
遗传算法在众多领域中均有重要应用,运用遗传算法同样可以求解最大流最小截问题。遗传算法解决最大流最小截问题可以有效地解决对于网络规模增长,传统算法计算量呈指数级增长的局限性。根据最大流最小截问题的相关理论和遗传算法的原理,设计出最大流最小截问题的遗传算法,根据最大流最小截问题的定义设计了遗传算法中的编码方法、解码方法以及群体初始化方法,形成算法的初始个体。设计适应度函数计算个体适应度,根据个体适应度设计算法的选择算子选择个体,设计了交叉算子和变异算子,将选择的个体进行交叉变异产生新的个体,并且设计了具体的算法步骤。通过仿真实验发现,对于小型网络和大型网络,该算法均能稳定求解,并且随着算法迭代次数的增加,算法求得最优解就越接近于真实解。
-
关键词
最大流最小截
遗传算法
选择
交叉
变异
-
Keywords
maximum flow minimum cut
genetic algorithm
selection
crossing
mutation
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名最大流问题的改进最短增广链算法
被引量:3
- 2
-
-
作者
赵礼峰
纪亚宝
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2016年第8期52-54,59,共4页
-
基金
国家自然科学基金青年基金项目(61304169)
-
文摘
在最大流问题中,由于Ford-Fulkerson算法中增广链选取的任意性,导致该算法不是有效的多项式算法。经典的最短增广链算法是通过在增广过程中寻找最短增广链,从而排除增广链选取的任意性。但计算过程中为寻找最短增广链,需要根据原网络循环地构建剩余网络和剩余分层网络,步骤非常繁杂。为改善以上不足,基于经典最短增广链算法,提出改进最短增广链算法。该算法的思想是:若在增广剩余分层网络中流值的过程中得到饱和弧,则删除该弧对应于原网络中的弧,使原网络得以简化,以此可降低构建剩余网络和剩余分层网络的复杂性,从而优化最短增广链算法。理论和仿真实验都表明,改进算法不仅正确,而且比原算法效率更高。
-
关键词
最大流
最短增广链
剩余网络
剩余分层网络
-
Keywords
maximum flow
shortest augmenting chain
remaining network
remaining layered network
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-