利用Kmeans與蟻群算法的路徑尋優方法

彭熙舜，陸安江，賈明俊，盧學敏

（貴州大學 大數據與信息工程學院，貴陽550025）

0 引 言

在當今時代，網購已經成為了一種新的潮流，每年由電商舉辦的雙十一、六一八更是風靡盛行。隨著快遞數目的劇烈增長，物流的配送工作越來越重要。人們購買的物件也是花樣繁多，生鮮快遞必須滿足時效性，裝飾類物品需要避免發生碰撞。物流配送過程中常規應用GPS導航，而高效的物流管理取決于兩個關鍵因素，車輛問題（VRP）與資源配置問題，因此路徑規劃開始被廣泛應用于物流管理中。本文提出了利用Kmeans聚類將客戶購買物品按照特性進行分類，再利用蟻群算法進行路徑規劃。

1 研究背景與意義

路徑規劃是近代興起的新型技術，被廣泛應用于機器人避障，無人機避障，防空導彈系統中。人們的日常生活也開始利用這種技術，比如城市交通規劃，GPS智能導航，物流配送管理系統。通常情況下，按照周圍環境信息的布局規劃，可以將其分為全局和局部兩種路徑規劃［1］。前者需要在實踐之前掌握所有的環境數據，提前作出路徑規劃判斷；后者主要是采取傳感器實時得來的局部環境信息，及時的給出路徑規劃。本文主要研究解決車輛路徑問題（VPR），以物流中心為起點，派出車輛向不同位置的客戶進行物資配送，配送任務結束后返回起點，而其中的關鍵在于將配送效率最大化，車輛使用率最大化。

路徑規劃一般是由環境建模，路徑搜索，路徑平滑這3步所組成［2］。環境建模是起始環節，搭建一個方便計算機規劃具體路徑的模型，實質上是將物理信息轉為數字信息，在空間上相互映射；路徑搜索是指在搭建的環境中尋求到達目標的路徑信息；路徑平滑是在所有的路徑信息中選取最優路徑。

2 智能算法

2.1 Kmeans算法簡介

網絡用戶的大幅度增長也帶動了數據的產生，面對愈來愈多的用戶數據，根據其之間的相似性，進行聚類分析（cluster analysis）。所謂聚類并不是通常意義上的按規格分類，空間中點的匯聚稱為一個類簇，不同類簇中任意的兩點距離應該大于同一類簇中的任意兩點距離［3］。具體過程可以描述為，第一步設置一個衡量標準，將系統中的個體數據特性計算區別；第二步使用算法將個體匯編并定義為一個新的集群。如今存在著多種不同的聚類分析方法，如何根據自身要求選擇一種合適的算法來進行數據分析成了當務之急。

Kmeans又稱為K均值，是一種劃分聚類的算法，具有高效簡潔的特點普及率高。其算法步驟清晰易懂，首先根據客戶需求設置值為k的n個初始質心；其次，將質心散開，將系統中的數據點根據自身特性匹配到與其距離最近的質心，同一個質心中的數據點構成了簇。分析簇中的數據點，更新質心的值。按照以上步驟重復進行，直到質心的值不再變化或者達到了設定的終止條件為止。

為了將數據點匹配到與之最近的質心，需要設定方法來測算距離。給定一個樣本空間x i＝將i，j設置為樣本數，n表示數據特征。首先計算有序距離度量，根據閔可夫斯基距離公式（1）：

其次，介紹無序屬性距離度量，式（2）：

Kmeans在空間中只需考慮數據點與質心問題，它的空間復雜度不高?？臻g的存儲量設定O（（m+k）n），其中的m是數據點數，n代表了屬性數。它的時間復雜性與數據點的數目有關，所需要的時間于m呈線性表示，為O（I×K×m×n），I代表了收斂的迭代次數。

2.2 蟻群算法

蟻群算法，顧名思義是模仿生物界中螞蟻特性的算法。這種算法模仿的是螞蟻從蟻窩中尋找食物所自動生成的最佳路徑的過程。在螞蟻行走的過程里，它們會釋放一種被稱為信息素的物質，以此來標識自己的行走路徑，路徑越長的地方，信息素越少，而路徑越短的地方，信息素越多，表示了螞蟻選擇走該路徑的數量居多。久而久之，信息素少的地方自然也就被淘汰，最后留下來的就是一個優化路線［4］。

蟻群算法在離散空間中是通過離散的點狀散布來選取的信息量的最優解。連續空間中的解空間與離散的不同，是以區域性的方式進行表示，不是用離散的點集合表示。連續空間與離散空間有著3處不同，首先是觀察蟻群的信息量留存方式；其次蟻群在解空間中尋找最優路徑方法；以及最后的群體前進策略。

蟻群算法在連續空間下的尋優方法是基于蟻群的初始分布狀態，螞蟻路途中釋放的信息量分布狀態，整個蟻群的行進方向策略。因此，可以用數學表達式模擬出基本過程：第一步是將群體的初始分布狀態表示，根據問題來設置蟻群的大小，例如設置共有N個小螞蟻；將問題的定義區間均等分為N個子空間，每個子空間匹配一只小螞蟻，編號為i。因為螞蟻會變換自己的活動區域，所以所規定的子空間也是隨著螞蟻同步變化的，一一對應。當小螞蟻隨機移動時，可以發現它所攜帶的子空間會與其它2個相鄰的子空間重疊，根據這個重疊的程度，可以推算出2個相鄰子空間內的實際螞蟻變化程度［5-6］。

按照以上敘述方式，設置提出問題的定義區間是［A，Z］，則當種群內的螞蟻數目為N時，可以得到各個子空間的長度為式（3）：

因為螞蟻有著自身運動的移動子空間，而這個移動子空間的長度與基本子空間是沒有區別的，所以有L R＝L，那么蟻群的初始點的坐標分布可以定義為式（4）：

螞蟻所處子空間i的左邊界為x iL，右邊界為x i R，可以得到式（5）：

當螞蟻隨機移動k時，移動子空間與相鄰子空間的重疊度也為k，那么可以定義兩個相鄰的子空間內對應當前螞蟻的實際個數N1的變化為式（6）：

所以，當小螞蟻向右行進時，右邊子空間內實際的螞蟻數目多出了Δn，與之相對，左邊的子空間實際螞蟻數目就減少了Δn。

接下來根據螞蟻的分布情況來確定空間中的信息量分布密度。若蟻群在x i處的函數值為f（x i)，那么可以規定此時螞蟻留下的信息量峰值為M i，這樣可以根據函數與信息量的大小得出最優路徑。假設在某一區間內去實現尋找函數的最小值，那么可以得到相應的信息量分布函數，式（7）：

其中，R是設定的常數，規定R＞f（x i）。 此時可以發現，函數值越小，信息量的分布函數峰值越大。相對的，如尋找函數的最大值，當f（x i）＞0，可以得到式（8）：

因此，可以得到單個螞蟻所對應的信息量分布函數為式（9）：

在得到螞蟻群分布的總信息量后，需要確定各子區間內的實際螞蟻數目［7］。根據信息量分布函數可以得出當前蟻群在各個子空間內分布積分和為式（10）：

實際上的各子空間總信息量為式（11）：

其中，q代表上上次的總信息量遺留部分，p代表信息量的揮發量。所以可以得出實際總空間中的總信息量為式（12）：

按照子空間中的實際總信息量與總空間的信息量可以推算出螞蟻的分布情況，得出螞蟻在某一子空間中的數目為式（13）：

3 仿真分析

利用Kmeans算法與蟻群算法思想，事先構思出聚類規劃和尋優路徑的新型路徑配送方式。將文本數據導入程序，設N為樣本數量，n是樣本中的屬性數；將螞蟻群分成4個小組；螞蟻總數目設為R，最大迭代次數用Tmax表示，表1為不同組參數設置表，其中Mi n代表螞蟻到其對應的聚類中心的距離最小值。

此外，還需要注意偏離誤差的計算，即為螞蟻到其對應的聚類中心的距離Mi n，Mi n越小，說明螞蟻越集中，聚類水平高。倘若得到每一只螞蟻的Mi n值，那么從中挑選出最小的Mi n，其所對應的路徑就是本次迭代的最佳路徑。而迭代的方法就是利用循環，更新蟻群的信息素，根據新的參數進行尋優計算，直到滿足要求為止。當R＝100，Tmax＝1 000時，仿真分析如圖1，當R＝100，Tmax＝10 000時，如圖2所示。

表1 程序參數設置表Tab.1 Program parameter setting table

圖1 第一次蟻群聚類結果Fig.1 The first ant colony clustering results

圖2 增大迭代次數后的聚類效果Fig.2 The clustering effect after increasing the number of iterations

從圖1中可以清晰地看到，共有R＝4種螞蟻組數，此時的M i n是30 690，達到了一定的聚類效果，但還不能滿足要求，接下來繼續增大迭代次數。將Tma x增大到10 000可得以下結果：

由圖2知，此時的Mi n＝19 726，相比于第一次聚類效果，在達到良好的聚類分析后，需要找出一條合適的路徑，從初始點到聚類中心，接下來需要對路徑進行尋優規劃。此時用400個單位方塊模擬環境地圖，邊長設置為1，以（0，0）作為初始點，（20，20）作為終點，圖3和圖4中隨機設置障礙物，并用矩陣存儲每一代的每一只螞蟻的爬行路線長度。

圖3 螞蟻爬行路線Fig.3 Ant crawling route

圖4 螞蟻無碰撞最優路徑Fig.4 The optimal path of ants without collision

由圖3可知，螞蟻從起始點到終點路線數量復雜，尤其是起始點附近，因為螞蟻剛從蟻穴出來，數量眾多，分泌的信息素也多，因為路徑更加的繁瑣。在接近終點處，由于路程長度，信息素散發稀釋，所以螞蟻的行進路線自然減少。螞蟻此次路程的最佳路徑如圖4所示，在無碰撞的情況下保證路程長度。

4 結束語

利用Kmeans與蟻群算法能夠很好地解決物流配送問題，尤其是當下不同種類的物資需要不同的配送方式。物流中心在接到配送訂單時，可以利用該組合算法對配送物品進行聚類分析，可以按照物件的時效性，安全性等作為路徑規劃，這樣就能更好的滿足客戶的需求，同時也減少了物流配送的時間成本。Kmeans與蟻群算法對當下的快遞行業有著一定的參考意義。