生產(chǎn)調(diào)度問(wèn)題及其優(yōu)化算法

1、個(gè)人資料整理僅限學(xué)習(xí)使用生產(chǎn)調(diào)度問(wèn)題及其優(yōu)化算法<采用遺傳算法與MATLAB 編程）信息 014孫卓明二零零三年八月十四日-0-/14個(gè)人資料整理僅限學(xué)習(xí)使用生產(chǎn)調(diào)度問(wèn)題及其優(yōu)化算法背景及摘要這是一個(gè)典型的 Job-Shop動(dòng)態(tài)排序問(wèn)題。目前調(diào)度問(wèn)題的理論研究成果主要集中在以Job-Shop問(wèn)題為代表的基于最小化完工時(shí)間的調(diào)度問(wèn)題上。一個(gè)復(fù)雜的制造系統(tǒng)不僅可能涉及到成千上萬(wàn)道車(chē)間調(diào)度工序，而且工序的變更又可能導(dǎo)致相當(dāng)大的調(diào)度規(guī)模。解空間容量巨大， N個(gè)工件、 M 臺(tái)機(jī)器的問(wèn)題包含 種排列。由于問(wèn)題的連環(huán)嵌套性，使得用圖解方法也變得不切實(shí)際。傳統(tǒng)的運(yùn)籌學(xué)方法，即便在單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問(wèn)題

2、中也難以有效應(yīng)用。b5E2RGbCAP本文給出三個(gè)模型。首先通過(guò)貪婪法手工求得本問(wèn)題最優(yōu)解，既而通過(guò)編解碼程序隨機(jī)模擬優(yōu)化方案得出最優(yōu)解。最后采用現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢(shì)的遺傳算法。文章有針對(duì)性地選取遺傳算法關(guān)鍵環(huán)節(jié)的適宜方法，采用MATLAB軟件實(shí)現(xiàn)算法模擬，得出優(yōu)化方案，并與計(jì)算機(jī)隨機(jī)模擬結(jié)果加以比較顯示出遺傳算法之優(yōu)化效果。對(duì)車(chē)間調(diào)度系列問(wèn)題的有效解決具有一定參考和借鑒價(jià)值。 p1EanqFDPw一問(wèn)題重述某重型機(jī)械廠(chǎng)產(chǎn)品都是單件性的，其中有一車(chē)間共有 A ， B，C，D四種不同設(shè)備，現(xiàn)接受 6件產(chǎn)品的加工任務(wù)，每件產(chǎn)品接受的程序在指定的設(shè)備上加工，其工序與加工周期如下表： <

3、;S-設(shè)備號(hào)、 T-周期） DXDiTa9E3d工序12345678產(chǎn)品STSTSTSTSTSTSTST1C8A2B4C24D62A4D 5B 3C 43C3D7A15B20A84B 7C6D21A1D16C35D10B4C 8D 4A12C6D 16A 1B 4A 7C 3D 5A 2C 5A 8(表一 >條件： 1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒；2、每臺(tái)設(shè)備在同一時(shí)間只能擔(dān)任一項(xiàng)任務(wù)。<每件產(chǎn)品的每個(gè)工序?yàn)橐粋€(gè)任務(wù)）問(wèn)題：做出生產(chǎn)安排，希望在盡可能短的時(shí)間里，完成所接受的全部任務(wù)。要求：給出每臺(tái)設(shè)備承擔(dān)任務(wù)的時(shí)間表。注：在上面，機(jī)器 A， B， C，D即為機(jī)器 1，

4、2， 3， 4，程序中以數(shù)字 1， 2， 3，4表示，說(shuō)明時(shí)則用 A， B， C， D-1-/14個(gè)人資料整理僅限學(xué)習(xí)使用二模型假設(shè)1每一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能被一臺(tái)機(jī)器所加工 ，同時(shí)加工過(guò)程為不間斷；2所有機(jī)器均同時(shí)開(kāi)工，且工件從機(jī)器I到機(jī)器 J 的轉(zhuǎn)移過(guò)程時(shí)間損耗不計(jì)；3各工件必須按工藝路線(xiàn)以指定的次序在機(jī)器上加工多次；4操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限。三符號(hào)說(shuō)明及初始數(shù)據(jù)表達(dá)分析- 第i 個(gè)工件 <i=1 6）- 機(jī)器順序陣表示 i 工件的第 j 個(gè)操作的機(jī)器號(hào)-第j 臺(tái)機(jī)器<j=14）-工件排列陣表示 i 機(jī)器上第

5、 j 次加工的工件號(hào)-加工時(shí)間陣為i 工件的第 j 個(gè)操作的時(shí)間周期- 整個(gè)任務(wù)完成時(shí)間整理數(shù)據(jù)后得到：= CABCD000=8 2424 6000RTCrpUDGiT ADBC0000 453400005PCzVD7HxA CDABA000 3715208000jLBHrnAILg BCDADC00 76 21116300xHAQX74J0X DBCDACD0 1048412610LDAYtRyKfE ABACDACA 14735258Zzz6ZB2Ltk上述二陣直接從題目得出，而則是我們要求的。關(guān)于工件的加工時(shí)間表 ：( 表二 >產(chǎn)品 / 工件 <i ） :123456總計(jì)總凈

6、加工時(shí)間 <周期）441653544535247加工工序總數(shù) <個(gè)）54567835關(guān)于機(jī)器的加工時(shí)間表：(表三>機(jī)器 / 設(shè)備 (j>:ABCD總計(jì)總凈加工時(shí)間60427075247加工操作次數(shù)10610935分析：由于各產(chǎn)品總凈加工時(shí)間和各機(jī)器總凈加工時(shí)間之中最大值為75 ，而總計(jì)為 247，-2-/14個(gè)人資料整理僅限學(xué)習(xí)使用那么 總時(shí)間 C 介于 75 ，247 。同時(shí)各工件加工繁雜程度不一，各機(jī)器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對(duì)于節(jié)省時(shí)間和資源是必要的。dvzfvkwMI1希望最優(yōu)化答案是75，這樣達(dá)到最小值，如果答案是75，那么意味著機(jī)器D不間斷工作

7、 , 直至全部加工任務(wù)完成。rqyn14ZNXI四貪婪法快速求解AB如果按照一定規(guī)則排序，當(dāng)多個(gè)工件出現(xiàn)“搶占”同一機(jī)器的局面的時(shí)候 , 我們可以制定如下的工序安排規(guī)則 :1. 優(yōu)先選擇總剩余時(shí)間或總剩余操作較多的工件。 <如果出現(xiàn)總剩余加工時(shí)間多者總剩余操作數(shù)反而較少的情況時(shí), 按照程度具體情況具體分析）。EmxvxOtOco2. 機(jī)器方面來(lái)說(shuō) , 盡量避免等待空閑時(shí)間，優(yōu)先考慮剩余凈加工時(shí)間或者剩余加工總次數(shù)較多的機(jī)器 , 尤其是機(jī)器 D,即倘若能夠使機(jī)器 D不間斷工作且其他機(jī)器完工時(shí)間均不多余 75時(shí), 那么就可以得到最優(yōu)解。 SixE2yXPq5首先按照最優(yōu)化時(shí)間為 75的設(shè)想避

8、免 D出現(xiàn)等待，排序后得到升以下具體排列順序。各機(jī)器承擔(dān)任務(wù)表為 ( 其中粗體字為對(duì)應(yīng)工件產(chǎn)品號(hào)，括號(hào)內(nèi)為對(duì)應(yīng)時(shí)間周期段>：操作 1操作 2操作 3操作 4操作 5操作 6操作 7操作 8操作 9操作 106216345636(1>(2-5>(12-13>(14-20>(21-35>(36>(43-54>(55-56>(57-64>(66-73>465132(1-7>(8-11>(12-15>(16-19>(36-55>(56-58>C3145615624(1-3>(4-11>(1

9、2-17>(18-25>(26-28>(29-52>(55-60>(61-65>(66-69>(70-72>D534562415(1-10>(11-17>(18-38>(39-42>(43-47>(48-52>(53-68>(69-74>(75>(表四>A 機(jī)器1 4 27151 12288B 機(jī)器744 4203C機(jī)器38683246543D 機(jī)器10721455166101020304050607080-3-/14個(gè)人資料整理僅限學(xué)習(xí)使用( 圖一>上圖為加工周期圖 <甘特

10、圖），標(biāo)注數(shù)字為相應(yīng)操作的周期，完工時(shí)間為第75 周期。五計(jì)算機(jī)隨機(jī)模擬 <編程）1編碼：隨機(jī)產(chǎn)生生產(chǎn)的工序操作優(yōu)先順序，進(jìn)行編碼，如：K=43566231 45<注：同時(shí)作為下文的染色體之用）意思為：工件 4優(yōu)先被考慮進(jìn)行第一次操作，然后 3進(jìn)行其第一步操作，然后 5操作， 6操作，再 6操作其第二步工序，依次進(jìn)行。如果前后互相不沖突，則可同時(shí)在不同機(jī)器上操作。6ewMyirQFL通過(guò)排列組合得出，總共有類(lèi)似K 的排列序列 2多種！當(dāng)然，這其中只對(duì)應(yīng)解 75， 247，意味著有大量排列序列對(duì)應(yīng)同一加工方案，而大量加工方案又對(duì)應(yīng)同一時(shí)間解。 kavU42VRUs2解碼：即對(duì)編碼進(jìn)行

11、翻譯，產(chǎn)生具體可操作工序安排方案，這里采用活動(dòng)化解碼算法。例如工件 2第i 步操作 <記為<2， i），且在機(jī)器 A 上進(jìn)行）被安排在工件 3第j 步操作 <記為 JM<3,j ）后面進(jìn)行，那么如果安排好y6v3ALoS89<3,j）后，只要<2， i）在工件 2已經(jīng)排序好的操作之后進(jìn)行，那么操作 <2，i ）可插入到機(jī)器 A 處最前可安置的時(shí)間段進(jìn)行。在這里，一個(gè)編碼序列對(duì)應(yīng)一個(gè)加工方案，而一個(gè)加工方案可對(duì)應(yīng)一個(gè)或多個(gè)編碼序列，這就是二者之關(guān)系。3編程：通過(guò)一組隨機(jī)編碼產(chǎn)生一生產(chǎn)加工優(yōu)先序列，通過(guò)解碼過(guò)程產(chǎn)生相應(yīng)加工方案及其總耗費(fèi)時(shí)間 C .N次模擬

12、后即可得出解 C的概率密度分布情況以及相對(duì)最優(yōu)解 <N個(gè)C的最小值，如 80，77等，甚至出現(xiàn) 75）。 M2ub6vSTnP4計(jì)算機(jī)模擬所得數(shù)據(jù)分析a. 進(jìn)行 100次模擬得出最優(yōu)解情況：(共運(yùn)行 10次 >82，83，82， 84，78， 80，81，83， 87，82 平均值 82.2，每回耗時(shí)約 3秒 b. 進(jìn)行 1000次模擬得出最優(yōu)解情況： (共運(yùn)行 10次 >-4-/14個(gè)人資料整理僅限學(xué)習(xí)使用80，79，78， 78，79， 79，76，80， 77，78 平均值 78.4 , 每回耗時(shí) 25秒 c. 進(jìn)行 10000次模擬得出最優(yōu)解情況： (共運(yùn)行 10次&

13、gt;76，77，77， 75，76， 76，77，76， 76，77 平均值 76.3, 每回耗時(shí) 4分鐘 d. 模擬 1000000次得到的解 C的概率密度分布情況為： <如圖二所示）(圖二 ><注： 75處為 17次<概率為 17/1000000=1/58823 ）， 76處為 40次， 77處 167次 ）結(jié)論：如果想將 2中排序序列以平均出現(xiàn)一次的可能性進(jìn)行模擬，即運(yùn)行 2 次，計(jì)算機(jī)需運(yùn)行將近 150萬(wàn)億年！當(dāng)然，我們沒(méi)有這個(gè)必要，因?yàn)槲覀冎恍枰\(yùn)行數(shù)萬(wàn)次，就很可能得到最優(yōu)解 75，<在隨機(jī)模擬 1000000次后出現(xiàn) 17次75，那么意味著概率大約

14、17/1000000=1/58823 ，另外 76處為 40次， 77處167次）。 0YujCfmUCw六遺傳算法模型建立和步驟解法遺傳算法 <GeneticAlgorithm ）作為一種優(yōu)化算法特別適合于對(duì)象模型難于建立、搜索空間非常龐大的復(fù)雜問(wèn)題的優(yōu)化求解。它和模糊控制技術(shù)一樣，雖然在理論上還沒(méi)有完善，但是在實(shí)踐中已經(jīng)得到了廣泛的應(yīng)用。遺傳算法的基本思想是：模仿生物系統(tǒng) “適者生成 " 的原理，通過(guò)選擇、復(fù)制、交叉、變異等簡(jiǎn)單操作的多次重復(fù)來(lái)達(dá)到去劣存優(yōu)的目的，從而獲得問(wèn)題的優(yōu)化結(jié)果。遺傳算法的實(shí)現(xiàn)由兩個(gè)部分組成，一是編碼與解碼，二是遺傳操作。其中遺傳操作又包括選擇、復(fù)制

15、、交叉、變異等步驟。eUts8ZQVRd本文根據(jù)實(shí)際情況采取了1-6 整數(shù)編碼。數(shù)字1，2，3，4，5，6 分別代表6 件待加工產(chǎn)品。本文遺傳算法基本流程:通過(guò)編碼，解碼程序隨機(jī)產(chǎn)生N 個(gè) <有一定數(shù)量 , 如 50 或 100）個(gè)體構(gòu)成初始種群a)從初始中群中選取 2 個(gè)具有最優(yōu)染色體 <最有排序方案）的個(gè)體作為臨時(shí)個(gè)體 <父代）；-5-/14個(gè)人資料整理僅限學(xué)習(xí)使用b)如果此 2 個(gè)體中有一個(gè)個(gè)體通過(guò)解碼操作能夠?qū)崿F(xiàn)最優(yōu)排序<即使總時(shí)間為 75 周期），那么結(jié)束此算法，得到最優(yōu)解；sQsAEJkW5Tc)對(duì) 2 個(gè)臨時(shí)個(gè)體以一定方式 ( 循環(huán)交叉 >執(zhí)行染色體

16、交叉變換和變異選擇<小概率 , 互換操作），產(chǎn)生2 個(gè)新的個(gè)體； GMsIasNXkAd)對(duì)父代和子代共4 個(gè)個(gè)體進(jìn)行選擇，從中選出最佳的2 個(gè)個(gè)體，做為下一代的父代；e) 重復(fù)執(zhí)行第二步 (b> 操作；f) 如果執(zhí)行完 M步后仍然未得出答案 75，那么將目前的最優(yōu)解作為本算法的最優(yōu)解答案。1編碼和解碼 < 同上）2交叉變換 (crossover>對(duì) 2 個(gè)父代臨時(shí)個(gè)體進(jìn)行染色體交叉變換，采用循環(huán)交叉方法<Cycle crossoverCX），如父代染色體為：X：9 2 6 4 7 3 5 8 1和 Y：3 4 5 8 1 6 7 2 9，如果隨機(jī)選到第二位開(kāi)始交

17、叉，那么X的 2對(duì)應(yīng) Y的 4，X的 4對(duì)應(yīng) Y的 8，X的 8對(duì)應(yīng) Y的 2 ，這樣就確定了以上為不變的染色體，其余位置的染色體互換位置，最后得到:3 2 5 4 1 6 7 8 9,:9 4 6 8 7 3 5 2 1,實(shí)現(xiàn)交叉變換。TIrRGchYzg3變異選擇 <mutation ）采用 互換操作 <SWAP），即隨機(jī)交換染色體中兩不同基因的位置。如上面的染色體為：:3 2 5 4 1 6 7 8 9。隨機(jī)產(chǎn)生變換位置號(hào)，如產(chǎn)生隨機(jī)數(shù)3 和 5，那么交換數(shù)字后得到染色體：3 2 1 4 5 6 7 8 9， 變異概率取0.1。 7EqZcWLZNX4選擇操作 <sel

18、ection）對(duì)父代 2 個(gè)體 f1,f2和子代 2 個(gè)體 f3,f4進(jìn)行選擇，通過(guò)編碼操作確定具有最優(yōu)解的2 個(gè)個(gè)體，成為新一代f1 和 f2。 lzq7IGf02E如此，通過(guò)多次編碼和解碼隨機(jī)產(chǎn)生一定數(shù)量的個(gè)體，選取2 個(gè)最佳個(gè)體進(jìn)行交叉變換操作，產(chǎn)生 2 個(gè)新個(gè)體，然后對(duì) 4 個(gè)個(gè)體進(jìn)行選擇，產(chǎn)生下一代，如果某時(shí)刻通過(guò)解碼操作得出最優(yōu)解 <所有解的下限，這里是 75 周期），那么算法結(jié)束，否則循環(huán)進(jìn)行，直至預(yù)先給定的循環(huán)次數(shù)達(dá)到為止，以最后得到的最優(yōu)解作為最終最優(yōu)解。zvpgeqJ1hk七遺傳算法模擬 <采用 MATLAB工具編程）主程序如下： <子程序見(jiàn)略）% 本程序

19、為主程序，調(diào)用以下各分支程序task= 'Welcome! Wait a moment please! - Writer:孫卓明, 信息 014',NrpoJac3v1f1=zeros(1,35>。 f2=zeros(1,35> 。while f1=f2。%此步避免初始染色體 f1,f2相同，導(dǎo)致以下死循環(huán)1nowfTG4KI(N>。 %minminmax1,s1=chushijie種群初始化；基于操作的編碼策略；活動(dòng)化解碼算法。chushijie(N>參數(shù) N 為初始種群數(shù) fjnFLDa5Zof1=s1 。 minminmax1,%選取的第一個(gè)初始個(gè)

20、體-6-/14個(gè)人資料整理僅限學(xué)習(xí)使用minminmax2,s2=chushijie(N>再次種群初始化。%f2=s2。 minminmax2,%選取的第二個(gè)初始個(gè)體end 。Mfor e=1:% e=1:M進(jìn)行 M次遺傳操作<交叉-變異-選擇>。tfnNhnE6e5D=jiaocha(f1,f2>。%交叉變化 <循環(huán)交叉操作， cycle crossover CX）, 選取HbmVN777sLf1 。 f2 ?！叭旧w”無(wú)需變動(dòng)部分基因f3,f4=jiaocha_bianyi(f1,f2,D>。%生成交叉后的“染色體”, 并進(jìn)行變異選擇V7l4jRB8Hs

21、f3。 f4 。f1,f2=xuanze(f1,f2,f3,f4>。%選擇：對(duì)父代f1,f2和子代f3,f4進(jìn)行解碼，得出2 個(gè)83lcPA59W9f1 。 f2 。較優(yōu)個(gè)體，成為下一代的父代mZkklkzaaPminmaxf1,a1,b1=tongbujinzhan(f1>。% 求 該 時(shí) 刻 個(gè) 體f1的 最 優(yōu) 時(shí) 間 ( 因 為f1優(yōu) 于f2> AVktR43bpwif minmaxf1=75。f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,ORjBnOwcEdtask='Finish! Succe

22、ssful!Best answer!Congratulation! ' , return。2MiJTy0dTTend 。end。f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,gIiSpiue7Aif minminmax_last>=90。 task='Finish! Action again please!',end。uEh0U1Yfmhif minminmax_last>=80&&minminmax_last<90。 task='Finish!' , en

23、d。IAg9qLsgBXif minminmax_last<80。task='Finish! Successful!', end。WwghWvVhPE八遺傳算法模擬結(jié)果首先給出最優(yōu)方案 :在進(jìn)行某次 n=100,m=200 的操作后得到模擬最優(yōu)結(jié)果75 周期時(shí)間：minminmax1 =83minminmax2 =78<二個(gè)初始較優(yōu)個(gè)體解）f1 =4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5 6 4 6 6 4 3 2 2 5 11 asfpsfpi4k<f1為各工件優(yōu)先選擇順序排列, 即“染色體”）a1= 5

24、35396400000<a1,b1為四臺(tái)機(jī)器空閑周期段）ooeyYZTjj115240000000175365000000000000000b1=113842650000020350000000185468000000000000000minminmax =75<最終最優(yōu)解 ）其中機(jī)器 A 空閑時(shí)間段為 :5-11,35-38,39-42,64-65。 機(jī)器 B 則為 :15-20,24-35。 機(jī)器 C 為 :17-18,53-54,65-68。機(jī)器 D 無(wú)空閑。 BkeGuInkxI-7-/14個(gè)人資料整理僅限學(xué)習(xí)使用以下為 : 取不同 N 和 M值情況下數(shù)據(jù)優(yōu)化過(guò)程以及時(shí)間上

25、的比較:(表五>NNM第一次運(yùn)行第二次運(yùn)行第三次運(yùn)行第四次運(yùn)行第五次運(yùn)行平均運(yùn)行時(shí)間111104-114- 9898-105- 9392-93-92100-132- 9586-86- 84/1110106-97- 86108-100- 89102-87- 8799-90- 9088-104- 84/1110094-81- 8181-102- 7891-105- 91101-84- 8090-101- 90/111000107-100- 7892-101- 76101-100 -8288-97- 8691-93- 878.5(s>111000088-105- 77103-81- 77

26、89-99- 84107-104- 7893-105- 7880(s>10101090-108- 90104-91- 83104-100- 9395-98- 87105-106- 87/101010098-96- 9693-99- 9088-90-80105-92- 8091-95- 85/10101000101-96- 7891-89- 8096-104- 87105-105- 8488-99- 789.5(s>10101000099-92- 7797-95- 7596-104- 7689-99- 7691-101- 7590(s>10010010095-100- 8698

27、-90- 80104-99- 7893-88 -8192-99- 80/1001001000109-98- 8591-100- 82100-99- 77114-101 -8496-110- 7611(s>1001001000096-101- 78101-86- 76101-97- 8099-110- 7699-111- 77100(s>說(shuō)明 :以最后一行第一次運(yùn)行“96-101-78 ”為例 ,96 和 101 分別為 2 次 N 取100 時(shí)得到的100*2 個(gè)隨機(jī)解中的最優(yōu)解 ,78 為經(jīng)過(guò) M=10000代的遺傳( 交叉變異選擇 >后得到的最終最優(yōu)解。PgdO0sRlM

28、o明顯地發(fā)現(xiàn) : M的增大所產(chǎn)生的優(yōu)化效果明顯好于N 增大產(chǎn)生的優(yōu)化效果M 從 1-10-100-1000-10000的變化使最優(yōu)解有從9*-8*-7*的變化規(guī)律，N 的 1-10-100 的變化則不明顯。因此相對(duì)于隨機(jī)取解 ,經(jīng)過(guò)遺傳算法優(yōu)化之后效果是顯著的。另外對(duì)采用遺傳算法前后模擬所得數(shù)據(jù)進(jìn)行比較:第一次第二次第三次第四次第五次均值平均時(shí)間N=1000 ,M=0787981807925(S>794N=1,N=1,M=1000807577768278.08.5(S>(表六 >由上表看來(lái) , 雖然在均值方面相差不顯著 , 但是時(shí)間上采用遺傳算法之后節(jié)約了約三分之二的運(yùn)行時(shí)間

29、 , 效率顯而易見(jiàn)。 3cdXwckm15九模型優(yōu)缺點(diǎn)及改進(jìn)模型優(yōu)點(diǎn)，采用遺傳算法可對(duì)一個(gè)理論上無(wú)法求盡的NP 問(wèn)題以較有效方法在較短時(shí)間內(nèi)得到較精確解。缺點(diǎn)，采用遺傳算法還不全面，只是一個(gè)簡(jiǎn)單模型，未考慮收斂性, 適配值等，對(duì)參數(shù)設(shè)置與最優(yōu)解關(guān)系研究還不夠深入。h8c52WOngM模型本身還具有漏動(dòng)，仍需改進(jìn)，較好設(shè)想為采用和模擬退火算法的混合遺傳算法，由于時(shí)間緊迫，在此就不再深入給出模型及分析了。v4bdyGious-8-/14個(gè)人資料整理僅限學(xué)習(xí)使用參考文獻(xiàn)：1車(chē)間調(diào)度與遺傳算法王凌清華大學(xué)出版社2數(shù)值計(jì)算的算法與分析張可村趙英良科學(xué)出版社3Permutation Based GAs a

30、nd Ordered GreedPeter G. Anderson,J0bm4qMpJ94MATLAB6.0與科學(xué)計(jì)算王沫然電子工業(yè)出版社5C程序設(shè)計(jì) <第二版）潭浩強(qiáng)清華大學(xué)出版社信息014孫卓明2003年8月 14日本文網(wǎng)上下載地址 ( 個(gè)人主頁(yè) >: 附錄：子程序一： ( 種群初始化，得較優(yōu)個(gè)while x<=7。體 >Jm(I,x>=Jm(I,x+1>。functionx=x+1。minminmax,ss=chushijie(n>end。% 種群初始化 , 以下為編碼和解碼過(guò)程，同時(shí)Jm(I,8>=0。對(duì) n 次選取最優(yōu)化個(gè)體XVauA9

31、grYPend。Jm=3 1 2 3 4 0 0 0。14230000。34Jm=3 1 2 3 4 0 0 0。14230000。 3 4121000。23414300。423413121000。23414300。42341340 。1213 4131。bR9C6TJscw40 。1213 4131。 DJ8T7nHuGTminminmax=200。T=824246000。45340000。 3 7for d=1:n 。15208000。7621116300。1048412610。147352 5s=0。8。%編 碼程 序： 基于 操作 的編 碼策略%解碼程序：活動(dòng)化解碼算法pN9LBDdt

32、rdQF81D7bvUAk=1 。for i=1:6。for t=1:35。k(i>=1。I=randint(1,1,1,6>。end 。while Jm(I,1>=0。for q=1:4。I=randint(1,1,1,6>。for x=1:9。end。a(q,x>=0。 b(q,x>=0 。flag_(q>=0 。s(k>=I。end 。k=k+1。end 。x=1。for p=1:6。-9-/14個(gè)人資料整理僅限學(xué)習(xí)使用flag(p>=0。flag(s(i>>=flag(s(i>>+t。end 。flag_(q

33、>=flag(s(i>>。for i=1:35。end 。q=Jm(s(i>,k(s(i>>>。t=T(s(i>,k(s(i>>>。end 。z=0。 v=0 。k(s(i>>=k(s(i>>+1。for x=1:9。end。ifminmax=0。max(flag(s(i>>,a(q,x>>+t<=b(q,x>&&z=0。for q=1:4。ifif minmax<flag_(q>。flag(s(i>><=a(q,x>

34、&&a(q,x>+t=b(q,x>。minmax=flag_(q>。flag(s(i>>=b(q,x>。forend 。y=x:8 。a(q,y>=a(q,y+1>。end。b(q,y>=b(q,y+1>。 4B7a9QFw9hifend。minminmax>minmax。z=1 。% 得出初始最優(yōu)解 Yl4HdOAA61elseifminminmax=minmax。 ss=s。flag(s(i>><=a(q,x>&&a(q,x>+t<b(q,x>。end

35、 。a(q,x>=a(q,x>+t。 flag(s(i>>=a(q,x>。 z=1 。end。ix6iFA8xoXelseifflag(s(i>>>a(q,x>&&a(q,x>+t=b(q,x>。flag(s(i>>=b(q,x>。 b(q,x>=b(q,x>-t。 z=1 。子程序二： <父代交叉變換）wt6qbkCyDEfunction D=jiaocha(f1,f2>%交叉變elseif化 <循環(huán)交叉操作，CX） , 選取“染色體”無(wú)需變flag(s(i>

36、;>>a(q,x>&&a(q,x>+t<b(q,x>。動(dòng)部分基因 ch4PJx4BlIfor y=8:x+2。s=randint(1,1,1,35>。a(q,y>=a(q,y-1>。b(q,y>=b(q,y-1>。while f1(s>=f2(s>。end。s=randint(1,1,1,35>。b(q,x+1>=b(q,x>。b(q,x>=flag(s(i>>。end。a(q,x+1>=flag(s(i>>+t。for p=1:34。flag(s

37、(i>>=a(q,x+1>。z=1。Kp5zH46zRkD(p>=0。end。end 。end 。z=0 。 j=1 。D(j>=s 。j=j+1。end 。for i=1:35。if z=0。if f1(i>=f2(s>&&z=0。if flag(s(i>><=flag_(q>。D(j>=i。j=j+1 。z=1 。flag(s(i>>=flag_(q>+t。end。flag_(q>=flag_(q>+t。end 。elseif flag(s(i>>>fla

38、g_(q>。if f2(D(j-1>>=f1(s>。for x=1:9。return。if a(q,x>=0&&v=0。end 。a(q,x>=flag_(q>。for m=1:34。b(q,x>=flag(s(i>>。 v=1。z=0。end。end。for i=1:35。10/14個(gè)人資料整理僅限學(xué)習(xí)使用if f1(i>=f2(D(j-1>> && z=0。end。w=0。 for t=3:j。if (i-D(t-1>>>0|(i-D(t-1>><

39、;0。w=w+1。 end 。end。子程序四：<四者中選取最優(yōu)二個(gè)if w=j-2。體）D(j>=i。 j=j+1 。 z=1。functionend。f1,f2=xuanze(f1,f2,f3,f4>%end。對(duì)父代 f1,f2和子代 f3,f4進(jìn)行解碼，得出 2個(gè)end 。較優(yōu)個(gè)體，成為下一代的父代E836L11DO5if f2(D(j-1>>=f1(s>&&z=1。min1=0。min2=0。min3=0。min4=0。h=0。 g=0。return。min1=tongbujinzhan(f1>。end。min2=tongbuj

40、inzhan(f2>。end 。min3=tongbujinzhan(f3>。end。min4=tongbujinzhan(f4>。if min1<=min2&&min1<=min3&&min1<=min4。h=f1。ifmin2<=min3&&min2<=min4。g=f2 。子程序三： <變異選擇，形成子代）elseif min3<=min2&&min3<=min4。 g=f3 。functionelseif min4<=min2&&min

41、4<=min3。 g=f4 。f3,f4=jiaocha_bianyi(f1,f2,D>%end。生成交叉后的“染色體”, 并進(jìn)行變異選擇elseifqd3YfhxCzomin2<=min1&&min2<=min3&&min2<=min4。g2=f1 。 g1=f2 。h=f2。ifmin1<=min3&&min1<=min4。for i=1:34。g=f1 。if D(i>>0。elseifmin3<=min1&&min3<=min4。g1(D(i>>

42、=f1(D(i>>。g2(D(i>>=f2(D(i>> 。g=f3 。end 。elseifmin4<=min1&&min4<=min3。end。g=f4 。f3=g1 。 f4=g2 。end。c=randint(1,1,1,100>。elseifif c=1。min3<=min1&&min3<=min2&&min3<=min4 。d1=randint(1,1,1,35>。h=f3。ifmin1<=min2&&min1<=min4。d2=r

43、andint(1,1,1,35>。g=f1 。while d1=d2。elseifmin2<=min1&&min2<=min4。d2=randint(1,1,1,35>。g=f2 。end 。elseifmin4<=min1&&min4<=min2。m=f3(d1>。f3(d1>=f3(d2>。 f3(d2>=m 。g=f4 。elseif c=2。end。d1=randint(1,1,1,35>。elseifd2=randint(1,1,1,35>。min4<=min1&&a

44、mp;min4<=min2&&min4<=min3。while d1=d2。h=f4。ifmin1<=min2&&min1<=min3。d2=randint(1,1,1,35>。g=f1 。end 。 m=f4(d1> 。f4(d1>=f4(d2> 。 f4(d2>=m。elseifmin2<=min1&&min2<=min3。11/14個(gè)人資料整理僅限學(xué)習(xí)使用g=f2 。ifelseifmin3<=min1&&min3<=min2。max(flag(s

45、(i>>,a(q,x>>+t<=b(q,x>&&z=0。g=f3 。ifend。flag(s(i>><=a(q,x>&&a(q,x>+t=b(q,x>。end 。flag(s(i>>=b(q,x>。 for y=x:8。end。a(q,y>=a(q,y+1>。b(q,y>=b(q,y+1>。f1=h 。f2=g 。LOZMkIqI0wwhile f1=f2。end。 z=1。minminmax3,s1=chushijie(30>。elseiff2=s1 。flag(s(i>><=a(q,x>&&