本文為大家分享了Python遺傳算法解決最大流問題，供大家參考，具體內(nèi)容如下

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 所對應(yīng)的下標(biāo)       index_1 = [t[0] for t in Line if t[1]==1] # 獲取 1 所對應(yīng)的下標(biāo)   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]]) # 將保留的一半方案 進(jìn)行復(fù)制 ，復(fù)制部分用于變異  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  # 將下移和右移映射到繪圖坐標(biāo)上 Road = [(1,x)] # 初始坐標(biāo) 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]: AOut[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)

較大規(guī)模的情況

In [105]: A = Generate_matrix(40,60)In [106]: road , M=Max_road(A,0.1,4)In [107]: roadOut[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)