裝備保障資源均衡遺傳算法優(yōu)化與仿真

王建成， 邱 輝， 郭 凱

(1. 裝備學(xué)院 裝備指揮系, 北京 101416； 2.裝備學(xué)院 研究生管理大隊(duì), 北京 101416； 3.61046部隊(duì))

?

裝備保障資源均衡遺傳算法優(yōu)化與仿真

王建成1， 邱 輝2, 3， 郭 凱1

(1. 裝備學(xué)院 裝備指揮系, 北京 101416； 2.裝備學(xué)院 研究生管理大隊(duì), 北京 101416； 3.61046部隊(duì))

合理利用裝備保障資源是組織裝備保障活動(dòng)的必然要求，科學(xué)規(guī)劃是裝備保障資源合理利用的基本前提。裝備保障任務(wù)工期內(nèi)對(duì)保障資源需求的波動(dòng)量越小越有利于裝備保障活動(dòng)的高效組織、實(shí)施、管理以及裝備保障效能的提高。資源均衡優(yōu)化是實(shí)現(xiàn)資源需求均衡的重要技術(shù)手段。傳統(tǒng)求解資源均衡問(wèn)題的精確解法和啟發(fā)式優(yōu)化方法在解決這類中大規(guī)模問(wèn)題時(shí)難以奏效，帶修復(fù)算子的遺傳算法能夠在一定程度上克服這些算法存在的缺點(diǎn)，其有效性通過(guò)獲得幾個(gè)模擬問(wèn)題的最優(yōu)或次最優(yōu)解得以驗(yàn)證。

資源均衡；裝備保障；遺傳算法；網(wǎng)絡(luò)計(jì)劃

裝備保障資源是裝備保障活動(dòng)的重要物質(zhì)基礎(chǔ)，裝備保障活動(dòng)對(duì)保障資源需求的波動(dòng)量越小越有利于裝備保障活動(dòng)的組織、實(shí)施、管理以及裝備保障效能的提高。資源均衡優(yōu)化是實(shí)現(xiàn)資源需求均衡的重要技術(shù)途徑[1]和進(jìn)行裝備保障任務(wù)規(guī)劃計(jì)劃的重要環(huán)節(jié)，其目標(biāo)是通過(guò)合理安排各道工序，從而盡可能地減少任務(wù)工期內(nèi)對(duì)資源使用需求的波動(dòng)。由于資源均衡優(yōu)化是NP(Non-deterministic Polynomial)問(wèn)題，用完全枚舉法求解中規(guī)模資源均衡問(wèn)題時(shí)因搜索空間過(guò)大而難以獲得問(wèn)題的最優(yōu)解。傳統(tǒng)求解這類問(wèn)題的數(shù)學(xué)模型包括整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃和分支定界法等[2-5]，但均因無(wú)法有效解決組合爆炸瓶頸問(wèn)題而僅能用于求解小規(guī)模問(wèn)題。近年來(lái)，遺傳算法(Genetic Algorithms，GA)作為一個(gè)全局隨機(jī)搜索算法[6-8]，具備有效克服組合爆炸問(wèn)題的能力，因而被用來(lái)求解裝備保障資源優(yōu)化問(wèn)題，從而在一定的折中條件下獲得中大規(guī)模資源均衡優(yōu)化問(wèn)題較為滿意的規(guī)劃解。

1 問(wèn)題描述

裝備保障資源均衡優(yōu)化問(wèn)題可以用網(wǎng)絡(luò)圖描述。圖1所示為一項(xiàng)裝備保障任務(wù)的雙代號(hào)網(wǎng)絡(luò)，其中有9道工序和6個(gè)節(jié)點(diǎn)。工序之間具有確定的前導(dǎo)后繼關(guān)系，并且每一對(duì)節(jié)點(diǎn)間的工序數(shù)不超過(guò)1。(i,j)表示節(jié)點(diǎn)i和j之間的一道工序，例如(4, 5)表示工序“G”。所有工序的集合記為W，所有虛工序的集合記為V，工序(i,j)的所有緊前工序的集合記為P(i,j)。

圖1 裝備保障任務(wù)雙代號(hào)網(wǎng)絡(luò)

(1)

(2)

2 帶修復(fù)算子的遺傳算法

遺傳算法實(shí)際上是通過(guò)對(duì)決策變量的迭代操作實(shí)現(xiàn)的。為獲得GA解，首先必須精心設(shè)計(jì)染色體結(jié)構(gòu)。一條染色體由N個(gè)基因組成，每一個(gè)基因?qū)?yīng)一個(gè)決策變量，表示一道工序的計(jì)劃開(kāi)工時(shí)間。簡(jiǎn)單遺傳算法的遺傳算子由選擇、交叉和變異算子構(gòu)成。選擇、交叉和變異算子分別選用賭輪選擇、單點(diǎn)交叉和隨機(jī)變異。由于遺傳算子的作用，一條可行的染色體可能退變?yōu)榉强尚械娜旧w，即非可行解。如果這種情況發(fā)生，就要使用修復(fù)算子對(duì)工序(i,j)的實(shí)際開(kāi)工時(shí)間tAS(i,j)進(jìn)行修復(fù)。迭代過(guò)程中利用修復(fù)準(zhǔn)則對(duì)一條染色體進(jìn)行適時(shí)檢查，當(dāng)發(fā)現(xiàn)該染色體中某一工序在其所有緊前工序還未結(jié)束時(shí)開(kāi)工，即當(dāng)式(3)所給出的不等式成立時(shí)，就表示該染色體為非可行染色體，就應(yīng)該啟動(dòng)修復(fù)算子進(jìn)行染色體修復(fù)。修復(fù)算子強(qiáng)制非法基因值等于工序(i,j)所有緊前工序?qū)嶋H完成時(shí)間的最大值。

(3)

遺傳算法是通過(guò)不斷產(chǎn)生新的個(gè)體、更新當(dāng)前最優(yōu)染色體來(lái)求解最優(yōu)化問(wèn)題的。進(jìn)化過(guò)程中，解的質(zhì)量由適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià)，并且這種評(píng)價(jià)是染色體選擇的前提。對(duì)于工期固定資源規(guī)劃問(wèn)題，工期內(nèi)資源需求量波動(dòng)越小，染色體的適應(yīng)性越強(qiáng)。因此，定義目標(biāo)函數(shù)g(tAS)如式(4)：

(4)

適應(yīng)度函數(shù)f(tAS)可以分別用相對(duì)適應(yīng)度函數(shù)和絕對(duì)適應(yīng)度函數(shù)定義，分別如式(5)和式(6)所示。

(5)

(6)

3 仿真結(jié)果

利用帶修復(fù)算子的遺傳算法求解了2個(gè)仿真算例：一個(gè)小規(guī)模問(wèn)題和一個(gè)中規(guī)模問(wèn)題。算法用Matlab語(yǔ)言實(shí)現(xiàn)。

3.1 小規(guī)模問(wèn)題

表1 小規(guī)模問(wèn)題參數(shù)及CPM結(jié)果

精確解。對(duì)于該小規(guī)模問(wèn)題，可利用完全枚舉法給出問(wèn)題的精確解。取所有關(guān)鍵工序的實(shí)際開(kāi)工時(shí)間為tES(i, j)，將所有非關(guān)鍵工序的實(shí)際開(kāi)工時(shí)間在區(qū)間[tES(i,j) tLS(i, j)]遍歷取值。求解時(shí)需要搜索的解的總數(shù)為1 280，其中非可行解的個(gè)數(shù)為480，可行解的個(gè)數(shù)為800。對(duì)這些可行解，通過(guò)比較其所對(duì)應(yīng)的任務(wù)工期內(nèi)資源需求量方差的大小選擇出最優(yōu)解。其中最好的前10個(gè)精確解如表2所示。對(duì)于最優(yōu)目標(biāo)值2.863 7，存在有6個(gè)最優(yōu)解，如表2的前6行所示。對(duì)這種最優(yōu)解不唯一的優(yōu)化問(wèn)題，傳統(tǒng)的優(yōu)化方法很難奏效。

表2 小規(guī)模問(wèn)題前10個(gè)最優(yōu)精確解

GA解。參數(shù)popSize=20，chromLen=9，PC=0.65，PM=[0.35 0.25]，maxGen=10。采用相對(duì)適應(yīng)度函數(shù)。運(yùn)行進(jìn)化程序10次，所得到的GA解列于表3。與精確解對(duì)比發(fā)現(xiàn)，遺傳算法得到的解中有9個(gè)與表2中的最優(yōu)解一致，這充分表明遺傳算法求解資源均衡優(yōu)化問(wèn)題時(shí)解的質(zhì)量。從表3給出的GA解可見(jiàn)，當(dāng)目標(biāo)值g(tAS)相同時(shí)，遺傳算法可以得到不同的染色體，這充分顯示出遺傳算法在優(yōu)化這類多極值目標(biāo)函數(shù)時(shí)具有隨機(jī)收斂到多個(gè)全局最優(yōu)解的優(yōu)越性能。目標(biāo)值的進(jìn)化曲線如圖2所示。顯而易見(jiàn)，當(dāng)問(wèn)題的規(guī)模較小時(shí)，進(jìn)化過(guò)程迅速向精確解收斂。

表3 小規(guī)模問(wèn)題10次運(yùn)行GA解

圖2 目標(biāo)值進(jìn)化曲線

3.2 中規(guī)模問(wèn)題

圖3 包括17道實(shí)工序和12個(gè)節(jié)點(diǎn)的裝備保障任務(wù)等效雙代號(hào)網(wǎng)絡(luò)

表4 中規(guī)模問(wèn)題參數(shù)及CPM結(jié)果

圖4 中規(guī)模問(wèn)題各工序規(guī)劃的實(shí)際開(kāi)工時(shí)間

圖5 中規(guī)模問(wèn)題工期內(nèi)單位時(shí)間資源需求量

ng(tAS)各工序的實(shí)際開(kāi)工時(shí)間ABC1C2C3DEFGH1H2IJKLMN15.020793950591081821114151515210201825.020793950591081821114151515210201835.020793950591081821114161515210201844.672967860491071821013161515210201855.0207939505910818211141615152102018

4 結(jié) 束 語(yǔ)

本文研究了基于遺傳算法的中小規(guī)模可更新裝備保障資源優(yōu)化問(wèn)題，設(shè)計(jì)了用于修復(fù)非可行染色體的修復(fù)算子，并通過(guò)仿真算例驗(yàn)證了該方法的有效性。對(duì)于中大規(guī)模特別是大規(guī)模問(wèn)題的求解以及實(shí)現(xiàn)初始種群的多樣性方面，仍需進(jìn)一步探索。該方法不僅可用于裝備保障活動(dòng)的規(guī)劃計(jì)劃，對(duì)于其他工作中涉及的同類型資源優(yōu)化問(wèn)題具有普遍的適用性。

References)

[1]歐陽(yáng)紅祥，劉炳勝，李欣.網(wǎng)絡(luò)計(jì)劃多資源均衡優(yōu)化遺傳算法[J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)，2013，35(2):180-182.

[2]左傳友.PERT方法優(yōu)化的導(dǎo)彈技術(shù)準(zhǔn)備流程[J].海軍航空工程學(xué)院學(xué)報(bào)，2008，23(5):569-572.

[3]LEU S S，YANG C H，HUANG J C.Resource leveling in construction by genetic algorithm-based optimization and its decision support system application [J].Automation in Construction，2000，10(1):27-41.

[4]RIECK J，ZIMMERMANN J，GATHER T.Mixed-integer linear programming for resource leveling problems [J].European Journal of Operational Research，2012，221(1):27-37.

[5]馬登武，郭小威，呂曉峰.基于網(wǎng)絡(luò)計(jì)劃技術(shù)的艦載機(jī)航空導(dǎo)彈轉(zhuǎn)運(yùn)流程[J].兵工自動(dòng)化，2010，29(9):48-51.

[6]AHMED B S，NEIL N E.Use of genetic algorithms in resource scheduling of construction projects [J].Journal of Construction Engineering and Management，2004，130(6):869-877.

[7]HEGAZY T.Optimization of resource allocation and leveling using genetic algorithms[J].Journal of Construction Engineering Management，1999，117(3):380-392.

[8]瞿軍，吳文軍，黃全.導(dǎo)彈技術(shù)保障資源均衡優(yōu)化的遺傳算法求解[J].海軍航空工程學(xué)院學(xué)報(bào)，2010，25(2):137-140.

(編輯：李江濤)

Optimization and Simulation of Genetic Algorithm for Equipment Support Resource Equilibrium

WANG Jiancheng1， QIU Hui2,3， GUO Kai1

(1. Department of Equipment Command, Equipment Academy, Beijing 101416, China；2. Department of Graduate Management, Equipment Academy, Beijing 101416, China； 3. 61046 Troops, China)

Reasonable utilization of equipment support resources is necessary when performing equipment support activities and scientific planning is the basic premise for reasonable utilization of the equipment support resource. In the implementation period of equipment support task, the smaller the fluctuation of the support resource demand is, the better the organization, implementation and management of equipment support activities is and this will improve equipment support effectiveness. Resource equilibrium and optimization are key technical approaches to the equilibrium of resource demand. However, traditional precise method and heuristic optimization method are inapplicable to such problems at a mid/large scale. Fortunately, the genetic algorithm with reparative factor can overcome the shortcoming of above algorithms and may be verified in terms of effectiveness by obtaining the optimal or suboptimal solution to several problems of modeling.

resource equilibrium; equipment support; genetic algorithm; network planning

2016-03-02

王建成(1970-)，男，副教授，主要研究方向?yàn)檠b備保障與指揮。wjianch@sohu.com

E91

2095-3828(2016)06-0133-04

A DOI 10.3783/j.issn.2095-3828.2016.06.025