计算机技术与发展2017，Vol.27Issue(4)：69-72,4.DOI:10.3969/j.issn.1673-629X.2017.04.016
最大流最小截问题的遗传算法研究
Investigation on Genetic Algorithm for Maximum FlowMinimum Cut Problem
摘要
Abstract
Genetic algorithm has important applications in many fields,so the problems of maximum flow minimum cut also can be solved by it.Genetic algorithm solving the maximum flow minimum cut problem can be a solution for the exponential growth limitations of calculating amount for traditional algorithms with the increasing of the network size.Based on theory of maximum flow minimum cut problem and genetic algorithm principle,a genetic algorithm is designed for maximum flow minimum cut problem.According to the definition of maximum flow minimum cut,the encoding method,decoding method and a group initialization method of genetic algorithm are designed to form the initial individual of algorithm.The fitness function is designed to calculate individual fitness by which the selection operator is designed to select individual,and design of crossover and mutation operator,the selected individuals are carried out crossover and mutation to produce new individuals,introducing specific algorithm steps.Simulation results show that for small and large networks,this algorithm is stable,and with increasing number of iterations,it can obtain the optimal solution much closer to the true solution.关键词
最大流最小截/遗传算法/选择/交叉/变异Key words
maximum flow minimum cut/genetic algorithm/selection/crossing/mutation分类
信息技术与安全科学引用本文复制引用
赵礼峰,纪亚宝..最大流最小截问题的遗传算法研究[J].计算机技术与发展,2017,27(4):69-72,4.基金项目
国家自然科学基金青年基金项目(61304169) （61304169）
