遗传算法解决旅行商问题

这篇具有很好参考价值的文章主要介绍了遗传算法解决旅行商问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、问题描述
旅行商问题(Travelling Salesman Problem, 简记TSP,亦称货郎担问题):设有n个城市和距离矩阵D=[dij],其中dij表示城市i到城市j的距离,i,j=1,2 … n,则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。
初始问题图像如下:
遗传算法解决旅行商问题,随笔,python,算法,人工智能
近似理想结果图像如下:
遗传算法解决旅行商问题,随笔,python,算法,人工智能
二、算法设计
2.1 GA遗传算法
遗传算法(GeneticAlgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,通过模拟自然进化过程搜索最优解。遗传算法首先初始化一个种群,然后根据适应性函数确定个体的适应度,由适应度来选择父代个体进行交叉产生子代种群,再以某种概率让后代个体进行变异,从而不断选出适应度高的个体,进而更新种群,最终得到近似最优解情况。
2.2 算法伪代码
—————————————————————————————————
Algorithm 1 算法伪代码
—————————————————————————————————
function GA_TSP
  确定种群规模M,迭代次数T,变异概率Pm,源点,交叉概率Pc等
  产生初始种群(初始化路径城市序列)
  while t<T
    计算个体适应度
    选择高适应度个体作为父代
    交叉产生子代种群
    变异得到新子代种群
    更新种群得到新一代群体
  end while
  输出适应度最高的个体
end function
—————————————————————————————————
三、程序代码

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import math
import random
#读取城市数据
def read_data():
    data = pd.read_csv('city.csv')
    city_name = data['city'].values
    city_position_x = data['x'].values
    city_position_y = data['y'].values
    #原始问题图
    plt.scatter(city_position_x, city_position_y)
    for i in range(len(city_position_x)):
        plt.annotate(city_name[i], xy=(city_position_x[i], city_position_y[i]), xytext=(city_position_x[i] + 0.1, city_position_y[i] + 0.1))  # xy是需要标记的坐标,xytext是对应的标签坐标
    plt.show()
    return city_name, city_position_x, city_position_y
#计算不同城市间距离矩阵
def distances(city_name, city_position_x, city_position_y):
    global city_count, city_distance
    #城市总数量
    city_count = len(city_name)
    #城市距离矩阵初始化
    city_distance = np.zeros([city_count, city_count])
    for i in range(city_count):
        for j in range(city_count):
            city_distance[i][j] = math.sqrt((city_position_x[i] - city_position_x[j]) ** 2 + (city_position_y[i] - city_position_y[j]) ** 2)
    return city_count, city_distance
#计算一条路径的总长度
def path_length(path,origin):#具体路径,出发源点
    distance = 0
    distance += city_distance[origin][path[0]]
    for i in range(len(path)):
        if i == len(path) - 1:
            distance += city_distance[origin][path[i]]
        else:
            distance += city_distance[path[i]][path[i + 1]]
    return distance
#改良
def improve(path,improve_count,origin):#具体路径,改良迭代次数
    distance = path_length(path,origin)
    for i in range(improve_count): 
        #随机选择两个城市
        u = random.randint(0, len(path) - 1)
        v = random.randint(0, len(path) - 1)
        if u != v:
            new_path = path.copy()
            t = new_path[u]
            new_path[u] = new_path[v]
            new_path[v] = t
            new_distance = path_length(new_path,origin)
            if new_distance < distance:  # 保留更优解
                distance = new_distance
                path = new_path.copy()
    return path
#环境选择父代种群
def selection(population, retain_rate, live_rate,origin):#种群,适者比例, 生命强度
    # 对总距离进行从小到大排序
    graded = [[path_length(path,origin), path] for path in population]
    graded = [path[1] for path in sorted(graded)]
    # 选出适应性强的染色体
    retain_length = int(len(graded) * retain_rate)
    parents = graded[: retain_length]   # 保留适应性强的染色体
    #保留一定存活程度强的个体
    for weak in graded[retain_length:]:
        if random.random() < live_rate:
            parents.append(weak)
    return parents
#使用常规匹配交叉获得子代
#随机选取一个交配位,子代1交配位之前的基因选自父代1交配位之前,交配位之后按父代2顺序选择没有在子代1中出现的基因
#子代2交配位之前的基因选自父代2交配位之前,交配位之后按父代1顺序选择没有在子代2中出现的基因
def crossover(parents,population_num):#存活的父代种群,种群总数
    # 生成子代的个数
    children_count = population_num - len(parents)
    # 孩子列表
    children = []
    while len(children) < children_count:
        # 在父母种群中随机选择父母
        male_index = random.randint(0, len(parents) - 1)
        female_index = random.randint(0, len(parents) - 1)
        if male_index != female_index:
            male = parents[male_index]
            female = parents[female_index]
            position = random.randint(0, len(male) - 1) #随机产生一个交配位
            child1 = male[:position]
            child2 = female[:position]
            for i in female:
                if i not in child1:
                    child1.append(i)
            for i in male:
                if i not in child2:
                    child2.append(i)
            children.append(child1)
            children.append(child2)
return children
#变异:随机交换路径中两个城市位置
def mutation(children,mutation_rate):#孩子种群,变异率
    for i in range(len(children)):
        if random.random() < mutation_rate:  # 变异
            child = children[i]
            u = random.randint(0, len(child) - 2)
            v = random.randint(u + 1, len(child) - 1)
            tmp = child[u]
            child[u] = child[v]
            child[v] = tmp
            children[i]=child
    return children
#得到当前代种群最优个体
def get_result(population,origin):
    graded = [[path_length(path,origin), path] for path in population]
    graded = sorted(graded)
    return graded[0][0], graded[0][1]  # 返回种群的最优解
#结果可视化
def plt_magin(iters,distance,result_path,origin,city_name,city_position_x,city_position_y):
    print("进化次数为",iters,"时的最佳路径长度为:", distance)
    result_path = [origin] + result_path + [origin]
#     print("最佳路线为:")
#     for i, index in enumerate(result_path):
#         print(city_name[index] + "(" + str(index) + ")", end=' ')
#         if i % 9 == 0:
#             print()
    X = []
    Y = []
    for i in result_path:
        X.append(city_position_x[i])
        Y.append(city_position_y[i])

    plt.figure()
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 用来正常显示中文标签
    plt.plot(X, Y, '-o')
    plt.xlabel('经度')
    plt.ylabel('纬度')
    plt.title("GA_TSP")
    for i in range(len(X)):
        plt.annotate(city_name[result_path[i]], xy=(X[i], Y[i]), xytext=(X[i] + 0.1, Y[i] + 0.1))  # xy是需要标记的坐标,xytext是对应的标签坐标
    plt.show()
#遗传算法总流程
def GA_TSP(origin,population_num,improve_count,iter_count,retain_rate,live_rate,mutation_rate):
    #源点,种群个体数,改良迭代数,进化次数,适者概率,生命强度,变异率
    city_name, city_position_x, city_position_y = read_data()
    city_count, city_distance = distances(city_name, city_position_x, city_position_y)
    list = [i for i in range(city_count)]
    list.remove(origin)
    population = []
    for i in range(population_num):
        # 随机生成个体
        path = list.copy()
        random.shuffle(path)#随机打乱
        path = improve(path,improve_count,origin)#使用改良方案尽量提高初始化种群多样性
        population.append(path)
    every_gen_best = []  # 存储每一代最好的
    distance, result_path = get_result(population,origin)
    for i in range(iter_count):
        # 选择繁殖个体群
        parents = selection(population, retain_rate, live_rate,origin)
        # 交叉繁殖
        children = crossover(parents,population_num)
        # 变异
        children = mutation(children,mutation_rate)
        # 更新种群,采用杰出选择
        population = parents + children
        distance, result_path = get_result(population,origin)
        every_gen_best.append(distance)
        if(i%500==0):
            plt_magin(i,distance,result_path,origin,city_name,city_position_x,city_position_y)
    plt_magin(i,distance,result_path,origin,city_name,city_position_x,city_position_y)
    plt.plot(range(len(every_gen_best)), every_gen_best)
    plt.show()
 
if __name__ == '__main__':
    GA_TSP(10,300,200,10000,0.3,0.5,0.01)#源点,种群个数,改良次数,进化次数,适者概率,生命强度,变异率

四、结果展示
城市个数为中国省会城市为34个,种群大小选择300,选择0.3比例的作为精英个体保留,并将其作为父代个体交叉变异产生子代种群,在变异概率为0.01的情况下,最佳路径长度随迭代次数的变化情况如下图所示:
遗传算法解决旅行商问题,随笔,python,算法,人工智能
迭代次数为500,1000,2000,6000时路线情况如下图所示:
遗传算法解决旅行商问题,随笔,python,算法,人工智能
遗传算法解决旅行商问题,随笔,python,算法,人工智能
遗传算法解决旅行商问题,随笔,python,算法,人工智能
遗传算法解决旅行商问题,随笔,python,算法,人工智能
遗传算法解决旅行商问题,随笔,python,算法,人工智能
城市信息如下:
遗传算法解决旅行商问题,随笔,python,算法,人工智能文章来源地址https://www.toymoban.com/news/detail-721893.html

到了这里,关于遗传算法解决旅行商问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 人工智能原理实验4(1)——遗传算法、蚁群算法求解TSP问题

    TSP问题是组合数学中一个古老而又困难的问题,也是一个典型的组合优化问题,现已归入NP完备问题类。NP问题用穷举法不能在有效时间内求解,所以只能使用启发式搜索。遗传算法是求解此类问题比较实用、有效的方法之一。下面给出30个城市的位置信息: 应用遗传算法和蚁

    2024年01月24日
    浏览(59)
  • 旅行商问题 python 不同算法实现

    一个网络上的最优路线问题,它寻求货郎走过网络上的所有点的路线最短。 定义: 输入 : 有穷个城市的集合 C = { c 1 , c 2 , . . . , c n } , 距 离 d ( c i , c j ) = d ( c j , c i ) ∈ Z + , 1 ≤ i j ≤ n C={c_1,c_2,...,c_n},距离d(c_i,c_j)=d(c_j,c_i)in Z^+,1 le i j le n C = { c 1 ​ , c 2 ​ , . . . , c n ​

    2024年02月06日
    浏览(35)
  • 基于遗传算法解决流水车间调度问题

    问题描述 n 个工件要在 m 台机器上加工,每个工件需要经过 m 道工序,每道工序要求不同的机器,n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的,设为 t i j ( i = 1.... , n ; j = 1 , . . . , m ) t_{ij}(i = 1....,n; j = 1,...,m) t ij ​ ( i = 1.... , n ; j = 1 , ... , m ) 问

    2024年02月07日
    浏览(44)
  • 【Python】人工智能-机器学习——不调库手撕演化算法解决函数最小值问题

    现在有一个函数 3 − s i n 2 ( j x 1 ) − s i n 2 ( j x 2 ) 3-sin^2(jx_1)-sin^2(jx_2) 3 − s i n 2 ( j x 1 ​ ) − s i n 2 ( j x 2 ​ ) ,有两个变量 x 1 x_1 x 1 ​ 和 x 2 x_2 x 2 ​ ,它们的定义域为 x 1 , x 2 ∈ [ 0 , 6 ] x_1,x_2in[0,6] x 1 ​ , x 2 ​ ∈ [ 0 , 6 ] ,并且 j = 2 j=2 j = 2 ,对于此例,所致对于 j =

    2024年01月20日
    浏览(76)
  • 路径规划问题的遗传算法实现(python代码)

        遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。     路径

    2024年02月04日
    浏览(46)
  • 遗传算法GA解决混合流水车间调度问题HFSP

    混合流水车间调度问题(HFSP)是传统流水车间调度问题(FSP)的拓展,本文针对HFSP问题进行描述、建模和求解。 通常模型做如下假设: HFSP符号描述: 决策变量: 主要约束: 优化目标: 本节使用带精英保留的遗传算法GA对HFSP问题进行求解。求解结果如下: 自定义算例如下:

    2024年02月11日
    浏览(50)
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」

    提示:上篇已经讲过了旅行商问题的QUBO建模,这里直接讲两种编程实现: 看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始点的。所以,下面👇的目标函数里,循环进行到 N N N 时,最后一个 x j , t + 1 x_{j,t+1} x j , t + 1 ​ 应该确定回到初始点的。 针对这

    2023年04月14日
    浏览(39)
  • 基于Python实现的遗传算法求最值问题

    遗传算法求最值问题 目录 人工智能第三次实验报告 1 遗传算法求最值问题 1 一 、遗传算法 1 1.1 遗传算法简介 1 1.2 遗传算法基本要素 2 4. 设定遗传操作: 2 1.3 遗传算法一般步骤 2 二 、程序说明 2 2.1 控制参数 2 2.2 编码规则 3 2.3 选择初始群体 3 2.4 适应度函数 4 三 、参数测试

    2023年04月25日
    浏览(37)
  • 【人工智能】遗传算法

    可以把遗传算法类比成一个游戏,我们需要通过这个游戏来找到最佳的解决方案。 首先,我们需要创建一些角色(也就是种群),每个角色有自己的装备和技能(染色体),但是我们并不知道哪个角色更加强大。 然后,我们让这些角色相互竞争,通过升级、打怪等方式来获

    2024年02月02日
    浏览(48)
  • 遗传算法求解车辆路径优化问题VRP(Python代码实现)

    学会了前面两篇遗传算法,但是那都是针对抽象的数学问题求解的,那么应用到现实中的实际问题中,我们又该怎样把遗传算法套进去呢,然后我第一个接触到的问题就是车辆路径优化问题VRP,当然也是找到了一篇比较好的文章,物流管理论文实现:基于遗传算法的带时间窗

    2024年01月18日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包