利用人工智能的遗传算法，通过不断迭代实现tsp问题：

import math
import numpy as np
def init_route(n_route,n_cities):
    routes=np.zeros((n_route,n_cities)).astype(int)
    for i in range(n_route):
        routes[i]=np.random.choice(range(n_cities),size=n_cities,replace=False)
    #print(routes)
    return routes
def get_cities_distance(cities):
    City_dis=np.zeros((len(cities),len(cities)))
    for i in range(City_Num-1):
        for j in range(i+1,City_Num):
            dist=get_two_cities_dist(City_Map[i],City_Map[j])
            City_dis[i,j]=dist
            City_dis[j,i]=dist
    return City_dis
def get_two_cities_dist(city1,city2):
    xi,yi=city1[0],city1[1]
    xj,yj=city2[0],city2[1]
    return math.sqrt((xi - xj)**2 + (yi - yj)**2)

def get_route_fitness(route,City_dist):
    sum_dist=0
    for i in range(len(route)-1):
        sum_dist+=City_dist[route[i],route[i+1]]
    sum_dist+=City_dist[route[len(route)-1],route[0]]
    return 1/sum_dist

def get_all_routes_fitness(routes,City_dist):
    fitness=np.zeros(len(routes))
    for i in range(len(routes)):
        f=get_route_fitness(routes[i],City_dist)
        fitness[i]=f
    return fitness

def Select(routes,fitness):
    select_routes=np.zeros(routes.shape).astype(int)
    #print(fitness)
    prob=fitness/np.sum(fitness)
    #prob = np.insert(prob, 0, 0.00)
    sorted_indices = np.argsort(prob)
    sorted_prob = prob[sorted_indices]
    #print(sorted_prob)
    n_routes=routes.shape[0]
    sum=0.0          #累计概率
    for i in range(n_routes):         #轮盘赌选择
        random_number = np.random.uniform(0, 1)
        for j in range(len(prob)+1):
            if random_number>sum and random_number<=sum+sorted_prob[j]:
                select_routes[i]=routes[j]
                #print(routes[j+1])
                break
            sum+=sorted_prob[j]
        sum=0.0
    #print(select_routes)
    return select_routes
def mutation(routes,City_Num):
    prob=0.15
    p_rand=np.random.rand(len(routes))
    for i in range(len(routes)):
        if p_rand[i]<prob:
            mut_pos=np.random.choice(range(City_Num),size=2,replace=False)
            l,r=mut_pos[0],mut_pos[1]
            routes[i,l],routes[i,r]=routes[i,r],routes[i,l]
    return routes
def cross(routes,City_Num):
    prob=0.85
    p_rand=np.random.rand(len(routes))
    for i in range(0,len(routes),2):
        if p_rand[i]<prob:
            new_r1,new_r2=np.zeros(City_Num).astype(int),np.zeros(City_Num).astype(int)
            cross_pos=np.random.choice(range(City_Num),size=2,replace=False)
            min_pos=min(cross_pos[0],cross_pos[1])
            max_pos=max(cross_pos[0],cross_pos[1])
            new_r1[:min_pos]=routes[i][:min_pos]
            new_r1[min_pos:max_pos+1]=routes[i+1][min_pos:max_pos+1]
            new_r1[max_pos+1:]=routes[i][max_pos+1:]
            new_r2[:min_pos]=routes[i+1][:min_pos]
            new_r2[min_pos:max_pos+1]=routes[i][min_pos:max_pos+1]
            new_r2[max_pos+1:]=routes[i+1][max_pos+1:]
            dic1={routes[i][j]:routes[i+1][j] for j in range(min_pos,max_pos+1)}
            dic2={routes[i+1][j]:routes[i][j] for j in range(min_pos,max_pos+1)}
            for k in range(max_pos-min_pos+1):         #4 14 5 3 11 9 6 12 7 13 0 2 1 15 8 10         4 1 14 11 3 8 6 10 7 5 9 0 13 12 2 15
                for j in range(City_Num):
                    if j<min_pos or j>max_pos:
                        if new_r1[j] in dic2:
                            new_r1[j]=dic2[new_r1[j]]
                        if new_r2[j] in dic1:
                            new_r2[j]=dic1[new_r2[j]]
            routes[i]=new_r1
            routes[i+1]=new_r2
    return routes

if __name__ == '__main__':
    City_Num=16
    generation=100
    popsize=100
    pc=0.85
    pm=0.15
    epoch = 100000
    City_Map = [[106.54, 29.59]
    ,[91.11,29.97]
    ,[87.68,43.77]
    ,[106.27,38.47]
    ,[111.65,40.82]
    ,[108.33,22.84]
    ,[126.63,45.75]
    ,[125.35,43.88]
    ,[123.38,41.8]
    ,[114.48,38.03]
    ,[112.53,37.87]
    ,[101.74,36.56]
    ,[117,36.65]
    ,[113.6,34.76]
    ,[118.78,32.04]
    ,[117.27,31.86]]
    City_dist=get_cities_distance(City_Map)
    routes=init_route(generation,City_Num)
    fitness=get_all_routes_fitness(routes,City_dist)
    not_improve_time = 0
    best_index=fitness.argmax()
    best_route,best_fitness=routes[best_index],fitness[best_index]
    for i in range(epoch):
        routes=Select(routes,fitness)
        routes=cross(routes,City_Num)
        routes=mutation(routes,City_Num)
        fitness=get_all_routes_fitness(routes,City_dist)
        best_index=fitness.argmax()
        if fitness[best_index]>best_fitness:
            not_improve_time=0
            best_route, best_fitness = routes[best_index], fitness[best_index]
        else:
            not_improve_time+=1
        if (i + 1) % 200 == 0:
            print(
                'epoch: {}, 当前最优路线距离： {}'.format(i + 1, 1 / get_route_fitness(best_route, City_dist)))
        if not_improve_time>=2000:
            print('连续2000次迭代都没有改变最优路线，结束迭代')
            break
    print('最优路线为：')
    print(best_route)
    print('总距离为： {}'.format(1 / get_route_fitness(best_route, City_dist)))