未加星标

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

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏
本文为大家分享了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)

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

较大规模的情况

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)

Python使用遗传算法解决最大流问题
In [109]: A = generate_Matrix(100,200)
In [110]: road , M=Max_road(A,0.1,10)
In [111]: draw_road(road,A)

Python使用遗传算法解决最大流问题
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。
您可能感兴趣的文章:python开发的小球完全弹性碰撞游戏代码python计算书页码的统计数字问题实例python益智游戏计算汉诺塔问题示例python机器人行走步数问题的解决浅谈Python实现贪心算法与活动安排问题Python3解决棋盘覆盖问题的方法示例Python基于回溯法解决01背包问题实例Python基于递归算法实现的走迷宫问题Python多线程经典问题之乘客做公交车算法实例Python基于动态规划算法解决01背包问题实例Python解决抛小球问题 求小球下落经历的距离之和示例

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

tags: road,solve,index,In,Python,range,Sum,random,Road,import,Max,np,init
分页:12
转载请注明
本文标题:Python使用遗传算法解决最大流问题
本站链接:http://www.codesec.net/view/572334.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(71)