一種基於類電磁機制的離散型優化方法

2023-09-16 14:42:25

專利名稱：一種基於類電磁機制的離散型優化方法
技術領域：
本發明屬於計算機領域，具體涉及一種基於類電磁機制的離散型優化方法，將連 續型的類電磁機制算法進行離散化，擴展了其應用領域，使其可以更好地用於解決組合優 化問題。
背景技術：
學者Birbil和Fang受電磁場中帶電粒子間吸引-排斥機制的啟發，於2003年提 出了一種新的全局優化啟發式算法——類電磁機制(Electromagnetism-like Mechanism, EM)算法。EM算法是一種隨機全局優化算法。和遺傳算法類似，EM算法也是先隨機從可行 域中產生一組初始解(這裡稱之為一群初始粒子)，然後根據每個粒子所確定的目標函數 值來確定吸引域，以某種機制產生新一代粒子。在遺傳算法裡，產生新一代粒子的機制是復 制、交叉和變異，而EM算法模擬電磁場中的吸引與排斥機制，將每個解比作一個帶電粒子， 然後按一定的準則使得搜索粒子朝最優解移動。這種思想來自於與電磁理論中吸引與排斥 機制的類比，由於兩者之間存在一些差異，因此稱之為類電磁機制。更重要的是EM算法的 收斂性已經得到了證明，證明結果表明當迭代趨於極限時，種群中至少有一個粒子以概率1 移動到全局最優附近。下面以如下形式的非線性、無約束(變量有界)的優化問題為例，具體介紹EM算 法的步驟，目標函數如下minf(x)(1)其中f :Rn — R為一非線性函數，χ e S，S為一有界可行域。η為問題的維度，f (χ) 為待優化的函數。EM算法由四個階段構成，即粒子的初始化，計算每個粒子上的合力，粒子沿合力方 向移動，以及局部搜索。(1)初始化初始化就是從已知可行域中隨機取一定數量的m個點，然後在後面的步驟中以這 些點為基礎來進行更進一步的搜索。在這裡，將初始粒子隨機均勻地分布在可行域裡，然後 計算出每個粒子的目標函數值，並將目標函數值最優的粒子記為Xtest。⑵局部搜索局部搜索是對單個粒子進行的，用來改進種群已搜索到的解。對於EM算法，局部 搜索起著非常重要的作用，因為它為種群的全局搜索提供了有效的局部信息，這樣使算法 既具有全局搜索能力，又具有局部區域精細搜索的能力。這裡使用的局部搜索是最簡單的 線性搜索，對每個粒子的每一維按照一定的步長進行搜索，一旦找到一個更好的解就停止。(3)計算合力計算合力是EM算法最重要的一步，這一步將粒子所獲得的局部信息與全局信息 結合起來了。基本電磁理論裡的疊加原理是一個粒子受到的其它粒子施加的電磁力與粒子之間的距離成反比且與它們所帶電荷數的乘積成正比。從這個角度出發，EM通過計算合 力來為下一步的搜索提供信息。 粒子i的電荷量Cii決定了粒子i所受的吸引力或者排斥力的大小。該電荷由下 式算得 這樣，目標函數值較優的粒子將擁有較大的電荷數，具有更強的吸引力。這一點並 不同於真正的電荷，因為公式(2)中各粒子的電荷都是沒有正負號的。我們在比較兩粒子 的目標函數值後決定兩粒子間作用力的方向。因此，作用在粒子i上的合力Fi由下式計算
(3)根據這個公式，對於兩個粒子而言，目標函數值較優(即較小)的粒子將吸引另一 個粒子，反之，目標函數值較劣(即較大)的粒子將排斥另一個粒子。由於Xtest的目標函數 值最小，它充當著一個絕對吸引的粒子，即它吸引著種群中的其它所有粒子。(4)移動粒子計算完合力向量Fi後，粒子i將沿著合力的方向以一個隨機步長(如公式(4)中 給出)移動。該步長λ在
上均勻分布。在公式(4)中，RNG為一個向量，其分(向)量表示對應的朝上邊界Uk或者下邊界 Ik移動的可行步長。另外，作用在每個粒子上的力都被「歸一化」了，從而保證了移動的可 行性。因此，粒子每一步移動的公式為 A = X, + 義
F
Il 巧 Il
(RNG),/i
(4) 這樣每個粒子的位置就得到了更新，也就完成了 EM算法的一次迭代。從前面的步 驟可以看到，類電磁機制算法是基於函數優化問題提出的，是一種連續型的優化算法。目前 採用類電磁機制算法解決組合優化問題的很少，而且都是採取的隨機鍵的轉換方式，將組 合優化問題的離散型編碼轉換成了連續型的編碼進行求解，這樣增大了算法搜索的空間。

發明內容
本發明在原始類電磁機制算法的基礎上，通過設計距離的計算方式和移動的方 式，提出了類電磁機制算法離散化的方法，該技術可以使類電磁機制算法能更好地解決組 合優化問題。為實現上述目的，本發明採用的技術方案如下(1)初始化。設置種群大小m、變異率PR0BMU、UP值以及最大迭代次數maxGen。在 可行域空間隨機選取m個粒子，對每個粒子進行編碼。(2)評價上述經初始化後的種群，找出當前種群中的最優粒子，並令迭代次數Gen=1。(3)計算粒子間的距離。距離的計算方式如下比較兩個粒子編碼中對應位置上 的值，不一樣的值的個數就是粒子間的距離。假定有兩個粒子，粒子1是[1 2 3 4 5]，粒 子2是[1 3 4 5 2]，那麼第2、3、4和5位上的值不一樣，所以這兩個粒子之間的距離是4。 (4)計算粒子間的作用力。對於任一粒子i，所帶電量的計算公式為 f (electron1)是粒子i的目標函數值，f (beSt_perSOnal)是當前種群中最優粒子 的目標函數值，UP是設定的常數，這個公式能保證越優的個體帶有的電量值越大。粒子i和粒子j之間的作用力的計算公式為 Dis表示粒子i和粒子j之間的距離。(5)移動粒子。移動是使減少兩個粒子之間的距離的一種操作，也就是使一個粒子 向另一個粒子進行靠近。針對不同的組合優化問題，在保證不產生非法解的情況下，可以採 取交換或者插入的方式，使得兩個粒子的距離減小。(6)變異操作。當r 0. 5，對要移動的粒子進行變異 操作1 ；如果r < 0. 5，對要移動的粒子進行變異操作2。r是(0，1)之間的隨機數。(7)評價每個粒子的目標函數值。(8)對當前的最優粒子進行局部搜索。通過在局部範圍內進行搜索，提高算法精細 搜索的能力。本技術採取了變鄰域的局部搜索策略。要針對具體問題，採用相應的領域構 造方法。(9)判斷迭代次數Gen是否達到規定的閾值maxGen，若是，則算法結束，輸出當前 最優粒子以及對應的目標函數值；否則令Gen = Gen+Ι，再回到步驟(3)。本發明和現有技術相比具有以下優點(1)使類電磁機制算法從連續型的編碼空間擴展到了離散型的編碼空間。 (2)和採用隨機鍵的方式相比，可以縮小搜索空間，使類電磁機制算法能更好地解 決組合優化問題。隨機鍵的方式雖然可以使連續型的算法可以用來解決組合優化問題，但 是還是針對連續型的編碼進行操作，這樣搜索空間很大。 (3)採用了變鄰域的局部搜索策略。針對具體問題設計鄰域結構，可以克服原始算 法中局部搜索的盲目性，提高算法的精度和效率。


圖1本發明的實現流程圖
具體實施例方式下面結合附圖和具體實施例對本發明作進一步說明。以解決分布式流水車間調度問題為例，詳細介紹一下算法的實施過程。分布式流水車間調度問題是流水車間調度問題的一般化，問題描述如下，有N個工件要在F個車間加 工，每個車間包含M臺機器，所有的車間都能處理每個工件，那麼調度的任務就是要將N個 工件分配到F個車間並排序，使得所有車間中的最大完工時間最小。具體實施步驟如下(1)初始化設置種群大小m、變異率PROBMU、UP值以及最大迭代次數maxGen。在可行域空間 隨機選取m個粒子，並對選取的每個粒子進行編碼。(2)評價上述經初始化後的種群，找出當前種群中的最優粒子，並令迭代次數Gen =1。(3)計算粒子間的距離距離的計算方式如下比較兩個粒子編碼中對應位置上的值，不一樣的值的個數 就是粒子間的距離。假定有兩個粒子，粒子1是[1 2 3 4 5]，粒子2是[1 3 4 5 2]，那麼 第2、3、4和5位上的值不一樣，所以我們設定這兩個粒子之間的距離是4。(4)計算粒子間的作用力。作用力的計算方式如下對於任一粒子i，所帶電量的計算公式為 其中，f (electron)是粒子i的目標函數值，f (best_personal)是當前粒子所找 到的最優值，UP是設定的常數，這個公式能保證越優的個體帶有的電量值越大。
廠 ,· ,· Dis -1粒子i和粒子j之間的作用力的計算公式為= W其中，Dis表示粒子
i和粒子j之間的距離。(5)移動粒子，以減小粒子間的距離。移動是使減少兩個粒子之間的距離的一種操作，也就是使一個粒子向另一個粒 子進行靠近。在這裡採用兩種移動策略，一種是交換，稱作m0Ve_SWap，一種是插入，稱作 move_insertion0move_swap具體的實施步驟如下有兩個粒子，本實施例中粒子1是[1 2 3 4 5]，粒子2是[1 3 4 5 2]。假設我 們要使粒子1向粒子2移動，1)計算兩個粒子間的距離，這裡距離為4 ；2)令變量 t = 1 ；3)判斷兩個粒子第t位的數是否相同，如果不相同，那麼轉到第4步，否則令t = t+Ι，並重複該第3)步。比如對於前面兩個粒子，當t = 2時跳過第三步；4)將粒子1上第t位上的數和粒子2上第t位上的數在粒子1上進行交換。比如對前面兩個粒子，應該交換的數為2和3，所以採用一次m0Ve_SWap後的粒子 1變成了 [1 3 2 4 5]。經過三次m0ve_swap後，粒子1和2之間的距離將變成0。move_insertion具體的實施步驟如下有兩個粒子，粒子1是[1 2 3 4 5]，粒子2是[5 3 2 1 4]。假設我們要使粒子 1向粒子2移動，
7
1)計算兩個粒子間的距離，這裡粒子1和2之間的距離是4 ；2)令變量 t = 1 ；3)判斷兩個粒子第t位的數是否相同，如果不相同，那麼轉到第4步，否則令t = t+Ι，並重複第三步。比如對於前面兩個粒子，當t = 1時跳過第三步；4)在粒子1中找到與粒子2中第t位的數字相同的數字，將它插到粒子1中第t 的位置。粒子1中原第t位至所述找到的位置之間的數字順序保持不變，依次後移一位，完 成移動操作。對於這裡的粒子1和2，經過兩次movejnsertion後，粒子1和2的距離就變成了 O0移動粒子的具體操作如下如果隨機數RAND > 0. 5，那麼對要移動的粒子進行m0Ve_SWap操作；如果隨機數 RAND < 0. 5，那麼對要移動的粒子進行move_insertion操作。(6)變異操作。當r 0. 5，對粒子i進行變異操作1 ；如果r < 0. 5，對粒子 i進行變異操作2。r是(0，1)之間的隨機數。其中，所述變異操作1是指隨機交換粒子編碼中的兩個位置，變異操作2是指對編 碼中隨機截取的一段位置的排列進行倒置操作，即將排列中的第K個位置和對應的倒數第 K個位置進行交換，如第一個位置和最後位置進行交換，第二個和倒數第二個交換等。(7)評價每個粒子的目標函數值，得到當前的最優粒子。根據粒子的編碼計算每個車間的最大完工時間，把其中最大的完工時間作為目標 函數值。其中目標函數值最小的粒子就是當前的最優粒子。(8)對當前的最優粒子進行局部搜索，改善當前的最優粒子。為了提高算法的精度，本發明採用基於變鄰域(VNS)的局部搜索策略，針對分布 式流水車間調度問題，我們採取了四種領域構造方式。前兩種是基於關鍵車間的，關鍵車間 指的是SUb-最大完工時間最大的車間，SUb-最大完工時間指的是每個子車間的最大完工 時間。這四種領域構造方式如下a 在關鍵車間進行插入操作，即隨機將關鍵車間中的一個工件插到另一個工件的 前面；b 在關鍵車間進行交換操作，即隨機交換關鍵車間中的兩個工件的位置；c 插入，即隨機將任一車間中的一個工件插到另一個工件的前面；d 交換，即隨機交換任一車間中的兩個工件的位置。基於VNS的局部搜索策略如下首先對當前最優粒子按方式a進行局部搜索，然後依次按方式b、方式c和方式d 進行局部搜索，循環上述過程，直到滿足局部搜索的終止條件為止。(9)判斷迭代次數Gen是否達到規定的閾值maxGen，若是，則算法結束，輸出當前 最優粒子以及對應的目標函數值；否則令Gen = Gen+l，再回到步驟(3)。本發明的效果可以通過以下仿真實驗進一步說明選取分布式流水車間調度問題進行測試，測試數據來自Naderia標準實例庫和 Taillard標準實例庫。通過C++進行編程，計算機配置為=Intel雙核、2GB內存、2. IGHz的筆記本電腦。參數設置如下1、EM的終止條件最大迭代次數150，或者當前最優粒子的目標值在10次內沒有 發生變化，就終止算法。2、基於VNS的局部搜索的終止條件當局部搜索中的目標函數值在三次迭代中沒 有發生變化就終止。3、m = 100 ；PROBMU = 0. 6 ；UP = 0. 91 ；實例結果如表1和表2所示。表1 Naderia標準實例庫測試得到的新解實例車丄機舊最新最實例車丄機舊最新最間 數件 數器 數優解優解間 數件 數器 數優解優解 表1是用Naderia標準實例庫測試的結果，對於這720個實例，我們可以找到151 個更好的新最優解。
表2是用Taillard標準實例庫測試的結果，並將測試結果和原始的連續型的EM 算法(採用的隨機鍵的編碼轉換方式)進行了比較。表中min，aver和max分別代表最小 相對誤差，平均相對誤差和最大相對誤差。Taver代表平均CPU時間。從表2可以看出，離 散的EM算法在計算時間方面比連續的EM要快，在誤差方面也基本上都比連續的EM要小。表2離散EM和連續EM算法的比較 Ta051_51730502012.77517.92524.1625.1522.4287.53213.3534.333Ta051_61636502010.88018.60324.1444.1292.5068.77116.1984.176Ta05111553502010.75317.83625.8216.1402.6408.53818.2874.085Ta0612284610052.8117.37914.68711.2100.1411.8853.97010.143Ta061_31792100520.25724.74930.4699.72111.21713.99618.0809.963Ta061_41505100517.27623.86430.63110.2845.44910.48220.0008.485Ta061__51256100515.76426.52140.4469.3745.49412.30930.49410.063Ta061_61070100521.68236.06545.7949.9977.10317.34637.3839.571Ta0611956100520.81637.60555.4399.34510.56522.47436.7159.103Ta071228461001021.29326.60233.20411.05516.69018.17520.2749.302Ta071_319721001034.48340.24644.9297.90923.93527.23631.3899.207Ta071_415051001045.44952.23960.1999.39032.69138.61550.8318.945Ta071_512561001055.25565.47883.9178.36538.85445.33856.2108.374Ta071_610701001064.01975.12687.2909.24248.78558.76269.2527.693Ta071—79561001064.95881.271107.9508.53451.88365.32980.6497.471Ta081_23892100207.86212.59818.88512.2544.1115.8749.7899.784Ta081_329851002014.20417.44125.0929.2674.4228.31016.6169.688Ta081_424971002016.54021.45231.4389.0894.64610.94520.9859.132Ta081_522421002014.98722.89933.0518.8588.25213.43720.7409.088Ta081_620311002017.43026.05431.7588.0738.66614.41422.1079.226Ta081119041002022.00630.08941.4399.5599.34916.16322.5328.110Ta09125721200104.92910.61415.17215.5942.6744.8406.53717.464Ta091_339952001015.14417.81522.37813.9284.7817.33312.76617.067Ta091__430982001019.17424.26743.02815.8038.61812.87824.14516.890Ta091_525682001020.87229.85246.69018.55110.20219.65034.73516.571Ta091_622442001028.38735.01847.86116.53215.33022.68331.41716.368Ta091J20042001022.30537.28054.54119.33014.82026.04045.75816.648TaOlO26406200209.66313.51118.42021.5268.6649.65310.72417.618TaOlO_347272002014.13218.43923.24915.7737.99710.45712.08016.809TaOlO_438282002018.15622.42829.99015.53713.03617.84629.72816.981TaOlO_533022002016.83826.62837.43217.26211.78117.55127.01416.727TaO 10__629252002022.12029.88039.96614.27910.66722.21535.17916.922TaOlO726822002023.11736.10749.96313.69112.86423.02432.32716.676TaOll213968500209.91613.66516.76025.03510.13012.39813.56040.263TaOll_398345002014.30818.51124.51722.89113.86017.48023.70333.821TaOll_476625002017.75025.78134.27328.57715.91025.34645.88931.492TaOll_564025002022.54031.75342.95527.70319.27529.57442.90829.229TaOll_655465002022.77333.59852.72324.61111.12532.56044.46428.711TaOll749345002024.17938.72848.94627.53123.38934.58244.12227.821 通過這兩個實例庫進行測試，驗證了離散的EM算法的有效性和優越性。
1權利要求
一種基於類電磁機制的離散型優化方法，將類電磁機制算法從連續型的編碼空間擴展到離散型的編碼空間，以解決離散製造工業或流程工業的流水線生產調度問題，該方法具體步驟如下(1)初始化在可行域空間隨機選取m個粒子，預設置變異率PROBMU、常數UP以及最大迭代次數maxGen，並記錄下由該m個粒子構成的種群中的最優粒子，並對選取的每個粒子進行編碼；(2)評價上述經初始化後的種群，找出當前種群中的最優粒子，並令迭代次數Gen＝1；(3)計算粒子間的距離距離的計算方式如下比較兩個粒子編碼中對應位置上的數字，數字不一樣的位置個數就是該兩粒子間的距離；(4)計算粒子間的作用力對於任一粒子i，所帶電量的計算公式為 q i=UPexp ( - f ( electron i) - f (best_personal) f (best_personal) ) 其中，f(electroni)是該粒子i的目標函數值，f(best_personal)是當前種群所找到的最優值；粒子i和j之間的作用力的計算公式為其中，Dis表示粒子i和j之間的距離，其中j表示不同於i的任意粒子；(5)移動粒子，以減小粒子間的距離；(6)對粒子進行變異操作；當變異隨機數r＜PROBMU時，如果隨機數r＞0.5，對粒子進行一種變異操作，即隨機交換粒子編碼中的兩個位置；如果隨機數r＜0.5，則對粒子進行另一種變異操作，即對粒子的編碼中隨機截取的一段位置的排列進行倒置操作，其中，r∈(0，1)；(7)評價每個粒子的目標函數值；根據粒子的編碼計算每個車間的最大完工時間，把其中最大的完工時間作為目標函數值，其中目標函數值最小的粒子就是當前的最優粒子；(8)對當前的最優粒子進行局部搜索，改善當前的最優粒子；(9)判斷迭代次數Gen是否達到規定的閾值maxGen，若是，則算法結束，輸出當前最優粒子以及對應的目標函數值；否則令Gen＝Gen+1，重複執行步驟(3) (8)。FDA0000023730670000012.tif
2.根據權利要求1所述的一種基於類電磁機制的離散型優化方法，其特徵在於，所述 的步驟(5)中的移動包括交換和插入兩種，如果隨機數RAND>0. 5，那麼要移動的粒子進行 交換操作；如果隨機數RAND < 0. 5，對要移動的粒子進行插入操作，其中RAND e (0，1)。
3.根據權利要求2所述的一種基於類電磁機制的離散型優化方法，其特徵在於，所述 的交換的具體步驟為3. 1)計算兩個粒子間的距離； 3. 2)令變量t = 1 ；3. 3)判斷兩個粒子第t位的編碼值是否相同，如果不相同，那麼轉到第3. 4)步，否則令t = t+Ι，並重複該第3.3)步；·3.4)將其中一個粒子上第t位上的數和另一個粒子上第t位上的數進行交換。
4.根據權利要求2或3所述的一種基於類電磁機制的離散型優化方法，其特徵在於，所 述的插入的具體步驟為·4. 1)計算兩個粒子間的距離； 4. 2)令變量t = 1 ；·4. 3)判斷兩個粒子第t位的數是否相同，如果不相同，那麼轉到第4. 4)步，否則令t = t+Ι，並重複第三步；·4.4)在其中一個粒子中找到與另一粒子第t位的值相同的數字，將其插到所述其中一 個粒子的第t位，而所述其中一個粒子中原第t位至所述找到的數字位置之間的數字保持 順序不變，依次相後移動一位。
5.根據權利要求1-4之一所述的一種基於類電磁機制的離散型優化方法，其特徵在 於，所述步驟(8)中的局部搜索採用基於變鄰域(VNS)的局部搜索。
6.根據權利要求5所述的一種基於類電磁機制的離散型優化方法，其特徵在於，所述 基於變鄰域(VNS)的局部搜索採取四種領域構造方式，所述四種領域構造方式如下a 在關鍵車間進行插入操作，即隨機將關鍵車間中的一個工件插到另一個工件的前 面，其中所述關鍵車間指最大完工時間最大的車間；b 在關鍵車間進行交換操作，即隨機交換關鍵車間中的兩個工件的位置； c 插入，即將任一車間中的一個工件隨機插到另一個工件的前面； d 交換，即隨機交換任一車間中的兩個工件的位置。具體搜索過程為首先對當前最優粒子按方式a進行局部搜索，然後依次按方式b、方 式c和方式d進行局部搜索，循環上述過程，直到滿足局部搜索的終止條件為止。
全文摘要
本發明提出了一種基於類電磁機制的離散型優化方法，通過距離計算和移動操作，使類電磁機制算法的操作應用在了離散型的編碼上，從連續的空間擴展到了離散的空間。首先針對具體問題進行編碼，然後根據目標值計算每個粒子的電量，並根據距離的定義來計算粒子間的距離，然後計算粒子間的作用力以及每個粒子所受的合力，再根據合力移動粒子，更新種群後再對當前最優粒子進行局部搜索。該發明擴展了原有算法的應用領域，有助於其更好地解決組合優化問題。
文檔編號G06N99/00GK101923664SQ20101023739
公開日2010年12月22日 申請日期2010年7月27日 優先權日2010年7月27日
發明者張利平, 李新宇, 王曉娟, 邵新宇, 高亮 申請人:華中科技大學