先看个问题：一个旅行商需要去拜访一系列城市，这些城市之间的距离都不相同，怎么才能访问每个城市一次并回到起始城市最短回路？
这一问题叫旅行商问题(TSP问题)，它是组合优化中的一个NP困难问题，当前有很多种解决算法，比如暴力搜索法、随机法或者模拟退火算法、遗传算法、蚁群算法等启发式算法。
今天来主要讲讲遗传算法是怎么解决此类问题的。
什么是遗传算法
遗传算法是一类受生物进化启发的一种随机搜索与优化的算法，它通过变异和交叉两种手段在当前已知的最好解来生成后续的解。
比如说蜜蜂采密，在亿万年的进化过程中，体内藏有一套高效的在不同花朵中寻找最短路劲的算法
遗传算法流程
遗传算法运行中会设置种群的规模、交叉率、变异率、保留胜出比例、进化迭代次数等参数，整体流程如下：
种群
种群是每代所产生的染色体总数，一个种群包含了该问题在这一代的一些解的集合
适应度评价
适应度评价是评估产生的解好坏的标准，如距离越短越好：f(s) = 1/dintance
选择
在种群中我们选择top N的优胜者进入下一轮迭代，一般使用按分数排序或者轮盘赌的方式来选择优胜者
交叉
交叉是将种群中两组优胜者的解分别拿出一部分，组合成为新的解
变异
变异是将种群中一组优胜者的解做一些随机变化，产生新的解
代码实现
# -*- encoding: utf8 -*-
import random
import math
import matplotlib.pyplot as plt
class GA:
def __init__(self, scale, num, max_gen, pc, elite):
# 种群规模
self.scale = scale
# 染色体数量(城市数量)
self.num = num
# 运行代数
self.max_gen = max_gen
# 交叉率
self.pc = pc
# 每代多少胜出者
self.elite = elite
def crossover(self, tour1, tour2, data):
# 交叉
c1 = random.randint(0, len(tour1['tour']) - 1)
c2 = random.randint(0, len(tour1['tour']) - 1)
while c1 == c2:
c2 = random.randint(0, len(tour1['tour']) - 1)
if c1 > c2:
c1, c2 = c2, c1
tour_part = tour1['tour'][c1:c2]
new_tour = []
index = 0
for i in range(len(tour2['tour'])):
if index == c1:
for item in tour_part:
new_tour.append(item)
if tour2['tour'][i] not in tour_part:
new_tour.append(tour2['tour'][i])
index += 1
return self.get_tour_detail(new_tour, data)
def mutate(self, tour, data):
# 变异
c1 = random.randint(0, len(tour['tour']) - 1)
c2 = random.randint(0, len(tour['tour']) - 1)
while c1 == c2:
c2 = random.randint(0, len(tour['tour']) - 1)
new_tour = []
for i in range(len(tour['tour'])):
if i == c1:
new_tour.append(tour['tour'][c2])
elif i == c2:
new_tour.append(tour['tour'][c1])
else:
new_tour.append(tour['tour'][i])
return self.get_tour_detail(new_tour, data)
def sort(self, tours):
# 排序
tours_sort = sorted(tours, key=lambda x: x['score'], reverse=True)
return tours_sort
def get_distance(self, c1, c2):
# 获取距离
xd = abs(c1['x'] - c2['x'])
yd = abs(c1['y'] - c2['y'])
distance = math.sqrt(xd * xd + yd * yd)
return distance
def get_score(self, distance):
# 适应性函数 距离越小适应值越大
return 1 / (distance + 1)
def get_tour(self, data):
# 随机获得一条路径
tour = []
for key, value in data.items():
tour.append(key)
random.shuffle(tour)
return self.get_tour_detail(tour, data)
def get_tour_detail(self, tour, data):
tmp = None
distance = 0
for item in tour:
if tmp is not None:
distance_tmp = self.get_distance(data[tmp], data[item])
distance += distance_tmp
tmp = item
return {'tour': tour, 'distance': distance, 'score': self.get_score(distance)}
def initialise(self, data):
# 初始种群
tours = []
for i in range(self.scale):
tours.append(self.get_tour(data))
return tours
def get_fittest(self, tours):
# 获取当前种群中最优个体
tmp = None
for item in tours:
if tmp is None or item['score'] > tmp['score']:
tmp = item
return tmp
def run(self, data):
pop = self.initialise(data)
old_fittest = self.get_fittest(pop)
topelite = int(self.scale * self.elite)
same_num = 0
max_same_num = 30
max_score = 0
for i in range(self.max_gen):
ranked = self.sort(pop)
pop = ranked[0:topelite]
fittest = self.get_fittest(pop)
if fittest['score'] > max_score:
same_num = 0
max_score = fittest['score']
else:
same_num += 1
# 最大分数保持n次一直没有变化则退出
if same_num > max_same_num:
break
while len(pop) < self.scale:
if random.random() < self.pc:
c1 = random.randint(0, topelite)
c2 = random.randint(0, topelite)
while c1 == c2:
c2 = random.randint(0, topelite)
tour = self.crossover(ranked[c1], ranked[c2], data)
else:
c = random.randint(0, topelite - 1)
tour = self.mutate(ranked[c], data)
pop.append(tour)
print 'total gen:', i
print 'before fittest:'
print old_fittest
print 'after fittest:'
new_fittest = self.get_fittest(pop)
print new_fittest
return new_fittest
def init_data(num):
data = {}
def get_random_point():
# 随机生成坐标
return {
'x': random.randint(1, 99),
'y': random.randint(1, 99)
}
for i in range(num):
data[i + 1] = get_random_point()
return data
def show(citys, tour):
# 绘图
plt.bar(left=0, height=100, width=100, color=(0, 0, 0, 0), edgecolor=(0, 0, 0, 0))
plt.title(u'tsp')
plt.xlabel('total distance: %s m' % tour['distance'])
x = []
y = []
i = 0
for item in tour['tour']:
city = citys[item]
x.append(city['x'])
y.append(city['y'])
i += 1
if i == 1:
plt.plot(city['x'], city['y'], 'or')
else:
plt.plot(city['x'], city['y'], 'bo')
plt.plot(x, y, 'g')
plt.xlim(0.0, 100)
plt.ylim(0.0, 100)
plt.show()
if __name__ == '__main__':
scale, num, max_gen, pc, elite = 50, 10, 1000, 0.8, 0.2
data = init_data(num)
ga = GA(scale, num, max_gen, pc, elite)
new_fittest = ga.run(data)
show(data, new_fittest)
运行效果：
遗传算法的优缺点
优点：
- 不盲目穷举, 是启发式搜索
- 与问题的领域无关,可快速切换
- 可并行计算一组种群
缺点：
- 计算量大, 不适合纬度高的问题
- 算法稳定性差
