1 目 錄 摘要
2 人工智能算法綜述 通信工程專業(yè)
摘要：隨著人工智能再當(dāng)今科學(xué)技術(shù)中的飛速發(fā)展和應(yīng)用，人工智能算法的開發(fā)學(xué)習(xí)及應(yīng)用也隨之越來越廣泛，它介紹了當(dāng)前存在的一些人工智能算法，闡述了其工作原理和特點(diǎn)并對(duì)其加以比較、評(píng)價(jià)，還對(duì)產(chǎn)生背景、應(yīng)用領(lǐng)域加以說明，同時(shí)又對(duì)人工智能算法的發(fā)展應(yīng)用進(jìn)行了展望。人工智能算法要解決的一般是最優(yōu)化問題。搜索技術(shù)和神經(jīng)網(wǎng)絡(luò)滲透在各種人工智能系統(tǒng)中，在專家系統(tǒng)、自然語言理解、自動(dòng)程序設(shè)計(jì)、模式識(shí)別、機(jī)器人學(xué)、信息檢索和博弈等領(lǐng)域都廣泛使用。 關(guān)鍵詞：盲目式搜索 啟發(fā)式搜索 局部搜索等高級(jí)搜索 人工神經(jīng)網(wǎng)絡(luò)算法 Algorithms summary of Artificial Intelligence Student majoring in Communication Engineering Luopu Tutor ZhangJinghu Abstract: With today's science and technology of artificial intelligence and then the rapid development and application of artificial intelligence algorithms and application development also will learn more and more widely, it introduces some existing artificial intelligence algorithm, described its working principle and characteristics and comparison of their evaluation, also gave instructions on the applications, while the development and application of artificial intelligence algorithms were reviewed. Artificial intelligence algorithms to solve the optimization problem in general is. Search technology and neural network penetration in various artificial intelligence system, the expert systems, natural language understanding, automatic programming, pattern recognition, robotics, information retrieval and game fields are widely used. Key words: blind-type local search and other heuristic search Advanced Search artificial neural network.。 引言 自從人工智能學(xué)科體系誕生以來，通過對(duì)自然界奧秘的研究，涌現(xiàn)出了很多人工智能算法，人工智能算法又稱“軟計(jì)算”，根據(jù)其原理，從自然界得到啟迪，模仿其結(jié)構(gòu)進(jìn)行發(fā)明創(chuàng)造，這就是仿生學(xué)。這是我們向自然界學(xué)習(xí)的一個(gè)方面。另一方面，我們還可以利用仿生原理進(jìn)行設(shè)計(jì)(包括設(shè)計(jì)算法)，這就是智能計(jì)算的思想。這方面的內(nèi)容很多，如盲目式搜索算法、啟發(fā)式搜索算法、模擬退火算法、遺傳算法、和群集智能算法、人工神經(jīng)網(wǎng)絡(luò)算法等。本文通過對(duì)若干智能算法的綜述，在一定程度上集合總結(jié)了大部分算法的基本原理、功能特點(diǎn)、應(yīng)用領(lǐng)域，并對(duì)其加以比較，使人們能夠?qū)θ斯ぶ悄芩惴ㄓ懈逦髁说恼J(rèn)識(shí)，減少對(duì)算法應(yīng)用方面上的失誤讓使用者能夠方便快速的了解到各算法的相關(guān)資料從而提高運(yùn)算效率。 人工智能算法要解決的一般是最優(yōu)化問題，智能算法最優(yōu)化問題是一種以數(shù)學(xué)為基礎(chǔ)，用于求解各種工程問題中最優(yōu)解或者滿意解的應(yīng)用技術(shù)。實(shí)際問題求解中，絕大多數(shù)問題通過變化都可以轉(zhuǎn)化為求解最優(yōu)化問題的研究：另外，在數(shù)學(xué)領(lǐng)域以及工程領(lǐng)域中存在較多的 NP 問題，很難找到精確的數(shù)學(xué)公式比如：背包問題，組合優(yōu)化問題，任務(wù)指派等，或許有些問題根本不需要精確解，而只要尋找到近似最優(yōu)解即可，所以智能算法尋優(yōu)問題目前已成為當(dāng)前的熱點(diǎn)研究方向。下面就盲目式和啟發(fā)式搜索、高級(jí)搜索、神經(jīng)網(wǎng)絡(luò)等算法分別作出詳細(xì)綜述。 3 1.無信息的搜索策略——盲目式搜索算法 即除了問題定義之外沒有任何關(guān)于狀態(tài)的附加信息，可做的事情只是生成后繼，并測(cè)試是否目標(biāo)狀態(tài)。盲目式搜索算法不考慮給定問題所具有的特定知識(shí), 系統(tǒng)根據(jù)事先確定好的某種固定排序, 依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則,一般統(tǒng)稱為無信息引導(dǎo)的搜索策略。典型的盲目搜索方法是深度優(yōu)先搜索和廣度優(yōu)先搜索。一般只適用于求解比較簡(jiǎn)單的問題。 1.1 廣度優(yōu)先搜索算法 又稱寬度優(yōu)先搜索算法，是最簡(jiǎn)便的圖的搜索算法之一，首先是擴(kuò)展根結(jié)點(diǎn)，接著擴(kuò)展根結(jié)點(diǎn)的所有后繼，然后再擴(kuò)展他們的后繼，以此類推，一般在下一層的任何結(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有結(jié)點(diǎn)都已經(jīng)擴(kuò)展過。之所以稱為廣度優(yōu)先算法，是因?yàn)樗惴ㄗ允贾两K一直通過已找到和末找到頂點(diǎn)之間的邊界向外擴(kuò)展。 如果最淺的目標(biāo)結(jié)點(diǎn)處于一個(gè)有限的深度，廣度優(yōu)先搜索在擴(kuò)展完比他淺的所有結(jié)點(diǎn)之后最終能找到這個(gè)目標(biāo)結(jié)點(diǎn)，所以說他是完備的。最淺目標(biāo)結(jié)點(diǎn)不一定是最優(yōu)目標(biāo)結(jié)點(diǎn)；技術(shù)上講如果路徑耗散是結(jié)點(diǎn)深度的非遞減函數(shù)，廣度優(yōu)先搜索才是最優(yōu)的。另外到目前為止，關(guān)于廣度優(yōu)先搜索的消息都是好的。 廣度優(yōu)先搜索算法時(shí)間和空間復(fù)雜度都比較高，當(dāng)目標(biāo)結(jié)點(diǎn)距離初始結(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無用的結(jié)點(diǎn)，搜索效率低，時(shí)間需求是一個(gè)很大的問題，特別是當(dāng)搜索深度較大時(shí)，尤為嚴(yán)重，但空間需求是比執(zhí)行時(shí)間更嚴(yán)重的問題。其優(yōu)點(diǎn)是目標(biāo)結(jié)點(diǎn)如果存在，用寬度優(yōu)先搜索可以找到該目標(biāo)結(jié)點(diǎn)。 1.2 代價(jià)一致搜索算法 代價(jià)一致搜索算法對(duì)一條路徑的步數(shù)并不關(guān)心，而只關(guān)心所經(jīng)步驟的總耗散，因此在擴(kuò)展到一個(gè)具有能返回同一狀態(tài)的零耗散行動(dòng)的結(jié)點(diǎn)時(shí)就會(huì)陷入無限循環(huán)。代價(jià)一致搜索由路徑的耗散引導(dǎo)而不是深度，代價(jià)一致搜索在搜索包括耗散大但可能是有用的步驟的路徑之前，可能而且經(jīng)常會(huì)先探索耗散小的步驟所在的很大的樹。 當(dāng)所有單步耗散相等的時(shí)候廣度優(yōu)先搜索時(shí)最優(yōu)的，因?yàn)樗偸窍葦U(kuò)展深度最淺的為擴(kuò)展結(jié)點(diǎn)。取代擴(kuò)展深度最淺結(jié)點(diǎn)，代價(jià)一致搜索擴(kuò)展的是路徑消耗最低的結(jié)點(diǎn)。如果當(dāng)所有單步耗散都相等的話，這種算法集合廣度優(yōu)先搜索算法相同。 1.3 深度優(yōu)先搜索算法（又名回溯) 深度優(yōu)先搜索算法總是擴(kuò)展搜索樹的當(dāng)前邊緣中最深的結(jié)點(diǎn)，搜索直接推進(jìn)到搜索樹的最深層，那里的結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，當(dāng)那些結(jié)點(diǎn)擴(kuò)展完之后，他們被從邊緣中去掉，然后搜索算法“向上回到”下一個(gè)還有未擴(kuò)展后繼結(jié)點(diǎn)的稍淺結(jié)點(diǎn)。 優(yōu)點(diǎn)：比寬度優(yōu)先搜索算法需要較少的時(shí)間，該算法只需要保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的結(jié)點(diǎn)標(biāo)志組成。因此，深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線性函數(shù)。 缺點(diǎn)：可能搜索到了錯(cuò)誤的路徑上（很多問題可能具有很深甚至無限搜索樹，如不幸選擇了一個(gè)錯(cuò)誤的路徑，則會(huì)一直搜索下去）要么陷入無 4 限循環(huán)而不能給出答案，要么最后找到一個(gè)答案，但路徑很長(zhǎng)且不是最優(yōu)答案（既不是完備的，也不是最優(yōu)的）對(duì)于深度較大的情況下，深度優(yōu)先搜索需要很長(zhǎng)的運(yùn)行時(shí)間而且不能解答[1]。 有界深度優(yōu)先搜索方法，總體上按深度優(yōu)先算法進(jìn)行，但對(duì)深度給出一個(gè)限制達(dá)到限制時(shí)沒有找到解答就停止對(duì)該分支的搜索，換到另一分支上。他是一種回避選擇最優(yōu)深度限制問題的策略。寬度優(yōu)先搜索算法需要指數(shù)數(shù)量的空間；深度的空間復(fù)雜度和最大搜索深度呈線性關(guān)系，迭代加深對(duì)一棵受控樹深度優(yōu)先搜索，結(jié)合寬度和深度優(yōu)點(diǎn)，即最優(yōu)的和完備的。 1.4 深度有限搜索算法 無邊界的搜索樹問題可以通過對(duì)深度優(yōu)先搜索提供一個(gè)預(yù)先設(shè)定的深度限制來解決，即深度為l 的結(jié)點(diǎn)被當(dāng)做沒有后繼的結(jié)點(diǎn)對(duì)待。這種方法就是深度有限搜索算法。他解決了無窮路徑的問題，但當(dāng)選擇ld 時(shí)深度有限搜索同樣也不是最優(yōu)的深度優(yōu)先搜索可以看做是深度有限搜索的一種特殊情況（其深度限制 l=∞）然而對(duì)于大多數(shù)問題，不到問題已經(jīng)解決我們是無法知道一個(gè)好的深度限制的。深度有限搜索也可以通過對(duì)一般的樹搜索算法或者遞歸深度優(yōu)先搜索算法進(jìn)行簡(jiǎn)單的修改來實(shí)現(xiàn) 1.5 迭代深入深度優(yōu)先搜索算法 它是一個(gè)用來尋找最合適的深度限制的通用策略，它經(jīng)常和深度優(yōu)先搜索結(jié)合使用（不斷地增大深度限制直到找到目標(biāo)結(jié)點(diǎn)）當(dāng)深度限制達(dá)到最淺目標(biāo)結(jié)點(diǎn)深度時(shí)，就能找到目標(biāo)結(jié)點(diǎn)。迭代深入搜索算法結(jié)合了深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法的優(yōu)點(diǎn)。他的空間需求和深度優(yōu)先搜索一樣小，他和廣度優(yōu)先搜索一樣當(dāng)分支因子有限時(shí)是完備的，當(dāng)路徑耗散是結(jié)點(diǎn)深度的非遞增函數(shù)時(shí)則是最優(yōu)的。迭代深入搜索因?yàn)樵谝豢妹繉拥姆种б蜃佣加邢嗤ɑ蚪葡嗤┑乃阉鳂渲薪^大多數(shù)都在底而上層結(jié)點(diǎn)生成多次影響不大并不像看起來那么浪費(fèi)。 迭代深入搜索和廣度優(yōu)先搜索是類似的，在每次迭代進(jìn)行到下一層之前要把整個(gè)當(dāng)前層的新結(jié)點(diǎn)全部探索過。發(fā)展類似于代價(jià)一致搜索的迭代搜索看起來是值得的，在繼承代價(jià)一致搜索的最優(yōu)化保證的同時(shí)避免了大量的內(nèi)存需求。主要思想是用不斷增加的路徑耗散限制代替不斷增加的深度限制，按照這種思想產(chǎn)生的算法被稱作“迭代延長(zhǎng)搜索”。不過不幸的是，與代價(jià)一致搜索相比，事實(shí)上迭代延長(zhǎng)將導(dǎo)致實(shí)在的額外開銷。 1.6 雙向搜索算法 雙向搜索算法的思想是運(yùn)行兩個(gè)同時(shí)的搜索——其中一個(gè)從初始狀態(tài)向前搜索而另一個(gè)從目標(biāo)狀態(tài)向后搜索，當(dāng)他們相遇時(shí)搜索終止。 雙向搜索時(shí)通過這樣一種方式實(shí)現(xiàn)的：讓他的一個(gè)或者全部搜索在擴(kuò)展結(jié)點(diǎn)之前先檢查該結(jié)點(diǎn)是否在另一棵搜索樹的邊緣結(jié)點(diǎn)集里；如果在，那么就找到了一個(gè)解。空間需求是雙向搜索最顯著的弱點(diǎn)，當(dāng)所用的兩個(gè)搜索都是廣度優(yōu)先搜索時(shí)，這個(gè)算法是完備的和最優(yōu)的（在相同單步耗散的情況下），其他搜索組合可能會(huì)犧牲完備性或最優(yōu)性，或者兩者都犧牲。雙向搜索中最困難的情況就是目標(biāo)測(cè)試只給出對(duì)可能很大的目標(biāo)狀態(tài)集合的一個(gè)隱性描述。 2.有信息的搜索——啟發(fā)式搜索算法 是一種在問題本身的定義之外的還利用問題的特定知識(shí)策略——如何能夠比無信息的策略更有效的找到解?？紤]問題領(lǐng)域可應(yīng)用的知識(shí), 動(dòng)態(tài)地確定規(guī)則的排序, 優(yōu)先調(diào)用較合適的規(guī)則使用。啟發(fā)式搜索彌補(bǔ)盲目搜索的不足，提高搜索效 5 率。 2.1 最佳優(yōu)先搜索算法 在最好優(yōu)先搜索算法中，搜索是從最有希望的結(jié)點(diǎn)開始，并且生成其所有的子結(jié)點(diǎn)，然后計(jì)算每個(gè)結(jié)點(diǎn)的性能，基于該性能選擇最有希望的結(jié)點(diǎn)擴(kuò)展（對(duì)所有結(jié)點(diǎn)進(jìn)行選擇優(yōu)點(diǎn)：如果早期選擇了一個(gè)錯(cuò)誤的結(jié)點(diǎn)，最好優(yōu)先搜索就提供了一個(gè)修改的機(jī)會(huì)），但是，該算法并沒有顯示地給出如何定義啟發(fā)式函數(shù)并且不能保證當(dāng)從起始節(jié)點(diǎn)到目的結(jié)點(diǎn)的最短路徑存在時(shí)，一定能夠找到他。（為此，需要對(duì)啟發(fā)式函數(shù)等進(jìn)行限制，A*算法就是對(duì)啟發(fā)式函數(shù)限制后得到的一種啟發(fā)式搜索算法） 2.2 貪婪最佳優(yōu)先搜索算法 試圖擴(kuò)展離目標(biāo)結(jié)點(diǎn)最近的結(jié)點(diǎn)建立在這樣可能很快找到解的基礎(chǔ)上，他的搜索代價(jià)最小而不是最優(yōu)，之所以稱之為“貪婪”，是因?yàn)樵诿恳徊剿家噲D找到離目標(biāo)盡可能最近的結(jié)點(diǎn)。 貪婪最佳優(yōu)先搜索算法再某些方面與深度搜索類似，它和深度優(yōu)先搜索算法一樣更傾向于沿著一條路徑搜索下去直到目標(biāo)，但在遇到死路的時(shí)候會(huì)退回，所以他和深度有同樣缺陷——他不是最優(yōu)的也不是最完備的（有可能沿著一條無限的路徑走下去而不回來嘗試其他的選擇）。 2.3 一般圖啟發(fā)式搜索A 算法 啟發(fā)式搜索算法A，簡(jiǎn)稱為A 算法，是一種典型的啟發(fā)式搜索算法。其基本思想是：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。利用評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)來排列OPEN 表節(jié)點(diǎn)順序的圖搜索。圖搜索算法只記錄狀態(tài)空間中那些被搜索過的狀態(tài)，他們組成一個(gè)搜索圖稱為G。 2.4 啟發(fā)式搜索算法A*，最小化總的估計(jì)解耗散 它把到達(dá)結(jié)點(diǎn)的耗散量和從該結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的消耗結(jié)合起來對(duì)結(jié)點(diǎn)進(jìn)行評(píng)價(jià)：f(n)=g(n)+h(n),g(n)給出了從起始結(jié)點(diǎn)到結(jié)點(diǎn)n 的路徑耗散，而h(n)是從結(jié)點(diǎn)n 到目標(biāo)結(jié)點(diǎn)的最低耗散路徑的估計(jì)耗散值。f(n)=經(jīng)過結(jié)點(diǎn)n 的最低耗散解估計(jì)耗散。 A*算法是完備的最優(yōu)的并且是有效地，但并不是說 A*算法對(duì)所有搜索問題的需求，對(duì)大多數(shù)搜索問題搜索目標(biāo)時(shí)的搜索空間的結(jié)點(diǎn)數(shù)仍然是目標(biāo)結(jié)點(diǎn)深度指數(shù)，從這個(gè)結(jié)果可以看到搜索過程中的復(fù)雜性仍然會(huì)以指數(shù)增長(zhǎng)，除非啟發(fā)式函數(shù)中差值的增長(zhǎng)沒有比實(shí)際路徑費(fèi)用的歲數(shù)來的大，對(duì)于大多數(shù)在實(shí)際中使用啟發(fā)式函數(shù)來說，差值至少和路徑的費(fèi)用成正比，并且指數(shù)增長(zhǎng)最終會(huì)使任何一臺(tái)計(jì)算機(jī)無法承受巨大的計(jì)算量。在 A*算法中計(jì)算時(shí)間不是主要問題，由于 A*算法把所有生成的結(jié)點(diǎn)保存，所以 A*算法在耗盡計(jì)算時(shí)間之前一般早已經(jīng)把空間耗盡了。 2.5 存儲(chǔ)限制的啟發(fā)式搜索算法 2.5.1 迭代加深A(yù)*算法IDA* 以深度優(yōu)先的方式在有限制的深度內(nèi)搜索目標(biāo)結(jié)點(diǎn)，該算法在每一個(gè)深度上檢查目標(biāo)結(jié)點(diǎn)是否出現(xiàn)，如果出現(xiàn)則停止，否則，加深加,繼續(xù)搜索，而A*算法是選擇具有最小估價(jià)函數(shù)值的結(jié)點(diǎn)擴(kuò)展，IDA*是上述兩種算法的結(jié)合。 IDA*與A*相比主要優(yōu)點(diǎn)是對(duì)于內(nèi)存的需求。A*算法需要指數(shù)級(jí)數(shù)量的存儲(chǔ)空間，因?yàn)闆]有深度方面限制，而 IDA*算法只有當(dāng)結(jié)點(diǎn)的所有子結(jié)點(diǎn)的 f(n)′小于限制值時(shí)才擴(kuò)展他，這樣就可以節(jié)省大量?jī)?nèi)存。當(dāng)啟發(fā)式函數(shù)是最優(yōu)的時(shí)候，IDA* 6 算法和A*算法擴(kuò)展相同的結(jié)點(diǎn)。 2.5.2 遞歸最佳優(yōu)先搜索算法 RBFS 是一個(gè)模仿標(biāo)準(zhǔn)的最佳優(yōu)先搜索的遞歸算法，但是他只使用線性的存儲(chǔ)空間。他的結(jié)構(gòu)和遞歸深度優(yōu)先搜索類似，但是它不沿著當(dāng)前的不確定路徑繼續(xù)下去，而是記錄從當(dāng)前結(jié)點(diǎn)的祖先可得到的最佳可替換路徑的f 值。如果當(dāng)前結(jié)點(diǎn)超過了這個(gè)限制，遞歸將轉(zhuǎn)回到替換的路徑上，當(dāng)遞歸回溯時(shí)，對(duì)回溯前的路徑上的每一個(gè)結(jié)點(diǎn)，RBFS 用其子結(jié)點(diǎn)的最佳 f 值替換其 f 值。這樣，RBFS 能記住被他遺忘的子樹中的最佳葉節(jié)點(diǎn) f 值，并因此能夠在以后某個(gè)時(shí)刻決定是否值得重新擴(kuò)展該子樹。 RBFS 算法比IDA*算法效率更高，但是他還是需要重復(fù)生成大量結(jié)點(diǎn)。像A*算法一樣，如果啟發(fā)函數(shù)h(n)是可采納的，那么RBFS 算法是最優(yōu)的，他的空間復(fù)雜度是 O（bd）,時(shí)間復(fù)雜度難以刻畫，既取決于他的啟發(fā)函數(shù)的準(zhǔn)確性，又取決于當(dāng)擴(kuò)展結(jié)點(diǎn)時(shí)改變最佳路徑的頻度，IDA*和 RBFS 都服從和圖搜索聯(lián)系在一起的潛在指數(shù)增長(zhǎng)復(fù)雜度，因?yàn)樗麄兌紵o法檢測(cè)除了當(dāng)前路徑上的狀態(tài)之外的重復(fù)狀態(tài)，因此，他們可能反復(fù)對(duì)一個(gè)狀態(tài)探索多次。IDA*和 RBFS 的問題在于利用的內(nèi)存過于小了。在兩次迭代之間，IDA*只保留一個(gè)數(shù)字：當(dāng)前的f 耗散值限制。RBFS 在內(nèi)存中保留的信息多一些，但他只能利用復(fù)雜度為O（bd）的內(nèi)存，即便有了更多可用的內(nèi)存，RBFS 也沒有辦法利用。 2.5.3 MA*和SMA*算法（儲(chǔ)限制Ａ*和簡(jiǎn)化MA*） SMA*算法和A*算法一樣，擴(kuò)展最佳葉結(jié)點(diǎn)直到內(nèi)存放滿為止。不丟棄一個(gè)舊結(jié)點(diǎn)他就無法在搜索樹上加入一個(gè)新結(jié)點(diǎn)，SMA*總是丟棄最差的一個(gè)葉結(jié)點(diǎn)——即f 值最高的。然后像RBFS 一樣把被遺忘結(jié)點(diǎn)的值備份到父結(jié)點(diǎn)。這樣被遺忘子樹的祖先結(jié)點(diǎn)可以了解那棵子樹中最佳路徑的質(zhì)量。只有當(dāng)所有其他路徑看來比被遺忘路徑要差的時(shí)候 SMA*才會(huì)利用這個(gè)信息重新生成該子樹。 從實(shí)用角度來講，SMA*算法是最好的尋找最優(yōu)解的通用算法，尤其當(dāng)狀態(tài)空間是一個(gè)圖，單步耗散不一致，并且與維護(hù)open 表和close 表的附加系統(tǒng)開銷相比生成結(jié)點(diǎn)更大的時(shí)候。然而，一些非常困難的問題中通常 SMA*算法將會(huì)在候選解路徑集里的路徑之間換來換去，只有一個(gè)很小的子集可以放到內(nèi)存中。那么重復(fù)生成相同的結(jié)點(diǎn)需要額外的時(shí)間意味著一個(gè)在有無限內(nèi)存的條件下能被Ａ*算法實(shí)際解決的問題，對(duì)于SMA*算法會(huì)成為不可操作的[2]。 2.6 與或圖的啟發(fā)式搜索算法AO* 對(duì)于與或圖來說，由于局部圖中有多個(gè)葉節(jié)點(diǎn)，不能像普通圖搜索那樣，通過對(duì)某一個(gè)節(jié)點(diǎn)的評(píng)價(jià)來實(shí)現(xiàn)對(duì)整個(gè)局部圖的評(píng)價(jià)。在普通圖搜索中，f(n)=g(n)+h(n)，表面上是對(duì)n 的評(píng)價(jià)，實(shí)際上是對(duì)通過n 的這條路徑的評(píng)價(jià)。因此對(duì)于與或圖搜索來說，就是通過對(duì)局部圖的評(píng)價(jià)來選擇待擴(kuò)展的節(jié)點(diǎn)。為了在AND-OR 圖中找到解需要一個(gè)類似于A*的算法，Nilsson 把它稱之為AO*算法。 AO*算法可以劃分為兩個(gè)階段，即圖生成過程和耗散值計(jì)算過程。 AO*算法類似于普通圖搜索中的 A*算法。在 A*算法中，對(duì)當(dāng)前搜索圖的"前沿"（即在OPEN 表中的節(jié)點(diǎn)）節(jié)點(diǎn)進(jìn)行評(píng)價(jià)，選取f 值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 他和A*算法的主要區(qū)別在于：1.AO*算法能夠處理AND 圖，他應(yīng)該找出一條路徑，即從該圖的開始結(jié)點(diǎn)出發(fā)到達(dá)代表解狀態(tài)的遺囑結(jié)點(diǎn)。2.如果有些路徑通往的結(jié)點(diǎn)是其他路徑上的結(jié)點(diǎn)擴(kuò)展出來的結(jié)點(diǎn)，那么不能獨(dú)立于這些路徑去考慮某些從結(jié)點(diǎn)到結(jié)點(diǎn)的個(gè)別路徑。A*算法中，從一結(jié)點(diǎn)到另一結(jié)點(diǎn)的預(yù)期路徑總是帶最低耗費(fèi)的路徑，但在 AO*算法中卻并非如此。3.AO*算法僅對(duì)保證不含有任何回路的圖進(jìn)行操作。這種保證是因?yàn)閮?chǔ)存一條回路路徑?jīng)]有必要。這樣的路徑代表了 7 一條循環(huán)推理鏈。此外，AO*算法沒有考慮子目標(biāo)間的任一交互。 3.局部搜索算法等高級(jí)算法 3.1 爬山搜索算法 爬山法 （hill-climbing）：登高將會(huì)在達(dá)到一個(gè)巔峰時(shí)終止，相鄰狀態(tài)沒有比他更高的值。他是一個(gè)向值增加的方向移動(dòng)的簡(jiǎn)單循環(huán)過程（最基本的局部搜索算法，在每一步中當(dāng)前的結(jié)點(diǎn)都會(huì)被最佳鄰結(jié)點(diǎn)所替代） 缺點(diǎn):該算法又稱作貪婪局部搜索算法，因?yàn)樗皇沁x擇鄰居狀態(tài)中最好的一個(gè)而事先不考慮之后下一步往哪個(gè)方向走。爬山算法從來不“下山”，即不會(huì)向值比當(dāng)前結(jié)點(diǎn)低的（或耗散高的）方向搜索，他肯定是不完備的因?yàn)樗赡芡Ａ粼诰植繕O大值上。 優(yōu)點(diǎn)：盡管這樣貪婪算法卻往往有很好的效果，爬山法能很快的朝著解得方向進(jìn)展，因?yàn)樗ǔ：苋菀滓粋€(gè)塊的狀態(tài)。 爬山狀態(tài)的成功與否在很大程度上取決于狀態(tài)空間地形圖的形狀，如果在圖中幾乎沒有局部極大值和高原，隨機(jī)重新開始的爬山法將會(huì)很快的找到好解。 3.2 局部剪枝搜索算法 只在內(nèi)存中保存一個(gè)結(jié)點(diǎn)看來是對(duì)內(nèi)存限制問題的一個(gè)極端反應(yīng)。局部剪枝搜索（local beam search）算法記錄k 個(gè)狀態(tài)而不是一個(gè)。它是由k 個(gè)隨機(jī)生成的狀態(tài)開始。每一步生成全部k 個(gè)狀態(tài)的所有后繼狀態(tài)，如果其中有一個(gè)是目標(biāo)狀態(tài)，算法就停止。否則，它從整個(gè)后繼列表中選擇k 個(gè)最佳的后繼，然后重復(fù)這個(gè)過程。 在其簡(jiǎn)單的形式中，局部剪枝搜索會(huì)受到這k 個(gè)狀態(tài)缺乏多樣性的影響——他們將很快聚集到狀態(tài)空間中的一小塊區(qū)域內(nèi)，使得搜索比一個(gè)代價(jià)高昂的爬山法版本略多一些。這個(gè)算法的變化稱為隨機(jī)剪枝搜索，以隨機(jī)爬山法類似，幫助緩解這個(gè)問題。隨機(jī)剪枝搜索不是從候選后繼集合中選擇最好的k 個(gè)后繼狀態(tài)，而是按一定概率隨機(jī)的選擇k 個(gè)后繼狀態(tài)，其中選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù)。隨機(jī)剪枝選擇和自然選擇的過程有些相似性[3]。 3.3 模擬退火搜索算法 （simulated annealing,SA）的思想最早是由Metropolis 等于1953 年提出的，SA 算法是基于 Mente Carlo 迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的搜索，優(yōu)化算法，目前已在工程中得到廣泛應(yīng)用，諸如VLSI，生產(chǎn)調(diào)度，控制工程，機(jī)器學(xué)習(xí)，神經(jīng)網(wǎng)絡(luò)，圖像處理等領(lǐng)域。 模擬退火算法將爬山法和隨機(jī)行走以某種方式結(jié)合起來，同時(shí)得到效率和完備性；在（冶金中，退火是增強(qiáng)金屬和玻璃的韌性和硬度，而先把它們加熱到高溫再讓它們逐漸冷卻過程，能使材料結(jié)合成一個(gè)低能量的結(jié)晶態(tài)）。模擬退火搜索算法和爬山搜索算法類似，不過它沒有選擇最佳的移動(dòng)而選擇隨機(jī)的移動(dòng)（一個(gè)允許下山的隨機(jī)爬山算法），在退火初期下山移動(dòng)容易被接受，而隨著時(shí)間的推移下山的次數(shù)越來越少。 模擬退火算法的實(shí)驗(yàn)性能具有質(zhì)量高，初值魯棒性強(qiáng)，通用易于實(shí)現(xiàn)的優(yōu)點(diǎn)。但是為了尋到最優(yōu)解的算法通常要求較高的初溫，較慢的降溫速率，較低的終止溫度以及各溫度下足夠多次的抽樣，因而模擬退火算法往往優(yōu)化過程過長(zhǎng)，這也 8 是SA 算法的缺點(diǎn)。 3.4 遺傳算法 （Genetic Algorithms 簡(jiǎn)稱GA）由美國(guó)michigan 大學(xué)John holland 教授創(chuàng)建的基于達(dá)爾文的進(jìn)化論和孟德爾的自然遺傳學(xué)說，是模擬遺傳選擇和自然淘汰的生物進(jìn)化過程的一種隨機(jī)搜索與全局優(yōu)化算法。 遺傳算法首先采用某種編碼方式將解空間映射到編碼空間，每個(gè)編碼對(duì)應(yīng)問題的一個(gè)解，稱為個(gè)體或染色體，再隨機(jī)確定起始的一群個(gè)體，稱為種群。在后續(xù)迭代中，按照適者生存原理，根據(jù)適應(yīng)度大小挑選個(gè)體，并借助各種遺傳算子對(duì)個(gè)體進(jìn)行交叉和變異，生成代表新的解集的種群，該種群比前代更適應(yīng)環(huán)境，如此進(jìn)化下去直到滿足優(yōu)化準(zhǔn)則。此時(shí)末代個(gè)體，經(jīng)過解碼，可作為問題近似最優(yōu)解。 遺傳算法以有限的代價(jià)解決搜索和優(yōu)化，其與傳統(tǒng)搜索方法的區(qū)別主要在于：①遺傳算法直接處理問題參數(shù)的適當(dāng)編碼而不是參數(shù)集本身。②遺傳算法按并行方式搜索一個(gè)種群數(shù)目的點(diǎn)，而不是單點(diǎn)。 ③ 遺傳算法不需要求導(dǎo)或其他輔助知識(shí)，只需要適應(yīng)度函數(shù)值。④ 遺傳算法使用概率轉(zhuǎn)換規(guī)則，而非確定的轉(zhuǎn)換規(guī)則指導(dǎo)搜索。⑤ 遺傳算法在搜索過程中不易陷入局部最優(yōu)，有較好的全局優(yōu)化能力。 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用模型，不依賴于問題的具體領(lǐng)域和種類，故它廣泛應(yīng)用于許多領(lǐng)域：函數(shù)優(yōu)化方面；組合優(yōu)化方面有背包問題，圖劃分問題等；生產(chǎn)調(diào)度問題方面有流水生產(chǎn)車間調(diào)度等；機(jī)器人學(xué)方面有路徑規(guī)劃等；圖象處理方面有模式識(shí)別，特征抽取等；機(jī)器學(xué)習(xí)方面有學(xué)習(xí)模糊控制規(guī)則等；數(shù)據(jù)挖掘方面有規(guī)則開采等[4]。 3.5 群集智能算法 受社會(huì)性昆蟲行為的啟發(fā)，計(jì)算機(jī)工作者通過對(duì)社會(huì)性昆蟲的模擬產(chǎn)生了一系列對(duì)于傳統(tǒng)問題的新的解決方法，這些研究就是群集智能的研究。群集智能中的群體指的是“一組相互之間可以進(jìn)行直接通信或者間接通信(通過改變局部環(huán)境)的主體，這組主體能夠合作進(jìn)行分布問題求解”。而所謂群集智能指的是“無智能的主體通過合作表現(xiàn)出智能行為的特性”。群集智能在沒有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題的解決方案提供了基礎(chǔ)。 群集智能的特點(diǎn)和優(yōu)點(diǎn)：群體中相互合作的個(gè)體是分布式的，這樣更能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài); 沒有中心的控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性，不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問題的求解。可以不通過個(gè)體之間直接通信而是通過非直接通信進(jìn)行合作，這樣的系統(tǒng)具有更好的可擴(kuò)充性。由于系統(tǒng)中個(gè)體的增加而增加的系統(tǒng)的通信開銷在這里十分小。系統(tǒng)中每個(gè)個(gè)體的能力十分簡(jiǎn)單，這樣每個(gè)個(gè)體的執(zhí)行時(shí)間比較短，并且實(shí)現(xiàn)也比較簡(jiǎn)單，具有簡(jiǎn)單性。因?yàn)榫哂羞@些優(yōu)點(diǎn)，雖說群集智能的研究還處于初級(jí)階段，并且存在許多困難，但是可以預(yù)言群集智能的研究代表了以后計(jì)算機(jī)研究發(fā)展的一個(gè)重要方向。 在計(jì)算智能領(lǐng)域有兩種基于群智能的算法，螞群算法和粒子群算法前者是對(duì)螞蟻群落食物采集過程的模擬，已經(jīng)成功運(yùn)用在很多離散優(yōu)化問題上。 3.5.1 蟻群算法 (ant colony optimization, ACO)又叫螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。20 世紀(jì)90 年代初意大利學(xué)者M(jìn).Dorigo等通過模擬螞蟻搜索路徑的行為，提出了一種新型的仿生優(yōu)化算法——蟻群算法，并將其應(yīng)用于經(jīng)典的旅行商問題( TSP) ,取得了較好的實(shí)驗(yàn)效果, 在二次分 9 配問題(QAP) ,車間任務(wù)調(diào)度問題(JSP) 等問題中也得到了成功的應(yīng)用。 螞蟻在運(yùn)動(dòng)過程中，在它所經(jīng)過的路程上留下信息素并感知信息素的存在及其強(qiáng)度朝著強(qiáng)度高的方向移動(dòng)，因此，由大量螞蟻組成的蟻群集體行為表現(xiàn)出一種信息正反饋現(xiàn)象。某一路徑上走過的螞蟻越多，后來的螞蟻選擇該路徑概率就越大，螞蟻個(gè)體之間就是通過這種信息的交流進(jìn)行路徑的最優(yōu)選擇，從而達(dá)到搜索食物的目的。 蟻群算法采用了正反饋并行自催化機(jī)制，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法結(jié)合的優(yōu)點(diǎn)，在短期內(nèi)得到了很大發(fā)展，其應(yīng)用領(lǐng)域也不斷得到擴(kuò)展，顯示了其在求解復(fù)雜的組合優(yōu)化問題方面已展現(xiàn)出其優(yōu)異的性能和巨大的發(fā)展?jié)摿?。同時(shí)由于蟻群算法收斂速度慢，容易發(fā)生停滯，易于陷入局部最優(yōu)解等不足，國(guó)內(nèi)外專家學(xué)者對(duì)其進(jìn)行了不斷的改進(jìn)，提高了算法的性能。 蟻群算法是一種模擬進(jìn)化算法,初步的研究表明該算法具有許多優(yōu)良的性質(zhì).針對(duì) PID 控制器參數(shù)優(yōu)化設(shè)計(jì)問題,將蟻群算法與遺傳算法的設(shè)計(jì)結(jié)果進(jìn)行了比較,數(shù)值仿真結(jié)果表明,蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。蟻群算法是一種求解組合最優(yōu)化問題的新型通用啟發(fā)式方法，該方法具有正反饋、分布式計(jì)算和富于建設(shè)性的貪婪的特點(diǎn)。 3.5.2 粒子群優(yōu)化算法(Particle Swarm optimization，PSO)是一種進(jìn)化計(jì)算技術(shù)，有Eberhart 博士和Kennedy 博士發(fā)明。源于對(duì)鳥群捕食的行為研究。 PSO 模擬鳥群的捕食行為。一群鳥在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。PSO 中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。稱之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。 PSO 同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過疊代搜尋最優(yōu)值。與遺傳算法比較，PSO 的信息共享機(jī)制是很不同的。在遺傳算法中，染色體 互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。在 PSO 中, 只有 gBest (or lBest) 給出信息給其他的粒子， 這是單向的信息流動(dòng)。整個(gè)搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程。與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法，同時(shí) PSO 速度比較快而且可以得到比較好的結(jié)果。 同遺傳算法比較，PSO 的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解。但是，PSO沒有遺傳操作如交叉和變異，而是根據(jù)自己的速度來決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶[5]。 4.人工神經(jīng)網(wǎng)絡(luò)算法 “人工神經(jīng)網(wǎng)絡(luò)”(Artificial Neural Network 簡(jiǎn)稱 ANN)是在對(duì)人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的認(rèn)識(shí)理解基礎(chǔ)之上模擬其結(jié)構(gòu)和智能行為的一種工程系統(tǒng)。早在本世紀(jì) 40 年代初期，心理學(xué)家 McCulloch、數(shù)學(xué)家 Pitts 就提出了人工神經(jīng) 10 網(wǎng)絡(luò)的第一個(gè)數(shù)學(xué)模型，從此開創(chuàng)了神經(jīng)科學(xué)理論的研究時(shí)代。其后，F(xiàn) Rosenblatt、Widrow 和J. J .Hopfield 等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展。 人工神經(jīng)網(wǎng)絡(luò)是由大量的神經(jīng)元廣泛互連而成的系統(tǒng)，它的這一結(jié)構(gòu)特點(diǎn)決定著人工神經(jīng)網(wǎng)絡(luò)具有高速信息處理的能力。人腦的每個(gè)神經(jīng)元大約有 103～104 個(gè)樹突及相應(yīng)的突觸，一個(gè)人的大腦總計(jì)約形成 1014～1015 個(gè)突觸。用神經(jīng)網(wǎng)絡(luò)的術(shù)語來說，即是人腦具有 1014～1015 個(gè)互相連接的存儲(chǔ)潛力。雖然每個(gè)神經(jīng)元的運(yùn)算功能十分簡(jiǎn)單，且信號(hào)傳輸速率也較低(大約 100 次/秒)，但由于各神經(jīng)元之間的極度并行互連功能，最終使得一個(gè)普通人的大腦在約1 秒內(nèi)就能完成現(xiàn)行計(jì)算機(jī)至少需要數(shù) 10 億次處理步驟才能完成的任務(wù)。人工神經(jīng)網(wǎng)絡(luò)是一種非線性的處理單元。只有當(dāng)神經(jīng)元對(duì)所有的輸入信號(hào)的綜合處理結(jié)果超過某一門限值后才輸出一個(gè)信號(hào)。因此神經(jīng)網(wǎng)絡(luò)是一種具有高度非線性的超大規(guī)模連續(xù)時(shí)間動(dòng)力學(xué)系統(tǒng)。它突破了傳統(tǒng)的以線性處理為基礎(chǔ)的數(shù)字電子計(jì)算機(jī)的局限，標(biāo)志著人們智能信息處理能力和模擬人腦智能行為能力的一大飛躍[6]。 4.1 多層感知網(wǎng)絡(luò)(誤差逆?zhèn)鞑ド窠?jīng)網(wǎng)絡(luò)) （Back Propagation，BP）網(wǎng)絡(luò)是 1986 年由 Rumelhart 和 McCelland為首的科學(xué)家小組提出，是一種按誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò)，是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。BP 網(wǎng)絡(luò)能學(xué)習(xí)和存貯大量的輸入-輸出模式映射關(guān)系，而無需事前揭示描述這種映射關(guān)系的數(shù)學(xué)方程。它的學(xué)習(xí)規(guī)則是使用最速下降法，通過反向傳播來不斷調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，使網(wǎng)絡(luò)的誤差平方和最小。BP 神經(jīng)網(wǎng)絡(luò)模型拓?fù)浣Y(jié)構(gòu)包括輸入層、隱層和輸出層，相鄰層之間的各神經(jīng)元實(shí)現(xiàn)全連接且每層各神經(jīng)元之間無連接。 BP 算法是一種有監(jiān)督式的學(xué)習(xí)算法，其主要思想是：輸入學(xué)習(xí)樣本，使用反向傳播算法對(duì)網(wǎng)絡(luò)的權(quán)值和偏差進(jìn)行反復(fù)的調(diào)整訓(xùn)練，使輸出的向量與期望向量盡可能地接近，當(dāng)網(wǎng)絡(luò)輸出層的誤差平方和小于指定的誤差時(shí)訓(xùn)練完成，保存網(wǎng)絡(luò)的權(quán)值和偏差。 但BP 網(wǎng)并不是十分的完善，它存在以下一些主要缺陷：學(xué)習(xí)收斂速度太慢、網(wǎng)絡(luò)的學(xué)習(xí)記憶具有不穩(wěn)定性，即：當(dāng)給一個(gè)訓(xùn)練好的網(wǎng)提供新的學(xué)習(xí)記憶模式時(shí)，將使已有的連接權(quán)值被打亂，導(dǎo)致已記憶的學(xué)習(xí)模式的信息的消失。 4.2 競(jìng)爭(zhēng)型(KOHONEN)神經(jīng)網(wǎng)絡(luò) 競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的基本思想是網(wǎng)絡(luò)競(jìng)爭(zhēng)層各神經(jīng)元競(jìng)爭(zhēng)對(duì)輸入模式的響應(yīng)機(jī)會(huì)，最后僅有一個(gè)神經(jīng)元成為競(jìng)爭(zhēng)的勝者，并且只將與獲勝神經(jīng)元有關(guān)的各連接權(quán)值進(jìn)行修正，使之朝著更有利于它競(jìng)爭(zhēng)的方向調(diào)整。神經(jīng)網(wǎng)絡(luò)工作時(shí)，對(duì)于某一輸入模式，網(wǎng)絡(luò)中與該模式最相近的學(xué)習(xí)輸入模式相對(duì)應(yīng)的競(jìng)爭(zhēng)層神經(jīng)元將有最大的輸出值，即以競(jìng)爭(zhēng)層獲勝神經(jīng)元來表示分類結(jié)果。這是通過競(jìng)爭(zhēng)得以實(shí)現(xiàn)的，實(shí)際上也就是網(wǎng)絡(luò)回憶聯(lián)想的過程。 競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)和不足：因?yàn)樗鼉H以輸出層中的單個(gè)神經(jīng)元代表某一類模式。所以一旦輸出層中的某個(gè)輸出神經(jīng)元損壞，則導(dǎo)致該神經(jīng)元所代表的該模式信息全部丟失。 4.3 Hopfield 神經(jīng)網(wǎng)絡(luò) 1986 年美國(guó)物理學(xué)家 J.J.Hopfield 提出的 Hopfield 神經(jīng)網(wǎng)絡(luò)是一層單層反饋非線性神經(jīng)網(wǎng)絡(luò)，是神經(jīng)網(wǎng)絡(luò)發(fā)展史上的一個(gè)重要里程碑。他利用非線性動(dòng)力學(xué)系統(tǒng)理論中的能量函數(shù)方法研究反饋人工神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性，并利用此方法建立求解優(yōu)化計(jì)算問題的系統(tǒng)方程式。 11 網(wǎng)絡(luò)中的每一個(gè)神經(jīng)元都將自己的輸出通過連接權(quán)傳送給所有其它神經(jīng)元，同時(shí)又都接收所有其它神經(jīng)元傳遞過來的信息，所以 Hopfield 神經(jīng)網(wǎng)絡(luò)是一個(gè)反饋型的網(wǎng)絡(luò)。其狀態(tài)變化可以用差分方程來表征。反饋型網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)就是它具有穩(wěn)定狀態(tài)。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時(shí)候，也就是它的能量函數(shù)達(dá)到最小的時(shí)候。這里的能量函數(shù)是在表達(dá)形式上與物理意義上的能量概念一致，來表征網(wǎng)絡(luò)狀態(tài)的變化的趨勢(shì)，并可以依據(jù) Hopfield 工作運(yùn)行規(guī)則不斷進(jìn)行狀態(tài)變化，最終能夠達(dá)到的某個(gè)極小值的目標(biāo)函數(shù)。網(wǎng)絡(luò)收斂就是指能量函數(shù)達(dá)到極小值。如果把一個(gè)最優(yōu)化問題的目標(biāo)函數(shù)轉(zhuǎn)換成網(wǎng)絡(luò)的能量函數(shù)，把問題的變量對(duì)應(yīng)于網(wǎng)絡(luò)的狀態(tài)，那么Hopfield 神經(jīng)網(wǎng)絡(luò)就能夠用于解決優(yōu)化組合問題。 Hopfield 神經(jīng)網(wǎng)絡(luò)的能量函數(shù)是朝著梯度減小的方向變化，但它仍然存在一個(gè)問題，那就是一旦能量函數(shù)陷入到局部極小值，它將不能自動(dòng)跳出局部極小點(diǎn)，到達(dá)全局最小點(diǎn)，因而無法求得網(wǎng)絡(luò)最優(yōu)解[7]。 5.展望： 雖然目前的人工智能算法研究水平暫時(shí)還很難使“人工智能機(jī)器”真正具備人類的常識(shí)和思維，但人工智能算法將會(huì)在今后的各個(gè)領(lǐng)域得到蓬勃發(fā)展。不僅僅只是功能模仿要持有信息機(jī)理一致的觀點(diǎn)。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。這兩者的結(jié)合將開辟一個(gè)全新的領(lǐng)域，開辟很多新的研究方向。人工智算法將探索智能的新概念，新理論，新方法和新技術(shù)來引導(dǎo)人工智能在我們社會(huì)生活和科學(xué)技術(shù)的跨躍，而這一切將在以后的發(fā)展中取得重大成就[8]。 致謝： 在本論文的寫作過程中，我的導(dǎo)師傾注了大量的心血，從選題到開題報(bào)告，從寫作提綱，到一遍又一遍地指出每稿中的具體問題，嚴(yán)格把關(guān)，循循善誘，在此我表示衷心感謝。同時(shí)我還要感謝在我學(xué)習(xí)期間給我極大關(guān)心和支持的各位老師以及關(guān)心我的同學(xué)和朋友。 參考文獻(xiàn)： [1]賁可榮，張彥鐸.人工智能[M]：清華大學(xué)出版社，2006.3 [2]Stuart Russell，Peter Norvig . Artificial Intelligence A Modern Approach[M].2版.姜哲等譯.人民郵電出版社，2004.6 [3]邵軍力，張景，魏長(zhǎng)華.人工智能基礎(chǔ)[M]：電子工業(yè)出版社，2000.3 [4]Thomas Dean，James Allen，Yiannis Aloimonos, 人工智能——理論與實(shí)踐[M].劉海波，宇等譯.電子工業(yè)出版社，2004.6 [5]朱福喜，湯怡群，傅建明.人工智能原理[M]：武漢大學(xué)出版社，2002.2 [6]Fredric M.Ham Ivica Kostanic.神經(jīng)計(jì)算原理[M]. 葉世偉，王海娟譯.機(jī)械工業(yè)出版社，2007.5 [7]丁永生.計(jì)算智能——理論、技術(shù)與應(yīng)用[M]：科學(xué)出版社，2004.8 [8]黃席樾，向長(zhǎng)城，殷禮勝.現(xiàn)代智能算法理論及應(yīng)用[M].2 版：科學(xué)出版社，2005.4
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
