利用差分模擬退火算法解決漂流調度問題

鄒戰勇，陸 淼，黃煒豪

（廣東商學院 數學與計算科學學院，廣東 廣州 510320）

0 引 言

Big Long River是座落在美國的世界第四長河，游客可以到屬于Big Long River的一段大長河（225英里）領略風光和令人興奮的白色激流。這條河是進不去登山者的，因此觀光只能用的方式是沿河旅行，這需要幾天的露營。所有的沿河旅行都始于第一站并在下游225英里遠的最終出口退出。如何安排一個最優方案使得大長河能容納更多的船只以及船只的相遇次數達到最小是本文研究的目標。Gimblett R［1－2］使 用The Wilderness Use Simulation Model模擬戶外娛樂環境中人類與環境相互作用，該模型被應用到旅行者的使用跟蹤段、越野旅行路線和營地，重點是對相遇次數和活動的潛在沖突進行估計。為了最大化利用露營地，本文設計了一個漂流模擬器。它擴增了河流容納量的同時盡可能減少船只相遇的次數。

為了盡量滿足大量的漂流需求，需要決定河流的最大容納量X′。當然，容納量由旅行的安排方案和Y值共同決定，同時還需要減少兩組的相遇，這是一個多約束的多目標規劃問題。本文將給出普遍適用的優化算法，并對于不同的Y值和旅行時間，都能求出最優安排方案，使得X′達到最大，同時相遇最少。

1 模型和算法

1.1 模型的建立

根據問題分析，我們知道這是一個多約束的目標規劃問題。第一目標是使得X′達到最大，第二目標是相遇最少，并滿足相應的約束條件。但與一般的規劃問題不同的是，影響目標的因素（旅行時間、船速和每天的航行時間）存在一定的隨機不確定性。這就產生了一個非常巨大的解空間，而我們則需要在這個解空間里面尋找最優方案使得X′最大。因此我們可以運用蒙特卡洛模擬產生解空間，并利用屬于智能搜索的模擬退火算法進行求解。

為了允許更多的旅行數量，設目標函數為：

約束條件：

（1）同一組露營者不能在同一個露營點露營超過一晚。

（2）兩組露營者不能同時占領同一個露營點。

根據以上的約束條件，建立以下目標規劃模型：

其中

Sd：第d天出發的船的總數，d＝1，2，3…18

sd，i：第d天i晚旅行出發的船的數量，i＝6，7，8…18

s′d，i：第d天i晚旅行出發的船的數量

Pk（ad）：a號船第d天占領第k個露營點，k＝1，2，3…18

1.2 模擬退火算法

模擬 退 火 算 法（Simulated Annealing，SA）［3－4］最 早 由Kirkpatrick等應用于組合優化領域，它是基于Mente－Carlo迭代求解策略的一種隨機尋優算法，其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。模擬退火算法從某一較高初溫出發，伴隨溫度參數的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出并最終趨于全局最優。

算法SA

（1）初始化：初始溫度T（充分大），初始解狀態S（是算法迭代的起點），每個T值的迭代次數L；

（2）對k＝1，…，L做第（3）至第6步；

（3）產生新解S′；

（4）計算增量Δt′＝C（S′）－C（S），其中C（S）為評價函數；

（5）若Δt′＜0則接受S′作為新的當前解，否則以概率exp（－Δt′／T）接受S′作為新的當前解；

（6）如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接受時終止算法；

（7）T逐漸減少，且T－＞0，然后轉第2步。

根據大長河的實際情況，我們設最長的旅行需要18天，故先假設Y＝18。我們用利用蒙特卡洛在MATLAB進行模擬仿真求解。我們這里隨機生成500個6～18天的旅行，并根據模擬退火算法從500個旅行中搜索最優的安排方案，從而求出最大X′＝288，總相遇次數為767。下面三維餅狀圖中，從9%開始逆時針方向的各個數值分別代表6～18天旅行各占X′的比例，可以看出各個時間的旅行所占比例基本持平。

圖1 16～18天旅行各占X′比例的餅狀圖

1.3 差分模擬退火算法

容易看出，并不是所有的組合優化問題都給出令人滿意的解決方案，當問題的解很平緩時，或則很少有局部最優值，模擬退火算法將很快找到最優解或無法爬出來，考慮到模擬退火算法有可能陷入局部最優的狀態（見圖2），我們將借鑒差分進化算法［5－6］。差分進化算法是一種基于群體進化的算法，具有記憶個體最優解和種群內信息共享的特點，即通過種群內個體間的合作與競爭來實現對優化問題的求解，其本質是一種基于實數編碼的具有保優思想的貪婪遺傳算法。

圖2 最優解和局部最優解圖

結合差分進化算法變異的思想和模擬退火算法，我們提出了差分模擬算法。

算法DE

求解非線性函數f（x1，x2，…，xn）的最小值問題，xi滿足：

令xi（t）是第t代的第i個染色體，則xLij≤xij≤xUijj＝1，2，…n

其中，n是染色體的長度，即變量的個數，M為群體規模，tmax是最大的進化代數。

第一步：生成初始種群

在n維空間里隨機產生滿足約束條件的染色體，實施如下措施：

第二步：變異操作

從群體中隨機選擇3個染色體xp1，xp2，xp3（i≠p1≠p2≠p3），則

其中，xp2j（t）－xp3j（t）為差異化向量，η為縮放因子。

根據差分模擬退火算法原理和思想，利用MATLAB編程求解，得到最優方案中X′為320，總相遇次數為925。X′比優化前的結果提高了11%（見圖3和圖4）。

從圖3中可以看到算法DE（optimized result）露營6晚和7晚的旅行團在優化方案中增加得比較明顯，這表明增加時間短的旅行團可以使X′更大。

圖4顯示了算法SA在30s左右時X′就到達最大值，這表明陷入局部最優解的可能性很大。優化后的算法DE雖然收斂速度相對較慢，但是我們可以得到更好的最優解X′，這表明優化后的算法的優異性。

具體的試驗結果是利用算法SA的得到X′和相遇次數分別為288和767，而用算法DE求得X′＝320，總相遇次數為925。這表明優化后的算法DE確實更優！

1.4 穩定性和靈敏度分析

用MATLAB在計算機上模擬了約70次，發現X′集中在305左右。模擬結果表明我們提出的模型和算法是穩定的（見圖5）。

圖5 模型和算法是穩定性圖

我們考慮6～18天的旅行時間服從正態分布，所以用同樣的方法求得此時的最優方案（見圖6），其中X′＝282，總相遇次數為314。結果表明，對于各種旅行時間的分布，算法都具有很強的實用性。

圖6 旅行時間正態分布下的最優方案圖

1.5 相遇次數的最小化

在第一目標的求解中，我們給出了最優的安排方案使得X′最大，并分析了算法的靈敏度和穩定性。下面我們對第二目標（相遇最少）進行分析求解。我們考慮通過合理分配摩托船或橡皮筏或通過調整同一天里不同旅行團的出發順序，來最大限度的減少相遇次數。實際情況中我們發現6～18中平均旅行時間是12晚，如果再把摩托船或橡皮筏的船速結合取平均為6mile／h，則可以求出每組平均每天需要漂流225／（12＊6）＝3.125h。即我們可以把3.125h視為一種整體上的每天漂流時間的平均數，從而為不同的旅行分配合理的摩托船或橡皮筏。

根據不同的旅行時間，我們可以為不同的旅行團安排摩托船或橡皮筏。當旅行團時間為9晚時，平均每天需要漂流25miles，如果用4miles／h的橡皮筏，每天平均至少需要漂流6h。則對于旅行時間為6、7、8、9的組，他們都需要每天平均漂流6h以上，我們可以認為這樣的漂流時間是過長的。所以6～9晚的旅行應該用摩托船。同樣道理，當旅行時間為15晚時，如果用摩托船，則每天平均漂流1.875h，我們認為這樣的漂流時間是過短的。故15～18晚旅行應該用橡皮筏（4miles／h）。故我們根據旅行團的時間得到以下安排：

表1 旅行團安排時間

在該安排方案中，我們首先找出一天內多組出發的情況。對于這一天，我們可以安排旅行時間短的組先出發，并分配合理的船。要使該方案的相遇次數盡量減少，其中原來的相遇次數為816，調整安排后為767，即相遇次數減少了6%。

我們用計算機同樣進行70次模擬（見圖7），平均減少約5%，說明我們的調整方法對一般安排方案的相遇次數都可以到達穩定的減少率。

圖7 模型與算法的穩定性70次模擬圖

2 結論及推廣

本文分別用算法SA和算法DE來求出最大化X′，結果顯示優化后的算法DE優于算法SA，模型和算法對于不同的參數可以重復得到最優方案。并檢驗了在不同假設條件下的結果都沒有對優化的結果有很大改變，數字最優化結果和分析技術的一致性表明求解的結果至少是一個局部最優解。

本文的模型和算法不僅適用于河道漂流問題，也能推廣到公車、火車、飛機等調度問題。對于一般的優化問題，通常都需要從所有方案中尋求最優方案。模擬退火和差分模擬退火算法是一種啟發式的智能算法，對于大規模的優化問題，其優點顯著。

［1］Gimblett R，Roberts C，Daniel T，et al.An intelligent agent based model for simulating and evaluating river trip scenarios along the colorado river in Grand Canyon National Park［M］.In H R Gimblett（Ed.），Integrating GIS and Agent based modeling techniques for Understanding Social and Ecological Processes，Oxford Press，2000：245－275.

［2］Gimblett，H.R.，B.Durnota，R.M.Itami.Spatially explicit autonomous agents for modeling recreation use in complex wilderness landscapes［J］.Complex International Journal，1996（3）：134－140.

［3］Shechter，M.，R.L.Lucus.Simulation of recreational use for park and wilderness management［M］.Johns Hopkins University Press for Resources for the Future，Inc，Washington，D.C.220pp.1978.

［4］Stan，Alexandru－Ioan.Assessing inbound call center scheduling through boots trapping and DGP based monte carlo simulation［J］.Review of Economic Studies ＆Research VirgilMadgearu，2011（3）：234－240.

［5］敖友云，遲洪欽.多目標差分演化算法研究綜述［J］.計算機科學與探索，2009（3）：234－246.

［6］劉明廣.差異演化算法及其改進［J］.系統工程，2005（2）：108－111.