《人工智能概論》第4章 搜索技術(shù)

1、第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.1 搜索 第四章 搜索技術(shù)4.1.1 什么是搜索搜索的概念：搜索(Search)根據(jù)問題的實(shí)際情況，按照一定的策略或者規(guī)劃。從知識(shí)庫中尋找到可以利用的知識(shí)，從而構(gòu)造出一條使得問題獲得解決的推理路線的過程。搜索的含義：搜索包含兩層含義，一是根據(jù)問題的實(shí)際情況， 按照一定的策略，從知識(shí)庫中尋找可利用的知識(shí)，從而構(gòu)造出一條使問題獲得解決的推理路線；另一是找到的這條路線是時(shí)空復(fù)雜度最小的求解路線。4.1 搜索 第四章 搜索技術(shù)4.1.2 狀態(tài)空間表示法狀態(tài)空

2、間法的基本思想是用 “狀態(tài)”和“操作”來表示和求解問題。4.1 搜索 第四章 搜索技術(shù)4.1.3 狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)。然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。 若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。4.1 搜索 第四章 搜索技術(shù)4.1.3 狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本分類。第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4

3、啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.2 廣度優(yōu)先 第四章 搜索技術(shù)4.2.1 廣度優(yōu)先搜索的基本思想在廣度優(yōu)先搜索算法中，解答樹上結(jié)點(diǎn)的擴(kuò)展是按它們?cè)跇渲械膶哟芜M(jìn)行的。首先生成第一層結(jié)點(diǎn)，同時(shí)檢查目標(biāo)結(jié)點(diǎn)是否在所生成的結(jié)點(diǎn)中，如果不在，則將所有的第一層結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)，并檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)，對(duì)層次為n+1的任一結(jié)點(diǎn)進(jìn)行擴(kuò)展之前，必須先考慮層次完層次為n的結(jié)點(diǎn)的每種可能的狀態(tài)。因此，對(duì)于同一層結(jié)點(diǎn)來說，求解問題的價(jià)值是相同的，可以按任意順序來擴(kuò)展它們。通常采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。4.2 廣度優(yōu)先 第四章 搜索技術(shù)4.2.2 廣度優(yōu)先搜索

4、的過程廣度優(yōu)先搜索BFS（Breadth First Search）也稱為寬度優(yōu)先搜索，它是一種先生成的結(jié)點(diǎn)先擴(kuò)展的策略。通過廣度優(yōu)先搜索獲得的頂點(diǎn)的遍歷次序?yàn)椋?。第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.3 深度優(yōu)先 第四章 搜索技術(shù)4.3.1 深度優(yōu)先搜索的基本思想深度優(yōu)先搜索屬于圖算法的一種,它的基本思想簡單的說就是對(duì)每一個(gè)分支的路徑搜索到最深處，并且每一個(gè)節(jié)點(diǎn)只能被訪問一次。深度優(yōu)先搜索遍歷和樹的先根遍歷比較類似，是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。思想是從一個(gè)頂點(diǎn)開

5、始，沿著一條路徑一直走到最后一個(gè)節(jié)點(diǎn)，如果發(fā)現(xiàn)不能達(dá)到目標(biāo)節(jié)點(diǎn)，就需要返回上一個(gè)節(jié)點(diǎn)，換一條路徑重復(fù)以上過程。4.3 深度優(yōu)先 第四章 搜索技術(shù)4.3.2 深度優(yōu)先搜索過程深度優(yōu)先搜索DFS（Depth-First-Search）是一種沿著樹的深的節(jié)點(diǎn)遍歷的方式，盡可能的搜索更深的節(jié)點(diǎn)的策略。如下圖是一個(gè)無向圖，如果從A點(diǎn)發(fā)起深度優(yōu)先搜索（以下的訪問次序并不是唯一的，第二個(gè)點(diǎn)既可以是B也可以是C,D），可以得到如下的一個(gè)訪問過程：ABE分支結(jié)束，重新回到A，ACFHGD沒有路，最終回到A，A也沒有未訪問的相鄰節(jié)點(diǎn)，本次搜索結(jié)束。深度優(yōu)先搜索的特點(diǎn)：每次深度優(yōu)先搜索的結(jié)果必然是圖的一個(gè)連通分量.

6、深度優(yōu)先搜索可以從多個(gè)節(jié)點(diǎn)發(fā)起。4.3 深度優(yōu)先 第四章 搜索技術(shù)4.3.2 深度優(yōu)先搜索過程右圖首先從一個(gè)未被遍歷過的頂點(diǎn)，例如從A開始，由于A作為第一個(gè)被訪問的節(jié)點(diǎn)，所以，需要標(biāo)記A的狀態(tài)為被訪問過；然后遍歷與A相鄰的節(jié)點(diǎn)，例如訪問B，并做標(biāo)記，然后訪問與B相鄰接點(diǎn)，例如D做標(biāo)記，然后F，然后E ；當(dāng)繼續(xù)遍歷E的鄰接點(diǎn)時(shí)，根據(jù)之前做的標(biāo)記顯示，所有鄰接點(diǎn)都被訪問過了。此時(shí)，從E回退到F，看F是否有未被訪問過的鄰接點(diǎn)，如果沒有，繼續(xù)回退到D，B，A；通過查看A，找到一個(gè)未被訪問過的頂點(diǎn)C，繼續(xù)遍歷，然后訪問C鄰接G，然后H；由于H沒有未被訪問的鄰接點(diǎn)，所有回退到G，繼續(xù)回退至C，最后到達(dá)A，

7、發(fā)現(xiàn)沒有未被訪問的；最后一步需要判斷是否所有頂點(diǎn)都被訪問，如果還有沒被訪問的，以未被訪問的頂點(diǎn)為第一個(gè)頂點(diǎn)，繼續(xù)依照上邊的方式進(jìn)行遍歷。4.3 深度優(yōu)先 第四章 搜索技術(shù)4.3.2 深度優(yōu)先搜索過程根據(jù)上邊的過程，可以得到通過深度優(yōu)先搜索獲得的頂點(diǎn)的遍歷次序?yàn)椋篈BDFECGH第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.4 啟發(fā)式搜索 第四章 搜索技術(shù)4.4.1 啟發(fā)性信息與估價(jià)函數(shù)啟發(fā)式搜索（Heuristically Search）又稱為有信息搜索(Informed Search)，是一個(gè)

8、基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，正如它的命名其搜索算法帶有啟發(fā)性即有一定引導(dǎo)的搜索方法。4.4 啟發(fā)式搜索 第四章 搜索技術(shù)4.4.2 局部尋優(yōu)搜索局部尋優(yōu)搜索指的是可以讓結(jié)果無窮接近最優(yōu)解的能力，而全局尋優(yōu)能力則是指找到全局最優(yōu)解所在大致位置的能力。局部尋優(yōu)搜索能力和全局尋優(yōu)搜索能力，缺一不可。向最優(yōu)解的導(dǎo)向，對(duì)于任何智能算法的性能都是很重要的。局部尋優(yōu)搜索算法是否能找到全局最優(yōu)解往往與初始點(diǎn)的位置有比較大的依賴關(guān)系。而這一問題解決的方法就是隨機(jī)生成一些初始點(diǎn)，從每個(gè)初始點(diǎn)出發(fā)進(jìn)行搜索，找到各自的最優(yōu)解，初始點(diǎn)找的好就可以更接近最優(yōu)解，再從這些最優(yōu)解中選擇一個(gè)最好的結(jié)果作為最終的結(jié)果。4.4 啟發(fā)

9、式搜索 第四章 搜索技術(shù)4.4.3 全局尋優(yōu)搜索全局尋優(yōu)搜索保留OPEN表，在這種方法搜索中，每當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察時(shí)，首先總是依照次序來比較OPEN表中所有節(jié)點(diǎn)的估價(jià)值，設(shè)法從中選擇一個(gè)估價(jià)值最小或最優(yōu)的節(jié)點(diǎn)來搜索求解；其次，若有多個(gè)解路徑存在時(shí)，要依照次序來比較每個(gè)解路徑的代價(jià)值，以便從中找到總代價(jià)最小的搜索解路徑，即盡可能得到最優(yōu)解。全局尋優(yōu)搜索又稱為有序搜索法。第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.5 遺傳算法 第四章 搜索技術(shù)4.5.1 遺傳算法的發(fā)展史遺傳算法起源于對(duì)生物

10、系統(tǒng)進(jìn)行的計(jì)算機(jī)模擬研究。盡管早在20世紀(jì)40年代，就有學(xué)者開始研究利用計(jì)算機(jī)進(jìn)行生物模擬的技術(shù)，但早期的研究特點(diǎn)是側(cè)重于對(duì)一些復(fù)雜操作的研究。最早意識(shí)到自然遺傳算法可以轉(zhuǎn)化為人工智能算法的是J.H.Hnllaad教授。4.5 遺傳算法 第四章 搜索技術(shù)4.5.1 遺傳算法的發(fā)展史20世紀(jì)70年代初，霍蘭德（Holland）教授提出了遺傳算法的基本定理模式定理，從而奠定了遺傳算法的理論基礎(chǔ)。模式定理揭示出種群中優(yōu)良個(gè)體(較好的模式)的樣本數(shù)將以指數(shù)級(jí)規(guī)律增長，因而從理論上保證了遺傳算法是一個(gè)可以用來尋求最優(yōu)可行解的優(yōu)化過程。1967年，Holland教授的學(xué)生J.D.Bagley在其博士論文中

11、首次提出了“遺傳算法”一詞，并發(fā)表了遺傳算法應(yīng)用方面的第一篇論文，從而創(chuàng)立了自適應(yīng)遺傳算法的概念。之后，J.D.Bagley發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個(gè)體編碼上使用了雙倍體的編碼方法。4.5 遺傳算法 第四章 搜索技術(shù)4.5.1 遺傳算法的發(fā)展史1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別。1975年，Holland教授出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性。20世紀(jì)80年代，holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)分類器系統(tǒng)（Classifier systems,簡稱CS）。進(jìn)入20世紀(jì)80年代,遺傳算法

12、迎來了興盛發(fā)展時(shí)期,無論是理論研究還是應(yīng)用研究都成了十分熱門的課題，尤其是遺傳算法的應(yīng)用領(lǐng)域也不斷擴(kuò)大。4.5 遺傳算法 第四章 搜索技術(shù)4.5.2 遺傳算法的基本原理遺傳算法是從一組隨機(jī)產(chǎn)生的初始解開始搜索，按照適者生存和優(yōu)勝劣汰的原理，通過交叉、變異和選擇運(yùn)算來實(shí)現(xiàn)的。其中，選擇是指從種群中選擇生命力強(qiáng)的染色體來產(chǎn)生新種群的過程，選擇的依據(jù)是每個(gè)染色體的適應(yīng)度大小, 適應(yīng)度越大, 被選中的概率就越大；交叉運(yùn)算是指兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體； 變異就是以很小的概率, 隨機(jī)改變?nèi)旧w某個(gè)位置上的基因。根據(jù)適應(yīng)度的大小，從上一代和后代中選擇一定數(shù)量的個(gè)

13、體作為下一代群體，再繼續(xù)進(jìn)化。這樣經(jīng)若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。4.5 遺傳算法 第四章 搜索技術(shù)4.5.3 遺傳算法的求解步驟第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.6 微粒群算法 第四章 搜索技術(shù)4.6.1 微粒群算法的基本概念及進(jìn)化方程微粒群算法（Particle Swarm Optimization,PSO），又稱粒子群優(yōu)化，是由J. Kennedy和R. C. Eberhart等于1995年開發(fā)的一種演化計(jì)算技術(shù)，來源于對(duì)一個(gè)簡化社會(huì)模型

14、的模擬。其中“群（swarm）”來源于微粒群匹配M. M. Millonas在開發(fā)應(yīng)用于人工生命（artificial life）的模型時(shí)所提出的群體智能的5個(gè)基本原則?！傲Ｗ樱╬article）”是一個(gè)折衷的選擇，因?yàn)榧刃枰獙⑷后w中的成員描述為沒有質(zhì)量、沒有體積的，同時(shí)也需要描述它的速度和加速狀態(tài)。4.6 微粒群算法 第四章 搜索技術(shù)4.6.1 微粒群算法的基本概念及進(jìn)化方程微粒群算法是（PSO）是一種有效地全局尋優(yōu)算法，具有進(jìn)化計(jì)算和群智能的特點(diǎn)，是基于群體智能理論的優(yōu)化算法，通過群體間微粒的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。其實(shí)與傳統(tǒng)的算法相比較，微粒群算法保留了基于種群的全局搜索策

15、略，但采用的“速度-移位”模型操作簡單，避免了復(fù)雜的遺傳操作，由于每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的雙重優(yōu)點(diǎn)，從而可以在較少的迭代次數(shù)中找到最優(yōu)解。4.6 微粒群算法 第四章 搜索技術(shù)4.6.2 標(biāo)準(zhǔn)微粒群算法流程4.6 微粒群算法 第四章 搜索技術(shù)4.6.3 微粒群算法的研究現(xiàn)狀在算法改進(jìn)方面的研究：在算法改進(jìn)方面，人們不僅將微粒群算法與其他理論進(jìn)行結(jié)合，并且將微粒群算法與其他算法進(jìn)行結(jié)合，從而產(chǎn)生了很多擁有各自優(yōu)勢的不同算法，如根據(jù)耗散結(jié)構(gòu)的自組織性，提出的一種耗散型PSO算法。算法的應(yīng)用：由于微粒群算法具有計(jì)算速度快、概念簡明，依賴的經(jīng)驗(yàn)參數(shù)較少，實(shí)現(xiàn)方便等特點(diǎn)，因此P

16、SO是非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題和會(huì)和非整數(shù)非線性優(yōu)化問題的有效優(yōu)化工具。目前已經(jīng)廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。例如，應(yīng)用PSO來分析人類的帕金森綜合征等顫抖類疾?。挥酶倪M(jìn)的速度更新方程訓(xùn)練模糊神經(jīng)網(wǎng)絡(luò)等。第四章搜索技術(shù)4.1 搜索4.2 廣度優(yōu)先4.3 深度優(yōu)先4.5 遺傳算法4.4 啟發(fā)式搜索4.6 微粒群算法4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法習(xí)題4.7 實(shí)驗(yàn)：粒子群優(yōu)化算法 第四章 搜索技術(shù)實(shí)驗(yàn)?zāi)繕?biāo)：PSO 初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)極值來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解pbest。另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，即全局極值gbest。實(shí)驗(yàn)內(nèi)容：根據(jù)粒子群優(yōu)