類電磁機制算法的應(yīng)用研究

段熙鵬，蔡延光，湯雅連

（廣東工業(yè)大學(xué) 自動化學(xué)院，廣東 廣州510006）

類電磁機制 EM（Electromagnetism-like Mechanism）算法是一種新型的基于種群的隨機全局優(yōu)化算法，在現(xiàn)實生活中具有很強的應(yīng)用背景，可以應(yīng)用到分子生物、調(diào)度安排、工程設(shè)計等領(lǐng)域。近幾年來已有不少學(xué)者做了相關(guān)研究[1-4]，并取得了很好的成果。但是對于關(guān)聯(lián)運輸調(diào)度問題 RVRP（Related Vehicle Routing Problem）的探討在國內(nèi)還不多見。但是前人研究的各種車輛路徑問題VRP（Vehicle Routing Problem）對本文的研究有很重要的借鑒意義。本文主要研究在載重約束下，對各車場中的多種不同類型車輛及配送路線進行合理安排，在滿足所有客戶要求的前提下，使配送成本最低。

1 問題描述及數(shù)學(xué)模型的建立

1.1 問題描述

多車場多車型關(guān)聯(lián)運輸調(diào)度問題可以簡單描述為：假設(shè)給定車場信息以及客戶信息(位置和貨物需求量等)、貨物之間的關(guān)聯(lián)系數(shù)、不同類型車輛信息（載重約束、里程約束和關(guān)聯(lián)約束等），要求合理安排車輛和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

1.2 數(shù)學(xué)模型

假設(shè)客戶編號為 1，2，…，l，車場編號為 l+1，l+2，…，l+N。定義變量如下：

2 改進的EMA

2.1 傳統(tǒng)EMA基本原理

EMA是一種隨機全局優(yōu)化算法。它模擬電磁場中的吸引和排斥機制，將每個解比作一個帶電粒子，然后按一定的準(zhǔn)則使得搜索粒子朝最優(yōu)解移動。由于此思想與電磁理論中吸引與排斥機制有相似性，但也存在差異性，所以稱之為類電磁機制。該算法的收斂性已經(jīng)得到證明，當(dāng)?shù)螖?shù)趨于極限時，種群中至少有一個粒子以概率1移動到全局最優(yōu)附近。

根據(jù)電磁理論中的吸引——排斥機制，EMA把每個搜索粒子想象成空間中的一個帶電粒子，每個粒子的電荷由待優(yōu)化的目標(biāo)函數(shù)的函數(shù)值決定。該電荷也決定了該粒子對其他粒子的吸引或排斥的強弱。目標(biāo)函數(shù)值越優(yōu)，尋優(yōu)越強。通過計算其他粒子與當(dāng)前粒子的合力來確定每個粒子下一步的走向。

2.2 算法流程

為不失一般性，考慮極小值的優(yōu)化問題，如式(12)所示。f(x)為目標(biāo)函數(shù)，x為決策向量。

算法流程如下所述：

(1)初始化

初始化就是從已知可行域中隨機取一定數(shù)量的點，然后對這些點進行進一步搜索，計算每個粒子的目標(biāo)函數(shù)值，并將目標(biāo)函數(shù)值最優(yōu)的粒子記為xbest。

(2)局部搜索

局部搜索針對單個粒子，用來改進種群中已搜索到的解。它為種群的全局搜索提供了有效的局部信息，使得算法既有全局搜索能力，又有局部區(qū)域精細搜索能力。當(dāng)只對當(dāng)前最優(yōu)粒子進行局部搜索時，能較好地維持速度和精度的平衡。

(3)計算合力

模擬電磁理論的疊加原理，EMA通過計算合力來決定粒子的下一步走向。粒子i的電荷量qi決定了此粒子所受吸引力或排斥力的大小，電荷量qi的計算如式（13）所示，由此可知，目標(biāo)函數(shù)值較優(yōu)的粒子擁有較大的電荷數(shù)，具有更強的吸引力。作用在粒子i上的合力Fi的計算如式（14）所示。每兩個粒子之間，目標(biāo)函數(shù)值較優(yōu)的粒子將吸引另一個粒子，目標(biāo)函數(shù)值較劣的粒子會排斥另外一個粒子。由于當(dāng)前最優(yōu)粒子xbest的目標(biāo)函數(shù)值最優(yōu)，所以它是絕對吸引子，吸引所有其他粒子。

(4)移動系數(shù)[5]

計算移動步長是比較關(guān)鍵的一步，當(dāng)步長較小時，對粒子的擾動較小，因而效果不明顯。針對此情況，可以引入移動系數(shù) k1和 k2，移動公式如式(15)所示，λ 在[0，1]上均勻分布，r表示第r維的分量，這樣每個粒子都可以得到不同程度的更新，且擾動程度較大。k1和k2能明顯地影響算法的收斂速度和解，根據(jù)經(jīng)驗，本文取k1=0.9，k2=1.0。

(5)終止準(zhǔn)則

當(dāng)達到最大迭代次數(shù)時，算法結(jié)束；否則，轉(zhuǎn)到步驟(2)。

3 數(shù)值實驗分析

某貨物供應(yīng)商有3個車場，且每個車場有不同類型的車輛，客戶信息如表1所示，車場信息如表2所示。每輛車的最大配送里程為120 km。

表1 客戶信息表

表2 車場位置信息表

本文中的實驗是在 Intel?CoreTMi3 CPU2.53 GHz、內(nèi)存2.0 GB的PC機上采用Microsoft Visual C++6.0編程實現(xiàn)，關(guān)聯(lián)系數(shù)由Microsoft Visual C++6.0隨機產(chǎn)生。運行程序30次，某一代迭代例證如表3所示。得到該算法求解本算例的最優(yōu)結(jié)果如表4所示，配送示意圖如圖1所示。

表3 迭代例證

表4 最優(yōu)配送方案

本文考慮關(guān)聯(lián)運輸調(diào)度問題的一種擴展特征——多車場多車型模型，并引入了移動系數(shù)，對傳統(tǒng)的移動粒子步長進行改進，相當(dāng)于對粒子添加擾動，使移動步長更為明顯，從而增加了解空間的多樣性。實驗證明，改進的類電磁機制算法求解此類問題是有效可行的，而且具有更快的收斂速度，并得到了更優(yōu)解。接下來可以將EMA運用到MDVRP、VRPTW、AVRP等模型中。

[1]韓麗霞，王宇平.求解無約束優(yōu)化問題的類電磁機制算法[J].電子學(xué)報，2009，37（3）：29-31.

[2]王曉娟，高亮，陳亞洲.類電磁機制算法及其應(yīng)用[J].計算機應(yīng)用研究，2006，23（6）：67-70.

[3]韓麗霞，王宇平，蘭紹江.基于模式搜索的類電磁算法求解約束優(yōu)化問題[J].系統(tǒng)工程與電子技術(shù)，2009，31（9）：2219-2222.

[4]尚云，何雪妮，雷虹.求全局最優(yōu)的類電磁機制算法[J].計算機應(yīng)用，2010，30（11）：2914-2916.

[5]高亮，王曉娟，魏巍，等.一種改進的類電磁機制算法[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2006，34（11）：4-6.