基于PSO算法的商旅問題探討

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

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

中圖分類號(hào)：TP181" " "文獻(xiàn)標(biāo)志碼：A" " "文章編號(hào)：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個(gè)城市考察，并要求商人每到一個(gè)城市只能考察一次，當(dāng)完成所有城市的考察后，最終必須返回出發(fā)最早的城市。在此基礎(chǔ)上，尋求商人能夠遍訪這N個(gè)城市所需的最短路徑尋優(yōu)問題。

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

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

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

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

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

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

若對(duì)于城市集W={w1，w2，……，wn}的訪問順序?yàn)門={t1，t2，……，tn}，其中，ti∈W；wi的二維空間坐標(biāo)為（xi，yi）。則它的數(shù)學(xué)表達(dá)式評(píng)價(jià)標(biāo)準(zhǔn)是商人在二維空間中使用的最短距離，也就是適應(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é)果顯示為一個(gè)環(huán)路，是極具特點(diǎn)的離散型問題。然而，粒子群算法［2］的解決域應(yīng)該是連續(xù)的而不是離散的，因此，為了解決離散的旅行商問題，粒子群算法的連續(xù)域必須通過離散化改進(jìn)粒子群算法。雖然連續(xù)型的粒子群算法很常見，并且國內(nèi)外研究也具有一定的深度，但是離散型的粒子群算法的探究至今仍很少，目前常見路徑算法有以下幾種。

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

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

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

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

1 PSO算法概述

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

肯尼迪和艾伯哈特最早對(duì)粒子進(jìn)行初始化操作如下。

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

當(dāng)前粒子位置的更新見式（5）。

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

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

2 基于改進(jìn)的PSO算法解決旅行商問題

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

由式4可知，在慣性權(quán)重因子ω的作用下，ωVid代表粒子的當(dāng)前速度。更新后的速度表明，在搜索空間中，當(dāng)前粒子的飛行動(dòng)力是否適宜。ω較大，則說明粒子主要參考上一次的速度來決定下一次的動(dòng)作；ω較小時(shí)，粒子更傾向于考慮個(gè)體和全局的最優(yōu)信息。因此，ω的值對(duì)粒子的局部尋優(yōu)性能以及全局尋優(yōu)性能都會(huì)產(chǎn)生很大影響。ω值的選取非常關(guān)鍵，一般ω的值介于0～1之間。本研究采用由智瀚宇等［7］提出的自適應(yīng)慣性權(quán)重策略，改進(jì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對(duì)整體速度更新的影響在于粒子個(gè)體之間和粒子種群之間的信息交流和傳遞（信息交換和傳輸）以及單個(gè)粒子的自身飛行經(jīng)驗(yàn)和粒子種群的整體飛行經(jīng)驗(yàn)對(duì)當(dāng)前飛行速度的影響因子。通常情況下，加速因子C1的值設(shè)置較大時(shí)，代表粒子會(huì)根據(jù)自身飛行經(jīng)驗(yàn)在局部徘徊，無法完成收斂；而當(dāng)C2較大時(shí)，代表粒子會(huì)參照種群的飛行經(jīng)驗(yàn)快速結(jié)束搜索，導(dǎo)致尋優(yōu)次數(shù)過小。也就是粒子會(huì)通過很小的更新次數(shù)得到最終的更新速度，造成粒子速度更新結(jié)果不具有大面積數(shù)據(jù)性。因此，要合理的給定加速度因子C1和C2的數(shù)值。根據(jù)Shi和Eberhart的研究經(jīng)驗(yàn)，通常取C1=C2=2，并且目前的粒子群算法應(yīng)用研究中仍然普遍采用此數(shù)值。偶爾也會(huì)采取二者不相等，但數(shù)值均在0～4區(qū)間之內(nèi)取值。根據(jù)研究經(jīng)驗(yàn)，最終對(duì)速度因子C1的取值是2，對(duì)C2的取值也是2。

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

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

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

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

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

基于改進(jìn)粒子群算法理論，我們?cè)贛atlab中對(duì)粒子群算法進(jìn)行了改進(jìn)后的算法編程［9］。具體編程實(shí)施過程如下。

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

［7］智瀚宇，賈新春，張學(xué)立.無人機(jī)路徑規(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工具的自動(dòng)控制實(shí)驗(yàn)教學(xué)案例設(shè)計(jì)［J］.工業(yè)和信息化教育，2023（12）：71-75.

（欄目編輯：孫焱）