遺傳算法(Genetic Algorithms)簡介

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-06 13:36:33   瀏覽：9532次  

遺傳算法(Genetic Algorithms)簡介

一、遺傳算法的歷史和現(xiàn)狀
遺傳算法（Genetic Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。其主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它是在70年代初期由美國密執(zhí)根（Michigan）大學(xué)的霍蘭（Holland）教授發(fā)展起來的。1975年霍蘭教授發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》（《Adaptation in Natural and Artificial Systems》）。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。
近幾年來，遺傳算法主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注，而且在發(fā)展過程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間差異越來越小。遺傳算法成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計(jì)、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題等等。
    （一）遺傳算法的特點(diǎn)
遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為：（1）首先組成一組候選解；（2）依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度；（3）根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；（4）對保留的候選解進(jìn)行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。
遺傳算法還具有以下幾方面的特點(diǎn)：
（1）遺傳算法的處理對象不是參數(shù)本身，而是對參數(shù)集進(jìn)行了編碼的個體。此操作使得遺傳算法可直接對結(jié)構(gòu)對象進(jìn)行操作。
（2）許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時算法本身易于實(shí)現(xiàn)并行化。
（3）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。
（4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。
（5）具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索，時硬度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。
    （二）遺傳算法的運(yùn)用領(lǐng)域

贊助本站