赵礼峰,纪亚宝
(南京邮电大学 理学院,江苏 南京 210023)
最大流最小截问题的遗传算法研究
赵礼峰,纪亚宝
(南京邮电大学 理学院,江苏 南京 210023)
遗传算法在众多领域中均有重要应用,运用遗传算法同样可以求解最大流最小截问题。遗传算法解决最大流最小截问题可以有效地解决对于网络规模增长,传统算法计算量呈指数级增长的局限性。根据最大流最小截问题的相关理论和遗传算法的原理,设计出最大流最小截问题的遗传算法,根据最大流最小截问题的定义设计了遗传算法中的编码方法、解码方法以及群体初始化方法,形成算法的初始个体。设计适应度函数计算个体适应度,根据个体适应度设计算法的选择算子选择个体,设计了交叉算子和变异算子,将选择的个体进行交叉变异产生新的个体,并且设计了具体的算法步骤。通过仿真实验发现,对于小型网络和大型网络,该算法均能稳定求解,并且随着算法迭代次数的增加,算法求得最优解就越接近于真实解。
最大流最小截;遗传算法;选择;交叉;变异
最大流最小截问题是一个经典的组合优化问题。最大流最小截算法是对网络进行划分,从而求出网络中的瓶颈部位,其在交通、计算机、通信、电力网络中有着广泛的应用[1]。
寻找网络最小截问题,经典方法是采用Ford-Fulkerson[2-3]。随着网络规模的增大,算法的计算量呈指数级增长,而采用启发式算法可以有效解决该问题。启发式算法并不能保证给出最优解,但其优点在于算法的实现较简单,复杂度不高,可以有效解决最大流最小截问题。……