import pandas as pd
import numpy as np
import random, operator
import matplotlib.pyplot as plt
class City(object):
"""城市"""
def __init__(self, x, y):
self.x = x
self.y = y
def distance(self, city):
# 计算两个城市的距离,使用欧拉距离，也就是两个坐标的直线距离
dx = abs(self.x - city.x)
dy = abs(self.y - city.y)
return np.sqrt((dx ** 2) + (dy ** 2))
def __repr__(self):
return "({},{})".format(self.x, self.y)
def generate_city(n):
# 用于生成随机城市，返回两种形式的表达
city_list = [] # 一种是城市坐标列表
distances_array = [] # 一种是城市与城市间的距离矩阵
for i in range(n):
city_list.append(City(
x=int(random.random() * 200),
y=int(random.random() * 200)))
for i in range(n):
row = list()
for j in range(n):
row.append(np.linalg.norm(
city_list[i].distance(city_list[j])))
distances_array.append(row)
distances_array = np.array(distances_array)
return city_list, distances_array
class GeneticAlgorithm(object):
"""遗传算法解决旅行者问题"""
def __init__(self, city_list, population_size,
elite_size, mutation_rate, generations):
self.city_list = city_list # 城市列表
self.population_size = population_size # 种群大小
self.elite_size = elite_size # 精英模式数量
self.mutation_rate = mutation_rate # 变异的概率
self.generations = generations # 进化的总代数
self.progress = [] # 记录每一代的最优结果
def init_population(self):
# 创建一个种群
population = []
for i in range(self.population_size):
route = random.sample(self.city_list, len(self.city_list))
population.append(route)
return population
def fitness(self, route):
# 计算个体的适应能力值
path_distance = 0 # 路径的总距离
for i in range(0, len(route)):
from_city = route[i]
if i + 1 < len(route):
to_city = route[i + 1]
else:
to_city = route[0]
path_distance += from_city.distance(to_city)
distance = path_distance
# 距离越长，适应能力值越小，因此用路径长度的倒数作为适应能力值
return 1 / float(distance)
def rank_routes(self, population):
# 适应能力值排名
fitness_results = {}
for i in range(0, len(population)):
fitness_results[i] = self.fitness(population[i])
return sorted(fitness_results.items(), key=operator.itemgetter(1), reverse=True)
def selection(self, population, population_ranked):
# 根据适应能力值挑选个体进入杂交处理
mating_pool = [] # 记录被挑选的个体
df = pd.DataFrame(np.array(population_ranked), columns=["Index", "Fitness"])
# 通过这个方法，把适应能力值归一化后，变成一个按排名的分数
df['cum_sum'] = df.Fitness.cumsum()
df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()
for i in range(0, self.elite_size):
# 精英模式
mating_pool.append(population[population_ranked[i][0]])
for i in range(0, len(population_ranked) - self.elite_size):
# 剩下的按轮盘赌选择
pick = 100 * random.random() # 每次生成一个（0到1）随机数
for i in range(0, len(population_ranked)):
if pick <= df.iat[i, 3]: # 看落在那个区间，选择该个体
mating_pool.append(population[population_ranked[i][0]])
break
return mating_pool
def breed_population(self, mating_pool):
# 杂交处理
def breed(parent1, parent2):
# 父母杂交，创建新的一代
child_p1 = [] # 来自parent1的基因
child_p2 = [] # 来自parent2的基因
gene_A = int(random.random() * len(parent1))
gene_B = int(random.random() * len(parent1))
start_gene = min(gene_A, gene_B)
end_gene = max(gene_A, gene_B)
# 随机抽取parent1一段基因
for i in range(start_gene, end_gene):
child_p1.append(parent1[i])
for item in parent2:
# 剩下的都来自parent2
if item not in child_p1:
child_p2.append(item)
child = child_p1 + child_p2
return child
children = [] # 记录下一代个体
length = len(mating_pool) - self.elite_size
pool = random.sample(mating_pool, len(mating_pool)) # 打乱顺序
for i in range(0, self.elite_size):
# 精英模式，直接进入下一代
children.append(mating_pool[i])
for i in range(0, length):
child = breed(pool[i], pool[len(mating_pool) - i - 1])
children.append(child)
return children
def mutate_population(self, population):
# 基因突变处理
def mutate(individual):
for index_city1 in range(len(individual)):
if (random.random() < self.mutation_rate):
# 若个体（路径）发生变异，随机挑选两个城市交换位置
index_city2 = int(random.random() * len(individual))
city1 = individual[index_city1]
city2 = individual[index_city2]
individual[index_city1] = city2
individual[index_city2] = city1
return individual
mutated_population = []
for index_population in range(0, len(population)):
mutated_population.append(mutate(population[index_population]))
return mutated_population
def next_generation(self, current_generation):
# 生成下一代
population_ranked = self.rank_routes(current_generation) # 计算排名
mating_pool = self.selection(current_generation, population_ranked) # 挑选个体繁衍
children = self.breed_population(mating_pool) # 杂交处理
new_generation = self.mutate_population(children) # 基因突变处理
return new_generation # 最后返回新的一代种群
def run(self):
# 算法调用的入口
population = self.init_population()
self.progress.append(1 / self.rank_routes(population)[0][1])
print("第一代最短路径: " + str(self.progress[0]))
for i in range(0, self.generations):
population = self.next_generation(population)
self.progress.append(1 / self.rank_routes(population)[0][1])
print("最后一代最短路径: " + str(1 / self.rank_routes(population)[0][1]))
index_best_route = self.rank_routes(population)[0][0]
return population[index_best_route]
def draw_progress(self):
plt.plot(self.progress)
plt.ylabel('Distance')
plt.xlabel('Generation')
plt.show()
if __name__ == '__main__':
citys, arr = generate_city(3)
print(citys)
print(arr)
ga = GeneticAlgorithm(city_list=citys, population_size=50, elite_size=5, mutation_rate=0.01, generations=30)
result = ga.run()
ga.draw_progress()
