智能算法匯總 2

智能算法匯總一、遺傳算法定義：遺傳算法(GeneticAlgorithm)是一類(lèi)借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來(lái)的隨機(jī)化搜索方法。主要特點(diǎn)：直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。應(yīng)用 廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能算法中的關(guān)鍵技術(shù)。遺傳算法的基本運(yùn)算過(guò)程如下：初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。交叉運(yùn)算：將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P(t1)。終止條件判斷:若t=匚則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。缺點(diǎn)1、 早熟。這是最大的缺點(diǎn)，即算法對(duì)新空間的探索能力是有限的，也容易收斂到局部最優(yōu)解。2、 大量計(jì)算。涉及到大量個(gè)體的計(jì)算，當(dāng)問(wèn)題復(fù)雜時(shí)，計(jì)算時(shí)間是個(gè)問(wèn)題。3、 處理規(guī)模小。目前對(duì)于維數(shù)較高的問(wèn)題，還是很難處理和優(yōu)化的。4、 難于處理非線性約束。對(duì)非線性約束的處理，大部分算法都是添加懲罰因子，這是一筆不小的開(kāi)支。5、穩(wěn)定性差。因?yàn)樗惴▽儆陔S機(jī)類(lèi)算法，需要多次運(yùn)算，結(jié)果的可靠性差，不能穩(wěn)定的得到解。F）總結(jié)優(yōu)點(diǎn)是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全局最優(yōu)解，全局搜索能力強(qiáng)；缺點(diǎn)是收斂較慢，局部搜索能力較弱，運(yùn)行時(shí)間長(zhǎng)，且容易受參數(shù)的影響。二、禁忌搜索算法A） 定義禁忌（TabuSearch）算法是一種亞啟發(fā)式（meta-heuristic）隨機(jī)搜索算法，它從一個(gè)初始可行解出發(fā)，選擇一系列的特定搜索方向（移動(dòng)）作為試探，選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動(dòng)。B） 方法為了避免陷入局部最優(yōu)解，TS搜索中采用了一種靈活的“記憶，技術(shù)，對(duì)已經(jīng)進(jìn)行的優(yōu)化過(guò)程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，這就是Tabu表的建立。C） 應(yīng)用迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來(lái)又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢(shì)。D） 特點(diǎn)禁忌搜索是對(duì)人類(lèi)思維過(guò)程本身的一種模擬，它通過(guò)對(duì)一些局部最優(yōu)解的禁忌（也可以說(shuō)是記憶）達(dá)到接納一部分較差解，從而跳出局部搜索的目的.。對(duì)于找到的一部分局部最優(yōu)解，有意識(shí)地避開(kāi)它（但不是完全隔絕），從而獲得更多的搜索區(qū)間。E） 缺陷對(duì)于出事劫具有較強(qiáng)的依賴(lài)性，一個(gè)較好的初始解可是禁忌搜索在解空間中搜索到更好的解，而一個(gè)較差的初始解則會(huì)降低禁忌搜索的收斂速度，搜索到的解也相對(duì)較差；此外，其搜索只是單操作，即在搜索過(guò)程中初始解只能有一個(gè)，在每代也只是把一個(gè)解移到另一解。三、模擬退火法A） 解釋模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。B） 應(yīng)用模擬退火算法（SimulatedAnnealing，SA）最早由Kirkpatrick等應(yīng)用于組合優(yōu)化領(lǐng)域，它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。C） 優(yōu)點(diǎn)局部搜索能力強(qiáng)，運(yùn)行時(shí)間較短；模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S（是算法迭代的起點(diǎn)）無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法;模擬退火算法具有并行性。D） 缺點(diǎn)是全局搜索能力差，容易受參數(shù)的影響。四、神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法A） 詮釋?zhuān)喝斯ど窠?jīng)網(wǎng)絡(luò)就是模擬人思維的第二種方式。這是一個(gè)非線性動(dòng)力學(xué)系統(tǒng)，其特色在于信息的分布式存儲(chǔ)和并行協(xié)同處理。雖然單個(gè)神經(jīng)元的結(jié)構(gòu)極其簡(jiǎn)單，功能有限，但大量神經(jīng)元構(gòu)成的網(wǎng)絡(luò)系統(tǒng)所能實(shí)現(xiàn)的行為卻是極其豐富多彩的。B） 神經(jīng)網(wǎng)絡(luò)的研究?jī)?nèi)容（1） 生物原型研究。從生理學(xué)、心理學(xué)、解剖學(xué)、腦科學(xué)、病理學(xué)等生物科學(xué)方面研究神經(jīng)細(xì)胞、神經(jīng)網(wǎng)絡(luò)、神經(jīng)系統(tǒng)的生物原型結(jié)構(gòu)及其功能機(jī)理。（2） 建立理論模型。根據(jù)生物原型的研究，建立神經(jīng)元、神經(jīng)網(wǎng)絡(luò)的理論模型。其中包括概念模型、知識(shí)模型、物理化學(xué)模型、數(shù)學(xué)模型等。（3） 網(wǎng)絡(luò)模型與算法研究。在理論模型研究的基礎(chǔ)上構(gòu)作具體的神經(jīng)網(wǎng)絡(luò)模型，以實(shí)現(xiàn)計(jì)算機(jī)模擬或準(zhǔn)備制作硬件，包括網(wǎng)絡(luò)學(xué)習(xí)算法的研究。這方面的工作也稱(chēng)為技術(shù)模型研究。（4） 人工神經(jīng)網(wǎng)絡(luò)應(yīng)用系統(tǒng)。在網(wǎng)絡(luò)模型與算法研究的基礎(chǔ)上，利用人工神經(jīng)網(wǎng)絡(luò)組成實(shí)際的應(yīng)用系統(tǒng)，例如，完成某種信號(hào)處理或模式識(shí)別的功能、構(gòu)作專(zhuān)家系統(tǒng)、制成機(jī)器人等等。C）原理：人工神經(jīng)網(wǎng)絡(luò)首先要以一定的學(xué)習(xí)準(zhǔn)則進(jìn)行學(xué)習(xí)，然后才能工作?，F(xiàn)以人工神經(jīng)網(wǎng)絡(luò)對(duì)手寫(xiě)“A”、"B”兩個(gè)字母的識(shí)別為例進(jìn)行說(shuō)明，規(guī)定當(dāng)“A”輸入網(wǎng)絡(luò)時(shí)，應(yīng)該輸出“1”，而當(dāng)輸入為“B”時(shí)，輸出為“0”。所以網(wǎng)絡(luò)學(xué)習(xí)的準(zhǔn)則應(yīng)該是：如果網(wǎng)絡(luò)作出錯(cuò)誤的的判決，則通過(guò)網(wǎng)絡(luò)的學(xué)習(xí)，應(yīng)使得網(wǎng)絡(luò)減少下次犯同樣錯(cuò)誤的可能性。首先，給網(wǎng)絡(luò)的各連接權(quán)值賦予（0，1）區(qū)間內(nèi)的隨機(jī)值，將“A”所對(duì)應(yīng)的圖象模式輸入給網(wǎng)絡(luò)，網(wǎng)絡(luò)將輸入模式加權(quán)求和、與門(mén)限比較、再進(jìn)行非線性運(yùn)算，得到網(wǎng)絡(luò)的輸出。在此情況下，網(wǎng)絡(luò)輸出為“1”和“0”的概率各為50%，也就是說(shuō)是完全隨機(jī)的。這時(shí)如果輸出為“1”（結(jié)果正確），則使連接權(quán)值增大，以便使網(wǎng)絡(luò)再次遇到“A”模式輸入時(shí)，仍然能作出正確的判斷。如果輸出為“0”（即結(jié)果錯(cuò)誤），則把網(wǎng)絡(luò)連接權(quán)值朝著減小綜合輸入加權(quán)值的方向調(diào)整，其目的在于使網(wǎng)絡(luò)下次再遇到“A”模式輸入時(shí)，減小犯同樣錯(cuò)誤的可能性。如此操作調(diào)整，當(dāng)給網(wǎng)絡(luò)輪番輸入若干個(gè)手寫(xiě)字母“A”、“B”后，經(jīng)過(guò)網(wǎng)絡(luò)按以上學(xué)習(xí)方法進(jìn)行若十次學(xué)習(xí)后，網(wǎng)絡(luò)判斷的正確率將大大提高。這說(shuō)明網(wǎng)絡(luò)對(duì)這兩個(gè)模式的學(xué)習(xí)已經(jīng)獲得了成功，它已將這兩個(gè)模式分布地記憶在網(wǎng)絡(luò)的各個(gè)連接權(quán)值上。當(dāng)網(wǎng)絡(luò)再次遇到其中任何一個(gè)模式時(shí)，能夠作出迅速、準(zhǔn)確的判斷和識(shí)別。一般說(shuō)來(lái)，網(wǎng)絡(luò)中所含的神經(jīng)元個(gè)數(shù)越多，則它能記憶、識(shí)別的模式也就越多。五、蟻群算法A） 定義：蟻群算法（antcolonyoptimization,ACO），又稱(chēng)螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。B） 優(yōu)點(diǎn)：蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì).針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問(wèn)題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。C） 設(shè)計(jì)：為螞蟻設(shè)計(jì)一個(gè)人工智能的程序，首先，你要讓螞蟻能夠避開(kāi)障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開(kāi)障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小，螞蟻算法的規(guī)則綜合起來(lái)具有下面兩個(gè)方面的特點(diǎn)： 1、多樣性2、正反饋主要特點(diǎn)就是：通過(guò)正反饋、分布式協(xié)作來(lái)尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過(guò)個(gè)體間簡(jiǎn)單的信息傳遞，搜索從蟻巢全食物間最短路徑的集體尋優(yōu)特征，以及該過(guò)程與旅行商問(wèn)題求解之間的相似性。得到了具有NP難度的旅行商問(wèn)題的最優(yōu)解答。同時(shí)，該算法還被用于求解Job-Shop調(diào)度問(wèn)題、二次指派問(wèn)題以及多維背包問(wèn)題等，顯示了其適用于組合優(yōu)化類(lèi)問(wèn)題求解的優(yōu)越特征。應(yīng)用：多年來(lái)世界各地研究工作者對(duì)蟻群算法進(jìn)行了精心研究和應(yīng)用開(kāi)發(fā)，該算法現(xiàn)己被大量應(yīng)用于數(shù)據(jù)分析、機(jī)器人協(xié)作問(wèn)題求解、電力、通信、水利、采礦、化工、建筑、交通等領(lǐng)域。六、粒子群優(yōu)化算法定義：粒子群優(yōu)化算法(ParticleSwarmoptimization,PSO)又翻譯為粒子群算法、微粒群算法、或微粒群優(yōu)化算法。是通過(guò)模擬鳥(niǎo)群覓食行為而發(fā)展起來(lái)的一種基于群體協(xié)作的隨機(jī)搜索算法?；具\(yùn)算過(guò)程①種群隨機(jī)初始化。 ②對(duì)種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitnessvalue)。適應(yīng)值與最優(yōu)解的距離直接有關(guān)。 ③種群根據(jù)適應(yīng)值進(jìn)行復(fù)制。④如果終止條件滿(mǎn)足的話，就停止，否則轉(zhuǎn)步驟②。PSO和遺傳算法共同之處：兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解。不同之處：PSO沒(méi)有遺傳操作如交叉(crossover)和變異(mutation)，而是根據(jù)自己的速度來(lái)決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。與遺傳算法比較，PSO的信息共享機(jī)制是很不同的。在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。在PSO中，只有g(shù)Best(orlBest)給出信息給其他的粒子，這是單向的信息流動(dòng)。整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)解的過(guò)程。與遺傳算法比較，在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解。演化計(jì)算的優(yōu)勢(shì)：在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或者沒(méi)有梯度信息存在。缺點(diǎn)在于：1、在某些問(wèn)題上性能并不是特別好。2.網(wǎng)絡(luò)權(quán)重的編碼而且遺傳算子的選擇有時(shí)比較麻煩。近期研究：最近已經(jīng)有一些利用PSO來(lái)代替反向傳播算法來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒(méi)有遺傳算法碰到的問(wèn)題。七、人工生命計(jì)算算法人工生命(AL:Artificiallife)是通過(guò)人工模擬生命系統(tǒng)，來(lái)研究生命的領(lǐng)域。人工生命的概念，包括兩個(gè)方面內(nèi)容：1)、屬于計(jì)算機(jī)科學(xué)領(lǐng)域的虛擬生命系統(tǒng)，涉及計(jì)算機(jī)軟件工程與人工智能技術(shù)，以及2)、基因工程技術(shù)人工改造生物的工程生物系統(tǒng)，涉及合成生物學(xué)技術(shù)。需要運(yùn)用很多計(jì)算機(jī)程序與計(jì)算機(jī)模擬，包括進(jìn)化算法evolutionarycomputation(evolutionaryalgorithms(EA)，遺傳算法geneticalgorithms(GA),遺傳編程geneticprogramming(GP),群體智慧swarmintelligence(SI),蟻群優(yōu)化antcolonyoptimization(ACO))人工化學(xué)合成artificialchemistries(AC),智能體agent-basedmodels,and細(xì)胞自動(dòng)機(jī)cellularautomata(CA).這些領(lǐng)域通常被視作AL的亞領(lǐng)域，這些領(lǐng)域的論題以及其他一些暫時(shí)未歸于其他領(lǐng)域的相關(guān)技術(shù)問(wèn)題，在他們