【建模算法】基于遗传算法求解TSP问题(Python实现)_城市序号x坐标y坐标-程序员宅基地

技术标签: 算法  数学建模  python  

【建模算法】基于遗传算法求解TSP问题(Python实现)

TSP (traveling salesman problem,旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还未找到一个多项式时间的有效算法。本文探讨了基于遗传算法求解TSP问题的Python实现。

一、问题描述

​ 本案例以31个城市为例,假定31个城市的位置坐标如表1所列。寻找出一条最短的遍历31个城市的路径。

城市编号 X坐标 Y坐标 城市编号 X坐标 Y坐标
1 1.304 2.312 17 3.918 2.179
2 3.639 1.315 18 4.061 2.37
3 4.177 2.244 19 3.78 2.212
4 3.712 1.399 20 3.676 2.578
5 3.488 1.535 21 4.029 2.838
6 3.326 1.556 22 4.263 2.931
7 3.238 1.229 23 3.429 1.908
8 4.196 1.044 24 3.507 2.376
9 4.312 0.79 25 3.394 2.643
10 4.386 0.57 26 3.439 3.201
11 3.007 1.97 27 2.935 3.24
12 2.562 1.756 28 3.14 3.55
13 2.788 1.491 29 2.545 2.357
14 2.381 1.676 30 2.778 2.826
15 1.332 0.695 31 2.37 2.975
16 3.715 1.678

二、解题思路及步骤

1.遗传算法步骤:

第一步:初始化 t←0进化代数计数器;T是最大进化代数(也可以没有);随机生成M个个体作为初始群体P(t);

第二步:个体评价 计算P(t)中各个个体的适应度;

第三步:选择运算 将选择算子作用于群体;

第四步:交叉运算 将交叉算子作用于群体;

第五步:变异运算 将变异算子作用于群体,并通过以上运算得到下一代群体P(t + 1);

第六步:终止条件判断 t≦T:t← t+1 转到步骤2;t>T:终止 输出解。

2.遗传算法求解的一般过程:

1)确定决策变量及各种约束条件,即个体的表现型X和问题的解空间;

2)建立优化模型 (目标函数最大OR 最小) 数学描述形式 量化方法;

3)染色体编码方法;

4)解码方法;

5)个体适应度的量化评价方法 F(x)

6)设计遗传算子;

7)确定有关运行参数。

3.方法实现

编码方式

应用于TSP问题,选用整数编码,每个整数代表一个城市,一整条路径就是整个染色体编码;如此显式的编码,可以不用解码;

population = []

# 初始化种群

index = [i for i in range(w)]
for i in range(count):
    x = index.copy()
    random.shuffle(x)
    gailiang(x)
    population.append(x)

初始种群

随机生成初始种群,并计算这个初始种群的个体适应度。初始化种群时,采用改良版本,为了初始化一个较好的种群,如果随即交换两个城市的位置,如果总距离减小,那么就更新这个染色体。

# 初始种群的改良
def gailiang(x):
    distance = get_total_distance(x)
    gailiang_num = 0
    while gailiang_num < gailiang_N:
        while True:
            a = random.randint(0, len(x) - 1)
            b = random.randint(0, len(x) - 1)
            if a != b:
                break
        new_x = x.copy()
        temp_a = new_x[a]
        new_x[a] = new_x[b]
        new_x[b] = temp_a
        if get_total_distance(new_x) < distance:
            x = new_x.copy()
        gailiang_num += 1

选择算子

选择总距离作为适应度函数,距离越小适应度越高,(存活率与总距离的倒数成正比)

# 适应度
def get_total_distance(x):
    dista = 0
    for i in range(len(x)):
        if i == len(x) - 1:
            dista += distance[x[i]][x[0]]
        else:
            dista += distance[x[i]][x[i + 1]]
    return dista

交叉算子

1 部分映射交叉

选择交换部分,交换父代个体基因产生子代,然后建立映射表,根据映射表来消除基因冲突。

2 顺序交叉

在父代样本1中选择交换部分,根据父代1的交叉部分先生成子代1的部分基因片段,然后将父代2中未被选中的基因按顺序复制到子代1的空余部分;然后根据父代2选择交叉部分生成子代2,并将父代1中未选择的部分复制到子代2的空余;

3 基于位置的交叉

在父代1选择时随机选择需要交换的基因,根据交叉部分生成子代1;将父代2中未被选择到的基因复制到子代1中;然后根据父代2随机选择交叉部分生成子代2,并将父代1中未选择的部分复制到子代2的空余;

# 交叉繁殖
def crossover(parents):
    target_count = count - len(parents)
    children = []
    while len(children) < target_count:
        while True:
            male_index = random.randint(0, len(parents)-1)
            female_index = random.randint(0, len(parents)-1)
            if male_index != female_index:
                break
        male = parents[male_index]
        female = parents[female_index]
        left = random.randint(0, len(male) - 2)
        right = random.randint(left, len(male) - 1)
        gen_male = male[left:right]
        gen_female = female[left:right]
        child_a = []
        child_b = []

        len_ca = 0
        for g in male:
            if len_ca == left:
                child_a.extend(gen_female)
                len_ca += len(gen_female)
            if g not in gen_female:
                child_a.append(g)
                len_ca += 1

        len_cb = 0
        for g in female:
            if len_cb == left:
                child_b.extend(gen_male)
                len_cb += len(gen_male)
            if g not in gen_male:
                child_b.append(g)
                len_cb += 1

        children.append(child_a)
        children.append(child_b)
    return children

变异算子

根据变异算子的概率,变异时随机选择两个不同的位置的基因进行交换。也可以采用三点变异法,随机生成abc三点,将ac基因片段与bc做交换。

# 变异操作
def mutation(children):
    for i in range(len(children)):
        if random.random() < mutation_rate:
            while True:
                u = random.randint(0, len(children[i]) - 1)
                v = random.randint(0, len(children[i]) - 1)
                if u != v:
                    break
            temp_a = children[i][u]
            children[i][u] = children[i][v]
            children[i][v] = temp_a

更新种群

采用杰出父代+子代的方式来更新种群。

while i < iter_time:
    # 自然选择
    parents = nature_select(population)

    # 繁殖
    children = crossover(parents)

    # 变异
    mutation(children)

    # 更新
    population = parents + children

    result_cur_best, dist_cur_best = get_result(population)
    distance_list.append(dist_cur_best)
    i = i + 1
    print(result_cur_best)
    print(dist_cur_best)

我在求解时采用了在初始种群中进行改良的方法,收敛速度相对较快,求解结果比较满意。

三、求解结果

距离和城市序列:

在这里插入图片描述

TSP图和Loss图:

在这里插入图片描述
在这里插入图片描述

四、实现代码

#遗传算法求解TSP问题完整代码:
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
import math
import random

# 处理数据

coord = []
with open("data.txt", "r") as lines:
    lines = lines.readlines()
for line in lines:
    xy = line.split()
    coord.append(xy)

coord = np.array(coord)
w, h = coord.shape
coordinates = np.zeros((w, h), float)
for i in range(w):
    for j in range(h):
        coordinates[i, j] = float(coord[i, j])

# print(coordinates)

# 得到距离矩阵

distance = np.zeros((w, w))
for i in range(w):
    for j in range(w):
        distance[i, j] = distance[j, i] = np.linalg.norm(coordinates[i] - coordinates[j])

# 种群数
count = 300

# 进化次数
iter_time = 1000

# 最优选择概率
retain_rate = 0.3  # 适应度前30%可以活下来

# 弱者生存概率
random_select_rate = 0.5

# 变异
mutation_rate = 0.1

# 改良
gailiang_N = 3000


# 适应度
def get_total_distance(x):
    dista = 0
    for i in range(len(x)):
        if i == len(x) - 1:
            dista += distance[x[i]][x[0]]
        else:
            dista += distance[x[i]][x[i + 1]]
    return dista

# 初始种群的改良
def gailiang(x):
    distance = get_total_distance(x)
    gailiang_num = 0
    while gailiang_num < gailiang_N:
        while True:
            a = random.randint(0, len(x) - 1)
            b = random.randint(0, len(x) - 1)
            if a != b:
                break
        new_x = x.copy()
        temp_a = new_x[a]
        new_x[a] = new_x[b]
        new_x[b] = temp_a
        if get_total_distance(new_x) < distance:
            x = new_x.copy()
        gailiang_num += 1


# 自然选择

def nature_select(population):
    grad = [[x, get_total_distance(x)] for x in population]
    grad = [x[0] for x in sorted(grad, key=lambda x: x[1])]
    # 强者
    retain_length = int(retain_rate * len(grad))
    parents = grad[: retain_length]
    # 生存下来的弱者
    for ruozhe in grad[retain_length:]:
        if random.random() < random_select_rate:
            parents.append(ruozhe)
    return parents


# 交叉繁殖
def crossover(parents):
    target_count = count - len(parents)
    children = []
    while len(children) < target_count:
        while True:
            male_index = random.randint(0, len(parents)-1)
            female_index = random.randint(0, len(parents)-1)
            if male_index != female_index:
                break
        male = parents[male_index]
        female = parents[female_index]
        left = random.randint(0, len(male) - 2)
        right = random.randint(left, len(male) - 1)
        gen_male = male[left:right]
        gen_female = female[left:right]
        child_a = []
        child_b = []

        len_ca = 0
        for g in male:
            if len_ca == left:
                child_a.extend(gen_female)
                len_ca += len(gen_female)
            if g not in gen_female:
                child_a.append(g)
                len_ca += 1

        len_cb = 0
        for g in female:
            if len_cb == left:
                child_b.extend(gen_male)
                len_cb += len(gen_male)
            if g not in gen_male:
                child_b.append(g)
                len_cb += 1

        children.append(child_a)
        children.append(child_b)
    return children


# 变异操作
def mutation(children):
    for i in range(len(children)):
        if random.random() < mutation_rate:
            while True:
                u = random.randint(0, len(children[i]) - 1)
                v = random.randint(0, len(children[i]) - 1)
                if u != v:
                    break
            temp_a = children[i][u]
            children[i][u] = children[i][v]
            children[i][v] = temp_a


def get_result(population):
    grad = [[x, get_total_distance(x)] for x in population]
    grad = sorted(grad, key=lambda x: x[1])
    return grad[0][0], grad[0][1]


population = []
# 初始化种群
index = [i for i in range(w)]
for i in range(count):
    x = index.copy()
    random.shuffle(x)
    gailiang(x)
    population.append(x)

distance_list = []
result_cur_best, dist_cur_best = get_result(population)
distance_list.append(dist_cur_best)

i = 0
while i < iter_time:
    # 自然选择
    parents = nature_select(population)

    # 繁殖
    children = crossover(parents)

    # 变异
    mutation(children)

    # 更新
    population = parents + children

    result_cur_best, dist_cur_best = get_result(population)
    distance_list.append(dist_cur_best)
    i = i + 1
    print(result_cur_best)
    print(dist_cur_best)


for i in range(len(result_cur_best)):
    result_cur_best[i] += 1

result_path = result_cur_best
result_path.append(result_path[0])

print(result_path)

# 画图

X = []
Y = []
for index in result_path:
    X.append(coordinates[index-1, 0])
    Y.append(coordinates[index-1, 1])

plt.rcParams['font.sans-serif'] = 'SimHei'  # 设置中文显示
plt.rcParams['axes.unicode_minus'] = False
plt.figure(1)
plt.plot(X, Y, '-o')
for i in range(len(X)):
    plt.text(X[i] + 0.05, Y[i] + 0.05, str(result_path[i]), color='red')
plt.xlabel('横坐标')
plt.ylabel('纵坐标')
plt.title('轨迹图')

plt.figure(2)
plt.plot(np.array(distance_list))
plt.title('优化过程')
plt.ylabel('最优值')
plt.xlabel('代数({}->{})'.format(0, iter_time))
plt.show()
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/baidu/article/details/124432689

智能推荐

com.alibaba.dubbo.remoting.TimeoutException: Waiting server-side response timeout by scan timer.-程序员宅基地

文章浏览阅读1.1w次,点赞6次,收藏3次。com.alibaba.dubbo.remoting.TimeoutException: Waiting server-side response timeout by scan timer.超时异常:等待服务响应超时。出现这个问题的分析:1,jar包依赖问题,没有成功引入依赖。2,服务提供方打了断点,导致代码执行堵塞,响应超时。3,服务端后台代码报错导致服务没有被成功调用(..._com.alibaba.dubbo.remoting.timeoutexception: waiting server-side response ti

利用Gh0st 3.6远程溢出漏洞反向控制攻击者_gh0st漏洞-程序员宅基地

文章浏览阅读883次。title: 利用Gh0st 3.6远程溢出漏洞反向控制攻击者comments: truetoc: truecategories:[Metasploit][Exp]tags:MetasploitOverflowGh0stdate: 2020-01-12 18:30:10abbrlink: 30568前言漏洞验证在2017年被公开,实际上Gh0st溢出漏洞在2009..._gh0st漏洞

EffectiveC++-条款25:考虑写出一个不抛异常的 swap 函数_effective c++ 条款25-程序员宅基地

文章浏览阅读206次。## 一. 内容1. swap 是一个有趣的函数。原本它只是STL的一部分,后面成为异常安全性编程的重要支柱(见条款29),以及处理自我赋值的常见机制(见条款11)。swap如此有用,考虑其合理的实现变得十分重要。2. 所谓 swap(置换),就是将两个对象的值彼此赋值给对方。3. 默认情况下,swap 可以交给 标准程序库提供的 swap 算法完成,其典型实现正如预期。 ```cpp namespace std{ template void swap(............_effective c++ 条款25

脚本和zabbix监控_不依赖zabbix,脚本监控-程序员宅基地

文章浏览阅读2.5k次,点赞3次,收藏9次。1 .LNMP环境一键安装脚本1.1 要求可编译也可yum安装,最终显示phpinfo信息:修改nginx默认端口为8000修改nginx的连接数为10240修改nginx的默认首页启动每个服务前,需要先检测服务是否存在1.2 脚本内容如下:#!/bin/bashnginx_install() { if [ -f /root/nginx-1.18.0.tar.gz ];then echo "nginx源码包存在,开始解压..." cd /root_不依赖zabbix,脚本监控

MybatisPlus实现多数据源_mybatis plus多数据源 @primary-程序员宅基地

文章浏览阅读2.2k次。关于mybatisPlus多数据源的一点小小的记录_mybatis plus多数据源 @primary

腾讯云颜松柏:详解DevOps成熟度模型与效能度量-程序员宅基地

文章浏览阅读2.6k次,点赞2次,收藏17次。成熟度模型是一次性评估,效能度量是持续、定期的度量_devops成熟度模型

随便推点

【C语言】枚举(enum)_c语言枚举-程序员宅基地

文章浏览阅读2.4k次,点赞4次,收藏21次。一、枚举语法的定义枚举(enum)是一种数据类型,它的语法定义格式为:enum枚举名{枚举元素1,枚举元素2,......};例如,一个星期有七天,使用枚举法进行定义为:enum Day{ Mon,Tue,Wed,Thu,Fri,Sat,Sun};需要注意的是,第一个枚举元素的默认值为0,后面的枚举元素的值在上一枚举元素的值上加1。因此,Mon=0,Tue=1,Wed=2,Thu=3,Fri=4,Sat=5,Sun=6.但是,在定义枚举类型时,可以改..._c语言枚举

2023 年江西省职业院校技能大赛 智能制造设备技术应用赛项任务书——学生赛样题_机器人拾取吸盘工具到物料区拾取物料并判断将合格品放到原料区不合格品放到回-程序员宅基地

文章浏览阅读982次,点赞20次,收藏21次。产品所在工位推动气缸缩回,缩回到位后升降气缸下降,下降到 位后检测LED灯闪烁,4s后,升降气缸上升,上升到位后推动气缸伸出,结果指示灯点亮(当检测结果为优良品时,绿灯常亮,当检测结果为废品时,红灯常亮,当检测为合格品时,红色和绿色指示灯交替闪烁)。1.程序正常运行过程中,若触发安全光栅,工业机器人速度降至当前速度的50%,降速超过6s,工业机器人停止运行。完成后,机器人回到安全点,暂停。4.按下 “开始”按钮,根据初次检测结果完成产品的入库工作,优良品的产品放入成品区,完成后机器人放下工具,回安全点。_机器人拾取吸盘工具到物料区拾取物料并判断将合格品放到原料区不合格品放到回

时间序列数据库KDB 与Java结合使用介绍 -- 3 基于KDB JDBC的写入实现_kdb支持sql吗-程序员宅基地

文章浏览阅读1.6k次。时间序列数据库KDB 与Java结合使用介绍 -- 3 基于KDB JDBC的写入实现_kdb支持sql吗

rgb颜色处理_rgb处理-程序员宅基地

这篇文章讲述了RGB颜色处理的方法,包括使用numpy和matplotlib库来处理图像,使用LAB色彩空间进行处理。

一、C++内存分区模型_c++的内存分区模型-程序员宅基地

文章浏览阅读129次。C++内存分区模型文章目录C++内存分区模型前言一、代码区和全局区1、代码区2、全局区二、栈区和堆区1.栈区2.堆区三、new操作符总结前言C++程序在执行时,将内存大方向相划分为4个区域:代码区:存放函数体的二进制代码,有操作系统进行管理全局区:存放全局变量和静态变量以及常量栈区: 由编译器自动分配和释放,存放函数的参数值,局部变量等堆区: 由程序员分配和释放,若程序员不释放,程序结束时由操作系统回收内存四区的意义: 不同区域存放的数据,赋予不同的生命周期,给我们更大的灵活_c++的内存分区模型

配置apache,直接访问服务器不显示文件目录_使用localhost进行浏览,显示apache网页,不显示文件目录-程序员宅基地

文章浏览阅读7.7k次。缺省情况下如果你的测试环境下在浏览器输入地址:http://localhost/如果你的文件根目录里有 index.html,index.php,浏览器就会显示 index.html的内容,如果没有 index.html,浏览器就会显示文件根目录的目录列表,目录列表包括文件根目录下的文件和子目录。同样你输入一个虚拟目录的地址:http://localhost/b/如_使用localhost进行浏览,显示apache网页,不显示文件目录

推荐文章

热门文章

相关标签