約束滿足型智能規(guī)劃算法研究

蔣 敏，張立行，魏振華

(火箭軍工程大學(xué)，西安 710025)

約束滿足型智能規(guī)劃算法研究

蔣 敏，張立行，魏振華

(火箭軍工程大學(xué)，西安 710025)

為解決約束滿足型任務(wù)規(guī)劃問(wèn)題具有約束條件多、計(jì)算復(fù)雜的問(wèn)題，建立了約束滿足型任務(wù)規(guī)劃模型，根據(jù)模型特點(diǎn)，借鑒遺傳算法和禁忌搜索算法的優(yōu)缺點(diǎn)，對(duì)遺傳算法進(jìn)行改進(jìn)，通過(guò)把遺傳算法和禁忌搜索算法進(jìn)行融合，形成了遺傳禁忌搜索融合算法，通過(guò)對(duì)比分析進(jìn)行性能比較，顯示該算法能夠顯著地提高計(jì)算效率，減少計(jì)算成本，是解決約束滿足型任務(wù)規(guī)劃的高效可行的智能算法。

約束滿足型；智能規(guī)劃；進(jìn)化算法；GTSA

0 引言

約束滿足型問(wèn)題(constraint satisfaction problem, CSP)是計(jì)算機(jī)科學(xué)和人工智能研究的核心問(wèn)題之一，日常生活中的組合優(yōu)化、車間調(diào)度問(wèn)題都可描述為約束滿足型問(wèn)題[1]，該問(wèn)題包含許多相互關(guān)聯(lián)的活動(dòng)，其中每個(gè)工序都有確定的持續(xù)時(shí)間和給定的資源需求，資源的數(shù)量是有限的，會(huì)隨著時(shí)間而變化[2-3]。資源之間存在差異性，不能完全相互替代。該類型問(wèn)題的解是在滿足各個(gè)活動(dòng)的前后約束和資源約束條件下，確定項(xiàng)目中各個(gè)活動(dòng)的開(kāi)始時(shí)間和對(duì)應(yīng)資源，使得該問(wèn)題在某項(xiàng)要求的指標(biāo)上達(dá)到最優(yōu)[4-5]。

約束滿足型任務(wù)規(guī)劃問(wèn)題(constraint satisfaction and mission plan problem，CSMPP)可以看成約束滿足型問(wèn)題和任務(wù)規(guī)劃的組合，即要求滿足所有約束條件下的任務(wù)完成目標(biāo)取得最優(yōu)值[6-8]。約束滿足型任務(wù)規(guī)劃問(wèn)題本身具有約束條件多、計(jì)算復(fù)雜的特點(diǎn)。同時(shí)，由于任務(wù)規(guī)劃需要考慮眾多約束條件，求最優(yōu)解變得非常困難。解決任務(wù)滿足型規(guī)劃問(wèn)題必須首先解決處理約束條件和表達(dá)規(guī)劃結(jié)果兩個(gè)問(wèn)題[9-12]：

1) 處理約束條件。由于進(jìn)化算法對(duì)所研究問(wèn)題約束條件的處理能力有限，主要依賴于適應(yīng)度計(jì)算。因此必須給予約束條件合適的表達(dá)形式，并將其很好地融入算法。

2) 表達(dá)規(guī)劃結(jié)果。對(duì)于不同的算法，特別是融合算法，需要尋找合適的規(guī)劃結(jié)果(也就是路徑群落)的表示方式。一方面有助于路徑群落的初始化，提高算法效率；同時(shí)能為進(jìn)化算法提供啟發(fā)知識(shí)，避免搜索的盲目性。

目前對(duì)約束滿足型任務(wù)規(guī)劃問(wèn)題的優(yōu)化方法主要有：網(wǎng)絡(luò)圖法、數(shù)學(xué)規(guī)劃方法、啟發(fā)式優(yōu)化方法、智能優(yōu)化方法[13]。從上述文獻(xiàn)中得知：項(xiàng)目任務(wù)數(shù)目越龐大，任務(wù)間邏輯關(guān)系越復(fù)雜的問(wèn)題越顯示出遺傳算法的尋優(yōu)效率，但遺傳算法執(zhí)行到一定階段后向最優(yōu)解的收斂速度緩慢?；谏鲜隹紤]，為了更好地解決約束滿足型任務(wù)規(guī)劃問(wèn)題，本文采用GTSA方法對(duì)問(wèn)題進(jìn)行研究。

1 約束規(guī)劃問(wèn)題建模

一個(gè)典型的約束滿足型任務(wù)規(guī)劃問(wèn)題可以描述成一個(gè)三元組P={B,Z,Y}。

其中：B為變量集，B={b1,b2,…,bn}。

Z為任務(wù)值域集，Z={z1,z2,…,zn}，zi為變量vi的值域。

Y為約束條件集，Y={y1,y2,…,ym}，每個(gè)約束zj與B的一個(gè)子集相關(guān)，即yj=表示一個(gè)約束關(guān)系，其中bsub是約束中包含的變量，bsub=bj1×bj2×…×bjn；R是與變量相關(guān)的值域；R=zj1×zj2×…×zjn，即每個(gè)約束關(guān)系確定了它所涉及的變量定義域笛卡爾積的一個(gè)子集。約束體現(xiàn)了變量集合中各變量之間的邏輯關(guān)系，限制了變量的可能賦值。

2 智能規(guī)劃求解算法

2.1 遺傳禁忌搜索融合策略

遺傳禁忌搜索融合策略主要包括兩個(gè)部分內(nèi)容：首先，遺傳禁忌搜索融合策略機(jī)制上的有效融合。遺傳算法本質(zhì)上為概率分布的智能優(yōu)化算法，適應(yīng)度大的個(gè)體將以較大的概率進(jìn)行下一次循環(huán)操作，進(jìn)而實(shí)現(xiàn)對(duì)全局的優(yōu)化，但也容易陷入局部最優(yōu)；而禁忌搜索算法通過(guò)禁忌表來(lái)實(shí)現(xiàn)狀態(tài)間的替換操作，具有一定的突跳性，可有效避免搜索過(guò)程中陷入局部最優(yōu)，但搜索效率較低，全局搜索能力較差。對(duì)遺傳禁忌兩種算法進(jìn)行機(jī)制上有效的融合，可增強(qiáng)全局搜索能力，也能夠增強(qiáng)局部搜索能力。其次，將遺傳算法與禁忌搜索算法有效結(jié)合，呈串行結(jié)構(gòu)，可以有效提高搜索速度，遺傳算法的遺傳操作得到的可行解能夠提供禁忌搜索算法較好的初始解，使得算法具有更好的爬山能力；與此同時(shí)，禁忌搜索算法生成的可行解能夠優(yōu)化遺傳算法中的種群質(zhì)量，使得算法搜索速度更快。

由此可見(jiàn)，在理論上遺傳禁忌搜索相融合所形成的GTSA算法具有更好的全局搜索和局部搜索能力，是一種比遺傳算法和禁忌搜索算法更佳的融合算法。

2.2 遺傳禁忌搜索融合算法

根據(jù)以上分析，能夠得到遺傳禁忌搜索算法的實(shí)現(xiàn)步驟，如圖1所示，具體如下：

1)隨機(jī)產(chǎn)生一個(gè)初始種群P(0)，種群規(guī)模為N，禁忌表設(shè)為φ。

圖1 遺傳禁忌搜索算法流程框圖

2)計(jì)算P(k)里各個(gè)個(gè)體適應(yīng)度。

3)判斷是否滿足相應(yīng)的收斂準(zhǔn)則，如果滿足收斂準(zhǔn)則，輸出相應(yīng)結(jié)果；如果不滿足收斂準(zhǔn)則，轉(zhuǎn)到4)。

4)令m=0。

5)比較適應(yīng)度大小，通過(guò)概率進(jìn)行遺傳操作，在P(k)里選擇兩個(gè)染色體。

6)如果此時(shí)的交叉概率Pc>ξ∈[0,1]，那么對(duì)所選染色體進(jìn)行交叉操作，并生成兩個(gè)臨時(shí)染色體；相反，則將選擇的父代染色體作為臨時(shí)染色體。

7)以變異概率Pm對(duì)臨時(shí)染色體進(jìn)行變異操作，生成的新染色體置于P(k+1)中，且令m=m+2。

8)如果m

9)運(yùn)用鄰域函數(shù)計(jì)算當(dāng)前解的全部鄰域解，生成鄰域解集，而后根據(jù)需求確定一定的候選解。

10)判斷生成的候選解能否滿足特赦準(zhǔn)則。若能滿足，那么用此解作為當(dāng)前解，并更替初始禁忌表中的禁忌對(duì)象，并生成當(dāng)前最優(yōu)解，而后跳轉(zhuǎn)至2)；相反，則跳轉(zhuǎn)至11)。

11)判斷相應(yīng)候選解集所對(duì)應(yīng)的禁忌屬性，將解集中的非禁忌對(duì)象所對(duì)應(yīng)的最優(yōu)狀態(tài)作為新的當(dāng)前解，且用相應(yīng)的禁忌對(duì)象更替初始禁忌表中的相應(yīng)元素，并跳轉(zhuǎn)至2)。

3 對(duì)比分析

為了檢驗(yàn)本文提出的GTSA算法的優(yōu)越性，運(yùn)用car和rec類Flow Shop調(diào)度中的15個(gè)典型問(wèn)題[14-15]使GTSA與GA、TS算法展開(kāi)對(duì)比分析。各參數(shù)設(shè)置如下：初始種群規(guī)模：300，交叉概率：Pc=0.9，變異概率：Pm=0.01，迭代次數(shù)：MaxGen=300，計(jì)算次數(shù)：Num=3；最大循環(huán)次數(shù)：H=100，W2=1，tmin=5，tmax=10。計(jì)算結(jié)果如表1所示。

從以上結(jié)果能夠看出：GTSA算法普遍優(yōu)化質(zhì)量較高，從圖2與圖3可以看出，在Car與Rec類問(wèn)題上，GTSA算法最終計(jì)算的結(jié)果以及各類偏差情況均要好于GA，且對(duì)于絕大部分問(wèn)題而言，GTSA算法的BRE、WRE、ARE值均較小，這也證明GTSA算法具有更好的魯棒性；在求解所需時(shí)間上，GTSA算法也明顯優(yōu)于TS與GA算法，如圖4所示。因此，本文所設(shè)計(jì)的GTSA算法是一種性能優(yōu)良的求解約束規(guī)劃問(wèn)題的算法。

表1 3種調(diào)度算法的計(jì)算結(jié)果

注： C*為問(wèn)題的最優(yōu)解；BRE為最大偏差；WRE為最小偏差；ARE為平均偏差。

表2 3種不同算法對(duì)Car 和Rec類問(wèn)題的偏差平均值

表3 不同算法消耗時(shí)間平均值

圖2 3種不同算法優(yōu)化Car和Rec問(wèn)題的最小偏差

圖3 3種不同算法優(yōu)化Car和Rec問(wèn)題的平均偏差

圖4 不同算法消耗時(shí)間比較

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

本文主要研究了約束滿足型任務(wù)規(guī)劃智能算法。首先分析了約束滿足型任務(wù)規(guī)劃問(wèn)題及相關(guān)算法存在的不足之處，然后，建立了約束滿足型任務(wù)規(guī)劃模型，根據(jù)模型特點(diǎn)，借鑒遺傳算法和禁忌搜索算法的優(yōu)缺點(diǎn)，對(duì)遺傳算法進(jìn)行改進(jìn)，通過(guò)把遺傳算法和禁忌搜索算法進(jìn)行融合，形成了遺傳禁忌搜索融合算法，通過(guò)對(duì)比分析進(jìn)行性能比較，顯示該算法能夠顯著的提高計(jì)算效率，減少計(jì)算成本，可應(yīng)用于任務(wù)規(guī)劃領(lǐng)域，是解決約束滿足型任務(wù)規(guī)劃問(wèn)題的高效可行的智能算法。

[1]王秦暉. 約束滿足及其分布式求解和應(yīng)用研究[D]. 北京：中國(guó)科學(xué)技術(shù)大學(xué), 2013.

[2]邢立寧，陳英武. 任務(wù)規(guī)劃系統(tǒng)研究綜述[J]. 火力與指揮控制，2011, 31(4): 15-18.

[3]楊輕云. 約束滿足問(wèn)題與調(diào)度問(wèn)題中離散粒子群算法研究[D].長(zhǎng)春：吉林大學(xué), 2011.

[4]王 凌. 車間調(diào)度及其遺傳算法[M].北京: 清華大學(xué)出版社, 2008.

[5]孫自廣. 基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J]. 自動(dòng)化與儀表，2009(06): 5-7.

[6]金希東. 李 治. 遺傳-災(zāi)變算法及其在神經(jīng)網(wǎng)絡(luò)和控制系統(tǒng)中的應(yīng)用[J]. 控制理論與應(yīng)用，2012，12(3)：255-260.

[7]王麗薇. 遺傳算法的收斂性研究[J]. 計(jì)算機(jī)學(xué)報(bào)，2013，10(6), 794-797.

[8]張超勇. 基于自然啟發(fā)式算法的作業(yè)車間調(diào)度問(wèn)題理論與應(yīng)用研究[D]. 武漢：華中科技大學(xué), 2010.12.

[9]姚倡鋒. 復(fù)雜零件異地協(xié)同制造資源優(yōu)化配置技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2012.

[10]胡慶夕. 并行環(huán)境下基于層次與特征技術(shù)的設(shè)備資源模型研究[J]. 中國(guó)機(jī)械工程，2014，10(11)：1231-1234.

[11]朱啟林，甘 泓，游進(jìn)軍,等. 基于規(guī)則的水資源配置模型應(yīng)用研究[J]. 水利水電技術(shù). 2009,4(3): 28-32.

[12]劉朝華, 章 兢, 李小花，等. 免疫協(xié)同微粒群進(jìn)化算法的永磁同步電機(jī)多參數(shù)辨識(shí)模型方法[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(10): 1698-1708.

[13]張 浩, 張鐵男, 沈繼紅,等. 混沌粒子群算法及其在結(jié)構(gòu)優(yōu)化決策中的應(yīng)用[J]. 控制與決策, 2010,23(8): 857-862.

[14]王 全. 混合遺傳算法及其改進(jìn)[J]. 安徽建筑工業(yè)學(xué)院學(xué)報(bào): 自然科學(xué)版, 2011,7(4): 59-62.

[15]趙 衛(wèi). 模擬退火遺傳算法在車間作業(yè)調(diào)度中的應(yīng)用[J]. 計(jì)算機(jī)仿真, 2011,28(7): 361-364.

Research on the Constraint Satisfaction Type of IntelligencePlanning Algorithm

Jiang Min, Zhang Lixing, Wei Zhenhua

(College of Rocket Force Engineering University, Xi'an 710025 China,China)

For solving the constraint satisfaction type of mission planning problems is with more constraints and computationally complex, the paper builds the constraint satisfaction type of mission planning model.According to the characteristics of the model, drawing on the advantages and disadvantages of genetic algorithms and tabu search algorithm, genetic algorithm is improved. By genetic algorithm and tabu search algorithm integrated, form the genetic tabu fusion algorithm. According to comparing analysis, it can be shown that the new algorithm can significantly improve the computational efficiency, reduce computing costs, which is feasible and efficient to solve the constraint satisfaction type of mission planning.

constraint satisfaction type; intelligent planning; evolutionary algorithm; GTSA

2016-08-26；

2016-09-10。

蔣 敏(1992-)，女，山東廣饒人，在讀研究生，主要從事通信工程方向的研究。

1671-4598(2016)12-0218-03

10.16526/j.cnki.11-4762/tp.2016.12.063

TN99

A