余 馨，陳 云，俞旭燕

（徐州工程學院 a. 金融學院； b. 信息工程學院， 江蘇 徐州 221018）

現(xiàn)有一種“穿越沙漠”游戲：玩家可根據(jù)一張地圖，在沙漠中從起點出發(fā)行走至終點，沙漠中有晴朗、高溫、沙暴三種天氣情況，玩家可利用初始資金購買一定數(shù)量的水和食物，也可在礦山、村莊補充資金或資源，最后在規(guī)定的時間內(nèi)到達沙漠終點，并盡可能保留更多的資金。整個游戲共六個關(guān)卡，每個關(guān)卡的參數(shù)設定、天氣狀況、路線地圖都不相同[1]。本文擬對2020 年全國大學生數(shù)學建模大賽B 題“穿越沙漠”中的最大資金剩余量問題進行研究。

1 解決問題一的動態(tài)規(guī)劃算法

賽題一包括第一關(guān)和第二關(guān)，在規(guī)定的時段內(nèi)每天天氣狀況事先全部已知。

1.1 動態(tài)規(guī)劃與狀態(tài)轉(zhuǎn)移

動態(tài)規(guī)劃的前提是狀態(tài)轉(zhuǎn)移。在沙漠行走，離不開水和食物資源。玩家在每天的資源保有量基礎上做決策，將決定下一天的資源剩余量，形成狀態(tài)轉(zhuǎn)移。

玩家選擇停留、行走或挖礦，對資源的消耗量分別是基礎量的 1、2、3 倍，故設 i=1，2，3，xki∈（1，0）表示第 k 天對 i 的選擇與否。

記αj、βj（j=1，2，3）為晴朗、高溫、沙暴天氣對水和食物的基礎消耗量，ykj∈（1，0）表示第 k 天是否為第j 種天氣，這均為已知參數(shù)[1]。

又設A、B 為在起點購買水和食物的數(shù)量，ak、bk為第k 天在村莊購買水和食物的數(shù)量。

計算第n 天水和食物的剩余量Sn和Wn：

在時間遞增的情況下，可運用式（1）、（2）不斷更新玩家所處位置并計算下一天水和食物的保有量。

1.2 已知天氣狀態(tài)的最大資金剩余量模型

變量設置：f 表示剩余資金量；T 表示從起點到終點的歷時天數(shù)，t 表示挖礦天數(shù)；其他設置同1.1 節(jié)。

目標函數(shù)為資金剩余量：

優(yōu)化方向為max f。其中：f0=10 000 元為初始資金，c 為給定的挖礦基礎收益，d=10 表示在村莊補充資源需支付基準價格2 倍的資金。

在問題一中，c=1 000 元/天。

根據(jù)游戲規(guī)則[1]設置約束條件：

體現(xiàn)資源不能耗盡。要求恰在終點處耗盡，即ST=WT=0，有利于最大化f max。

體現(xiàn)負重上限約束。初始時刻也受此約束，而達到3A+2B=1 200 可對f max 提供保障。

體現(xiàn)0-1 變量的單一選擇性，以及沙暴天氣不能行走。

體現(xiàn)所耗時間的限制。問題一中T0=30 天。

1.3 第一關(guān)的求解

30 天內(nèi)天氣狀態(tài)已知[1]，玩家選擇的行走狀態(tài)分成3 種：停留、行走和挖礦。用動態(tài)規(guī)劃求解第一關(guān)，需建立狀態(tài)轉(zhuǎn)移方程[2]。

方程中的變量解釋：time 為時間，time-1 為前一時刻的時間狀態(tài)，v 表示水與食物的質(zhì)量，i 為水的消耗量，j 為食物的消耗量。Need 為消耗，_s表示水的屬性，_w 表示食物屬性，s′為增加的水質(zhì)量，w′為增加的食物質(zhì)量。下面分不同情況建立四維DP 狀態(tài)轉(zhuǎn)移方程。

第一種情況，天氣不是沙暴時選擇行走：

表示下一時刻的水與食物的消耗量在前一時刻水消耗量的基礎上增加兩倍基礎消耗。

第二種情況，路過村莊時玩家選擇補給水與食物：

表示所耗資金為原先兩倍，時間不增加。其中增加的補給量為負數(shù)，消耗量為正數(shù)。

第三種情況，路過礦山時，選擇挖礦：

表示當天不能挖礦，下一狀態(tài)停留在原地，并獲基礎收益。

第四種情況，停在原地：

此時，只有一倍基礎消耗，時間增加，位置不轉(zhuǎn)移。

運用Java 進行編譯，運算結(jié)果如表1 所示。最大資金剩余量為10 470 元。具體行走路徑如圖1 所示。

圖1 第一關(guān)的具體路徑

表1 第一關(guān)的部分運算結(jié)果

運算結(jié)果顯示，玩家從出發(fā)到終點耗時24天。其中晴天出現(xiàn)7 次，6 次選擇行走；高溫天氣出現(xiàn)12 次，5 次選擇挖礦；沙暴天氣出現(xiàn)5 次，其中1 次選擇挖礦（沙暴天氣必停，但可挖礦），4 次選擇停留。

1.4 第二關(guān)的求解

第二關(guān)地圖[1]的區(qū)域排列類似于矩形分布，從起點1 到礦山30 的最短路徑需要走7 步。由相鄰區(qū)域的交換律可知，固定步數(shù)時，7 塊相鄰區(qū)域等效，故可剔除以下屬于冗雜多余的區(qū)域：

3，4，5，6，7，8，11，12，13，14，15，16，20，21，22，23，24，31，32。

起點到村莊需要8 步，故刪除以下區(qū)域：

17，25，33，34，41，42，49，50，51，57，58，59。

村莊到終點刪去繞行區(qū)域：40，48。

運用1.3 節(jié)的狀態(tài)轉(zhuǎn)移方程，代入目標函數(shù)，運用Java 進行編譯，運算結(jié)果如表2 所示，最大資金剩余量為12 730 元。具體行走路徑如圖2所示。

圖2 第二關(guān)的具體路徑

表2 第二關(guān)的部分運算結(jié)果

玩家的策略為：礦山較遠，挖礦前要補資源，所以先到村莊，后到礦山。挖礦6 天折返回村莊又補資源，再經(jīng)2 步到第二座礦山挖礦7 天，然后2步到達終點。

2 解決問題二的遺傳算法

問題二包括第三關(guān)和第四關(guān)，玩家僅知道當天的天氣狀況，可據(jù)此決定當天的行動方案。

2.1 馬爾科夫鏈天氣預測模型

根據(jù)當天的天氣狀況，可利用馬爾科夫鏈模型預測未來的天氣狀況。

以不出現(xiàn)沙暴的第三關(guān)[1]為例。設當天為晴天時，下一天是晴天和高溫的概率分別為p 和1-p；當天為高溫時，下一天是高溫和晴天的概率分別為 p′和 1-p′，則稱

為一階狀態(tài)轉(zhuǎn)移概率矩陣。其中的概率值滿足0.1的梯度下降規(guī)則，即

若初始的狀態(tài)概率分布為P0，則n 天后的狀態(tài)概率分布為Pn=QnP0。當n 趨向于無窮時，Pn趨于恒定。這表明，用馬爾科夫鏈對天氣狀態(tài)進行預測，與初始狀態(tài)無關(guān)。

2.2 問題二的最大資金剩余量模型

問題二的優(yōu)化模型與問題一相同，仍為式（1）～（7），只是部分已知參數(shù)有所不同[1]：第三關(guān)的挖礦基礎收益為c=200 元/天，行走限時為T0=10天；第四關(guān)則仍為 c=1 000 元/天，T0=30 天。

此外，第三關(guān)的地圖中有礦山但沒有村莊，故只針對資金進行補充，不考慮資源補給，即所有的ak=bk=0；第三關(guān)不出現(xiàn)沙暴天氣，所有yk3=0，涉及的下標僅取j=1，2 即可。

2.3 第三關(guān)的求解

先用Java 模擬出不同概率下設定的1 000 組數(shù)值解，多次嘗試之后得出各種結(jié)果，再用遺傳算法[3-4]，搜索出不同組中10 日天氣情況不同的最優(yōu)資金剩余量[5]。遺傳算法的具體過程如下。

Step1：編碼方案

行為狀態(tài)的染色體個體為三進制串，以0、1、2分別表示停留、行走和挖礦。天氣狀態(tài)的染色體個體為二進制串，以0、1 分別表示晴天和高溫。

Step2：種群初始化

隨機生成1 000 組染色體，根據(jù)梯度下降原理，設定晴朗天氣出現(xiàn)的概率為不同的p，高溫天氣則為對應的1-p。

具體以p=0.7 為例，利用馬爾科夫預測模型[6-7]求解10 日內(nèi)不同天氣的數(shù)學期望。

Step3：初始群體的確定

種群規(guī)模N=1 000，交叉概率Pc=0.9，變異概率Pm=0.1，迭代次數(shù)m=1 000；

本文所選取的初始化群體為Java 在限定區(qū)間內(nèi)隨機模擬生成。按照這種解法，可以選出1 000 組個體組成解。

Step4：適應度函數(shù)

適應度函數(shù)即目標函數(shù)（3）。計算隨機模擬的1 000 組天氣狀況下的最大資金保留量，計算每個個體的適應值Fitness 相當于通過自變量求得適應度函數(shù)的值，然后判斷是否應刪除質(zhì)量差的個體。

Step5：約束檢驗

檢驗約束條件（4）～（7），剔除不合格的行為狀態(tài)。

Step6：評價個體適應度

對不同組天氣狀態(tài)所生成的二進制串和人的行為方式進行解碼處理，可得到不同天氣狀態(tài)下的表現(xiàn)型，由個體表現(xiàn)型計算對應個體的目標函數(shù)值。根據(jù)適應度函數(shù)最大的條件，求出個體適應度。

Step7：選擇函數(shù)

運用最佳保留選擇，隨機概率設定為0.95。將當前種群中適應度最高的個體放到下一種群中。

Step8：個體的交叉與變異

從染色體串中選擇NPc 個個體進行交叉選項，本文交叉方法為部分染色體段進行交叉，并檢查交叉結(jié)果是否滿足合法性，即在不同天氣狀態(tài)下玩家所對應的方式能否正確表示，若不符合則再次交叉或取消該操作。

Step9：循環(huán)

變異是根據(jù)變異概率更改染色體串中某個值使之變?yōu)椴煌鞖鉅顟B(tài)和人的行為狀態(tài)。

完成交叉變異后，代入適應度函數(shù)，選擇再生個體，適應度高的個體即剩余資金留用數(shù)量高的被留下，一直進行循環(huán)。

Step10：終止計算

滿足停止準則時終止計算，輸出最優(yōu)結(jié)果。

運用遺傳算法進行具體運算[8]，設置初始晴天出現(xiàn)的概率為0.7。迭代1 000 次后最大資金剩余量為9 189，4 天的天氣情況為“高溫，高溫，高溫，晴朗”。

考慮是否要挖礦：挖礦需繞道兩天，至少多付出 55×2×2 ＝220 元（晴天），而挖礦一天收益最多為200－55×3 ＝35 元（晴天），10 天中至多有5 天可以挖礦，獲得收益的上限為35 × 5 ＝175元。由于收益小于付出，所以放棄挖礦。第三關(guān)的具體行走路徑如圖3 所示。

圖3 第三關(guān)的具體路徑

綜上，一般情況下第三關(guān)玩家的最佳策略為：晴天必行走，出現(xiàn)高溫則停留，若連續(xù)兩天都是高溫，則用馬爾科夫鏈分析第三天的天氣情況，經(jīng)狀態(tài)轉(zhuǎn)移概率計算[9-10]，當?shù)谌烨缋矢怕食^高溫50 %時選擇行走，否則繼續(xù)停留。

2.4 第四關(guān)的求解

第四關(guān)既有礦山，也有村莊，且出現(xiàn)沙暴天氣的概率較小[1]。求解方法與第三關(guān)相仿。

設置初始沙暴出現(xiàn)概率為0.1（較低值），運用Java 仿真模擬，沙暴出現(xiàn)的概率為0.1～0.4，依據(jù)收益的數(shù)學期望，經(jīng)遺傳算法求解，得到最大資金剩余量為1 1265 元，8 天的天氣情況為“沙暴3天，晴朗 4 天，高溫 1 天”。

分析求解結(jié)果，可得最佳策略：晴朗必走，出現(xiàn)高溫適合停留，若連續(xù)出現(xiàn)高溫天氣，第一天選擇停留，根據(jù)貝葉斯概率分布可得未來一天各種天氣出現(xiàn)的概率，若出現(xiàn)高溫天氣的概率超過0.64 則停留，若低于0.64 則行走，遇沙暴時停留，有礦山則挖礦。