#!/usr/bin/env python
# coding: utf-8
# # 采用遗传算法解决10城市TSP问题
# 10城市坐标为：
# - 1： (41, 94)；
# - 2： (37, 84)；
# - 3： (54, 67)；
# - 4： (25, 62)；
# - 5： (7, 64)；
# - 6： (2, 99)；
# - 7： (68, 58)；
# - 8： (71, 44)；
# - 9： (54, 62)；
# - 10： (83, 69)
import numpy as np
import random
import matplotlib.pyplot as plt
# # 1. 获取临接矩阵
def CacDistance(a, b):
"""
计算两点之间的距离
"""
a = np.array(a)
b = np.array(b)
c = a-b
distance = np.sqrt(np.sum(c*c))
return distance
def CityDistance():
"""
获取临接矩阵
"""
locs = [(41, 94), (37, 84), (54, 67), (25, 62), (7, 64),
(2, 99), (68, 58), (71, 44), (54, 62), (83, 69)]
n = len(locs)
dis_mat = np.zeros([10, 10])
for i in range(n-1):
for j in range(i+1, n):
dist = CacDistance(locs[i], locs[j])
dis_mat[i, j] = dist
for i in range(n):
dis_mat[:, i] = dis_mat[i, :]
return dis_mat
# # 2. 遗传算法
# ## 2.1交叉
def Cross(p1, p2):
a = np.array(p1).copy()
b = np.array(p2).copy()
# 0~9之间随机生成两个整数,作为映射的起始点和结束点
begin = random.randint(0, 9)
end = random.randint(0, 9)
# 使 begin 小于 end
if begin > end:
temp = begin
begin = end
end = temp
# print begin,end
# 建立映射关系
cross_map = {}
is_exist = False
# 初步映射
for i in range(begin, end+1):
if a[i] not in cross_map.keys():
cross_map[a[i]] = []
if b[i] not in cross_map.keys():
cross_map[b[i]] = []
cross_map[a[i]].append(b[i])
cross_map[b[i]].append(a[i])
# 处理传递映射 如1:[6],6:[3,1]-->1:[6,3,1],6:[3,1]
# 计算子串中元素出现的个数，个数为2，则该元素为传递的中间结点，如如1:[6],6:[3,1],‘6’出现的次数为2
appear_times = {}
for i in range(begin, end+1):
if a[i] not in appear_times.keys():
appear_times[a[i]] = 0
if b[i] not in appear_times.keys():
appear_times[b[i]] = 0
appear_times[a[i]] += 1
appear_times[b[i]] += 1
if a[i] == b[i]:
appear_times[a[i]] -= 1
for k, v in appear_times.items():
if v == 2:
values = cross_map[k]
for key in values:
cross_map[key].extend(values)
cross_map[key].append(k)
cross_map[key].remove(key)
cross_map[key] = list(set(cross_map[key]))
# 使用映射关系交叉
# 先映射选中的子串
temp = a[begin:end+1].copy()
a[begin:end+1] = b[begin:end+1]
b[begin:end+1] = temp
# 根据映射规则映射剩下的子串
seg_a = a[begin:end+1]
seg_b = b[begin:end+1]
remain = list(range(begin))
remain.extend(range(end+1, len(a)))
for i in remain:
keys = cross_map.keys()
if a[i] in keys:
for fi in cross_map[a[i]]:
if fi not in seg_a:
a[i] = fi
break
if b[i] in keys:
for fi in cross_map[b[i]]:
if fi not in seg_b:
b[i] = fi
break
return a, b
# ## 2.2 变异
def Variation(s):
c = range(10)
index1, index2 = random.sample(c, 2)
temp = s[index1]
s[index1] = s[index2]
s[index2] = temp
return s
# ## 2.3 计算适应度
def cost(s):
dis = CityDistance()
n = len(s)
cost = 0
for i in range(n):
cost += dis[s[i], s[(i+1) % n]]
return -cost
# ## 2.4 构建遗传算法
# 获取列表的第三个元素
def TakeThird(elem):
"""
按适应度从大到小，排序时作为sort的key参数
"""
return elem[2]
def CacAdap(population):
"""
# adap n*4,n为行数，每行包括：个体下标,适应度,选择概率,累积概率
"""
# 计算每一个个体的适应度,选择概率
adap = []
psum = 0
# 计算适应度
i = 0
for p in population:
icost = np.exp(cost(p))
psum += icost
# 添加个体下标
adap.append([i])
# 添加适应度
adap[i].append(icost)
i += 1
# 计算选择概率
for p in adap:
# 添加选择概率和累积概率，这里累积概率暂时等于选择概率，后面会重新计算赋值
p.append(p[1]/psum)
p.append(p[2])
# 根据适应度从大到小排序
adap.sort(key=TakeThird, reverse=True)
# print adap
# 计算累计概率
n = len(adap)
for i in range(1, n):
p = adap[i][3] + adap[i-1][3]
adap[i][3] = p
return adap
def Chose(adap):
"""
轮盘选择操作
"""
chose = []
# 选择次数
epochs = 20 # max(len(adap)/2,20)
# while(len(set(chose)) <2):
# print 'chosing...length %d'%len(set(chose))
n = len(adap)
for a in range(epochs):
p = random.random()
if adap[0][3] >= p:
chose.append(adap[0][0])
else:
for i in range(1, n):
if adap[i][3] >= p and adap[i-1][3] < p:
chose.append(adap[i][0])
break
chose = list((chose))
return chose
def Cross_Variation(chose, population):
"""
交叉变异操作
"""
# 交叉率
p_c = 0.7
# 变异率
p_m = 0.3
# 交叉变异操作
chose_num = len(chose)
sample_times = chose_num//2
for i in range(sample_times):
index1, index2 = random.sample(chose, 2)
# print index1,index2
# 参与交叉的父结点
parent1 = population[index1]
parent2 = population[index2]
# 这两个父结点已经交叉，后面就不要参与了，就像这两个人以及结婚，按规矩不能在与其他人结婚了，故从采样样本中移除
chose.remove(index1)
chose.remove(index2)
p = random.random()
if p_c >= p:
child1, child2 = Cross(parent1, parent2)
# print child1,child2
p1 = random.random()
p2 = random.random()
if p_m > p1:
child1 = Variation(child1)
if p_m > p2:
child2 = Variation(child2)
population.append(list(child1))
population.append(list(child2))
return population
def GA(population):
"""
一次遗传过程
"""
adap = CacAdap(population)
# 选择操作
chose = Chose(adap)
# 交叉变异
population = Cross_Variation(chose, population)
return population
# ## 2.5 循环调用遗传算法，直到达到终止条件
def find_min(population):
loss = []
# 遗传次数
epochs = 51
i = 0
while i < epochs:
adap = []
# 计算适应度
for p in population:
icost = cost(p)
adap.append(icost)
# 使用遗传算法更新种群
population = GA(population)
min_cost = max(adap)
if i % 10 == 0:
print('epoch %d: loss=%.2f' % (i, -min_cost))
loss.append([i, -min_cost])
i += 1
if i == epochs:
# 输出最优解
p_len = len(population)
for index in range(p_len):
if adap[index] == min_cost:
print('最优路径:')
print(population[index])
print('代价大小:')
print(-min_cost)
break
# 打印损失函数变换
loss = np.arra
