混合粒子群算法研究

混合粒子群算法研究1.1引言粒子群優(yōu)化算法是通過(guò)模擬自然界中鳥(niǎo)群覓食行為抽象出來(lái)的群智能優(yōu)化算法，現(xiàn)已被廣泛應(yīng)用到流水車間調(diào)度、路徑最優(yōu)化選取、神經(jīng)網(wǎng)絡(luò)治療等多個(gè)領(lǐng)域。本章結(jié)合實(shí)際應(yīng)用過(guò)程中的問(wèn)題及粒子群算法特點(diǎn)，提出一種混合粒子群算法。1.2標(biāo)準(zhǔn)粒子群算法標(biāo)準(zhǔn)粒子群算法是在1995年由R.Eberhart和J.Kennedy兩位研究學(xué)者提出來(lái)的，是一種群智能優(yōu)化算法，通過(guò)自然界中鳥(niǎo)群覓食行為抽象出來(lái)的優(yōu)化算法，它把實(shí)際問(wèn)題遍歷區(qū)域看成搜索空間，將鳥(niǎo)群中的個(gè)體看作單獨(dú)粒子，搜索空間中每個(gè)粒子均有自己的初始位置和初始速度，當(dāng)鳥(niǎo)群中發(fā)現(xiàn)有覓食食物時(shí)，搜索空間中的每一個(gè)粒子受自身和其他粒子影響，重新賦予位置及速度，以此類推，通過(guò)多次迭代搜索，直至找到目標(biāo)位置。粒子群算法是一種并行算法，其原理簡(jiǎn)單易懂，參數(shù)少，目前已經(jīng)用于最優(yōu)路徑選取、流水車間調(diào)度、神經(jīng)網(wǎng)絡(luò)治療等領(lǐng)域。1.2.1粒子群算法的數(shù)學(xué)模型由N個(gè)粒子組成的一個(gè)群體，在D維的搜素空間中，xi表示第i個(gè)粒子在搜索空間中的位置，所有的粒子的搜索空間中以一定速度在搜索空間中運(yùn)行。在每一次迭代更新后，粒子以自身速度與其他粒子對(duì)其本身的影響更新自己運(yùn)行的速度與新位置。通過(guò)評(píng)價(jià)函數(shù)評(píng)定每一個(gè)粒子迭代后的好快，保留粒子個(gè)體最優(yōu)解和全局最優(yōu)解。其速度及位置更新公式如下：1.2.2粒子群算法基本操作步驟標(biāo)準(zhǔn)粒子群算法處理優(yōu)化問(wèn)題操作步驟如下：步驟一：初始化粒子。在D維搜索空間中隨機(jī)初始化種群粒子N，并賦予每個(gè)粒子初始速度v。步驟二：適應(yīng)度函數(shù)評(píng)價(jià)機(jī)制。對(duì)搜索空間中每個(gè)粒子進(jìn)行適應(yīng)度評(píng)價(jià)機(jī)制，判斷粒子當(dāng)前最優(yōu)解位置。步驟三：迭代更新。通過(guò)迭代更新和適應(yīng)度函數(shù)判斷，更新每個(gè)粒子位置及迭代速度，更新當(dāng)前最優(yōu)位置及全局最優(yōu)位置。步驟四：找出最優(yōu)解。依據(jù)尋優(yōu)精度，判斷是否結(jié)束尋優(yōu)過(guò)程。如達(dá)到尋優(yōu)精度或迭代次數(shù)，符合條件，找到最優(yōu)解，結(jié)束尋優(yōu)算法；如沒(méi)有達(dá)到尋優(yōu)精度或迭代次數(shù)，返回步驟二，繼續(xù)驗(yàn)證適應(yīng)度函數(shù)，進(jìn)行迭代尋優(yōu)更新。適應(yīng)度函數(shù)一般為目標(biāo)函數(shù)，根據(jù)求解問(wèn)題的不同而不同，適應(yīng)度值越高，代表所得解越好，越接近目標(biāo)位置，一般使用f（x）代表適應(yīng)度函數(shù)。1.3混合粒子群算法PSO算法盡管具有原理簡(jiǎn)單、參數(shù)少、容易實(shí)現(xiàn)等諸多優(yōu)點(diǎn)，但是由于每次迭代更新需要通過(guò)自身認(rèn)知和社會(huì)其他粒子影響的共同作用下進(jìn)行的，進(jìn)而導(dǎo)致使粒子容易陷入局部最優(yōu)區(qū)域而找不到全局最優(yōu)解。本文對(duì)粒子群算法進(jìn)行如下改進(jìn)：添加局部搜索算法，提高算法搜索精度，動(dòng)態(tài)調(diào)節(jié)種群多樣性，從根源消除算法容易陷入局部極值的缺點(diǎn)。1.3.1局部搜索算法鑒于PSO算法搜索精度低，容易陷入局部極值等缺點(diǎn)，因此提高局部搜索精度、增強(qiáng)種群多樣性成為提高優(yōu)化算法得整體思路，在優(yōu)化算法中，慣性權(quán)重值得引入，使得算法在搜索初期對(duì)搜索空間中所有粒子進(jìn)行全局大范圍搜索，體現(xiàn)了智能算法得全局性，隨著更新迭代的進(jìn)行，逐步搜索到某一局部區(qū)域，算法只會(huì)在局部?jī)?nèi)進(jìn)行搜索，而無(wú)法跳出當(dāng)前局部搜索空間，這一現(xiàn)象被稱為陷入局部極值。在粒子迭代過(guò)程中，搜索空間中設(shè)定有多個(gè)局部極值，在PSO算法中，粒子更新會(huì)同時(shí)收到自身慣性及周圍粒子影響進(jìn)行搜索，進(jìn)而隨機(jī)性陷入某一個(gè)局部極值無(wú)法跳出。本文引入模擬退火機(jī)制，實(shí)現(xiàn)局部搜索的精確搜索，引入變異策略，增強(qiáng)種群多樣性，跳出局部最優(yōu)概率。1.3.2退火機(jī)制模擬退火機(jī)制可理解為三個(gè)階段：（1）加溫。假定固態(tài)物體內(nèi)部粒子原先處于不平衡狀態(tài)，當(dāng)把固態(tài)物體加熱，內(nèi)部粒子會(huì)因?yàn)闇囟鹊纳叨x相對(duì)穩(wěn)定的狀態(tài)，直到液化固態(tài)物體，內(nèi)部粒子打破原來(lái)狀態(tài)，達(dá)到相對(duì)均勻。（2）平衡。當(dāng)外界不再加熱，物體由于自身溫度高于外界溫度，將與外界進(jìn)行溫度置換，物體內(nèi)部粒子能量減少，當(dāng)物體與外界溫度一致時(shí)，此時(shí)物體內(nèi)部能量最少，系統(tǒng)達(dá)到平衡。（3）冷卻。當(dāng)進(jìn)一步將物體冷卻，系統(tǒng)內(nèi)能量進(jìn)一步減少，物體內(nèi)部粒子相對(duì)穩(wěn)定，系統(tǒng)達(dá)到穩(wěn)定。模擬退火算法具有很好的局部搜索能力，主要因?yàn)樗梢越邮鼙犬?dāng)前解更差的解，在模擬退火算法初期，隨著溫度的升高，算法不接受或小概率接受最優(yōu)解，逐漸到算法后期，隨著溫度降低，最優(yōu)解接受概率較高，可以容納比當(dāng)前最優(yōu)解較差的解，有利于算法跳出局部極值。模擬退火算法思想如下：產(chǎn)生可行鄰域解。模擬退火算法是鄰域搜索算法，利用Metropolis接受機(jī)制，有幾率產(chǎn)生比當(dāng)前全局最優(yōu)粒子差的鄰域解，使算法有概率跳出局部極值。設(shè)優(yōu)化目標(biāo)函數(shù)為f（x），當(dāng)前迭代次數(shù)時(shí)全局最優(yōu)解為fx1，產(chǎn)生鄰域解為fx2，兩者差值設(shè)定df=fx2-fx1，則Metropolis準(zhǔn)則接受鄰域值得概率p為：P=由此公式可以看出，當(dāng)df<0時(shí)，一定會(huì)產(chǎn)生新的鄰域解，即還有達(dá)到局部最優(yōu)狀態(tài)；當(dāng)df>=0時(shí)，算法以***概率接受鄰域解，即當(dāng)前全局最優(yōu)解好了鄰域解時(shí)，產(chǎn)生概率p是溫度T得增函數(shù)，當(dāng)T減少時(shí)概率p也減少，即體現(xiàn)算法后期鄰域搜索能力較強(qiáng)特性。初溫及降溫設(shè)定。初溫設(shè)定一般較大，能夠使得所有轉(zhuǎn)移狀態(tài)都被接受，但也不宜過(guò)大，否則算法搜索時(shí)間過(guò)長(zhǎng)，本文取t=1000作為初始溫度。其降溫公式為：****，t為迭代次數(shù)，從公式可以看出，隨著t得增加，溫度降低。終止溫度。當(dāng)模擬退火算法內(nèi)、外循環(huán)在每一次迭代沒(méi)有產(chǎn)生新的更新?tīng)顟B(tài)或已經(jīng)達(dá)到設(shè)定的溫度下限，即看成完成尋優(yōu)任務(wù)，終止循環(huán)。1.3.3編碼與解碼優(yōu)化問(wèn)題中粒子編碼就是所求優(yōu)化問(wèn)題得所有解得表達(dá)方式。編碼得選取直接影響粒子群算法得優(yōu)化性能，需符合調(diào)度方案，可以映射調(diào)度問(wèn)題得解空間，能夠適應(yīng)粒子群算法中位置、速度得迭代更新。在車間調(diào)度問(wèn)題中，粒子編碼可以選取得種類很多，可從工件、工序、機(jī)器等進(jìn)行編碼，比較編碼復(fù)雜性和時(shí)間復(fù)雜度來(lái)說(shuō)，本文選取工序編碼方式進(jìn)行。解碼是相對(duì)于編碼而言的，簡(jiǎn)單概括編碼是將具體問(wèn)題抽象化，建立數(shù)學(xué)模型，便于求解，解碼是將所得數(shù)據(jù)還原具體問(wèn)題當(dāng)中，從而進(jìn)行評(píng)估、選擇?，F(xiàn)有3個(gè)工件需要加工，每個(gè)工件需要加工3道工序，采用工序編碼，下圖給出一組可行解。1313212231.1可行解編碼如圖所示，圖中1、2、3代表工業(yè)生產(chǎn)中工件編碼，在可行解編碼中出現(xiàn)的位置代表加工的有效順序，以第一件工件為例，出現(xiàn)的位置分別為1號(hào)、3號(hào)、6號(hào)位，即代表工件1分別在對(duì)應(yīng)的位置進(jìn)行工序1、工序2、工序3得加工工作，以此類推，圖1只是給出一個(gè)可行編碼解，代表工件加工順序優(yōu)先級(jí)。1.3.3交叉與變異交叉與變異操作是遺傳算法得重要手段，是通過(guò)生物進(jìn)化而得來(lái)的準(zhǔn)則。交叉操作是指子代中繼承父代有利基因，淘汰不利基因；變異是將原有基因序列某一片段進(jìn)行修改，進(jìn)而增強(qiáng)子代基因，通過(guò)交叉變異操作可以提高子代基因種類。由粒子群公式可以看出，粒子迭代后速度更新由自身與群體其他粒子均有影響，正是因?yàn)橛杀旧須v史最優(yōu)粒子和全局最優(yōu)粒子得影響下，保持向全局最優(yōu)粒子靠攏，從而實(shí)現(xiàn)子代更新迭代。由此可知，交叉操作是父代在參考群體搜索經(jīng)驗(yàn)當(dāng)中進(jìn)行的，子代在繼承父代有利基因外，還將繼承群體經(jīng)驗(yàn)中交叉變異后的有利基因，這樣增加了跳出局部極值得概率。粒子群算法不能動(dòng)態(tài)實(shí)現(xiàn)種群更新，本文引入交叉變異操作提高粒子群算法種群動(dòng)態(tài)更新。（1）交叉操作選定需要進(jìn)行交叉操作的兩個(gè)父代粒子x1、x2，將x1粒子隨機(jī)選中和保留粒子的基因位，并記錄選中基因個(gè)數(shù)，在x2粒子隨機(jī)選中與x1粒子選中基因數(shù)相同的粒子，并保留其所在基因位，復(fù)制到新一代y粒子當(dāng)中，將x1粒子中未選中基因按照順序重新插入到y(tǒng)粒子中，所得新的基因序列即為交叉操作所得粒子。交叉操作示意圖：（2）變異操作在粒子群算法中引入變異操作，也是提高種群多樣性的有效途徑，引導(dǎo)算法指向更高的適應(yīng)度函數(shù)進(jìn)化，在鄰域搜索算法中，引入變異操作，使粒子產(chǎn)生鄰域解，增強(qiáng)種群多樣性，有易于跳出當(dāng)前迭代極值，實(shí)現(xiàn)全局搜索。在基于工序編碼的車間調(diào)度問(wèn)題當(dāng)中，變異操作是隨機(jī)選擇父代中一個(gè)粒子基因片段的不同基因位進(jìn)行互換，需要強(qiáng)調(diào)的是，一個(gè)基因片段可以互相調(diào)換多組基因位，如果調(diào)換位置基因位相同，則父代基因與變異后子代基因相同，則實(shí)質(zhì)上沒(méi)有進(jìn)行變異。以3*3車間調(diào)度問(wèn)題為背景對(duì)其變異過(guò)程如圖所示：1.4靜態(tài)車間調(diào)度求解混合粒子群算法根據(jù)車間調(diào)度問(wèn)題提出，為了驗(yàn)證混合粒子群算法在車間調(diào)度問(wèn)題中的應(yīng)用，首先采用靜態(tài)車間調(diào)度問(wèn)題，采用matlab測(cè)試軟件進(jìn)行模擬仿真實(shí)驗(yàn)，驗(yàn)證結(jié)果。1.4.1建立數(shù)學(xué)模型確定車間調(diào)度問(wèn)題的輸入輸出是建立數(shù)學(xué)模型的關(guān)鍵，我們以工件個(gè)體及加工時(shí)間為輸入對(duì)象，輸出則以甘特圖表示最佳調(diào)度流程，經(jīng)過(guò)限制條件、智能算法優(yōu)化、最終達(dá)到求解最優(yōu)值。車間調(diào)度問(wèn)題數(shù)學(xué)模型圖如下：1.4.2仿真實(shí)驗(yàn)本文選取較為常見(jiàn)的FT06實(shí)例進(jìn)行仿真測(cè)試實(shí)驗(yàn)，F(xiàn)T06實(shí)例描述為一批待加工6個(gè)工件，6臺(tái)加工機(jī)器，每個(gè)工件需要加工6道工序，求解如何加工工件順序使得加工時(shí)間最少，效率最高。具體工件及加工時(shí)間如下表：FT06實(shí)例問(wèn)題目前達(dá)到的最好解為55。利用混合粒子群算法求解的FT06問(wèn)題得出甘特圖如圖3.2，圖中以工件加工總消耗時(shí)間為橫坐標(biāo)，以工件編號(hào)為縱坐標(biāo)，以矩形框表示工件加工順序。為了進(jìn)一步驗(yàn)證混合粒子群算法在實(shí)例當(dāng)中收斂性、魯棒性，同時(shí)選取了DPSO、GA算法進(jìn)行模擬對(duì)比實(shí)驗(yàn)，在FT06實(shí)例問(wèn)題上三種算法分別求解10次，每種算法迭代200次，選取每一次迭代全局最優(yōu)解平均值做出如圖**所示，圖中以每種算法迭代次數(shù)為橫坐標(biāo)，以每次迭代中全局最優(yōu)值平均值為縱坐標(biāo)。從圖中可以看出，混合粒子群算法在收斂速度和收斂效果上都比DPSO、GA算