Python使用遗传算法解决最大流问题

 更新时间:2018年01月29日 16:10:18   作者:ZJun310   我要评论
这篇文章主要为大家详细介绍了Python使用遗传算法解决最大流问题,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下

Generate_matrix

def Generate_matrix(x,y):
 import numpy as np
 import random
 return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y))

Max_road

def Max_road(A,degree,start):
 import random
 import numpy as np
 import copy
 def change(M,number,start): # number 控制变异程度 start 控制变异量 
  x , y = M.shape
  for i in range(start,x):
   Line = zip(range(len(M[i])),M[i])
   index_0 = [t[0] for t in Line if t[1]==0] # 获取 0 所对应的下标    
   index_1 = [t[0] for t in Line if t[1]==1] # 获取 1 所对应的下标
   M[i][random.sample(index_0,number)[0]]=1 # 随机改变序列中 number 个值 0->1
   M[i][random.sample(index_1,number)[0]]=0 # 随机改变序列中 number 个值 1->0
  return M
 x,y = A.shape
 n=x
 generation = y
 #初始化一个有 n 中情况的解决方案矩阵
 init_solve = np.zeros([n,x+y-2]) 
 init=[1]*(x-1)+[0]*(y-1)
 for i in range(n) :
  random.shuffle(init)
  init_solve[i,:] = init # 1 表示向下走 0 表示向右走 
 solve = copy.copy(init_solve)
 for loop in range(generation):
  Sum = [A[0,0]]*n # 用于记录每一种方案的总流量
  for i in range(n):
   j=0;k=0;
   for m in solve[i,:]:
    if m==1:
     k=k+1
    else:
     j=j+1   
    Sum[i] = Sum[i] + A[k,j]
  Sum_index = zip(range(len(Sum)),Sum)
  sort_sum_index = sorted(Sum_index,key = lambda d : d[1] , reverse =True) # 将 方案 按照流量总和排序
  Max = sort_sum_index[0][1] # 最大流量
  #print Max
  solve_index_half = [a[0] for a in sort_sum_index[:n/2]] # 保留排序后方案的一半
  solve = np.concatenate([solve[solve_index_half],solve[solve_index_half]]) # 将保留的一半方案 进行复制 ,复制部分用于变异
  change(solve,int((x+y-2)*degree)+1 ,start) # 变异
 return solve[0] , Max

Draw_road

def Draw_road(road,A):
 import pylab as plt
 import seaborn
 seaborn.set()
 x , y =A.shape 
 # 将下移和右移映射到绘图坐标上
 Road = [(1,x)] # 初始坐标
 j=1;k=x;
 for m in road:
  if m==1:
   k=k-1
  else:
   j=j+1
  Road.append((j,k))
 # print Road
 for i in range(len(road)):  
  plt.plot([Road[i][0],Road[i+1][0]],[Road[i][1],Road[i+1][1]])

实际运行的例子

In [119]: A = Generate_matrix(4,6)
In [120]: A
Out[120]: 
array([[ 10., 1., 7., 10., 8., 8.],
  [ 4., 8., 8., 4., 8., 2.],
  [ 9., 8., 8., 3., 9., 8.],
  [ 7., 2., 5., 9., 3., 8.]])
In [121]: road , M=Max_road(A,0.1,2)
In [122]: Draw_road(road,A)

较大规模的情况

In [105]: A = Generate_matrix(40,60)
In [106]: road , M=Max_road(A,0.1,4)
In [107]: road
Out[107]: 
array([ 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0.,
  1., 0., 0., 0., 1., 0., 0., 1., 0., 1., 1., 1., 1.,
  1., 0., 0., 0., 0., 0., 1., 0., 0., 1., 0., 0., 0.,
  1., 0., 0., 0., 1., 0., 1., 0., 0., 1., 0., 0., 1.,
  0., 0., 0., 1., 0., 0., 1., 1., 1., 1., 0., 0., 0.,
  0., 0., 0., 1., 0., 1., 1., 1., 1., 0., 1., 0., 1.,
  1., 1., 0., 1., 0., 1., 0., 1., 0., 1., 0., 0., 1.,
  0., 1., 0., 0., 1., 0., 1.])
In [108]: Draw_road(road,A)

In [109]: A = generate_Matrix(100,200)
In [110]: road , M=Max_road(A,0.1,10)
In [111]: draw_road(road,A)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持澳门金沙网上娱乐。

相关文章

  • python将txt等文件中的数据读为numpy数组的方法

    python将txt等文件中的数据读为numpy数组的方法

    今天小编就为大家分享一篇python将txt等文件中的数据读为numpy数组的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-12-12
  • 浅谈Python中的闭包

    浅谈Python中的闭包

    简单说,闭包就是根据不同的配置信息得到不同的结果。再来看看专业的解释:闭包(Closure)是词法闭包(Lexical Closure)的简称,是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外。
    2015-07-07
  • Python数据结构之Array用法实例

    Python数据结构之Array用法实例

    这篇文章主要介绍了Python数据结构之Array用法实例,较为详细的讲述了Array的常见用法,具有很好的参考借鉴价值,需要的朋友可以参考下
    2014-10-10
  • Python 多维List创建的问题小结

    Python 多维List创建的问题小结

    这篇文章主要介绍了Python 多维List创建的问题小结,详细的介绍了遇到的一个小问题的解决方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2019-01-01
  • Python wxPython库Core组件BoxSizer用法示例

    Python wxPython库Core组件BoxSizer用法示例

    这篇文章主要介绍了Python wxPython库Core组件BoxSizer用法,结合实例形式分析了wxPython BoxSizer布局管理相关使用方法及操作注意事项,需要的朋友可以参考下
    2018-09-09
  • python multiprocessing模块用法及原理介绍

    python multiprocessing模块用法及原理介绍

    这篇文章主要介绍了python multiprocessing模块用法及原理介绍,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
    2019-08-08
  • python下解压缩zip文件并删除文件的实例

    python下解压缩zip文件并删除文件的实例

    下面小编就为大家分享一篇python下解压缩zip文件并删除文件的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-04-04
  • Python中比较特别的除法运算和幂运算介绍

    Python中比较特别的除法运算和幂运算介绍

    这篇文章主要介绍了Python中比较特别的除法运算和幂运算介绍,“/”这个是除法运算,那么这个“//”呢?“*”这个是乘法运算,那么这个“**”呢?本文就讲解这些运算的不同,需要的朋友可以参考下
    2015-04-04
  • python中异常报错处理方法汇总

    python中异常报错处理方法汇总

    之前在学习python的时候有整理过python异常处理的文章,不够简单也不够完整,所以决定再整理一篇,算做补充,大家学习一下,就可以自己思考解决方法了,希望对大家能够有所帮助
    2016-11-11
  • Python中print和return的作用及区别解析

    Python中print和return的作用及区别解析

    print的作用是输出数据到控制端,就是打印在你能看到的界面上。这篇文章给大家介绍Python中print和return的作用及区别解析,感兴趣的朋友跟随小编一起看看吧
    2019-05-05

最新评论