鄧海鑫，艾麗蓉

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710129)

0 引言

現(xiàn)實(shí)世界的優(yōu)化問題往往屬于多目標(biāo)優(yōu)化問題，與單目標(biāo)優(yōu)化不同，多個(gè)相互競(jìng)爭(zhēng)目標(biāo)的優(yōu)化結(jié)果得到的是一組可行解，被稱作Pareto最優(yōu)解集。由于缺少喜好信息，Pareto最優(yōu)解集中找不到一個(gè)解比另一個(gè)解更好［1］。傳統(tǒng)的方法，例如分支定界法、分治法會(huì)得到全局優(yōu)化［2］，但是需要大量的運(yùn)行時(shí)間，或者不能解決實(shí)際問題。如果為了避免這樣的情況而使用傳統(tǒng)的局部搜索方法［3］，則很容易陷入局部?jī)?yōu)化。由于不能改變NP-hard問題的時(shí)間復(fù)雜度，現(xiàn)代啟發(fā)式方法把重點(diǎn)放在避免局部?jī)?yōu)化這樣的問題上，其另一個(gè)特點(diǎn)是推廣性、魯棒性很高。因此，對(duì)于資源包投放優(yōu)化問題這種NP-hard問題，應(yīng)該設(shè)計(jì)更為高效的啟發(fā)式算法來解決它。

資源包投放優(yōu)化問題即如何用最少的資源包滿足更多區(qū)域?qū)τ谫Y源包的需求。資源包投放優(yōu)化問題在現(xiàn)實(shí)活動(dòng)中有著重大的實(shí)際應(yīng)用意義。例如:2008年以來，我國陸續(xù)遭遇百年不遇的冰雪災(zāi)害和慘絕人寰的5·12汶川大地震之后，冰雪災(zāi)害和大地震中，救援包的及時(shí)高效的投放，可以為抗震救災(zāi)的勝利奠定堅(jiān)實(shí)的基礎(chǔ)。通過資源包投放優(yōu)化問題的研究，設(shè)計(jì)合理的優(yōu)化算法，以最快的反應(yīng)能力在災(zāi)害影響的范圍內(nèi)發(fā)放救援包，并使發(fā)放的救援包可以覆蓋最大的區(qū)域。在軍事上資源包的投放優(yōu)化問題也有著重要的應(yīng)用。例如:戰(zhàn)斗機(jī)轟炸目標(biāo)時(shí)，如何用最少的彈藥打擊更多的目標(biāo)是衡量一次戰(zhàn)斗行動(dòng)成功與否的重要標(biāo)準(zhǔn)。通過設(shè)計(jì)高效的優(yōu)化算法，計(jì)算出合理的炸彈投放點(diǎn)，實(shí)現(xiàn)用最少的彈藥完成打擊目標(biāo)的目的，這對(duì)提高國家的國防實(shí)力也有極大的意義。

1 算法設(shè)計(jì)及實(shí)現(xiàn)

為了更高效地運(yùn)用演化算法解決資源包的投放問題，本文方法首先對(duì)目標(biāo)區(qū)域進(jìn)行區(qū)域分類，然后應(yīng)用演化算法，最后對(duì)落點(diǎn)的結(jié)果進(jìn)行線性規(guī)劃求解。區(qū)域分類的目的是將各個(gè)目標(biāo)區(qū)域進(jìn)行劃分從而剔除大部分空白區(qū)域，這樣在各個(gè)小區(qū)域類中應(yīng)用算法求解資源包的落點(diǎn)將更加高效，最后因?yàn)楦鱾€(gè)小區(qū)域類中的落點(diǎn)相互影響著最優(yōu)落點(diǎn)，所以通過線性規(guī)劃再將各個(gè)區(qū)域類中的落點(diǎn)整合成整體的最優(yōu)落點(diǎn)。下面是算法的具體實(shí)現(xiàn)步驟。

1.1 區(qū)域分類

(1)區(qū)域Di和Dj具有關(guān)系R指這2個(gè)區(qū)域?qū)儆谕活?，則可用圖G表示這些區(qū)域和區(qū)域間的關(guān)系，計(jì)算圖G的鄰接矩陣W=(wij)n×n。如果dis(a，b)＜CP(CP在此例中為10)，則 wij=min{dis(a，b)|a∈Di，b∈Dj}，否則 wij=0;其中 dis(a，b)表示 a 和 b兩點(diǎn)間的距離。

(2)利用深度優(yōu)先或?qū)挾葍?yōu)先算法，遍歷圖G，求G的連通分量。

(3)每個(gè)連通分量的頂點(diǎn)集合，作為一類區(qū)域。

通過對(duì)區(qū)域進(jìn)行分類，可以對(duì)每個(gè)區(qū)域類分別使用演化算法，這樣可以極大地縮短實(shí)驗(yàn)程序運(yùn)行的時(shí)間，同時(shí)也可以減少實(shí)驗(yàn)誤差。

1.2 應(yīng)用演化算法

演化算法［7］是基于生物演化思想發(fā)展起來的一類隨機(jī)搜索技術(shù)，它們是模擬由個(gè)體組成群體的學(xué)習(xí)過程，其中每個(gè)個(gè)體表示給定問題搜索空間的一點(diǎn)。演化算法從一個(gè)初始的群體出發(fā)，通過隨機(jī)選擇、變異和重組過程，使群體演化到搜索空間中越來越好的區(qū)域。選擇過程是群體中適應(yīng)性好的個(gè)體比適應(yīng)性差的個(gè)體有更多的復(fù)制機(jī)會(huì)，交叉算子將父輩信息結(jié)合在一起并將它們遺傳到子代個(gè)體，變異保證在群體中產(chǎn)生新的個(gè)體。演化算法這種以生物智能或自然現(xiàn)象為基礎(chǔ)的隨機(jī)搜索算法具有比數(shù)學(xué)規(guī)劃方法更大的優(yōu)越性，使得演化算法已經(jīng)成為人工智能領(lǐng)域的研究熱點(diǎn)。

1.2.1 演化算法的描述

首先用演化算法的數(shù)學(xué)形式描述資源包投放優(yōu)化問題:

設(shè)NP為種群大小，在整個(gè)求解過程中保持不變，不妨設(shè)可行域:D={(x1，x2，…，xn)|xl≤xi≤xh，i=1，2，…，n}，其中 xl與 xh代表每個(gè)個(gè)體可取的分量的范圍，而xi代表種群中某個(gè)個(gè)體的一個(gè)分量。例如:在資源包的投放優(yōu)化問題中每個(gè)分量都是一個(gè)落點(diǎn)的坐標(biāo)。設(shè)x(i)(k)表示第k代種群中第i個(gè)個(gè)體，xj(i)(k)表示這個(gè)個(gè)體的第j個(gè)分量。

第k代種群集合可以表示為:

演化算法的主要操作如下:

(1)建立初始種群。

一般選可行域D上具有統(tǒng)一分布的NP個(gè)偽隨機(jī)數(shù)構(gòu)成初始種群。例如，取:

其中r(i)為［0，1］上均勻分布的隨機(jī)數(shù)。

(2)變異操作。

對(duì)第k代種群中的每一個(gè)個(gè)體，從種群中隨機(jī)抽取3個(gè)不同的個(gè)體x(r)(k)、x(s)(k)、x(t)(k)，通過如下變異操作產(chǎn)生試驗(yàn)向量u(i)(k+1):

其中F∈［0，1］為縮放因子，且一般為固定的，用于控制向量x(r)(k)－x(s)(k)的縮放，從而確定在距點(diǎn)x(t)(k)多遠(yuǎn)位置生成試驗(yàn)向量u(i)(k+1)。

(3)交叉操作。

對(duì)第k代種群G(k)中的每一個(gè)向量x(i)(k)及其變異得到的試驗(yàn)向量u(i)(k+1)做交叉操作，得到第k+1代向量v(i)(k+1)。

如果r≤CR，則 v(i)(k+1)=xi(k)，否則 v(i)jjjj(k+1)=uj(i)(k+1)，其中CR為預(yù)先給定的交叉概率，rj為隨機(jī)生成的［0，1］上的隨機(jī)數(shù)(j=1，2，…，n)。

最后檢查向量v(i)(k+1)是否在可行域D中，即xl≤vj(i)(k+1)≤xh，用［xl，xh］中的隨機(jī)值代替這個(gè)分量，即vj(i)(k+1)=xl+r*(xh－xl)，r為［0，1］上均勻分布的隨機(jī)數(shù)。

(4)選擇操作。

演化算法按照貪婪準(zhǔn)則將當(dāng)前種群中的目標(biāo)向量與由它所產(chǎn)生的試驗(yàn)向量比較，選擇目標(biāo)函數(shù)值較優(yōu)的放入下一代種群，函數(shù)f()為計(jì)算適應(yīng)度的目標(biāo)函數(shù)，如果f(v(i)(k+1))≤f(x(i)(k))，則 x(i)(k+1)=v(i)(k+1)，否則使 x(i)(k+1)=x(i)(k)。

這種選擇方法保證了下一代中所有個(gè)體都不次于當(dāng)前代中對(duì)應(yīng)的個(gè)體。

1.2.2 應(yīng)用演化算法進(jìn)行資源包落點(diǎn)計(jì)算

1.對(duì)演化算法中的各個(gè)參數(shù)進(jìn)行定值，如種群數(shù)目 NP=8，交叉概率 CR=0.6。

2.適應(yīng)度函數(shù)。整個(gè)演化迭代過程總的來說就是搜索最優(yōu)適應(yīng)度個(gè)體的過程，種群個(gè)體為在這個(gè)區(qū)域類中所有資源包投放點(diǎn)的坐標(biāo)，而且投點(diǎn)與落點(diǎn)存在誤差，假設(shè)某個(gè)個(gè)體即染色體內(nèi)的資源包個(gè)數(shù)為m，這個(gè)區(qū)域類中的區(qū)域個(gè)數(shù)為t，采用如下方法計(jì)算出個(gè)體適應(yīng)度。

(1)通過蒙特卡洛算法得出每個(gè)資源包落入?yún)^(qū)域類中第 j個(gè)區(qū)域的概率為 p1j、p2j、…、pmj。

(2)計(jì)算不符合要求的概率值(假設(shè)滿足區(qū)域需求的資源包數(shù)目為3)。

①?zèng)]有資源包落入?yún)^(qū)域的概率為:

②當(dāng)求只有一個(gè)資源包落入該區(qū)域時(shí)的概率可以通過公式表示為:

③當(dāng)求有兩個(gè)資源包落入該區(qū)域時(shí)的概率可以通過公式表示為:

(3)計(jì)算區(qū)域類中某個(gè)區(qū)域滿足資源包落入需求的概率為:pj=1 －v1j－v2j－v3j，其中 j=1，2，…，t。

(4)設(shè)一個(gè)變量count的初值為0，依次比較pj與應(yīng)用中要求的概率P，其中j=1，2，…，t。如果pj大于P，則count自加;最后若count等于t，則此個(gè)體的適應(yīng)度為1，否則適應(yīng)度為count/t。

3.對(duì)每個(gè)區(qū)域類分別使用所描述的演化算法。

1.3 線性規(guī)劃求解

(1)生成各個(gè)區(qū)域類規(guī)劃信息，假設(shè)某個(gè)區(qū)域類中有區(qū)域個(gè)數(shù)k個(gè)，則規(guī)劃信息如表1所示。表1中為在第k個(gè)區(qū)域類中，滿足投放要求的區(qū)域數(shù)為i時(shí)的資源包個(gè)數(shù)。

表1 規(guī)劃信息

(2)對(duì)各個(gè)區(qū)域類進(jìn)行線性規(guī)劃求解，求出當(dāng)滿足從各個(gè)區(qū)域類中取出滿足投放要求的區(qū)域數(shù)之和為6時(shí)，資源包個(gè)數(shù)最少的情況即為實(shí)例的結(jié)果。如共有d個(gè)區(qū)域類，從每個(gè)區(qū)域類中取出的區(qū)域數(shù)的要求為a1+a2+…+ad=value時(shí)(其中a1為從第一個(gè)區(qū)域類中取出的滿足要求的區(qū)域數(shù)，value為總的要求的區(qū)域個(gè)數(shù))的值為最小時(shí)即為所求結(jié)果。

2 實(shí)驗(yàn)結(jié)果及分析

將以上算法應(yīng)用于資源包投放問題的一個(gè)特定的實(shí)例中，實(shí)例如圖1所示。

圖1 實(shí)例圖

在圖1中11個(gè)平面區(qū)域內(nèi)(即目標(biāo)區(qū)域)投放資源包，使得其中6個(gè)平面區(qū)域以不小于概率P獲得所需的資源包數(shù)量，同時(shí)使得所需的資源包數(shù)量盡可能地少(大圓的半徑為30 m，小圓半徑為20 m)。假設(shè)P為0.8，每個(gè)區(qū)域滿足需求的資源包數(shù)目為3，求出滿足條件的最少投放資源包的數(shù)目和其落點(diǎn)。

應(yīng)用前面所設(shè)計(jì)的算法得到的投放信息如圖2所示。

圖2 演化算法投放信息結(jié)果圖

若將上述方法中的演化算法改成傳統(tǒng)的遺傳算法，得到投放信息如圖3所示。

圖3 遺傳算法投放信息結(jié)果圖

通過實(shí)驗(yàn)結(jié)果分析可知，使6個(gè)平面區(qū)域以不小于0.8的概率獲得3個(gè)資源包時(shí)應(yīng)用演化算法后只需要16個(gè)資源包投放點(diǎn)。如果使用遺傳算法得到的結(jié)果將差于演化算法的結(jié)果，大概需要17個(gè)資源包投放點(diǎn)，而且算出結(jié)果的速度也會(huì)非常慢。這是因?yàn)檠莼惴ɡ梅N群中個(gè)體間的差分向量對(duì)個(gè)體進(jìn)行擾動(dòng)，實(shí)現(xiàn)個(gè)體變異，而遺傳算法則是直接對(duì)個(gè)體進(jìn)行變異，其運(yùn)算時(shí)間較長(zhǎng)且收斂較慢，使結(jié)果非常容易向不好的方向變化。

演化算法所具有的內(nèi)含并行性使它能以較少的計(jì)算量獲得較大的收益，而且與傳統(tǒng)搜索算法一般要使用導(dǎo)數(shù)等其它輔助信息相比，演化算法只使用目標(biāo)函數(shù)，并在增加效率和減小開銷之間進(jìn)行權(quán)衡，因此演化算法在處理資源包投放優(yōu)化這類NP-hard問題中非常高效。而區(qū)域分類和線性規(guī)劃更高效地運(yùn)用了演化算法，使資源包投放問題得到了很好的解決。

3 結(jié)束語

本文詳細(xì)介紹了如何運(yùn)用演化算法實(shí)現(xiàn)對(duì)資源包投放的優(yōu)化，使用演化算法處理該問題可以解決使用傳統(tǒng)遺傳算法時(shí)運(yùn)算時(shí)間長(zhǎng)和收斂較慢的缺陷。實(shí)驗(yàn)表明該算法在處理資源包投放問題中是非常高效的，但是演化算法自身存在參數(shù)敏感問題，選用合適的參數(shù)范圍可能要經(jīng)過多次實(shí)驗(yàn)分析，因此設(shè)計(jì)參數(shù)自適應(yīng)的演化算法來處理資源包投放優(yōu)化問題將是下一步的研究重點(diǎn)。

［1］張利彪，周春光，馬銘，等.基于極大極小距離密度的多目標(biāo)微分進(jìn)化算法［J］.計(jì)算機(jī)研究與發(fā)展，2007，44(1):177-184.

［2］劉立英.分支定界法的推廣應(yīng)用［D］.青島:青島農(nóng)業(yè)大學(xué)，2011.

［3］Hakimi S L.Optimum locations of switching centers and the absolute centers and medians of a graph［J］.Operations Research，1964，12(3):450-459.

［4］Mark S Daskin，Edmund H Stern.A hierarchical objective set covering model for emergency medical service vehicle deployment［J］.Transportation Science，1981，15(2):137-152.

［5］Richard Church，Charles ReVelle.The maximal covering location problem［J］.Papers of the Regional Science Association，1974，32(1):101-l18.

［6］張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)(第2版)［M］.西安:西安交通大學(xué)出版社，2003.

［7］劉波，王凌，金以慧.差分進(jìn)化算法研究進(jìn)展［J］.控制與決策，2007，22(7):721-729.

［8］汪彤，李云強(qiáng).基于近鄰策略的旅行商問題求解［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(28):67-68，71.

［9］孟紅云，張小華，劉三陽.用于約束多目標(biāo)優(yōu)化問題的雙群體差分進(jìn)化算法［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31(2):228-235.

［10］吳亮紅，王耀南，周少武，等.雙群體偽并行差分進(jìn)化算法研究及應(yīng)用［J］.控制理論與應(yīng)用，2007，24(3):453-458.

［11］江雷，陳賢富.一種衡量TSP問題種群多樣性的新方法［J］.微電子學(xué)與計(jì)算機(jī)，2004，21(8):10-12.

［12］陶利民，郭俊恩.改進(jìn)遺傳算法在求解TSP問題上的應(yīng)用研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(33):45-47.

［13］張啟義，邱國慶，寇學(xué)智，等.兩階段遺傳算法在求解TSP問題中的應(yīng)用［J］.解放軍理工大學(xué)學(xué)報(bào):自然科學(xué)版，2011，12(1):79-83.