小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

直接说基础语法,也许大家不会感兴趣。前言之后的这一章,给大家介绍一下我最近写出来的一个小功能。用python语言实现GA算法来解决TSP问题,希望以此来激发大家学习python的兴趣。

何为GA,何为TSP问题,我将会在以后准备写的算法专题里详细解释,这里不再赘述,文章将主要讲述算法思路,以及实现效果,并内附重要代码。

程序思路

python3.6+pycharm+Anaconda3.6外加了一个basemap包是我的编程环境。

遗传算法流程图.jpg

首先我创建了一个GA.py,用来实现解决TSP问题的GA算法。算法流程如上图大致所述。有关TSP问题的解决算法有很多,近似算法,模拟退火,遗传算法等等,已经是造好了的轮子,可以拿来就用,也可以自己实现一边,还是蛮有意思的。最重要的是要领会算法思想,体会它解决问题的思路。

实现算法核心后,再来实现程序主体TSP.py,即用算法将读取的城市信息进行处理计算,并最后可视化呈现出来。

程序整体架构.jpg

如图所示,先从txt文件中读取34个城市的经纬度,然后根据地球弧度以及角度计算出34个城市两两之间距离。将这个数据传递给GA算法类,类内部有一个适配函数计算,通过距离数据,进行交叉,变异,产生下一代等一系列操作。最终产生一个最优秀的个体,也就是遍历了34个城市后使路程距离最短的那个序列。

其实所谓交叉,变异等等就是说,在这个算法中,我们把一个数组当作个体,这个数组代表什么含义呢?就是城市先后顺序。交叉就是让两个数组交换一部分序列产生新数组,变异就是一个数组部分序列改变,自己变成新数组。注意的是,第一代个体中,要特意保留下来本来路径就是最短的数组,直接放到下一代中,如此循环往复,以求寻找到最佳数组序列。

在这里我设置了一个全局数组,即迭代足够多的次数后,将最后得到的个体,或者说数组储存在里面,再在画图函数中使用它,以求将最优数组展现在由basemap勾勒出的地图上。

最短路径实现图.jpeg

代码实现

    def __init__(self, aLifeCount=100, ):
        self.initCitys()
        self.lifeCount = aLifeCount
        self.ga = GA(aCrossRate=0.7,
                     aMutationRage=0.02,
                     aLifeCount=self.lifeCount,
                     aGeneLenght=len(self.citys),
                     aMatchFun=self.matchFun())
        self.bestcityorder = []

这是初始化函数,其中self.bestcityorder即是我所说的全局数组,它起到一个在各个函数中间传递数据的中枢作用。此外,该初始化函数还初始化了GA算法的交叉概率,变异概率,以及适配函数等等。

这里面的self要特别提一下,它是一个关键字,它的意思是该类的一个实例化对象。相当于一个指针,才让全局数组起到畅通无阻的中枢作用。

    def distance(self, order):
        distance = 0.0
        for i in range(-1, len(self.citys) - 1):
            index1, index2 = order[i], order[i + 1]
            city1, city2 = self.citys[index1], self.citys[index2]
            distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
        return distance

这个是距离计算函数,没什么好说的。

    def run(self, n=0):
        while n > 0:
            self.ga.next()
            distance = self.distance(self.ga.best.gene)
            print(self.ga.best.gene)
            print(("%d : %f") % (self.ga.generation-1, distance))
            n -= 1

这是整个代码的核心关键,self.ga.next()即实现通过遗传变异以及接受上一代最优秀的个体组合形成下一代。n是迭代次数,我取的是100,即循环迭代一百次以寻求最优个体。最后将最有个体输出,并将该个体存储在全局数组中。

 def mappath(self):
        citylon1 = []
        citylat1 = []
        citylon2 = []
        citylat2 = []

        for i in self.bestcityorder:
            temp = i[0]
            i[0] = i[1]
            i[1] = temp
        # create new figure, axes instances.
        fig = plt.figure()
        ax = fig.add_axes([0, 0, 1, 1])

        # setup mercator map projection.
        m = Basemap(llcrnrlon=73.33, llcrnrlat=14.01, urcrnrlon=138.16, urcrnrlat=54.123, resolution='i',
                    projection='merc', lat_0=42.5, lon_0=120)
        # nylat, nylon are lat/lon of New York
        for i in self.bestcityorder:
            citylon1.append(i[0])
            citylat1.append(i[1])
        for i in range(len(self.bestcityorder)):
            if i == len(self.bestcityorder)-1:
                citylon2.append(self.bestcityorder[0][0])
                citylat2.append(self.bestcityorder[0][1])
            else:
                citylon2.append(self.bestcityorder[i + 1][0])
                citylat2.append(self.bestcityorder[i + 1][1])

        x, y = m(citylon1, citylat1)
        m.scatter(x, y, marker='D', color='m')


        # draw great circle route between NY and London
        for i in range(len(self.bestcityorder)):
            lon1 = citylon1[i]
            lat1 = citylat1[i]
            lon2 = citylon2[i]
            lat2 = citylat2[i]
            m.drawgreatcircle(lon1, lat1, lon2, lat2, linewidth=2, color='r')
        m.drawcoastlines()
        m.readshapefile('CHN_adm_shp/CHN_adm1', 'comarques', drawbounds=True)
        #m.fillcontinents()
        m.drawcountries()
        # draw parallels
        m.drawparallels(np.arange(10, 90, 20), labels=[1, 1, 0, 1])
        # draw meridians
        m.drawmeridians(np.arange(-180, 180, 30), labels=[1, 1, 0, 1])
        ax.set_title('Great Circle the shortest path')
        plt.show()

这个可以说是最长的一个函数了,其实它很简单,因为basemap画地图比较繁杂,所以代码也显得比较冗余。它实现了先在中国地图上用散点图函数标出34个城市,在利用传递过来的全局数组将里面的城市一个一个连起来。

大功告成,python是不是很简单?

可改进的地方

这个程序肯定不够实用,毕竟它计算的是直线距离。所以下一步我打算调用百度地图API爬取铁路数据,这个工程比较浩大,敬请期待哦~

大家也可以尝试一下,体验一把将代码融入生活的乐趣。

需要源码可以私信我,不要做伸手党,点个赞再来哦~

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]老王赛马

题目描述 赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到...

2749
来自专栏数据结构与算法

洛谷P1720 月落乌啼算钱

目背景 (本道题目木有以藏歌曲……不用猜了……) 《爱与愁的故事第一弹·heartache》最终章。 吃完pizza,月落乌啼知道超出自己的预算了。为了不在爱与...

3019
来自专栏null的专栏

优化算法——拟牛顿法之DFP算法

一、牛顿法    image.png image.png 二、DFP拟牛顿法 1、DFP拟牛顿法简介         DFP拟牛顿法也称为DFP校正方法,DFP...

3226
来自专栏窗户

斐波那契数列的算法分析

看过我其他一些文章的人,可能想象不出我会写一篇关于斐波那契数列的文章。因为可能会感觉1,1,2,3…这样一个数列能讲出什么高深的名堂?嗯,本篇文章的确是关于斐氏...

3442
来自专栏趣学算法

ACM竞赛学习指南(算法工程师成长计划)

5921
来自专栏大数据文摘

数学菜鸟的AI学习攻略 | 数学符号轻松入门

3104
来自专栏深度学习思考者

最短路径(一)——多源最短路径

引出问题:多源最短路径的问题 暑假,小文准备去一些城市旅游。为了节省经费以及方便计划旅程,小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。 我们...

21410
来自专栏C语言及其他语言

[每日一题]矩阵转置(1242)

题目描述 输入N*N的矩阵,输出它的转置矩阵。 输入 第一行为整数N。 接着是一个N*N的矩阵。 输出 转置矩阵 样例输入 2 1 2 1 2 样例输出 1 ...

3429
来自专栏一个会写诗的程序员的博客

函数式编程与面向对象编程[3]:Scala的OOP-FP混合式编程与抽象代数理论

Scala是纯种的面向对象的语言。从概念上讲,每一个值都是一个对象,每一个操作都是一个方法调用。语言支持通过类和特征的高级组件架构。

1182
来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

1246

扫码关注云+社区

领取腾讯云代金券