Python使用遗传算法解决最大流问题
作者:ZJun310 发布时间:2023-02-19 10:49:57
标签: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)
来源:http://blog.csdn.net/u014135091/article/details/48733295
0
投稿
猜你喜欢
- pandas获取groupby分组里最大值所在的行方法如下面这个DataFrame,按照Mt分组,取出Count最大的那行import pa
- 前面的文章,主要讲到如何使用无序列表ul元素来实现复杂柱状图,但是在Web标准中,除了注重表现外,更加注重语意,所谓的语意就是样式和内容的相
- 作为一个MySQL的系统管理员,你有责任维护你的MySQL数据库系统的数据安全性和完整性。本文主要主要介绍如何建立一个安全的MySQL系统,
- pytorch 输出中间层特征:tensorflow输出中间特征,2种方式:1. 保存全部模型(包括结构)时,需要之前先add_to_col
- 最近写了一个网络验证登录的爬虫,需要发布为Rest服务,然后发现Flask是一个很好的Web框架,使用Python语言实现。1. 安装fla
- 通过学习借鉴朋友的实现方法进行整理,实现了PHP版的微信公共平台消息主动推送,分享给大家供大家参考,具体内容如下此方法是通过模拟登录微信公共
- python中的Reportlab模块reportlab模块是用python语言生成pdf文件的模块安装:pip install repor
- 1.安装Apache 在终端中输入下面的命令就可以安装Apache了:sudo yum install httpdsudo的意思是
- 1.自定义用户表 注意事项必须在settings中配置AUTH_USER_MODEL这个字段 # 覆盖默认的用户模型,使用自定义
- 在ASP中,直接使用“Insert into” 语句与使用ADO中AddNew方法有什么区别?哪一种更好呢?AddNew方法的实质就是封装了
- caller 属性返回一个对函数的引用,该函数调用了当前函数。functionName.caller functionName 对象是所执行
- python 容器总结整理list可变数组tuple不可变数组dict键值对(key-value)的字典(dictionary)初始化:a=
- 一、概述OLAP的系统(即Online Aanalyse Process)一般用于系统决策使用。通常和数据仓库、数据分析、数据挖掘等概念联系
- 1. 模块(Module)在计算机程序的开发过程中,随着程序代码越写越多,在一个文件里代码就会越来越长,越来越不容易维护。为了编写可维护的代
- 众所周知,pip 可以安装、更新、卸载 Python 的第三方库,非常方便。你们中的许多人可能已经使用 pip 
- PyQt5切换按钮控件QPushButton简介QAbstractButton类为抽象类,不能实例化,必须由其他的按钮类继承QAbstrac
- 或许现在关心交互设计的设计师们大部分来自于了互联网行业,所以我们看到当你搜索“交互设计”时更多的BLOG和文章是在谈论互联网,网站的导航,注
- ASP中从数据库读取二进制文件数据代码:<%driver_name1="DRIVER={Microsoft&n
- 本文实例讲述了Symfony2之session与cookie用法。分享给大家供大家参考,具体如下:session操作:1. Set Sess
- 1. __init__ 初始化文件路径,关键字1,关键字2;2. key_match 使用with open 方法,以二进制方式(也可以改成