mtsp模型及求解word版(編輯修改稿)
2025-09-17 16:22 本頁面
【文章內(nèi)容簡(jiǎn)介】 (6), S {1,…,N+M}, 2≤|S|≤N+M2 (7)Xij∈{0,1}, i, j∈{1,…,N+M} (8)目標(biāo)函數(shù)式(1)使得總的懲罰最小。約束式(2)表示任務(wù)i之后軋制的任務(wù)有且只有一個(gè)；約束式(3)表示在訂單j之前有且只有一個(gè)任務(wù)被軋制；約束式(4)~(6)表示軋制規(guī)范，其中式(4)表示相鄰板坯寬度跳躍約束，式(5)表示相鄰板坯厚度跳躍約束，式(6)表示硬度等級(jí)跳躍約束；約束式(7)是為了避免在可行解中構(gòu)成子回路而引進(jìn)的約束；約束式(8)表示變量是01變量[6]。按照熱軋生產(chǎn)約束，相鄰板坯之間的寬度、厚度和硬度等變化越小，則綜合衡量指標(biāo)越優(yōu)。因此兩節(jié)點(diǎn)之間的距離可定義為相鄰軋件的各軋制參數(shù)的改變(跳躍)值之和，以此作為相鄰板坯之間的對(duì)軋制參數(shù)寬度、厚度和硬度跳躍值懲罰。相鄰板坯之間的寬度、厚度和硬度跳躍值之和越大，則作為懲罰值也就越大，對(duì)應(yīng)的軋制計(jì)劃評(píng)價(jià)就越差。3 改進(jìn)的遺傳算法解決旅行商問題將熱軋調(diào)度中的N種任務(wù)看成N個(gè)城市,把加工不同任務(wù)的轉(zhuǎn)換懲罰看成是城市之間的距離，這樣就把熱軋生產(chǎn)問題歸結(jié)為一個(gè)旅行商問題[7]。遺傳算法（GA）是一種全新的隨機(jī)搜索與優(yōu)化算法，而標(biāo)準(zhǔn)遺傳算法執(zhí)行的效率不高，而且容易在局部最優(yōu)解處收斂[8]。為了提高搜索的速度和效率，并針對(duì)對(duì)熱軋調(diào)度的TSP問題模型，我們對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)，得到了一種改進(jìn)的遺傳算法(MGA)。根據(jù)生物遺傳規(guī)律,雙親血緣關(guān)系越遠(yuǎn),子代優(yōu)良的可能性越大。在兩交換啟發(fā)交叉規(guī)則中，由2個(gè)父代生成1個(gè)子代，當(dāng)2個(gè)父代的鏈結(jié)構(gòu)接近時(shí)，通過HGA交叉后，子代不會(huì)有很大的改善[9]。這里提出了一種改進(jìn)遺傳算法，稱為三交換啟發(fā)交叉方法（THGA），主要有2點(diǎn)改進(jìn)：(1)通過增加交配的父代染色體的數(shù)量，由3個(gè)父代產(chǎn)生1個(gè)子代；(2)動(dòng)態(tài)調(diào)整交叉和變異概率，從而降低了染色體近親繁殖的可能,有效地控制了進(jìn)化過程[10]?！∪粨Q啟發(fā)交叉方法的基本思想選3個(gè)參加交配的染色體作為父代，以8個(gè)城市（訂單）為例來說明這一過程，其中dij由表1給出,父代染色體為：A = 3 2 1 4 8 7 6 5B = 2 4 6 8 1 3 5 7C = 8 7 5 6 4 3 2 1SUM1=42，SUM2=40，SUM3=46(SUM1，SUM2，SUM3分別為這3種排法所走的距離或懲罰費(fèi)用總和) 隨機(jī)選出初始城市（定單）j=1，Sj=3右轉(zhuǎn)動(dòng),使3成為3父代的第1位置。A = 3 2 1 4 8 7 6 5B = 3 5 7 2 4 6 8 1C = 3 2 1 8 7 5 6 4由于d(3,2)d(3,5)，所以有：A =5 2
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1