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