蔣 敏，張立行，魏振華

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

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

蔣 敏，張立行，魏振華

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

2.1 遺傳禁忌搜索融合策略

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

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

2.2 遺傳禁忌搜索融合算法

根據以上分析，能夠得到遺傳禁忌搜索算法的實現步驟，如圖1所示，具體如下：

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

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

2)計算P(k)里各個個體適應度。

3)判斷是否滿足相應的收斂準則，如果滿足收斂準則，輸出相應結果；如果不滿足收斂準則，轉到4)。

4)令m=0。

5)比較適應度大小，通過概率進行遺傳操作，在P(k)里選擇兩個染色體。

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

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

8)如果m

9)運用鄰域函數計算當前解的全部鄰域解，生成鄰域解集，而后根據需求確定一定的候選解。

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

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

3 對比分析

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

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

表1 3種調度算法的計算結果

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

表2 3種不同算法對Car 和Rec類問題的偏差平均值

表3 不同算法消耗時間平均值

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

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

圖4 不同算法消耗時間比較

4 結束語

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

[1]王秦暉. 約束滿足及其分布式求解和應用研究[D]. 北京：中國科學技術大學, 2013.

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

[3]楊輕云. 約束滿足問題與調度問題中離散粒子群算法研究[D].長春：吉林大學, 2011.

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

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

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

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

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

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

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

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

[12]劉朝華, 章 兢, 李小花，等. 免疫協同微粒群進化算法的永磁同步電機多參數辨識模型方法[J]. 自動化學報, 2012, 38(10): 1698-1708.

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

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

[15]趙 衛(wèi). 模擬退火遺傳算法在車間作業(yè)調度中的應用[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