第9章智能計(jì)算

第九章智能計(jì)算人工智能概論目錄遺傳算法遺傳算法進(jìn)化算法的產(chǎn)生與發(fā)展人工智能相關(guān)概念粒子群優(yōu)化算法進(jìn)化算法的產(chǎn)生與發(fā)展進(jìn)化算法的概念進(jìn)化算法（evolutionaryalgorithm，EA）是基于自然選擇和自然遺傳等生物進(jìn)化機(jī)制的一種搜索算法。進(jìn)化算法是以達(dá)爾文的進(jìn)化論思想為基礎(chǔ)，通過(guò)模擬生物進(jìn)化過(guò)程與機(jī)制來(lái)求解問(wèn)題的自組織、自適應(yīng)的人工智能技術(shù)，是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。人工智能基礎(chǔ)進(jìn)化算法的生物學(xué)背景進(jìn)化算法類似于生物進(jìn)化，需要經(jīng)過(guò)長(zhǎng)時(shí)間的成長(zhǎng)演化，最后收斂到最優(yōu)化問(wèn)題的一個(gè)或者多個(gè)解。因此，了解一些生物進(jìn)化過(guò)程，有助于理解遺傳算法的工作過(guò)程?！斑m者生存”揭示了大自然生物進(jìn)化過(guò)程中的一個(gè)規(guī)律：比較適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。生物進(jìn)化的基本過(guò)程如圖所示。進(jìn)化算法的產(chǎn)生與發(fā)展進(jìn)化算法的設(shè)計(jì)原則進(jìn)化算法的產(chǎn)生與發(fā)展適用性原則：一個(gè)算法的適用性是指該算法所能適用的問(wèn)題種類，它取決于算法所需限制與假定。優(yōu)化的問(wèn)題不同，則相應(yīng)的處理方式也不同?？煽啃栽瓌t一個(gè)算法的可靠性是指算法對(duì)于所設(shè)計(jì)的問(wèn)題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問(wèn)題的能力。因?yàn)檠莼?jì)算的結(jié)果帶有一定的隨機(jī)性和不確定性，所以在圖9.1生物進(jìn)化的基本過(guò)程人工智能概論（微課版）144設(shè)計(jì)算法時(shí)應(yīng)盡量經(jīng)過(guò)較大樣本的檢驗(yàn)，以確認(rèn)算法是否具有較高的可靠性。收斂性原則指算法能否收斂到全局最優(yōu)。在收斂的前提下，希望算法具有較快的收斂速度。穩(wěn)定性原則指算法對(duì)其控制參數(shù)及問(wèn)題的數(shù)據(jù)的敏感度。如果算法對(duì)其控制參數(shù)或問(wèn)題的數(shù)據(jù)十分敏感，則依據(jù)它們?nèi)≈档牟煌瑢⒖赡墚a(chǎn)生不同的結(jié)果，甚至過(guò)早地收斂到某一局部最優(yōu)解。所以，在設(shè)計(jì)算法時(shí)應(yīng)盡量使得算法對(duì)一組固定的控制參數(shù)能在較廣泛的問(wèn)題的數(shù)據(jù)范圍內(nèi)解題，而且對(duì)一組給定的問(wèn)題數(shù)據(jù)，算法對(duì)其控制參數(shù)的微小擾動(dòng)不那么敏感。生物類比原則因?yàn)檫M(jìn)化算法的設(shè)計(jì)思想是基于生物演化過(guò)程的，所以那些在生物界被認(rèn)為是有效的方法及操作可以通過(guò)類比的方法引入算法中，有時(shí)會(huì)帶來(lái)較好的結(jié)果。遺傳算法遺傳算法是人工智能的重要新分支，是基于達(dá)爾文進(jìn)化論，在微型計(jì)算機(jī)上模擬生命進(jìn)化機(jī)制而發(fā)展起來(lái)的一門新學(xué)科。它根據(jù)“適者生存，優(yōu)勝劣汰”等進(jìn)化規(guī)律來(lái)進(jìn)行搜索計(jì)算和問(wèn)題求解。對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜的問(wèn)題，特別是最優(yōu)化問(wèn)題，遺傳算法提供了一個(gè)行之有效的新途徑。遺傳算法的基本流程如圖所示。遺傳算法的基本思想遺傳算法的基本思想基于達(dá)爾文進(jìn)化論和孟德爾遺傳學(xué)說(shuō)。達(dá)爾文進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來(lái)越適應(yīng)環(huán)境。物種每個(gè)個(gè)體的基本特征由后代所繼承，但后代又會(huì)產(chǎn)生一些異于父代的新變化，在環(huán)境變化時(shí)，只有那些能適應(yīng)環(huán)境的個(gè)體特征能保留下來(lái)。孟德爾遺傳學(xué)說(shuō)最重要的是基因遺傳原理。它認(rèn)為遺傳信息以密碼方式存在于細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性?；蛲蛔兒突螂s交可產(chǎn)生更適應(yīng)于環(huán)境的后代，經(jīng)優(yōu)勝劣汰的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來(lái)。遺傳算法遺傳算法的特點(diǎn)（1）遺傳算法的編碼操作使得它可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。所謂結(jié)構(gòu)對(duì)象泛指集合、序列、矩陣、樹、圖、鏈和表等各種一維、二維甚至三維結(jié)構(gòu)形式的對(duì)象。因此，遺傳算法具有非常廣泛的應(yīng)用領(lǐng)域。（2）遺傳算法是一個(gè)利用隨機(jī)技術(shù)來(lái)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效率搜索的方法，而不是無(wú)方向的隨機(jī)搜索。這與其他隨機(jī)搜索是不同的。（3）許多傳統(tǒng)搜索方法都是單解搜索算法，即通過(guò)一些變動(dòng)規(guī)則，將問(wèn)題的解從搜索空間中的當(dāng)前解移到另一解。對(duì)于多峰分布的搜索空間，這種點(diǎn)對(duì)點(diǎn)的搜索方法常常會(huì)陷于局部的某個(gè)單峰的優(yōu)解。而遺傳算法采用群體搜索策略，即采用同時(shí)處理群體中多個(gè)個(gè)體的方法，同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，從而使遺傳算法具有較好的全局搜索性能，減少了陷于局部?jī)?yōu)解的風(fēng)險(xiǎn)，但還是不能保證每次都得到全局最優(yōu)解。遺傳算法本身也十分易于并行化。（4）在基本遺傳算法中，基本上不用搜索空間的知識(shí)或其他輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作，使種群中個(gè)體之間進(jìn)行信息交換。特別是遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域也可以任意設(shè)定。對(duì)適應(yīng)度函數(shù)的唯一要求是能夠算出可以比較的正值。遺傳算法的這一特點(diǎn)使它的應(yīng)用范圍大大擴(kuò)展，非常適合解決傳統(tǒng)優(yōu)化方法難以解決的復(fù)雜優(yōu)化問(wèn)題。遺傳算法群體智能算法自然界中有許多現(xiàn)象令人驚奇，如螞蟻搬家、鳥群覓食、蜜蜂筑巢等，這些現(xiàn)象不僅吸引生物學(xué)家去研究，也讓計(jì)算機(jī)學(xué)家癡迷。鳥群的排列看起來(lái)似乎是隨機(jī)的，其實(shí)它們有著驚人的同步性，這種同步性使得鳥群的整體運(yùn)動(dòng)非常流暢。有幾位科學(xué)家對(duì)鳥群的運(yùn)動(dòng)進(jìn)行了計(jì)算機(jī)仿真，他們讓每個(gè)個(gè)體按照特定的規(guī)則運(yùn)動(dòng)，形成鳥群整體的復(fù)雜行為。模型成功的關(guān)鍵在于對(duì)個(gè)體間距離的操作，也就是說(shuō)群體行為的同步性是因?yàn)閭€(gè)體努力維持自身與鄰居之間的距離為最優(yōu)，為此每個(gè)個(gè)體必須知道自身位置和鄰居的信息。生物社會(huì)學(xué)家E.O.威爾遜（E.O.Wilson）也曾說(shuō)過(guò)：“至少?gòu)睦碚撋?，在搜索食物的過(guò)程中群體中的個(gè)體成員可以得益于所有其他成員的發(fā)現(xiàn)和先前的經(jīng)歷。當(dāng)食物源不可預(yù)測(cè)地零星分布時(shí)，這種協(xié)作帶來(lái)的優(yōu)勢(shì)是決定性的，遠(yuǎn)大于對(duì)食物的競(jìng)爭(zhēng)帶來(lái)的劣勢(shì)。”這些由簡(jiǎn)單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為，稱為“群體智能”。在計(jì)算智能領(lǐng)域，群體智能算法包括粒子群優(yōu)化算法、蟻群算法等。粒子群優(yōu)化算法粒子群算法也稱為粒子群優(yōu)化（particleswarmoptimization，PSO）算法，是近幾年發(fā)展起來(lái)的一種新的進(jìn)化算法，是由美國(guó)普渡大學(xué)的埃伯哈特（Eberhart）博士和肯尼迪（Kennedy）博士發(fā)明的一種新的全局優(yōu)化進(jìn)化算法，源于對(duì)鳥群捕食的行為研究。PSO同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)迭代搜尋最優(yōu)值。同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單和容易實(shí)現(xiàn)，并且沒有許多參數(shù)需要調(diào)整。粒子群優(yōu)化算法（7）經(jīng)濟(jì)領(lǐng)域。利用PSO求解博弈論中的均衡解，利用PSO和神經(jīng)元網(wǎng)絡(luò)解決最大利益的股票交易決策問(wèn)題。（8）圖像處理領(lǐng)域。離散PSO方法解決多邊形近似問(wèn)題，提高多邊形近似結(jié)果；利用PSO對(duì)用于放射治療的模糊認(rèn)知圖的模型參數(shù)進(jìn)行優(yōu)化；利用基于PSO的微波圖像法來(lái)確定電磁散射體的絕緣特性；利用結(jié)合局部搜索的混合PSO算法對(duì)生物醫(yī)學(xué)圖像進(jìn)行配準(zhǔn)。（9）生物信息領(lǐng)域。利用PSO訓(xùn)練隱馬爾可夫模型來(lái)處理蛋白質(zhì)序列比對(duì)問(wèn)題，克服利用Baum-Welch算法訓(xùn)練隱馬爾可夫模型時(shí)容易陷入局部極小的缺點(diǎn)；利用基于自組織映射和PSO的混合聚類方法來(lái)解決基因聚類問(wèn)題。（10）醫(yī)學(xué)領(lǐng)域。離散PSO選擇MLR（multiplelinearregression，多元線性回歸）和模型PLSR（partialleastsquaresregression，偏最小二乘回歸）的參數(shù)，并預(yù)測(cè)血管緊縮素的對(duì)抗性。（11）運(yùn)籌學(xué)領(lǐng)域?；诳勺冾I(lǐng)域搜索的VNS（variableneighborhoodsearch，可變鄰域搜索）的PSO，解決滿足最小耗時(shí)指標(biāo)的置換問(wèn)題。粒子群優(yōu)化算法（1）神經(jīng)網(wǎng)絡(luò)訓(xùn)練。利用PSO來(lái)訓(xùn)練神經(jīng)元網(wǎng)絡(luò)，將遺傳算法與PSO結(jié)合來(lái)設(shè)計(jì)遞歸/模糊神經(jīng)元網(wǎng)絡(luò)等。利用PSO設(shè)計(jì)神經(jīng)元網(wǎng)絡(luò)是快速、高效并具有潛力的方法。（2）化工系統(tǒng)領(lǐng)域。利用PSO求解苯乙烯聚合反應(yīng)的最優(yōu)穩(wěn)態(tài)操作條件，獲得了最大的轉(zhuǎn)化率和最小的聚合體分散性；使用PSO來(lái)估計(jì)在化工動(dòng)態(tài)模型中產(chǎn)生不同動(dòng)態(tài)現(xiàn)象（如周期振蕩、雙周期振蕩、混沌等）的參數(shù)區(qū)域，仿真結(jié)果顯示提高了傳統(tǒng)動(dòng)態(tài)分叉分析的速度；利用遺傳編程和PSO辨識(shí)最優(yōu)生產(chǎn)過(guò)程模型及其參數(shù)。（3）電力系統(tǒng)領(lǐng)域。將PSO用于最低成本發(fā)電擴(kuò)張GEP（geneexpressionprogramming，基因表達(dá)式編程）問(wèn)題，結(jié)合罰函數(shù)法解決帶有強(qiáng)約束的組合優(yōu)化問(wèn)題；利用PSO優(yōu)化電力系統(tǒng)穩(wěn)壓器參數(shù)；利用PSO解決考慮電壓安全的無(wú)功功率和電壓控制問(wèn)題；利用PSO算法解決滿足發(fā)電機(jī)約束的電力系統(tǒng)經(jīng)濟(jì)調(diào)度問(wèn)題；利用PSO解決滿足開、停機(jī)熱備份約束的機(jī)組調(diào)度問(wèn)題。（4