欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于遗传算法解决旅行商问题(Python代码)

程序员文章站 2022-03-15 15:00:07
大家好!本文为大家提供了遗传算法解决TSP问题的一种python实现。...

大家好!本文为大家提供了遗传算法解决TSP问题的一种python实现。有兴趣的同学可以通过“蚁群算法解决TSP问题”,看看蚁群算法与遗传算法的不同之处。

import math
import numpy as np
import matplotlib.pyplot as plt

# 随机生成城市信息
nCity = 10
City = np.random.uniform(-10, 10, [nCity, 2])
Dis = {}
for i in range(nCity):
    for j in range(nCity):
        if i > j:
            dis = ((City[i][0] - City[j][0]) ** 2 + (City[i][1] - City[j][1]) ** 2) ** 0.5
            Dis[(i, j)] = dis
            Dis[(j, i)] = dis

Data_BestFit =[]   #用于保存每一代蚂蚁的最优适应度

#适应度计算函数 适应值 = 1 / 路径距离
def Cal_Fit(X):
    total_dis = Dis[(X[-1],X[0])]
    for i in range(nCity-1):
        total_dis += Dis[(X[i],X[i+1])]
    return 1 / total_dis

def GA_TSP():
    # 定义基本参数
    nPop = 100  # 种群大小
    Maxit = 100 # 最大迭代次数
    Pm = 0.15   # 变异概率
    Pc = 0.7    # 交叉概率

    #种群初始化
    X = [list(np.random.permutation(nCity)) for i in range(nPop)]
    Fit = np.zeros([nPop])
    Best_X = None
    Best_Fit = -math.inf
    for i in range(nPop):
        Fit[i] = Cal_Fit(X[i])
        if Fit[i] > Best_Fit:
            Best_Fit = Fit[i]
            Best_X = X[i].copy()

    #迭代求解
    for j in range(Maxit):
        # 变异-在一个解中随机选取两座不同的城市交换遍历顺序
        for k in range(nPop):
            if np.random.random() < Pm:
                point1 = int(np.random.random() * nCity)
                point2 = int(np.random.random() * nCity)
                while point1 == point2:
                    point1 = int(np.random.random() * nCity)
                    point2 = int(np.random.random() * nCity)
                X[k][point1],X[k][point2] = X[k][point2],X[k][point1]
                
        #交叉-交换解的部分序列
        k = 0
        while k < nPop:
            if np.random.random() < Pc:
                point = int(np.random.random() * nCity)
                x1 = X[k][0:point+1]
                x2 = X[k][point+1:nCity]
                x2.extend(x1)
                X[k] = x2
            k += 1

        #选择 以适应度占比为概率选取下一代个体(有的个体会被重复选取)
        for i in range(nPop):
            Fit[i] = Cal_Fit(X[i])
            if Fit[i] > Best_Fit:
                Best_Fit = Fit[i]
                Best_X = X[i].copy()
        fit = Fit.copy()
        P = fit / sum(fit)
        swarm = np.random.choice(range(nPop),size = nPop,replace=True,p = P)
        x = X.copy()
        for k in range(nPop):
            X[k] = x[swarm[k]]

        Data_BestFit.append(Best_Fit)

    return Best_X ,Best_Fit

# 绘制路径与迭代曲线
def Draw_City(City, X ,Best_Fit):
    X = list(X)
    X.append(X[0])
    coor_x = []
    coor_y = []
    for i in X:
        i = int(i)
        coor_x.append(City[i][0])
        coor_y.append(City[i][1])

    plt.plot(coor_x, coor_y, 'r-o')
    plt.title('TSP with Genetic Algorithm\n'+'total_dis = '+str(round(Best_Fit,3)))
    plt.show()

    plt.plot(range(len(Data_BestFit)), Data_BestFit)
    plt.title('Iteration_BestFit')
    plt.xlabel('iteration')
    plt.ylabel('fitness')
    plt.show()

if __name__ == '__main__':
    Best_X, Best_Fit = GA_TSP()
    Draw_City(City ,Best_X ,(Best_Fit)**-1)


本文地址:https://blog.csdn.net/qq_44936034/article/details/112686431