遗传算法求解TSP问题

遗传算法求解TSP问题

问题描述

使用遗传算法求下图中从北京出发经过其他四个城市之后回到北京的最短路径，两个城市之间的距离如图所示：

遗传算法

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

参数编码

因为求解的是旅行商问题，我们可以直接对城市编号，省去了编码和解码的步骤。

如：北京-西安-上海-广州-昆明-北京的路径可以表示为0->1->2->4->3->0

初始群体的设定

我们需要生成一定数量的个体作为初始种群，以便后续生成子代进行迭代。

考虑到题目，我们这里首先设置初始种群个体数目：

# 初始种群个体
individual_num = 8

在个体类中，我们进行实例变量初始化时，对个体的基因进行随机生成：

class Individual:def __init__(self, genes=None):if genes == None:genes = [i for i in range(city_num)]# 不打乱第一个，因为出发地是固定的last = genes[1:]random.shuffle(last)del genes[1:]genes = genes + lastself.genes = genes# 计算路径距离self.distance = self.evaluate_distance()# 计算适应度self.fitness = self.evaluate_fitness()

这里需要注意的一点：因为题目规定我们的出发地为北京，所以我们所有个体的基因的首位应当为固定值，最终目的地为北京，所以基因的末位应该也为固定值。

由于出发地和目的地相同，所以我们这里省略了末位，但是在计算路径距离时需要增加一句：

    def evaluate_distance(self):distance = 0for i in range(gene_num-1):distance = distance + city_dist_mat[self.genes[i]][self.genes[i+1]]# 回到出发地distance = distance + city_dist_mat[self.genes[gene_num-1]][0]return distance

适应度函数的设计

适应度值的大小代表了种群中个体的优劣程度，种群中每次迭代都要进行适应度的比较。

因为题目中欲求最短路径，所以我们不妨用路径的距离来表示个体的优劣。距离越长，个体越差，距离越短，个体越好。

这里我们使用距离的倒数来表示适应度大小：适应度越小，个体越差，适应度越大，个体越好。

# 计算个体的适应度
def evaluate_fitness(self):value = 0for i in range(gene_num-1):value = value + city_dist_mat[self.genes[i]][self.genes[i+1]]# 记得要回到最初出发的城市value = value + city_dist_mat[self.genes[gene_num-1]][0]return 1/value

遗传操作设计

遗传操作设计涉及了交叉、变异和选择，下面依次介绍每个步骤使用的算法。

交叉

这里我们简要介绍一下顺序交叉法。

在两个父代染色体中随机选择起始和结束位置，将父代染色体1该区域内的基因复制到子代1相同位置上，再在父代染色体2上将子代1中缺少的基因按照顺序填入。另一个子代以类似方式得到。

例：起始位置为1，结束位置为5
父代1： 1 2 3 4 5 6 7 8
父代2： 5 2 1 7 3 8 6 4
子代1： 1 2 3 4 5 6 7 8
子代2： 4 2 1 7 3 8 5 6

实现代码如下：

# 种群交叉
def genes_cross(self, CROSS_RATE = 0.8):new_pop = []# 循环选择两个父代for i in range(0, len(self.individual_list)-1, 2):# 以一定概率进行交叉if np.random.rand() < CROSS_RATE:parent1 = self.individual_list[i].genesparent2 = self.individual_list[i+1].genes# 采用顺序交叉法begin = random.randint(1, city_num - 1)end = random.randint(1, city_num - 1)# 确保begin小于endif begin > end:tmp = beginbegin = endend = tmpindiviual1_gene = copy.deepcopy(parent2)indiviual2_gene = copy.deepcopy(parent1)# 将子代二里父代二被选中的部分删除for i in range(begin, end+1):indiviual2_gene.remove(parent2[i])# 放入相应位置元素 begin -> endfor i in range(begin, end+1):indiviual2_gene.insert(i, parent2[i])# 将子代一里父代一被选中的部分删除for i in range(begin, end+1):indiviual1_gene.remove(parent1[i])# 放入相应位置元素begin->endfor i in range(begin, end+1):indiviual1_gene.insert(i, parent1[i])# 产生两个子代new_pop.append(Individual(indiviual1_gene))new_pop.append(Individual(indiviual2_gene))return new_pop

变异

交叉生成子代后，对新生成的子代进行一定概率的变异，我们这里使用的方法为基于次序的变异。

基于次序的变异为：首先随机的产生两个变异位置，然后交换这两个变异位置上的基因即可，假设变异位位2和5，即：
变异前：1 2 3 4 5
变异后：1 5 3 4 2

这里需要注意，在这个题目中，因为出发地是固定的，所以我们进行变异时，位置的选择区间应该不包括首位（这里末位不用考虑，因为前面解释过，目的地和出发地一样，所以目的地未被写到基因序列中）。

# 种群变异
def genes_update(self, new_gene, UPTATE_RATE = 0.2):# 基于次序的变异# 依次遍历for gene in new_gene:# 以一定概率进行变异if np.random.rand() < UPTATE_RATE:# 随机选择两位进行交换，变异x = random.randint(1, gene_num - 1)y = random.randint(1, gene_num - 1)temp = gene.genes[x]gene.genes[x] = gene.genes[y]gene.genes[y] = temp

选择

在经过交叉和变异生成新子代后，我们需要从生成的子代中随机选择加入到种群中，这里我们使用的选择算法为轮盘赌选择算法（Roulette Wheel Selection）。

它模拟博彩游戏的轮盘赌。一个轮盘被划分为N个扇形表示种群的一个染色体，而每个扇形的面积与它所表示的染色体的适应值成正比，为了选择种群中的个体，设想有一个指针指向轮盘，转动轮盘，当轮盘停止后，指针所之乡的染色体被选择。因为一个染色体的适应值越大表示该染色体的扇形面积就越大，因此它被选择的可能性也就越大。

实现代码为：

def wheel_select(self, new_gene):new_ga = []sum_val = 0for gene in new_gene:sum_val = sum_val + gene.fitnessfor i in range(individual_num):random_val = random.random()*sum_valprobability = 0for gene in new_gene:probability += gene.fitnessif probability >= random_val:new_ga.append(gene)return new_ga

控制参数设定

遗传算法一共有4个参数需要提前设定，一般是以下范围内：
（1）群体大小：20~100
（2）遗传算法的终止进化代数：100~500
（3）交叉概率：0.4~0.99
（4）变异概率：0.0001~0.1

但是由于我们这个题目过于简单，所以在程序中，设置的参数分别为：

# 初始种群个体
individual_num = 5
# 迭代次数
circle_num = 10
# 交叉概率
CROSS_RATE = 0.8
# 变异概率
UPTATE_RATE = 0.2

完整代码

代码中一共定义了两个类：个体Individual、种群Ga。

import copy
import random
import numpy as np
city_num = 5
gene_num = 5
# 初始种群个体
individual_num = 5
# 迭代次数
circle_num = 10# 实验一矩阵
city_dist_mat = np.zeros([city_num, city_num])
city_dist_mat[0][1] = city_dist_mat[1][0] = 1165
city_dist_mat[0][2] = city_dist_mat[2][0] = 1462
city_dist_mat[0][3] = city_dist_mat[3][0] = 3179
city_dist_mat[0][4] = city_dist_mat[4][0] = 1967
city_dist_mat[1][2] = city_dist_mat[2][1] = 1511
city_dist_mat[1][3] = city_dist_mat[3][1] = 1942
city_dist_mat[1][4] = city_dist_mat[4][1] = 2129
city_dist_mat[2][3] = city_dist_mat[3][2] = 2677
city_dist_mat[2][4] = city_dist_mat[4][2] = 1181
city_dist_mat[3][4] = city_dist_mat[4][3] = 2216class Individual:def __init__(self, genes=None):if genes == None:genes = [i for i in range(city_num)]# 不打乱第一个，因为出发地是固定的last = genes[1:]random.shuffle(last)del genes[1:]genes = genes + lastself.genes = genesself.distance = self.evaluate_distance()self.fitness = self.evaluate_fitness()# 计算个体的适应度def evaluate_fitness(self):value = 0for i in range(gene_num-1):value = value + city_dist_mat[self.genes[i]][self.genes[i+1]]value = value + city_dist_mat[self.genes[gene_num-1]][0]return 1/valuedef evaluate_distance(self):distance = 0for i in range(gene_num-1):distance = distance + city_dist_mat[self.genes[i]][self.genes[i+1]]distance = distance + city_dist_mat[self.genes[gene_num-1]][0]return distanceclass Ga:def __init__(self, input_=city_dist_mat):global city_dist_matcity_dist_mat = input_# 当代的最佳个体self.best = None# 种群self.individual_list = np.array([])# 每一代的最佳个体self.result_list = []# 每一代个体对应的最佳适应度self.fitness_list = []# 每一代个体的距离self.distance_list = []# 种群交叉def genes_cross(self, CROSS_RATE = 0.8):new_pop = []# 循环选择两个父代for i in range(0, len(self.individual_list)-1, 2):# 以一定概率进行交叉if np.random.rand() < CROSS_RATE:parent1 = self.individual_list[i].genesparent2 = self.individual_list[i+1].genes# 采用顺序交叉法begin = random.randint(1, city_num - 1)end = random.randint(1, city_num - 1)# 确保begin小于endif begin > end:tmp = beginbegin = endend = tmpindiviual1_gene = copy.deepcopy(parent2)indiviual2_gene = copy.deepcopy(parent1)# 将子代二里父代二被选中的部分删除for i in range(begin, end+1):indiviual2_gene.remove(parent2[i])# 放入相应位置元素 begin -> endfor i in range(begin, end+1):indiviual2_gene.insert(i, parent2[i])# 将子代一里父代一被选中的部分删除for i in range(begin, end+1):indiviual1_gene.remove(parent1[i])# 放入相应位置元素begin->endfor i in range(begin, end+1):indiviual1_gene.insert(i, parent1[i])# 产生两个子代new_pop.append(Individual(indiviual1_gene))new_pop.append(Individual(indiviual2_gene))return new_pop# 种群变异def genes_update(self, new_gene, UPTATE_RATE = 0.2):# 基于次序的变异# 依次遍历for gene in new_gene:# 以一定概率进行变异if np.random.rand() < UPTATE_RATE:# 随机选择两位进行交换，变异x = random.randint(1, gene_num - 1)y = random.randint(1, gene_num - 1)temp = gene.genes[x]gene.genes[x] = gene.genes[y]gene.genes[y] = temp# 轮盘赌选择def wheel_select(self, new_gene):new_ga = []sum_val = 0for gene in new_gene:sum_val = sum_val + gene.fitnessfor i in range(individual_num):random_val = random.random()*sum_valprobability = 0for gene in new_gene:probability += gene.fitnessif probability >= random_val:new_ga.append(gene)return new_ga# 更新种群def next_gene(self):new = self.genes_cross() # 交叉子代self.genes_update(new)   # 变异子代self.individual_list = self.wheel_select(new)# self.wheel_select(new)   # 选择，优胜略汰# 获得该代最佳个体for individual in self.individual_list:if individual.fitness > self.best.fitness:self.best = individualdef train(self):# 随机出初代种群self.individual_list = [Individual() for _ in range(individual_num)]self.best = self.individual_list[0]# 迭代for i in range(circle_num):# 获得下一代self.next_gene()# 找到这一代的最佳个体放入result中result = copy.deepcopy(self.best.genes)# 加入起点result.append(result[0])self.result_list.append(result)self.fitness_list.append(self.best.fitness)self.distance_list.append(self.best.distance)return self.result_list, self.fitness_list, self.distance_listif __name__ == '__main__':ga = Ga()resultlist, fitnesslist, distancelist = ga.train()print(resultlist)print(fitnesslist)print(distancelist)