1.遗传算法简介

遗传算法(Genetic Algorithm), 简称 GA。是一种通过模拟自然进化过程搜索最优解的方法。在遗传算法中，每个个体通常由染色体表示（个体（潜在解）的二进制编码），通过选择、交叉和变异等遗传操作来模拟生物进化过程，以寻找最优解或近似最优解。

2.遗传算法核心思想

遗传算法的核心要素有5个：参数编码、初始群体、适应度函数、遗传操作（选择、交叉和变异）、解码。GA 算法最重要的就是明白什么是个体 和怎么样对个体进行评估 (他们的 Fitness)。

2.1参数编码

在遗传算法中，每个个体通常由染色体表示（个体（可能解）的二进制编码）。首先我们搞清楚可能解的形式是什么。以10座城市为例，城市编码（0、1、2........n），我们希望得到的解或许是3 5 4 8 6 7 9 0 2 1。因此，在遗传算法中，每个个体的形式可以用10个不重复数字的排列表示。好消息是这样一来不需要进行二进制编码解码了。

2.2初始群体

个体是指代表问题解空间中一个可能解的一个实体，群体则是这样的一组一组的可能解的集合。下面这小段代码可以生产一个初始群体：

self.city_num = 10 # 有10个城市
self.pop_size = 100  # 种群大小（个体个数）
 # 初始化种群
def init_population(self):
    path=np.array(range(self.city_num)) # 初始化1个个体
    population = []
    for i in range(self.pop_size):
        x=path.copy()
        np.random.shuffle(x)    # 随机洗牌
        population.append(x)    # 初始化100个个体，生成群体

2.3适应度函数

适应度函数作用是对个体进行评估 (他们的 Fitness)，评价一个个体的基因是否适合被遗传下来。这就需要计算个体的适应度，适应度越高的个体，被选择的概率就越大。在tsp问题中，我们希望一个个体的路径长度越短越好，即路径越短，适应度越大。因此适应度公式可以是这样的：

    # 根据路径长度计算每个个体的适应度
    self.fitness = []
    for i in range(self.pop_size):
        self.fitness.append(1 / (self.dis[i] ** 15))

2.4遗传操作

• 选择操作 (selection)-适者生存，不适者淘汰

• 交叉操作 (crossover)

• 变异操作 (mutation)

选择操作

适应度越大的个体被选中的可能性越大，用numpy.choice来实现。其他方式：也可以采用杰出父代+子代的方式来更新种群。

    # 根据适应度进行选择，适应度大的被选择概率大
    idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True,
                               p=(self.fitness) / (fitness_sum))

交叉操作

常见的3种交叉操作：部分映射交叉，顺序交叉，基于位置的交叉

我们这里可以选择顺序交叉，步骤如下：

变异操作

变异时随机选择两个不同的位置的基因进行交换。也可以采用三点变异法，随机生成abc三点，将ac基因片段与bc做交换。如果是二进制编码，主要采用单点变异，也叫位变异，即只需要对基因序列中某一个位进行变异，以二进制编码为例，即0变为1，而1变为0

3.遗传算法实现过程

第一步：初始化 i←0进化代数计数器；max_gen是最大进化代数（也可以没有）；随机生成M个个体作为初始群体P（i）；

第二步：个体评价 计算P（i）中各个个体的适应度；

第三步：交叉运算 将交叉算子作用于群体；-》在原始群体中，每对父母以一定概率生成一个新解，生成新群体

第四步：变异运算 将变异算子作用于群体，-》在交叉后的群体中，每个个体以一定概率发生突变，生成新群体

第五步：选择运算 将选择算子作用于群体；-》用轮盘赌的方式进行自然选择，fitness越大的被选择的概率越大

，经过以上运算后得到下一代群体P（i+ 1）;

第六步：终止条件判断 i≦max_gen：

i← i+1 转到步骤2；

i>max_gen：终止 输出解。

4.遗传算法实现34个城市的TSP问题

核心算子的代码：

    # 获得距离矩阵
    def gen_dist_mat(self):
        D = self.cities
        city_cnt = self.cities_num
        dist_mat = np.zeros((city_cnt, city_cnt))
        for i in range(city_cnt):
            for j in range(city_cnt):
                if i == j:
                    # 相同城市不允许访问
                    dist_mat[i][j] = 1000000
                else:
                    # 单位：km
                    dist_mat[i][j] = 6378.14 * math.acos(
                        math.cos(D[i][1]) * math.cos(D[j][1]) * math.cos(D[i][0] - D[j][0]) +
                        math.sin(D[i][1]) * math.sin(D[j][1]))
        self.dist_mat = dist_mat
 
    # 计算路径长度
    def dis_cal(self, path):
        """
        适应度函数，计算目标函数值.
        :param path: 一个解
        :return: 目标函数值，即总距离
        """
        distance = 0
        for i in range(len(path) - 1):
            distance += self.dist_mat[path[i]][path[i + 1]]
        distance += self.dist_mat[path[-1]][path[0]]  # 从最后一个城市回到出发城市
        return distance
 
    # 初始化种群
    def init_population(self):
        path = np.array(range(self.cities_num))
        self.population = []
        for i in range(self.pop_size):
            x = path.copy()
            np.random.shuffle(x)  # 随机洗牌
            self.population.append(x)
 
    # 自然选择，种群根据适应度进行更新
    def select(self):
        # 计算每条路径的长度，放入列表
        self.dis = []
        for i in range(self.pop_size):
            self.dis.append(self.dis_cal(path=self.population[i]))
        # 根据路径长度计算每个个体的适应度
        self.fitness = []
        for i in range(self.pop_size):
            self.fitness.append(1 / (self.dis[i] ** 15))
        # 适应度总和
        fitness_sum = 0
        for i in range(self.pop_size):
            fitness_sum += self.fitness[i]
        # 根据适应度进行选择，适应度大的被选择概率大
        idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True,
                               p=(self.fitness) / (fitness_sum))
        self.new_pop = []
        for i in idx:
            self.new_pop.append(self.population[i])
        self.population = self.new_pop
 
    # 交叉互换
    def crossover(self):
        self.new_pop = []
        for father in self.population:
            child = father  # 初步让子代获得父本染色体
            if np.random.rand() < self.cross_rate:
                # 随机选择一个染色体作为母本
                mother_index = np.random.randint(0, self.pop_size)
                mother = self.population[mother_index]
                # 确定切割点     
                left = np.random.randint(0, self.cities_num - 2)
                right = np.random.randint(left + 1, self.cities_num - 1)
                mother = mother.tolist()
                father = father.tolist()
                # 切割片段
                gene = mother[left:right]
                child1_c = father[right:] + father[:right]
                child1 = child1_c.copy()
                # 去除重复基因
                for o in gene:
                    child1_c.remove(o)
                child1[left:right] = gene
                child1[right:] = child1_c[0:len(child1) - right]
                child1[:left] = child1_c[(len(child1) - right):]
                child = np.array(child1)
 
            self.new_pop.append(child)
        self.population = self.new_pop
 
    # 变异
    def mutation(self):
        for i in range(self.pop_size):
            if np.random.rand() < self.muta_rate:
                child = self.population[i]
                u = np.random.randint(0, self.cities_num - 2)
                v = np.random.randint(u + 1, self.cities_num - 1)
                child_x = child[u + 1:v]
                child_x = child_x[::-1]
                child = np.concatenate((child[0:u + 1], child_x, child[v:]))
                self.population[i] = child

5.结果输出

the shortest path is:30-->29-->31-->28-->27-->26-->24-->25-->23-->19-->18-->20-->21-->22-->15-->14-->16-->17-->5-->8-->9-->11-->13-->12-->10-->6-->7-->4-->3-->2-->1-->0-->33-->32
the total distance is 16253.778217630528

6.相关阅读

1.遗传算法解决tsp问题（基于python）_遗传算法解决tsp问题python-CSDN博客

2.【建模算法】基于遗传算法求解TSP问题（Python实现）_城市序号x坐标y坐标-CSDN博客

3.干货 | 遗传算法(Genetic Algorithm) （附代码及注释）

相关视频会在后续发布，欢迎关注我的bilibili：无形忍者的个人空间-无形忍者个人主页-哔哩哔哩视频