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

2017-05-02 05:43:25赵礼峰纪亚宝
计算机技术与发展 2017年4期
关键词:实验

赵礼峰,纪亚宝

(南京邮电大学 理学院,江苏 南京 210023)

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

赵礼峰,纪亚宝

(南京邮电大学 理学院,江苏 南京 210023)

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

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

0 引 言

最大流最小截问题是一个经典的组合优化问题。最大流最小截算法是对网络进行划分,从而求出网络中的瓶颈部位,其在交通、计算机、通信、电力网络中有着广泛的应用[1]。

寻找网络最小截问题,经典方法是采用Ford-Fulkerson[2-3]。随着网络规模的增大,算法的计算量呈指数级增长,而采用启发式算法可以有效解决该问题。启发式算法并不能保证给出最优解,但其优点在于算法的实现较简单,复杂度不高,可以有效解决最大流最小截问题。……

登录APP查看全文

猜你喜欢
实验
记住“三个字”,写好小实验
记一次有趣的实验
有趣的实验
小主人报(2022年4期)2022-08-09 08:52:06
做个怪怪长实验
NO与NO2相互转化实验的改进
实践十号上的19项实验
太空探索(2016年5期)2016-07-12 15:17:55
《实验流体力学》征稿简则
我实验,我快乐
学与玩(2004年7期)2004-04-29 00:00:00