专栏首页小红豆的数据分析小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

小蛇学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 条评论
登录 后参与评论

相关文章

  • 毕业设计:基于CNN的图像分类算法

    近年来人工智能越来越火,好像本科毕设不搞人工智能都很丢人似的。但是普通本科生对于这个领域的了解显然很少,基本也就是做做数据搜集、数据标注、工程实现、调调参的工作...

    用户2145057
  • 小蛇学python(12)分析《今生今世》人物关系图谱

    《今生今世》是渣男胡兰成所写的一部自传体小说。今天我们就来分析一下在他所写的自传中的人物关系图谱,分析一下胡兰成到底和多少女人有关系。

    用户2145057
  • 小蛇学python(20)魔法函数

    init负责类内成员的初始化,当类初始化实例的时候,会将传入的值赋给类内成员,与c++中的构造函数十分相似。

    用户2145057
  • python自学成才之路 类详细用法

    python是一门面向对象编程的语言,python的类和java中的类思想上有很多一样的地方,比如python类也是通过class修饰,里面也有成员属性,成员方...

    我是李超人
  • Python GUI项目实战(一)登录窗体的设计与实现

    前面我们学习了Python GUI 图型化界面Tkinter的基础知识,为了检测我们的学习成果,学以致用。我们从今天开始做一个综合Tkinter案例--基于Tk...

    小雨编程
  • ReactiveCocoa,最受欢迎的iOS函数响应式编程库(2.5版),没有之一!

    简介 项目主页: ReactiveCocoa 实例下载: https://github.com/ios122/ios122 简评: 最受欢迎,最有价值的iOS响...

    ios122
  • Loxodon.Framework.XLua

    Loxodon.Framework.XLua 是一个XLua的开源的MVVM框架,它做为Unity3D的MVVM框架Loxodon.Framework的插件来使...

    Loxodon Studio
  • PyQt5 字体/颜色/打印/打印预览对话框

    用户6021899
  • Django实现验证码

    Django实现验证码 背景知识 1. 验证码的作用 防恶意破解密码:防止,使用程序或机器人恶意去试密码.为了提高用户的体验,用户输入错误以后,才会要求输入验证...

    若与
  • python GUI库图形界面开发之PyQt5拖放控件实例详解

    在GUI中,拖放指的是点击一个对象,并将其拖动到另一个对象上的动作。比如百度云PC客户端支持的拖放文件以快速移动文件:

    砸漏

扫码关注云+社区

领取腾讯云代金券