dtcms 源码 Springboot HashMap mysql安装 云计算架构 macos jsf iis audio hyperlink angular ui router 品优购电商系统开发 jquery延时 鼠标失去焦点事件 hbase集群搭建 android入门实例 matlab网页版 完全去vm去虚拟化工具 SketchUp python基础教程免费 python正则表达式语法 java正则表达式 java案例 java入门新手教程 java类型 php项目实例 python视频教程 python下载教程 内存整理软件 免费脚本 福昕阅读器绿色版 小工具 千千静听老版本 自动答题软件 证书小精灵 游戏linux正则表达式 ios12录屏 360越狱版 pp安卓助手 php完全自学手册
当前位置: 首页 > 学习教程  > 编程语言

【启发式算法】Python实现遗传算法求解TSP问题

2020/8/31 13:03:38 文章标签:

遗传算法

算法相关参数

  • 种群个体数量p_num
  • 进化代数gen
  • 变异率pm

算法效果分析

  1. 种群数量越多,迭代次数越多,搜索次数越多,程序运行越慢,相对来 得到的解更可信
  2. 种群中个体的路径长度越短,被选中作为父代的概率越大,即优胜劣汰
  3. 算法随机性体现在:父代的随机选取,孩子继承父母的基因序列长度随机,一定概率进行变异,变异中随机选取基因进行交换

算法步骤

  1. 数据初始化:计算距离矩阵(dist[i][j]表示i城市与j城市之间的距离);随机得到初始解(起点为0城市);编写距离计算函数;初始化第一代的种群
  2. 求得当前代时种群中的最优解,并初始化子代矩阵
  3. 遗传算法的核心:算法迭代gen次,每次产生p_num个子代。
    3.1 随机选择一对父母(路径越短,选中的概率越大),并选取父母各自一段基因序列进行遗传(基因即路径,长度随机生成);
    3.2 第一个孩子继承母亲的部分基因序列
    3.3 随机生成概率,判断是否变异
    3.4 将孩子基因放入孩子序列,孩子的数量+1
    3.5 同理第二个孩子继承父亲的基因(见3.2~3.4)
    3.6 计算过所有p_num个子代后,找出当前代的最优解并与全局最优解比较
  4. 直到迭代gen次,算法结束
# -*- coding: utf-8 -*-
import numpy as np
import random
import math
import matplotlib.pyplot as plt
import time

"""
Desicribe:遗传算法解TSP问题

"""

# 解决中文显示问题
plt.rcParams['font.sans-serif'] = ['KaiTi'] # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题

# 原始数据
coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],
                        [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],
                        [1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],
                        [725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
                        [300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],
                        [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],
                        [420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],
                        [685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],
                        [475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],
                        [830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],
                        [1340.0, 725.0], [1740.0, 245.0]])
gl_num = coordinates.shape[0]  # 城市数目
coord_x = coordinates[:, 0]  # 城市横坐标
coord_y = coordinates[:, 1]  # 城市纵坐标
gl_dist = np.zeros((gl_num, gl_num))  # 距离矩阵
gl_route_origin = np.zeros(gl_num)  # 初始解
gl_sumDist_origin = 0.0  # 初始距离
# 遗传算法参数
p_num = 200  # 种群个体数量
gen = 2000  # 进化代数
pm = 0.1  # 变异率


def init():
    """
    初始化解,初始距离和距离矩阵
    :return:
    """
    global gl_dist
    global gl_route_origin
    global gl_sumDist_origin
    global gl_num
    for i in range(gl_num):
        x_i = coord_x[i]
        y_i = coord_y[i]
        for j in range(i, gl_num):
            x_j = coord_x[j]
            y_j = coord_y[j]
            gl_dist[i][j] = gl_dist[j][i] = math.sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
    # 随机列表  固定起点终点,起点终点均为0
    gl_route_origin = list(range(0, gl_num))
    gl_route_origin = shuffle(gl_route_origin)
    gl_sumDist_origin = getDist(gl_route_origin)
    gl_num = len(gl_route_origin)
    print("路径上城市数:", gl_num)



def getDist(route):
    """
    计算距离,注意计算返回起点的路径长度
    :param route: 传递路径
    :return: 距离
    """
    dist = 0.0
    for i in range(0, gl_num - 1):
        dist += gl_dist[route[i]][route[i + 1]]
    dist += gl_dist[route[gl_num - 1]][0]
    return dist


def shuffle(my_list):
    """
    对可行解进行排列组合,除去起点
    :param my_list: 可行解
    :return:
    """
    temp_list = my_list[1:]  # 数据切片,左闭右开,获取除起点以外的所有元素
    np.random.shuffle(temp_list)
    shuffle_list = my_list[:1] + temp_list   # 切片的拼接
    return shuffle_list


def path_len_probability(my_list):
    """
    求解当前代中的最优解和概率
    :param my_list:种群
    :return:my_list[gen_best_length_index]当前种群中的最优路径
            gen_best_length当前种群中的最优解(最短距离)
            path_len_pro_list路径_距离_概率的集合
    """
    len_list = []  # 路径解长度列表
    pro_list = []  # 概率列表
    path_len_pro_list = []  # 路径_距离_概率
    for path in my_list:
        len_list.append(getDist(path))  # 对每个路径解求长度
    max_len = max(len_list) + 1e-10  # 最长距离
    gen_best_length = min(len_list)  # 最短距离,即当前最优解
    gen_best_length_index = len_list.index(gen_best_length)  # 最优解下标索引位置
    mask_list = np.ones(p_num) * max_len - np.array(len_list)  # 求解距离的最大值与当前距离之差
    sum_len = np.sum(mask_list)  # 对距离差值求和
    # print(gen_best_length)
    # print(gen_best_length_index)
    # print(sum_len)

    # 计算概率值(轮盘赌法),概率值的标准是路径距离越短,被选中的概率越高,即择优
    for i in range(p_num):
        if i == 0:  # 第一个概率
            pro_list.append(mask_list[i] / sum_len)  # 差值i/差值之和,路径越短,计算出的比值越大
        elif i == p_num - 1:  # 最后一个概率
            pro_list.append(1)  # 概率为1
        else:  # 中间的概率
            pro_list.append(pro_list[i - 1] + mask_list[i] / sum_len)  # i-1的概率 + 差值i / 差值之和
    for i in  range(p_num):
        path_len_pro_list.append([my_list[i], len_list[i], pro_list[i]])
    return my_list[gen_best_length_index], gen_best_length, path_len_pro_list


def choose_cross(population):
    """
    以一定概率选取parents进行交配函数
    jump:随机跳跃值
    通过二分搜索,找到随机跳跃值所在的概率范围,并返回对应索引下标
    :param population:
    :return:
    """
    jump = np.random.random()  # 生成(0,1)之间的随机数
    if jump < population[0][2]:  # population[0]的概率最小
        return 0
    # 二分搜索,high,low代表个体种群的下标
    low = 1
    high = p_num
    mid = int((low + high) / 2)
    while low < high:
        if jump > population[mid][2]:
            low = mid
            mid = int((low + high) / 2)
        elif jump < population[mid - 1][2]:
            high = mid
            mid = int((low + high) / 2)
        else:
            return mid


def variation(my_list):
    """
    变异函数
    :param my_list:
    :return:
    """
    ver1 = np.random.randint(1, gl_num - 1)
    ver2 = np.random.randint(1, gl_num - 1)
    # 如果随机产生数相同,则再次进行随机取数
    while ver2 == ver1:
        ver2 = np.random.randint(1, gl_num - 1)
    my_list[ver1], my_list[ver2] = my_list[ver2], my_list[ver1]
    return my_list


if __name__ == '__main__':
    start = time.time()

    init()
    print("初始解:", gl_route_origin)
    print("初始距离:", gl_sumDist_origin)
    population = [0] * p_num  # 初始化种群矩阵
    # 建立初始第一代的种群
    population[0] = gl_route_origin
    for i in range(1, p_num):
        population[i] = shuffle(gl_route_origin)

    # 建立初始化种群获得的最优路径和最优路径长度,并初始化son
    gen_best, gen_best_length, population = path_len_probability(population)
    # print(population)  #这个列表的每一项中有三项,第一项是路径,第二项是长度,第三项是使用时转盘的概率
    son_list = [0] * p_num  # 初始化子代矩阵,子代规模与父代规模相同
    best_path = gen_best  # 最优路径初始化
    best_path_length = gen_best_length  # 最优路径长度

    # 记录每一代中的最优解,便于画图
    every_gen_best = list()  # every_gen_best = []会有波浪线
    every_gen_best.append(gen_best_length)

    # 迭代gen代
    for i in range(gen):
        son_num = 0
        while son_num < p_num:  # 产生p_num数量的子代,杂交变异
            # choose_cross随机选择一对父母(双亲的下标)进行交配
            father_index = choose_cross(population)
            mother_index = choose_cross(population)
            # 获取双亲的基因即路径
            father = population[father_index][0]
            mother = population[mother_index][0]

            # 父母变成下一代的父母(孩子继承父母的基因)
            son1 = father.copy()
            son2 = mother.copy()
            # 随机数据product_set表示双亲将哪些基因传给孩子
            product_set = np.random.randint(1, gl_num)  # 随机生成要遗传的基因序列的长度
            # 父亲中的某一段基因和母亲中的某一段基因
            father_cross_set = set(father[1:product_set])  # 除去起点
            mother_cross_set = set(mother[1:product_set])
            # 第一个son继承母亲的基因
            cross_complete = 1
            for j in range(1, gl_num - 1):
                if son1[j] in mother_cross_set:
                    son1[j] = mother[cross_complete]  # 母亲的基因遗传给孩子
                    cross_complete += 1
                    if cross_complete > product_set:  # 遗传的基因个数超过基因序列,则跳出循环
                        break
            # 第一个son基因变异
            if np.random.random() < pm:
                son1 = variation(son1)
            son_list[son_num] = son1
            son_num += 1
            if son_num == p_num:
                break

            # 第二个孩子继承父亲基因
            cross_complete = 1
            for j in range(1, gl_num - 1):
                if son2[j] in father_cross_set:
                    son2[j] = father[cross_complete]
                    cross_complete += 1
                    if cross_complete > product_set:
                        break
            # 第二个son基因变异
            if np.random.random() < pm:
                son2 = variation(son2)
            son_list[son_num] = son2
            son_num += 1
        # 找最优解,当前代的最优解与全局最优解进行比较
        gen_best, gen_best_length, population = path_len_probability(son_list)
        if gen_best_length < best_path_length:
            best_path = gen_best
            best_path_length = gen_best_length
        every_gen_best.append(gen_best_length)
    end = time.time()

    x = []
    y = []
    for point in best_path:
        x.append(coordinates[point][0])
        y.append(coordinates[point][1])
    print(gen_best)  # 最后一代最优路径
    print(gen_best_length)  # 最后一代最优路径长度
    print(best_path)  # 最优路径
    print(best_path_length)  # 最优路径长度
    # 绘图
    plt.figure(1)
    plt.subplots_adjust(hspace=0.4, wspace=0.4)
    plt.subplot(211)
    plt.title("每代最短路径")
    plt.plot(every_gen_best)
    plt.subplot(212)
    plt.title("最优路径")
    plt.scatter(x, y)
    plt.plot(x, y)
    plt.grid()
    plt.show()

    print('Running time: %s Seconds' % (end - start))

"""
[0, 21, 29, 22, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 36, 37, 33, 43, 45, 15, 28, 19, 49, 34, 35, 38, 39, 4, 5, 23, 47, 14, 3, 24, 42, 32, 50, 11, 10, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 21, 0]
10112.612313214102
[0, 21, 19, 49, 28, 29, 22, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 39, 36, 37, 23, 47, 45, 15, 43, 33, 34, 35, 38, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 21, 0]
9600.890171898773
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 37, 23, 47, 45, 43, 33, 34, 39, 36, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 6, 0]
9494.64650869738
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 36, 23, 47, 45, 43, 33, 34, 39, 37, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 6, 0]
9449.437077391805
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 36, 23, 47, 45, 43, 33, 34, 39, 37, 14, 4, 5, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 20, 0]
9416.094900698994
"""


本文链接: http://www.dtmao.cc/news_show_150042.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?