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)
較大規(guī)模的情況
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)
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
Pandas是Python的第三方庫,提供高性能易用的數(shù)據(jù)類型和分析工具,下面這篇文章主要給大家介紹了關于pandas學習之txt與sql文件的基本操作指南,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了使用多線程改進flask案例，線程是指進程內的一個執(zhí)行單元,也是進程內的可調度實體.線程的劃分尺度小于進程，使得多線程程序的并發(fā)性高，更多具體內容，需要的小伙伴可以參考下面文章相關資料，希望對你有所幫助2022-03-03
這篇文章主要介紹了python圖像處理之反色實現(xiàn)方法,涉及Python結合OpenCV與numpy操作圖片的相關技巧,需要的朋友可以參考下2015-05-05
用python 實現(xiàn)在不確定行數(shù)情況下多行輸入方法
今天小編就為大家分享一篇用python 實現(xiàn)在不確定行數(shù)情況下多行輸入方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
本篇文章主要介紹了python中的json的基本使用方法，在Python中使用json的時候，主要也就是使用json模塊，json是以一種良好的格式來進行數(shù)據(jù)的交互，有興趣的可以了解一下。2016-12-12
這篇文章主要介紹了python之模擬鼠標鍵盤動作具體實現(xiàn)，有需要的朋友可以參考一下2013-12-12
Flask框架學習筆記之使用Flask實現(xiàn)表單開發(fā)詳解
這篇文章主要介紹了Flask框架學習筆記之使用Flask實現(xiàn)表單開發(fā),結合實例形式較為詳細的分析了flask框架表單模板定義、數(shù)據(jù)提交等相關操作技巧,需要的朋友可以參考下2019-08-08
這篇文章主要介紹了Python如何通過變量ID得到變量的值，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
這篇文章主要為大家詳細介紹了python webp圖片格式轉化的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
這篇文章主要介紹了如何在PyCharm中切換Python版本的步驟,包括查看現(xiàn)有版本、文件設置切換、選擇解釋器路徑以及應用更改,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2024-12-12