進化演算法的選擇交叉編譯

㈠ 進化演算法的簡介

進化演算法包括遺傳演算法、遺傳規劃、進化規劃和進化策略等等。進化演算法的基本框架還是簡單遺傳演算法所描述的框架，但在進化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化，進化演算法的大致框圖可描述如右圖所示：
同遺傳演算法一樣，進化演算法的收斂性也有一些結果，文獻證明了在保存最優個體時通用的進化計算是收斂的，但進化演算法的很多結果是從遺傳演算法推過去的。
遺傳演算法對交叉操作要看重一些，認為變異操作是演算法的輔助操作；而進化規劃和進化策略認為在一般意義上說交叉並不優於變異，甚至可以不要交叉操作。

㈡ 多目標優化演算法

多目標優化演算法如下：

一、多目標進化演算法（MOEA）

1、MOEA通過對種群X（t）執行選擇、交叉和變異等操作產生下一代種群X（t+1）。

2、在每一代進化過程中 ,首先將種群X（t）中的所有非劣解個體都復制到外部集A（t）中。

2、智能優化演算法：包括進化演算法（簡稱EA）、粒子群演算法（簡稱PSO）等。

兩者的區別：傳統優化技術一般每次能得到Pareo解集中的一個，而用智能演算法來求解，可以得到更多的Pareto解，這些解構成了一個最優解集，稱為Pareto最優解（任一個目標函數值的提高都必須以犧牲其他目標函數值為代價的解集）。

㈢ 遺傳演算法的優缺點

優點：

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

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

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

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

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

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

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

缺點：

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

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

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

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

(3)進化演算法的選擇交叉編譯擴展閱讀

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

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

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

㈣ 網路架構搜索

        作為計算智能方法的代表，起源於上個世紀四十年代的人工神經網路經歷了五六十年代的繁榮，七十年代的低潮，八十年代的再次復甦，到近十年的廣泛關注，如今已經成為理論日趨完善，應用逐步發展的前沿方向。Hinton 等人2006 年在《Science》上發表的文章引發了深度神經網路研究的熱潮。面對大數據的諸多挑戰，以深度信念網路、卷積神經網路和遞歸神經網路為代表的深度神經網路模型在很多應用領域展示出明顯的優勢和潛力，特別是隨著數據量和數據維數的增加，深度學習的優勢愈加突出。例如，Google 藉助深度學習開發的AlphaGo 能從海量的對弈中學習正確的決策，微軟語音識別採用深度學習使識別錯誤率顯著降低，網路基於深度學習開發的機器人「小度」在跨年齡人臉識別上超越了人類。

       經過多年的研究和發展，基於人工神經網路的識別方法也逐漸取代傳統的模式識別方法。神經網路已成為當前比較先進的技術，用來解決許多具有挑戰性的識別任務如文字識別、語音識別、指紋識別、遙感圖像識別、人臉識別、手寫體字元的識別等。其中主流的神經網路模型有卷積網路和遞歸神經網路，卷積神經網路由 Yann LeCun 在 1998 年提出，自從 AlexNe 在 2012 年的 ImageNet 比賽中使用了這一架構拔得頭籌，卷積神經網路迅速流行起來並廣泛應用到視覺任務。如今，最先進的卷積神經網路演算法在進行圖像識別時，甚至可以超過人類肉眼識別的准確率。遞歸神經網路網路提出於 1990 年，被視為循環神經網路的推廣，遞歸神經網路可以引入門控機制以學習長距離依賴，適用於包含結構關系的機器學習任務，在序列識別方面有重要應用。

        深度神經網路和深度學習演算法因為在科研工作與工程任務中都取得了顯著的效果從而大受歡迎。它取代了傳統的手動提取特徵方法，夠端到端地自動提取和學習特徵。而其中取得顯著成功的深度神經網路通常是由於它們成功的架構設計，研究的工作重心從提取特徵轉移到了尋找最優架構上。通常來說，模型的容量越大網路的性能就越好，能夠擬合任意函數。因此為了提升網路性能，網路結構被設計的越來越復雜。例如，VGG-16 約有1.4億浮點數參數，整個網路佔用超過500兆存儲空間，需要153億次浮點操作來處理一個$224\times224$大小的圖像。雖然更深的網路層次和復雜的拓撲結構能夠更有效地學習特徵，但是網路規模的增大意味著人工設計網路時需要花費更多時間來反復試驗，即使是專家也需要大量的資源和時間來創建性能良好的模型。

        神經網路架構搜索(NAS)是一種自動化學習網路結構的新方法，用於減少繁重的網路設計成本。目前為止，NAS方法設計的網路在識別任務上的表現已經超過了人工設計的架構。NAS可以視作自動機器學習（AutoML）的子領域，與超參數優化和元學習有明顯的重疊。不同的NAS方法的區別主要在於三個維度：搜索空間、搜索策略和性能評估，我們對此分別進行了調研。

        搜索空間：搜索空間定義了網路的所有可選結構和操作，通常指數級大，甚至無界。在設計搜索空間時結合先驗知識，即參考現有的針對當前任務的先進結構設計知識，能夠有效減小搜索空間並簡化搜索。但這也會引入偏好，從而限制網路學習到超越當前人類知識的結構。

        搜索策略：定義搜索空間後，搜索策略引導尋找高性能的模型架構，其中的難點是保證探索和利用的平衡。一方面，希望快速找到性能良好的架構，另一方面，需要避免過早收斂到次優的架構。

        性能評估：NSA的目的是找到一個在未知數據上具有良好泛化性能的架構，一旦模型生成，就需要對其性能進行評估。直觀的方法是在訓練集上訓練收斂，並在驗證集上得到其性能，但是這種方法會耗費巨大的算力，從而限制了可探索的網路結構。一些先進的方法關注於減小性能評估時的計算代價，但會引入誤差。因此，平衡評價的效率和效果是一個需要研究的問題。

       從計算的角度來看，神經網路代表了一個通過一系列操作將輸入變數 x 轉換為輸出變數 y 的函數。基於計算圖語言，神經網路可以表示為一個有向無環圖(DAG)，其中每個節點表示一個張量 z ，通過邊連接其父節點 I(k)，每條邊表示從候選操作集O中選擇的一個操作 o 。節點 k 的計算公式為：

        其中候選操作集合$O$主要包括卷積、池化、激活函數、跳躍連接、拼接、加法等基本操作。此外，為了進一步提高模型的性能，一些先進的人工設計模塊也可以作為候選操作，如深度可分離卷積、膨脹卷積、組卷積。基於操作的類型可以選擇不同的超參數，例如輸入節點選取、卷積核數量、尺寸、步長等。不同的搜索空間設計，選擇和組合操作的方法也不同所以參數化的形式也不一樣。一般來說，一個好的搜索空間應該能夠排除人類的偏見，並且足夠靈活，能夠覆蓋更廣泛的模型架構。

        全局搜索空間搜索一個完整的網路結構，具有很高的自由度。最簡單的例子是鏈式搜索空間，見圖1左。固定的數量的節點按順序堆疊，只有前一個節點的輸出提供給後一個節點作為輸入，每個節點代表一個層，並具有指定的操作。右圖引入更復雜的跳躍鏈接和多支路結構，此時當前節點可以結合前面所有節點的輸出作為輸入，使得搜索的自由度顯著增大。許多網路都是多分支網路的特例，比如

1）鏈式網路： ；

2）殘差網路： ；

3）DenseNets：

        雖然整體結構搜索很容易實現，但它也有一些缺點。首先，搜索空間的大小與網路深度是指數級關系，尋找泛化性能好的深度網路計算成本高。此外，生成的架構缺乏可遷移性和靈活性，在小型數據集上生成的模型可能不適合較大的數據集。有研究提出，初始架構的選擇在搜索全局結構時十分重要。在適當的初始條件下，可以獲得與單元搜索空間性能相當的架構，但是初始架構選擇的指導原則仍然不明確。

        基於單元的搜索空間受啟發於人工設計知識，許多有效的網路結構都會重復使用固定結構，例如在RNNs中重復LSTM塊或堆疊殘差模塊。因此可以只搜索這樣的重復單元(cells)，整個神經結構的搜索問題被簡化為在單元搜索空間中搜索最優的單元結構，從而極大的減小搜索空間。大多數研究對比了基於全局搜索空間和單元搜索空間的實驗結果，證明在基於單元的搜索空間中可以獲得良好的性能。單元搜索空間的另一個優勢是能方便地在數據集和任務之間進行泛化，因為通過增減卷積核和單元的數量，架構的復雜性幾乎可以任意改變。

        NASNet是最早提出的單元搜索空間之一，也是當前最熱門的選擇，之後的大部分改進只是在此基礎上對操作選擇和單元組合策略進行了少量修改。如圖2所示，它由兩種單元組成，分別為保持輸入特徵維度的標准單元(normal cell)，和減小空間維度的簡化單元(rection cell)。每個單元由b個塊組成，每個塊由它的兩個輸入和相應的操作定義。可選的輸入包括前兩個單元的輸出和單元中先前定義的塊的輸出，所以它支持跨單元的跳躍連接。未使用的塊被連接起來並作為單元格的輸出，最終通過預定義好的規則級聯這些單元。

        不同於上面將單元結構按照人工定義的宏結構進行連接，層次結構是將前一步驟生成的單元結構作為下一步單元結構的基本組成部件，通過迭代的思想得到最終的網路結構。Hier提出的層次搜索空間，通過合並低層單元生成高級單元實現單元級別和網路級別的同時優化。此方法具體分為3層。第一層包含一系列的基礎操作；第二層通過有向無環圖連接第一層的基礎操作，構建不同的單元，圖結構用鄰接矩陣編碼；第三層是網路級的編碼，決定如何連接第二層的單元，組合成一個完整的網路。基於單元的搜索空間可以看作是這種層次搜索空間的一個特殊情況。

        強化學習方法（RL）能夠有效建模一個順序決策的過程，其中代理與環境相互作用，代理學會改善其行為從而使目標回報最大化。（圖3）給出了一個基於強化的NAS演算法的概述。代理通常是一個遞歸神經網路(RNN)，它在每一步t執行一個動作 來從搜索空間采樣一個新的樣本，同時接收狀態 的觀察值和環境中的獎勵 ，以更新代理的采樣策略。這種方法非常適合於神經結構搜索，代理的行為是生成神經結構，行為空間是搜索空間，環境是指對代理生成的網路進行訓練和評估，獎勵是訓練後的網路結構對未知數據的預測性能，在最後一個行為之後獲得。

4.2進化演算法

        進化演算法（EA）是一種成熟的全局優化方法，具有較高的魯棒性和廣泛的適用性。許多研究使用進化演算法來優化神經網路結構。進化演算法演化了一組模型，即一組網路；在每個世代中，至少從這組模型中選擇一個模型，作為親本在突變後作為生成子代。在對子代進行訓練之後，評估它們的適應度並將它們添加到種群中。

        典型的進化演算法包括選擇、交叉、變異和更新等步驟。選擇時一般使用聯賽選擇演算法對父類進行采樣，其中適應性最好的一個作為親本。Lemonade對適應度使用核密度估計，使網路被選擇的概率與密度成反比。交叉方式因編碼方案的不同而不同。突變針對的是親本的部分操作，例如添加或移除層，改變層的超參數，添加跳躍連接，以及改變訓練超參數。對於產生的後代，大多數方法隨機初始化子網路權重，而Lemonade把父網路學習到的權重通過使用網路態射傳遞給其子網路。Real等人讓後代繼承其父母的所有不受突變影響的參數，雖然這種繼承不是嚴格意義上的功能保留，它可以加速學習。生成新的網路的同時需要從種群中移除一些個體。Real等人從群體中移除最差的個體，AmoebaNet移除最老的個體。也有一些方法定期丟棄所有個體，或者完全不移除個體。EENA通過一個變數調節最壞模型和最老模型的刪除概率。

        基於代理模型的優化方法(SMBO)用一個代理模型來近似目標函數。即不需要訓練采樣到的網路結構，只需要訓練一個代理模型，使用代理模型預測網路的性能。通常在實踐中只需要得到架構的性能排序，而不一定要計算出具體的損失值，因此代理模型只需要預測相對得分並選出有前途的候選架構。然後只對預測性能好的架構進行評估，用它們的驗證精度更新代理模型，這樣只需要完全訓練少量候選架構，大大減少搜索時間。代理模型通常訓練為最小化平方誤差：

        貝葉斯優化（BO）是用於超參數優化的最流行的方法之一。最經典的是基於高斯過程的BO，生成的神經結構的驗證結果可以建模為高斯過程，然而，基於高斯的BO方法在觀察次數上的推理時間尺度是立方的，並且不擅長處理變長神經網路。有些工作使用基於樹或者隨機森林的方法來在非常高維的空間中高效的搜索，並且在很多問題上取得了優異的效果。Negrinho利用其搜索空間的樹形結構，並使用蒙特卡洛樹搜索。雖然沒有完整的比較，但初步的證據表明這些方法可以超越進化演算法。

        上面的搜索策略搜是從一個離散的搜索空間提取神經結構樣本。DARTS提出搜索空間的連續鬆弛，在連續可微的搜索空間上搜索神經架構如圖4所示，並使用如下softmax函數來鬆弛離散空間:

 

鬆弛後，架構搜索的任務轉化為網路架構與神經權值的聯合優化。這兩類參數分別在訓練集和驗證集上交替優化，表示為一個雙層優化問題。

        為了對搜索過程進行引導，必須對產生的神經網路性能進行評估。一種直觀的方法是訓練網路至收斂，然後評估其性能。但是，這種方法需要大量的時間和計算資源。因此提出了幾種加速模型評估的方法。

        為了減少計算負擔，可以用實際性能的低質近似來估測性能。實現方法包括: 縮短訓練時間、選擇數據集的子集、在低解析度的圖像上訓練、每層使用更少的通道數、堆疊更少的單元結構。在低質條件下搜索到的最優網路或單元，構建出最終結構在數據集上重新訓練，得到目標網路。雖然這些低精度的近似能夠減少訓練花費，但性能被低估的同時不可避免地引入了誤差。最近的研究表明，當這種低質評價與完全評價之間的差異較大時，網路性能的相對排名可能變化很大，並強調這種誤差會逐漸增加。

        早停技術最初用於防止過擬合。一些研究通過在訓練初期預測網路性能，在驗證集上預計表現不佳的模型被強制停止訓練，以此來加速模型評估。一種在早期估計網路性能的方法是學習曲線外推法。Domhan 等提出訓練初期對學習曲線進行插值，並終止那些預測性能不好的網路結構的訓練。Swersky等在評估學習曲線的好壞時，把網路架構的超參數作為參考因素。另一種方法根據梯度的局部統計信息實現早期停止，它不再依賴驗證集，允許優化器充分利用所有的訓練數據。

        代理模型可以被訓練用預測網路性能。PNAS提出訓練一個代理網路（LSTM）來預測網路結構的性能，他不考慮學習曲線而是基於結構的特點來預測性能，並在訓練時推斷更大的網路結構。SemiNAS是一種半監督NAS方法，利用大量的未標記架構進一步提高搜索效率。不需要在對模型進行訓練，只使用代理模型來預測模型精度。預測網路性能的主要難點是：為加快搜索過程，需要在對較大的搜索空間進行較少的評估的基礎上進行良好的預測。當優化空間過大且難以量化，且對每個結構的評估成本極高時，基於代理的方法就不適用。

        代理模型還可以用來預測網路權重。超網路（Hypernetworks）是一種神經網路，被訓練來為各種架構生成網路權值。超網路在搜索過程中節省了候選體系結構的訓練時間，因為它們的權值是通過超網路的預測得到的。Zhang等人提出了一種計算圖表示，並使用圖超網路(GHN)比常規超網路(SMASH)更快更准確地預測所有可能架構的權值。

        權重繼承是讓新網路結構繼承之前訓練完成的其他網路結構的權值。其中一種方法是網路態射，一般的網路設計方法是首先設計出一個網路結構，然後訓練它並在驗證集上查看它的性能表現，如果表現較差，則重新設計一個網路。可以很明顯地發現這種設計方法會做很多無用功，因此耗費大量時間。而基於網路態射結構方法能夠在原有的網路結構基礎上做修改，修改後的網路可以重用之前訓練好的權重。其特殊的變換方式能夠保證新的網路結構還原成原網路，因此子網路的表現至少不會差於原網路，並且能在較短的訓練時間內繼續成長為一個更健壯的網路。具體地，網路射態能夠處理任意非線性激活函數，可以添加跳躍連接，並且支持添加層或通道得到更深或更寬的等效模型。經典的網路態射只能使網路變大，這可能導致網路過於復雜，之後提出的近似網路態射通過知識蒸餾允許網路結構減小。進化演算法經常使用基於網路態射的變異，或者直接讓孩子繼承親本的權重，再執行一般變異操作，這樣產生的網路具有一個更好的初始值，而不用重頭開始訓練。

㈤ 優化演算法筆記（七）差分進化演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
差分進化演算法（Differential Evolution Algorithm，DE）是一種基於群體的進化演算法，它模擬了群體中的個體的合作與競爭的過程。演算法原理簡單，控制參數少，只有交叉概率和縮放比例因子，魯棒性強，易於實現。
差分進化演算法中，每一個個體的基因表示待求問題的一個候選解。每次迭代將先進行變異操作，選擇一個或多個個體的基因作為基，然後選擇不同的個體的差分來構成差分基因，最後將作為基的基因與差分基因相加來得出新的個體。交叉操作將新的個體將於父代的對應個體交叉，然後進行選擇操作，比較交叉後的個體與父代的對應個體，選擇較優的個體保留至下一代。在迭代完成之後將選擇種群中最優個體的基因作為解。
差分進化演算法可以算是我所使用過的優化演算法中大魔王級別的演算法，雖然它每個方面都沒有強到離譜，但是綜合起來的效果好於大多數演算法。它就像一個每個科目都能考到90分（百分制）的學生，雖然沒門課都不是最優秀的，但是論綜合，論總分，它有極大的概率是第一名。

在我研究優化演算法的小路上，我的目標就是找到一個能打敗大魔王或是能在大多數方面壓制魔王的演算法。

這次的主角就選魔王軍吧（或者蟻王軍，為了與蟻群演算法區別還是叫魔王軍吧），個體則稱之為魔王兵。
魔王兵的能力取決於它們的基因，它們可以根據環境或者需要改變自己的基因使得自己更加強大，更方便的處理問題，問題的維度與基因維度相同。

表示第i個魔王兵在進化了第t次後的基因，該個體有D位基因。
與遺傳演算法同為進化演算法的差分進化演算法，它們的操作（運算元）也都非常相似的，都是交叉，變異和選擇，流程也幾乎一樣（遺傳演算法先交叉後變異，差分進化演算法先變異後交叉）。

說到差分進化演算法中的變異，我就想到一句論語 「三人行，必有我師焉。擇其善者而從之，其不善者而改之。」 ，其實這句論語已經向我們說明了差分進化演算法的整個流程：
「三人行，必有我師焉」——變異，交叉。
「擇其善者而從之，其不善者而改之」——選擇。
差分進化演算法中，當一個魔王兵變異時，它會先找來3個小夥伴，當然是隨機找來3個小夥伴，避免同化。在一個小夥伴的基因上加上另外兩個小夥伴基因之差作為自己的目標基因。其變異公式如下：

表示第i個魔王兵找到了編號為r1、r2和r3的三個魔王兵，當然了i、r1、r2、r3為互不相同的整數，F為縮放比例因子，通常 ，一般取F=0.5。 為第i個魔王兵交叉後的目標基因圖紙，不過這是個半成品，再經過交叉後，目標基因圖紙才算完成。
其實現在我們已經有了5個基因圖紙了 ，接下來將進行交叉操作。由於變異操作，差分進化演算法的種群中個體數至少為4，即魔王軍中至少有4個小兵。

交叉操作中，魔王兵i會將目標基因圖紙 進行加工得到 ，加工過程如下：

其中 。 為交叉概率，其值越大，發生交叉的概率越大，一般取 。 為{1,2,…,D}中的隨機整數，其作用是保證交叉操作中至少有一維基因來自變異操作產生的基因，不能讓交叉操作的努力白費。
從公式上可以看出交叉操作實際上是從變異操作得出的基因圖紙上選擇至少一位基因來替換自己的等位基因，得到最終的基因圖紙。

選擇操作相對簡單，魔王兵i拿到了最終的基因圖紙 ，大喊一聲，進化吧，魔王兵i的基因改變了。它拿出了能力測量器fitness function,如果發現自己變強了，那麼就將基因 保留到下一代，否則它選擇放棄進化，讓自己還原成 。

實驗又來啦，還是那個實驗 ，簡單、易算、好畫圖。
實驗1 ：參數如下

圖中可以看出在第20代時，群體已經非常集中了，在來看看最終得出的結果。

這結果真是好到令人發指，惡魔在心中低語「把其他的優化演算法都丟掉吧」。不過別往心裡去，任何演算法都有優缺點，天下沒有免費的午餐，要想獲得某種能力必須付出至少相應的代價。
實驗2：
將交叉率CR設為0,即每次交叉只選擇保留一位變異基因。

看看了看圖，感覺跟實驗1中相比沒有什麼變化，那我們再來看看結果。

結果總體來說比實驗1好了一個數量級。為什麼呢？個人感覺應該是每次只改變一位基因的局部搜索能力比改變多位基因更強。下面我們將交叉率CR設為1來看看是否是這樣。
實驗3：
將交叉率CR設為1,即每次交叉只選擇保留一位原有基因。

實驗3的圖與實驗1和實驗2相比好像也沒什麼差別,只是收斂速度好像快了那麼一點點。再來看看結果。

發現結果比實驗2的結果還要好？那說明了實驗2我得出的結論是可能是錯誤的，交叉率在該問題上對差分進化演算法的影響不大，它們結果的差異可能只是運氣的差異，畢竟是概率演算法。
實驗4：
將變異放縮因子設為0，即變異只與一個個體有關。

收斂速度依然很快，不過怎麼感覺結果不對，而且個體收斂的路徑好像遺傳演算法，當F=0，時，差分進化演算法退化為了沒有變異、選擇操作的遺傳演算法，結果一定不會太好。

果然如此。下面我們再看看F=2時的實驗。
實驗5：
將變異放縮因子設為2。

實驗5的圖可以明顯看出，群體的收斂速度要慢了許多，到第50代時，種群還未完全收斂於一點，那麼在50代時其結果也不會很好，畢竟演算法還未收斂就停止進化了。

結果不算很好但也算相對穩定。

通過上面5個實驗，我們大致了解了差分進化演算法的兩個參數的作用。
交叉率CR，影響基因取自變異基因的比例，由於至少要保留一位自己的基因和變異的基因導致CR在該問題上對演算法性能的影響不大（這個問題比較簡單，維度較低，影響不大）。
變異放縮因子F，影響群體的收斂速度，F越大收斂速度越慢，F絕對值越小收斂速度越快，當F=0是群體之間只會交換基因，不會變異基因。

差分進化演算法大魔王已經如此強大了，那麼還有什麼可以改進的呢？當然有下面一一道來。
方案1 .將3人行修改為5人行，以及推廣到2n+1人行。
實驗6：
將3人行修改為5人行，變異公式如下：

五人行的實驗圖看起來好像與之前並沒有太大的變化，我們再來看看結果。

結果沒有明顯提升，反而感覺比之前的結果差了。反思一下五人行的優缺點，優點，取值范圍更大，缺點，情況太多，減慢搜索速度。

可以看出演算法的收斂速度比之前的變慢了一點，再看看結果。

比之前差。

差分進化演算法的學習在此也告一段落。差分進化演算法很強大，也很簡單、簡潔，演算法的描述都充滿了美感，不愧是大魔王。不過這里並不是結束，這只是個開始，終將找到打敗大魔王的方法，讓新的魔王誕生。
由於差分進化演算法足夠強，而文中實驗的問題較為簡單導致演算法的改進甚至越改越差（其實我也不知道改的如何，需要大量實驗驗證）。在遙遠的將來，也會有更加復雜的問題來檢驗魔王的能力，總之，後會無期。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（六）遺傳演算法
下一篇 優化演算法筆記（八）人工蜂群演算法

優化演算法matlab實現（七）差分進化演算法matlab實現

㈥ 請問，遺傳演算法中的交叉編譯概率在編寫子函數時為啥要在rand(1)小於概...

遺傳演算法中的交叉變異概率在編子函數時，應該是rand(1)產生的隨機數小於交叉率pc,或交叉率pm才能進行交叉變異操作。
因為遺傳演算法中，交叉變異操作是以一定的交叉率pc和一定的變異率pm執行的。所以首先選擇參與交叉或變異操作的個體進入到交配池，選擇過程是隨機選擇的，即滿足rand(1)
<pc或rand(1)
<pm才被選擇

㈦ 各種進化演算法有什麼異同

（差異進化演算法DE）是一種用於優化問題的啟發式演算法。本質上說，它是一種基於實數編碼的具有保優思想的貪婪遺傳演算法[1] 。同遺傳演算法一樣，差異進化演算法包含變異和交叉操作，但同時相較於遺傳演算法的選擇操作，差異進化演算法採用一對一的淘汰機制來更新種群。由於差異進化演算法在連續域優化問題的優勢已獲得廣泛應用，並引發進化演算法研究領域的熱潮。 差異進化演算法由Storn 以及Price [2]提出，演算法的原理採用對個體進行方向擾動，以達到對個體的函數值進行下降的目的，同其他進化演算法一樣，差異進化演算法不利用函數的梯度信息，因此對函數的可導性甚至連續性沒有要求，適用性很強。

㈧ 人工智慧之進化演算法

進化計算的三大分支包括：遺傳演算法(Genetic Algorithm ，簡稱GA)、進化規劃(Evolu-tionary Programming，簡稱EP)和進化策略(Evolution Strategies ，簡稱ES)。這三個分支在演算法實現方面具有一些細微的差別，但它們具有一個共同的特點，即都是藉助生物進化的思想和原理來解決實際問題。

遺傳演算法是一類通過模擬生物界自然選擇和自然遺傳機制的隨機化搜索演算法，由美國Holand J教授於1975年首次提出。它是利用某種編碼技術作用於稱為染色體的二進制數串，其基本思想是模擬由這些串組成的種群的進化過程，通過有組織的、然而是隨機的信息交換來重新組合那些適應性好的串。遺傳演算法對求解問題的本身一無所知，它所需要的僅是對演算法所產生的每個染色體進行評價，並根據適應性來選擇染色體，使適應性好的染色體比適應性差的染色體有更多的繁殖機會。遺傳演算法尤其適用於處理傳統搜索方法難於解決的復雜的非線性問題，可廣泛用於組合優化、機器學習、自適應控制、規劃設計和人工生命等領域，是21世紀有關智能計算中的關鍵技術之一。

1964年，由德國柏林工業大學的RechenbergI等人提出。在求解流體動力學柔性彎曲管的形狀優化問題時，用傳統的方法很難在優化設計中描述物體形狀的參數，然而利用生物變異的思想來隨機地改變參數值並獲得了較好效果。隨後，他們便對這種方法進行了深入的研究和發展，形成了進化計算的另一個分支——進化策略。

進化策略與遺傳演算法的不同之處在於：進化策略直接在解空間上進行操作，強調進化過程中從父體到後代行為的自適應性和多樣性，強調進化過程中搜索步長的自適應性調節;而遺傳演算法是將原問題的解空間映射到位串空間之中，然後再施行遺傳操作，它強調個體基因結構的變化對其適應度的影響。

進化策略主要用於求解數值優化問題。

進化規劃的方法最初是由美國人Fogel LJ等人在20世紀60年代提出的。他們在人工智慧的研究中發現，智能行為要具有能預測其所處環境的狀態，並按照給定的目標做出適當的響應的能力。在研究中，他們將模擬環境描述成是由有限字元集中符號組成的序列。

進化演算法與傳統的演算法具有很多不同之處，但其最主要的特點體現在下述兩個方面：

進化計算的智能性包括自組織、自適應和自學習性等。應用進化計算求解問題時，在確定了編碼方案、適應值函數及遺傳運算元以後，演算法將根據「適者生存、不適應者淘汰"的策略，利用進化過程中獲得的信息自行組織搜索，從而不斷地向最佳解方向逼近。自然選擇消除了傳統演算法設計過程中的-一個最大障礙：即需要事先描述問題的全部特點，並說明針對問題的不同特點演算法應採取的措施。於是，利用進化計算的方法可以解決那些結構尚無人能理解的復雜問題。

進化計算的本質並行性表現在兩個方面：

一是進化計算是內在並行的，即進化計算本身非常適合大規模並行。

二是進化計算的內含並行性，由於進化計算採用種群的方式組織搜索，從而它可以同時搜索解空間內的多個區域，並相互交流信息，這種搜索方式使得進化計算能以較少的計算獲得較大的收益。

㈨ 各種進化演算法有什麼異同

同遺傳演算法一樣，差異進化演算法包含變異和交叉操作，但同時相較於遺傳演算法的選擇操作，差異進化演算法採用一對一的淘汰機制來更新種群。由於差異進化演算法在連續域優化問題的優勢已獲得廣泛應用，並引發進化演算法研究領域的熱潮。

進化演算法

或稱「演化演算法」 (evolutionary algorithms) 是一個「演算法簇」，盡管它有很多的變化，有不同的遺傳基因表達方式，不同的交叉和變異運算元，特殊運算元的引用，以及不同的再生和選擇方法，但它們產生的靈感都來自於大自然的生物進化。

與傳統的基於微積分的方法和窮舉法等優化演算法相比，進化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優化方法，具有自組織、自適應、自學習的特性，能夠不受問題性質的限制，有效地處理傳統優化演算法難以解決的復雜問題。

㈩ 進化演算法的基本步驟

進化計算是基於自然選擇和自然遺傳等生物進化機制的一種搜索演算法。與普通的搜索方法一樣，進化計算也是一種迭代演算法，不同的是進化計算在最優解的搜索過程中，一般是從原問題的一組解出發改進到另一組較好的解，再從這組改進的解出發進一步改進。而且在進化問題中，要求當原問題的優化模型建立後，還必須對原問題的解進行編碼。進化計算在搜索過程中利用結構化和隨機性的信息，使最滿足目標的決策獲得最大的生存可能，是一種概率型的演算法。
一般來說，進化計算的求解包括以下幾個步驟：給定一組初始解；評價當前這組解的性能；從當前這組解中選擇一定數量的解作為迭代後的解的基礎；再對其進行操作，得到迭代後的解；若這些解滿足要求則停止，否則將這些迭代得到的解作為當前解重新操作。
以遺傳演算法為例，其工作步驟可概括為：
（1） 對工作對象——字元串用二進制的0/1或其它進制字元編碼 。
（2） 根據字元串的長度L，隨即產生L個字元組成初始個體。
（3） 計算適應度。適應度是衡量個體優劣的標志，通常是所研究問題的目標函數。
（4） 通過復制，將優良個體插入下一代新群體中，體現「優勝劣汰」的原則。
（5） 交換字元，產生新個體。交換點的位置是隨機決定的
（6） 對某個字元進行補運算，將字元1變為0，或將0變為1，這是產生新個體的另一種方法，突變字元的位置也是隨機決定的。
（7） 遺傳演算法是一個反復迭代的過程，每次迭代期間，要執行適應度計算、復制、交換、突變等操作，直至滿足終止條件。
將其用形式化語言表達，則為：假設α∈I記為個體，I記為個體空間。適應度函數記為Φ：I→R。在第t代，群體P(t)={a1(t),a2(t)，…，an(t)}經過復制r(reproction)、交換c(crossover)及突變m(mutation)轉換成下一代群體。這里r、c、m均指宏運算元，把舊群體變換為新群體。L：I→{True, Flase}記為終止准則。利用上述符號，遺傳演算法可描述為：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end