其实Python智能优化算法已经提出来好几年了,包括粒子群算法PSO、遗传算法等等,曾经在上世纪包括本世纪初特别流行,这几年随着算力的提升和更高效算法的提出,其已经逐渐离开大众视野了。但是了解智能优化算法,并且使用Python实现部分算法仍旧对于我们思维能力的养成以及Python编程能力的培养不无裨益。

遗传算法

参考博客1:https://blog.csdn.net/ha_ha_ha233/article/details/91364937
参考博客2:https://blog.csdn.net/weixin_41503009/article/details/104782088

思维框架

image.png

算法实现

遗传算法代码如下:

  1. import numpy as np
  2. import math
  3. import matplotlib.pyplot as plt
  4. from matplotlib import cm
  5. from mpl_toolkits.mplot3d import Axes3D
  6. N_GENERATIONS = 50
  7. DNA_LEN=10
  8. POP_SIZE=100
  9. XBound=[-1,2]
  10. #f(x)为需要求解的函数
  11. def f(pop):
  12. flist=[]
  13. for one in pop:
  14. flist.append(one * np.sin(10*math.pi*one) + 2)
  15. return flist
  16. #prese(x)为把给定的数值矩阵压缩为指定范围的列表
  17. def press(fx,Xbound):
  18. coeff = np.array([2**i for i in range(len(fx[0]))])
  19. ans = np.dot(fx,coeff)/(2**(len(fx[0]))-1)
  20. mappx = [i * (Xbound[1]-Xbound[0])+ Xbound[0] for i in ans]
  21. return mappx
  22. #这是根据每个点的值得到每个点的适应度
  23. def get_fitness(fpred):
  24. return fpred-np.min(fpred)+1e-3
  25. #选择函数,得到新的种群矩阵
  26. def select(pop, fitness): # nature selection wrt pop's fitness
  27. temp=np.array(fitness)
  28. idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
  29. p=(temp)/(temp.sum()) )
  30. return pop[idx]
  31. pop=np.random.randint(low=0,high=2,size=(POP_SIZE,DNA_LEN))
  32. save_1 = f(press(pop,XBound))
  33. fitness=get_fitness(save_1)
  34. select=select(pop,save_1)
  35. print(select)

模拟退火算法

参考博客:https://blog.csdn.net/WFRainn/article/details/80303138?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161451812216780271524683%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161451812216780271524683&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-2-80303138.first_rank_v2_pc_rank_v29&utm_term=%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95Python

思维框架

算法实现

模拟退火算法代码如下:

  1. import numpy as np
  2. import random
  3. import math
  4. '''
  5. 下面几个初始化参数聪上往下分别为:求解范围的上、下界、温度降低的速率以及初始温度
  6. '''
  7. HIGH = 3
  8. LOW = -3
  9. ALF = 0.95
  10. Temper = 50
  11. #目标函数
  12. def f(x):
  13. return 11*np.sin(x) + 7 * np.cos(5*x)
  14. #概率函数p,这里只考虑下山的情况
  15. def p(x,x1):
  16. return math.exp(-abs(f(x)-f(x1))/Temper)
  17. #新解的随机产生
  18. def new(x):
  19. x1 = x + Temper*random.uniform(-1,1)
  20. if (x1 <= HIGH) & (x1 >= LOW):
  21. return x1
  22. elif x1 < LOW:
  23. rand = random.uniform(-1,1)
  24. return rand * LOW + (1 - rand) * x
  25. else:
  26. rand = random.uniform(-1,1)
  27. return rand * HIGH + (1 - rand) * x
  28. def main():
  29. global x,Temper
  30. x=random.uniform(LOW,HIGH)
  31. while Temper > 0.001:
  32. for i in range(500):
  33. x1 =new(x)
  34. if f(x1) <= f(x):
  35. x = x1
  36. elif random.random() <= p(x,x1):
  37. x = x1
  38. else:
  39. continue
  40. Temper = Temper*ALF
  41. print('最小值为:{}'.format(f(x)))
  42. if __name__=="__main__":
  43. main()

蚁群算法

参考博客1:https://blog.csdn.net/ACA_JSP/article/details/88362006?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161466651216780255259333%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161466651216780255259333&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-8-88362006.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95
参考博客2:https://blog.csdn.net/fanxin_i/article/details/80380733?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161461094416780266251736%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161461094416780266251736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-2-80380733.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95Python
参考博客3:https://blog.csdn.net/qq_38526623/article/details/105318909?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161461094416780266251736%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161461094416780266251736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-1-105318909.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95Python

普通蚁群算法

普通蚁群算法代码如下:

  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. import seaborn as sns
  4. sns.set()
  5. '''
  6. 下面是几个城市基本参数的设置
  7. 蚁群蚂蚁数量为10
  8. '''
  9. CHENGDU = [1,1]
  10. SHANGHAI = [5,2]
  11. XIAN = [2,3]
  12. WUHAN = [3,2]
  13. BEIJING = [4,3.5]
  14. SHENZHEN = [3.5,0]
  15. FUZHOU = [4.5,0.5]
  16. CITY_LEN = 7
  17. ANT_NUMBER = 35
  18. MOVE_TIMES = 20
  19. CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]
  20. #计算两个城市间的距离
  21. def distance(city1,city2):
  22. temp = [i-j for i,j in zip(city1,city2)]
  23. return (sum([x**2 for x in temp]))**(1/2)
  24. #计算周游一圈总的长度
  25. def total_distance(cityset):
  26. citycopy = cityset[:]
  27. citycopy.append(cityset[0])
  28. dist = 0
  29. for i in range(len(cityset)):
  30. dist += distance(citycopy[i],citycopy[i+1])
  31. return dist
  32. #根据城市列表生成距离矩阵
  33. def dist_matrix(cityset):
  34. dist_matrix = np.zeros((CITY_LEN,CITY_LEN))
  35. for i in range(CITY_LEN):
  36. for j in range(CITY_LEN):
  37. dist_matrix[i][j] = distance(cityset[i],cityset[j])
  38. return dist_matrix
  39. #生成初始信息素矩阵
  40. def phe_matrix():
  41. phe_matrix = np.diag([-5,-5,-5,-5,-5,-5,-5])
  42. phe_matrix += 5
  43. return phe_matrix
  44. #求解最后的预测路径
  45. def find_route(mat,cityset):
  46. list1 = []
  47. list1.append(0)
  48. count = 0
  49. while(True):
  50. data = mat[count]
  51. for item in list1:
  52. data[item] = 0
  53. count = max_index = np.argmax(data)
  54. list1.append(max_index)
  55. if(len(list1) == 7):
  56. break
  57. route = []
  58. for number in list1:
  59. route.append(cityset[number])
  60. return route
  61. #打印当前的路程情况
  62. def print_plot(cityset):
  63. x_list=[];y_list=[]
  64. for city in cityset:
  65. x_list.append(city[0])
  66. y_list.append(city[1])
  67. x_list.append(cityset[0][0])
  68. y_list.append(cityset[0][1])
  69. plt.plot(x_list,y_list)
  70. plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
  71. plt.scatter(x_list[0],y_list[0],color="red",marker="o")
  72. plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
  73. print('最短路径长度为:',total_distance(cityset))
  74. #蚂蚁类,有当前位置和移动禁忌表两个元素
  75. class ant:
  76. def __init__(self):
  77. self.position = np.random.randint(low=0,high=CITY_LEN)
  78. self.Tabu_list = []
  79. def update_Tabu(self):
  80. if len(self.Tabu_list) >= CITY_LEN - 1:
  81. self.Tabu_list = []
  82. else:
  83. self.Tabu_list.append(self.position)
  84. def info(self):
  85. print('当前此蚂蚁所在位置为:',self.position+1)
  86. if len(self.Tabu_list)==0:
  87. print('当前此蚂蚁移动禁忌表为:',self.Tabu_list)
  88. else:
  89. print('当前此蚂蚁移动禁忌表为:',[i+1 for i in self.Tabu_list])
  90. def move(self,new_position):
  91. self.update_Tabu()
  92. self.position = new_position
  93. #蚁群类,有蚁群蚂蚁数量和十个蚂蚁两个元素
  94. class ants:
  95. def __init__(self,ant_number):
  96. self.number = ant_number
  97. self.antss = []
  98. for i in range(ant_number):
  99. self.antss.append(ant())
  100. def info(self):
  101. for i in range(self.number):
  102. print('蚂蚁',i+1)
  103. self.antss[i].info()
  104. #路径类,有距离矩阵、信息素矩阵和比值矩阵三个元素
  105. #距离矩阵一旦生成不再改变,信息素矩阵会更新
  106. class route_matrix:
  107. def __init__(self,cityset):
  108. self.dist_matrix = dist_matrix(cityset)
  109. self.phe_matrix = phe_matrix()
  110. for i in range(CITY_LEN):
  111. self.dist_matrix[i][i] = 1
  112. self.index_matrix = self.phe_matrix/self.dist_matrix
  113. def update_index(self,pos1,pos2):
  114. self.index_matrix[pos1][pos2] += 3.0/self.dist_matrix[pos1][pos2]
  115. def info(self):
  116. #print('当前路径的距离矩阵为:')
  117. #print(self.dist_matrix)
  118. print('当前路径的信息素矩阵为:')
  119. print(self.phe_matrix)
  120. print('当前路径的比值矩阵为:')
  121. print(self.index_matrix)
  122. #蚁群类,包含了蚂蚁和路程矩阵两个元素
  123. class antcolony:
  124. def __init__(self,ants,route_matrix):
  125. self.ants = ants
  126. self.matrix = route_matrix
  127. def info(self):
  128. self.ants.info()
  129. self.matrix.info()
  130. def move_prob(self):
  131. prob_lists = []
  132. for ant in self.ants.antss:
  133. temps = self.matrix.index_matrix[ant.position][:]
  134. prob_list = []
  135. for temp in temps:
  136. prob_list.append(temp)
  137. for Tabu in ant.Tabu_list:
  138. prob_list[Tabu] = 0
  139. new_list = [x/sum(prob_list) for x in prob_list]
  140. prob_lists.append(new_list)
  141. return prob_lists
  142. def update_matrix(self,pos1,pos2):
  143. self.matrix.phe_matrix[pos1][pos2] += 3.0/self.matrix.dist_matrix[pos1][pos2]
  144. self.matrix.update_index(pos1,pos2)
  145. def wholemove(self):
  146. if len(self.ants.antss[0].Tabu_list) < 6:
  147. prob_lists = self.move_prob()
  148. for i in range(ANT_NUMBER):
  149. if len(self.ants.antss[i].Tabu_list) < 6:
  150. idx = np.random.choice(np.arange(CITY_LEN),p=prob_lists[i])
  151. #print(i,"的当前位置为:",self.ants.antss[i].position+1)
  152. #print(i,'选择的下一位置为:',idx+1)
  153. last_pos = self.ants.antss[i].position
  154. self.ants.antss[i].move(idx)
  155. self.update_matrix(last_pos,idx)
  156. else:
  157. last_pos = self.ants.antss[i].position
  158. origin = self.ants.antss[i].Tabu_list[0]
  159. self.ants.antss[i].move(origin)
  160. self.update_matrix(last_pos,origin)
  161. if __name__ == "__main__":
  162. np.random.shuffle(CHENGSHI)
  163. route = route_matrix(CHENGSHI)
  164. ants = ants(ANT_NUMBER)
  165. antcolony = antcolony(ants,route)
  166. for count in range(MOVE_TIMES):
  167. antcolony.wholemove()
  168. matrix = antcolony.matrix.index_matrix
  169. answer = find_route(matrix,CHENGSHI)
  170. antcolony.info()
  171. print_plot(answer)

最优-最差蚂蚁-蚁群算法

最优-最差蚂蚁策略的蚁群算法代码如下:

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
'''
下面是几个城市基本参数的设置
蚁群蚂蚁数量为10
'''
CHENGDU = [1,1]
SHANGHAI = [5,2]
XIAN = [2,3]
WUHAN = [3,2]
BEIJING = [4,3.5]
SHENZHEN = [3.5,0]
FUZHOU = [4.5,0.5]
CITY_LEN = 7
ANT_NUMBER = 35
MOVE_TIMES = 20
CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]

#计算两个城市间的距离
def distance(city1,city2):
    temp = [i-j for i,j in zip(city1,city2)]
    return (sum([x**2 for x in temp]))**(1/2)

#计算周游一圈总的长度
def total_distance(cityset):
    citycopy = cityset[:]
    citycopy.append(cityset[0])
    dist = 0
    for i in range(len(cityset)):
        dist += distance(citycopy[i],citycopy[i+1])
    return dist

#根据城市列表生成距离矩阵
def dist_matrix(cityset):
    dist_matrix = np.zeros((CITY_LEN,CITY_LEN))
    for i in range(CITY_LEN):
        for j in range(CITY_LEN):
            dist_matrix[i][j] = distance(cityset[i],cityset[j])
    return dist_matrix

#根据数字列表生成的路径
def pro_route(index_list,cityset=CHENGSHI):
    alter = []
    for index in index_list:
        alter.append(cityset[index])
    return alter

#生成初始信息素矩阵
def phe_matrix():
    phe_matrix = np.diag([-5,-5,-5,-5,-5,-5,-5])
    phe_matrix += 5
    return phe_matrix

#将路程表分解为所有相邻两个元素组成的列表
def decompose(index_list):
    indexcopy = index_list[:]
    indexcopy.append(index_list[0])
    decom = []
    for i in range(len(index_list)):
        part = indexcopy[i:i+2]
        decom.append(part)
    return decom

#求解最后的预测路径
def find_route(mat,cityset):
    list1 = []
    list1.append(0)
    count = 0
    while(True):
        data = mat[count]
        for item in list1:
            data[item] = 0
        count = max_index = np.argmax(data)
        list1.append(max_index)
        if(len(list1) == 7):
            break
    route = []
    for number in list1:
        route.append(cityset[number])
    return route

#打印当前的路程情况
def print_plot(cityset):
    x_list=[];y_list=[]
    for city in cityset:
        x_list.append(city[0])
        y_list.append(city[1])
    x_list.append(cityset[0][0])
    y_list.append(cityset[0][1])
    plt.plot(x_list,y_list)
    plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
    plt.scatter(x_list[0],y_list[0],color="red",marker="o")
    plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
    print('最短路径长度为:',total_distance(cityset))

#蚂蚁类,有当前位置和移动禁忌表两个元素
class ant:
    def __init__(self):
        self.position = np.random.randint(low=0,high=CITY_LEN)
        self.Tabu_list = []

    def update_Tabu(self):
        if len(self.Tabu_list) >= CITY_LEN - 1:
            self.Tabu_list = []
        else:
            self.Tabu_list.append(self.position)

    def info(self):
        print('当前此蚂蚁所在位置为:',self.position+1)
        if len(self.Tabu_list)==0:
             print('当前此蚂蚁移动禁忌表为:',self.Tabu_list)
        else:
           print('当前此蚂蚁移动禁忌表为:',[i+1 for i in self.Tabu_list]) 

    def move(self,new_position):
        self.update_Tabu()
        self.position = new_position

#蚁群类,有蚁群蚂蚁数量和十个蚂蚁两个元素
class ants:
    def __init__(self,ant_number):
        self.number = ant_number
        self.antss = []
        for i in range(ant_number):
            self.antss.append(ant())

    def info(self):
        for i in range(self.number):
            print('蚂蚁',i+1)
            self.antss[i].info()

#路径类,有距离矩阵、信息素矩阵和比值矩阵三个元素
#距离矩阵一旦生成不再改变,信息素矩阵会更新
class route_matrix:
    def __init__(self,cityset):
        self.dist_matrix = dist_matrix(cityset)
        self.phe_matrix = phe_matrix()
        for i in range(CITY_LEN):
            self.dist_matrix[i][i] = 1
        self.index_matrix = self.phe_matrix/self.dist_matrix

    def update_index(self,pos1,pos2,num):
        if num == 2:
            up = 5.0
        elif num == 3:
            up = 1.0
        else:
            up = 3.0
        self.index_matrix[pos1][pos2] += up/self.dist_matrix[pos1][pos2]

    def info(self):
        #print('当前路径的距离矩阵为:')
        #print(self.dist_matrix)
        print('当前路径的信息素矩阵为:')
        print(self.phe_matrix)
        print('当前路径的比值矩阵为:')
        print(self.index_matrix)

#蚁群类,包含了蚂蚁和路程矩阵两个元素
class antcolony:
     def __init__(self,ants,route_matrix):
         self.ants = ants
         self.matrix = route_matrix
         self.best = []
         self.worst = []

     def info(self):
         self.ants.info()
         self.matrix.info()

     def move_prob(self):
         prob_lists = []
         for ant in self.ants.antss:
             temps = self.matrix.index_matrix[ant.position][:]
             prob_list = []
             for temp in temps:
                 prob_list.append(temp)
             for Tabu in ant.Tabu_list:
                 prob_list[Tabu] = 0
             new_list = [x/sum(prob_list) for x in prob_list]
             prob_lists.append(new_list)
         return prob_lists

     def update_matrix(self,pos1,pos2):
         if [pos1,pos2] in self.best or [pos2,pos1] in self.best:
             self.matrix.phe_matrix[pos1][pos2] += 5.0/self.matrix.dist_matrix[pos1][pos2]
             self.matrix.update_index(pos1,pos2,2)
         elif [pos1,pos2] in self.worst or [pos2,pos1] in self.worst:
             self.matrix.phe_matrix[pos1][pos2] += 1.0/self.matrix.dist_matrix[pos1][pos2]
             self.matrix.update_index(pos1,pos2,3)
         else:
            self.matrix.phe_matrix[pos1][pos2] += 3.0/self.matrix.dist_matrix[pos1][pos2]
            self.matrix.update_index(pos1,pos2,1)

     def wholemove(self):
         if len(self.ants.antss[0].Tabu_list) < 6:
             prob_lists = self.move_prob()
             turn_on = 0
         else:
             best_list = []
             turn_on = 1
         for i in range(ANT_NUMBER):
             if turn_on == 0:
                 idx = np.random.choice(np.arange(CITY_LEN),p=prob_lists[i])
                 #print(i,"的当前位置为:",self.ants.antss[i].position+1)
                 #print(i,'选择的下一位置为:',idx+1)
                 last_pos = self.ants.antss[i].position
                 self.ants.antss[i].move(idx)
                 self.update_matrix(last_pos,idx)
             else:
                 sums = sum(self.ants.antss[i].Tabu_list)
                 self.ants.antss[i].Tabu_list.append(21-sums)
                 best_list.append(self.ants.antss[i].Tabu_list)
                 last_pos = self.ants.antss[i].position
                 origin = self.ants.antss[i].Tabu_list[0]
                 self.ants.antss[i].move(origin)
                 self.update_matrix(last_pos,origin)
         if turn_on == 1:
             dist_list = [total_distance(pro_route(i)) for i in best_list]
             self.best = decompose(best_list[np.argmin(dist_list)])
             self.worst = decompose(best_list[np.argmax(dist_list)])
             print('当前最优为:',self.best)
             print('当前最不优为:',self.worst)


if __name__ == "__main__":
    np.random.shuffle(CHENGSHI)
    route = route_matrix(CHENGSHI)
    ants = ants(ANT_NUMBER)
    antcolony = antcolony(ants,route)
    for count in range(MOVE_TIMES):
        antcolony.wholemove()
    matrix = antcolony.matrix.index_matrix
    answer = find_route(matrix,CHENGSHI)
    antcolony.info()
    print_plot(answer)

禁忌搜索

参考博客1:https://blog.csdn.net/adkjb/article/details/81712969
参考博客2:https://blog.csdn.net/ChinaJane163/article/details/49095085
参考博客3:https://blog.csdn.net/tyhj_sf/article/details/54235550
参考博客4:https://blog.csdn.net/weixin_42528077/article/details/86762878

思维框架

算法实现

禁忌搜索算法实现:

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()

'''
下面是几个城市基本参数的设置,N_GENERATIONS是迭代的次数
禁忌长度为2,候选集合长度为6
'''
CHENGDU = [1,1]
SHANGHAI = [5,2]
XIAN = [2,3]
WUHAN = [3,2]
BEIJING = [4,3.5]
SHENZHEN = [3.5,0]
FUZHOU = [4.5,0.5]
CITY_LEN = 7
CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]
N_GENERATIONS = 15
Tabu_list = [10,10]

#计算两个城市间的距离
def distance(city1,city2):
    temp = [i-j for i,j in zip(city1,city2)]
    return (sum([x**2 for x in temp]))**(1/2)

#计算整个周游下来的总路程,即适应度函数
def total_distance(cityset):
    citycopy = cityset[:]
    citycopy.append(cityset[0])
    dist = 0
    for i in range(len(cityset)):
        dist += distance(citycopy[i],citycopy[i+1])
    return dist

#产生候选集合,长度为6
def alter_cityset(cityset):
    alterset=[]
    for i in range(CITY_LEN - 1):
        citys = cityset[:]
        if i != CITY_LEN - 2:
            citys[1+i],citys[2+i] = citys[2+i],citys[1+i]
        else:
            citys[1+i],citys[1] = citys[1],citys[1+i]
        alterset.append(citys)
    return alterset

#计算长度为6的候选集合中各个路径对应的总路程,即计算候选的适应度函数值
def set_to_distance(altercities):
    dist = []
    for altercity in altercities:
        dist.append(total_distance(altercity))
    return dist

#打印当前的路程情况
def print_plot(cityset):
    x_list=[];y_list=[]
    for city in cityset:
        x_list.append(city[0])
        y_list.append(city[1])
    x_list.append(cityset[0][0])
    y_list.append(cityset[0][1])
    plt.plot(x_list,y_list)
    plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
    plt.scatter(x_list[0],y_list[0],color="red",marker="o")
    plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
    print('最优适应度为:',total_distance(cityset))  

#完成禁忌表Tabu_list的变换
def swtich_tabu(number=0):
    Tabu_list.pop(0)
    Tabu_list.append(number)

#找到列表中第n小元素的索引
def find_min(list1=None,n=1):
    temp = list1[:];count = 0
    while count < n-1:
        temp[np.argmin(temp)]=np.max(temp)
        count += 1
    return np.argmin(temp)

#这就是循环主体部分,不断更新目前最优路径和最优适应度
def explore(chengshi,optimization,route_best):
    alter = alter_cityset(chengshi)
    dis = set_to_distance(alter)
    min_index = np.argmin(dis)
    route_be = []
    if dis[min_index] < optimization:
        opti = dis[min_index]
        route_be = city_now = alter[min_index]
        swtich_tabu(min_index)
    elif min_index not in Tabu_list:
        [opti,route_be] = [optimization,route_best]
        city_now = alter[min_index]
        swtich_tabu(min_index)    
    else:
        min2_index = find_min(dis,2)
        if min2_index not in Tabu_list:
            [opti,route_be] = [optimization,route_best]
            city_now = alter[min2_index]
            swtich_tabu(min2_index)
        else:
            min3_index = find_min(dis,3)
            [opti,route_be] = [optimization,route_best]
            city_now = alter[min3_index]
            swtich_tabu(min3_index)
    return [city_now,opti,route_be]

if __name__ == "__main__":
    route_now = CHENGSHI
    route_best = []
    np.random.shuffle(route_now)
    optimization = total_distance(CHENGSHI)
    print('初始适应度:',optimization)
    for count in range(N_GENERATIONS):
        [route_now,optimization,route_best] = explore(route_now,optimization,route_best)
        print('当前最优路径是:',route_now)
        print('当前最优适应度是:',optimization)
    [route_now,optimization,route_best] = explore(route_now,optimization,route_best)
    print_plot(route_best)