計(jì)算機(jī)仿真大賽二等獎(jiǎng)?wù)撐睦眠z傳算法解決生產(chǎn)調(diào)度問(wèn)題(已修改)
2025-06-23 05:19 本頁(yè)面
【正文】 利用 遺傳算法解決生產(chǎn)調(diào)度問(wèn)題 摘要 在 現(xiàn)代制造業(yè)中 ， 生產(chǎn)特點(diǎn)是品種多、批量小，而車間資源的有限性制約著能否有效利用車間現(xiàn)有資源完成任務(wù)，以最快的速度響應(yīng)市場(chǎng)需求。調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個(gè)加工對(duì)象確定具體的加工路線、時(shí)間、機(jī)器和操作等。優(yōu)良的調(diào)度策略對(duì)于提高生產(chǎn)系統(tǒng)的最優(yōu)性、提高經(jīng)濟(jì)效益都有著極大的作用。作業(yè)車間調(diào)度問(wèn)題是一個(gè)典型的 NP— hard 問(wèn)題，是最困難的組合優(yōu)化問(wèn)題之一。 我們 發(fā)現(xiàn) 傳統(tǒng)的 利用微分 方程的優(yōu)化方法 并不適用，為了 解決這個(gè)問(wèn)題， 我們 將遺傳算法 引入 了 這個(gè) 模型當(dāng)中 。 這個(gè) 問(wèn)題的輸入 是每個(gè) 工件的每道工序 所用 的機(jī)器及 對(duì)應(yīng) 時(shí)間 ，用 兩個(gè)矩陣表示，要求 輸出 的是一個(gè) 最優(yōu) 的調(diào)度 方案 。 首先 ， 我們 采用 十進(jìn)制編碼， 用 一個(gè)一維的 數(shù)組，即 一條染色體 ， 來(lái)表示 一種調(diào)度 方案， 這個(gè) 數(shù)組中的每一個(gè)數(shù)表示 一個(gè) 工件 ，該 數(shù)字 出現(xiàn) 的次數(shù)表示這是該工件的第幾道工序 。 然后我們要得到一個(gè)初始化的種群，其中有一定數(shù)量的 隨機(jī) 得到的 染色體 。 接著 ， 我 們根據(jù)各個(gè) 染色體的 適應(yīng)度 對(duì)這個(gè)種群進(jìn)行選擇 、交叉和變異， 選擇時(shí) 我們 采用了 輪盤賭方法， 交叉時(shí) 為了 解決 不合理的情形，我們改良了 交叉 方法，根據(jù) 這樣 產(chǎn)生 出 一個(gè) 新的種群 ， 并不斷迭代 。 最后 當(dāng) 迭代達(dá)到 規(guī)定 次數(shù) 時(shí) ，終止 迭代，從最終種群中 挑選出 適應(yīng)度最高的染色體，即為最優(yōu) 方案 。 根據(jù) 這個(gè)模型，我們 進(jìn)行 了 編程實(shí)現(xiàn) ， 并 得到了最終結(jié)果 ， 發(fā)現(xiàn)最后 的種群已經(jīng) 趨近于 唯一 的最優(yōu)解了， 并根據(jù) 過(guò)程 中每個(gè)種群 中的局部 最優(yōu)解 迭代圖 ， 發(fā)現(xiàn)最后已 達(dá)到了 非常 穩(wěn)定 的 狀態(tài) 。 最后 我們 利用 新的 輸入矩陣檢驗(yàn)了 模型 的 魯棒性，發(fā)現(xiàn)類似地能得到 非常好 的調(diào)度方案 ， 這說(shuō)明 模型魯棒性良好 。 然后分析了模型的優(yōu)缺點(diǎn) 并提出了 改進(jìn)方向。 關(guān)鍵詞 ：生產(chǎn)調(diào)度問(wèn)題 遺傳算法 種群 染色體 目錄 摘要 ............................................................................................................................................. 1 1. 問(wèn)題重述 .............................................................................................................................. 3 2. 遺傳算法簡(jiǎn)介 ....................................................................................................................... 3 基本內(nèi)容 ....................................................................................................................... 3 遺傳算法求解調(diào)度問(wèn)題的優(yōu)越性 ............................................................................... 5 3. 模型建立 ................................................................................................................................ 7 基本思想概述 .................................................................................................................... 7 生產(chǎn)調(diào)度問(wèn)題的數(shù)學(xué)描述 .................................................................................................. 7 仿真過(guò)程 ........................................................................................................................... 9 編碼 ............................................................................................................................ 9 生成初始種群 ............................................................................................................. 9 適應(yīng)度函數(shù) ................................................................................................................. 9 選擇算子 ....................................................................................................................10 交叉算子 ....................................................................................................................10 變異算子 ....................................................................................................................11 4. 仿真結(jié)果 ...............................................................................................................................11 5. 模型檢驗(yàn)與魯棒性分析 .........................................................................................................12 6. 模型的優(yōu)缺點(diǎn)和改進(jìn)方向 .....................................................................................................12 7. 參考文獻(xiàn) ...............................................................................................................................13 8. 附錄 ......................................................................................................................................13 附錄一：初始化種群的代碼 .........................................................................................13 附錄二：計(jì)算一個(gè)方案對(duì)應(yīng)的總時(shí)間和適應(yīng)度的代碼 .................................................15 附錄三：計(jì)算一種方案對(duì)應(yīng)的被選中概率的代碼 ........................................................17 附錄四：選擇、交叉和變異過(guò)程的代碼 .......................................................................18
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1