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