使用蚁群算法求解TSP旅行商问题

# -*- coding: utf-8 -*-
 # author: 'boliang'
 # date: 2018/5/7 20:04
 
 import numpy as np
 import matplotlib.pyplot as plt
 
inf = float('inf')
rec_dis = inf
best_record = []
 
 class AntColonySystem(object):
     def __init__(self, d, ant_sum, alpha, beta, ro):
         self.__d = d
         self.__alpha = alpha
         self.__beta = beta
         self.__ro = ro
         self.__ant_sum = ant_sum
         self.__city_len = len(self.__d)
    '''
     description: 改变一条边的信息素(ACS的优化方法)
     '''
     def __change_local_phe(self, pheromone, i, j, phe_init):
         alsimon = 0.1
         pheromone[i][j] = (1-alsimon) * pheromone[i][j] + alsimon*phe_init
         pheromone[j][i] = pheromone[i][j]
 
    '''
     descritpion: 更新全局信息素, 以ACS为基准(效果较优)
     '''
     def __change_global_phe(self, pheromone, min_dis, best_record):
         for i in range(self.__city_len):
             for j in range(self.__city_len):
                 pheromone[i][j] = (1 - self.__ro) * pheromone[i][j]
                ind_a = best_record.index(i)
                ind_b = best_record.index(j)
                if abs(ind_a - ind_b) == 1 or abs(ind_a - ind_b) == self.__city_len - 1:
                     pheromone[i][j] += self.__ro * (1 / min_dis)
 
    '''
     description: 获得可选择的城市的概率与城市列表
     return: 
         next_ps 所有可选择城市的概率
         next_cities 所有可选择的城市
     '''
     def __get_probilities(self, records, ant, pheromone):
         cur_c = records[ant][-1]
        next_cities = [next_c for next_c in range(self.__city_len) if
                        next_c not in records[ant] and self.__d[cur_c][next_c] != inf]
        next_cs_alpha = list(map(
            lambda next_c: (pheromone[cur_c][next_c] ** self.__alpha) * ((1 / self.__d[cur_c][next_c]) ** self.__beta),
             next_cities))
        beta = sum(next_cs_alpha)
        return list(map(lambda alpha: alpha / beta, next_cs_alpha)), next_cities
 
    '''
     当前的蚂蚁选择下一个城市
     return next_c 返回选择好的城市号
     '''
     def __choose_next_city(self, records, record_dis, ant, pheromone, next_ps, next_cities):
         cur_c = records[ant][-1]
        select_id = 0
         if np.random.random() < 0.7:
             tmp = list(map(lambda next_c: pheromone[cur_c][next_c]*((1/self.__d[cur_c][next_c])**self.__beta), next_cities))
            select_id = tmp.index(max(tmp))
        else:
             num = 0
             select_num = np.random.random()
            for tmp in next_ps:
                 num += tmp
                if select_num <= num:
                     break
                 select_id += 1
 
         records[ant].append(next_cities[select_id])
        record_dis[ant] += self.__d[cur_c][next_cities[select_id]]
        return next_cities[select_id]
 
 
    '''
     description: 主方法，调用所有子方法进行问题迭代求解
     '''
     def solve(self, step):
         pheromone = [[1 for i in range(self.__city_len)] for j in range(self.__city_len)]
        best_record = []
        min_dis = inf
        records = [list() for i in range(self.__ant_sum)]
        record_dis = [0 for i in range(self.__ant_sum)]
        is_init = True
         pheromone_init = 0
 
         records_dis = []
 
        while step > 0:
             for ant in range(self.__ant_sum):
                 records[ant] = [np.random.randint(0, self.__city_len)]
                record_dis[ant] = 0
                 while len(records[ant]) < self.__city_len:
                     # 得到当前城市
                     cur_c = records[ant][-1]
                    # 获得下一个可以选择的所有城市选择概率与可选择的城市列表
                     next_ps, next_cities = self.__get_probilities(records, ant, pheromone)
                    # 选择下一个城市，返回选择好的城市号，便于局部更新信息素
                     next_c = self.__choose_next_city(records, record_dis, ant, pheromone, next_ps, next_cities)
                    if is_init == False:
                         # 局部更新信息素
                         self.__change_local_phe(pheromone, cur_c, next_c, pheromone_init)
 
                # 把头尾城市接上
                 record_dis[ant] += self.__d[records[ant][0]][records[ant][-1]]
                if is_init == False:
                     self.__change_local_phe(pheromone, records[ant][0], records[ant][-1], pheromone_init)
 
                # 更新最优路径
                 if min_dis == inf or min_dis > record_dis[ant]:
                     best_record = records[ant]
                    min_dis = record_dis[ant]
 
            # 是否初始化
             if is_init:
                 is_init = False
                 pheromone_init = 1/(self.__city_len*min_dis)
                pheromone = [[pheromone_init for i in range(self.__city_len)] for j in range(self.__city_len)]
                continue
 
             # 全局更新信息素
             self.__change_global_phe(pheromone, min_dis, best_record)
            step -= 1
             records_dis.append(min_dis)
        plt.plot([i for i in range(len(records_dis))], records_dis)
        plt.xlabel('times')
        plt.ylabel('distance')
        plt.show()
        print('计算出的序列为：', end='')
        print(best_record)
        print('最小值为：', end='')
        print(min_dis)
 
 if __name__ == '__main__':
     cities = [[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535], [3326, 1556], [3238, 1229],
         [4196, 1004], [4312, 790], [4386, 570], [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695],
         [3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931], [3429, 1908],
         [3507, 2367], [3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826], [2370, 2975]]
 
    d = []
    for i in range(len(cities)):
         d.append([])
        for j in range(len(cities)):
             if i == j:
                 d[-1].append(inf)
            else:
                 d[-1].append( np.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2) )
 
 
    ant_sum = 30
     alpha = 1
     beta = 2
     ro = 0.1
     sol = AntColonySystem(d, ant_sum, alpha, beta, ro)
    sol.solve(100)

迭代图

输出结果（走的城市序列和走过的路径长度）