360SDN.COM

R语言与优化模型(三):图与网络优化

来源:louwill 数据科学家养成记  2017-07-28 13:33:47    评论:0点击:

用R语言做优化也不是一次两次了,继前面的R语言线性与非线性规划之后,小编今天要把R做规划的最后一部分:图与网络规划的R实现给学习了。

学过图论和运筹学的同学应该都知道,图与网络优化是现在数学建模竞赛的一个必备知识储备啊。图与网络优化问题,简单而言就是许多实际研究中的优化问题无法通过数学方程式进行处理而研究对象又恰好适合用一些图来表示,相应的问题便可转化为图的极值问题。

网络模型中通常的问题包括最短路问题、最大流问题、最小生成树问题以及著名的旅行商问题(TSP)。本文小编就给大家介绍R语言中求解前三个问题的igraph包以及专门求解TSP问题的TSP包。

 

igraph包与网络模型

igraph包是R语言专门用来求解经典图论与网络优化问题的一个包。常见的最小生成树、最短路、最大流等问题,在igraph包中一个函数即可得到最优解。关于igraph包的详细内容可参考帮助文档:

http://127.0.0.1:31454/library/igraph/html/00Index.html

igraph包中,求解网络最大流问题的函数用法为:

graph.maxflow(graph,source,target,capacity=NULL)

graph为要处理的图,source和target分别代表最大流的起点和终点,capacity为边的权重。

求解最小生成树的函数用法为:

minimum.spanning.tree(graph,weights=NULL,algorithm=NULL,..)

graph为要处理的图,weights为边权,algorithm为所选择的生成树算法。

求解最短路问题的函数用法:

shortest.paths(graph,v=V(graph),mode=c("all","out","in"),
                weights=NULL)

其中graph和weights意义同上,v为图的顶点,mode参数为all时,表示忽略图形的方向,即图为无向图,为out时表示考虑各个边的方向,为in时表示考虑各个边的倒置方向。

 

例子

求如下图形的最小生成树、最短路和最大流。

各边权重数据如下:

(1,2,5, 1,3,4, 1,4,3, 2,5,5, 2,6,3, 3,6,3, 3,7,2, 4,7,2, 5,2,5, 5,8,4, 6,8,3, 7,8,5)

用igraph包函数求解上述问题如下:

library(igraph)
e<-matrix(nc=3,byrow=TRUE,c(1,2,5, 1,3,4, 1,4,3, 2,5,5,
 2,6,3, 3,6,3, 3,7,2, 4,7,2, 5,2,5, 5,8,4, 6,8,3, 7,8,5))
#边权矩阵
g<-add_edges(graph.empty(8),t(e[,1:2]),weight=e[,3])
#构造图
tkplot(g)
#绘制图
graph.maxflow(g,1,8,capacity=E(g)$weight)
11     #求解最大流为11
mst<-minimum.spanning.tree(g)
tkplot(mst)
36     #计算绘制最小生成树
tree_min<-sum(E(mst)$weight)
tree_min
20
#计算最小生成树的权
shortest.paths(g,mode="out")
    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0    5    4    3   10    7    5   10
[2,]  Inf    0  Inf  Inf    5    3  Inf    6
[3,]  Inf  Inf    0  Inf  Inf    3    2    6
[4,]  Inf  Inf  Inf    0  Inf  Inf    2    7
[5,]  Inf    5  Inf  Inf    0    8  Inf    4
[6,]  Inf  Inf  Inf  Inf  Inf    0  Inf    3
[7,]  Inf  Inf  Inf  Inf  Inf  Inf    0    5
[8,]  Inf  Inf  Inf  Inf  Inf  Inf  Inf    0
#最短路矩阵

 

最小生成树图:

 

TSP问题的R实现

旅行商问题(TSP)作为世界上著名的NP难题之一,仍然吸引着大批学者的研究。解决该问题的算法也种类繁多,一些启发式、半启发式算法在该问题上广为应用。包括像遗传算法、模拟退火、蚁群算法、粒子群优化算法等解法也颇为常见。R语言中有专门处理TSP问题的包TSP,可直接调用其核心函数solve_TSP( )进行求解。其使用格式如下:

 

sovle_TSP(x,method,control)

x为处理TSP问题的数据格式,method为所采用的求解方法,这里内置了十多种启发式、半启发式算法可供选择。

2015年全国研究生数学建模竞赛F题要求参赛队伍对全国201个5A级景区制定一个旅游规划路线,这道题就是一个典型TSP问题。假设现要求一个从北京出发游遍全国34个省级行政中心的最少路线规划问题,下面我们看看用R中的TSP包如何对该问题求解。

#加载所需要的包
library(TSP)
library(maps)
library(maptools)
#读取34个省级中心的经纬度数据
pr<-read.csv("D:/Rdata/datasets/province.csv")
#计算两点之间的球面距离
f_dis<-function(x,y){
   r=6371
   x=x*pi/180;y=y*pi/180
   a=c(cos(x[2])*cos(x[1]),cos(x[2])*sin(x[1]),sin(x[2]))
   b=c(cos(y[2])*cos(y[1]),cos(y[2])*sin(y[1]),sin(y[2]))
   cosg=sum(a*b)/sqrt(sum(a^2)*sum(b^2))
   dis=r*acos(cosg)
}
k<-cbind(pr$longitude,pr$latitude)
#计算34个城市的两两距离
dis_mat<-matrix(NA,34,34)
for (i in 1:34){
   for(j in 1:34){
     dis_mat[i,j]=f_dis(k[i,],k[j,])
   }
}
colnames(dis_mat)<-rownames(dis_mat)<-pr[,1]
#tsp问题求解
tsp<-TSP(dis_mat)
tour<-solve_TSP(tsp,method="2-opt")
#数字路线
path<-as.integer(tour)
#总长度
tour_length(tsp,tour)
#在地图上标识
map("world","China",fill=T,col="lightgray")
map.axes()
tsp_map<-pr[path,]
attach(tsp_map)
points(c(longitude,longitude[1]),c(latitude,latitude[1]),
col=2,pch=20,type="o")
pointLabel(longitude,latitude,province,
col="blue",cex=0.74)
detach(tsp_map)

在多次运行上述代码后,我们可以从众多解中选取一个最优解为15638.01千米,最佳路线为北京-天津-济南-合肥-南京-上海-杭州-台北-福州-南昌-武汉-长沙-广州-香港-澳门-海口-南宁-昆明-贵州-重庆-拉萨-乌鲁木齐-西宁-兰州-银川-西安-郑州-石家庄-太原-呼和浩特-哈尔滨-长春-沈阳-北京。利用maps和maptool包可将路线展现在地图上:

 

到这里小编的R语言的优化专题就算结束了。我们在用Matlab和Lingo这样主流的求优化的软件工具进行求解的同时,也不妨使用R语言看看不一样的效果。

 

 

 

参考文献:

魏太云.R软件与最优化[C]//中国r语言会议.2008.

为您推荐

友情链接 |九搜汽车网 |手机ok生活信息网|ok生活信息网|ok微生活
 Powered by www.360SDN.COM   京ICP备11022651号-4 © 2012-2016 版权