智能優(yōu)化算法的研究

1、智能優(yōu)化算法的研究,問題-一個人問數(shù)學家他的三個兒子都是幾歲。他三個兒子的年齡積是36，年齡和是某棟房子的窗戶個數(shù)。數(shù)學家又要求再提供一個信息，這人說他的大兒子的眼睛是藍色的。,請算出三個兒子的年齡？,answer,AI for GamesCM-0328D,,,Bluffer’s guide to game theory,The Prisoner’s Dilemma,P1,P2,Next week…,Decision Making E

2、xample,Goods must be transported from factories in Watford, Maidstone and Manchester to Depots in Birmingham, Sheffield and London. The cost per unit transported and the number of units supplied or in demand is given in

3、the following table. Find a delivery plan which satisfies the demand at each depot for minimum cost.,計算最少花費,,Phases problem analysis,最優(yōu)化問題,優(yōu)化技術是一種以數(shù)學為基礎，用于求解各種工程問題優(yōu)化解的應用技術，主要應用在系統(tǒng)控制、人工智能、模式識別、生產(chǎn)調(diào)度、VLSI技術、計算機工程等。,優(yōu)化算法,是一種

4、搜索過程或規(guī)則，基于某種思想和機制，通過一定的途徑或規(guī)則來滿足用戶要求的問題的解。分類為： (1) 經(jīng)典算法-線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃、分支定界等運籌學的傳統(tǒng)算法。 (2) 構造算法-用構造的方法快速建立問題的解。 (3) 改進算法-或鄰域搜索算法，從任一解出發(fā)，對其鄰域的不斷搜索和當前解替換的來實現(xiàn)優(yōu)化。局部搜索法和指導性搜索法。 (4) 基于系統(tǒng)動態(tài)演化的方法-將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動態(tài)的演

5、化過程，基于系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化。神經(jīng)網(wǎng)絡和混沌搜索等。 (5) 混合型算法-將上述算法從結構或操作上相混合而產(chǎn)生的各類算法。,爬山法搜索Hill-Climbing,貪婪局部搜索Function Hill-Climbing(problem) //returns a state that is a local maximum input: problem, a problem local variables: cur

6、rent, a node neighbor, a node current=Make-Node(Initial-State[problem]) loop do neighbor=a highest-valued successor of current if Value[neighbor]<=Value[current] then retu

7、rn State[current] else current=neighbor,爬山法搜索Hill-Climbing,該算法是一個向值增加的方向持續(xù)移動的簡單循環(huán)過程， 登高。將會在到達頂峰時終止，相鄰狀態(tài)中沒有比它更高的值。,模擬退火搜索-基本含義Simulate Annealing,模擬退火算法（SA）在某一初溫下，伴隨溫度參數(shù)的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性

8、地跳出并最終趨于全局最優(yōu)。,模擬退火搜索-算法描述Simulate Annealing,Function Simulated-Annealing(problem,schedule) //returns a solution state inputs: problem, a problem schedule, a mapping from time to temperature local varia

9、bles: current, a node next, a node T, a temperature controlling probability of downward steps current=Make-Node(Initial-State[problem]) for t=1 to ∞ do T=schedul

10、e[t] if T==0 then return current next= a randomly selected successor of current △E=Value]next]-Value[current] if △E>0 then current=next else current=next only with probability e?

11、//(n= △E/T),模擬退火搜索-說明Simulate Annealing,一個允許下山的隨機爬山法算法。在退火初期下山移動容易接受，隨著時間推移下山的次數(shù)越來越少。尋求梯度下降（耗散最小）。,禁忌搜索-基本思想Taboo Search,禁忌搜索(Tabo Search or Taboo Search, TS): 給定一個當前解（初始解）和一種鄰域，在當前解的鄰域中確定若干候選解；

12、若最佳候選解對應的目標值優(yōu)于best so far狀態(tài)，則忽視其禁忌特性，用其代替當前解和best so far狀態(tài)，并將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期； 若不存在上述候選解，則選擇在候選解中選擇非禁忌的最佳狀態(tài)為新的當前解，將相應的對象加入禁忌表，并修改表中各對象的任期；如此反復迭代搜索過程，指導滿足停止準則。,給定算法參數(shù)，隨機產(chǎn)生初始解x，置禁忌表為空；判斷算法終止條件是否滿足？是，則結

13、束算法并輸出優(yōu)化結構；否，繼續(xù)；利用當前解x的鄰域函數(shù)產(chǎn)生其所有鄰域解，并從中確定若干候選解；對候選解判斷藐視準則是否滿足？成立，則用滿足藐視準則的最佳狀態(tài)y替換x成為新的當前解，即x=y，并用于y對應的禁忌對象替換最早進入禁忌表的禁忌對象，用y替換best so far狀態(tài)，轉(zhuǎn)到（2）；不成立，執(zhí)行（5）；判斷候選解對應的各對象的禁忌屬性，選擇候選解中非禁忌對象的最佳狀態(tài)為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的

14、禁忌對象元素。,禁忌搜索-基本思想-說明Taboo Search,（1）搜索過程中可以接受劣解，具有較強的爬山能力；（2）新解不是在當前解的鄰域中隨機產(chǎn)生，而是，或是由于best so far的解，或是非禁忌的最佳解。選取優(yōu)良解的概率遠大于其他解。,知 識 表 示,人工智能主要研究用機器來模仿和執(zhí)行人類的一些智力功能，而人類的智力功能又是以知識為基礎，所以如何從現(xiàn)實世界中獲取知識，如何將已獲取的知識以適當?shù)男问皆跈C器中存儲，以及如何

15、利用這些知識進行推理以解決實際問題，即知識的獲取、知識的表示和知識的運用就構成人工智能研究的三個主要內(nèi)容。,知識、數(shù)據(jù)和信息,,狀態(tài)空間表示法,由一個問題的全部狀態(tài)以及可以使用的全部操作所構成的集合就稱為該問題的狀態(tài)空間。它一般由三部分構成：問題可能具有的初始狀態(tài)的集合S，操作的集合F，目標狀態(tài)的集合G。用三元組表示如下：,,狀態(tài)空間表示法的基本思想,用“狀態(tài)”和“操作”來表示問題及其變化，形成狀態(tài)空間，求解問題的過程就是在狀態(tài)空間樹中

16、搜索表示解的狀態(tài)的過程。搜索時，從某個初始狀態(tài)出發(fā)，每次使用一個操作使得問題能夠從一種狀態(tài)變?yōu)榱硗庖环N狀態(tài)，直到到達目標狀態(tài)為止。,,8 3 6 47 ■ 5,初始狀態(tài),1 2 3 ■ 8 47 6 5,目標狀態(tài),,要求：用盡可能少棋步能由初始狀態(tài)到達目標狀態(tài)。,產(chǎn)生式系統(tǒng) Production System,產(chǎn)生式系統(tǒng)（Production System）是194

17、3年Post提出的一種計算形式體系里所使用的術語，主要是使用類似于文法的規(guī)則，對符號串作替換運算。產(chǎn)生式系統(tǒng)的組成部分　　綜合數(shù)據(jù)庫、產(chǎn)生式規(guī)則集和控制系統(tǒng)，被稱為產(chǎn)生式系統(tǒng)的三要素。,產(chǎn)生式系統(tǒng)組成,產(chǎn)生式系統(tǒng) Production System,綜合數(shù)據(jù)庫-是一個數(shù)據(jù)的集合，用于存放在推理過程中的已知條件、推導出的中間結果和最終結論等。產(chǎn)生式規(guī)則集-采用“IF THEN ”的形式，其中規(guī)則的表達的是該條規(guī)則所要滿足的條件，

18、規(guī)則的表示的是該規(guī)則所得出的結論，或者動作。以中國象棋為例，前者描述的是象棋的走棋規(guī)則，如“馬走日”、“象走田”等。后者描述是在什么情況下，應該如何走棋才能戰(zhàn)勝對手，或者什么樣的局面比較有力，什么樣的局面不利等?？刂葡到y(tǒng)，又稱為控制策略或者搜索策略，用于控制系統(tǒng)的運行，它根據(jù)綜合數(shù)據(jù)庫中的當前數(shù)據(jù)，來選擇合適的規(guī)則。不同的選擇規(guī)則的方法，就構成了不同的控制策略。因此，控制系統(tǒng)也可以稱之為推理引擎。,Example-八數(shù)碼游戲,八數(shù)碼

19、游戲（Eight－Puzzle）　　在3×3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1-8數(shù)碼中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格移動，這樣通過移動將牌就可以不斷改變將牌的布局。這種游戲求解的問題是：給定一種初始的將牌布局或結構（稱初始狀態(tài)）和一個目標的布局（稱目標狀態(tài)），問如何移動將牌，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變。問題的解答其實就是給出一個合法的走步序列。,八數(shù)碼游戲,,初始狀態(tài),

20、目標狀態(tài),八數(shù)碼游戲-產(chǎn)生式表示,（1）綜合數(shù)據(jù)庫：在這里是要選擇一種數(shù)據(jù)結構來表示將牌的布局。有符號串、向量、集合、數(shù)組、樹、表格、文件等。八數(shù)碼問題，選用二維數(shù)組來表示將牌的布局很直觀，因此該問題的綜合數(shù)據(jù)庫可以如下形式表示：（ Sij），其中1≤i、j≤3， ∈{0，1，…，8}，且 互不相等。這樣每一個具體的矩陣就可表示一個棋局狀態(tài)。對八數(shù)碼游戲，顯然共有9!＝362880個狀態(tài)。所有可能的狀態(tài)集合就構成該問題的狀態(tài)空間或

21、問題空間。八數(shù)碼問題實際上是將牌在移動，但將牌的移動也可以看成是空格的移動。由于空格只有一個，因此表示起來更方便。,八數(shù)碼游戲-產(chǎn)生式表示,八數(shù)碼游戲-產(chǎn)生式表示,（2）規(guī)則集合：移動一塊將牌（即走一步）就使狀態(tài)發(fā)生轉(zhuǎn)變。改變狀態(tài)有4種走法：空格左移、空格上移、空格右移、空格下移。規(guī)則集可形式化表示如下：設 Sij記矩陣第i行第j列的數(shù)碼， i0,j0記空格所在的行、列數(shù)值，即 Si0j0=0，則 If j0-1>=1 t

22、hen Si0j0=Si0(j0-1),Si0(j0-1)=0;If i0-1>=1 then Si0j0=S(i0-1)j0,S(i0-1)j0=0;If j0+1<=3 then Si0j0=Si0(j0+1),Si0(j0+1)=0;If i0+1<=3 then Si0j0=S(i0+1)j0,S(i0+1)j0=0;,八數(shù)碼游戲-產(chǎn)生式表示,（3）搜索策略：是從規(guī)則集中選取規(guī)則并作用于狀態(tài)的一種廣義選取

23、函數(shù)。給出問題的初始狀態(tài)和結束狀態(tài)（目標狀態(tài)）。初始狀態(tài)和結束狀態(tài)要求采用與綜合數(shù)據(jù)庫相同的結構表達。,Example-傳教士和野人問題,傳教士和野人問題（Missionaries and Cannibals）　 有N個傳教士和N個野人來到河邊準備渡河，河岸有一條船，每次至多可供k人乘渡。問傳教士為了安全起見，應如何規(guī)劃擺渡方案，使得任何時刻，在河的兩岸以及船上的野人數(shù)目總是不超過傳教士的數(shù)目。即求解傳教士和野人從左岸全部擺渡到右

24、岸的過程中，任何時刻滿足M（傳教士數(shù)）≥C（野人數(shù)）和M＋C≤k的擺渡方案。設N＝3，k＝2，L和R表示左岸和右岸，B＝1或0分別表示有船或無船。約束條件是：兩岸上M≥C，船上M＋C≤2。只描述一岸--如左岸--的情況就可以了。,Example-傳教士和野人問題,,初始狀態(tài),目標狀態(tài),傳教士和野人問題-產(chǎn)生式規(guī)則表示,（1）綜合數(shù)據(jù)庫：用三元組表示左岸的情況，即（Ml ，Cl ，Bl ），其中0≤Ml ，Cl ≤3， Bl∈

25、{0，1}，其中 Ml表示在左岸的傳教士人數(shù)， Cl表示在左岸的野人數(shù)，Bl ＝1表示船在左岸，Bl ＝0表示船在右岸。則此時問題描述可以簡化為：（3，3，1）→（0，0，0）,傳教士和野人問題-產(chǎn)生式規(guī)則表示,（ Ml, Cl, Bl）（ 0　0　0）（ 0　1　0）（ 0　2　0）（ 0　3　0）達不到 （ 1　0　0）不合法 （ 1　1　0） （ 1　2　0）不合法 （ 1　3　0）不合法 （ 2　0　0）不

26、合法 （ 2　1　0）不合法 （ 2　3　0）不合法 （ 3　0　0） （ 2　2　0） （ 3　1　0） （ 3　2　0） （ 3　3　0）達不到,（ Ml, Cl, Bl ） （ 0　0　1）達不到 （ 0　1　1） （ 0　2　1） （ 0　3　1） （ 1　0　1）不合法 （ 1　1　1） （ 1　2　1）不合法 （ 1　3　1）不合法 （ 2　0　1）不合法 （ 2　1　1）不合法 （

27、 2　2　1） （ 2　3　1）不合法 （ 3　0　1）達不到 （ 3　1　1） （ 3　2　1） （ 3　3　1）,傳教士和野人問題-產(chǎn)生式規(guī)則表示,（2）規(guī)則集合：由擺渡操作組成。該問題主要有兩種操作： Pmc操作（規(guī)定為從左岸劃向右岸）和 Qmc操作（從右岸劃向左岸）。每次擺渡操作，船上人數(shù)有五種組合，因而組成有10條規(guī)則的集合。,規(guī)則集合,If(Ml,Cl,Bl=1) then P(Ml-1,Cl,Bl-1)

28、 // p10If(Ml,Cl,Bl=1) then P(Ml,Cl-1,Bl-1)   // p01If(Ml,Cl,Bl=1) then P(Ml-1,Cl-1,Bl-1)   // p11If(Ml,Cl,Bl=1) then P(Ml-2,Cl,Bl-1) // p20If(Ml,Cl,Bl=1) then P(Ml,Cl-2,Bl-1)  

29、// p02If(Ml,Cl,Bl=0) then Q(Ml+1,Cl,Bl+1)   // q10If(Ml,Cl,Bl=0) then Q(Ml,Cl+1,Bl+1)   // q01If(Ml,Cl,Bl=0) then Q(Ml+1,Cl+1,Bl+1)  // q11 If(Ml,Cl,Bl=0) then Q(Ml+2,Cl,Bl+1)   // q20If

30、(Ml,Cl,Bl=0) then Q(Ml,Cl+2,Bl+1)   // q02,初始和目標狀態(tài),（3）初始和目標狀態(tài)：即（3，3，1）和（0，0，0）。狀態(tài)轉(zhuǎn)換見下圖。,產(chǎn)生式系統(tǒng)的基本過程,例：設字符轉(zhuǎn)換問題規(guī)則如下：A∧B→CA∧C→DB∧C→GB∧E→FD→E已知：A，B求：F用產(chǎn)生式系統(tǒng)來描述該問題。（1）綜合數(shù)據(jù)庫 綜合數(shù)據(jù)庫用集合{x}表示，其中x為字符。（2）規(guī)

31、則集 1，IF A∧B THEN C 2，IF A∧C THEN D 3，IF B∧C THEN G 4，IF B∧E THEN F 5，IF D THEN E（3）控制策略 控制策略是選擇規(guī)則的方法，這里采用按照規(guī)則的自然順序選擇規(guī)則的

32、方法。稱為順序排隊。（4）初始狀態(tài)- {A，B}，A、B是已知條件。（5）結束條件- F∈{x}，當目標F在綜合數(shù)據(jù)庫中出現(xiàn)時，則F被求得。,Example-練習,對量水問題給出產(chǎn)生式系統(tǒng)描述，并畫出狀態(tài)空間圖。有兩個無刻度標志的水壺，分別可裝5升和2升的水。設另有一水缸，可用來向水壺灌水或倒出水，兩個水壺之間，水也可以相互傾灌。已知5升壺為滿壺，2升壺為空壺，問如何通過倒水或灌水操作，使能在2升的壺中量出一升的水來。,量

33、水問題-產(chǎn)生式規(guī)則,綜合數(shù)據(jù)庫定義兩元組：（L5, L2）其中：05 THEN (5, L5+L2-5) /* L2倒入L5中 */ r7：IF (L5, L2) and L5+L25 THEN (L5+L2-2, 2) /* L5倒入L2中 */3 初始狀態(tài)：(5, 0) 結束條件：(x, 1)，其中x表示不定。結束條件寫成：(0, 1) (5,0)->(3,2)->(3,0)->(1,2)->(

34、1,0)->(0,1),給出狀態(tài)轉(zhuǎn)換,,Exercise-狀態(tài)空間表示,井字棋游戲,假定我方先走：1 定義初始狀態(tài)、結 束狀態(tài)2 給出狀態(tài)轉(zhuǎn)換過程3 給出我方獲勝的路徑。,基本搜索方法的劃分,（1）求任一解路經(jīng)的搜索策略　　回溯法（Backtracking）　　爬山法（Hill Climbing）　　寬度優(yōu)先法（Breadth-first）　　深度優(yōu)先法（Depth-first）　　限定范圍搜索法（Beam Sea

35、rch）　　好的優(yōu)先法（Best-first）（2）求最佳解路經(jīng)的搜索策略　　大英博物館法（British Museum）　　分枝界限法（Branch and Bound）　　動態(tài)規(guī)劃法（Dynamic Programming）　　最佳圖搜索法（A﹡）（3）求與或關系解圖的搜索法　　一般與或圖搜索法（AO﹡）　　極小極大法（Minimax）　　α－β剪枝法（Alpha-beta Pruning）　　啟發(fā)式剪枝法（H

36、euristic Pruning）,小結,本次課主要介紹了最優(yōu)化的一些簡單算法，讓我們知道人工智能的理論研究遠遠沒有結束，不論你研究哪一方面，都會用到優(yōu)化算法。產(chǎn)生式規(guī)則是一種基本的知識表示形式，我們僅僅介紹了它的組成部分。,總結,本門課程簡要向同學們介紹了人工智能思想的廣泛用途和應用價值，并結合游戲的基本實現(xiàn)過程融入人工智能思想，進一步介紹了人工智能研究中的重要方法，如狀態(tài)機、模糊邏輯、貝葉斯、遺傳算法。但我們?nèi)匀粵]能包含全部，如神