遺傳算法求解TSP

一、基本步驟

遺傳算法求解旅行商問題（TSP）的一般步驟如下：

  1. 編碼：

    • 通常采用整數編碼，將城市的訪問順序表示為一個染色體。例如，假設有 5 個城市，編碼為[1, 3, 5, 2, 4]，表示旅行商的訪問順序為城市 1、城市 3、城市 5、城市 2、城市 4，最后回到出發城市 1。

  2. 初始化種群：

    • 隨機生成一定數量的染色體，作為初始種群。

  3. 適應度評估：

    • 計算每個染色體所代表的路徑長度，路徑長度越短，適應度越高。適應度函數可以是路徑長度的倒數或其他與路徑長度相關的函數。

  4. 選擇操作：

    • 基于適應度，選擇一定比例的染色體進入下一代種群。常見的選擇方法有輪盤賭選擇、錦標賽選擇等。

  5. 交叉操作：

    • 對選中的染色體進行交叉，生成新的染色體。例如，單點交叉，隨機選擇一個交叉點，交換兩個染色體在交叉點之后的部分。

  6. 變異操作：

    • 以一定的概率對染色體中的基因進行變異，例如隨機交換兩個城市的位置。

  7. 重復步驟 3 - 6 ，直到滿足終止條件（如達到預定的迭代次數或找到滿意的解）。

通過不斷迭代，種群中的染色體逐漸優化，最終得到較優的 TSP 路徑。需要注意的是，遺傳算法的參數（如種群大小、交叉概率、變異概率等）需要根據具體問題進行調整和優化，以獲得更好的求解效果。

二、代碼

#!/usr/bin/env python
# coding: utf-8# In[32]:import numpy as np
import copy
import matplotlib
import matplotlib.pyplot as plt
from matplotlib.pyplot import MultipleLocator
import random# In[33]:#準備好距離矩陣
city_num = 5
city_dist_mat = np.zeros([city_num, city_num])
city_dist_mat[0][1] = city_dist_mat[1][0] = 1165
city_dist_mat[0][2] = city_dist_mat[2][0] = 1462
city_dist_mat[0][3] = city_dist_mat[3][0] = 3179
city_dist_mat[0][4] = city_dist_mat[4][0] = 1967
city_dist_mat[1][2] = city_dist_mat[2][1] = 1511
city_dist_mat[1][3] = city_dist_mat[3][1] = 1942
city_dist_mat[1][4] = city_dist_mat[4][1] = 2129
city_dist_mat[2][3] = city_dist_mat[3][2] = 2677
city_dist_mat[2][4] = city_dist_mat[4][2] = 1181
city_dist_mat[3][4] = city_dist_mat[4][3] = 2216
#標號說明
#list_city = ['0_北京', '1_西安', '2_上海', '3_昆明', '4_廣州']# In[34]:#1.定義個體類，包括基因（城市路線）和適應度
num_person_idx = 0
num_person = 0
dis_list = []
class Individual:def __init__(self, genes = None):global num_personglobal dis_listglobal num_person_idxnum_person_idx += 1if num_person_idx % 20 == 0:num_person += 1self.genes = genesif self.genes == None:genes = [0]*5temp = [0]*4temp = [i for i in range(1,city_num)]########################################################################random.shuffle(temp)genes[1:] = tempgenes[0] = 0self.genes = genesself.fitness = self.evaluate_fitness()else:self.fitness = float(self.evaluate_fitness())#2. #計算個體的適應度def evaluate_fitness(self):dis = 0for i in range(city_num - 1):dis += city_dist_mat[self.genes[i]][self.genes[i+1]]if i == city_num - 2:dis += city_dist_mat[self.genes[i + 1]][0]#回到0if num_person_idx % 20 == 0:dis_list.append(dis)return 1/dis# In[35]:def copy_list(old):new = []for element in old:new.append(element)return new
def sort_win_num(group):for i in range(len(group)):for j in range(len(group) - i - 1):
#             print('group[j].fitness_type', type(group[j].fitness))if group[j].fitness < group[j+1].fitness:temp = group[j]group[j] = group[j+1]group[j+1] = tempreturn group
#定義Ga類 
#3~5，交叉、變異、更新種群，全部在Ga類中實現
class Ga:#input_為城市間的距離矩陣def __init__(self, input_):#聲明一個全局變量global city_dist_matcity_dist_mat = input_#當代的最佳個體########################################此處做了更改#self.best = Noneself.best = Individual(None)
#         print("BBBBBBbest.fitness",self.best.fitness)#種群self.individual_list = []#每一代的最佳個體self.result_list = []#每一代個體對應的最佳適應度self.fitness_list = []#交叉,這里采用交叉變異def cross(self):new_gen = []#隨機選取一段，含有num_cross個數字（城市）num_cross = 3#后期可能需要調試的參數,考慮到實際問題里只有5個城市，所以認為3較為合適for i in range(0, len(self.individual_list) - 1, 2):parent_gen1 = copy_list(self.individual_list[i].genes)parent_gen2 = copy_list(self.individual_list[i+1].genes)
#             print("parent_gen1",parent_gen1)
#             print("parent_gen2",parent_gen2)     index1_1 = 0index1_2 = 0index2_1 = 0index2_2 = 0#定義一個下表列表index_list = [0]*3for i in range(city_num - 3):#就是2，即0，1index_list[i] = i + 1index1_1 = random.choice(index_list)index1_2 = index1_1 + 2index2_1 = random.choice(index_list)index2_2 = index2_1 + 2choice_list1 = parent_gen1[index1_1:index1_2 + 1]choice_list2 = parent_gen2[index2_1:index2_2 + 1]
#             print("choice_list1",choice_list1)
#             print("choice_list2",choice_list2)#利用這一段生成兩個子代,下面的賦值只是為了獲取長度，所以用哪個父代能可以#也可以直接用city_num直接代替son_gen1 = [0]*city_numson_gen2 = [0]*city_num
#             print('son_gen1_size = ',len(son_gen1))
#             print('son_gen2_size = ',len(son_gen2))
#             print("index1_1 == ",index1_1)
#             print("index1_2 == ",index1_2)
#             print("index2_1 == ",index2_1)
#             print("index2_2 == ",index2_2)#找到之后進行交叉，分別得到son_gen1,son_gen2#先把選中的段復制進去son_gen1[index1_1: index1_2 + 1] = choice_list1son_gen2[index2_1: index2_2 + 1] = choice_list2
#             print("now,  son_gen1 = ", son_gen1)
#             print("now,  son_gen2 = ", son_gen2)#然后左、右“查漏補缺”temp1 = choice_list1temp2 = choice_list2if index1_1 == 0:passelse: for i in range(index1_1):for j in range(city_num):#如果父代2里面的這個當初沒被選中，那就加入son_gene1if parent_gen2[j] not in choice_list1:son_gen1[i] = parent_gen2[j]#這個時候要擴增choice_list1, 這樣parent_gen2里面未被選中的元素才會一個個被遍歷到#1choice_list1.append(parent_gen2[j])#找到之后馬上break，防止被覆蓋breakchoice_list1 = temp1if index1_2 == city_num - 1:passelse:for i in range(index1_2 + 1, city_num):for j in range(city_num):if parent_gen2[j] not in choice_list1:son_gen1[i] = parent_gen2[j]#這個時候要擴增choice_list1, 這樣parent_gen2里面未被選中的元素才會一個個被遍歷到#2choice_list1.append(parent_gen2[j])#找到之后馬上break，防止被覆蓋break#son_gen2亦是如此if index2_1 == 0:passelse:for i in range(index2_1):for j in range(city_num):#如果父代1里面的這個當初沒被選中，那就加入son_gen2if parent_gen1[j] not in choice_list2:son_gen2[i] = parent_gen1[j]#這個時候要擴增choice_list2, 這樣parent_gen1里面未被選中的元素才會一個個被遍歷到#3choice_list2.append(parent_gen1[j])#找到之后馬上break，防止被覆蓋breakchoice_list2 = temp2if index2_2 == city_num - 1:passelse:for i in range(index2_2 + 1, city_num):for j in range(city_num):if parent_gen1[j] not in choice_list2:
#                             print("i == ", i)son_gen2[i] = parent_gen1[j]#這個時候要擴增choice_list2, 這樣parent_gen1里面未被選中的元素才會一個個被遍歷到#4choice_list2.append(parent_gen1[j])#找到之后馬上break，防止被覆蓋break#新生成的子代基因加入new_gene列表
#             print('son_gen1 = ',son_gen1)
#             print('son_gen2 = ',son_gen2)new_gen.append(Individual(son_gen1))#print('new_gen[-1].genes', new_gen[-1].genes)new_gen.append(Individual(son_gen2))return new_gen#變異def mutate(self, new_gen):mutate_p = 0.02#待調參數index_list = [0]*(city_num-1)index_1 = 1index_2 = 1for i in range(city_num - 1):index_list[i] = i + 1for individual in new_gen:if random.random() < mutate_p:
#                 change += 1#如果變異，采用基于位置的變異,方便起見，直接使用上面定義的index列表index_l = random.choice(index_list)
#                 index_2 = (index_1 + 2) % city_num#這里讓間隔為2的兩個城市進行交換index_2 = random.choice(index_list)while index_1 == index_2:index_2 = random.choice(index_list)#交換temp = individual.genes[index_1]individual.genes[index_1] = individual.genes[index_2]individual.genes[index_2] = temp#變異結束，與老一代的進行合并self.individual_list += new_gen#選擇def select(self):#在此選用輪盤賭算法#考慮到5的階乘是120，所以可供選擇的個體基數應該適當大一些，#在此每次從種群中選擇6個，進行輪盤賭，初始化60個個體，同時適當調高變異的概率select_num = 6select_list = []for i in range(select_num):gambler = random.choice(self.individual_list)gambler = Individual(gambler.genes)select_list.append(gambler)#求出這些fitness之和sum = 0for i in range(select_num):sum += select_list[i].fitnesssum_m = [0]*select_num#實現概率累加for i in range(select_num):for j in range(i+1):sum_m[i] += select_list[j].fitnesssum_m[i] /= sumnew_select_list = []p_num = 0#隨機數for i in range(select_num):p_num = random.uniform(0,1)if p_num>0 and p_num < sum_m[0]:new_select_list.append(select_list[0])elif p_num>= sum_m[0] and p_num < sum_m[1]:new_select_list.append(select_list[1])elif p_num >= sum_m[1] and p_num < sum_m[2]:new_select_list.append(select_list[2])elif p_num >= sum_m[2] and p_num < sum_m[3]:new_select_list.append(select_list[3])elif p_num >= sum_m[3] and p_num < sum_m[4]:new_select_list.append(select_list[4])elif p_num >= sum_m[4] and p_num < sum_m[5]:new_select_list.append(select_list[5])else:pass#將新生成的一代替代父代種群self.individual_list = new_select_list#更新種群def next_gen(self):#交叉new_gene = self.cross()#變異self.mutate(new_gene)#選擇self.select()#獲得這一代的最佳個體
#         print("**************************************")
#         print('self.best.fitness = ', self.best.fitness)
#         print('now, best.fitness = ', self.best.fitness)for individual in self.individual_list:if individual.fitness > self.best.fitness:self.best = individual
#                 print("更換了最優路徑")
#                 print('now, best.fitness = ', self.best.fitness)def train(self):#隨機出初代種群#individual_num = 60self.individual_list = [Individual() for _ in range(individual_num)]#迭代gen_num = 100for i in range(gen_num):#從當代種群中交叉、變異、選擇出適應度最佳的個體，獲得子代產生新的種群self.next_gen()#連接首位
#             print("i = ", i)result = copy.deepcopy(self.best.genes)result.append(result[0])self.result_list.append(result)self.fitness_list.append(self.best.fitness)print(self.result_list[-1])print('距離總和是：', 1/self.fitness_list[-1])
#         return self.result_list, self.fitness_listdef draw(self):x_list = [i for i in range(num_person)]y_list = dis_listplt.rcParams['figure.figsize'] = (60, 45)plt.plot(x_list, y_list, color = 'g')plt.xlabel('Cycles',size = 50)plt.ylabel('Route',size = 50)x = np.arange(0, 910, 20)y = np.arange(7800, 12000, 100)plt.xticks(x)plt.yticks(y)plt.title('Trends in distance changes', size = 50)plt.tick_params(labelsize=30)
#         plt.savefig("D:\AI_pictures\遺傳算法求解TSP問題_1_輪盤賭算法")plt.show()
route = Ga(city_dist_mat)
route.train()
route.draw()

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/41639.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/41639.shtml
英文地址，請注明出處：http://en.pswp.cn/web/41639.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Leetcode3195. 包含所有 1 的最小矩形面積 I

Leetcode3195. 包含所有 1 的最小矩形面積 I

Every day a Leetcode 題目來源&#xff1a;3195. 包含所有 1 的最小矩形面積 I 解法1&#xff1a;遍歷 設最左、最右、最上、最下的 1 的行號/列號分別為 left、right、top、bottom&#xff0c;則答案為&#xff1a;(right - left 1) * (bottom - top 1)。 代碼&#xf…
閱讀更多...
新手教學系列——kswapd0 CPU占用100%問題解析與解決

新手教學系列——kswapd0 CPU占用100%問題解析與解決

在日常運維中，我們常會遇到一些疑難雜癥，其中kswapd0進程CPU占用100%就是一個常見的問題。通常情況下，這個問題是因為內存耗盡，需要使用到swap空間，可以通過調整swap大小或使用比例來控制磁盤讀寫。然而，今天我要分享的是一個特例，如何在內存并未耗盡且swap使用比例正常…
閱讀更多...
【STM32項目】基于Stm32搞怪盒子的設計（完整工程資料）

【STM32項目】基于Stm32搞怪盒子的設計（完整工程資料）

基于stm32搞怪的盒子設計 前言&#xff1a; 最近我看到一個極具創意的搞怪盒子&#xff0c;設計得相當有意思。作為一個熱衷于電子DIY的狂熱愛好者&#xff0c;怎能錯過這樣一個有趣的項目呢&#xff1f;于是&#xff0c;我決定親自動手&#xff0c;設計一個屬于自己的、獨一無…
閱讀更多...
C語言中關鍵字

C語言中關鍵字

C語言中的關鍵字共有32個&#xff0c;這些關鍵字根據其功能可以劃分為以下幾類&#xff1a; 1. 數據類型關鍵字&#xff08;12個&#xff09; char&#xff1a;聲明字符型變量或函數&#xff0c;通常占用1個字節。double&#xff1a;聲明雙精度浮點數變量或函數&#xff0c;占…
閱讀更多...
C#面：C# 如何使? ActionFilterAttribute？

C#面：C# 如何使? ActionFilterAttribute？

在C#中&#xff0c;ActionFilterAttribute是一個特性類&#xff0c;用于在控制器的動作方法執行前后添加自定義邏輯。它可以用于實現日志記錄、異常處理、權限驗證等功能。 要使用ActionFilterAttribute&#xff0c;可以按照以下步驟進行操作&#xff1a; 創建一個繼承自Acti…
閱讀更多...
Apache Seata分布式事務原理解析探秘

Apache Seata分布式事務原理解析探秘

本文來自 Apache Seata官方文檔&#xff0c;歡迎訪問官網&#xff0c;查看更多深度文章。 本文來自 Apache Seata官方文檔&#xff0c;歡迎訪問官網&#xff0c;查看更多深度文章。 前言 fescar發布已有時日&#xff0c;分布式事務一直是業界備受關注的領域&#xff0c;fesca…
閱讀更多...
【carla】ubuntu安裝carla環境

【carla】ubuntu安裝carla環境

我們可以通過查看 CARLA 的 GitHub release 頁面來找到最新版本的下載鏈接。 下載 CARLA 壓縮包 訪問 CARLA Releases 頁面&#xff1a; CARLA Releases on GitHub 查找最新版本&#xff1a; 找到最新的版本&#xff0c;點擊下載&#xff0c;第一個壓縮包 3. 解壓 CARLA 包&…
閱讀更多...
深度學習中的正則化技術 - 引言篇

深度學習中的正則化技術 - 引言篇

序言 在深度學習中&#xff0c;正則化技術是防止模型過擬合、提升泛化能力的關鍵策略。隨著模型復雜度的增加&#xff0c;過擬合風險也隨之上升。正則化通過引入額外約束或信息&#xff0c;調整模型訓練過程&#xff0c;旨在簡化模型結構&#xff0c;使其學習到數據中的本質特…
閱讀更多...
VMware Workstation Pro 17.5.2 + license key

VMware Workstation Pro 17.5.2 + license key

Workstation Pro是專為Windows操作系統設計的功能強大的虛擬化軟件平臺，它允許用戶在其計算機上創建和運行虛擬機，這使他們能夠同時與多個操作系統、應用程序和開發環境一起工作。 Workstation Pro的主要特點之一是其易用性，程序提供了直觀的界面，允許用戶輕松創建、配置和…
閱讀更多...
uabntu安裝opencv

uabntu安裝opencv

1. 安裝前置依賴 sudo apt update sudo apt upgrade sudo apt install build-essential cmake git pkg-config sudo apt install libjpeg-dev libtiff-dev libpng-dev # Image libraries sudo apt install libavcodec-dev libavformat-dev libswscale-dev libv4l-dev # Vide…
閱讀更多...
RocketMQ NettyRemotingServer、NettyRemotingClient 實例化、初始化、啟動源碼解析

RocketMQ NettyRemotingServer、NettyRemotingClient 實例化、初始化、啟動源碼解析

&#x1f52d; 嗨&#xff0c;您好 &#x1f44b; 我是 vnjohn&#xff0c;在互聯網企業擔任后端開發&#xff0c;CSDN 優質創作者 &#x1f4d6; 推薦專欄&#xff1a;Spring、MySQL、Nacos、Java&#xff0c;后續其他專欄會持續優化更新迭代 &#x1f332;文章所在專欄&#…
閱讀更多...
數學系C++ 類與對象 STL（九）

數學系C++ 類與對象 STL（九）

目錄 目錄 面向對象&#xff1a;py&#xff0c;c艸&#xff0c;Java都是,但c是面向過程 特征&#xff1a; 對象 內斂成員函數【是啥】&#xff1a; 構造函數和析構函數 構造函數 復制構造函數/拷貝構造函數&#xff1a; ?【……】 實參與形參的傳遞方式&#xff1a;值…
閱讀更多...
Node.js Stream

Node.js Stream

Node.js Stream Node.js 是一個基于 Chrome V8 引擎的 JavaScript 運行環境&#xff0c;它允許開發者使用 JavaScript 編寫服務器端代碼。Node.js 的一個核心特性是其對流&#xff08;Stream&#xff09;的處理能力。流是一種在 Node.js 中處理讀/寫文件、網絡通信或任何端到端…
閱讀更多...
【LeetCode】螺旋矩陣

【LeetCode】螺旋矩陣

目錄 一、題目二、解法完整代碼 一、題目 給你一個 m 行 n 列的矩陣 matrix &#xff0c;請按照 順時針螺旋順序 &#xff0c;返回矩陣中的所有元素。 示例 1&#xff1a; 輸入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 輸出&#xff1a;[1,2,3,6,9,8,7,4,5] 示例 2&…
閱讀更多...
go-redis 封裝事件-client封裝模型、批量數據處理的導出器設計

go-redis 封裝事件-client封裝模型、批量數據處理的導出器設計

一、redis-go的封裝實踐-client模型 // Copyright 2020 Lingfei Kong <colin404foxmail.com>. All rights reserved. // Use of this source code is governed by a MIT style // license that can be found in the LICENSE file.package storageimport ("context&q…
閱讀更多...
MySQL性能優化 二、表結構設計優化

MySQL性能優化 二、表結構設計優化

1.設計中間表 設計中間表&#xff0c;一般針對于統計分析功能&#xff0c;或者實時性不高的需求。 2.設計冗余字段 為減少關聯查詢&#xff0c;創建合理的冗余字段&#xff08;創建冗余字段還需要注意數據一致性問題&#xff09; 3.折表 對于字段太多的大表&#xff0c;考…
閱讀更多...
C++ STL容器：序列式容器-鏈list，forward_list

C++ STL容器：序列式容器-鏈list，forward_list

摘要&#xff1a; CC STL&#xff08;Standard Template Library&#xff0c;標準模板庫&#xff09;在C編程中的重要性不容忽視&#xff0c;STL提供了一系列容器、迭代器、算法和函數對象&#xff0c;這些組件極大地提高了C程序的開發效率和代碼質量。 STL 容器 分為 2 大類 …
閱讀更多...
Halcon 銑刀刀口破損缺陷檢測

Halcon 銑刀刀口破損缺陷檢測

一 OTSU OTSU&#xff0c;是一種自適應閾值確定的方法,又叫大津法&#xff0c;簡稱OTSU&#xff0c;是一種基于全局的二值化算法,它是根據圖像的灰度特性,將圖像分為前景和背景兩個部分。當取最佳閾值時&#xff0c;兩部分之間的差別應該是最大的&#xff0c;在OTSU算法中所采…
閱讀更多...
排序 -- 萬能測試oj

排序 -- 萬能測試oj

. - 力扣&#xff08;LeetCode&#xff09; 這道題我們可以使用我們學過的那些常見的排序方法來進行解答 //插入排序 void InsertSort(int* nums, int n) {for (int i 0; i < n-1; i){int end i;int tmp nums[end 1];while (end > 0){if (tmp < nums[end]){nums[…
閱讀更多...
PyVideoTrans：一款功能全面的視頻翻譯配音工具！【送源碼】

PyVideoTrans：一款功能全面的視頻翻譯配音工具！【送源碼】

PyVideoTrans是一款功能全面的視頻翻譯配音工具&#xff0c;專為視頻內容創作者設計。它能夠將視頻中的語言翻譯成另一種語言&#xff0c;并自動生成與之匹配的字幕和配音。支持多種語言&#xff0c;包括但不限于中文&#xff08;簡繁體&#xff09;、英語、韓語、日語、俄語、…
閱讀更多...
最新文章

Copyright @ 2022~2023