本文關(guān)鍵詞：基于啟發(fā)式搜索的靈活規(guī)劃的算法研究，由筆耕文化傳播整理發(fā)布。

計(jì)算機(jī)科學(xué)２００８Ｖ０１．３５№．４

基于啟發(fā)式搜索的靈活規(guī)劃的算法研究與系統(tǒng)實(shí)現(xiàn)＊）

李楊１ ２陳佳豫１ ２韓誠(chéng)山１孫焱３谷文祥３

（中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所長(zhǎng)春１３００３３）１（中國(guó)科學(xué)院研究生院北京１０００４９）２

（東北師范大學(xué)計(jì)算機(jī)學(xué)院長(zhǎng)春１３０１１７）３

摘要隨著智能規(guī)劃研究的深入，經(jīng)典規(guī)劃已不能滿足實(shí)際應(yīng)用的需要。本文分析了經(jīng)典規(guī)劃無(wú)法滿足實(shí)際應(yīng)用要求及產(chǎn)生靈活規(guī)劃的原因。在對(duì)啟發(fā)式搜索和靈活規(guī)劃深入研究的基礎(chǔ)上，提出了利用啟發(fā)式搜索的方法來(lái)處理靈活規(guī)劃問(wèn)題的思想，并給出了基于啟發(fā)式搜索的靈活規(guī)劃算法和求解模型。采用智能規(guī)劃中的基準(zhǔn)問(wèn)題對(duì)該算法進(jìn)行測(cè)試，實(shí)驗(yàn)表明該方法在處理很多領(lǐng)域問(wèn)題上都可以得到非常好的效果。

關(guān)鍵詞人工智能，智能規(guī)劃，靈活規(guī)劃，啟發(fā)式搜索

ＲｅｓｅａｒｃｈｏｆＦｌｅｘｉｂｌｅＰｌａｎｎｉｎｇＡｌｇｏｒｉｔｈｍａｎｄＳｙｓｔｅｍＩｍｐｌｅｍｅｎｔＢａｓｅｄｏｎＨｅｕｒｉｓｔｉｃＳｔａｔｅＳｅａｒｃｈ

ＬＩＹａｎ９１ ２ＣＨＥＨＪｉａ－Ｙｕ１，２ＨＡＮＣｈｅｎｇ－Ｓｈａｎ＇ＳＵＮＹａｎ３ＧＵＷｅｎ－Ｘｉａｎｇｚ

（ＣｈａｎｇｃｈｕｎＩｎｓｔｉｔｕｔｅｏｆＯｐｔｉｃｓ，ＦｉｎｅＭｅｃｈａｎｉｃｓａｎｄＰｈｙｓｉｃｓ，Ｃ１１ｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｃｈａｎｇｃｈｕｎ１３００３３）１

（ＧｒａｄｕａｔｅＳｃｈｏｏｌｏｔｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００４９）２

（Ｓｃｈ００ＩｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＮｏｒｔｈｅａｓｔＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３０１１７）３

ＡｂｓｔｒａｃｔＴｒａｄｉｔｉｏｎａｌｌｙ，ｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｓａｒｅｃａｓｔｉｎｔｅｒｍｓｏｆｉｍｐｅｒａｔｉｖｅｃｏｎｓｔｒａｉｎｔｓｔｈａｔａｒｅｅｉｔｈｅｒｗｈｏｌｌｙｓａｔｉｓｆｉｅｄｏｒｗｈｏｌｌｙｖｉｏｌａｔｅｄ．Ｉｎｔｈｉｓｐａｐｅｒ．ｗｈｙｃｌａｓｓｉｃａｌｐｌａｎｎｉｎｇｃａｎｎｏｔｃａｐｔｕｒｅｔｈｅｆｕｌｌｓｕｂｔｌｅｔｙｏｆｍａｎｙｒｅａｌｐｒｏｂｌｅｍｓｉｓａｒｇｕｅｄ．Ａｎｅｗｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｉｓｄｅｆｉｎｅｄｗｈｉｃｈｓｕｐｐｏｒｔｓｔｈｅｓｏｆｔｃｏｎｓｔｒａｉｎｔｓｏｆｔｅｎｆｏｕｎｄｉｎｒｅａｌｉｔｙ．Ａｎｅｗｃｏｎｃｅｐｔｕ－ｓｉｎｇｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈｔｈｅｏｒｙｔＯｓｏｌｖｅｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｉｓｄｅｓｃｒｉｂｅｄ．Ｔｈｉｓｐａｐｅｒａｌｓｏｉｎｔｒｏｄｕｃｅｓａｎｏｖｅｌｓｏｌ—ｖｉｎｇｍｏｄｅｌｏｆｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇｕｓｉｎｇｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈｔｈｅｏｒｙａｎｄｅｘｐｌｏｉｔｓｔｈｅａｌｇｏｒｉｔｈｍｆｒａｍｅｗｏｒｋｏｆｆｌｅｘｉｂｌｅｐｌａｎ－１１ｉＴｌｇｂａｓｅｄｏｎｈｅｕｒｉｓｔｉｃｓｔａｔｅｓｅａｒｃｈ．

ＫｅｙｗｏｒｄｓＡＩ，Ｉｎｔｅｌｌｉｇｅｎｔｐｌａｎｎｉｎｇ，Ｆｌｅｘｉｂｌｅｐｌａｎｎｉｎｇ，Ｓｔａｔｅｈｅｕｒｉｓｔｉｃｓｅａｒｃｈ

Ｉ引言于Ｇｒａｐｈｐｌａｎ和ＣＳＰ的。

本文提出了基于啟發(fā)式搜索的靈活規(guī)劃的算法。啟發(fā)式

智能規(guī)劃是一門(mén)涉及知識(shí)表達(dá)、知識(shí)推理、非單調(diào)邏輯、搜索是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)式信息，用以指導(dǎo)情景演算、人機(jī)交互和知識(shí)挖掘等各個(gè)方面知識(shí)的多領(lǐng)域交搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并最終叉性學(xué)科［１］，被廣泛運(yùn)用于航空航天技術(shù)、機(jī)器人控制、后勤找到最優(yōu)解。在多次國(guó)際規(guī)劃器比賽中發(fā)現(xiàn)，采用啟發(fā)式知調(diào)度、游戲角色設(shè)計(jì)、系統(tǒng)建模等方面，，帶來(lái)的成果有目共睹。識(shí)的規(guī)劃器比沒(méi)有采用啟發(fā)式知識(shí)的規(guī)劃器得到的效果要近幾年來(lái)，隨著客觀條件的改善，世界上特別是一些發(fā)達(dá)國(guó)家好，表現(xiàn)出了很強(qiáng)的問(wèn)題求解能力�；谝陨蠁l(fā)式搜索和在此領(lǐng)域獲得了長(zhǎng)足的發(fā)展，在國(guó)防和空間技術(shù)領(lǐng)域中得到靈活規(guī)劃的優(yōu)點(diǎn)，把啟發(fā)式思想運(yùn)用到了靈活規(guī)劃中，產(chǎn)生了成功應(yīng)用，取得了巨大的經(jīng)濟(jì)和社會(huì)效益。新的有效算法，為靈活規(guī)劃的求解開(kāi)辟了新的途徑。

９０年代，規(guī)劃系統(tǒng)的研究達(dá)到高潮。目前解決規(guī)劃問(wèn)題本文的其它部分安排如下：第２節(jié)是本文的研究基礎(chǔ)，主主要有三種方法：第一種方法是Ｂｌｕｍ和Ｆｕｒｓｔ提出的Ｇｒａｐｈ－要介紹靈活規(guī)劃的提出背景及靈活規(guī)劃的相關(guān)知識(shí)和啟發(fā)式ｐｌａｎ方法［ｚ１；第二種方法是Ｋａｕｔｚ和Ｓｅｌｍａｎ提出的約束可滿搜索的知識(shí)；第３節(jié)提出基于啟發(fā)式搜索的靈活規(guī)劃的算法足方法［３］；第三種方法是Ｂｏｎｅｔ和Ｇｅｆｆｅｒ提出的啟發(fā)式搜索和求解模型；第４節(jié)是實(shí)驗(yàn)結(jié)果分析；最后是總結(jié)。

規(guī)劃方法［４］。用啟發(fā)式函數(shù)產(chǎn)生規(guī)劃實(shí)例的說(shuō)明，用來(lái)指導(dǎo)

規(guī)劃在狀態(tài)空間中的搜索。２研究基礎(chǔ)

隨著規(guī)劃的不斷深入研究，經(jīng)典規(guī)劃存在的不足越來(lái)越２．１靈活規(guī)劃（ＦｌｅｘｉｂｌｅＰｌａｎｎｉｎｇ）概述

明顯。它對(duì)現(xiàn)實(shí)世界的許多問(wèn)題，例如一些復(fù)雜的航空航天現(xiàn)實(shí)世界非常復(fù)雜，很多實(shí)際問(wèn)題的約束條件靈活。經(jīng)問(wèn)題，都無(wú)法有效地刻畫(huà)，因此產(chǎn)生了一種新的規(guī)劃即靈活規(guī)典規(guī)劃是一種強(qiáng)約束問(wèn)題，即對(duì)于約束條件或者完全滿足或劃。用于處理這種靈活規(guī)劃的規(guī)劃器稱(chēng)為靈活規(guī)劃器。規(guī)劃者完全不滿足，操作的可用性在特定情況下是布爾的。這種器實(shí)際上是一個(gè)軟件，在這里規(guī)劃算法無(wú)疑成為規(guī)劃器的核框架對(duì)于刻畫(huà)現(xiàn)實(shí)世界的很多問(wèn)題太過(guò)于嚴(yán)格。為了解決上心，目前用于解決靈活規(guī)劃的規(guī)劃器所使用的算法多數(shù)是基述情況，產(chǎn)生了靈活規(guī)劃。靈活規(guī)劃描述支持軟約束，是對(duì)經(jīng)＊）國(guó)家自然科學(xué)基金項(xiàng)目（編號(hào)為：６０５７３０６７和６０４７３０４２）。李楊博士研究生，主要研究方向?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別、軟件可靠性、軟件工程；陳佳豫博士研究生，主要研究方向?yàn)檐浖こ�；韓誠(chéng)山研究員，碩士生導(dǎo)師，主要研究方向?yàn)榭臻g相機(jī)控制方法研究；孫焱碩士研究生，主要研究方向?yàn)閳D像處理；谷文祥教授，博士生導(dǎo)師，主要研究方向?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別、形式語(yǔ)言與自動(dòng)機(jī)理論、模糊數(shù)學(xué)及其應(yīng)用。萬(wàn)　方數(shù)據(jù) ２０７

  本文關(guān)鍵詞：基于啟發(fā)式搜索的靈活規(guī)劃的算法研究，由筆耕文化傳播整理發(fā)布。