遗传算法求解TSP问题

#遗传算法求解TSP问题| 来源: 网络整理| 查看: 265

文章目录遗传算法求解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 + last self.genes = genes # 计算路径距离 self.distance = self.evaluate_distance() # 计算适应度 self.fitness = self.evaluate_fitness()

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

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

def evaluate_distance(self): distance = 0 for 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 = 0 for 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() end: tmp = begin begin = end end = tmp indiviual1_gene = copy.deepcopy(parent2) indiviual2_gene = copy.deepcopy(parent1) # 将子代二里父代二被选中的部分删除 for i in range(begin, end+1): indiviual2_gene.remove(parent2[i]) # 放入相应位置元素 begin -> end for 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->end for 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() = 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] = 2216 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 + last self.genes = genes self.distance = self.evaluate_distance() self.fitness = self.evaluate_fitness() # 计算个体的适应度 def evaluate_fitness(self): value = 0 for 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 def evaluate_distance(self): distance = 0 for 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 class Ga: def __init__(self, input_=city_dist_mat): global city_dist_mat city_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() end: tmp = begin begin = end end = tmp indiviual1_gene = copy.deepcopy(parent2) indiviual2_gene = copy.deepcopy(parent1) # 将子代二里父代二被选中的部分删除 for i in range(begin, end+1): indiviual2_gene.remove(parent2[i]) # 放入相应位置元素 begin -> end for 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->end for 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() = 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 = individual def 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_list if __name__ == '__main__': ga = Ga() resultlist, fitnesslist, distancelist = ga.train() print(resultlist) print(fitnesslist) print(distancelist)

【本文地址】

公司简介

联系我们