《遺傳算法的特點與步驟分析綜述》3400字

遺傳算法的特點與步驟分析綜述1.1遺傳算法的定義遺傳算法（GeneticAlgorithm,GA）起源于對生物系統(tǒng)所進行的計算機模擬硏究，由Michigan大學的約翰·霍蘭德（J·Holland）教授于1975年首先提出來的，并撰寫了《AdaptationinNaturalandArtificialSystems》一書，其學生在論文“Ananalysisofthebehaviorofthebehaviorofaclassofgeneticadaptativesystems”中通過大量的試驗，嘗試將遺傳算法的思想運用到最優(yōu)化問題當中，創(chuàng)造出的一種基于生物遺傳和進化機制的適合于復雜系統(tǒng)優(yōu)化的自適應概率優(yōu)化的技術REF_Ref72572479\r\h[55]REF_Ref72572484\r\h[56]。根據(jù)自然界適者生存的法則，種群中的個體選擇優(yōu)秀的基因進行遺傳。每個個體的染色體通過選擇、交叉和變異等操作產(chǎn)生新的適應度更大的染色體，其中適應度越大的個體越優(yōu)秀，種群得到優(yōu)化，得到的解越逼近最優(yōu)解，種群重復迭代不斷優(yōu)化最終得到目標問題的最優(yōu)解。1.2遺傳算法的特點遺傳算法在模擬自然界生物進化機制的過程中，將實際問題進行編碼轉換成計算機能夠識別的語言，編碼形成的字符串被稱為染色體，其模仿生物進化的過程，進行選擇、交叉和變異，產(chǎn)生不同于父代且比父代更加優(yōu)秀的染色體，新的染色體比父代更加適應環(huán)境；染色體再進行選擇、交叉和變異等操作，不斷的進行迭代，形成帶有優(yōu)秀基因的子代種群，新的子代種群比上一代更優(yōu)秀。遺傳算通過種群的不斷迭代，在種群中尋找最優(yōu)解。遺傳算法與精確算法相比，遺傳算法能夠計算更加復雜的問題，精確算法適用與于簡單問題的計算。與經(jīng)典啟發(fā)式算法相比，遺傳算法不易陷入局部最優(yōu)、計算速度快和容易操作等特點，遺傳算法具體的特點包括：（1）遺傳算法具有可操作性強、應用領域廣泛，能夠快速解決比較復雜問題的特點。遺傳算法解決復雜問題的方式是通過模仿自然界的進化機制，用對決策變量進行編碼、字符串或者問題的解來對運算對象進行定義。遺傳算法能夠對圖、集合、矩陣、數(shù)列等進行操作，不需要對決策變量本身進行操作，有利于選擇、交叉、變異算子模擬生物染色體遺傳進化的進程，方便遺傳算法解決定性而無具體數(shù)值描述的優(yōu)化問題，例如生產(chǎn)調度、圖像處理、函數(shù)優(yōu)化等。（2）使用遺傳算法進行求解時不易陷入局部最優(yōu)。遺傳算法在求解的過程中從多個染色體構成的種群開始搜索，多個點同時開始搜索，不是從單點開始進行搜索，無論搜索空間為單峰或者多峰分布時，都能夠快速地尋找到最優(yōu)解。其他的啟發(fā)式算法從單點進行搜索，遇到搜索空間不是單峰時，很容易得到局部的最優(yōu)解，然而遺傳算法能夠在搜索空間為多峰時得到最優(yōu)解避免這種情況發(fā)生。即使當使用遺傳算法進行求解的適應度函數(shù)是不規(guī)則、不連續(xù)時，也能尋找到全局的最優(yōu)解。（3）遺傳算法進行計算時無需其他輔助信息。使用遺傳算法進行運算時，搜索最優(yōu)解的依據(jù)是適應度函數(shù)，不是直接對實際問題的目標函數(shù)進行求導，實際問題的目標函數(shù)大多數(shù)是不容易進行求導，或者本身就沒有導數(shù)。用適應度函數(shù)作為搜索最優(yōu)解的依據(jù)，不受函數(shù)連續(xù)可微的影響，可以隨意設定函數(shù)的定義域。使用遺傳算法進行編碼時，需要與適應度函數(shù)可行解的空間相對照，不允許存在死碼的情況。然而其他的啟發(fā)式算法沒有適應度函數(shù)或者其它能夠作為搜索最優(yōu)解的依據(jù)。（4）遺傳算法在進行選擇、交叉和變異的運算過程時，均是通過一定的隨機概率來實現(xiàn)。采用隨機概率的變遷不斷調整遺傳算法的搜索方向，產(chǎn)生更多的優(yōu)良個體，而不是采用確定性規(guī)則，遺傳算法這種概率性規(guī)則，搜索最優(yōu)解時更加靈活，變量對搜索過程的作用很小。1.3遺傳算法的步驟遺傳算法是一種全局搜索算法，使用遺傳算法進行求解時，根據(jù)實際問題的初始解，進行編碼形成染色體，染色體經(jīng)過選擇、交叉、變異后形成新的染色體，新形成的染色體比之前的染色體更接近最優(yōu)解。再經(jīng)過不斷的迭代，一直得到最優(yōu)解，遺傳算法的主要步驟是編碼解碼、確定初始種群、確定適應度函數(shù)、選擇、交叉和變異。（1）編碼解碼使用遺傳算法進行求解時，第一步是將可行解進行編碼組成基因字符串，這些字符串相當于自然界生物的染色體。遺傳算法有很多不同的編碼方式，包括二進制、格雷碼、浮點數(shù)編碼等。其中遺傳算法不能對染色體或者個體的單個基因進行優(yōu)化，能夠對染色體或者個體進行優(yōu)化。編碼的優(yōu)劣影響后續(xù)染色體的選擇、交叉和變異，從而影響最優(yōu)解的獲得，所以在設計編碼策略時需要遵循非冗余性、完備性、健全性等原則。解碼則是將字符串恢復為原始信息的過程。（2）確定初使種群確定初始種群是進行遺傳算法的第一步，是編碼完成的一個個獨立的個體，這些個體構成了遺傳算法的初始解。初始種群大小會影響遺傳算法的計算速度和最優(yōu)解的質量，初始種群的數(shù)量一般在30-200之間，種群太小，遺傳算法在求解過程中容易過早的收斂，陷入局部最優(yōu)；種群太大，用遺傳算法求解的計算量增大，增加求解的時間，降低求解的速度。初始種群的選擇，經(jīng)常用的方法有以下兩種：第一種是根據(jù)實際建立優(yōu)化模型，考慮規(guī)模的大小，選擇適合優(yōu)化模型可行解的規(guī)模，選擇的可行解均勻分布在整個可行解的規(guī)模內，使得可行解不集中在一個地方。第二種是首先選擇一個較小規(guī)模的種群，進行不斷地迭代，優(yōu)秀個體會逐漸進入到初始種群，使得初始種群越來越接近最優(yōu)解，種群的規(guī)模會不斷的增大。雖然種群的優(yōu)良性會隨著迭代次數(shù)的增加逐漸升高，但是種群規(guī)模的上限不容易控制。（3）確定適應度函數(shù)適應度函數(shù)用來判斷染色體的優(yōu)劣，適應度函數(shù)與目標函數(shù)有關，當目標函數(shù)為正數(shù)時，目標函數(shù)可以作為適應度函數(shù)；當目標函數(shù)為負數(shù)時，因為適應度函數(shù)不能為負數(shù)，所以需要先將目標函數(shù)轉化成正數(shù)，再作為適應度函數(shù)，適應度越高種群的優(yōu)良性越好，遺傳給下一代的可能性越大，此時的解越接近最優(yōu)解。（4）選擇選擇又稱復制，是從群體中選擇優(yōu)秀個體并淘汰劣等個體的過程。根據(jù)確定適應度值的大小，選擇種群中優(yōu)秀的個體，適應度大的個體優(yōu)秀。選擇優(yōu)秀的個體進行交叉、變異形成新的種群。隨著種群進行不斷的迭代，更多優(yōu)秀的基因遺傳給下一代得到適應度更大的后代，此時得到的解越接近最優(yōu)解。因此選擇合適的算子進行迭代，可以增加所求解的質量，每一次迭代遺傳給下一代的基因更靠近最優(yōu)解，可以將這種通過種群不斷迭代得到最優(yōu)解的過程稱為試根的過程。選擇的方法經(jīng)常用的有比例選擇法，比例選擇法被稱為蒙特卡羅法或者輪盤賭法，首先根據(jù)適應度函數(shù)計算每個個體的適應度值，其次將每個個體的適應度函數(shù)值與所有個體的總適應度的比值，作為每個個體被選擇的概率，所有個體被選擇的概率之和為1，按照被選擇的概率劃分輪盤，轉動輪盤指針停在的位置即被選擇的個體，這種隨機選擇的方法，可以大概率的指到適應度大個體，進行復制產(chǎn)生適應度更高的個體，提高種群的適應度。（5）交叉交叉又稱重組，是在選擇復制操作之后，染色體有交叉概率，按照交叉概率將染色體進行交叉，互換兩個染色體交叉點的部分基因，產(chǎn)生兩個新的不同于父代的染色體，新的染色體保留了優(yōu)秀的基因。并且經(jīng)過交叉操作之后形成的染色體，適應度會更高，染色體更優(yōu)秀，在進行迭代后得到的子代更接近問題的最優(yōu)解。交叉將父代看成起點，結合父代染色體的特征形成新的染色體的過程，可以看成通過已知最優(yōu)解的規(guī)模，根據(jù)一個解，尋找未知最優(yōu)接的過程。遺傳算法的交叉算子主要有單點交叉算子、雙點交叉算子、多點交叉算子、均勻交叉算子等。單點交叉算子是指在兩個染色體的基因串中分別選擇一個交叉點，在交叉的位置將兩個父代基因串進行截斷重新組合形成新的兩個基因串。單點交叉容易操作、效率高，是使用最多的一種算子。雙點交叉算子是指在兩個染色體的基因串中分別選擇兩個交叉點，截取兩個交叉點之間的基因片段，進行交換重新組合形成新的基因串。雙點交叉算子能夠得到比單點交叉算子更加全新的染色體，使搜索速度加快，但是可能會得到次優(yōu)解。多點交叉算子與雙點交叉算子相似，選擇多個不同的點進行交叉。均勻交叉算子：均勻交叉算子屬于一種多點交叉，在多點交叉的基礎上，設置一些屏蔽位置，規(guī)定能夠進行交叉遺傳給下一代的基因片段。（6）變異遺傳算法在經(jīng)過選擇、交叉操作過程之后進行變異操作。變異是將染色體的部分基因以很小的概率來進行變異，通過將染色體的基因片段用一些等位基因片段進行交換，變異操作能夠提高染色體的多樣性，有效的防止選擇和交叉操作過程中以部分信息的遺失。變異的方式有很多種包括