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

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

0 引 言

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

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

1 模型和算法

1.1 模型的建立

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

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

約束條件：

（1）同一組露營(yíng)者不能在同一個(gè)露營(yíng)點(diǎn)露營(yíng)超過(guò)一晚。

（2）兩組露營(yíng)者不能同時(shí)占領(lǐng)同一個(gè)露營(yíng)點(diǎn)。

根據(jù)以上的約束條件，建立以下目標(biāo)規(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號(hào)船第d天占領(lǐng)第k個(gè)露營(yíng)點(diǎn)，k＝1，2，3…18

1.2 模擬退火算法

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

算法SA

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

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

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

（4）計(jì)算增量Δt′＝C（S′）－C（S），其中C（S）為評(píng)價(jià)函數(shù)；

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

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

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

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

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

1.3 差分模擬退火算法

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

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

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

算法DE

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

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

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

第一步：生成初始種群

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

第二步：變異操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 旅行團(tuán)安排時(shí)間

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

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

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

2 結(jié)論及推廣

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

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

［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］敖友云，遲洪欽.多目標(biāo)差分演化算法研究綜述［J］.計(jì)算機(jī)科學(xué)與探索，2009（3）：234－246.

［6］劉明廣.差異演化算法及其改進(jìn)［J］.系統(tǒng)工程，2005（2）：108－111.