使用蚁群算法加邻域搜索算法解决带有起点和终点的TSP问题(python)

经典的TSP问题,是通过随机初始化蚂蚁的起始地点,然后设置每个城市都可以访问,访问完所有的城市那么结束循环,来形成回路的。

带有起始点的TSP问题就是,初始化时蚂蚁的初始点只能是起点,并且如果没访问的城市还有两个或者以上那么就设置终点不可访问(当访问的城市只剩最后一个时候打开即可,我的程序中是设置open_table的布尔值)。

所以带有起点和终点的TSP问题相对于经典的TSP问题使用蚁群算法进行求解的时候只用改两行代码即可,非常的简单。

这个蚁群算法是使用op2优化(邻域搜索优化)的蚁群,基本上100个城市的规模使用30个蚂蚁一次循环在10s内就可以得到最优值/次优解,所谓邻域搜索+蚁群算法也很简单,就是在一只蚂蚁算出所有路径之后,对子路径进行翻转即可(不懂的用笔验算一下就明白了),翻转操作用程序实现非常简单。

作者:VanJordan
链接:https://www.jianshu.com/p/a8acd65aba79
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

import numpy as np
import matplotlib.pyplot as plt
import random
import copy
import time
import sys
import math
import datetime
from math import radians, cos, sin, asin, sqrt

class Ant(object):
    # 初始化
    def __init__(self,ID,distance_graph,pheromone_graph,ALPHA,BETA):
        self.city_num=len(distance_graph)
        self.distance_graph=distance_graph #距离矩阵
        self.pheromone_graph=pheromone_graph #信息素矩阵
        self.ID = ID  # ID
        (self.ALPHA, self.BETA) = (ALPHA , BETA)#蚂蚁在选择路径时  信息素与距离反比的比重
        self.path = []  # 当前蚂蚁的路径
        self.total_distance = 0.0  # 当前路径的总距离
        self.move_count = 0  # 移动次数
        self.current_city = -1  # 当前停留的城市
        self.open_table_city = [True for i in range(self.city_num)]  # 探索城市的状态
        if self.city_num >2:  #如果商店数目大于2那么就不能走city[1]
            self.open_table_city[1]=False
        #city_index = random.randint(0, self.city_num - 1)  # 随机初始出生点
        city_index=0 #初始点是开始点
        self.current_city = city_index
        self.path.append(city_index)  # 这只蚂蚁经过的路径
        self.open_table_city[city_index] = False  # 城市是否无访问
        self.move_count = 1

    # 选择下一个城市
    def _choice_next_city(self):

        next_city = -1
        select_citys_prob = [0.0 for i in range(self.city_num)]  #选择城市的可能性
        total_prob = 0.0

        # 获取去下一个城市的概率
        for i in range(self.city_num):
            if self.open_table_city[i]:
                try:
                    # 计算概率:与信息素浓度成正比,与距离成反比
                    select_citys_prob[i] = pow(self.pheromone_graph[self.current_city][i], self.ALPHA) * pow(
                        (1.0 / (self.distance_graph[self.current_city][i]+0.00001)), self.BETA)
                    total_prob += select_citys_prob[i]
                except ZeroDivisionError as e:
                    print('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID=self.ID,current=self.current_city,target=i))
                    sys.exit(1)

        # 轮盘选择城市
        if total_prob > 0.0:
            # 产生一个随机概率
            temp_prob = random.uniform(0.0, total_prob)
            for i in range(self.city_num):
                if self.open_table_city[i]:#如果城市没有被访问
                    # 轮次相减
                    temp_prob -= select_citys_prob[i]
                    if temp_prob < 0.0:
                        next_city = i
                        break

        # 未从概率产生,顺序选择一个未访问城市 如果temp_prob恰好选择了total_prob那么就在所有未去的城市中选择一个去的城市
        if next_city == -1:
            for i in range(self.city_num):
                if self.open_table_city[i]:
                    next_city = i
                    break

        # 返回下一个城市序号
        return next_city

    # 移动操作
    def _move(self, next_city):
        self.path.append(next_city)
        self.open_table_city[next_city] = False
        self.current_city = next_city
        self.move_count += 1

    #翻转操作
    def _reverse(self,start,end):#表示是protect函数
        #self.path[start:end+1]=self.path[end:start-1:-1]   #从bc  变成cb
        tmpPath=self.path.copy()
        tmpPath[start:end+1]=tmpPath[end:start-1:-1]
        return tmpPath

    def _cal_lenth(self,path):
        temp_distance = 0.0
        for i in range(1, len(path)):
            start, end = path[i], path[i - 1]
            temp_distance += self.distance_graph[start][end]
        return temp_distance

    def _need_reverse(self,start,end):
        tmpPath=self.path[start-1:end+2].copy()
        tmpPath[1:-1]=tmpPath[-2:0:-1]
        return self._cal_lenth(tmpPath) < self._cal_lenth(self.path[start-1:end+2])

    # 搜索路径
    def search_path(self):
        # 搜素路径,遍历完所有城市为止
        while self.move_count < self.city_num:
            # 移动到下一个城市
            next_city = self._choice_next_city()
            self._move(next_city)
            if self.move_count== self.city_num-1:#最后一个城市选择终点城市
                self.open_table_city[1]=True

        # 计算路径总长度
        self.total_distance=self._cal_lenth(self.path)

        i=2#步长
        while i < self.city_num-1:
            j=1#起始位置
            while j < self.city_num-i:
                if self._need_reverse(j,i+j-1):
                    self.path=self._reverse(j,i+j-1) #得到翻转之后的路径
                    self.total_distance =self._cal_lenth(self.path)  #更新总长度
                    i=2#重做整个结果
                    j=1
                j+=1
            i+=1



class tsp(object):

    def __init__(self,data_set):#data_set是所有点的经纬度坐标,label_list是这个分组的编号序列
        self.cities = data_set  # 商店的地址(经纬度信息)
        self.maxIter = 1 #蚁群算法的最大迭代次数
        self.rootNum = data_set.shape[0]#本分组的商店的数目
        (self.city_num, self.ant_num) = (self.rootNum, 30)
        (self.ALPHA, self.BETA, self.RHO, self.Q) = (1.0, 9.0, 0.5, 100.0)#蚁群算法参数
        self.distance_graph=[[0.0 for i in range(self.city_num)] for j in range(self.city_num)]
        self.pheromone_graph=[[1.0 for i in range(self.city_num)] for j in range(self.city_num)]
        self.get_Dis_Pherom()#初始化距离
        self.new()



    def transf_Dist(self,lon1, lat1, lon2, lat2):  # 经度1,纬度1,经度2,纬度2 (十进制度数)
        """
        Calculate the great circle distance between two points
        on the earth (specified in decimal degrees)
        """
        # 将十进制度数转化为弧度
        lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

        # haversine公式
        dlon = lon2 - lon1
        dlat = lat2 - lat1
        a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
        c = 2 * asin(sqrt(a))
        r = 6371  # 地球平均半径,单位为公里
        return c * r * 1000


    def get_Dis_Pherom(self):
        # 初始化城市距离
        for i in range(self.city_num):
            for j in range(self.city_num):
                self.distance_graph[i][j] =self.transf_Dist(self.cities[i,0],self.cities[i,1],self.cities[j,0],self.cities[j,1])

    def new(self,evt=None):
        # 初始化信息素
        self.ants = [Ant(ID,self.distance_graph,self.pheromone_graph,self.ALPHA, self.BETA) for ID in range(self.ant_num)]  # 初始蚁群
        self.best_ant = self.ants[-1]  # 初始最优解
        self.best_ant.total_distance = (1 << 31)  # 初始最大距离
        self.iter = 0  # 初始化迭代次数


    def search_path(self,evt=None):
        while self.iter<self.maxIter:
            # 遍历每一只蚂蚁
            for ant in self.ants:
                # 搜索一条路径
                ant.search_path()
                # 与当前最优蚂蚁比较
                if ant.total_distance < self.best_ant.total_distance:
                    # 更新最优解
                    self.best_ant = copy.deepcopy(ant)
            # 更新信息素
            self.update_pheromone_gragh()
            #print("迭代次数:", self.iter, u"最佳路径总距离:", int(self.best_ant.total_distance))
            #self.draw()
            self.iter += 1
        #self.draw()
        return self.best_ant.path


    def update_pheromone_gragh(self):
        # 获取每只蚂蚁在其路径上留下的信息素
        temp_pheromone = [[0.0 for col in range(self.city_num)] for raw in range(self.city_num)]
        for ant in self.ants:
            for i in range(1, self.city_num):
                start, end = ant.path[i - 1], ant.path[i]
                # 在路径上的每两个相邻城市间留下信息素,与路径总距离反比
                temp_pheromone[start][end] += self.Q / ant.total_distance
                temp_pheromone[end][start] = temp_pheromone[start][end]

        # 更新所有城市之间的信息素,旧信息素衰减加上新迭代信息素
        for i in range(self.city_num):
            for j in range(self.city_num):
                self.pheromone_graph[i][j] = self.pheromone_graph[i][j] * self.RHO + temp_pheromone[i][j]


def draw_line(cities,bestPath):
    city_num=cities.shape[0]
    ax = plt.subplot(111)
    ax.plot(cities[:, 0], cities[:, 1], 'x', color='blue')
    ax.plot(cities[0,0],cities[0,1],'ro')
    ax.plot(cities[1, 0], cities[1, 1], 'ro')
    for i in range(city_num):
        ax.text(cities[i, 0], cities[i, 1], str(i))
    ax.plot(cities[bestPath, 0], cities[bestPath, 1], color='red')
    plt.show()

def notInList(lon,lat,pointList):
    for i in range(0,len(pointList)):
        if abs(lon-pointList[i][0])<=0.000001 and abs(lat-pointList[i][1])<=0.000001:
            return i
    return len(pointList)

def get_route(startlon,startlat,endlon,endlat,pointdarry):
    pointList=pointdarry.tolist()
    listLen=len(pointList)
    sameIndex=notInList(startlon,startlat,pointList)
    if sameIndex < listLen:
        pointList.pop(sameIndex)
    sameIndex = notInList(endlon, endlat, pointList)
    if sameIndex < listLen:
        pointList.pop(sameIndex)
    coordinateList=[[startlon,startlat],[endlon, endlat]]
    coordinateList+=pointList
    dataSet=np.array(coordinateList)
    pathList = tsp(dataSet).search_path()
    draw_line(dataSet, pathList)
    resultList=[]
    for i in range(len(pathList)):
        if i>0 :
            if coordinateList[pathList[i]][0]==coordinateList[pathList[i-1]][0] and coordinateList[pathList[i]][1]==coordinateList[pathList[i-1]][1]:
                continue
            else :
                resultList.append(coordinateList[pathList[i]])
        else :
            resultList.append(coordinateList[pathList[i]])
    return resultList



if __name__ == '__main__':

    point_num = 66  # 点的数目
    random.seed(point_num)
    data_set = np.array(  # 生成point_num个随机的经纬坐标信息
        [[(random.random() * 100000 + 116300000) / 1000000, (random.random() * 100000 + 39900000) / 1000000] for i in
         range(point_num)])

    #其中第0个点是起点,第1个点是终点

    resultList=get_route(116.37494599868327, 39.905368158173204, 116.36079610914554, 39.93572462665125,data_set)

    print(resultList)
    print(len(resultList))



上一篇:基于Python的指数基金量化投资-股票数据源baostock


下一篇:8.10 不使用新变量交换a,b变量的一个不溢出的方法(非异或)