摘 要：【目的】商旅問題是指商人在訪問多個城市時，要求不能走回頭路且最終要回到起點，尋求這個過程中最短路徑的問題。通過分析旅行商問題，探討不同算法的應(yīng)用范圍，選擇合適的算法來優(yōu)化解決旅行商問題?！痉椒ā扛鶕?jù)目前各種尋優(yōu)算法的特點，選擇粒子群算法作為求優(yōu)算法來解決商旅問題，并在此基礎(chǔ)上進行優(yōu)化改進。先確定權(quán)重因子和加速因子，再根據(jù)隨機函數(shù)對粒子個體和種群進行算法變異，從而實現(xiàn)旅行商問題尋優(yōu)算法的改進。在此基礎(chǔ)上，通過粒子群算法和MATLAB算法編程，以實現(xiàn)優(yōu)化結(jié)果?！窘Y(jié)果】通過改進參數(shù)和引入變量函數(shù)進行尋優(yōu)算法改進，有利于算法的收斂?！窘Y(jié)論】改進后的尋優(yōu)算法可以快速找到商人旅行過程的最優(yōu)路徑規(guī)劃。

關(guān)鍵詞：粒子群算法PSO；優(yōu)化問題；旅行商問題

中圖分類號：TP181" " "文獻標志碼：A" " "文章編號：1003-5168（2024）10-0032-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2024.10.006

Discussion on Business Travel Problem Based on PSO Algorithm

HAN Linping ZHU Haoyun XIE Mengmin MA Fei WANG Mingjie

（Henan Vocational College of Water Conservancy and Environment， Zhengzhou 450008，China）

Abstract： [Purposes] The business travel problem refers to the problem of merchants visiting multiple cities， demanding that they cannot turn back and ultimately return to the starting point， seeking the shortest path in this process. This article analyzes the traveling salesman problem， explores the application scope of different algorithms， and selects appropriate algorithms to optimize and solve the traveling salesman problem. [Methods] Based on the characteristics of various optimization algorithms currently available， particle swarm optimization algorithm is selected as the optimization algorithm to solve the business travel problem. Based on this， optimization and improvement are carried out by first determining the weight factor and acceleration factor， and then using random functions to perform algorithm variation on the individual particles and population， in order to improve the optimization algorithm for the business travel problem. On this basis， we will use particle swarm optimization algorithm and program it through MATLAB algorithm to achieve the implementation of optimization results. [Findings] By improving parameters and introducing variable functions for optimization algorithm improvement， it is beneficial for the convergence of the algorithm. [Conclusions] The improved optimization algorithm can quickly find the optimal path planning for the merchant′s travel process.

Keywords：PSO; optimization problem; traveling salesman problem

0 引言

旅行商問題［1］是指商人需要到N個城市考察，并要求商人每到一個城市只能考察一次，當完成所有城市的考察后，最終必須返回出發(fā)最早的城市。在此基礎(chǔ)上，尋求商人能夠遍訪這N個城市所需的最短路徑尋優(yōu)問題。

為方便運用算法討論該問題，給出了以下定義。

定義1：將城市位置假定為圖上坐標點，將這N個城市點創(chuàng)建在一張圖幅中，稱為G圖。G圖經(jīng)過各點一次后的圓圈稱為H圓圈。

定義2：在圖G中求解路徑最小的H圈，即路徑L。

通過上述定義可以將旅行商問題轉(zhuǎn)化為尋找最小H圈的問題。

設(shè)Dij為兩城市i和j之間的距離，每訪問一次從i到j(luò)，則Xij=1，否則為0，則目標函數(shù)見式（1）。

[minZ=i， j=1nxijdij] （1）

若對于城市集W={w1，w2，……，wn}的訪問順序為T={t1，t2，……，tn}，其中，ti∈W；wi的二維空間坐標為（xi，yi）。則它的數(shù)學表達式評價標準是商人在二維空間中使用的最短距離，也就是適應(yīng)度函數(shù)見式（2）。

[minL=i=1n-1（xi+1-xi）2+（yi+1-yi）2+（x1-xn）2+（y1-yn）2] （2）

由式（2）可知，旅行商問題是具有代表性的組合優(yōu)化性問題，最終的結(jié)果顯示為一個環(huán)路，是極具特點的離散型問題。然而，粒子群算法［2］的解決域應(yīng)該是連續(xù)的而不是離散的，因此，為了解決離散的旅行商問題，粒子群算法的連續(xù)域必須通過離散化改進粒子群算法。雖然連續(xù)型的粒子群算法很常見，并且國內(nèi)外研究也具有一定的深度，但是離散型的粒子群算法的探究至今仍很少，目前常見路徑算法有以下幾種。

①遺傳算法。遺傳學算法是從生物學中物競天擇，適者生存的生物遺傳規(guī)律中得出的一種智能搜索算法。其中不只包含有遺傳，還存在變異以及斗爭和生存等問題。該算法通過選擇合適的功能，并引入基因交叉和變異來優(yōu)化篩選群體中的個體，一代一代篩選出更好的粒子，最終得到最好的篩選結(jié)果。在遺傳學算法［3］中應(yīng)用了“自然選擇、優(yōu)勝劣汰”的生物進化理論。

②蟻群算法。蟻群算法最早誕生于20世紀末，是由意大利學者提出的一種智能仿生算法［4］。蟻群算法最早思路是從螞蟻尋找食物的現(xiàn)象中產(chǎn)生靈感，從而想出基于群體的模擬種群進化方法。該算法收斂速度快、魯棒性強，容易與其他算法相結(jié)合，同時容易陷入局部最優(yōu)，并且當種群規(guī)模過大時，計算過程比較煩瑣。

③PSO粒子群算法。PSO粒子群算法最初是從鳥群覓食活動中獲得靈感的［5］，也是以鳥類群體的覓食活動為基礎(chǔ)的仿生隨機算法。該算法吸取了鳥群覓食的群體理論思想，算法簡單、收斂速度快且易于實現(xiàn)。目前，神經(jīng)網(wǎng)絡(luò)訓(xùn)練、函數(shù)優(yōu)化、帶約束優(yōu)化等復(fù)雜問題的求解已經(jīng)成功地應(yīng)用了粒子群算法。

以上路徑規(guī)劃算法的優(yōu)化性能相對來說還是比較優(yōu)秀的。但蟻群算法的最大弊端是，當種群基數(shù)變大、計算時間增長時，算法就會變得復(fù)雜煩瑣。粒子群算法和遺傳學算法雖然有很多共性，但是粒子群算法更加簡單方便，沒有遺傳算法的交叉變異操作。在解決旅行商問題上，粒子群算法還有一項展現(xiàn)優(yōu)越性的獨特之處，那就是其具有的粒子記憶功能。因此，決定選擇粒子群優(yōu)化算法來探討旅行商的路徑規(guī)劃問題。

1 PSO算法概述

粒子種群尋優(yōu)算法（ParticleSwarmOptimization，PSO）由埃伯哈特和肯尼迪于1995年首次提出。算法最初是基于鳥群覓食問題，搭建場景，設(shè)置尋優(yōu)方法，建立數(shù)學模型，尋找最優(yōu)解的過程［6］。將鳥群覓食問題轉(zhuǎn)化為數(shù)學模型，把搜尋食物的每一只鳥看成一個粒子，給其一個初始化速度值，該初始化值由適應(yīng)度函數(shù)得出，然后通過迭代的方式尋找路徑最優(yōu)解。

肯尼迪和艾伯哈特最早對粒子進行初始化操作如下。

適應(yīng)度函數(shù)見式（3）。

[fitness（i）=i， j=1npathi， j] （3）

粒子速度更新見式（4）。

[V′id=ωVid+c1rand（）（Pid-Xid）+c2rand（）（Pgd-Xid）] （4）

式中：Vid表示在D維上第i個粒子的速度；ω表示慣性權(quán)重影響因子，即各粒子更新后的速度與上一次速度的相關(guān)度影響（structionfactor）；Pid表示粒子i求得的最好現(xiàn)在值；Pgd表示粒子種群求得的最好路徑；參數(shù)C1和C2為確定Pid和Pgd比例關(guān)系的參數(shù)調(diào)節(jié)因子；函數(shù)rand（）為確定路徑中下一個目標點位置的隨機數(shù)生成函數(shù)。

當前粒子位置的更新見式（5）。

[X′id=Xid+V′id] （5）

粒子群算法求優(yōu)的最終條件是根據(jù)特定問題設(shè)定最終的迭代次數(shù)，從而找到最終的結(jié)果。

2 基于改進的PSO算法解決旅行商問題

2.1 慣性權(quán)重ω和加速因子C的確定

由式4可知，在慣性權(quán)重因子ω的作用下，ωVid代表粒子的當前速度。更新后的速度表明，在搜索空間中，當前粒子的飛行動力是否適宜。ω較大，則說明粒子主要參考上一次的速度來決定下一次的動作；ω較小時，粒子更傾向于考慮個體和全局的最優(yōu)信息。因此，ω的值對粒子的局部尋優(yōu)性能以及全局尋優(yōu)性能都會產(chǎn)生很大影響。ω值的選取非常關(guān)鍵，一般ω的值介于0～1之間。本研究采用由智瀚宇等［7］提出的自適應(yīng)慣性權(quán)重策略，改進公式見式（6）。

[ω=ωmin+ωmax-ωminfi-fminfavr-fmin， f≤favrωmax" " " " " " " " " " " " " " " " " " " " " " " " " "， fgt;favr] （6）

式中：ωmax和ωmin分為慣性權(quán)值ωmin的取值上限和取值下限；fi為粒子xi的初始化值，即適應(yīng)度函值；favr和fmin分別為適應(yīng)度函數(shù)的平均值和最小值。

由式4可知，加速因子C1和加速因子C2對整體速度更新的影響在于粒子個體之間和粒子種群之間的信息交流和傳遞（信息交換和傳輸）以及單個粒子的自身飛行經(jīng)驗和粒子種群的整體飛行經(jīng)驗對當前飛行速度的影響因子。通常情況下，加速因子C1的值設(shè)置較大時，代表粒子會根據(jù)自身飛行經(jīng)驗在局部徘徊，無法完成收斂；而當C2較大時，代表粒子會參照種群的飛行經(jīng)驗快速結(jié)束搜索，導(dǎo)致尋優(yōu)次數(shù)過小。也就是粒子會通過很小的更新次數(shù)得到最終的更新速度，造成粒子速度更新結(jié)果不具有大面積數(shù)據(jù)性。因此，要合理的給定加速度因子C1和C2的數(shù)值。根據(jù)Shi和Eberhart的研究經(jīng)驗，通常取C1=C2=2，并且目前的粒子群算法應(yīng)用研究中仍然普遍采用此數(shù)值。偶爾也會采取二者不相等，但數(shù)值均在0～4區(qū)間之內(nèi)取值。根據(jù)研究經(jīng)驗，最終對速度因子C1的取值是2，對C2的取值也是2。

2.2 變異算法的操作實現(xiàn)

對粒子種群進行個體編號。對于種群的個體編碼方式，通常采用整數(shù)編碼，每個編碼代表商人所要訪問的城市，例如當經(jīng)歷的城市數(shù)量為8個，個體編碼為42137685，表示城市遍歷從7開始，經(jīng)過4、2、1、3，最后返回城市7，從而完成一次算法的路徑計算。

個體與種群粒子的交叉變異［8］通常采用整數(shù)交叉法，是通過選擇新的交叉位置來實現(xiàn)的。具體實施如下。

通過運用隨機函數(shù)產(chǎn)生隨機數(shù)的方式來確定交叉變異的位置。例如，隨機函數(shù)產(chǎn)生的數(shù)值為3和5，那么就認為交叉數(shù)值為3和5，若個體編碼為［4 2 1 3 7 6 8 5］，種群優(yōu)化值為［2 1 3 7 6 8 5］，那么交叉后的新個體為［4 2 7 3 1 6 8 5］，種群優(yōu)化結(jié)果交叉變異為［2 1 6 7 3 8 5］。

2.3 用MATLAB軟件編程實現(xiàn)尋優(yōu)過程

基于改進粒子群算法理論，我們在Matlab中對粒子群算法進行了改進后的算法編程［9］。具體編程實施過程如下。

假定商人要遍訪的城市個數(shù)為20。城市坐標分布圖用MATLAB軟件編程實現(xiàn)生成城市坐標的二維圖，得到的城市坐標位置分布如圖1所示。

算法訓(xùn)練的過程如圖2所示。由圖2可知，編程操作過程中適應(yīng)度函數(shù)值的大小隨變化次數(shù)的增加而遞減，迭代次數(shù)逐漸增加，適應(yīng)度值由迭代次數(shù)為40時開始穩(wěn)定，不再有明顯的變化。

本次編程的城市個數(shù)為20，產(chǎn)生300個體數(shù)，循環(huán)迭代次數(shù)為200，用時9 s得到尋優(yōu)的最佳路徑。最佳路徑值約為112公里。仿真結(jié)果重要數(shù)據(jù)見表1。尋優(yōu)最佳旅游路線如圖3所示。

3 結(jié)語

基本的粒子群演算法，通過簡單的程序?qū)?yōu)、較少的迭代就可以達到快速收斂，并獲得最優(yōu)解法（Sublication）。隨著數(shù)據(jù)迭代次數(shù)的增加，各個粒子的尋優(yōu)路徑會趨于一致，導(dǎo)致速度更新結(jié)果陷入死循環(huán)，無法完成收斂。本研究改進的粒子群算法，在改進權(quán)重因子和加速因子的基礎(chǔ)上，引入了個體與種群交叉以及粒子種群自身變異的方法，來保證粒子在速度更新時不會陷入死循環(huán)。實驗證明，改良后的PSO粒子群算法具有易于操作、快速收斂及多次迭代的特點。

參考文獻：

［1］沈繼紅，王侃.求解旅行商問題的混合粒子群優(yōu)化算法［J］.智能系統(tǒng)學報，2012，7（2）：174-182.

［2］莫愿斌，陳德釗，胡上序.粒子群復(fù)形法求解旅行商問題［J］.浙江大學學報（工學版），2007，41（3）：369-373

［3］梁慧.混沌粒子群優(yōu)化算法的分析與應(yīng)用［D］.廣州：廣東工業(yè)大學，2011.

［4］李明皓.基于混合離散粒子群算法的焊接機器人路徑規(guī)劃［D］.上海：華東理工大學，2014.

［5］王翠茹，馮海迅，張江維，等.基于改進粒子群優(yōu)化算法求解旅行商問題［J］.微計算機信息，2006（8S）：273-275，306

［6］陳峰，丁泉，吳樂，等.混合驅(qū)動的粒子群算法［J］.計算機工程與應(yīng)用，2024，60（8）：78-89.

［7］智瀚宇，賈新春，張學立.無人機路徑規(guī)劃：一種粒子群和灰狼復(fù)合算法［J/OL］.控制工程，1-8［2023-12-22］.https：//doi.org/10.14107/j.cnki.kzgc.20221058.

［8］邊錦華，張曉霞.求解TSP問題的一種變領(lǐng)域遺傳算法［J］.福建電腦，2023，39（12）：24-27

［9］王君.基于MATLAB和VR工具的自動控制實驗教學案例設(shè)計［J］.工業(yè)和信息化教育，2023（12）：71-75.

（欄目編輯：孫焱）