鄒戰(zhàn)勇，陸 淼，黃煒豪

（廣東商學院 數(shù)學與計算科學學院，廣東 廣州 510320）

0 引 言

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

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

1 模型和算法

1.1 模型的建立

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

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

約束條件：

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

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

根據(jù)以上的約束條件，建立以下目標規(guī)劃模型：

其中

Sd：第d天出發(fā)的船的總數(shù)，d＝1，2，3…18

sd，i：第d天i晚旅行出發(fā)的船的數(shù)量，i＝6，7，8…18

s′d，i：第d天i晚旅行出發(fā)的船的數(shù)量

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

1.2 模擬退火算法

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

算法SA

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

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

（3）產(chǎn)生新解S′；

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

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

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

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

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

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

1.3 差分模擬退火算法

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

圖2 最優(yōu)解和局部最優(yōu)解圖

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

算法DE

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

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

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

第一步：生成初始種群

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

第二步：變異操作

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

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

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

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

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

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

1.4 穩(wěn)定性和靈敏度分析

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

圖5 模型和算法是穩(wěn)定性圖

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

圖6 旅行時間正態(tài)分布下的最優(yōu)方案圖

1.5 相遇次數(shù)的最小化

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

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

表1 旅行團安排時間

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

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

圖7 模型與算法的穩(wěn)定性70次模擬圖

2 結(jié)論及推廣

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

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

［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］.系統(tǒng)工程，2005（2）：108－111.