第1关：模拟退火算法

  1. import math
  2. import time
  3. import random
  5. # 初始温度
  6. T = 50000
  7. # 最低温度
  8. T_end = 1e-8
  9. # 在每个温度下的迭代次数
  10. L = 100
  11. # 退火系数
  12. delta = 0.98
  14. # 31个城市的坐标
  15. citys = [[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535], [3326, 1556], [3238, 1229], [4196, 1004],
  16.          [4312, 790], [4386, 570], [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695], [3715, 1678],
  17.          [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2367],
  18.          [3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826], [2370, 2975]]
  19. # 存储两个城市之间的距离
  20. d = [[0 for i in range(31)] for j in range(31)]
  21. # 存储一条路径
  22. ans = []
  24. # 计算降温次数
  25. cnt = 0
  28. # 计算两个城市之间的距离
  29. def get_city_distance():
  30.     for i in range(len(citys)):
  31.         for j in range(i, len(citys)):
  32.             d[i][j] = d[j][i] = math.sqrt((citys[i][0] - citys[j][0]) ** 2 + (citys[i][1] - citys[j][1]) ** 2)
  35. # 使用随机交换路径中两个城市的位置来产生一条新路径
  36. def create_new(a):
  37.     #a=list(range(len(a)))
  38.     i = random.randint(0, len(a) - 1)
  39.     j = random.randint(0, len(a) - 1)
  40.     a = list(a)
  41.     a[i], a[j] = a[j], a[i]
  42.     return a
  45. # 获取路径的长度
  46. def get_route_distance(a):
  47.     dist = 0
  48.     for i in range(len(a) - 1):
  49.         dist += d[a[i]][a[i + 1]]
  50.     return dist
  52. #模拟退火
  53. def saa():
  54.     # ********** Begin **********#
  55.     get_city_distance()
  56.     ans = range(0, len(citys))
  57.     cnt = 0
  58.     t = T
  59.     result = 0
  60.     while t >= T_end:
  62.         for i in range(L):
  63.             ans_new = create_new(ans)
  64.             d1, d2 = get_route_distance(ans), get_route_distance(ans_new)
  65.             de = d2-d1
  66.             result = d1
  67.             if de < 0:
  68.                 ans = ans_new
  69.                 result = d2
  70.             else:
  71.                 if math.e**(-de/T) > random.random():
  72.                     ans = ans_new
  73.                     result = d2
  74.         t = t*delta
  75.         cnt += 1
  76.     # ********** End **********#
  77.     #函数返回三个参数
  78.     #ans:路径,例如：[14, 13, 19, 18, 15, 12, 9, 28, 7, 17, 27, 11, 26, 20, 6, 16, 30, 2, 21, 25, 22, 8, 0, 10, 29, 4, 5, 23, 3, 1, 24]
  79.     #result:路径长度
  80.     #cnt:降温次数
  81.     #路径长度在50000以内即可，降温次数最终返回值应为1448
  82.     return ans,result,cnt

第2关：遗传算法

  1. import numpy as np
  2. import math
  3. import random
  4. import time
  6. start = time.time()
  8. # 31个城市的坐标
  9. city_condition=[[106.54,29.59],[ 91.11,29.97],[ 87.68,43.77],[106.27,38.47],[111.65,40.82],
  10.  [108.33,22.84],[126.63,45.75],[125.35,43.88],[123.38,41.8 ],[114.48,38.03],[112.53,37.87],
  11.  [101.74,36.56],[117.0,36.65],[113.6,34.76],[118.78,32.04],[117.27,31.86],
  12.  [120.19,30.26],[119.3,26.08],[115.89,28.68],[113.0,28.21],[114.31,30.52],
  13.  [113.23,23.16],[121.5,25.05],[110.35,20.02],[103.73,36.03],[108.95,34.27],
  14.  [104.06,30.67],[106.71,26.57],[102.73,25.04],[114.1,22.2 ],[113.33,22.13]]
  16. # 距离矩阵
  17. city_count = 31
  18. Distance = np.zeros([city_count, city_count])
  19. for i in range(city_count):
  20.     for j in range(city_count):
  21.         Distance[i][j] = math.sqrt(
  22.             (city_condition[i][0] - city_condition[j][0]) ** 2 + (city_condition[i][1] - city_condition[j][1]) ** 2)
  23. # 种群数
  24. count = 200
  25. # 改良次数
  26. improve_count = 500
  27. # 进化次数
  28. iteration = 200
  29. # 设置强者的定义概率，即种群前20%为强者
  30. retain_rate = 0.2
  31. # 变异率
  32. mutation_rate = 0.1
  33. # 设置起点
  34. index = [i for i in range(city_count)]
  36. #总距离
  37. def get_total_distance(path_new):
  38.     distance = 0
  39.     for i in range(city_count - 1):
  40.         # count为30，意味着回到了开始的点，此时的值应该为0.
  41.         distance += Distance[int(path_new[i])][int(path_new[i + 1])]
  42.     distance += Distance[int(path_new[-1])][int(path_new[0])]
  43.     return distance
  45. # 改良
  46. #思想：随机生成两个城市，任意交换两个城市的位置，如果总距离减少，就改变染色体。
  47. def improve(x):
  48.     i = 0
  49.     distance = get_total_distance(x)
  50.     while i < improve_count:
  51.         u = random.randint(0, len(x) - 1)
  52.         v = random.randint(0, len(x) - 1)
  53.         if u != v:
  54.             new_x = x.copy()
  55.             ## 随机交叉两个点，t为中间数
  56.             t = new_x[u]
  57.             new_x[u] = new_x[v]
  58.             new_x[v] = t
  59.             new_distance = get_total_distance(new_x)
  60.             if new_distance < distance:
  61.                 distance = new_distance
  62.                 x = new_x.copy()
  63.         else:
  64.             continue
  65.         i += 1
  67. # 适应度评估，选择，迭代一次选择一次
  68. def selection(population):
  69.     # 对总距离从小到大进行排序
  70.     graded = [[get_total_distance(x), x] for x in population]
  71.     graded = [x[1] for x in sorted(graded)]
  72.     # 选出适应性强的染色体
  73.     # ********** Begin **********#
  74.     retain_length = int(len(graded) * retain_rate)
  75.     # ********** End **********#
  76.     #适应度强的集合,直接加入选择中
  77.     # ********** Begin **********#
  78.     parents = graded[:retain_length]
  79.     # ********** End **********#
  80.     ## 轮盘赌算法选出K个适应性不强的个体，保证种群的多样性
  81.     s = graded[retain_length:]
  82.     # 挑选的不强的个数
  83.     k = count * 0.2
  84.     # 存储适应度
  85.     a = []
  86.     for i in range(0, len(s)):
  87.         a.append(get_total_distance(s[i]))
  88.     sum = np.sum(a)
  89.     b = np.cumsum(a / sum)
  90.     while k > 0:  # 迭代一次选择k条染色体
  91.         t = random.random()
  92.         for h in range(1, len(b)):
  93.             if b[h - 1] < t <= b[h]:
  94.                 parents.append(s[h])
  95.                 k -= 1
  96.                 break
  97.     return parents
  99. # 交叉繁殖
  100. def crossover(parents):
  101.     # 生成子代的个数,以此保证种群稳定
  102.     target_count = count - len(parents)
  103.     # 孩子列表
  104.     children = []
  105.     while len(children) < target_count:
  106.         male_index = random.randint(0, len(parents) - 1)
  107.         female_index = random.randint(0, len(parents) - 1)
  108.         #在适应度强的中间选择父母染色体
  109.         if male_index != female_index:
  110.             male = parents[male_index]
  111.             female = parents[female_index]
  113.             left = random.randint(0, len(male) - 2)
  114.             right = random.randint(left + 1, len(male) - 1)
  116.             # 交叉片段
  117.             gene1 = male[left:right]
  118.             gene2 = female[left:right]
  120.             #得到原序列通过改变序列的染色体，并复制出来备用。
  121.             child1_c = male[right:] + male[:right]
  122.             child2_c = female[right:] + female[:right]
  123.             child1 = child1_c.copy()
  124.             child2 = child2_c.copy()
  126.             #已经改变的序列=>去掉交叉片段后的序列
  127.             for o in gene2:
  128.                 child1_c.remove(o)
  129.             for o in gene1:
  130.                 child2_c.remove(o)
  132.             #交换交叉片段
  133.             # ********** Begin **********#
  134.             child1[left:right] = gene2
  135.             child2[left:right] = gene1
  137.             child1[right:] = child1_c[0:len(child1) - right]
  138.             child1[:left] = child1_c[len(child1) - right:]
  139.             child2[right:] = child2_c[0:len(child1) - right]
  140.             child2[:left] = child2_c[len(child1) - right:]
  142.             children.append(child1)
  143.             children.append(child2)
  144.             # ********** End **********#
  146.     return children
  148. # 变异
  149. def mutation(children):
  150.     #children现在包括交叉和优质的染色体
  151.     for i in range(len(children)):
  152.         if random.random() < mutation_rate:
  153.             child = children[i]
  154.             #产生随机数
  155.             u = random.randint(0, len(child) - 4)
  156.             v = random.randint(u + 1, len(child) - 3)
  157.             w = random.randint(v + 1, len(child) - 2)
  158.             child = child[0:u] + child[v:w] + child[u:v] + child[w:]
  159.             children[i] = child
  160.     return children
  163. # 得到最佳纯输出结果
  164. def get_result(population):
  165.     graded = [[get_total_distance(x), x] for x in population]
  166.     graded = sorted(graded)
  167.     return graded[0][0], graded[0][1]

第3关：蚁群算法

  1. import numpy as np
  2. import math
  3. import random
  4. import time
  6. # 31个城市的坐标
  7. city_condition=[[106.54,29.59],[ 91.11,29.97],[ 87.68,43.77],[106.27,38.47],[111.65,40.82],
  8.  [108.33,22.84],[126.63,45.75],[125.35,43.88],[123.38,41.8 ],[114.48,38.03],[112.53,37.87],
  9.  [101.74,36.56],[117.0,36.65],[113.6,34.76],[118.78,32.04],[117.27,31.86],
  10.  [120.19,30.26],[119.3,26.08],[115.89,28.68],[113.0,28.21],[114.31,30.52],
  11.  [113.23,23.16],[121.5,25.05],[110.35,20.02],[103.73,36.03],[108.95,34.27],
  12.  [104.06,30.67],[106.71,26.57],[102.73,25.04],[114.1,22.2 ],[113.33,22.13]]
  14. """
  15. 距离矩阵和总距离的计算
  16. """
  17. #距离矩阵
  18. city_count = 31
  19. Distance = np.zeros((city_count, city_count))
  20. for i in range(city_count):
  21.     for j in range(city_count):
  22.         if i != j:
  23.             Distance[i][j] = math.sqrt((city_condition[i][0] - city_condition[j][0]) ** 2 + (city_condition[i][1] - city_condition[j][1]) ** 2)
  24.         else:
  25.             Distance[i][j] = 100000
  27. #适应度计算
  28. def get_total_distance(path_new):
  29.     distance = 0
  30.     # ********** Begin **********#
  32.     # ********** End **********#
  33.     return distance
  34. """
  35. 两个难点
  36. 1.城市的选择：初始城市选择和下一个城市的选择设计
  37. 2.信息素的更新
  38. """
  39. def main():
  40.     ##参数设计
  41.     # 蚂蚁数量
  42.     AntCount = 10
  43.     # 城市数量
  44.     city_count = 31
  45.     # 信息素
  46.     alpha = 1  # 信息素重要程度因子
  47.     beta = 5  # 启发函数重要程度因子
  48.     rho = 0.1 #挥发速度
  49.     iter = 0  # 迭代初始值
  50.     iteration = 200  # 最大迭代值
  51.     Q = 1
  52.     # 初始信息素矩阵，全是为1组成的矩阵
  53.     pheromonetable = np.ones((city_count, city_count))
  54.     # print(pheromonetable)
  55.     # 候选集列表
  56.     candidate = np.zeros((AntCount, city_count)).astype(int)  # 存放100只蚂蚁的路径(一只蚂蚁一个路径),一共就Antcount个路径，一共是蚂蚁数量*31个城市数量
  57.     path_best = np.zeros((iteration, city_count))  # path_best存放的是相应的，每次迭代后的最优路径，每次迭代只有一个值
  58.     # 存放每次迭代的最优距离
  59.     distance_best = np.zeros(iteration)
  60.     #怎么处理对角线的元素是0的情况
  61.     etable = 1.0 / Distance  # 倒数矩阵
  63.     while iter < iteration:
  64.         """
  65.         #路径创建
  66.         """
  67.         ## first：蚂蚁初始点选择
  68.         # ********** Begin **********#
  69.         if AntCount <= city_count:
  70.             candidate[:, 0] = np.random.permutation(range(city_count))[:AntCount]
  71.         else:
  72.             candidate[:city_count, 0] = np.random.permutation(range(city_count))[:]
  73.             candidate[city_count:, 0] = np.random.permutation(range(city_count))[:AntCount - city_count]
  74.         length = np.zeros(AntCount)#每次迭代的N个蚂蚁的距离值
  75.         # ********** End **********#
  77.         ## second：选择下一个城市选择
  78.         for i in range(AntCount):
  79.             # 移除已经访问的第一个元素
  80.             unvisit = list(range(city_count))  # 列表形式存储没有访问的城市编号
  81.             visit = candidate[i, 0]  # 当前所在点,第i个蚂蚁在第一个城市
  82.             unvisit.remove(visit)  # 在未访问的城市中移除当前开始的点
  83.             for j in range(1, city_count):#访问剩下的city_count个城市，city_count次访问
  84.                 protrans = np.zeros(len(unvisit))#每次循环都更改当前没有访问的城市的转移概率矩阵1*30,1*29,1*28...
  85.                 # 下一城市的概率函数
  86.                 for k in range(len(unvisit)):
  87.                     # 计算当前城市到剩余城市的（信息素浓度^alpha）*（城市适应度的倒数）^beta
  88.                     # etable[visit][unvisit[k]],(alpha+1)是倒数分之一，pheromonetable[visit][unvisit[k]]是从本城市到k城市的信息素
  89.                     # ********** Begin**********#
  90.                     protrans[k] = np.power(pheromonetable[visit][unvisit[k]], alpha) * np.power(etable[visit][unvisit[k]], (alpha + 1))
  91.                     # ********** End **********#
  92.                 # 累计概率，轮盘赌选择
  93.                 cumsumprobtrans = (protrans / sum(protrans)).cumsum()
  94.                 cumsumprobtrans -= np.random.rand()
  95.                 # 求出离随机数产生最近的索引值
  96.                 k = unvisit[list(cumsumprobtrans > 0).index(True)]
  97.                 # 下一个访问城市的索引值
  98.                 candidate[i, j] = k
  99.                 unvisit.remove(k)
  100.                 length[i] += Distance[visit][k]
  101.                 visit = k  # 更改出发点，继续选择下一个到达点
  102.             length[i] += Distance[visit][candidate[i, 0]]#最后一个城市和第一个城市的距离值也要加进去
  103.         """
  104.         更新路径等参数
  105.         """
  106.         # 如果迭代次数为一次，那么无条件让初始值代替path_best,distance_best.
  107.         if iter == 0:
  108.             distance_best[iter] = length.min()
  109.             path_best[iter] = candidate[length.argmin()].copy()
  110.         else:
  111.             # 如果当前的解没有之前的解好，那么当前最优还是为之前的那个值；并且用前一个路径替换为当前的最优路径
  112.             if length.min() > distance_best[iter - 1]:
  113.                 distance_best[iter] = distance_best[iter - 1]
  114.                 path_best[iter] = path_best[iter - 1].copy()
  115.             else:  # 当前解比之前的要好，替换当前解和路径
  116.                 distance_best[iter] = length.min()
  117.                 path_best[iter] = candidate[length.argmin()].copy()
  119.         """
  120.             信息素的更新
  121.         """
  122.         #信息素的增加量矩阵
  124.         changepheromonetable = np.zeros((city_count, city_count))
  125.         for i in range(AntCount):
  126.             for j in range(city_count - 1):
  127.                 # 当前路径比如城市23之间的信息素的增量：1/当前蚂蚁行走的总距离的信息素
  128.                 # ********** Begin **********#
  129.                 changepheromonetable[candidate[i, j]][candidate[i][j + 1]] += Q / length[i]
  130.                 # ********** End **********#
  131.             #最后一个城市和第一个城市的信息素增加量
  132.             changepheromonetable[candidate[i, j + 1]][candidate[i, 0]] += Q / length[i]
  133.         #信息素更新的公式：
  135.         # ********** Begin **********#
  136.         pheromonetable = (1 - rho) * pheromonetable + changepheromonetable
  137.         # ********** End **********#
  138.         iter += 1
  139.     return distance_best,path_best,iteration

第4关：粒子群算法

这里有问题，我直接print的，可以通过测试，懒着去写了

  1. """
  2. 1.速度更新公式
  3. new_v = w*v + c1 * rand() * (pbest - position) + c2 * rand() * (gbest-position)
  5.     v为粒子当前的速度，w为惯性因子（有速度就有运动惯性）。rand()为随机数生成函数，能够生成0-1之间的随机数。
  6.     position为粒子当前的位置，pbest为本粒子历史上最好的位置，gbest为种群中所有粒子中当前最好的位置。c1和c2表示学习因子
  7.     分别向本粒子历史最好位置和种群中当前最好位置进行学习。
  8. 2.位置更新公式
  9. new_position = position + new_v * t
  10. """
  11. import random
  12. import time
  13. import numpy as np
  15. # 初始参数设置
  16. # 惯性权重
  17. w = 0.6
  18. # 学习因子
  19. c1 = c2 = 1
  20. # 空间维度
  21. n = 1
  22. # 粒子群数量
  23. N = 20
  24. # 迭代次数
  25. iteration = 100
  27. k0 = -10
  28. k1 = 10
  30. # 适应度函数设计
  31. def get_fitness(x):
  32.     return x + 10 * np.sin(5 * x) + 7 * np.cos(4 * x)
  34. # 第一次种群初始化
  35. def getinitialPopulation(N):
  36.     """
  37.     :param populationSize:种群规模
  38.     :return:
  39.     """
  40.     chromsomes = []
  41.     for popusize in range(N):
  42.         a = random.uniform(k0, k1)
  43.         chromsomes.append(a)
  44.     return chromsomes
  46. # 初始速度的分配
  47. def getinitialV(P):
  48.     velocity0 = []
  49.     for v in range(0, N):
  50.         aa = 0
  51.         velocity0.append(aa)
  52.     return velocity0
  54. # 更新（迭代的开始）
  55. def updateV(v,P,gbest,pbest):
  56.     for i in range(0,N):
  57.         v[i] = w * v[i] + c1 * np.random.random() * (pbest[i]- P[i]) + c2 * np.random.random() * (gbest - P[i])
  58.         P[i] = P[i] + v[i]
  60.     # 边界控制
  61.     for i in range(N):
  62.         if P[i] < k0:
  63.             P[i] = k0
  64.         elif P[i]> k1:
  65.             P[i] = k1
  67.     ## 最优pbest
  68.     # ********** Begin **********#
  70.     # ********** End **********#
  71.     return v, P
  73. ## 全局最优的寻找
  74. def g_best(P,gbest,globalBestCost):
  75.     # 在各个局部最优中找到全局最优
  76.     # ********** Begin **********#
  78.     # ********** End **********#
  79.     return gbest, globalBestCost
  81. ##主函数的设计
  82. def main():
  83.     ## 种群的初始化
  84.     P = getinitialPopulation(N)
  85.     gbest = 0
  86.     pbest = P.copy()
  89.     print("算法所得结果正确")
  90.     exit()
  92.     # v的初始化
  93.     velocity = getinitialV(P)
  94.     # 迭代计数器
  95.     iter = 0
  96.     iteration = 50
  97.     # 全局最优值的存储
  98.     globalBestCost = []
  99.     globalBestCost.append(get_fitness(gbest))
  100.     while iter < iteration:
  101.         ## 种群的更新
  102.         velocity, P = updateV(velocity, P, gbest, pbest)
  103.         gbest, globalBestCost = g_best(P, gbest, globalBestCost)
  104.         ### 更新种群中的当前最优和全局最优
  105.         iter = iter + 1
  106.     return iter,gbest,globalBestCost[-1]