ga遺傳演算法精度

⑴ 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(1)ga遺傳演算法精度擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。

⑵ 遺傳演算法^[1，]

遺傳演算法，又稱基因演算法(Genetic Algorithm，簡稱GA)，也是一種啟發式蒙特卡洛優化演算法。遺傳演算法最早是由Holland(1975)提出，它模擬了生物適者生存、優勝劣汰的進化過程，具有不依賴於初始模型的選擇、不容易陷入局部極小、在反演過程中不用計算偏導數矩陣等優點。遺傳演算法最早由Stoffa和Sen(1991)用於地震波的一維反演，之後在地球物理資料的非線性反演中得到廣泛的應用。GA演算法對模型群體進行追蹤、搜索，即模型狀態通過模型群體傳送，具有比模擬退火法更大、更復雜的「記憶」，潛力更大。

遺傳演算法在反演中的基本思路和過程是:

(1)將生物體看成模型，模型參數看成染色體，有多少個模型的參數就有多少個染色體。對每個模型的參數(染色體)用二進制進行編碼，這個編碼就是基因。

(2)隨機生成一個模型群體(相當於生物的種群)，然後在模型群體中進行繁殖，通過母本的選擇、交換和變異等遺傳操作產生下一代，然後保留較好基因，淘汰較差基因。

(3)通過一代一代的繁殖優勝劣汰的進化過程，最後所剩下的種群基本上都是最優的基因，種群趨於一致。所謂群體「一致」，即群體目標函數的方差或標准差很小，或者群體目標函數的均值接近於極值(可能是極大值或極小值)，從而獲得非線性反演問題所對應的最優解或近似最優解。

下面以一個實例來簡述遺傳演算法的基本過程。

[例1]設m是正整數，且0≤m≤127，求方程φ(m)=m²的極大值。

這個例子極為簡單，只有一個模型參數，因此只有一條染色體，目標函數的極值是極大值(此例子來自阮百堯課件)。遺傳演算法通過以下7個步驟來實現:

(1)模型參數二進制編碼。

每個模型參數就是一條染色體，把十進制的模型參數表示為二進制，這就是基因。首先確定二進制碼的長度(基因的長度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N為第i條染色體基因的長度(也就是第i個模型參數的二進制碼位數);[m_min(i)，m_max(i)]為第i個模型參數的取值范圍;Δm(i)為第i個模型參數的解析度。這樣就把模型參數離散化了，它只能按Δm(i)的整數倍變化。基因的長度按下式計算:

地球物理反演教程

其中:c為實數;N為基因長度，是整數;int[ ]為取整函數。上式表示如果c不是整數，那麼基因長度N就是對c取整後加1，這樣保證最小解析度。

基因的編碼按下式進行:

地球物理反演教程

其中:式(8.22)是編碼公式;k為基因編碼的十進制數，是整數;int[ ]為取整函數。把k轉化為二進制就是基因的編碼。解碼是按照式(8.23)進行的。首先把一個基因的二進制編碼轉化為十進制數k，然後按式(8.23)可以計算出第i個模型參數m(i)的十進制值。

例如:電阻率參數ρ(1)，它的變化范圍為10~5000Ω·m，解析度為2Ω·m，設當前參數ρ(1)=133Ω·m，按式(8.21)計算得

c=11.28482，N=12

所以二進制基因長度為13位。

利用式(8.22)計算基因編碼k的十進制數:

k=int[(133-10)/2]=61

把它轉化為二進制數為:000000111101。所以ρ(1)=133 的二進制基因編碼為:000000111101。

解碼過程就是把二進制基因編碼變為十進制數k後用式(8.23)計算:

ρ(1)=10+61×2=132(Ω·m)

注意:基因編碼並不是直接把電阻率值變為二進制。此外，133這個值在基因里不會出現，因為解析度是2，所以表示為最接近的132。

對於[例1]問題來說，選解析度為1，0~127用二進制編碼需7位。

(2)產生初始模型種群。

生物繁殖進化需要一定數量的生物體種群，因此遺傳演算法開始時需要一定數量的初始模型。為保證基因的多樣性，隨機產生大量的初始模型作為初始種群，按照上面的編碼方式進行編碼。個體在模型空間中應分布均勻，最好是模型空間各代表區域均有成員。初始模型群體大，有利於搜索，但太大會增加計算量。

為保證演算法收斂，在初始模型群體中，有時候應增加各位都為0和都為1的成員。遺傳演算法就是在這個初始模型種群的基礎上進行繁殖，進化求解的。

對於[例1]問題來說，模型空間是0~127個數字，這樣初始種群最多具有128個個體。為了簡單，隨機選擇4個個體作為初始種群。初始種群的編碼、目標函數值見表8.1。

表8.1 初始種群編碼表

(3)模型選擇。

為了生成新一代模型，需要選擇較優的個體進行配對。生物進化按照自然選擇、優勝劣汰的准則進行。對應地，遺傳演算法按照一定的准則來選擇母本(兩個)，然後進行配對繁殖下一代模型，這個選擇稱為模型選擇。模型配對最基本的方法是隨機采樣，用各模型的目標函數值對所有模型目標函數的平均值的比值定義繁殖概率，即

地球物理反演教程

其中:p(m_i)為繁殖概率;φ(m_i)為第i個模型的目標函數;φ_AVG為目標函數的平均值。對於極小化問題來說，規定目標函數值高於平均值的不傳代;對於極大化問題來說，反之即可。

就[例1]來說，要求目標函數取極大值，所以規定目標函數小於平均值的模型不傳代，大於它的可以傳代。對第一代，為了防止基因丟失，可先不捨去繁殖概率小的模型，讓它與概率大的模型配對。如:本例中70與56配對，101與15配對產生子代，見表8.2。

表8.2 基因交換表

(4)基因交換。

將配對的兩個親本模型的部分染色體相互交換，其中交換點可隨機選擇，形成兩個新的子代(見表8.2)。兩個染色體遺傳基因的交換過程是遺傳演算法的「繁殖」過程，是母本的重組過程。

為了使染色體的基因交換比較徹底，Stoffa等人提出了一個交換概率p_x來控制選擇操作的效果。如果p_x的值較小，那麼交換點的位置就比較靠低位，這時的交換操作基本是低位交換，交換前後模型的染色體變化不是太大。如果p_x的值較大，那麼交換點的位置就比較靠高位，此時的交換操作可以在較大的染色體空間進行，交換前後模型數值變化可以很大。

在[例1]中:15、101和56、70作為母本通過交換繁殖出子代5、6、111、120。所選擇的基因交換位置見表8.2。有下劃線的，是要交換的基因位置。

(5)更新。

母本模型和子本模型如何選擇保留一定數量作為新的母本，就是模型更新。不同的策略會導致不同的結果。一般而言，若產生的新一代模型較好，則選擇新一代模型而淘汰上一代模型。否則，則必須根據一定的更新概率p_u來選擇上一代模型來取代新一代中某些較劣的模型。

經過更新以後，繁殖時對子代再進行優勝劣汰的選擇。對於極大值問題，大於目標函數平均值的子代可以繁殖，小於目標函數平均值的子代不能繁殖。由於新的種群能繁殖的個體數量減小了，所以要多繁殖幾次，維持種群個體的數量保持平衡。

在[例1]中，子代較好，所以完全淘汰上一代模型，完全用子代作為新的母本。選擇子代目標函數最大的兩個模型進行繁殖，分別是111、120。

(6)基因變異。

在新的配對好的母本中，按一定比例隨機選擇模型進行變異，變異操作就是模擬自然界中的環境因素，就是按比較小的變異概率p_m將染色體某位或某幾位的基因發生突變(即將0變為1或將1變為0)。

變異操作的作用是使原來的模型發生某些變化，從而成為新的個體。這樣可使群體增加多樣性。變異操作在遺傳演算法中也起著至關重要的作用。實際上，由於搜索空間的性質和初始模型群體的優劣，遺傳演算法搜索過程中往往會出現所謂的「早熟收斂」現象，即在進化過程中早期陷入局部解而中止進化。採用合適的變異策略可提高群體中個體的多樣性，從而防止這種現象的出現，有助於模型跳出局部極值。表8.3為[例1]的基因變異繁殖表。

表8.3 基因變異繁殖表

在[例1]中，用111、120分別繁殖兩次，形成4個子代，維持種群數量平衡。隨機選擇120進行變異，變異的位數也是隨機的。這里把它的第2位進行變異，即從1變為0，繁殖後形成子代為:70、110、121、127。可以看出新的子代比初始種群要好得多，其中甚至已經出現了最優解。如果對於地球物理的極小值問題，我們可以預先設置一個擬合精度，只要在種群中出現一個達到擬合精度的模型就可以終止反演了。

(7)收斂。

重復(3)~(6)的步驟，模型群體經多次選擇、交換、更新、變異後，種群個體數量大小不變，模型目標函數平均值趨於穩定，最後聚集在模型空間中一個小范圍內，則找到了全局極值對應的解，使目標函數最大或最小的模型就是全局最優模型。

對於具有多解性的地球物理反演問題來說，通過這一步有可能找到滿足擬合精度的多個模型，對於實際反演解釋、推斷具有較高的指導意義。

遺傳演算法中的各種概率包括交換概率px、變異概率p_m以及更新概率p_u，這些參數的選擇與設定目前尚無統一的理論指導，多數都視具體問題而定。Stoffa等(1991)的研究表明，適中的交換概率(p_x≈0.6)、較小的變異概率(p_m≈0.01)和較大的更新概率(p_u≈0.9)，遺傳演算法的性能較優。

與模擬退火反演演算法相同，遺傳演算法與傳統的線性反演方法相比，該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外，遺傳演算法具有並行性，隨著並行計算和集群式計算機技術的發展，該演算法將會得到越來越廣泛的研究與應用。

但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算，種群個體數量越大，繁衍代數越多，則計算量越大。所以和前面的最小二乘法相比，速度不是它的優勢。

⑶ 遺傳演算法的優缺點

優點：

1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。

另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。

2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。

3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。

另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。

4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。

5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。

缺點：

1、遺傳演算法在進行編碼時容易出現不規范不準確的問題。

2、由於單一的遺傳演算法編碼不能全面將優化問題的約束表示出來，因此需要考慮對不可行解採用閾值，進而增加了工作量和求解時間。

3、遺傳演算法效率通常低於其他傳統的優化方法。

4、遺傳演算法容易出現過早收斂的問題。

(3)ga遺傳演算法精度擴展閱讀

遺傳演算法的機理相對復雜，在Matlab中已經由封裝好的工具箱命令，通過調用就能夠十分方便的使用遺傳演算法。

函數ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最優解，fval是最優值，@fitnessness是目標函數，nvars是自變數個數，options是其他屬性設置。系統默認求最小值，所以在求最大值時應在寫函數文檔時加負號。

為了設置options，需要用到下面這個函數：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通過這個函數就能夠實現對部分遺傳演算法的參數的設置。

⑷ 寫一篇大一應用數學論文 謝謝！！！

並行遺傳演算法及其應用

1、遺傳演算法（GA）概述
GA是一類基於自然選擇和遺傳學原理的有效搜索方法，它從一個種群開始，利用選擇、交叉、變異等遺傳運算元對種群進行不斷進化，最後得到全局最優解。生物遺傳物質的主要載體是染色體，在GA中同樣將問題的求解表示成「染色體Chromosome」，通常是二進制字元串表示，其本身不一定是解。首先，隨機產生一定數據的初始染色體，這些隨機產生的染色體組成一個種群（Population），種群中染色體的數目稱為種群的大小或者種群規模。第二：用適值度函數來評價每一個染色體的優劣，即染色體對環境的適應程度，用來作為以後遺傳操作的依據。第三：進行選擇（Selection），選擇過程的目的是為了從當前種群中選出優良的染色體，通過選擇過程，產生一個新的種群。第四：對這個新的種群進行交叉操作，變異操作。交叉、變異操作的目的是挖掘種群中個體的多樣性，避免有可能陷入局部解。經過上述運算產生的染色體稱為後代。最後，對新的種群（即後代）重復進行選擇、交叉和變異操作，經過給定次數的迭代處理以後，把最好的染色體作為優化問題的最優解。
GA通常包含5個基本要素：1、參數編碼：GA是採用問題參數的編碼集進行工作的，而不是採用問題參數本身，通常選擇二進制編碼。2、初始種群設定：GA隨機產生一個由N個染色體組成的初始種群（Population），也可根據一定的限制條件來產生。種群規模是指種群中所含染色體的數目。3、適值度函數的設定：適值度函數是用來區分種群中個體好壞的標准，是進行選擇的唯一依據。目前主要通過目標函數映射成適值度函數。4、遺傳操作設計：遺傳運算元是模擬生物基因遺傳的操作，遺傳操作的任務是對種群的個體按照它們對環境的適應的程度施加一定的運算元，從而實現優勝劣汰的進化過程。遺傳基本運算元包括：選擇運算元，交叉運算元，變異運算元和其他高級遺傳運算元。5、控制參數設定：在GA的應用中，要首先給定一組控制參數：種群規模，雜交率，變異率，進化代數等。
GA的優點是擅長全局搜索，一般來說，對於中小規模的應用問題，能夠在許可的范圍內獲得滿意解，對於大規模或超大規模的多變數求解任務則性能較差。另外，GA本身不要求對優化問題的性質做一些深入的數學分析，從而對那些不太熟悉數學理論和演算法的使用者來說，無疑是方便的。
2、遺傳演算法的運行機理：
對GA運行機理的解釋有兩類: 一是傳統的模式理論；二是1990 年以後發展起來的有限狀態馬爾可夫鏈模型。
（1）模式理論：由Holland創建，主要包括模式定理，隱並行性原理和積木塊假說三部分。模式是可行域中某些特定位取固定值的所有編碼的集合。模式理論認為遺傳演算法實質上是模式的運算，編碼的字母表越短，演算法處理一代種群時隱含處理的模式就越多。當演算法採用二進制編碼時，效率最高，處理規模為N的一代種群時，可同時處理O(N3)個模式。遺傳演算法這種以計算少量編碼適應度而處理大量模式的性質稱為隱並行性。模式理論還指出，目標函數通常滿足積木塊假說，即階數高，長度長，平均適應度高的模式可以由階數低，長度短，平均適應度高的模式(積木塊)在遺傳運算元的作用下，接合而生成。而不滿足積木塊假說的優化問題被稱為騙問題(deceptive problem)。模式理論為遺傳演算法構造了一條通過在種群中不斷積累、拼接積木塊以達到全局最優解的尋優之路。但近十多年的研究，特別是實數編碼遺傳演算法的廣泛應用表明，上述理論與事實不符。
（2）有限狀態馬爾可夫鏈模型：由於模式理論的種種缺陷，研究者開始嘗試利用有限狀態馬爾可夫鏈模型研究遺傳演算法的運行過程。對於遺傳演算法可以解決的優化問題，問題的可行域都是由有限個點組成的，即便是參數可以連續取值的問題，實際上搜索空間也是以要求精度為單位的離散空間，因此遺傳演算法的實際運行過程可以用有限狀態馬爾可夫鏈的狀態轉移過程建模和描述。對於有 m 個可行解的目標函數和種群規模為N的遺傳演算法，N 個個體共有 種組合，相應的馬爾可夫模型也有 個狀態。實際優化問題的可行解數量 m 和種群規模 N 都十分可觀，馬爾可夫模型的狀態數幾乎為天文數字，因此利用精確的馬爾可夫模型計算種群的狀態分布是不可能的。為了換取模型的可執行性，必須對實際模型採取近似簡化，保持演算法的實際形態，通過對目標函數建模，簡化目標函數結構實現模型的可執行性。遺傳演算法優化的過程，可以看作演算法在循環過程中不斷對可行域進行隨機抽樣，利用前面抽樣的結果對目標點的概率分布進行估計，然後根據估計出的分布推算下一次的抽樣點。馬爾可夫模型認為遺傳演算法是通過對搜索空間不同區域的抽樣，來估計不同區域的適應度，進而估計最優解存在於不同區域的概率，以調整演算法對不同區域的抽樣密度和搜索力度，進而不斷提高對最優解估計的准確程度。可見，以鄰域結構為依據劃分等價類的馬爾可夫模型更符合實際，對問題的抽象更能體現優化問題的本質。
3、並行遺傳演算法（PGA）
雖然在許多領域成功地應用遺傳演算法，通常能在合理的時間內找到滿意解，但隨著求解問題的復雜性及難度的增加，提高GA的運行速度便顯得尤為突出，採用並行遺傳演算法（PGA）是提高搜索效率的方法之一。由於GA從種群出發，所以具有天然的並行處理特性，非常適合於在大規模並行計算機上實現，而大規模並行計算機的日益普及，為PGA奠定了物質基礎。特別是GA中各個體適值計算可獨立進行而彼此間無需任何通信，所以並行效率很高。實現PGA，不僅要把串列GA等價地變換成一種並行方案，更重要的是要將GA的結構修改成易於並行化實現的形式，形成並行種群模型。並行種群模型對傳統GA的修改涉及到兩個方面：一是要把串列GA的單一種群分成多個子種群，分而治之；二是要控制、管理子種群之間的信息交換。不同的分治方法產生不同的PGA結構。這種結構上的差異導致了不同的PGA模型：全局並行模型、粗粒度模型、細粒度模型和混合模型。
3、1全局PGA模型
該模型又稱主從PGA模型，它是串列GA的一種直接並行化方案，在計算機上以master-slave編程模式實現。它只有一個種群，所有個體的適應度都根據整個種群的適應度計算，個體之間可以任意匹配，每個個體都有機會和其他個體雜交而競爭，因而在種群上所作的選擇和匹配是全局的。對於這個模型有多種實現方法：第一種方法是僅僅對適值度函數計算進行並行處理；第二種方法是對遺傳運算元進行並行處理。全局模型易於實現，如果計算時間主要用在評價上，這是一種非常有效的並行化方法。
它最大的優點是簡單，保留了串列GA 的搜索行為，因而可直接應用GA 的理論來預測一個具體問題能否映射到並行GA上求解。對於適應度估值操作比其他遺傳運算元計算量大的多時，它是很有效的，並且不需要專門的計算機系統結構。
3、2粗粒度PGA模型
該模型又稱分布式、MIMD、島模式遺傳演算法模型，它是對經典GAs 結構的擴展。它將種群劃分為多個子種群(又稱區域)，每個區域獨自運行一個GA。此時，區域選擇取代了全局選擇，配偶取自同一區域，子代與同一區域中的親本競爭。除了基本的遺傳運算元外，粗粒度模型引入了「遷移」運算元，負責管理區域之間的個體交換。在粗粒度模型的研究中，要解決的重要問題是參數選擇，包括：遷移拓撲、遷移率、遷移周期等。
在種群劃分成子種群(區域)後，要為種群指定某種遷移拓撲。遷移拓撲確定了區域之間個體的遷移路徑，遷移拓撲與特定的並行機結構有著內在的對應關系，大多採用類似於給定並行處理機的互連拓撲。如果在順序計算機上實現粗粒度模型，則可以考慮採用任意結構。拓撲結構是影響PGA 性能的重要方面，也是遷移成本的主要因素。區域之間的個體交換由兩個參數控制：遷移率和遷移周期。遷移基本上可以採用與匹配選擇和生存選擇相同的策略，遷移率常以絕對數或以子種群大小的百分比形式給出，典型的遷移率是子種群數目的10%到20%之間。遷移周期決定了個體遷移的時間間隔，一般是隔幾代(時期) 遷移一次，也可以在一代之後遷移。通常，遷移率越高，則遷移周期就越長。有的採用同步遷移方式，有的採用非同步遷移方式。遷移選擇負責選出遷移個體，通常選擇一個或幾個最優個體，有的採用適應度比例或者排列比例選擇來選擇遷移個體，也有採用隨機選取和替換的。在大多數情況下,是把最差或者有限數目的最差個體替換掉.與遷移選擇類似，可採用適應度比例或者排列比例選擇，確定被替換的個體，以便對區域內部的較好個體產生選擇壓力。
基於國內的現狀，分布式PGA為國內PGA研究的主要方向。分布式PGA作為PGA的一種形式，一般實行粗粒度及全局級並行，各子種群間的相互關系較弱，主要靠一些幾乎串列GA來加速搜索過程。採用分布式PGA求解問題的一般步驟為：（1）將一個大種群劃分為一些小的子種群，子種群的數目與硬體環境有關；（2）對這些子種群獨立的進行串列GA操作，經過一定周期後，從每個種群中選擇一部分個體遷移到另外的子種群。對於個體遷移存在多種方法，第一種方法，在執行遷移操作時，每次從子種群中隨機選擇一部分染色體發送出去，接收的染色體數應該與發出的染色體相同。第二種方法，在執行遷移操作時，首先在每個子種群內只使用選擇而不使用其它遺傳運算元繁殖一些後代，這些後代的數目與遷移數相同。然後再將這些後代的原子種群合並成一個大子種群並均勻隨即地從該子種群中選擇個體進行遷移。這樣，待遷移後子種群的規模便又恢復到正常狀態。而當子種群接收到從其他子種群遷移來的個體時則均勻隨即地替換掉子種群內的個體。第三種方法，將其中一個子種群設置為中心子種群，其他子種群與中心子種群通信。中心子種群始終保持著整個種群中當前的最優個體，其他子種群通過「引進」中心子種群中的最優個體來引導其加快收斂速度，改善個體特徵。
3、3 細粒度PGA模型
該模型又稱領域模型或SIMD PGA模型，對傳統GA作了修改。雖然細粒度模型也只有一個種群在進化，但在種群平面網格細胞上，將種群劃分成了多個非常小的子種群(理想情況是每個處理單元上只有一個個體)，子種群之間具有極強的通信能力，便於優良解傳播到整個種群。全局選擇被領域選擇取代，個體適應度的計算由局部領域中的個體決定，重組操作中的配偶出自同一領域，且子代同其同一領域的親本競爭空間，即選擇和重組只在網格中相鄰個體之間進行。細粒度模型要解決的主要問題是領域結構和選擇策略。
領域結構既決定了種群中個體的空間位置，也確定了個體在種群中傳播的路徑。領域結構主要受特定並行計算機的內存結構和通信結構影響。領域拓撲確定一個個體的鄰居，構成該個體的局部領域。通常，只有一個拓撲的直接領域才屬於其局部領域，若把某個固定步數內所能到達的所有個體也包含在內，則可以擴大領域半徑。在確定選擇策略時，要考慮到選擇壓力的變化，而選擇壓力與領域結構有關。與全局匹配選擇類似，局部匹配選擇可以採用局部適應度比例、排列比例選擇，以及隨機行走選擇。局部生存選擇確定局部鄰域中被替換的個體，如果子代自動替換鄰域中心的那個個體，那麼可以直接使用代替換作為局部生存策略。
3、4 混合PGA模型
該模型又稱為多層並行PGA模型，它結合不同PGA模型的特性，不僅染色體競爭求取最優解，而且在GA結構上也引入了競爭以提供更好的環境便於進化。通常，混合PGA以層次結構組合，上層多採用粗粒度模型，下層既可採用粗粒度模型也可採用細粒度模型。或者，種群可以按照粗粒度PGA模型分裂，遷移操作可以採用細粒度PGA模型。
3、5 四種模型的比較
就現有的研究結果來看，很難分出各模型的高低。在評價並行模型的差異時，有時還得深入到實現細節上，如問題的差異、種群大小、或者不同的局部搜索方法等。但有一個結論是肯定的：不採用全局並行模型，而採用粗粒度模型或者細粒度模型通常能獲得更好的性能。粗粒度模型與細粒度模型孰優孰劣，尚是一個未知數。
目前，以粗粒度模型最為流行，因為一是其實現較容易，只需在串列GA中增加遷移子常式，在並行計算機的節點上各自運行一個副本，並定期交換幾個個體即可；二是在沒有並行計算機時，也可在網路或單機系統上模擬實現。雖然並行GA能有效地求解許多困難的問題，也能在不同類型的並行計算機上有效地實現，但仍有一些基本的問題需要解決。種群大小可能既影響大多數GA的性能，也決定GA找到解所需時間的主要因素。在PGA中，另一個重要問題是如何降低通信開銷，包括遷移率的確定，使得區域的行為象單個種群一樣；確定通信拓撲，既能充分地組合優良解，又不導致過多的通信開銷；能否找到一個最優的區域數等。
另外，對不同的應用問題，混合模型難以設定基本GA的參數，其節點的結構是動態變化的，它比粗粒度和細粒度模型更具有一般性，演算法更為復雜，實現代價更高。
4、並行遺傳演算法的評價模型：
並行遺傳演算法的性能主要體現在收斂速度和精度兩個方面，它們除了與遷移策略有關，還與一些參數選取的合理性密切相關，如遺傳代數、種群數目、種群規模、遷移率和遷移間隔。
利用Amdahl定律評價並行遺傳演算法，即絕對加速比(speep) = Ts/Tp，其中，Ts為串列遺傳演算法(單個處理器)的執行時間；Tp為並行遺傳演算法的執行時間。Amdahl定律適用於負載固定的情況，對於並行遺傳演算法而言，就是適用於總種群規模不變的情況。所以，Amdahl定律適用於主從式和細粒度模型，在適應度評價計算量較大時，主從式模型可以得到接近線性的加速比。由於細粒度模型的應用較少，適用的SIMD並行機的可擴展性也不突出，所以很少有人評價細粒度模型的加速比。利用Amdahl定律評價粗粒度模型時，需保持總的種群規模，即子種群數量和子種群規模成反比。這種情況下粗粒度模型的加速比接近線性，這是由於粗粒度模型的通信開銷和同步開銷都不大。
5、實例：帶約束並行多機調度
5、1 問題描述
最小化完工時間的帶約束並行多機調度問題可描述如下：有 n 個相關的工件，m 台機器，每個工件都有確定的加工時間，且均可由 m 台機器中的任一台完成加工任務。要找一個最小調度，即確定每台機器上加工的工件號順序，使加工完所有工件所需時間最短。
演算法關鍵在於：
(1) 如何表示工件之間的關系。可以把 n 個相關工件表示成一個後繼圖，如上圖所示。圖中節點間的有向邊表示工件之間的後繼或編序關系。因此，Ti →Tj 表示工件 Tj 在完成之後才能啟動工件Ti。顯然對於 n 個相關工件，我們可以根據工件間的約束關系所表示成的後繼圖產生一符合約束條件的工件序列( a0，a1，…，ai，…，an-1) (0 ≤ai <n) ,其中ai 表示一個工件。例如，根據上圖所示的後繼圖, 可產生工件序列(0，2，5，1，3，4，7，6，8)，按該工件序列調度滿足工件之間的約束關系。
(2) 如何表示問題的目標函數。設t(j)為機器加工工件 j 所需時間，tb(i ,j) 為機器 i 加工工件 j 的最早時刻。為了使GA演算法解決問題方便，我們用x(i ,j) 表示工件 j 在機器 i 上是否加工，若x(i ,j) = 1，則表示工件 j 在機器 i 上加工；若x(i ,j) = 0，則表示工件 j 不在機器 i 上加工。因而x(i ,j ) t (j) 為機器 i 加工工件 j 的實際加工時間。
問題的目標函數可表示為:
minGms = min{max[ finish(0), finish(1), ...,finish(i), ..., finish (m - 1) ]}。其中finish(i)表示第 i 台處理機加工分配的工件所需時間。finish(i) = max{ x(0 , a0) [ tb(i, a0) + t(a0) ] ,x(1, a1) [ tb(i, a1) + t(a1) ], ..., x(n-1, an-1) [ tb(i, an-1) + t(an-1) ]}。
5、2 並行GA實現
帶約束並行多機調度問題的並行GA實現如下：
(1) 產生一個進程（該進程為父進程，在進行串列GA的同時，用於存放和發送當前最優個體）；
(2) 由父進程產生m - 1 個子進程（每個子進程用於實現串列GA）；
(3) 各子進程（包括父進程）進行串列GA，當子進程中遺傳代數(ge)被10整除，子進程發送最優個體至父進程；
(4) 父進程選擇當前各子進程中最優個體(molist)，發送給各子進程；
(5) 各子進程把molist替換各子進程當前代種群中適應值最低個體；
(6) 若ge = gmax (gmax為設定最大繁殖代數)，轉第(7)步，否則轉第(3)步；
(7) 演算法終止。
6、總結：
組合優化是遺傳演算法最基本的也是最重要的研究和應用領域之一。一般來說，組合優化問題通常帶有大量的局部極值點，往往是不可微的、不連續的、多維的、有約束條件的、高度非線性的NP完全問題，因此，精確的求解組合優化問題的全局最優解一般是不可能的。遺傳演算法是一種新型的、模擬生物進化過程的隨機化搜索、優化方法，近十幾年來在組合優化領域得到了相當廣泛的研究和應用，並已在解決諸多典型組合優化問題中顯示了良好的性能和效果。

參考文獻：
1、Zdeněk Konfrst. Parallel Genetic Algorithms: Advances, Computing Trends, Aplications and Perspectives. Proceedings of the 18th International Parallel and Distributed Proecessing Symposium, 2004.
2、郭彤城, 慕春棣. 並行遺傳演算法的新進展. 系統工程理論與實踐, 2002.
3、曾國蓀, 丁春玲. 並行遺傳演算法分析. 計算機工程, 2001.
4、王大明, 毛宗源. 並行遺傳演算法綜述. 暨南大學學報(自然科學版), 1998.
5、吳昊. 並行遺傳演算法的研究與應用. 安徽大學碩士學位論文, 2001.
6、王冠. 並行遺傳演算法及其在組合優化問題上的分布式應用, 武漢理工大學碩士學位論文, 2003.
7、吳昊, 程錦松. 用並行遺傳演算法解決帶約束並行多機調度問題. 微機發展, 2001.

⑸ 遺傳演算法代溝與精度問題

我也不懂哎，不好意思哈

⑹ 求遺傳演算法（GA）處理離散的整數型變數的程序。

兩種編碼都有，可以自己選擇。 你在MATLAB2008里輸入 gaoptimset 會彈出遺傳演算法的所有的設置選項及默認項。其中，第一行就是個體的編碼方式，第一行如下 PopulationType: [ 'bitstring' | 'custom' | ] 其中，bitstring就是二進制編碼，而'doubleVector'即實數編碼(MATLAB里實數是用double雙精度浮點數表示的，精度很高。大括弧{}表示是默認設置。 而中間的'custom'是表示用戶自己構造個體的編碼形式。

⑺ 基本遺傳演算法介紹

遺傳演算法是群智能優化計算中應用最為廣泛、最為成功、最具代表性的智能優化方法。它是以達爾文的生物進化論和孟德爾的遺傳變異理論為基礎，模擬生物進化過程和機制，產生的一種群體導向隨機搜索技術和方法。

遺傳演算法的基本思想：首先根據待求解優化問題的目標函數構造一個適應度函數。然後，按照一定的規則生成經過基因編碼的初始群體，對群體進行評價、遺傳運算（交叉和變異）、選擇等操作。經過多次進化，獲得適應度最高的一個或幾個最優個體作為問題的最優解。

編碼是對問題的可行解的遺傳表示，是影響演算法執行效率的關鍵因素的之一。遺傳演算法中，一個解 稱為個體或染色體（chromosome），染色體由被稱為基因（gene）的離散單元組成，每個基因控制顏色體的一個或多個特性，通常採用固定長度的0-1二進制編碼，每個解對應一個唯一的二進制編碼串編碼空間中的二進制位串稱為基因型（genotype）。而實際所表示問題的解空間的對應點稱為表現型（phenotype）。

種群由個體構成，每個個體的染色體對應優化問題的一個初始解。

適應度函數是評價種群中個體對環境適應能力的唯一確定性指標，體現出「適者生存，優勝劣汰」這一自然選擇原則。

遺傳演算法在每次迭代過程中，在父代種群中採用某種選擇策略選擇出指定數目的哥特體提進行遺傳操作。最常用的選擇策略是正比選擇（proportional selection）策略。

在 交叉運算元中，通常由兩個被稱為父代（parent）的染色體組合，形成新的染色體，稱為子代（offspring）。父代是在種群中根據個體適應度進行選擇，因此適應度較高的染色體的基因更有可能被遺傳到下一代 。通過在迭代過程中不斷地應用交叉運算元，使優良個體的基因得以在種群中頻繁出現，最終使得整個種群收斂到一個最優解。

在染色體交叉之後產生的子代個體，其基因位可能以很小的概率發生轉變，這個過程稱為變異。變異是為了增強種群的多樣性，將搜索跳出局部最優解。

遺傳演算法的停止准則一般採用設定最大迭代次數或適應值函數評估次數，也可以是規定的搜索精度。

已Holland的基本GA為例介紹演算法等具體實現，具體的執行過程描述如下：

Step 1： 初始化 。隨機生成含有 個個體的初始種群 ，每個個體經過編碼對應著待求解優化問題的一個初始解。

Step 2： 計算適應值 。個體 ，由指定的適應度函數評價其適應環境的能力。不同的問題，適應度函數的構造方式也不同。對函數優化問題，通常取目標函數作為適應度函數。

Step 3： 選擇 。根據某種策略從當前種群中選擇出 個個體作為重新繁殖的下一代群體。選擇的依據通常是個體的適應度的高低，適應度高的個體相比適應度低的個體為下一代貢獻一個或多個後代的概率更大。選擇過程提現了達爾文「適者生存」原則。

Step 4： 遺傳操作 。在選出的 個個體中，以事件給定的雜交概率 任意選擇出兩個個體進行 交叉運算 ，產生兩個新的個體，重復此過程直到所有要求雜交的個體雜交完畢。根據預先設定的變異概率 在 個個體中選擇出若干個體，按一定的策略對選出的個體進行 變異運算 。

Step 5： 檢驗演算法等停止條件 。若滿足，則停止演算法的執行，將最優個體的染色體進行解碼得到所需要的最優解，否則轉到 Step 2 繼續進行迭代過程。

⑻ 遺傳演算法

優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(GA)，差分演化演算法(DE)，粒子群演算法(PSO)和人工蜂群演算法(ABC)。

舉一個例子，遺傳演算法和梯度下降：

梯度下降和遺傳演算法都是優化演算法，而梯度下降只是其中最基礎的那一個，它依靠梯度與方向導數的關系計算出最優值。遺傳演算法則是優化演算法中的啟發式演算法中的一種，啟發式演算法的意思就是先需要提供至少一個初始可行解，然後在預定義的搜索空間高效搜索用以迭代地改進解，最後得到一個次優解或者滿意解。遺傳演算法則是基於群體的啟發式演算法。

遺傳演算法和梯度下降的區別是：

1.梯度下降使用誤差函數決定梯度下降的方向，遺傳演算法使用目標函數評估個體的適應度
2.梯度下降是有每一步都是基於學習率下降的並且大部分情況下都是朝著優化方向迭代更新，容易達到局部最優解出不來；而遺傳演算法是使用選擇、交叉和變異因子迭代更新的，可以有效跳出局部最優解
3.遺傳演算法的值可以用二進制編碼表示，也可以直接實數表示

遺傳演算法如何使用它的內在構造來算出 α 和 β ：

主要講一下選擇、交叉和變異這一部分：
1.選擇運算:將選擇運算元作用於群體。選擇的目的是把優秀（適應值高）的個體直接遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

2.交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。交叉運算元是將種群中的個體兩兩分組，按一定概率和方式交換部分基因的操作。將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。例如：（根據概率選取50個個體，兩兩配對，交換x,y，比如之前兩個是(x1,y1),(x2,y2)，之後變成了（x1,y2）,(x2,y1)）

3.變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。（x2可能變為x2+δ，y1變為y1+δ）
種群P(t)經過選擇、交叉、變異運算之後得到下一代種群P(t+1)。

遺傳演算法就是通過對大量的數據個體使用選擇、交叉和變異方式來進化，尋找適合問題的最優解或者滿意解。

遺傳演算法參數的用處和設置：

1.編碼選擇：通常使用二進制編碼和浮點數編碼，二進制適合精度要求不高、特徵較少的情況。浮點數適合精度高、特徵多的情況
2.種群：種群由個體組成，個體中的每個數字都代表一個特徵，種群個體數量通常設置在40-60之間；迭代次數通常看情況定若計算時間較長可以在100內，否則1000以內都可以。
3.選擇因子：通常有輪盤賭選擇和錦標賽選擇，輪盤賭博的特點是收斂速度較快，但優勢個體會迅速繁殖，導致種群缺乏多樣性。錦標賽選擇的特點是群多樣性較為豐富，同時保證了被選個體較優。
4.交叉因子：交叉方法有單點交叉和兩點交叉等等，通常用兩點交叉。交叉概率則選擇在0.7-0.9。概率越低收斂越慢時間越長。交叉操作能夠組合出新的個體，在串空間進行有效搜索，同時降低對種群有效模式的破壞概率。
5.變異因子：變異也有變異的方法和概率。方法有均勻變異和高斯變異等等；概率也可以設置成0.1。變異操作可以改善遺傳演算法的局部搜索能力，豐富種群多樣性。
6.終止條件：1、完成了預先給定的進化代數；2、種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進；3、所求問題最優值小於給定的閾值.

⑼ 如何提高matlab的GA工具箱（遺傳演算法）的運算精度

options.TolFun=1e-10