一、問(wèn)題描述
旅行商問(wèn)題（Travelling Salesman Problem, 簡(jiǎn)記TSP，亦稱貨郎擔(dān)問(wèn)題)：設(shè)有n個(gè)城市和距離矩陣D=[dij]，其中dij表示城市i到城市j的距離，i，j=1，2 … n，則問(wèn)題是要找出遍訪每個(gè)城市恰好一次的一條回路并使其路徑長(zhǎng)度為最短。
初始問(wèn)題圖像如下：

近似理想結(jié)果圖像如下：

二、算法設(shè)計(jì)
2.1 GA遺傳算法
遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解。遺傳算法首先初始化一個(gè)種群，然后根據(jù)適應(yīng)性函數(shù)確定個(gè)體的適應(yīng)度，由適應(yīng)度來(lái)選擇父代個(gè)體進(jìn)行交叉產(chǎn)生子代種群，再以某種概率讓后代個(gè)體進(jìn)行變異，從而不斷選出適應(yīng)度高的個(gè)體，進(jìn)而更新種群，最終得到近似最優(yōu)解情況。
2.2 算法偽代碼
—————————————————————————————————
Algorithm 1 算法偽代碼
—————————————————————————————————
function GA_TSP
??確定種群規(guī)模M，迭代次數(shù)T，變異概率Pm，源點(diǎn)，交叉概率Pc等
??產(chǎn)生初始種群（初始化路徑城市序列）
??while t<T
????計(jì)算個(gè)體適應(yīng)度
????選擇高適應(yīng)度個(gè)體作為父代
????交叉產(chǎn)生子代種群
????變異得到新子代種群
????更新種群得到新一代群體
??end while
??輸出適應(yīng)度最高的個(gè)體
end function
—————————————————————————————————
三、程序代碼

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import math
import random
#讀取城市數(shù)據(jù)
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
    #原始問(wèn)題圖
    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是需要標(biāo)記的坐標(biāo)，xytext是對(duì)應(yīng)的標(biāo)簽坐標(biāo)
    plt.show()
    return city_name, city_position_x, city_position_y
#計(jì)算不同城市間距離矩陣
def distances(city_name, city_position_x, city_position_y):
    global city_count, city_distance
    #城市總數(shù)量
    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
#計(jì)算一條路徑的總長(zhǎng)度
def path_length(path,origin):#具體路徑，出發(fā)源點(diǎn)
    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):#具體路徑，改良迭代次數(shù)
    distance = path_length(path,origin)
    for i in range(improve_count): 
        #隨機(jī)選擇兩個(gè)城市
        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:  # 保留更優(yōu)解
                distance = new_distance
                path = new_path.copy()
    return path
#環(huán)境選擇父代種群
def selection(population, retain_rate, live_rate,origin):#種群，適者比例, 生命強(qiáng)度
    # 對(duì)總距離進(jìn)行從小到大排序
    graded = [[path_length(path,origin), path] for path in population]
    graded = [path[1] for path in sorted(graded)]
    # 選出適應(yīng)性強(qiáng)的染色體
    retain_length = int(len(graded) * retain_rate)
    parents = graded[: retain_length]   # 保留適應(yīng)性強(qiáng)的染色體
    #保留一定存活程度強(qiáng)的個(gè)體
    for weak in graded[retain_length:]:
        if random.random() < live_rate:
            parents.append(weak)
    return parents
#使用常規(guī)匹配交叉獲得子代
#隨機(jī)選取一個(gè)交配位，子代1交配位之前的基因選自父代1交配位之前，交配位之后按父代2順序選擇沒(méi)有在子代1中出現(xiàn)的基因
#子代2交配位之前的基因選自父代2交配位之前，交配位之后按父代1順序選擇沒(méi)有在子代2中出現(xiàn)的基因
def crossover(parents,population_num):#存活的父代種群，種群總數(shù)
    # 生成子代的個(gè)數(shù)
    children_count = population_num - len(parents)
    # 孩子列表
    children = []
    while len(children) < children_count:
        # 在父母種群中隨機(jī)選擇父母
        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) #隨機(jī)產(chǎn)生一個(gè)交配位
            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
#變異：隨機(jī)交換路徑中兩個(gè)城市位置
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
#得到當(dāng)前代種群最優(yōu)個(gè)體
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]  # 返回種群的最優(yōu)解
#結(jié)果可視化
def plt_magin(iters,distance,result_path,origin,city_name,city_position_x,city_position_y):
    print("進(jìn)化次數(shù)為",iters,"時(shí)的最佳路徑長(zhǎng)度為：", 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']  # 用來(lái)正常顯示中文標(biāo)簽
    plt.plot(X, Y, '-o')
    plt.xlabel('經(jīng)度')
    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是需要標(biāo)記的坐標(biāo)，xytext是對(duì)應(yīng)的標(biāo)簽坐標(biāo)
    plt.show()
#遺傳算法總流程
def GA_TSP(origin,population_num,improve_count,iter_count,retain_rate,live_rate,mutation_rate):
    #源點(diǎn)，種群個(gè)體數(shù)，改良迭代數(shù),進(jìn)化次數(shù)，適者概率，生命強(qiáng)度，變異率
    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):
        # 隨機(jī)生成個(gè)體
        path = list.copy()
        random.shuffle(path)#隨機(jī)打亂
        path = improve(path,improve_count,origin)#使用改良方案盡量提高初始化種群多樣性
        population.append(path)
    every_gen_best = []  # 存儲(chǔ)每一代最好的
    distance, result_path = get_result(population,origin)
    for i in range(iter_count):
        # 選擇繁殖個(gè)體群
        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)#源點(diǎn)，種群個(gè)數(shù)，改良次數(shù)，進(jìn)化次數(shù)，適者概率，生命強(qiáng)度，變異率

四、結(jié)果展示
城市個(gè)數(shù)為中國(guó)省會(huì)城市為34個(gè)，種群大小選擇300，選擇0.3比例的作為精英個(gè)體保留，并將其作為父代個(gè)體交叉變異產(chǎn)生子代種群，在變異概率為0.01的情況下，最佳路徑長(zhǎng)度隨迭代次數(shù)的變化情況如下圖所示：

迭代次數(shù)為500，1000，2000，6000時(shí)路線情況如下圖所示：





城市信息如下：
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-721893.html

到了這里，關(guān)于遺傳算法解決旅行商問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！