这是一份机器学习作业，我觉得遗传算法是一种很有趣的算法
GitHub项目链接github.com/K1ndred-zsq…
我的代码并不完美欢迎大佬来修改

1 旅行商问题

标题：
设有n个城市和距离矩阵D=[dij]，其中dij表明城市i到城市j的距离，i，j=1，2 … n，则问题是要找出遍访每个城市刚好一次的一条回路并使其途径长度为最短。
思路：
- 所有符合“每个城市刚好一次的一条回路”的道路均视为可行解
- 则该问题只需要找出最优解

2 遗传算法

具体的原理这儿暂时不做赘述
算法的流程包括
1. 初始化种群
2. 核算习惯度
3. 挑选
4. 穿插
5. 变异
6. 发生新一代种群
7. 重复2 – 6，优胜劣汰

graph TD
s(Start) --> 初始化种群 --> 核算习惯度--> p{判别进化是否完毕} --no--> 
挑选,精英保存 --> 穿插 --> 概率变异 --> 核算习惯度
p -- yes --> e(Stop)

3 算法描述

3.1 环境搭建

版别：python3.8.8
编译器：vscode

导包

import random
from matplotlib import pyplot as plt
import numpy as np
import math
# 避免中文和特别字符乱码
plt.rcParams['font.sans-serif'] = ['SimHei'] 
plt.rcParams['axes.unicode_minus'] = False

3.2 城市界说

界说城市类

建立size个城市，编码为”0″ – “size - 1“
每座城市均为一个坐标点
假定区域的巨细为100 x 100，区域左下角为坐标系原点
为了确保成果准确度，城市的坐标暂时规定为整数
设size=5，则一条染色体为”0-1-2-3-4″

class City:
    def __init__(self, size:int):
        # 城市数量
        self.size = size
        # 方位矩阵
        self.position = np.zeros((size, 2))
        x_list = random.sample(range(0, 100), size)
        y_list = random.sample(range(0, 100), size)
        self.position[:, 0] = x_list[:]
        self.position[:, 1] = y_list[:]
        # 距离矩阵D
        self.D = np.zeros((size, size), dtype='float64')
        for i in range(size):
            for j in range(size):
                self.D[i, j] = math.sqrt(pow((self.position[i, 0] - self.position[j, 0]), 2) + pow((self.position[i, 1] - self.position[j, 1]), 2))
    # 可视化办法
    def show_city(self):
        fig, ax = plt.subplots(figsize=(10, 10))
        ax.scatter(self.position[:, 0], self.position[:, 1], s=30, color='b')
        ax.legend()
        x_list = self.position[:, 0].copy().tolist()
        y_list = self.position[:, 1].copy().tolist()
        # zip打包函数：将两个列表按次序打包成一个个元组，如[1, 2]和[3, 4]会被打包成类似于[(1, 3), (2, 4)]这样的格式
        for a, b in zip(x_list, y_list):
            plt.text(a, b, (a,b), ha='center', va='bottom', fontsize=10)
        plt.show()

3.3 个别界说以及习惯度核算

界说个别类

习惯度值为一次回路进行的距离

class Individuality:
    def __init__(self, city: City):
        # 染色体
        self.chromosome = []
        # 习惯度
        self.fitness = 0.0
        self.size = city.size
        self.city = city
    # 设置起点城市完善个别
    def initByStart(self, num):
        self.chromosome = [i for i in range(self.size)]
        random.shuffle(self.chromosome)
        self.chromosome.remove(num)
        self.chromosome.insert(0, num)
        self.setFitness()
    # 依据染色体完善个别
    def initByChromosome(self, chromosome):
        self.chromosome = chromosome
        self.setFitness()
    # 核算习惯度
    def setFitness(self):
        for i in range(self.size - 1):
            self.fitness += self.city.D[self.chromosome[i], self.chromosome[i + 1]]
        self.fitness += self.city.D[self.chromosome[-1], self.chromosome[0]]
    # 可视化办法
    def show(self, title:str):
        fig, ax = plt.subplots(figsize=(10, 10))
        ax.scatter(self.city.position[:, 0], self.city.position[:, 1], s=30, color='b')
        ax.legend()
        plt.plot(self.city.position[self.chromosome, 0], self.city.position[self.chromosome, 1], 'r')
        plt.plot([self.city.position[self.chromosome[-1], 0], self.city.position[self.chromosome[0], 0]], [self.city.position[self.chromosome[-1], 1], self.city.position[self.chromosome[0], 1]], 'r')
        plt.title(title+f"/习惯度:{self.fitness}")
        x_list = self.city.position[:, 0].copy().tolist()
        y_list = self.city.position[:, 1].copy().tolist()
        for a, b in zip(x_list, y_list):
            plt.text(a, b, (a,b), ha='center', va='bottom', fontsize=10)
        plt.show()

3.4 进化流程

界说训练类,后文逐个叙述思路

class Train:
    def __init__(self, city:City, lens, groups):
        # 导入城市布局
        self.city = city
        # 种群列表
        self.gen = []
        # 组巨细
        self.lens = lens
        # 组数
        self.groups = groups
        # 种群巨细
        self.size = lens * groups
    # 初始化种族
    def init_gen(self):
        pass
    # 穿插
    def cross(self):
        pass
    # 变异
    def mutate(self, new_chros):
        pass
    # 挑选迭代
    def select(self):
        pass
    # 排序
    def mySort(self):
        pass

3.4.1 初始化种群

虽然终究道路是回路，但不同的起点总能诞生更多的可能
将个别分成groups个组，每组起点不一样，每组lens个个别
0<=groups<=city.size
则总个别数size = groups * lens ，总数最好为偶数

    def init_gen(self):
        self.gen = []
        for i in range(self.groups):
            for j in range(self.lens):
                ind = Individuality(self.city)
                ind.initByStart(i)
                self.gen.append(ind)

3.4.2 穿插

将两个个别直接交流某一片段可能会导致基因缺失/重复
如 0-1-2-3-4-5和5-4-3-2-1-0，将前三个基因交流，
则变成5-4-3-3-4-5和0-1-2-2-1-0
所以咱们能够将两个个别交流基因片段转变为单个个别逐个改动基因方位
如上面的两个个别交流前两个个基因，变成单个个别交流0-5,1-4的方位
穿插完变成5-4-2-3-1-0和0-1-3-2-4-5
咱们能够以字典的方式记载每个基因的方位，便利交流

    def cross(self):
        new_chros = []
        # 按次序两两穿插,若总个数为奇数则忽略最终一名，所以主张总数为偶数
        for i in range(self.size // 2):
            chro1 = self.gen[i * 2].chromosome.copy()
            chro2 = self.gen[i * 2 + 1].chromosome.copy()
            # 随机交流片段
            index1 = random.randint(0, self.city.size - 2)
            index2 = random.randint(index1 + 1, self.city.size - 1)
            vk1 = {v: k for k, v in enumerate(chro1)}
            vk2 = {v: k for k, v in enumerate(chro2)}
            for j in range(index1, index2 + 1):
                v1 = chro1[j]
                v2 = chro2[j]
                nk1 = vk1[v2]
                nk2 = vk2[v1]
                chro1[j], chro1[nk1] = chro1[nk1], chro1[j]
                chro2[j], chro2[nk2] = chro2[nk2], chro2[j]
                vk1[v1], vk1[v2] = nk1, j
                vk2[v1], vk2[v2] = j, nk2
            new_chros.append(chro1)
            new_chros.append(chro2)
        return new_chros

3.4.3 变异

抽取大约50%穿插后染色体的一个片段，打乱以后放回去，生成新个别，参加种群

    def mutate(self, new_chros):
        for chro in new_chros:
            # 50%概率
            n = random.randint(0, 1)
            if n == 0:
                self.gen.append(ind)
                continue
            index1 = random.randint(0, self.city.size - 2)
            index2 = random.randint(index1 + 1, self.city.size - 1)
            mu_chro = chro[index1: index2 + 1]
            random.shuffle(mu_chro)
            new_chro = chro[:index1]
            new_chro.extend(mu_chro)
            new_chro.extend(chro[index2 + 1: ])
            ind = Individuality(self.city)
            ind.initByChromosome(new_chro)
            self.gen.append(ind)

3.4.4 挑选

锦标赛算法
按习惯度巨细升序排序
此时两代加起来理论有size*2个个别，保存前size名

# 挑选迭代
    def select(self):
        self.mySort()
        self.gen = self.gen[:self.size]
    # 排序
    def mySort(self):
        for i in range(self.size * 2 - 1):
            for j in range(i + 1, self.size * 2):
                if self.gen[i].fitness > self.gen[j].fitness:
                    self.gen[i], self.gen[j] = self.gen[j], self.gen[i]

3.4.5 一次迭代

综合上面的办法

    def train(self, n):
        self.mutate(self.cross())
        self.select()
        print(f"第{n}次迭代最优个别习惯度：{self.gen[0].fitness}")

3.5 迭代

主张按次数迭代，观察习惯度曲线来判别是否已经完毕

举例并打印终究成果

if __name__ == '__main__':
    # 迭代次数
    count = 1000
    # 10个城市
    city = City(10)
    # 种群初始化，4组，每组10个，共40个个别
    train = Train(city, 10, 4)
    train.init_gen()
    for i in range(count):
        train.train(i + 1)
    train.gen[0].show(f"{count}次迭代最优解")

部分成果展现

4 验证

下面供给一个一般的深度优先搜索办法，枚举每一种状况，得出理论最小习惯度，大家能够参阅

def dfs(chro: list, city: City):
    if len(chro) == city.size:
        ind = Individuality(city)
        ind.initByChromosome(chro)
        return ind
    inds = []
    for i in range(city.size):
        if i not in chro:
            new_chro = chro.copy()
            new_chro.append(i)
            ind = dfs(new_chro, city)
            inds.append(ind)
    n = len(inds)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if(inds[j].fitness < inds[i].fitness):
                inds[i], inds[j] = inds[j], inds[i]
    # 返回最优个别
    return inds[0]

5 结论

遗传算法也能够作为一种智能搜索算法，但也有局限性，有很大的开展和改善空间，结合轮盘赌算法能更好，我的办法仅作为参阅。实际生活中，不同路段的损耗，城市之间的通行约束会让这个算法更杂乱，更有趣。

6 完好源代码(不包括枚举)

import random
from matplotlib import pyplot as plt
import numpy as np
import math
# 避免中文和特别字符乱码
plt.rcParams['font.sans-serif'] = ['SimHei'] 
plt.rcParams['axes.unicode_minus'] = False 
# 城市类
class City:
    def __init__(self, size:int):
        # 城市数量
        self.size = size
        # 方位矩阵
        self.position = np.zeros((size, 2))
        x_list = random.sample(range(0, 100), size)
        y_list = random.sample(range(0, 100), size)
        self.position[:, 0] = x_list[:]
        self.position[:, 1] = y_list[:]
        # 距离矩阵D
        self.D = np.zeros((size, size), dtype='float64')
        for i in range(size):
            for j in range(size):
                self.D[i, j] = math.sqrt(pow((self.position[i, 0] - self.position[j, 0]), 2) + pow((self.position[i, 1] - self.position[j, 1]), 2))
    # 可视化办法
    def show(self):
        fig, ax = plt.subplots(figsize=(10, 10))
        ax.scatter(self.position[:, 0], self.position[:, 1], s=30, color='b')
        ax.legend()
        x_list = self.position[:, 0].copy().tolist()
        y_list = self.position[:, 1].copy().tolist()
        for a, b in zip(x_list, y_list):
            plt.text(a, b, (a,b), ha='center', va='bottom', fontsize=10)
        plt.show()
# 个别类
class Individuality:
    def __init__(self, city: City):
        # 染色体
        self.chromosome = []
        # 习惯度
        self.fitness = 0.0
        self.size = city.size
        self.city = city
    # 设置起点城市完善个别
    def initByStart(self, num):
        self.chromosome = [i for i in range(self.size)]
        random.shuffle(self.chromosome)
        self.chromosome.remove(num)
        self.chromosome.insert(0, num)
        self.setFitness()
    # 依据染色体完善个别
    def initByChromosome(self, chromosome):
        self.chromosome = chromosome
        self.setFitness()
    # 核算习惯度
    def setFitness(self):
        for i in range(self.size - 1):
            self.fitness += self.city.D[self.chromosome[i], self.chromosome[i + 1]]
        self.fitness += self.city.D[self.chromosome[-1], self.chromosome[0]]
    # 可视化办法
    def show(self, title:str):
        fig, ax = plt.subplots(figsize=(10, 10))
        ax.scatter(self.city.position[:, 0], self.city.position[:, 1], s=30, color='b')
        ax.legend()
        plt.plot(self.city.position[self.chromosome, 0], self.city.position[self.chromosome, 1], 'r')
        plt.plot([self.city.position[self.chromosome[-1], 0], self.city.position[self.chromosome[0], 0]], [self.city.position[self.chromosome[-1], 1], self.city.position[self.chromosome[0], 1]], 'r')
        plt.title(title+f"/习惯度:{self.fitness}")
        x_list = self.city.position[:, 0].copy().tolist()
        y_list = self.city.position[:, 1].copy().tolist()
        for a, b in zip(x_list, y_list):
            plt.text(a, b, (a,b), ha='center', va='bottom', fontsize=10)
        plt.show()
class Train:
    def __init__(self, city:City, lens, groups):
        # 导入城市布局
        self.city = city
        # 种群列表
        self.gen = []
        # 组巨细
        self.lens = lens
        # 组数
        self.groups = groups
        # 种群巨细
        self.size = lens * groups
    # 初始化种族
    def init_gen(self):
        self.gen = []
        for i in range(self.groups):
            for j in range(self.lens):
                ind = Individuality(self.city)
                ind.initByStart(i)
                self.gen.append(ind)
    # 穿插
    def cross(self):
        new_chros = []
        # 按次序两两穿插,若总个数为奇数则忽略最终一名，所以主张总数为偶数
        for i in range(self.size // 2):
            chro1 = self.gen[i * 2].chromosome.copy()
            chro2 = self.gen[i * 2 + 1].chromosome.copy()
            # 随机交流片段
            index1 = random.randint(0, self.city.size - 2)
            index2 = random.randint(index1 + 1, self.city.size - 1)
            vk1 = {v: k for k, v in enumerate(chro1)}
            vk2 = {v: k for k, v in enumerate(chro2)}
            for j in range(index1, index2 + 1):
                v1 = chro1[j]
                v2 = chro2[j]
                nk1 = vk1[v2]
                nk2 = vk2[v1]
                chro1[j], chro1[nk1] = chro1[nk1], chro1[j]
                chro2[j], chro2[nk2] = chro2[nk2], chro2[j]
                vk1[v1], vk1[v2] = nk1, j
                vk2[v1], vk2[v2] = j, nk2
            new_chros.append(chro1)
            new_chros.append(chro2)
        return new_chros
    # 变异
    def mutate(self, new_chros):
        for chro in new_chros:
            # 50%概率
            n = random.randint(0, 1)
            if n == 0:
                self.gen.append(ind)
                continue
            index1 = random.randint(0, self.city.size - 2)
            index2 = random.randint(index1 + 1, self.city.size - 1)
            mu_chro = chro[index1:index2 + 1]
            random.shuffle(mu_chro)
            new_chro = chro[:index1]
            new_chro.extend(mu_chro)
            new_chro.extend(chro[index2 + 1: ])
            ind = Individuality(self.city)
            ind.initByChromosome(new_chro)
            self.gen.append(ind)
    # 挑选迭代
    def select(self):
        self.mySort()
        self.gen = self.gen[:self.size]
    # 排序
    def mySort(self):
        for i in range(self.size * 2 - 1):
            for j in range(i + 1, self.size * 2):
                if self.gen[i].fitness > self.gen[j].fitness:
                    self.gen[i], self.gen[j] = self.gen[j], self.gen[i]
    # 进化一次
    def train(self, n):
        self.mutate(self.cross())
        self.select()
        print(f"第{n}次迭代最优个别习惯度：{self.gen[0].fitness}")
if __name__ == '__main__':
    # 迭代次数
    count = 1000
    # 10个城市
    city = City(10)
    # 种群初始化，4组，每组10个，共40个个别
    train = Train(city, 10, 4)
    train.init_gen()
    for i in range(count):
        train.train(i + 1)
    train.gen[0].show(f"{count}次迭代最优解")

基于遗传算法求解旅行商问题（python，有源码）

1 旅行商问题

2 遗传算法

3 算法描述

3.1 环境搭建

3.2 城市界说

3.3 个别界说以及习惯度核算

3.4 进化流程

3.4.1 初始化种群

3.4.2 穿插

3.4.3 变异

3.4.4 挑选

3.4.5 一次迭代

3.5 迭代

4 验证

5 结论

6 完好源代码(不包括枚举)

作者信息

推广

基于遗传算法求解旅行商问题（python，有源码）

1 旅行商问题

2 遗传算法

3 算法描述

3.1 环境搭建

3.2 城市界说

3.3 个别界说以及习惯度核算

3.4 进化流程

3.4.1 初始化种群

3.4.2 穿插

3.4.3 变异

3.4.4 挑选

3.4.5 一次迭代

3.5 迭代

4 验证

5 结论

6 完好源代码(不包括枚举)

相关文章

iOS启动时间优化-二进制重排的前世

团队技术专家回老家了，留下的技术设计模板真好用！

在 iOS 中使用 IdentifyLookup 进行短信过滤

Rust简明学习手册 – Rust安装和基本概念

作者信息

推广