畢業(yè)設(shè)計-基于遺傳算法的高校網(wǎng)上排課系統(tǒng)-資料下載頁
2024-12-02 13:57本頁面
【導(dǎo)讀】在傳統(tǒng)遺傳算法的基礎(chǔ)上，首先把問題分解以。減少算法的復(fù)雜度，然后提出了適合本問題的染色體編碼方案和操作方法，以盡量減少非法個體，最后使用和C#實現(xiàn)了一個網(wǎng)上自動排課系統(tǒng)，并使用本學(xué)院的真實數(shù)據(jù)進行測試，滿足所用的約束條件，產(chǎn)生了滿意的結(jié)果。
【正文】 0 6000代數(shù)適應(yīng)度適應(yīng)度 圖 42 加入波茲曼變比未加入優(yōu)化函數(shù) 加入波茲曼變比并加入優(yōu)化函數(shù)的條件下 ，進行了 6 次實驗，結(jié)果如 表 41 所示。 表 41 加入波茲曼變比和優(yōu)化函數(shù)的實驗結(jié)果 代數(shù) 適應(yīng)度 1 適應(yīng)度 2 適應(yīng)度 3 適應(yīng)度 4 適應(yīng)度 5 適應(yīng)度 6 0 1 2 3 4 5 1 1 1 6 7 8 9 1 1 10 1 8 在 實驗一和實驗二中，我們發(fā)現(xiàn)算法經(jīng)常收斂于局部最優(yōu)解，我們采取的方法是保留若干最優(yōu)個體，然后把其他適應(yīng)度相同的個體重新 初始化 的方法。 加入變比之前， 算法初期，產(chǎn)生更優(yōu)解的時間間隔比較平均，到了 算法后期（ 2500 代以后）， 隨著種群適應(yīng)度的提高，進化壓力越來越大， 時間 間隔越來越長 ， 產(chǎn)生 更 優(yōu)解 就變得十分困難 。 最后也沒有產(chǎn)生最優(yōu)解（適應(yīng)度為 1 的解），主要是由于不滿足彈性約束 2，其他條件可以較好滿足。 加入變比以后， 由于能夠以一定概率選擇 較差 的解，種群的適應(yīng)度更好， 產(chǎn)生更優(yōu)解的時間間隔更為平均 ，最后產(chǎn)生解的適應(yīng)度更高，用的時間反而更短。 在實驗三中，由于優(yōu)化函數(shù)實際是把 染色體中的不良基因有目的性的進行修正，修正時也 使用隨機函數(shù)隨機選擇 合適的時間段， 這樣 既增加了種群的適應(yīng)度，還 增加了種群的多樣性 ，避免了收斂于局部最優(yōu)解的問題 。這種變化在初始化（第 0 代）和進化第1 代個體的適應(yīng)度中表現(xiàn)的尤為明顯 ，初始化種群中最優(yōu)個體的適應(yīng)度在 左右， 第一代的適應(yīng)度在 左右， 僅用一代就 至少 提高了 ，達到了實驗 2 需進化 5000代才能達到的適應(yīng) 度 。 并且在 10 代以內(nèi)就可以找到最優(yōu)解，使適應(yīng)度達到 1，大大減少了排課時間，提高了排課效率。 交叉和變異函數(shù)以班為單位，對原有的染色體破壞程度較小，尤其是變異函數(shù)， 我們發(fā)現(xiàn) 經(jīng)過變異操作適應(yīng)度一般不會降低 ，具體原因還有待探究 。 當(dāng)然，與實驗 1 和實驗 2 相比，實驗 3 添加一些輔助的數(shù)據(jù)結(jié)構(gòu)和函數(shù)，占用的內(nèi)存資源更多，每代計算的時間更長，但最終用時（ 4min）比原來（ 20min）大大減低，隨著計算機內(nèi)存的不斷增大和處理器能力的不斷增強，這個問題就越來越不明顯了。 5 總結(jié) 本文在使用傳統(tǒng)遺傳算法解決時間表問題的基礎(chǔ)上， 減小 了問題的復(fù)雜度，提出了自己的編碼方案和操作方法，并大膽加入優(yōu)化函數(shù) ， 不僅 有效解決了陷于局部最優(yōu)解的問題，并 且在排課時的能夠根據(jù)排課時產(chǎn)生的沖突調(diào)用相應(yīng)的優(yōu)化函數(shù)進行優(yōu)化處理，使排課效率大大提高。 不僅提出了完整的解決方案，并且對遺傳算法解決時間表問題進行了有益的探索， 在 解決其它問題時 也 具有 借鑒意義 。 致謝 本論文的工作是在我的導(dǎo)師 董兆安老師 的悉心指導(dǎo)下完成的，導(dǎo)師淵博的知識、嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度、科學(xué)的工作方法、勤奮的敬業(yè)精神給了我極大的幫助和影響，讓我受益匪淺，在本文完成之際，衷心感謝導(dǎo)師對我的關(guān)心和指導(dǎo)。 在 開 發(fā)系統(tǒng) 及撰寫論文期問， 同組的馬義凱、王丙景、邢兆林 同學(xué)對我論文及研究工作給予了熱情幫助，在此向他們表達我的感激之情。 衷心感謝在我漫長的求學(xué)過程中，給予我無私幫助的眾多老師、同學(xué)們。感謝我的家人，他們的理解和支持使我能夠完成我的學(xué)業(yè)。 借此機會，向在百忙中抽出時間評審本文的專家表示衷心的感謝 ! 參考文獻 [1] Gotlieb,.The Construction of ClassTeacher TimeTables [C], Proceedings of the IFIP Congress., 1962, NorthHolland Pub. Co., Amsterdam: 7377 [2] Erben,W. and Keppler, J. A Geic Algorithm Solving a Weekly Course Timetabling Problem[M], in Practice and Theory of Automated Timetabling, SpringerVerlag Lecture Notesin Computer Science 1153, Burke amp。 Ross, eds., 1996 [3] , , . A Hybrid Geic Algorithm Approach to a Departmental Class Timetabling Problem Using Efficient Data Structures[J] ,2021 International Journal of Computer Applications, 2021,Volume 1 – No. 17:117121 9 [4] Antariksha Time Table Scheduling Using Geic Artificial Immune Network[C], art, 2021 International Conference on Advances in Recent Technologies in Communication and Computing, 2021:289292, [5] 滕姿，鄭輝文，楊久俊 .基于遺傳算法的排課系統(tǒng)的設(shè)計與實現(xiàn) [J]，計算機應(yīng)用， 2021 年 12 月，(27)： 199204 [6] 黃杰 ， 陳琳 ， 鄒鵬 .一種求解極小診斷的遺傳模擬退火算法 [J], 軟件學(xué)報 ,2021年 09 期 ， (15)：13451350 [7] （美）布克蘭德 ， 游戲編程中的人工智能技術(shù) [M]， 吳祖 增，沙鷹 ，譯 .北京 ， 2021 附錄 實驗 一 和實驗二 的數(shù)據(jù) 實驗一 實驗二 代數(shù) 適應(yīng)度 代數(shù) 適應(yīng)度 601 640 623 724 645 811 682 830 747 855 769 922 812 955 821 989 845 1036 864 1065 1407 1098 1422 1138 1467 1144 1483 1180 1682 1287 1743 1314 1766 1323 2055 1346 2073 1570 2095 1596 2287 1649 2312 1938 3063 1971 3090 2025 3493 2661 3526 2742 5564 2868 5591 2936 3098 3931 3997 4339 4354 4674 10 4814
公司管理相關(guān)推薦
鄂ICP備17016276號-1