智能優(yōu)化理論- 課件 第10、11章 粒子群優(yōu)化算法、混合蛙跳算法

第10章粒子群優(yōu)化算法contents目錄粒子群優(yōu)化算法的基本原理基本粒子群優(yōu)化算法改進的PSO算法離散粒子群優(yōu)化算法粒子群優(yōu)化算法應(yīng)用舉例粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題復(fù)習思考題粒子群優(yōu)化算法的基本原理01粒子群優(yōu)化算法(PSO)是通過觀察鳥群捕食行為啟發(fā)而來。在搜索空間中，每個優(yōu)化問題的解被視為一只鳥，即“粒子”。初始化一群粒子，每個粒子都是可行解，并由目標函數(shù)評價其適應(yīng)度值。粒子群優(yōu)化算法的基本原理03設(shè)每個優(yōu)化問題的解是搜索空間的一只鳥，把鳥視為空間中的一個沒有重量和體積的理想化的“質(zhì)點”，稱為粒子。01每個粒子都在解空間中運動，并由一個速度決定其飛行方向和距離。02粒子追隨當前的最優(yōu)粒子在解空間中進行搜索，每一次迭代都跟蹤兩個“極值”來更新自己。粒子群優(yōu)化算法的基本原理010203每個粒子都有一個由被優(yōu)化函數(shù)所決定的適應(yīng)度值，還有一個速度決定它們飛行方向和距離。粒子通過追隨當前的最優(yōu)粒子在解空間中搜索最優(yōu)解，需要性能評價和粒子之間進行全局或局部的信息交流。PSO算法通常具有3種基本的信息拓撲結(jié)構(gòu)：環(huán)形拓撲、星形拓撲、分簇拓撲。粒子群優(yōu)化算法的基本原理粒子群優(yōu)化算法的基本原理01在環(huán)形拓撲結(jié)構(gòu)中，任意一個粒子僅與其鄰域中的兩個粒子交流信息。02在星形拓撲結(jié)構(gòu)中，中心粒子與其他所有粒子之間具有雙向信息交流。其他也有諸如小世界的信息拓撲結(jié)構(gòu)等。03粒子群優(yōu)化算法的基本原理不同的信息拓撲結(jié)構(gòu)具有不同的鄰域定義，體現(xiàn)了不同效率的信息共享能力與社會組織協(xié)作機制。它通過鄰域規(guī)模、鄰域算子和鄰域中的迄今最優(yōu)解，影響PSO算法的性能?；玖Ｗ尤簝?yōu)化算法02基本粒子群優(yōu)化算法在n維連續(xù)搜索空間中，對粒子群中的第i個粒子或個體進行定義。n維位置向量表示該粒子或個體的當前位置；n維最優(yōu)位置向量表示該粒子或個體迄今所獲得的具有最優(yōu)適應(yīng)度值的位置；n維速度向量表示該粒子或個體的搜索方向。PSO算法中的m個粒子一直在并行地進行搜索運動。每個粒子可認為是一個在搜索空間中飛行的智能體。在每次迭代中，該算法記錄下每個粒子的迄今最優(yōu)位置，并相互交流粒子之間的局部信息，進一步獲得整個粒子群或鄰域的迄今最優(yōu)位置。問題歸結(jié)為每個粒子在n維連續(xù)解空間中如何從一個位置運動到下一個位置。而這可通過將簡單地加上得到。群體中所有粒子所經(jīng)歷過的最優(yōu)位置稱為全局最優(yōu)位置?；玖Ｗ尤簝?yōu)化算法123若令（單位時間），則有以下位置更新公式為這里，對第i個粒子，在計算出后，應(yīng)對其進行評價，即須計算出相應(yīng)的適應(yīng)度值。PSO算法在根據(jù)上式計算之前，須先確定出，而這可由PSO算法中的速度更新公式給出?；玖Ｗ尤簝?yōu)化算法01基本PSO算法的實現(xiàn)步驟如下02步驟1：初始化。設(shè)定PSO算法中涉及的各類參數(shù)，包括搜索空間的下限Le和上限He，加速度因子和，算法的最大迭代次數(shù)Tmax?；蚴諗烤龋Ｗ铀俣确秶鶾vmin，vmax]。03隨機初始化搜索點的位置xi和速度vi，設(shè)每個粒子的當前位置為pi，從個體找到的最優(yōu)解中找出種群最優(yōu)解，記錄對應(yīng)于最優(yōu)解的粒子的序號g和其位置pg?；玖Ｗ尤簝?yōu)化算法評價每一個粒子。計算每個粒子的適應(yīng)值，如果該適應(yīng)值優(yōu)于該粒子當前的個體最優(yōu)值，則將pi設(shè)置為該粒子的位置，同時更新個體最優(yōu)值。更新粒子狀態(tài)。根據(jù)式對每一個粒子的速度和位置進行更新。如果則將其置為；如果，則將其置為?；玖Ｗ尤簝?yōu)化算法步驟3步驟2改進的PSO算法03在PSO算法的迭代過程中，速度值有可能變得非常大，導(dǎo)致性能降低。為了控制速度的增加，通常可采取兩個措施：一是通過增加慣性權(quán)重，二是加入收縮系數(shù)。具有慣性權(quán)重的PSO算法通過增加慣性權(quán)重可以增強算法的全局搜索能力，并通過減小慣性權(quán)重提高局部搜索能力。010203具有速度控制的改進型PSO算法具有速度控制的改進型PSO算法選擇一個合適的慣性權(quán)重有助于PSO算法均衡它的探索能力和開發(fā)能力。在迭代過程中，初始時取較大的值，比如0.9-1.2之間的值，以擴大算法的全局搜索能力。隨著迭代的進行呈線性遞減，以加強迭代后期的局部搜索性能，能夠使算法精確得到全局最優(yōu)解。引入慣性權(quán)重可以消除基本PSO算法對vmax的依賴，并平衡全局和局部搜索能力。隨著時間收斂，粒子的振蕩軌跡幅度會隨時間不斷減少。具有速度控制的改進型PSO算法PSO算法的粒子群規(guī)模或粒子數(shù)m的選擇，需要折中求解質(zhì)量與計算量之間。避免PSO算法的早熟，可增加粒子群的規(guī)模，但也會降低搜索速度。將基本PSO算法中的整個粒子群的迄今最優(yōu)解擴展為考慮粒子鄰域的迄今最優(yōu)解。具有鄰域算子的PSO算法鄰域大小實際描述了信息共享或社會相互作用的范圍，也給出了通信的代價。采用全鄰域似乎更好，因其算法性能與基于環(huán)形拓撲結(jié)構(gòu)的PSO算法相差不大。PSO算法有全局版本和局部版本。全局版本每個粒子的鄰域包含所有個體，而局部版本僅包含與該粒子有直接信息連接的部分個體。具有鄰域算子的PSO算法具有鄰域算子的PSO算法010203全局版本PSO算法收斂速度較快，但是容易陷入局部最優(yōu)，而采用不同的鄰域拓撲結(jié)構(gòu)的局部版本PSO算法更容易找到全局最優(yōu)或次優(yōu)解。如果信息在粒子之間傳遞得太快，則很容易使整個系統(tǒng)出現(xiàn)早熟，即粒子很快聚集到一個局部極值點上；反之，如果信息傳遞得太慢，則因為單個粒子很難迅速得到相距較遠的粒子的信息，使得算法的收斂速度變慢，從而影響計算效率。常見的鄰域結(jié)構(gòu)有星形結(jié)構(gòu)、環(huán)形結(jié)構(gòu)、金字塔結(jié)構(gòu)以及馮·諾依曼結(jié)構(gòu)，如圖10.2所示。星形結(jié)構(gòu)以其中一個粒子為中心，與鄰域中的其他所有粒子相聯(lián)系，而其他粒子不進行信息交換。星形結(jié)構(gòu)在環(huán)形結(jié)構(gòu)中所有粒子排成一個環(huán)，該結(jié)構(gòu)中每個粒子與其相鄰的兩個粒子交換信息，從而有效地保證了種群的多樣性。環(huán)形結(jié)構(gòu)具有鄰域算子的PSO算法離散粒子群優(yōu)化算法04PSO算法在求解離散變量優(yōu)化問題上形成了兩條完全不同的技術(shù)路線。一是以經(jīng)典的連續(xù)型PSO算法為基礎(chǔ)，將離散問題空間映射到連續(xù)粒子運動空間，并適當修改PSO算法來求解。二是針對離散優(yōu)化問題，以PSO算法信息更新的本質(zhì)機理為基礎(chǔ)，重新定義特有的粒子群離散表示方式與操作算子來求解。在計算上，以離散空間特有的、對向量的位操作來取代傳統(tǒng)向量計算；從信息流動機制上看，仍保留了PSO算法特有的信息交換和流動機制。區(qū)別在于前者將實際離散問題映射到粒子連續(xù)運動空間后，在連續(xù)空間中計算和求解；后者則是將PSO算法映射到離散空間，在離散空間中計算和求解。0102030405PSO算法的離散化方法現(xiàn)有文獻對基于連續(xù)空間的DPSO算法的研究居多，形成了針對0-1規(guī)劃問題的二進制PSO算法（BinaryPSO，BPSO），并建立了不同于傳統(tǒng)PSO算法的新計算模式。針對排序組合優(yōu)化問題，在傳統(tǒng)PSO算法上增加一些離散化策略是當前研究常采用的方法。在BPSO算法中，粒子位置的每一維被限制為1或者0，而對速度則不作這種限制。使用速度更新位置時，值越大，粒子的位置越有可能選1，值越小則越接近0。基于連續(xù)空間的DPSO算法速度更新公式在形式上保持不變，即其中定義在二進制問題空間中的第i個粒子的第j位(bit)以及相應(yīng)的、取值為1或0。每個粒子均對應(yīng)一個長度為n的二進制串，如同遺傳算法一樣，它表示了問題的一個解。粒子的當前速度分量被定義為二進制位取值為1或0的概率，因此必須將概率限制在[0，1]之間。基于連續(xù)空間的DPSO算法BPSO算法的粒子狀態(tài)更新公式為：式中，Sigmoid函數(shù)可以保證向量的每個分量都在區(qū)間[0，1]內(nèi)；rand()為滿足[0，1]之間均勻分布的隨機數(shù)。試驗結(jié)果表明，對于大多數(shù)測試函數(shù)，BPSO算法都比遺傳算法速度快，尤其是在問題的維數(shù)增加時。為此，該算法引入了Sigmoid函數(shù)進行變換。基于連續(xù)空間的DPSO算法用基于連續(xù)空間的DPSO算法求解離散問題時，算法生成的連續(xù)解與整數(shù)規(guī)劃問題的目標函數(shù)評價值之間存在多對一的映射。因此該目標函數(shù)不能完全反映PSO算法中連續(xù)解的質(zhì)量。BPSO算法并不直接優(yōu)化二進制變量本身，而是通過優(yōu)化連續(xù)變化的二進制變量為1的概率，達到間接優(yōu)化離散變量的目的。基于連續(xù)空間的DPSO算法基于連續(xù)空間的DPSO算法整數(shù)規(guī)劃問題的連續(xù)化導(dǎo)致大量冗余解空間與冗余搜索，從而影響了算法的收斂速度。由于連續(xù)空間里的向量計算十分簡單，消耗時間短，因此基于連續(xù)空間的DPSO算法仍能保持較快的運算速度。目前關(guān)于基于離散空間的DPSO算法的研究還比較少。研究者們往往根據(jù)具體問題構(gòu)建相應(yīng)的粒子表達方式，并通過重新定義粒子優(yōu)化算法中的加減法和乘法運算規(guī)則來求解。Clerc針對旅行商問題提出的TSP-DPSO算法和Farzaneh針對0-1規(guī)劃問題提出的離散二進制PSO算法（記為B-PSO）。010203基于離散空間的DPSO算法Clerc重新定義了PSO算法中的“加減法”操作和“乘法”操作，實現(xiàn)了PSO算法向離散空間的映射。重新定義后的粒子狀態(tài)更新公式為：，其中，表示粒子的位置和速度，表示因子和為隨機生成的與位置同維度的向量，向量間的“加減法”定義為對二進制位的“異或”操作，記為，向量間“乘法”定義為對二進制位的“與”操作，記為。基于離散空間的DPSO算法基于離散空間的DPSO算法030201B-PSO算法借鑒免疫機制以避免算法陷入局部最優(yōu)，從其試驗結(jié)果來看，B-PSO算法的效率高于BPSO算法和遺傳算法。B-PSO算法中的粒子速度是與位置同維的二進制向量，粒子的更新計算在離散空間中進行，這與連續(xù)空間的BPSO算法完全不同。基于離散空間的DPSO算法采用了位操作，雖可能增加單步計算代價，但不存在冗余搜索問題，且對離散問題表達自然，易與其他進化算法結(jié)合。混合PSO算法將PSO算法的基本思想與各種進化計算方法相結(jié)合，發(fā)展各種混合PSO算法，已成為目前的研究熱點之一。PSO算法的最大優(yōu)點是實現(xiàn)簡單，全局搜索能力強，應(yīng)用廣泛。在PSO算法的粒子群中引入遺傳算法中的自然選擇原理，又如與人工免疫算法結(jié)合的免疫PSO算法等。還有與量子計算、混沌方法、耗散結(jié)構(gòu)等相結(jié)合的方法，也層出不窮?；陔x散空間的DPSO算法粒子群優(yōu)化算法應(yīng)用舉例05010405060302Schwefel函數(shù)的全局最大值為，當n=2時，取得該值。利用PSO算法計算Schwefel函數(shù)的近似全局最優(yōu)解。參數(shù)選擇：粒子個數(shù)n=40，學(xué)習率=，慣性權(quán)重的初始值為1.0，隨迭代次數(shù)線性遞減。搜索過程如圖10.4所示。平均適應(yīng)度值曲線如圖10.5所示。搜索結(jié)果如表10.1所示。粒子群優(yōu)化算法應(yīng)用舉例粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題06010203以社會交互為基礎(chǔ)的群體智能具有巨大的價值創(chuàng)造能力，特別是在復(fù)雜問題的優(yōu)化領(lǐng)域。粒子群優(yōu)化算法應(yīng)用的優(yōu)勢主要體現(xiàn)在非導(dǎo)數(shù)型優(yōu)化、魯棒性、協(xié)作行為和靈活性方面。該算法不需要依賴于目標函數(shù)的導(dǎo)數(shù)信息，而是通過個體之間的社會交互機制尋找最優(yōu)解。粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題搜索過程陷入局部最優(yōu)值的可能性大大降低，并且基于群體的PSO算法更不容易受到個體失誤的影響。02粒子群優(yōu)化算法最大的優(yōu)勢是它可以工作于動態(tài)環(huán)境中，并且對于GbestPSO算法，粒子最終收斂于全局最佳與個體最佳位置連線上的一點。03增加慣性的權(quán)重，將會增加粒子的速度而導(dǎo)致更多的全局搜索和更少的局部搜索，反之亦然。01調(diào)整適當?shù)膽T性權(quán)值并不是一個簡單的任務(wù)，它與問題相關(guān)。粒子群優(yōu)化算法還缺少堅實的數(shù)學(xué)分析基礎(chǔ)，尤其缺少算法收斂條件和參數(shù)調(diào)整的通用方法學(xué)。粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題復(fù)習思考題070102基本粒子群算法包括初始化粒子群、定義適應(yīng)度函數(shù)、進行迭代搜索、評估搜索結(jié)果等步驟。改進的粒子群算法在基本…引入慣性權(quán)重、增加學(xué)習因子、引入非支配策略等。粒子群算法具有很多優(yōu)點…簡單易行、魯棒性強、適用于各種優(yōu)化問題等。缺點包括可能存在局部最優(yōu)解、對初值敏感、難以處理大規(guī)模搜索空間等。針對其缺點，可以采取一…增加搜索范圍、引入隨機噪聲、采用多線程等。030405復(fù)習思考題THANKYOU感謝觀看第11章混合蛙跳算法目錄contents混合蛙跳算法的提出混合蛙跳算法的基本原理基本混合蛙跳算法的描述混合蛙跳算法的實現(xiàn)步驟協(xié)同進化混合蛙跳算法復(fù)習思考題混合蛙跳算法的提出01混合蛙跳算法是2001年由美國學(xué)者Eusuff和Lansey等為解決水資源網(wǎng)絡(luò)管徑優(yōu)化設(shè)計問題而提出的一種群智能優(yōu)化算法。2003年和2006年對此算法又做了詳細的說明。混合蛙跳算法基于文化算法框架，根據(jù)青蛙群體中個體在覓食過程中交流文化基因來構(gòu)建算法模型。采用類似粒子群優(yōu)化算法的個體進化的局部搜索和混合操作的全局搜索策略。在算法中，虛擬青蛙是文化基因的宿主并作為算法最基本的單位。這些文化基因由最基本的文化特征組成。SFLA具有思想簡單、尋優(yōu)能力強、實驗參數(shù)少、計算速度快等特點，已被用于成品油管網(wǎng)優(yōu)化、函數(shù)優(yōu)化、生產(chǎn)調(diào)度等領(lǐng)域?；旌贤芴惴ǖ奶岢龌旌贤芴惴ǖ幕驹?2混合蛙跳算法模擬了青蛙在沼澤中跳躍尋找食物的行為，通過將種群均勻分為若干族群，并使用類似粒子群算法的進化策略進行獨立進化。在每個文化基因體內(nèi)，青蛙們能被其他青蛙的文化基因感染，進而發(fā)生文化進化。算法使用三角概率分布來選擇部分青蛙進行進化，保證適應(yīng)度較好的青蛙產(chǎn)生新文化基因的貢獻比較差的青蛙大。混合蛙跳算法的基本原理

混合蛙跳算法的基本原理在進化過程中，青蛙們可以使用文化基因體中最佳和種群最佳的青蛙信息改變文化基因。青蛙每一次跳躍的步長作為文化基因的增量，而跳躍達到的新位置作為新文化基因。這個新文化基因產(chǎn)生后就隨即用于下一步傳承進化。達到預(yù)先定義的局部搜索（傳承進化）迭代步數(shù)后，這些文化基因體被混合，重新確定種群中的最佳青蛙，并產(chǎn)生新的文化基因族群。混合蛙跳算法將隨機性和確定性相結(jié)合，隨機性保證搜索的靈活性和魯棒性，而確定性則允許算法積極有效地使用響應(yīng)信息來指導(dǎo)啟發(fā)式搜索。混合蛙跳算法全局信息交換和局部深度搜索的平衡策略使得算法具有避免過早陷入局部極值點的能力，從而指引算法搜索過程向著全局最優(yōu)點的方向進行搜索?；旌贤芴惴ǖ幕驹砘净旌贤芴惴ǖ拿枋?3混合蛙跳算法將每只青蛙視為優(yōu)化問題的可行解。初始時，隨機生成一個覆蓋整個沼澤地（解空間，可行域）的青蛙種群（蛙群）。把整個蛙群按照某種具體原則（如均分原則）劃分成多個相互獨立排序的族群（子種群）。每個族群具有不同文化基因體，因此被稱為文化基因體或模因組。01020304蛙群、族群及其初始化選取族群的數(shù)量為m，每個族群中青蛙數(shù)量為n。蛙群中總的青蛙數(shù)為選取族群的數(shù)量為m設(shè)在可行域中有青蛙X1，X2，…，XS，其中d為決策變量數(shù)(每只青蛙基因所含的特征數(shù)）。第i只青蛙用決策變量表示為。設(shè)在可行域中有青蛙X0102每只青蛙用適應(yīng)度為適應(yīng)度可以作為評估青蛙健康狀況的重要指標，幫助判斷青蛙是否適合進行繁殖或作為其他用途。每只青蛙都有一定的適應(yīng)度，適應(yīng)度越高，表示它越能適應(yīng)各種環(huán)境。個體青蛙被看作元信息的載體個體青蛙被看作元信息的載體，每個元信息包含多個信息元素。這與遺傳算法中基因和染色體的概念相類似。010204族群劃分將青蛙種群F中的青蛙平均分到m族群中，每個包含n只青蛙。這些族群可以朝著不同的搜索方向獨立進化。根據(jù)具體的執(zhí)行策略，族群中的青蛙在解空間中進行局部搜索。元信息在局部個體之間進行傳播，這就是元進化過程。03子族群是預(yù)防算法陷于局部最優(yōu)值的，由按照適應(yīng)度進行選擇后產(chǎn)生的青蛙所構(gòu)成。族群中的青蛙具有的適應(yīng)度越好，則被選中進入子族群的概率就越大。子族群代替族群在解空間進行局部搜索，每次完成子族群內(nèi)的局部搜索，族群內(nèi)的青蛙就需要按照適應(yīng)度的大小進行重新排序，并重新生成子族群。構(gòu)建子族群01選取族群中的青蛙進入子族群是通過三角概率分布公式完成的，即文化基因體中適應(yīng)度最好的青蛙有最高的被選中的概率，而適應(yīng)度最差的青蛙有最低的被選中的概率。02選擇過程是隨機的，這樣就保證選出的q(q<n)只青蛙能全面反映該文化基因體中青蛙的適應(yīng)度分布。03將選出的q只青蛙組成子文化基因體Z，并將其中青蛙按照適應(yīng)度遞減的順序排序。分別記錄適應(yīng)度最好的青蛙(iq=l)為最差的青蛙(iq=q)。構(gòu)建子族群計算子文化基因體中適應(yīng)度最差青蛙的跳躍步長為，其中r為[0，1]之間的隨機數(shù)；青蛙的新位置的計算公式為：若更新的最差青蛙位置不能產(chǎn)生較好的結(jié)果，則需要再次更新最差青蛙位置，并需要計算跳躍步長為；青蛙位置的更新和分別為子文化基因體中對應(yīng)于青蛙最好位置和最差位置；為青蛙被感染之后最大跳躍步長。其中，為青蛙的全局最好位置。更新最差膏蛙位置的計算仍采用青蛙新位置的計算公式。算法參數(shù)01混合蛙跳算法的計算包括一些參數(shù)，如S、m、n、、SF、LS等。02S代表種群中青蛙的數(shù)量，m代表族群數(shù)量，n代表族群中青蛙數(shù)量。代表全局最好解，代表局部最好解，代表局部最差解。03123S的值一般和問題的復(fù)雜性相關(guān)，樣本容量越大，算法找到或接近全局最優(yōu)的概率也就越大。對于族群數(shù)量m的選擇，要確保子族群中青蛙數(shù)量不能太小。如果m太小，則局部進行進化搜索的優(yōu)點就會丟失。n為子族群中青蛙的數(shù)量，引入該參數(shù)的目的是為了保證青蛙族群的多樣性，同時也是為了防止陷入局部最優(yōu)解。算法參數(shù)LS為局部迭代進化次數(shù)，它的選擇也要大小適中。如果太小，會使得青蛙子族群頻繁地跳躍，減少了信息之間的交流，失去了局部深度搜索的意義，算法的求解精度和收斂速度就會變差；相反，雖然可以保證算法的收斂性能，但是進行一次全局信息交換的時間過長，而導(dǎo)致算法的計算效率下降。為最大允許跳動步長，它可以控制算法進行全局搜索的能力。如果太小，會減少算法全局搜索的能力，使得算法容易陷入局部搜索；如果太大，又很可能使得算法錯過真正的最優(yōu)解。SF為全局思想交流次數(shù)。SF的大小一般也和問題的規(guī)模相關(guān)，問題規(guī)模越大，其值相應(yīng)也越大。算法參數(shù)算法停止條件SFLA可以采用可定義的迭代次數(shù)來控制算法停止，確保在一定次數(shù)后結(jié)束循環(huán)搜索。算法也會在至少有一只青蛙達到最佳位置時停止，以避免浪費過多時間和精力。在最近的K次全局信息交流過程之后，如果全局最好解沒有得到明顯改進，則算法也將退出整個循環(huán)搜索過程?；旌贤芴惴ǖ膶崿F(xiàn)步驟04全局搜索過程青蛙種群初始化，設(shè)置SFLA參數(shù)，包括青蛙群體總數(shù)S、族群數(shù)量m、每個族群的青蛙數(shù)n、最大迭代次數(shù)N、最大、最小步長ΔXmax、ΔXmin。青蛙分類，隨機生成S只青蛙并計算各個蛙的適應(yīng)值，按適應(yīng)值大小進行降序排序并記錄最好解Xg，記錄S中適應(yīng)度最好的青蛙位置Xg為F(X1)。將蛙群分成多個族群，把S個蛙分配到m個族群中去，每個族群包含n個蛙。按式劃分族群（文化基因體）。Fk(j)表示第k族群中第j蛙所處的位置，fk(j)表示第k族群中第j蛙的適應(yīng)度值。每個族群執(zhí)行族群局部搜索，即文化基因體傳承進化。每個文化基因體根據(jù)局部搜索步驟獨立進化。將各個族群進行混合，即將各文化基因體進行混合。在每個文化基因體都進行過一輪局部搜索之后，將重新組合種群S，并再次根據(jù)適應(yīng)度遞減排序，更新種群中最優(yōu)青蛙，并記錄全局最優(yōu)青蛙的位置Xg。檢驗停止條件，若滿足了算法收斂條件，則停止算法執(zhí)行過程；否則，轉(zhuǎn)到步驟(2)。全局搜索過程局部搜索過程是對上面全局搜索過程中步驟(4)的進一步展開，具體過程包括定義計算器、選取q只青蛙構(gòu)成子族群、改善子群中最差青蛙的位置、計算跳躍步長等步驟。混合蛙跳算法是一種新型的后啟發(fā)式群體智能進化算法，它通過模擬現(xiàn)實自然環(huán)境中青蛙群體在覓食過程中所體現(xiàn)的信息交互和協(xié)同合作行為，來完成對問題的求解過程。采用模因分組方法把種群分成若干個子種群，每個子種群稱為模因分組，種群中青蛙被定義為問題解。模因組中的每個青蛙都有努力靠近目標的想法，具有對食物源遠近的判斷能力，并隨著模因分組的進化而進化。在模因組的每一次進化過程中，找到組內(nèi)位置最差和最好的青蛙。組內(nèi)最差青蛙要按照一定更新策略來進行位置調(diào)整。0102030405局部搜索過程輸入標題02010403信息傳遞方式混合蛙跳算法通過種群分類實現(xiàn)信息傳遞，結(jié)合局部進化和重新混合過程，將全局信息交互和局部搜索相結(jié)合，具有很強的全局搜索能力。如此反復(fù)，直到定義的收斂條件結(jié)束為止。全局信息交換和局部深度搜索的平衡策略使得算法能夠跳出局部極值點，向全局最優(yōu)方向進行。局部搜索部分稱為文化基因體傳承進化過程。完成局部搜索后，將所有文化基因體內(nèi)的青蛙重新混合并排序和劃分文化基因體，再進行局部搜索?；旌贤芴惴鞒贪ㄈ炙阉髦鞒绦蛄鞒虉D和進入主程序流程圖中的局部搜索程序的流程圖。協(xié)同進化混合蛙跳算法05為了充分利用子群最優(yōu)個體和全局最優(yōu)個體的優(yōu)秀基因，深入搜索最優(yōu)青蛙附近空間以獲得更優(yōu)青蛙?？紤]到全組青蛙的更新現(xiàn)狀對下一步進化具有重要的影響，組內(nèi)最優(yōu)個體代表了組內(nèi)青蛙所處的最好位置，對整個子群起到重要的引領(lǐng)作用。傳統(tǒng)混合蛙跳算法只對子群內(nèi)最差青蛙個體Pw進行更新，導(dǎo)致搜索區(qū)域受限，進化后期種群多樣性下降，易陷入局部最優(yōu)。局部位置更新算子組內(nèi)所有青蛙的平均值在一定程度上反映了子群的整體水平。因此，對傳統(tǒng)混合蛙跳算法的組內(nèi)更新策略進行了重新設(shè)計。從最優(yōu)青蛙位置出發(fā)，利用最優(yōu)青蛙與最差青蛙以及組內(nèi)所有青蛙的平均值與最差青蛙的隨機差值為步長基數(shù)，調(diào)整更新步長，最后采用隨機雙向的更新方式。雙向隨機查找更優(yōu)青蛙，以此擴大解空間的搜索范圍，從而提高了局部搜索的效率。局部位置更新算子VS在進行組內(nèi)搜索時，首先計算組內(nèi)青蛙的平均值Pa。對子群內(nèi)最差青蛙的更新策略進行改進，定義如下：其中r代表[0,1]內(nèi)的隨機數(shù)。根據(jù)子群最優(yōu)個體Pb對Pw進行更新操作，若所得出的新個體Pn優(yōu)于子群內(nèi)最差青蛙個體Pw，則對其進行取代；若得出的結(jié)果沒有改進，那么用種群的最優(yōu)個體Pg代替Pb，代入式重新進行更新操作，若優(yōu)于Pw則用新個體取代Pw；否則雙向隨機生成一個新個體取代Pw。局部位置更新算子啟發(fā)于人類社會不同群體間可以交互學(xué)習的特點，利用生物學(xué)原理，個體與其近鄰?fù)橹g進行頻繁的信息交互，可以擴大個體的感知范圍，提高個體感知信息的速度和準確率。成員間的信息交互有利于個體進化。在算法進行局部搜索時，對子群內(nèi)較差的青蛙個體采取交互學(xué)習策略進行更新，對子群內(nèi)部少量適應(yīng)值較差的青蛙個體，利用全局最優(yōu)個體Pg與所在子群的最優(yōu)個體Pb之間的隨機點為起點，以保持當前迭代全局最優(yōu)個體以及所在子群的優(yōu)秀基因。每一只較差青蛙個體向鄰近子群的最優(yōu)個體進行交互學(xué)習，獲取其他子群的優(yōu)質(zhì)元素，整體提升整個種群的質(zhì)量。通過此交互學(xué)習策略產(chǎn)生的新個體，若優(yōu)于原個體則對其進行取代，否則保持不變。010203交互學(xué)習策略定義式如下：Po代表新位置的隨機起點，r代表[0,1]內(nèi)的隨機數(shù)；rand(-1,1)代表[-1,1]內(nèi)的隨機數(shù)；Pmi為第m個子群內(nèi)第i個向鄰近子群最優(yōu)個體進行交互學(xué)習的較差青蛙；和為鄰近子群的最優(yōu)個體。對于第一組（m＝1）子群選擇向其后兩組子群的最優(yōu)個體交互學(xué)習，最后一組子群向其前面兩組子群學(xué)習。交互學(xué)習策略使得青蛙個體學(xué)習的方向具有了多樣性，為算法擺脫局部最優(yōu)提供了新的額外動力。同時，可以減少算法尋優(yōu)過程的盲目性，加快算法的尋優(yōu)速度。交互學(xué)習策略針對目前蛙跳算法研究中忽視個體能動性，尤其是種群中精英群體的自主學(xué)習進化能力，提出了精英群自學(xué)習進化機制。在全局迭代中種群的多個精英個體組成單獨的精英群進行主動的自我學(xué)習和調(diào)整，在精英個體空間進行小鄰域精細搜索。自然界的生物不斷調(diào)整自身狀態(tài)來適應(yīng)環(huán)境。精英群自學(xué)習進化機制精英群自學(xué)習進化機制010203將搜索到的更優(yōu)解返回當前迭代種群，每一代個體都能比上一代個體更好地適應(yīng)環(huán)境，從而最終必然更加逼近最優(yōu)個體。精英群自學(xué)習進化機制的第1步是精英個體的選擇。根據(jù)多精英比單精英更能夠引導(dǎo)群體學(xué)習的社會現(xiàn)象，將個體按適應(yīng)值進行排序，選取當前種群最好的m個精英個體組成一個精英群。引入雙向隨機變異算子，通過對“精英”個體攜帶的信息進行多次多角度的隨機擾動變異操作進行自學(xué)習進化，保留精英個體的優(yōu)秀基因，在其周圍鄰域空間進行更深入的精細探索以產(chǎn)生更優(yōu)秀的新個體。通過在精英群空間多角度雙向隨機探索，使算法具備了一定的自主學(xué)習能力，有利于算法跳出局部最優(yōu)解的束縛進行全局搜索。精英自學(xué)習方程為：Pij是個體Pi第j維數(shù)；rand(-1,1)ij為對應(yīng)Pij的－１到１的隨機數(shù)