首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

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

作者头像
用户2145057
发布2018-09-12 15:21:29
1.1K1
发布2018-09-12 15:21:29
举报

直接说基础语法,也许大家不会感兴趣。前言之后的这一章,给大家介绍一下我最近写出来的一个小功能。用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爬取铁路数据,这个工程比较浩大,敬请期待哦~

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

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.02.10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档