遺傳算法簡(jiǎn)介01遺傳算法基本思想和組成要素02遺傳算法實(shí)現(xiàn)與應(yīng)用03群智能算法概述04本講提綱粒子群算法及應(yīng)用05第7章

進(jìn)化計(jì)算與群智能算法遺傳算法（GeneticAlgorithm,GA）是一種模擬生物進(jìn)化論和遺傳學(xué)機(jī)理的隨機(jī)搜索技術(shù)，它依據(jù)“適者生存、優(yōu)勝劣汰”的自然進(jìn)化法則，致力于探尋全局最優(yōu)解。7.1遺傳算法簡(jiǎn)介20世紀(jì)60~70年代，美國(guó)密歇根大學(xué)的JohnHolland教授及其學(xué)生團(tuán)隊(duì)提出了編碼、交叉、變異、選擇以及適應(yīng)度評(píng)價(jià)等核心機(jī)制，開創(chuàng)性地將這些自然科學(xué)的原理應(yīng)用于計(jì)算機(jī)科學(xué)與優(yōu)化問題的求解中，從而奠定了遺傳算法的基礎(chǔ).20世紀(jì)80年代開始被學(xué)術(shù)界廣泛接受及應(yīng)用。JohnHolland教授達(dá)爾文進(jìn)化論孟德爾遺傳學(xué)說遺傳算法的提出者及發(fā)展歷程7.1遺傳算法簡(jiǎn)介（1）物種的可變性：物種會(huì)隨著時(shí)間的推移發(fā)生演化。（2）自然選擇：生物在生存競(jìng)爭(zhēng)中，適應(yīng)環(huán)境的個(gè)體更有可能生存下來并繁衍后代，從而將其有利的遺傳特征傳遞給下一代。（3）共同祖先：所有的生物都有一個(gè)或多個(gè)共同的祖先，并通過長(zhǎng)時(shí)間的演化形成了現(xiàn)今多種多樣的生物種類。達(dá)爾文進(jìn)化論：物競(jìng)天擇，適者生存遺傳算法的生物學(xué)背景7.1遺傳算法簡(jiǎn)介（1）分離定律：基因作為獨(dú)立的單位會(huì)代代相傳，細(xì)胞中的成對(duì)遺傳單位分別來自于雌雄親本；（2）獨(dú)立分配定律：染色體上的等位基因能夠獨(dú)立地進(jìn)行遺傳。孟德爾遺傳學(xué)說：物種的進(jìn)化是由于基因的遺傳和變異遺傳算法的生物學(xué)背景7.1遺傳算法簡(jiǎn)介優(yōu)點(diǎn)

全局優(yōu)化能力。處理數(shù)學(xué)描述復(fù)雜的問題。處理缺少數(shù)學(xué)模型的問題?？乖肼暷芰?。支持并行和分布式處理。持續(xù)學(xué)習(xí)的適應(yīng)性。

特殊定義。超參數(shù)優(yōu)化。計(jì)算密集型操作。過早收斂風(fēng)險(xiǎn)。無絕對(duì)最優(yōu)解。局限性7.1遺傳算法簡(jiǎn)介適用場(chǎng)景問題具有復(fù)雜的數(shù)學(xué)表述：遺傳算法的優(yōu)勢(shì)在于，它僅需依賴適應(yīng)度函數(shù)的結(jié)果。因此，它適用于那些目標(biāo)函數(shù)難以明確區(qū)分或根本無法區(qū)分的問題，以及參數(shù)眾多或參數(shù)類型混合的問題。無需數(shù)學(xué)表述的問題：遺傳算法并不要求問題必須有明確的數(shù)學(xué)描述。只要能夠獲得一個(gè)評(píng)分值，或者有方法比較兩個(gè)解的優(yōu)劣，遺傳算法就能發(fā)揮作用。包含噪聲環(huán)境的問題：遺傳算法對(duì)于數(shù)據(jù)可能不一致的問題表現(xiàn)出很強(qiáng)的適應(yīng)性，這類問題可能源于傳感器輸出的數(shù)據(jù)波動(dòng)或人工評(píng)分的主觀性。涉及環(huán)境變化的問題：遺傳算法能夠通過持續(xù)生成適應(yīng)新環(huán)境的新一代種群，來有效應(yīng)對(duì)環(huán)境的緩慢變化。7.1遺傳算法簡(jiǎn)介遺傳算法的基本思想遺傳算法本質(zhì)上是一種并行、高效、全局搜索的方法，它能在搜索過程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過程以求得最優(yōu)解。在遺傳算法的每一代中，模擬自然選擇過程（適應(yīng)度較高的個(gè)體具有更高的概率產(chǎn)生下一代），根據(jù)個(gè)體在問題域中的適應(yīng)度值和從自然遺傳學(xué)中借鑒來的再造方法（交叉和變異）進(jìn)行個(gè)體選擇，產(chǎn)生一個(gè)新的近似解。這個(gè)過程導(dǎo)致種群中個(gè)體的進(jìn)化，得到的新個(gè)體比原個(gè)體更能適應(yīng)環(huán)境，就像自然界中的改造一樣。如此迭代，直至產(chǎn)生一個(gè)適應(yīng)度最高的個(gè)體（最優(yōu)解）。7.2基本思想和組成要素遺傳算法的組成要素1.染色體和基因一個(gè)染色體代表了問題的一個(gè)候選解。借鑒生物學(xué)中的概念，一個(gè)染色體由多個(gè)基因構(gòu)成。例如，使用一個(gè)二進(jìn)制字符串表示問題的一個(gè)候選解（染色體），那么該二進(jìn)制字符串中的每一位被稱為一個(gè)基因，即一個(gè)解碼單元。將問題的候選解表示為染色體的過程稱為編碼。7.2基本思想和組成要素7.2基本思想和組成要素遺傳算法的組成要素2.種群待解決問題候選解的集合。因?yàn)榉N群中的每個(gè)個(gè)體由染色體表示，所以種群也可視為染色體的集合。3.適應(yīng)度函數(shù)和適應(yīng)度值適應(yīng)度函數(shù)用于計(jì)算種群中每個(gè)個(gè)體（染色體）的適應(yīng)度值。計(jì)算得到的適應(yīng)度值越大，說明該染色體的質(zhì)量越高（是一個(gè)更好的解），也就更有可能被用于繁殖后代。遺傳算法的組成要素4.選擇在種群中挑選用于繁殖下一代的所有染色體的過程。染色體的適應(yīng)度值越高，被選中的幾率越大。適應(yīng)度值較低的染色體依然可被選擇，但概率較低。5.交叉為了創(chuàng)造一對(duì)新個(gè)體，作為雙親的兩個(gè)父代個(gè)體交換某些基因形成子代個(gè)體的過程，亦稱為重組。交叉操作依概率進(jìn)行，即：一對(duì)染色體是否進(jìn)行交叉操作由預(yù)先定義的交叉概率決定。7.2基本思想和組成要素遺傳算法的組成要素6.變異一個(gè)或多個(gè)染色體基因的隨機(jī)更改，依概率進(jìn)行，但變異的概率一般都較小。變異旨在周期性的隨機(jī)更新種群，豐富染色體的多樣性，使算法在解空間的未知區(qū)域進(jìn)行搜索，避免陷入局部解。例如，染色體的第6個(gè)基因發(fā)生變異，如下圖所示。7.2基本思想和組成要素遺傳算法的基本流程7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析1.編碼遺傳算法通過編碼將問題的解空間映射到遺傳算法的搜索空間，所以遺傳算法中編碼方式的選擇對(duì)算法的性能和效率有著至關(guān)重要的影響。二進(jìn)制編碼實(shí)數(shù)編碼排列編碼7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（1）二進(jìn)制編碼遺傳算法中最基本、最常用的編碼方式。它將問題的解空間映射到一個(gè)由0和1組成的二進(jìn)制字符串上，每個(gè)二進(jìn)制位代表解的一個(gè)特征或決策變量的一部分。二進(jìn)制編碼一般用于將數(shù)值轉(zhuǎn)為二進(jìn)制串，用以求解問題。二進(jìn)制編碼具有編解碼簡(jiǎn)單、交叉和變異操作易于實(shí)現(xiàn)的優(yōu)點(diǎn)，但在表示高精度連續(xù)變量時(shí)可能存在精度損失的問題。7.3遺傳算法的實(shí)現(xiàn)過程編碼原理：要想實(shí)現(xiàn)每個(gè)數(shù)值都能分配一個(gè)獨(dú)一無二的串，那么串所能表示的數(shù)值個(gè)數(shù)就要大于等于數(shù)值解的個(gè)數(shù)。一個(gè)長(zhǎng)度為n的串，能表示2"個(gè)數(shù)。假設(shè)某一參數(shù)的區(qū)間范圍是[a,b]，精度為E的條件下，二進(jìn)制串的長(zhǎng)度為n，三者關(guān)系需滿足:

，其中

被稱為編碼精度δ例如:想達(dá)到1e-5的精度，對(duì)于區(qū)間為[0,10]，串的長(zhǎng)度n應(yīng)該滿足計(jì)算得到n≥20。n=20時(shí)，串提供的精度約為0.00000954。變量X的某值xi的二進(jìn)制編碼yi的計(jì)算公式為：7.3遺傳算法的實(shí)現(xiàn)過程二進(jìn)制編碼示例：假設(shè)有一個(gè)擁有兩個(gè)決策變量的優(yōu)化問題，每個(gè)變量的取值范圍都在[0,1]之間，精度為0.1。根據(jù)精度計(jì)算可得，串長(zhǎng)至少為4。因此，兩個(gè)變量的取值可以分別編碼為兩個(gè)長(zhǎng)度為4的二進(jìn)制串，構(gòu)成一個(gè)總長(zhǎng)度為8的染色體。例如，X1=0.2、X2=0.8，根據(jù)編碼計(jì)算公式可以近似編碼為00111100（注意：在實(shí)際計(jì)算中這里可能產(chǎn)生精度損失）。X1

=((0.2-0)/15)2=(3)2=0011X2=((0.8-0)/15)2=(12)2=11007.3遺傳算法的實(shí)現(xiàn)過程解碼原理：將二進(jìn)制串轉(zhuǎn)換為原參數(shù)數(shù)值的過程稱為解碼。一般的，區(qū)間范圍為[a,b]，串長(zhǎng)為n，當(dāng)前串對(duì)應(yīng)的十進(jìn)制值為T（例如二進(jìn)制1011對(duì)應(yīng)的十進(jìn)制值為11），則該串對(duì)應(yīng)的實(shí)值x為:解碼示例：

7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（2）實(shí)數(shù)編碼實(shí)數(shù)編碼是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)實(shí)數(shù)來表示，編碼長(zhǎng)度等于決策變量的個(gè)數(shù)。這種編碼方式直接反映了問題的解空間，避免了二進(jìn)制編碼中的精度損失問題，特別適用于連續(xù)變量的優(yōu)化問題。示例：對(duì)于一個(gè)兩變量的優(yōu)化問題，其中每個(gè)變量的取值范圍在[0,10]之間。我們可以直接使用實(shí)數(shù)來表示每個(gè)變量的值，例如X1=3.4、X2=8.7。這個(gè)候選解可以表示為一個(gè)長(zhǎng)度為2的實(shí)數(shù)向量[3.4,8.7]。在實(shí)數(shù)編碼下，交叉和變異操作需要采用特定的方法來實(shí)現(xiàn)，如算術(shù)交叉和多項(xiàng)式變異等。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（3）排列編碼排列編碼是針對(duì)特定問題（如旅行商問題TSP）的一種編碼方式。它將有限集合內(nèi)的元素進(jìn)行排列來表示問題的解。這種編碼方式使得問題表示簡(jiǎn)潔且易于理解，特別適用于需要排序或排列的問題。在TSP問題中，假設(shè)有n個(gè)城市需要訪問，則一個(gè)可能的解可以表示為一個(gè)長(zhǎng)度為n的整數(shù)向量，其中每個(gè)整數(shù)代表一個(gè)城市的編號(hào)，且每個(gè)編號(hào)只出現(xiàn)一次。例如，[4,2,3,1,5]表示先訪問城市4，然后訪問城市2、3、1、5，最后回到起點(diǎn)城市4。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析2.種群初始化種群初始化指的是在選定編碼方案后通過某種方式產(chǎn)生N個(gè)染色體，其中N稱為種群規(guī)模。種群初始化方法的選擇取決于具體問題的特點(diǎn)和需求。常用種群初始化方法有：隨機(jī)初始化法(無先驗(yàn)知識(shí))、均勻分布初始化法、聚類初始化法、問題特定初始化法（有先驗(yàn)知識(shí)）、進(jìn)化初始化法等。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析3.選擇（1）輪盤賭選擇輪盤賭選擇是一種基于適應(yīng)度比例的選擇方法，較為常用，其基本思想是各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。個(gè)體適應(yīng)度值被選中概率

x1100.1

x2200.2

x3300.3

x4400.47.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（1）輪盤賭選擇為了在計(jì)算機(jī)上方便地實(shí)現(xiàn)輪盤賭選擇，通常需要計(jì)算每個(gè)個(gè)體的累積概率。累積概率表示從第一個(gè)個(gè)體到當(dāng)前個(gè)體為止，所有個(gè)體被選中概率之和。累積概率的計(jì)算公式為：q(x1)=0.1q(x2)=0.1+0.2=0.3q(x3)=0.1+0.2+0.3=0.6q(x4)=0.1+0.2+0.3+0.4=1.0假設(shè)生成的隨機(jī)數(shù)為0.25，則因?yàn)?.1<0.25≤0.3，所以選擇個(gè)體x27.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（1）輪盤賭選擇輪盤賭的選擇過程如下：1）生成隨機(jī)數(shù)：在[0,1]區(qū)間內(nèi)生成一個(gè)均勻分布的隨機(jī)數(shù)r。2）匹配隨機(jī)數(shù)：將生成的隨機(jī)數(shù)r與每個(gè)個(gè)體的累積概率進(jìn)行比較，找到滿足條件q(xk-1)<r≤q(xk)的個(gè)體xk,其中k為選中的個(gè)體索引。注意，這里q(x0)被定義為0，以便比較第一個(gè)個(gè)體。3）選擇個(gè)體：根據(jù)上一步的結(jié)果，選擇個(gè)體xk進(jìn)入下一代種群。4）重復(fù)過程：如果需要選擇多個(gè)個(gè)體，則重復(fù)步驟1至3，直到達(dá)到所需的個(gè)體數(shù)量。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（2）基于排序的選擇基于排序的選擇策略是在輪盤賭選擇的基礎(chǔ)上改進(jìn)而來。這種方法的核心思想是將種群中的個(gè)體按照適應(yīng)度進(jìn)行排序，然后根據(jù)排序結(jié)果為每個(gè)個(gè)體賦予一個(gè)排名值，根據(jù)排名值計(jì)算輪盤賭的概率。個(gè)體適應(yīng)度值排名值被選中概率（輪盤賭）被選中概率（基于排序）

x11010.100.1

x21330.130.3

x31220.120.2

x47540.750.4假設(shè)我們有一個(gè)包含4個(gè)個(gè)體的種群，每個(gè)個(gè)體的適應(yīng)度值分別為10,13,12,75。由于種群規(guī)模為4，則適應(yīng)度最高的個(gè)體獲得排名值4，以此類推。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（2）基于排序的選擇該方法適用于個(gè)體適應(yīng)度比其他所有個(gè)體大得多的情況（如上表中x4）。依據(jù)排名值而非適應(yīng)度值，可以消除適應(yīng)度值帶來的巨大差異，避免少數(shù)高適應(yīng)度個(gè)體被過度重復(fù)選擇，從而占據(jù)下一代的全部種群。同樣，如果種群中多個(gè)個(gè)體的適應(yīng)度值很相似（如上表中x1，x2，x3），該方法可將他們進(jìn)行有效區(qū)分，為優(yōu)秀個(gè)體帶來優(yōu)勢(shì)。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（3）錦標(biāo)賽選擇錦標(biāo)賽選擇是一種基于競(jìng)爭(zhēng)的選擇方法。在每次選擇操作中，從種群中隨機(jī)選擇一定數(shù)量（如3個(gè)，稱為錦標(biāo)賽規(guī)模）的個(gè)體進(jìn)行錦標(biāo)賽，即比較它們的適應(yīng)度值，選擇適應(yīng)度值最高的個(gè)體進(jìn)入下一代種群。錦標(biāo)賽選擇在實(shí)際應(yīng)用中經(jīng)常被使用，因?yàn)樗c遺傳算法的適應(yīng)度函數(shù)尺度無關(guān)，只關(guān)注個(gè)體之間的適應(yīng)度值相對(duì)大小，而不是絕對(duì)大小。7.3遺傳算法的實(shí)現(xiàn)過程遺傳算法的關(guān)鍵步驟解析（4）精英保留選擇精英保留選擇是一種保證最優(yōu)個(gè)體不被破壞的選擇方法。在每次選擇操作之前，首先找出當(dāng)前種群中適應(yīng)度最高的個(gè)體（或幾個(gè)個(gè)體），然后將這些個(gè)體直接復(fù)制到下一代種群中。接下來，對(duì)剩余的個(gè)體執(zhí)行其他選擇操作（如輪盤賭選擇、錦標(biāo)賽選擇等）。這種方法可以有效地保留種群中的優(yōu)秀個(gè)體，防止算法在進(jìn)化過程中丟失最優(yōu)解。7.3遺傳算法的實(shí)現(xiàn)過程4.交叉（1）單點(diǎn)交叉在個(gè)體的基因序列上隨機(jī)選擇一個(gè)交叉點(diǎn)，將兩個(gè)個(gè)體的基因序列在交叉點(diǎn)處交換，生成兩個(gè)新的子代個(gè)體。7.3遺傳算法的實(shí)現(xiàn)過程（2）兩點(diǎn)交叉和多點(diǎn)交叉兩點(diǎn)交叉：在個(gè)體的基因序列上隨機(jī)選擇兩個(gè)交叉點(diǎn)，將兩個(gè)個(gè)體的基因序列在這兩個(gè)交叉點(diǎn)之間的部分進(jìn)行交換，生成兩個(gè)新的子代個(gè)體。注意：兩點(diǎn)交叉可以通過執(zhí)行兩次位置不同的單點(diǎn)交叉來實(shí)現(xiàn)，同理，多點(diǎn)交叉可以看作是兩點(diǎn)交叉的拓展。7.3遺傳算法的實(shí)現(xiàn)過程（3）均勻交叉對(duì)于每個(gè)基因位，以一定的概率（如0.5）選擇從一個(gè)父代個(gè)體繼承該基因位的值，從另一個(gè)父代個(gè)體繼承該基因位的值，生成兩個(gè)新的子代個(gè)體。注意：結(jié)果隨機(jī)7.3遺傳算法的實(shí)現(xiàn)過程（4）部分匹配交叉一種用于解決特定類型問題（如旅行商問題TSP）的交叉方法。它首先隨機(jī)選擇兩個(gè)交叉點(diǎn)，然后建立一個(gè)映射關(guān)系來確保交叉后生成的子代個(gè)體中的基因不重復(fù)。

無效解（存在重復(fù)）7.3遺傳算法的實(shí)現(xiàn)過程（4）部分匹配交叉此時(shí)就需要通過映射關(guān)系修復(fù)交叉后的子代個(gè)體，以確保每個(gè)城市只被訪問一次。具體處理過程如下：1）根據(jù)交換的兩組基因建立映射關(guān)系，示例中建立的映射關(guān)系為1?6?3?4,2?5。2）由于中間個(gè)體A’中存在重復(fù)基因1，按照映射關(guān)系將其中一個(gè)轉(zhuǎn)變?yōu)?，重復(fù)該過程，直至不存在沖突位置。7.3遺傳算法的實(shí)現(xiàn)過程5.變異（1）反轉(zhuǎn)變異適用于二進(jìn)制編碼染色體。反轉(zhuǎn)變異是指以某一較小的概率反轉(zhuǎn)某些基因位的值。對(duì)于二進(jìn)制編碼的個(gè)體，反轉(zhuǎn)變異就是將某些基因位上的基因值取反（0變1，1變0）。舉例：假設(shè)有一個(gè)二進(jìn)制編碼的個(gè)體10110011，若第三個(gè)基因位發(fā)生變異，則變異后的個(gè)體為10010011。針對(duì)二進(jìn)制編碼和排列編碼的變異策略7.3遺傳算法的實(shí)現(xiàn)過程5.變異（2）交換變異適用于二進(jìn)制編碼染色體或排列編碼染色體。隨機(jī)選擇兩個(gè)基因位進(jìn)行互換，如下圖所示。（3）逆序變異適用于二進(jìn)制編碼染色體或排列編碼染色體。在染色體中隨機(jī)選擇一個(gè)基因序列，然后將該基因序列逆置，如下圖所示。針對(duì)二進(jìn)制編碼和排列編碼的變異策略7.3遺傳算法的實(shí)現(xiàn)過程5.變異（4）插入變異適用于二進(jìn)制編碼染色體或排列編碼染色體。隨機(jī)選擇染色體（個(gè)體編碼）上的一個(gè)基因（或基因片段），然后將其插入到染色體中的另一個(gè)隨機(jī)位置，從而生成一個(gè)新的染色體（個(gè)體）。如下圖所示。針對(duì)二進(jìn)制編碼和排列編碼的變異策略7.3遺傳算法的實(shí)現(xiàn)過程5.變異（1）均勻變異：取值范圍內(nèi)的一個(gè)隨機(jī)數(shù)。（2）非均勻變異：隨著迭代次數(shù)的增加，變異量逐漸減小。有助于在搜索初期進(jìn)行全局搜索，而在搜索后期進(jìn)行局部搜索。變異量大小與當(dāng)前進(jìn)化代數(shù)和基因原始值有關(guān)。（3）邊界變異：它使得變異后的基因值更趨向于取值范圍的邊界。這種變異方式有助于探索解空間的邊界區(qū)域，可能發(fā)現(xiàn)更優(yōu)的解。（4）高斯變異：以高斯分布（正態(tài)分布）產(chǎn)生的隨機(jī)數(shù)來替換原有基因值的一種變異方式。這種變異方式有助于在解空間中進(jìn)行更加細(xì)致的搜索。針對(duì)實(shí)數(shù)編碼的變異策略7.3遺傳算法的實(shí)現(xiàn)過程6.遺傳算法的結(jié)束條件（1）達(dá)到預(yù)設(shè)的最大迭代次數(shù)（2）當(dāng)前最優(yōu)解的適應(yīng)度已經(jīng)超過預(yù)設(shè)值或達(dá)到期望解決方案（3）前幾代的最優(yōu)解與當(dāng)前的最優(yōu)解之間的差別已經(jīng)趨于穩(wěn)定或縮小到一個(gè)較小的范圍內(nèi)（4）系統(tǒng)出現(xiàn)了無法解決的異常情況或技術(shù)問題7.3遺傳算法的實(shí)現(xiàn)過程scikit-opt（簡(jiǎn)稱sko）為用戶提供了一個(gè)靈活的框架，以應(yīng)用于各種優(yōu)化問題。其中，GA類和GA_TSP類是特別用于解決優(yōu)化問題的兩個(gè)關(guān)鍵類，它們分別針對(duì)一般優(yōu)化問題和旅行商問題（TSP）進(jìn)行了專門的優(yōu)化處理。通過靈活的配置和自定義選項(xiàng)，用戶可以針對(duì)特定問題調(diào)整算法行為，以期獲得更好的優(yōu)化結(jié)果。7.4遺傳算法的應(yīng)用使用scikit-opt庫求解函數(shù)極值Schaffer函數(shù)F2，是一種多維優(yōu)化測(cè)試函數(shù)，由Dr.Schaffer于1984年提出。該函數(shù)表達(dá)式相對(duì)簡(jiǎn)單，但其優(yōu)化過程卻極具挑戰(zhàn)性，常用于檢驗(yàn)優(yōu)化算法的局部搜索能力和全局搜索能力。函數(shù)公式如下所示：注意：案例代碼實(shí)現(xiàn)基于sko庫的GA模塊，GA模塊默認(rèn)使用二進(jìn)制編碼，選擇方法采用輪盤賭選擇。7.4遺傳算法的應(yīng)用遺傳算法的常用設(shè)置參數(shù)種群大小（PopulationSize）交叉率（CrossoverRate）變異率（MutationRate）選擇方法（SelectionMethod）停止準(zhǔn)則（TerminationCriterion）編碼方式（Encoding）其他參數(shù)7.4遺傳算法的應(yīng)用群智能算法的概念群體智能（Swarmintelligence，SI）是分散的、自組織的自然或人工系統(tǒng)的集體行為。這個(gè)概念是由GerardoBeni和Wang于1989年在細(xì)胞機(jī)器人系統(tǒng)的背景下引入的。群智能算法模擬自然界中生物群體行為來解決復(fù)雜優(yōu)化問題，自然界中的螞蟻群落、魚群、鳥群、陸地動(dòng)物等群體由眾多簡(jiǎn)單個(gè)體組成，群體中的個(gè)體通過與環(huán)境之間的相互作用和相互之間直接或間接的通信方式，實(shí)現(xiàn)復(fù)雜的尋路、覓食等群體行為。7.5群智能算法生物界的群體行為：蟻群尋路鳥群覓食魚群覓食7.5群智能算法自1992年Dorigo受螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為啟發(fā)，提出了蟻群優(yōu)化(AntColonyOptimization，ACO)理論，之后群體智能作為一個(gè)研究熱點(diǎn)吸引了大量研究者。陸續(xù)提出了幾十種群智能算法，一些典型的算法列舉如下：蟻群優(yōu)化算法（AntColonyOptimization，ACO，1992）粒子群優(yōu)化算法（ParticleSwarmOptimization，PSO，1995）人工蜂群算法（ArtificialBeeColony，ABC，2007）布谷鳥搜索算法（CuckooSearch，CS，2009）螢火蟲算法（FireflyAlgorithm，F(xiàn)A，2009）蝙蝠算法（BatAlgorithm，BA，2010）灰狼優(yōu)化算法（GreyWolfOptimizer，GWO，2012）鯨魚優(yōu)化算法（WhaleOptimizationAlgorithm，WOA，2016）7.5群智能算法群智能算法的應(yīng)用領(lǐng)域：優(yōu)化問題（OptimizationProblems）群體智能算法廣泛用于解決工程、物流、金融和電信等不同領(lǐng)域的優(yōu)化問題。機(jī)器人與自動(dòng)化（RoboticsandAutomation）群體智能技術(shù)越來越多地應(yīng)用于機(jī)器人技術(shù)和自動(dòng)化，協(xié)調(diào)自主代理和多機(jī)器人系統(tǒng)的行為。數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)（DataMiningandMachineLearning）群體智能算法用于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)應(yīng)用，用于特征選擇、聚類、分類和異常檢測(cè)任務(wù)。電信與網(wǎng)絡(luò)（TelecommunicationsandNetworking）群體智能技術(shù)用于電信和網(wǎng)絡(luò)優(yōu)化資源分配路由和負(fù)載平衡任務(wù)，其它新興應(yīng)用（OtherEmergingApplications）群體智能越來越多地應(yīng)用于農(nóng)業(yè)科技、醫(yī)療保健、環(huán)境監(jiān)測(cè)和智慧城市等新興領(lǐng)域。7.5群智能算法蟻群算法簡(jiǎn)介：蟻群路徑選擇示意圖，圖中F表示食物源(Food)，N表示巢穴(Nest)7.5群智能算法螞蟻出巢覓食時(shí)，尋路路徑是隨機(jī)的。螞蟻在尋路過程中，會(huì)在沿途釋放出一種叫做信息素（pheromone）的物質(zhì)。經(jīng)過該路徑的其它螞蟻能感知到釋放的信息素，路徑上的信息素濃度會(huì)隨著時(shí)間的流逝而降低。不同路徑中，長(zhǎng)度較短的路徑上單位時(shí)間內(nèi)往返的螞蟻數(shù)目更多，釋放的信息素濃度也更高。其它螞蟻出巢時(shí)會(huì)傾向于選擇信息素濃度更高的路徑。經(jīng)過一段時(shí)間長(zhǎng)度較短的路徑上螞蟻越來越多，信息素越來越濃，形成正反饋機(jī)制。另外一條長(zhǎng)度較長(zhǎng)的路徑上信息素越來越淡，螞蟻越來越少。蟻群算法簡(jiǎn)介：7.5群智能算法蟻群算法流程圖7.5群智能算法蟻群算法的應(yīng)用：蟻群算法可以有效地解決旅行商問題、圖著色問題、網(wǎng)絡(luò)路由問題、車輛路徑問題、分配問題等全局尋優(yōu)問題。這些問題在高維度空間求解時(shí)，使用遍歷搜索方法需要耗費(fèi)巨大的計(jì)算時(shí)間，傳統(tǒng)的窮舉算法難以甚至無法求解。旅行商問題圖著色問題7.5群智能算法蟻群算法的應(yīng)用：

7.5群智能算法粒子群算法的基本原理：

粒子群算法模擬鳥群覓食，初始時(shí)在搜索空間中隨機(jī)生成一群粒子的位置參數(shù)，將位置參數(shù)代入需要求解的函數(shù)獲取個(gè)體函數(shù)值，在這些函數(shù)值里找出群體最優(yōu)解。每個(gè)粒子還有一個(gè)初始時(shí)隨機(jī)生成的速度值決定它們下一步的方向和距離。每個(gè)粒子由當(dāng)前速度、當(dāng)前位置、個(gè)體歷史最優(yōu)位置和群體最優(yōu)位置等數(shù)據(jù)以及更新公式來獲取新的速度和位置，在新的位置中找出新的群體最優(yōu)解，重復(fù)迭代執(zhí)行上述步驟。圖參考：Intuitionofparticleswarmoptimization()個(gè)體當(dāng)前位置個(gè)體當(dāng)前速度個(gè)體歷史最優(yōu)位置群體最優(yōu)位置個(gè)體歷史最優(yōu)位置7.6粒子群算法及應(yīng)用基本粒子群算法公式

KennedyEberhart1995年7.6粒子群算法及應(yīng)用基本粒子群算法公式

7.6粒子群算法及應(yīng)用

粒子群算法公式圖解（2維函數(shù)求最小值）

7.6粒子群算法及應(yīng)用

粒子群算法公式圖解（2維函數(shù)求最小值）

7.6粒子群算法及應(yīng)用標(biāo)準(zhǔn)粒子群算法公式

粒子群算法公式的改進(jìn)7.6粒子群算法及應(yīng)用

粒子群算法公式的改進(jìn)7.6粒子群算法及應(yīng)用粒子群算法各參數(shù)權(quán)重影響1.?粒子數(shù)量（Number?of?Particles）

粒子數(shù)量影響算法的搜索范圍和搜索速度。一般來說，粒子數(shù)量越多，搜索范圍越廣，越能快速找到全局最優(yōu)解，但同時(shí)也會(huì)增加算法的計(jì)算復(fù)雜度。2.?迭代次數(shù)（Number?of?Iterations）

迭代次數(shù)影響算法的搜索精度和計(jì)算時(shí)間。一般來說，迭代次數(shù)越多，算法收斂的可能性越大，但同時(shí)也會(huì)增加計(jì)算時(shí)間。在高維度空間中，落入局部最優(yōu)解后，迭代次數(shù)的增加并不一定能夠脫離局部最優(yōu)解，因此增加迭代次數(shù)并不一定能夠收斂得到全局最優(yōu)解。7.6粒子群算法及應(yīng)用粒子群算法各參數(shù)權(quán)重影響3.?慣性權(quán)重ω

速度的慣性權(quán)重ω作用是平衡粒子的歷史速度和當(dāng)前速度對(duì)位置更新的影響。較大的權(quán)重值能夠增加粒子的探索能力，但可能導(dǎo)致粒子在搜索空間中震蕩，增加收斂時(shí)間；較小的權(quán)重值能夠增加粒子的局部搜索能力，加快收斂速度，但可能導(dǎo)致陷入局部最優(yōu)解。