用GA算法设计22个地点之间最短旅程-R语言实现

某毕业班共有30位同学,来自22个地区,我们希望在假期来一次说走就走的旅行,将所有同学的家乡走一遍。算起来,路费是一笔很大的花销,所以希望设计一个旅行方案,确保这一趟走下来的总路程最短。

旅行商问题是一个经典的NP问题

NP就是Non-deterministic Polynomial,即多项式复杂程度的非确定性问题,是世界七大数学难题之一。

如果使用枚举法求解,22个地点共有: (22-1)!/2 = 25545471085854720000 种路线方案

GA算法

遗传算法将“优胜劣汰,适者生存”的生物进化原理引入优化参数形成的编码串联群体中,按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。遗传算法的算法简单,可并行处理,并能到全局最优解。

GA算法设计

1.生成原始染色体种群

采用实数编码,以N个城市的序号作为一条可能的路径。 例如对8个城市,可生成如下的染色体代表一条路径,8,6,4,2,7,5,3,1.重复操作生成数目等于n的染色体种群。

2.生成适应度函数

由于是求最短路径,适应度函数一般求函数最大值,所以取路径总长度T的倒数,即fit ness=1/T。

3.选择染色体

采用轮盘赌的方式产生父代染色体。

4.对染色体种群进行编码

假设有一个含有九个城市的列表:W=(A,B,C,D,E,F,G,H,I)。 有如下两条路线: W1=(A,D,B,H,F,I,G,E,C) W2=(B,C,A,D,E,H,I,F,G) 则这两条路线可编码为: W1=(142869753) W2=(231458967)

5.交叉

以概率Pc选择参加交叉的个体(偶数个),用两点交叉算子进行操作。 例如对于下面两个染色体个体 (1 3 4 | 5 2 9 | 8 6 7) (1 7 6 | 9 5 2 | 4 3 8) 通过两点交叉可得到子代染色体为 (1 3 4 | 9 5 2 | 8 6 7) (1 7 6 | 5 2 9 | 4 3 8)

6.变异

以概率Pm选择参加变异的个体,用对换变异进行操作。随机的选择个体中的两个位点,进行交换基因。 如A=123456789;如果对换点为4和7,则经过对换后为B=123756489

7.解码

对染色体进行解码,恢复染色体的实数表示方法。

8.逐代进化

根据得出的新的染色体,再次返回选择染色体的步骤,进行迭代,直到达到迭代次数,算法停止。

算法实现

#加载packageslibrary(sp)
library(maptools)
library(geosphere)

source("C:\\Users\\ShangFR\\Desktop\\路径优化\\GA算法脚本.R")
data=read.csv("C:\\Users\\ShangFR\\Desktop\\路径优化\\143地理坐标.csv") #读取城市经纬度数据
border <- readShapePoly("C:\\Users\\ShangFR\\Desktop\\路径优化\\map\\bou2_4p.shp") #读取各省的边界数据等#初始化(列出地区距离矩阵-聚类)da=data[,1:2]
rownames(da)=data[,3]
hc=hclust(dist(da))
cutree(hc, h = 10)
plot(hc)

route=CreatDNA(data,5)  
x = route[,1]
y = route[,2]
z = route[,3]
cols=route[,4]

muer.lonlat = cbind(route[,1],route[,2]) # matrixmuer.dists = distm(muer.lonlat, fun=distVincentyEllipsoid) # 精确计算,椭圆ans=round(muer.dists/1000,2)
roundots = list(x=x,y=y,ans=ans,z=z,cols=cols)
species = GA4TSP(dots=roundots,initDNA=NULL,N=50,cp=0.1,vp=0.01,maxIter=1000,maxStay=100,maxElite=2,drawing=TRUE)

最优路径可视化

此图基于百度Echarts

R语言-GA算法脚本


原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2016-09-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

一文读懂遗传算法工作原理(附Python实现)

几天前,我着手解决一个实际问题——大型超市销售问题。在使用了几个简单模型做了一些特征工程之后,我在排行榜上名列第 219 名。

2964
来自专栏机器之心

资源 | 囊括欧亚非大陆多种语言的25个平行语料库数据集(拿走不谢!)

原文链接:https://gengo.ai/datasets/25-best-parallel-text-datasets-for-machine-transl...

1333
来自专栏机器之心

教程 | 遗传算法的基本概念和实现(附Java实现案例)

选自Medium 作者:MallawaarachchiFollow 机器之心编译 参与:俞云开、蒋思源 基因遗传算法是一种灵感源于达尔文自然进化理论的启发式搜索...

2968
来自专栏华章科技

大白话讲解遗传算法

种群(Population):生物的进化以群体的形式进行,这样的一个群体称为种群。

881
来自专栏量化投资与机器学习

【高能】用PyMC3进行贝叶斯统计分析(代码+实例)

问题类型1:参数估计 真实值是否等于X? 给出数据,对于参数,可能的值的概率分布是多少? 例子1:抛硬币问题 硬币扔了n次,正面朝上是h次。 参数问题 想知道...

6669
来自专栏大数据

有向无环图检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

3837
来自专栏携程技术中心

干货 | ElasticSearch相关性打分机制

作者简介 孙咸伟,后端开发一枚,在携程技术中心市场营销研发部负责“携程运动”项目的开发和维护。 携程运动是携程旗下新业务,主要给用户提供羽毛球、游泳等运动项目的...

1.3K8
来自专栏小樱的经验随笔

遗传算法详解(LINGO及MatlabGA工具箱求解实现)

遗传算法 1.前言 遗传算法是一种基于生物界自然群体遗传进化机制的自适应全局优化概率搜索算法。它与传统算法不同,不依赖梯度信息,而是通过模拟自然进化过程来搜索最...

1.3K6
来自专栏算法channel

Spark|有向无环图(DAG)检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

4808
来自专栏数据小魔方

动态地理信息可视化——leaflet在线地图简介

最近稍微涉猎了一下leaflet这个包,突然感到发现了动态可视化的新大门,这个包所提供的地图类型、动态效果、图层展示方式都大大扩展了ggplot作图系统的在数据...

3984

扫码关注云+社区