3遺傳算法的優(yōu)缺點(diǎn)

1、遺傳算法的優(yōu)缺點(diǎn)遺傳算法屬于進(jìn)化算法（Evolutionary Algorithms）的一種，它通過(guò)模仿 自然界的選擇與遺傳的機(jī)理來(lái)尋找最優(yōu)解.遺傳算法有三個(gè)基本算子:選擇、交 叉和變異。數(shù)值方法求解這一問(wèn)題的主要手段是迭代運(yùn)算。一般的迭代方法容易陷入局部極小的陷阱而出現(xiàn)死循環(huán)現(xiàn)象，使迭代無(wú) 法進(jìn)行。遺傳算法很好地克服了這個(gè)缺點(diǎn)，是一種全局優(yōu)化算法。 生物在漫 長(zhǎng)的進(jìn)化過(guò)程中，從低等生物一直發(fā)展到高等生物，可以說(shuō)是一個(gè)絕妙的優(yōu)化 過(guò)程。這是自然環(huán)境選擇的結(jié)果。人們研究生物進(jìn)化現(xiàn)象，總結(jié)出進(jìn)化過(guò)程包 括復(fù)制、雜交、變異、競(jìng)爭(zhēng)和選擇。一些學(xué)者從生物遺傳、進(jìn)化的過(guò)程得到啟發(fā)，提出了遺傳算法（GA）。

2、算 法中稱(chēng)遺傳的生物體為個(gè)體（individual），個(gè)體對(duì)環(huán)境的適應(yīng)程度用適應(yīng)值 （fitness）表示。適應(yīng)值取決于個(gè)體的染色體（chromosome），在算法中染色 體常用一串?dāng)?shù)字表示，數(shù)字串中的一位對(duì)應(yīng)一個(gè)基因（gene）。一定數(shù)量的個(gè) 體組成一個(gè)群體（population）。對(duì)所有個(gè)體進(jìn)行選擇、交叉和變異等操作， 生成新的群體，稱(chēng)為新一代（new generation）o遺傳算法計(jì)算程序的流程可以表示如下3:第一步準(zhǔn)備工作 （1）選擇合適的編碼方案，將變量（特征）轉(zhuǎn)換為染 色體（數(shù)字串，串長(zhǎng)為m）。通常用二進(jìn)制編碼。 （2）選擇合適的參數(shù)，包 括群體大?。▊€(gè)體數(shù)M）、交叉概率PC和變

3、異概率Pm。 （3）確定適應(yīng)值函數(shù) f（x）。f（x）應(yīng)為正值。第二步 形成一個(gè)初始群體（含M個(gè)個(gè)體）。在邊坡滑裂面搜索問(wèn)題中，取 已分析的可能滑裂面組作為初始群體。第三步對(duì)每一染色體（串）計(jì)算其適應(yīng)值fi，同時(shí)計(jì)算群體的總適應(yīng)值。第四步 選擇 計(jì)算每一串的選擇概率Pi=fi/F及累計(jì)概率選擇一般通過(guò)模 擬旋轉(zhuǎn)滾花輪（roulette，其上按Pi大小分成大小不等的扇形區(qū)）的算法進(jìn)行。 旋轉(zhuǎn)M次即可選出M個(gè)串來(lái)。在計(jì)算機(jī)上實(shí)現(xiàn)的步驟是：產(chǎn)生0, 1間隨機(jī)數(shù) r，若rq1，則第一串v1入選，否則選v2，使?jié)M足qi-1rpc，則該串參加交叉操作，如此選出參加交叉的一組后，隨機(jī)配對(duì)。（2）對(duì)每一對(duì)，產(chǎn)

4、生1,m間的隨機(jī)數(shù)以確定交叉的位置。第六步變異 如變異概率為Pm，則可能變異的位數(shù)的期望值為Pm XmXM， 每一位以等概率變異。具體為對(duì)每一串中的每一位產(chǎn)生0，1間的隨機(jī)數(shù)r， 若rPm，則該位發(fā)生反轉(zhuǎn)，如對(duì)染色體二進(jìn)制編碼為數(shù)字0變?yōu)?，1變?yōu)?。 如新個(gè)體數(shù)達(dá)到M個(gè)，則已形成一個(gè)新群體，轉(zhuǎn)向第三步；否則轉(zhuǎn)向第四步繼 續(xù)遺傳操作。直到找到使適應(yīng)值最大的個(gè)體或達(dá)到最大進(jìn)化代數(shù)為止。由于選擇概率是由適應(yīng)值決定的，即適應(yīng)值大的染色體入選概率也較大， 使選擇起到擇優(yōu)汰劣的作用。交叉使染色體交換信息，結(jié)合選擇規(guī)則，使優(yōu) 秀信息得以保存，不良信息被遺棄。變異是基因中得某一位發(fā)生突變，以達(dá)到 產(chǎn)生確實(shí)有

5、實(shí)質(zhì)性差異的新品種。遺傳算法雖是一種隨機(jī)算法，但它是有導(dǎo)向 的，它所使用的按概率隨機(jī)選擇方法是在有方向的搜索方法中的一種工具。 正是這種獨(dú)特的搜索方法，使遺傳算法自然地避開(kāi)了其它最優(yōu)化算法常遇到的 局部最小陷阱。遺傳算法與傳統(tǒng)的優(yōu)化方法（枚舉，啟發(fā)式等）相比較，以生物進(jìn)化為原 型，具有很好的收斂性，在計(jì)算精度要求時(shí)，計(jì)算時(shí)間少，魯棒性高等都是它 的優(yōu)點(diǎn)。遺傳算法的優(yōu)點(diǎn)：與問(wèn)題領(lǐng)域無(wú)關(guān)切快速隨機(jī)的搜索能力。搜索從群體出發(fā)，具有潛在的并行性，可以進(jìn)行多個(gè)個(gè)體的同時(shí)比較， robust.搜索使用評(píng)價(jià)函數(shù)啟發(fā)，過(guò)程簡(jiǎn)單使用概率機(jī)制進(jìn)行迭代，具有隨機(jī)性。具有可擴(kuò)展性，容易與其他算法結(jié)合。遺傳算法的缺點(diǎn)：

6、1、遺傳算法的編程實(shí)現(xiàn)比較復(fù)雜，首先需要對(duì)問(wèn)題進(jìn)行編碼，找到最優(yōu)解之 后還需要對(duì)問(wèn)題進(jìn)行解碼，2、另外三個(gè)算子的實(shí)現(xiàn)也有許多參數(shù)，如交叉率和變異率，并且這些參數(shù)的 選擇嚴(yán)重影響解的品質(zhì)，而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn).3、沒(méi)有能夠及時(shí)利用網(wǎng)絡(luò)的反饋信息，故算法的搜索速度比較慢，要得要 較精確的解需要較多的訓(xùn)練時(shí)間。4、算法對(duì)初始種群的選擇有一定的依賴(lài)性，能夠結(jié)合一些啟發(fā)算法進(jìn)行改 進(jìn)。5、算法的并行機(jī)制的潛在能力沒(méi)有得到充分的利用，這也是當(dāng)前遺傳算法 的一個(gè)研究熱點(diǎn)方向。在現(xiàn)在的工作中，遺傳算法（1972年提出）已經(jīng)不能很好的解決大規(guī)模計(jì) 算量問(wèn)題，它很容易陷入“早熟”。常用混合遺傳算法，合作型協(xié)同進(jìn)化算法 等來(lái)替代，這些算法都是GA的衍生算法。遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索 出，而不會(huì)陷入局部最優(yōu)解的快速下降陷阱；并且利用它的內(nèi)在并行性，可以 方便地進(jìn)行分布式計(jì)算，加快求解速度。但是遺傳算法的局部搜索能力較差， 導(dǎo)致單純的遺傳算法比較費(fèi)時(shí)，在進(jìn)化后期搜索效率較低。在實(shí)際應(yīng)用中，遺 傳算法容易產(chǎn)生早熟收斂的問(wèn)題。采用何種選擇方法既要使優(yōu)良個(gè)體得以保留， 又要維持群體的多樣性，一直是遺傳算法中較難解決的問(wèn)題。模擬退火算法雖具有擺脫局部最優(yōu)解的能力，能夠以隨機(jī)搜索技術(shù)從概 率的意義上