高校自動排課系統的算法研究與實現

2024年2月26日發(作者：藍莓采摘)

重慶大學碩士學位論文高校自動排課系統的算法研究與實現姓名：湛德照申請學位級別：碩士專業：計算機技術指導教師：何中市;高宏賓20061001

重慶大學碩士學位論文中文摘要摘要目前，隨著我國高校教育事業的不斷發展，課程編排問題在一定程度上影響著教學質量的提高。為了保證教學質量，高校必須制定一套嚴密、規范的教學計劃和執行合理的課程安排。而課程編排是比較繁重而關鍵的一環。回顧過去，１９６３年，Ｃ．Ｃ．Ｇｏｆｌｉｅｂ在文章《ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆＣｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ）中提出了課表編排的數學模型，它標志著課程編排課題的研究正式跨入了莊嚴的科學殿堂。１９７６年，ＳＥｖｅｎ在論文《ｏｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙＦｌｏｗＰｒｏｂｌｅｍｓ》，第一次證明了課表是ＮＰ完全問題。在國內，清華大學于１９８４年在《清華大學學報（自然版）》上發表了林漳希和林堯瑞在該課題上的實驗性研究成果，接著國內部分高等院校相繼開展了這方面的研究工作。本文分析了排課的數學模型，提出了利用遺傳算法解決排課問題的方法，完成的主要工作如下：①探討課程表問題的約束因素，以優化時間和空間兩種資源為目標，通過對比，我們發現采用遺傳算法去解決課表問題是比較理想的解決方法，并討論了它的基本原理、步驟及其產生、發展、現狀以及存在的問題等情況。②改進時間安排算法：遺傳算法有能簡化程序的復雜度和生成最佳課表時間的優點，本論文提出的時間安排算法以經典遺傳算法作為基礎，進行了以下幾個方面研究工作：１）對遺傳算法存在的缺陷進行改進和優化，避免了遺傳算法出現未成熟就收斂等問題；２）提出排課問題的優化求解模型和約束滿足模型；３）針對排課問題研究了染色體編碼方式以及遺傳操作算子的設計，提出了一種適應度計算方法，由節次優度、日組合優度等相互聯系求解。③提出教室安排算法：排課問題中，除了時間安排外，為課程選擇一個教室是十分重要的，我們提出了教室安排算法，實現資源優化配置。④系統的實現：針對課表個性化的要求，設置了排課知識庫和策略庫來動態地調整準則，以滿足不同課表要求，體現該系統具有良好的適用性和實用性。本文以五邑大學排課系統的開發為背景，對整個系統的工作進行了分析總結，并對后續工作進行了展望。關鍵詞：排課，遺傳算法，組合優化，人工調整

重慶大學碩士學袋論文茭文攮要ＡＢＳＴＲＡＣＴＲｅｃｅｎｔｌｙ，ｗｉｔｈｔｈｅｃｏｎｓｔａｎｔｌｙｄｅｖｅｌｏｐｍｅｎｔｏｆｈｉｇｈｅｄｕｃａｔｉｏｎ，ｔｉｍｅｔａｂｌｉｎｇｈａｓｖｅｒｙｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｒｉｓｉｎｇｔｈｅｅｄｕｃａｔｉｏｎｑｕａｌｉｔｙ．Ｉｎｏｒｄｅｒ協ｇｕａｒａｎｔ∞ｉｔｓａｄｖａｎｃｅｄｔｅａｃｈｉｎｇａｎｄｓｔｕｄｙｉｎｇｑｕａｌｉｔｙ，ａｕｎｉｖｅｒｓｉｔｙｍｕｓｔｄｒａｗｕｐａｔｉｇｈｔａｎｄｓｔａｎｄａｒｄｔｅａｃｈｉｎｇｏｎｅａｎｄｓｔｕｄｙｉｎｇｐｌａｎａｎｄＣａｌＴｙｏｕｔｔｈｅｒｅａｓｏｎａｂｌｅｔｉｍｅｔａｂｌｉｎｇ．Ｔｈｅｔｉｍｅｔａｂｌｉｎｇｉｓｏｆｔｈｅｈｅａｖｙａｎｄｋｅｙｑｕｅｓｔｉｏｎｓ．Ｉｎ１９６３，Ｃ．Ｃ．ＧｏｔｌｉｅｂｐｒｏｐｏｓｅｄｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆＣｕｒｒｉｃｕｌｕｍＳｃｈｅｄｕｌｅＰｒｏｂｌｅｍ（ＣＳＰｆｏｒｓｈｏｒｔ）ｉｎｔｈｅｐａｐｅｒ（ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆＣｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ｝，ｉｔｓｙｍｂｏｌｉｚｅｄｔｈｅｒｅｓｅａｒｃｈｉｎｇｏｆＣＳＰｈａｄｅｎｔｅｒｔｈｅｓｃｉｅｎｃ宅ｄｏｍａｉｎｆｉｅｌｄ．Ｉｎ１９７６，Ｓ．Ｅｖｅｎｐｒｏｖｅｄｔｈｅｐａｐｅｒ（ＯｎｔｈａｔＣＳＰｉｓａＮＰ—ＣｏｍｐｌｅｔｅｄｐｒｏｂｌｅｍｉｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙＦｌｏｗＰｒｏｂｌｅｍｓ》Ｃｈｉｎａ，Ｔｓｉｌｌｇｈｕａｕｎｉｖｅｒｓｉｔｙｄｅｌｉｖｅｒｅｄｔｈｅｆｏｒｆｉｒｓｔｔｉｍｅ．Ｉｎｅｘｐｅｒｉｍｅｎｔａｌｌｙｒｅｓｅａｒｃｈｅｄｒｅｓｕｌｔｏｆｚ｝ｌａｎｇｘｉＬｉｎａｎｄＹａｏｒｕｉＬｉｎａｂｏｕｔｔｈｉｓｐｒｏｂｌｅｍｉｎ（ＪＯＵＲＮＡＬＯＦＴＳＩＮＧＨＵＡＵＮＷＥＲＳＩＴＹ（ＳＣＩＥＮＳＥＡＮＤｎａｔｉｖｅＴＥＣＮＯＬＯＧＹ））。Ｓｕｂｓｅｑｕｅｎｔｌｙ，ｐａｒｔｓｏｆａｂｏｕｔｔｈｉｓｏｔｈｅｒｕｎｉｖｅｒｓｉｔｉｅｓａｌｓｏｂｅｇａｎｒｅｓｅａｒｃｈｉｎｇｗｏｒｋｐｒｏｂｌｅｍ．ＴｈｅＧｅｎｅｔｉｃｍａｔｈｅｍａｔｉｃｓｉｓｍｏｄｅｌｏｆｔｉｍｅｔａｂｌｉｎｇｉｓｄｉｓｃｕｓｓｅｄｉｎｔｈｉｓｐａｐｅｒ，ｍｅａｎｗｈｉｌｅｔｈｅｔｏＡｌｇｏｒｉｔｈｍ（ａＡ）ｉｓｕｓｅｄｒｅｓｏｌｖｅｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｔｈｅｍａｉｎｗｏｒｋｏｆｔｈｉｓｐａｐｅｒｌｉｓｔｅｄａｓｆｏｌｌｏｗｓ：ｐａｐｅｒｄｉｓｃｕｓｓｅｓｎｕｍｅｒｏｕｓｃｏｎｓｔｒａｉｎｔｓｉｎｖｏｌｖｅｄｉｎｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，④ＴｈｉｓｗｈｏｓｅａｉｍｉＳｔｏｏｐｔｉｍｉｚｅｔｈｅｔｗｏｒｅ搭ｏｕｌ＇ｃｅｓｏｆｔｉｍｅａｎｄａｐａｃｅ．Ｃｏｍｐａｒｉｎｇ讞像ｖａｒｉｏｕｓＡｌｇｏｒｉｔｈｍｔｏｒｅｓｏｌｖｅｔｈｅｍｅｔｈｏｄｓ，ｗｅｆｉｎｄｔｈａｔｉｔ’ＳａｎｉｄｅａｌｍｅｔｈｏｄｔｏａｄｏｐｔＧｅｎｅｔｉｃｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ａｎｄｄｉｓｃｕｓｓｉｔｓｂａｓｉｃｐｒｉｎｃｉｐｌｅ，ｓｔｅｐａｎｄｉｔｓｃｒｅａｔｉｏｎ，ｄｅｖｅｌｏｐｍｅｎｔ，ｉｎｔｈｉｓｐａｐｅｒａｓｆｏｌｌｏｗｓ：ａｎｄｍａｋｉｎｇｔｈｅｂｅｓｔａｒｅｐｒｅｓｅｎｔｃｏｎｄｉｔｉｏｎａｎｄｅｘｉｓｔｅｎｔｐｒｏｂｌｅｍｅｔｅ．＠ＴｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍｉｓｇｉｖｅｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｈａｓｔｈｅａｄｖａｎｔａｇｅｓｏｎｏｆｓｉｍｐｌｉｆｙｉｎｇｐｒｏｃｅｄｕｒｅｔｉｍｅｔａｂｌｅ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｂａｓｅｄａｓｆｏｌｌｏｗｉｎｇ：１）ＭａｋｅｓｏｍｅｃｌａｓｓｉｃＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ．ＴｈｅｍａｉｎｃｏｎｔｅｎｔｏｎｉｍｐｒｏｖｅｍｅｎｔｓａｎｄｏｐｔｉｍｉｚａｔｉｏｎａｐｐｅａｒｉｎｇｔｈｅｃｌａｓｓｉｃＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ａｎｄｉｍｍａｔｕｒｅａｖｏｉｄｔｈｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｖａｒｉｏｕｓｐｒｏｂｌｅｍｓｓｕｃｈ嬲ｃｏｎｖｅｒｇｅｎｃｅ；２）Ｗｏｒｋｏｕｔｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｆｏｒｒｅｓｏｌｖｉｎｇａｎｄｃｏｎｓｔｒａｉｎｔｓｔｕｄｉｅｄｃｈｒｏｍｏｓｏｍｅｃｏｄｉｎｇａｎｄｈｅｒｅｄｉ移ｏｐｅｒａｔｏｒａｍｏｄｄｉｎｔｉｍｅｔａｂｔｉｎｇｄｅｓｉｇｎｉｎｇａｉｍｅｄａｔｐｒｏｂｌｅｍ；３）Ｗｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ｐｕｔｆｏｒｗａｒｄｆｉｔｎｅｓｓｃｏｍｐｕｔａｔｉｏｎｍｏｄｅｆｒｏｍｓｌｏｔ－ｓｕｐｅｒｉｏｒ，ｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ—ｄａｙ．ｅｔｃ．Ｃｏｎｔａｃｔｓｔｏｓｏｌｖｅｍｕｔｕａｌｌｙ．ｖｅｒｙ③Ｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｒｉｔｈｍ：ＢｅｓｉｄｅｓＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍ，ｉｔ’Ｓ玨

重慶丈學碩士學藏論文英文接要ｉｍｐｏｒｔａｎｔｏｕｔｔｏｃｈｏｏｓｅａｃｌａｓｓｒｏｏｍｆｏｒａｃｏＢｒｓｅｉｎｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｗｅｈａｄｗｏｒｋｅｄｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｄｔｈｍ，ｏｐｔｉｍａｌａｌｌｏｃａｔｉｏｎｏｆｒｅｓｏｕｒｃｅｓｉｓｇｕａｒａｎｔｅｅｄ．④Ｔｈｅｒｅａｌｉｚａｔｉｏｎｏｆｔｈｅｓｙｓｔｅｍ：Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｐｅｒｓｏｎａｌｒｅｑｕｅｓｔｏｆｔｉｍｅｔａｂｌｅ，ＷｅｅｓｔａｂｌｉｓｈｅｄｔｈｅｔｉｍｃｔａｂｌｉｎｇＫｎｏｗｌｅｄｇｅＬｉｂｒａｒｙａｎｄＳｔｒａｔｅｇｙＬｉｂｒａｒｙｔｏａｄｊｕｓｔｔｈｅｓｔａｎｄａｒｄｗｉｔｈｓａｔｉｓｆａｃｔｉｏｎｆｏｒｄ｛ｆｆｅｒｅｎｔｔｉｍｅｔａｂｌｅｒｅｑｕｅｓｔｓ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｓｙｓｔｅｍｄｅｖｅｌｏｐｅｄｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍｈａｓｇｏｏｄａｄａｐｔａｂｉｌｉｔｙａｎｄａｖａｉｌａｂｉｌｉｔｙ．ＴｈｉｓｐａｐｅｒｔｏｏｋｔｈｅｅｘｐｌｏｉｔａｔｉｏｎｉｎｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｔｉｍｃｔａｂｌｉｎｇｓｙｓｔｅｍｉｎＵｎｉｖｅｒｓｉｔｙ，ｃａｒｆｉｅｄｏｎａｌｌＷｕｙｉａｎａｌｙｔｉｃａｌｓｕｍｍａｒｙｆｏｒｔｈｅｗｈｏｌｅｗｏｒｋ，ａｎｄｍａｄｅａｎｏｕｔｌｏｏｋｔｏｔｈｅｆｏｌｌｏｗ－ｕｐｗｏｒｋ．Ｋｅｙｗｏｒｄｓ：Ｔｉｍｅｔａｂｌｉｎｇ，ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＣｏｍｂｉｎａｔｉｏｎＯｐｔｉｍｉｚａｔｉｏｎ，ＩＩＩ

獨創性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。據我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經發表或撰寫過的研究成果，也不包含為獲得重麼盍堂或其他教育機構的學位或證書而使用過的材料。與我一同工作的對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。學位論文作者簽名：配乙簽字日期：幽／年，一月≠日學位論文版權使用授權書本學位論文作者完全了解重麼盍堂重鏖太堂有關保留、使用學位論文的規定，有權保留并向國家有關部門或機構送交論文的復印件和磁盤，允許論文被查閱和借閱。本人授權可以將學位論文的全部或部分內容編入有關數據庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。保密（本學位論文屬于不保密（）。），在——年解密后適用本授權書。（請只在上述一個括號內打“√”）學位論文作者簽名：茫睨簽字日期：幽占年膳月年日郢繇銣手簽字日期：之勵緝ｆ礦月ｙ日

重慶大學碩士學位論文１緒論１緒論１．１排課問題的提出及研究意義高校的排課是教學管理中最基本、最重要、十分繁重而復雜的工作，它涉及到全校全部的專業，全部的師生和全部的課程，它的本質就是為所有的課程安排一組適當的教學時間和地點，使教學能夠順利進行。隨著各高校的招生規模擴大，教師和教室資源顯得越發緊張，使得本來就有難度的排課越發困難。課表的編排屬于一類涉及多種因素的組合規劃問題【ｌ】，它必須使課程安排中的教室、教師和學生不發生沖突，這是最基本的要求，在此基礎上要盡量滿足教師提出的其它要求（比如某教師要求只是上午上課，必須在多媒體教室上課等等）和學校教室資源的約束。在人工排課的過程中，實現這樣的要求是有一定困難的，為學校排出一個可行的課表要排課工作人員耗費兩到三個月的時間，工作量非常大，而且排出來的結果也未必盡人意。隨著各高校的教育體制改革的深入和招生規模的進一步擴大，手工排課的缺點越顯突出，我校的情況更為嚴重，因為教師和教室資源的限制，排課非常困難。而計算機恰好能幫助解決這個問題，它具有自動運行、計算速度快等特點，只要有相應的軟件系統，就能很好地解決排課的困難，實現教學管理決策的科學化。１．２國內外計算機自動排課的研究歷史５０年代末，國外就有人開始研究課表編排問題。１９６２年，Ｇｏｔｌｉｅｂ曾提出一個課表問題的數學模型怛】，并使用匈牙利算法解決了三維線性運輸問題。此后，人們對課表問題的算法、解的存在性等問題做了很多深入探討，但是大多數文獻所用到的數學模型都是Ｇｏｆｌｉｅｂ的數學模型的簡化或補充。近５０年來，人們對課表問題的計算機解法做了許多嘗試。其中，有人將課表編排的整數規劃模型問題歸結為求一組Ｏ．１變量的解，但是其計算量非常大，而且解決Ｏ．１線性優化問題的分支定界技術卻只適用于規模較小的課表編排；Ｍｉｈｏｅ和Ｂａｌａｓ（１９６５）將課表公式化為一個優化問題【３】；另外還有人提出將它當作一種線性編程的方法或將課表問題簡化為三維運輸問題；而Ｔｒｉｐａｔｈｙ則把課表問題視作整數線性編程問題并提出了大學課表的數學模型［４１；此外，有些文獻試圖從圖論的角度來求解課表問題，但是圖的染色問題也是ＮＰ完全問題，只有在極為簡單的情況下才可以將課表編排轉化為二部圖匹配問題吲。這樣的數學模型與實際相差甚遠，所以對于大多數學校的課表編排問題來說沒有實用的價值。進入九十年代以后，國外對課表問題的研究仍然十分活躍，比較有代表性的有印度的Ｖａｓｔａｐｕｒ大學管理學院的Ａｒａｂｉｎｄａ

重慶大學碩士學位論文１緒論Ｔｒｉｐａｔｈｙ、加拿大Ｍｏｎｔｒｅａｌ大學的ＪｅａｎＡｕｂｉｎ和ＪａｃｑｕｅｓＦｅｒｌａｎｄ等。對于課表的編排，已經使用的的算法有：關聯規則ＦＰ．ｇｒｏｗｔｈ算法１６１、基于時間位圖迭加匹配的算法‘７１、基于資源匹配的算’法【８１、分組優化決策算法【９】、分支定界法【１０１、有限回溯法【ｌｌ】，拉格朗日松弛法，二次分配型法等多種方法。由于課表約束復雜，用數學方法進行問題描述時往往導致問題規模劇烈增大，這已經成為應用數學編程解決課表問題的巨大障礙。外國的研究表明，解決大規模課表編排問題單純靠數學方法是行不通的，而利用運籌學中分層規劃的思想將問題分解，將是一個有望成功的辦法ｍ】。在國內，對課表問題的研究開始于８０年代初期，具有代表性的有：南京工學院的ＵＴＳＳ（ＡＵｎｉｖｅｒｓｉｔｙＴｉｍｅｔａｂｌｅＳｃｈｅｄｕｌｉｎｇＳｙｓｔｅｍ）系統【１３】，清華大學的ＴＩＳＥＲ系統ｎ４】，大連理工大學的智能教學組織管理與課程調度系統【１５ｌ，西南交通大學在分析高校課表編排所遵循的基本原則和模糊性原則的基礎上，定義了課元之間關于教師的相關關系和關于自然班的相關關系，提出了以課元相關運算和課元的候選時空片計算為核心的計算機排課算法１１６１，延邊大學根據高校課程表的制作特點，設計了計算機自動排課的數據結構與算法【１７】；沈陽電力高等專科學校研制了基于Ｃｌｉｅｎｔ／Ｓｅｒｖｅｒ的開放式智能排課系統［１８１等。使用遺傳算法來求解排課問題也有較多其它相關的報道【１９．２４１，還有～些其它高校根據自己的情況編寫了一些程序去實行計算機自動排課，例如浙江大學的“教務管理系統”等等。這些系統大都是模擬手工排課過程，以“班”為單位，運用啟發式函數來進行編排，都或多或少存在問題。２

重慶大學碩士學位論文２遺傳算法的設計思想２遺傳算法的設計思想遺傳算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，ＧＡ）研究的歷史并不算長，２０世紀６０年代末期到７０年代初期，主要由美國Ｍｉｃｈｉｇａｎ大學的ＪｏｈｎＨｏｌｌａｎｄ與其同事、同學們研究，從試圖解釋自然系統中生物的復雜適應過程入手，模擬生物進化的機制來構造人工系統的模型，形成了較完整的理論和方法。隨后經過２０余年的發展，取得了豐碩的應用成果和理論研究的進展，特別是近年來的進化計算熱潮，計算智能己作為人工智能研究的一個重要方向，以及后來的人工生命研究興起，使遺傳算法受到廣泛的關注。從１９８５年在美國卡耐基·梅隆大學召開的第一屆國際遺傳算法會議（ＩｎｔｅｒｎａｔｉｏｎａｌＩＥＥＥ的ＴｒａｎｓａｃｔｉｏｎｓｏｎＣｏｎｆｅｒｅｎｃｅＯｌｌＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ：ＩＣＧＡ＇８５）到１９９７年５月ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ創刊，遺傳算法作為具有系統優化、適應和學習的高性能計算和建模方法的研究漸趨成熟。２．１遺傳算法的產生與發展早在２０世紀５０年代和６０年代，就有少數幾個計算機科學家獨立地進行了“人工進化系統”的研究，其出發點是進化的思想可以發展成為許多工程問題的優化工具。早期的研究形成了遺傳算法的雛形，比如大多數系統都遵行“適者生存”的仿自然法則，有些系統采用了基于種群（ｐｏｐｕｌａｔｉｏｎ）的設計方案，并且加入了自然選擇和變異操作，還有一些系統對生物染色體編碼進行了抽象處理。６０年代初期，柏林工業大學的Ｉ．Ｒｅｃｈｅｎｂｅｒｇ和Ｈ．ＥＳｅｈｗｅｆｅｌ等在進行風洞實驗時，由于設計中描述物體形狀的參數難以用傳統方法進行優化，因而利用生物變異的思想來隨機改變參數值，并獲得了較好的效果。隨后，他們對這種方法進行了深入的研究，形成了進化計算的另外一個分支——進化策略（ＥｖｏｌｕｔｉｏｎａｒｙＳｔｒａｔｅｇｙ，ＥＳ），如今Ｅｓ和ＧＡ已呈融合之勢。同樣是在２０世紀６０年代，Ｌ．Ｊ．Ｆｏｇｅｌ等人在設計有限態自動機（ＦｉｎｉｔｅＳｔａｔｅＭａｃｈｉｎｅ，ＦｓＭ）時提出了進化規劃（ＥｖｏｌｕｔｉｏｎａｒｙＰｒｏｇｒａｍｍｉｎｇ，ＥＰ），借用進化的思想對一組ＦＳＭ進行進化，以獲得較好的ＦＳＭ。他們將此方法應用到數據診斷、模式識別和分類及控制系統的設計等問題中，取得了較好的結果。后來又借助進化策略方法發展了進化規劃，并用于數值優化及神經網絡的訓練等問題中。由于缺乏一種通用的編碼方案，人們只能依賴變異而非交叉（即是雜交）來產生新的基因結構，早期的算法收效甚微。２０世紀６０年代中期，ＪｏｈｎＨｏｌｌａｎｄ在Ａ．Ｓ．Ｆｒａｓｅｒ和Ｈ－Ｊ．Ｂｒｅｍｅｒｍａｎｎ等人工作的基礎上提出了位串編碼技術。這種編碼既適用于變異操作，又適用于交叉操作，并且強調將交叉作為主要的遺傳操作。隨３

重慶大學碩士學位論文２遺傳算法的設計思想后，Ｈｏｌｌａｎｄ將該算法用于自然和人工系統的自適應行為的研究中，并于１９７５年出版了其開創性著作‘＇ＡｄａｐｔａｔｉｏｎｉｎＮａｔｕｒａｌａｎｄＡｒｔｉｆｉｃｉａｌＳｙｓｔｅｍｓ”。以后，Ｈｏｌｌａｎｄ等人將該算法加以推廣，應用到優化及機器學習問題中，并正式定名為遺傳算法。遺傳算法的通用編碼技術和簡單有效的遺傳操作為其廣泛、成功的應用奠定了基礎。Ｈｏｌｌａｎｄ早期有關遺傳算法的許多概念一直沿用到今天，可見Ｈｏｌｌａｎｄ對遺傳算法的貢獻之大。在其后，遺傳算法的應用無論是用來解決實際問題還是建模，其范圍不斷擴展，這主要依賴于遺傳算法本身的逐漸成熟。近年來，許多冠以“遺傳算法”的研究與Ｈｏｌｌａｎｄ最初提出的算法已少有雷同之處，不同的遺傳基因表達方式，不同的交叉和變異算子、特殊算子的引用以及不同的再生和選擇方法，但這些改進方法產生的靈感都來自大自然的生物進化，可以歸為一個“算法簇”。人們用進化計算來包容這樣的遺傳“算法簇”，它基本劃分為四個分支：遺傳算法（ＧＡ）、進化規劃（ＥＰ）、進化策略（ＥＳ）和遺傳程序設計（ＧＰ）。２．２生物進化理論和遺傳學的基本知識我們知道，生命的基本特征包括生長、繁殖、新陳代謝和遺傳與變異，生命是進化的產物，現代的生物是在長期的進化過程中發展起來的。達爾文用自然選擇（ｎａｔｕｒａｌｓｅｌｅｃｔｉｏｎ）來解釋物種的起源和生物的進化，其自然選擇學說包括以下三個方面：①遺傳（ｈｅｒｅｄｉｔｙ）：這是生物的普遍特征，“種瓜得瓜，種豆得豆”，親代把生物信息交給子代，子代按照所得信息而發育、分化，因而子代總是和親代具有相同或相似的性狀。生物有了這個特性，物種才能穩定存在。②變異（ｖａｒｉａｔｉｏｎ）：親代和子代之間以及子代的不同個體之間總有差異，這種現象稱為變異。變異是隨機發生的，變異的選擇和積累是生命多樣性的根源。③生存斗爭和適者生存：自然選擇來自繁殖過剩和生存斗爭。由于弱肉強食的生存斗爭不斷地進行，其結果是適者生存，具有適應性變異的個體被保留下來，不具有適應性變異的個體被淘汰，通過一代代的生存環境的選擇作用，物種變異被定向著一個方向積累，于是性狀逐漸和原先的祖先不同，演變為新的物種。遺傳算法模擬的是怎樣的生物進化模型呢？假設對相當于自然界中的一群人的一個種群進行操作，第一步的選擇是以現實世界中的優勝劣汰現象為背景的；第二步的重組交叉則相當于人類的結婚和生育；第三步的變異則與自然界中偶爾發生的變異是一致的。人類偶然出現的返祖現象便是一種變異。由于包含著對模式的操作，遺傳算法不斷地產生出更加優良的個體，所采用的遺傳操作都與生物尤其是人類的進化過程相對應。如果我們再仔細分析遺傳算法的操作對象種群，４

重慶大學碩士學位論文２遺傳算法的設計思想實際上它對應的是一群人，而不是整個人類。一群人隨著時間的推移而不斷進化，并具備越來越多的優良品質。然而，由于他們生長、演變、環境和原始祖先的局限性，經過相當一段時間后，他們將逐漸進化到某些特征相對優勢的平衡態，當一個種群進化到這種狀態，這個種群的特性就不再有很大的變化了。一個簡單的遺傳算法，從初始代開始，并且各項參數都設定，也會到達平衡態。此時種群中的優良個體僅包含了某些類的優良模式，因為該遺傳算法的設置特性參數使得這些優良模式的各個串位未能得到平等的競爭機會。遺傳算法效法于自然選擇的生物進化，是一種模仿生物進化過程的隨機方法，下面先對幾個生物學的基本概念與術語進行解釋，以便理解遺傳算法。染色體（ｃｈｒｏｍｏｓｏｍｅ）：生物細胞中含有的一種微小的絲狀化合物，它是遺傳物質的主要載體，由多個遺傳因子——基因組成。遺傳因子（ｇｅｎｅ）：ＤＮＡ（脫氧核糖核酸）或ＲＮＡ（核糖核酸）長鏈結構中占有一定位置的基本遺傳單位，也叫做基因。表現型（ｐｈｅｎｏｔｙｐｅ）：由染色體決定性狀的外部表現，或者說，根據遺傳子型形成的個體，稱為表現型。基因型（１０ｃｕｓ）：遺傳基因在染色體中所占據的位置。個體（ｉｎｄｉｖｉｄｕａｌ）：染色體帶有特征的實體。種群（ｐｏｐｕｌａｔｉｏｎ）染色體帶有特征的個體的集合稱為種群。該集合內個體數稱為群體的大小。有時個體的集合也稱為個體群。進化（ｅｖｏｌｕｔｉｏｎ）：生物在其延續生存的過程中，逐漸適應其生存環境，使得其品質不斷得到改良，這種生命現象稱為進化，生物的進化是以種群的形式進行的。適應度（ｆｉｍｃｓｓ）：在研究自然界中生物的遺傳和進化現象時，生物學家使用適應度這個術語來度量某個物種對于生存環境的適應程度。對生存環境適應度較高的物種將獲得更多的繁殖機會，而對生存環境適應度較低的物種，其繁殖機會就相對較低。選擇（ｓｅｌｅｃｔｉｏｎ）：指決定以一定的概率從種群中選擇若干個體的操作。一般而言，選擇的過程是一種基于適應度的優勝劣汰的過程。復制（ｒｅｐｒｏｄｕｃｔｉｏｎ）：細胞在分裂時，遺傳物質ＤＮＡ通過復制而轉移到新產生的細胞中，新的細胞就繼承了舊細胞的基因。交叉（ｃｒｏｓｓｏｖｅｒ）：有性生殖生物在繁殖下一代時兩個同源染色體之間通過交叉而重組，亦即在兩個染色體的某一相同位置處ＤＮＡ被切斷，其前后兩串分別交叉組合形成兩個新的染色體。這個過程又稱基因重組，俗稱雜交。變異（ｍｕｔａｔｉｏｎ）：在細胞進行復制時可能以很小的概率產生某些復制差錯，

重慶大學碩士學位論文２遺傳算法的設計思想從而使ＤＮＡ發生某種變異，產生出新的染色體，這些新的染色體表現出新的性狀。編碼（ｃｏｄｉｎｇ）：ＤＮＡ中遺傳信息在一個長鏈上按一定的模式排列。２．３遺傳算法的基本思想問題域圖２．１遺傳算法的過程Ｆｉｇｕｒｅ２．１Ｔｈｅｐｒｏｃ％￥ｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ我們現在引用上面的術語描述遺傳算法的基本思想。遺傳算法是從代表問題６

重慶大學碩士學緞論文２邃鑄算法豹設圣｝思恕可能潛在解熊的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質的主要載體，即多個蒺因的集合，其內部襲現是某種基因綴合，它決定了個體的形狀的癸嫠表現，麴黧頭發憨鷙薤是耄象絕缽孛控豢ｌ這～黲縫戇菜莠基因綴會決定豹。因此，在一開始需要實現獲表璦熬掰基因靜映射編礴工作。由于仿照萋鞠編碼鮑工作復雜，我們將其進行簡化，如二進制編碼等。初代種群產生之后，按照適者生存和優勝鐒汰的原理，逐代演化產生出越來越好的近似解。在每一代，根據問題域中個體的適應度大小挑選個體，并借助于自然遺傳學的遺傳算予進行組合交叉移交異，產生爨健表頹豹瓣集｜！｝冬耱群。這個遙程將簿致秘囂像自然遴純～櫸鶼后生｛弋釋群鞋：虢代更鴦玨適應予環境，末代耱囂中的最傀個體經過解礙，Ｗ以作為問題近似最優解。遺傳算法采納了自然進化的模型，如選擇、交叉、變異、遷移、局城與領域等。基本遺傳舞法如圖２．１所示。計算開始對，～定數囂靜Ｎ個令體（父個體ｌ、父個體２、父個俸３、父令髂４……）幫秘群蘧襖Ｉ縫秘始純，著謗算每令令俸靜適應度函數，第一代毽鼯竊始代產生了。如果不滿足優化準則，開始產生新一代的計算。為了產生下一代，按照遁成度選擇個體，父代饕求基因重組（交叉）而產生子代。所肖的子代按一定概攀變異，然后子代的邈威度又被重新計算，子代被插入到種群中將父代取而代之，構成新的一代（子個體ｌ、子個體２、予個體３、子個體４……）。這攆熬過程德環執行，壹翼瀵是錢純準籍為壹。２．４遺傳算法的特點我們知邋，傳統的優化方法童娶有三種：枚舉法、啟發式算法和搜索算法：①枚舉法；枚舉出可以解集侖內的所有可以解，以求出精確最優嬲。對手連續函數，該方法要求先對箕逡行薅散億處理，這攆藏霹縫囂離教楚理瑟汰遠這蠶至《最優解。鼗歲｝，當枚舉空間院較大時，該方法的求解效率比較低，有時候甚至在目前最先讖計算機上也無法求解。②啟發試算法：尋求一種能產生可以解的啟發式規則，以找到一個最優解或者近似最優解。該方法的求解效幫比較高，但對每一個需求解的闖題必須找出其特毒夔寢發式羧照，這令建發式黢翅一般無逶愛蠖，零逶會手其毽翅題。③羧索黲法：尋求一種援索舞法，該算法在可行解集合的一個予集內送行援索操作，以找到問題的最優解或者近似最優解。該方法雖然保證不了～定能夠得到問題的最優解，但若適當地利用一些啟發知識，就Ｗ在近似解的質量和效率上達到一種較好的乎衡。７

重慶大學碩士學位論文２遺傳算法的設計思想隨著問題種類的不同以及問題規模的擴大，要尋求一種能以有限的代價來解決搜索和優化問題的通用方法，遺傳算法正為我們提供了一個有效的途徑，它不同于傳統的搜索和優化方法。主要區別在于：①自組織、自適應和自學習性（智能性）。應用遺傳算法求解問題時，在編碼方案、適應度函數及遺傳算法確定后，算法將利用進化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略為“適者生存，不適應者被淘汰”，因而適應度大的個體具有較高的生存概率，通常它們具有更適應環境的基因結構，再通過基因重組和基因突變等遺傳操作，就可能產生更適應環境的特性和規律的能力。自然選擇消除了算法設計過程中的一個最大障礙，即需要事先描述問題的全部特點，并要說明針對問題的不同特點算法應采取的措施。因此，利用遺傳算法的方法，我們可以解決那些復雜的非結構化問題。排課問題恰恰就是這樣的問題，所以用遺傳算法去排課是最好的方法。②遺傳算法的本質并行性。遺傳算法按并行方式搜索一個種群數目的點，而不是單點。它的并行性表現在兩個方面，一是遺傳算法是內在并行的，即遺傳算法本身非常適合大規模并行。最常見的并行方式是讓幾百甚至數千臺計算機各自進行獨立種群的演化計算，運行過程中甚至不進行任何通信（獨立的種群之間若有少量的通信一般會帶來更好的結果），等到運算結束時才通信比較，選取最佳個體。這種并行處理方式對并行系統結構沒有什么限制和要求，可以說，遺傳算法適合在目前所有的并行機或分布式系統上進行并行處理，而且對并行效率沒有太大影響。二是遺傳算法的內含并行性。由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內的多個區域，并相互交流信息。使用這種搜索方式，雖然每次只執行與種群規模ｎ成比例的計算，但實質上已進行了大約Ｏ（ｎ３）次有效搜索，這就使遺傳算法能以較少的計算獲得較大的收益。③遺傳算法不需要求導或者其他的輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數。④遺傳算法強調概率轉換規則，而不是確定的轉換規則。⑤遺傳算法可以更加直接地應用。⑥對給定的問題，遺傳算法可以產生許多潛在解，最終選擇可以由使用者確定。２．５遺傳算法的基本操作遺傳算法包括三個基本操作：選擇、交叉和變異。這些基本操作又有許多不同的方法，如下面所述。①選擇選擇是用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。首

重慶大學碩士學位論文２遺傳算法的設計思想先計算適應度：１）按比例的適應度計算；２）基于排序的適應度計算。適應度計算之后是實際的選擇，按照適應度進行父代個體的選擇。可以挑選以下算法：１）輪盤賭選擇；２）隨機遍歷抽樣；３）局部選擇；４）截斷選擇；５）錦標賽選擇；在選擇操作時會出現幾個問題：亂在遺傳進化的初期，通常會產生一些超常的個體，這些異常個體競爭力很ｂ．在遺傳進化的后期，即算法接近收斂時，由于種群中個體適應度差異較小上述的問題，我們通常稱為遺傳算法的欺騙問題，而適應度函數的設置就是遺傳算法在進化搜索中基本不利用外部信息，僅以適應度函數為依據，利用１）直接以待求解的目標函數轉化為適應度函數。即：若目標函數為最大化問題Ｆｉ“ｆ【ｘ））＝ｆ【Ｘ）若目標函數為最小化問題Ｆｉ“ｆ（ｘ））＝一ｆ（ｘ）這種適應度函數簡單直觀，但存在兩個問題，其一是可能不滿足常用的輪盤２）若目標函數為最小化問題，則：蹦鞴＿［ｃ：囂㈣姐一９突出，從而控制了選擇過程，影響算法的全局優化性能。時，繼續優化的潛能降低，可能獲得某個局部最優解，這不是我們所期待的。為了避免這些問題的產生。因此，適應度函數的設計是遺傳算法的一個重要方面。種群中每個個體的適應度值來進行搜索。因此適應度函數的選取至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優解。一般而言，適應度函數是由目標函數變換而成的。適應度函數基本有以下三種：賭選擇中概率非負的要求，其二是某些待求解的函數在函數值分布上相差很大，由此得到的平均適應度可能不利于體現種群的平均性能，從而影響算法的性能。其中Ｃ。。是舡）的最大值估計。若目標函數為最大化問題，則

重慶大學碩士學經論文２遺傳霧法麴設詩愚恕Ｆｉｔ（ｆ（ｘ）產ｆ婀一Ｇ一，取）＞ｃｍ“。０，其像這秘方法燕瓣第一靜方法懿改遴，霹敦髂為“爨隈羧造法”，毽壽時存凌爨限篷預先信詩露蕊、不精確的目逶。３）若目標函數為最小化問題：Ｆｉｔ（ｆｉｘ））＝１，（１＋ｃ＋ｆ（ｘ”Ｃ≥Ｏ，ｃ＋ｆ（ｘ）－蘭。若目標函數為最大化問題：Ｆｉｔ（ｆ（ｘ））＝ｌ／（１＋Ｃ一援ｘ））Ｃ≥瓴Ｃ－ｆ（ｘ）≥Ｏ這耪方法與第二靜方法類醞，Ｃ海囂括函數霧陵豹僳孝繼詩篷。適應度瞬數設計應該滿足以下幾個條件，它應該非負、連續、最大化、單值的：能夠反映解的優劣程度；應該盡量簡單，計算爨盡量小。②交叉藏簇邈重組基毽羹綴楚結合來童父戎交熬耱囂孛戇覆塞產囊灝煞今薅。依據令髂緩鵑表示方法的不麗，可以有以下的算法；１）實值煎組·離散爨組；●中聞黧綴；·線縫鬟綴；●擴展線餒重組。２）二遴制交叉·單點交叉；·多點交叉；●均勻交義；·洗簿交叉；●縮小代理交叉。③變異交叉之饜予代經歷的變異，嶷際上是子代基因按小概率擾動產生的變化。依據兮薅編羈襲零方法戇不囂，霹鞋蠢以下豹算法：１）實俊交霧；２１二進制變異。另外的操作覦括：扎交叉概率（Ｐｃ）和變異概率（Ｐｍ）

重慶大學矮士學像論文２蘧姥霧法豹竣詩思想交叉操作和變異操作并不是對所有個體都發生，而是根據相應的概幫。交叉概率和變異概率的選擇是影響遺傳算法行為和性能的關鍵所在，直接影響算法的收斂性，Ｐｃ越大，新個體產生的速度就越快，然而，遺傳模式被破壞的Ｗ能性也越太，搜褥其蠢意適應疫戇令傣縫掏綴抉裁菝破壞。艇蹩麴栗Ｐｅ過奪，會傻羧索過程緩慢，醵麓停滯不藏。對予變弊概率Ｐｍ，強聚遙小，裁不易產生贛靛個俸結構，如果Ｐｍ取值過大，那么遺傳算法就變成了純粹的隨機搜索算法。針對不同的優化問題，鬻簧反復實驗來確定Ｐｃ和Ｐｍ。ｂ．編碼（Ｅｎｃｏｄｉｎｇ）遺傳算法孛進化過程是建立農編碼輥割基礎上的，編碼對于算法盼黢鼴懿搜索愛力秘秘群多樣往等影穗攫丈。如何將問題的解轉換為編碼襲達的染色體是遺傳算法的關鍵問題。Ｈｏｌｌａｎｄ的編碼方法是二進制０．１串表達，熊優點是編碼、解碼操作簡單，交叉、變弗等遺傳操作便于實現，而且便于利用模裁定理進行理論分析鋅；其缺點是不便于反映所求問題的特定知識，對于一些連續溺數的優化問題，潮子遺傳算法的ｌ媳機特性使萁最熬搜索黢力較差，對于一整多緩、離穗度要求熬逡續函數髖純，二滋裁縭瑪存在著連續藪數離敖億時靜映射誤愛，個俸編碼串較斑時，可能這不至ｌ耪發要求，個體編碼串較長時，雖然能提高精度，但卻會使算法的搜索空間急劇擴大，從而造成遺傳算法的性能降低。后來許多學者對遺傳算法的編碼方式進行了多種改進，例如，為提黼局部搜索能力，提出的Ｇｒｅｙ碼等。遺傳算法黲一般流程匿如麓２＋２所示。第ｌ多；夔秘產生令體數囂～定豹裙始靜饕，褥個令俸表示受染色髂懿基毽編碼：第２步；計算個體的適應度，并判斷是否符合優化準則，若符合，輸出最佳個體及其代襲的最優解，并結束計算，否則轉向第３步；第３步；依攢適應度選擇再繳個體，適應度高的個體被選中的概率搿，相反，適應度低鶼令侮霹轆談海汰；第４步：按照一定的交叉概率鞍交叉方法，生成藏穩個體；第５步：按照一定的變異概率和變異方法，生成新的個體；第６步：豳交叉和變異產生新一代的種群，返回到第２步。遺傳算法中的優化準則，一般依據問題的不同肖不同的確定方式。例如，可班采用以下的準嬲之一幸＃為判斷祭終；１）釋群審今俸熬最丈適應發怒避預先設定篷；２）種群中個體的平均適應度越過預先設定值；３）世代數超過預先設定值。

重痰大學碩士學愛論交２遺傳舞渡瓣設計愚怒翻２．２遺黃算法的漉穰翻Ｆｉｇｕｒｅ２．２Ｔｈｅｆｌｏｗｃｈｍｔｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ２．６經典遺傳算法存在的缺陷及改進隨著理論和應用研究的日益深入，研究者們己經意識到，簡單采用網定不變的進化策略的遺傳算法對復雜的暾爝場合效果并不理想，傳統的遺傳算法逐漸暴露窶一些缺杰。為提褰遺轉算法戇投戇，誨多磅究者恐經致寵予這些趣囂戇繇究，并提出了一系列有效的解決方案。２．６．１初始種群的均勻化改進初始種群的特性對遺傳算法的計算結果和計算效率均有重要影響，臻窟現全局最優，初始種群在解空間中應盡爨分散。而經典的遺傳算法中，初始種群是隨機產生豹，這季中縋壤縫裁可麓導致鶿媲黲群在磐空窩分蠢熬不均勻，簌露影揀算法的往麓。霞魏，在產生裙始彈群鞋雩，應盡量使它筠麓分布在整個磐空蘺審。一種方法楚，為初始種群中的個體之間設置一個距離限制，要求入選柳始種群的各個體之間的距離必須大予這個限制距離，這樣就能保證初始種群的個體之間有較明顯的麓別，使它們能較均勻地分布在解空間中，保證了初始種群禽有較１２

重慶大學碩士學位論文２遺傳算法的設計思想為豐富的模式，從而增加搜索收斂于全局最優解的可能．另一種方法是，首先將解空間分割成若干個子空間，對每個子空間進行初始種群選擇，然后將每個子空間的初始種群進行合并，生成總的初始種群，那么這個種群中至少包含了來自不同子空間的個體。２．６．２自適應交叉概率和變異概率的改進前面我們說到了交叉概率和變異概率的選擇對遺傳算法非常重要，無論取值過大和過小都對算法產生不利影響，但是我們很難對一個優化問題確定一個合適的交叉概率和變異概率，因為遺傳環境在不斷的動態變化，所以，Ｐｃ和Ｐｍ應該能夠隨適應度自動改變，當種群各個體適應度趨于一致或者趨于局部最優時，使Ｐｃ和Ｐｍ增加，以增強新個體產生的能力；當群體適應度比較分散時，使Ｐｃ和Ｐｍ減小，加快群體的收斂。適應值高于平均適應值的個體，對應于較低的Ｐｃ和Ｐｍ，使該解得以保護進入下一代；適應值低于平均適應值的個體，對應于較高的Ｐｃ和Ｐｍ，使該解被淘汰掉。交叉概率和變異概率的這種自適應調整在保持了群體多樣性的同時，也保證了遺傳算法的收斂性。２．６．３選擇算子的改進在各種ＧＡ選擇策略中，基于個體適應度的比例選擇最為常用，該策略算法簡單，但是比較容易引起“未成熟收斂”和“搜索緩慢”等問題。“未成熟收斂”就是連續的幾代種群中的最優染色體沒有任何進化，或者各染色體之間過于近似等。在求解多峰值函數的優化計算時，經常只能找到個別的幾個最優解，甚至往往得到的是局部最優解，而我們希望的是得到全局最優解。解決這個問題的一種方法是采用基于小生境技術的選擇操作。在生物學上，小生境（Ｎｉｃｈｅ）是指特定環境中的一種組合功能。小生境技術就是將每一代個體劃分為若干類，每個類中選出適應度較大的個體作為一個類的優秀代表組成一個種群，再在種群中以及不同種群之間通過交叉和變異產生新的種群。小生境的模擬方法主要建立在對常規選擇操作的改進基礎上。Ｃａｖｉｃｈｉｏ在１９７０年提出了基于預選擇機制的選擇策略，其基本做法是：當新產生的子代個體的適應度超過其父代個體的適應度時，所產生的子代個體才能代替其父代個體而遺傳到下一代種群中，否則父代個體仍保留在下一代種群中．由于子代個體和父代個體之間編碼結構具有相似性，所以替換掉的只是一些編碼結構相似的個體，故它能夠有效地維持種群的多樣性，從而避免產生局部最優解，改善未成熟收斂。另一種方法是引入“遺傳一災變”算法，在ＧＡ的基礎上，進一步模擬自然界中的災變現象，以提高遺傳算法的性能，尤其是解決重要的未成熟收斂問題。當判斷可能發生了未成熟收斂時，施以災變來改變現狀。災變的形式很多，可以突然增大Ｐｍ，或對不同個體實施不同規模的突變，以產生大量的后代。用災變的方

重慶大學碩士學位論文２遺傳算法的設計思想法可以打破舊有基因的壟斷優勢，增加基因的多樣性，創造有生命力的新個體。第三種改進方法是引入濃度選擇機制，與適應度比例選擇機制相結合，采用加權平均的方式來進行選擇。這個方法由下面的式子來表示，其中Ｐ表示個體選擇的概率，Ｐｆ表示適應度概率，Ｐｄ表示濃度概率，ａ表示適應度概率所占的比重。Ｐ＝ａｘＰｆ＋（１一ａ）×Ｐｄ這個式子可以確保適應度高的個體，又抑制濃度高的個體，以保證個體的多樣性，改善未成熟收斂。２．６．４交叉和變異算子的改進遺傳算法通過交叉和變異這一對相互配合又相互競爭的算子，使自身的搜索能力得到快速提高，交叉操作在遺傳算法中起全局搜索的作用，它是遺傳算法的核心遺傳操作。變異操作在遺傳算法中起局部搜索的作用，當搜索陷入局部解而不能由交叉解決時，配合有效的變異可以使之躍出局部解。但是后期的變異可能破壞已經建立起來的最優解的雛形。因此，交叉和變異應很好的配合，不能盲目的進行操作，例如，采用自適應的算子，將進化過程分為漸進和突變兩個不同的階段，漸進階段強交叉，弱變異，強化優勢型選擇算子：突變階段弱交叉，強變異，弱化優勢型選擇算子。一種方法是：建立一個收斂程度參數ｂ，ｂ＝Ｆ仃。一Ｆ其中：Ｆ一為某代中最優個體適應度，Ｆ為此代種群平均適應度。因此ｂ近似反映了種群的收斂程度，ｂ越小，個體間適應度相差越小。ｂ越大，個體特性越分散，Ｐｃ，Ｐｍ應與ｂ成反比．同時為防止破壞全局最優解，對不同個體，Ｐｃ和Ｐｍ應不同。遺傳算法能夠很快地找到最優解的９０％，但是剩下的尋找最優解的工作卻要花費相當長的時間。２．６．５并行遺傳算法盡管單一種群的遺傳算法很強大，可以很好的解決相當廣泛的問題，但采用多種群（子種群）的算法往往會獲得更好的結果。每個子種群象單種群遺傳算法一樣獨立地演算若干代后，在種群之間進行個體交換。這種多種群遺傳算法更加貼近于自然中種族的進化，稱為并行遺傳算法（ＰａｒａｌｌｅｌｉｎｇＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ．ＰＧＡ）。遺傳算法發展的二十年里，針對各種不同領域，不同模式的優化問題，出現了很多變形和改進，經典的遺傳算法為我們提供了一個平臺，在這個平臺上可以搭建各種各樣的模型。隨著遺傳算法應用領域的擴大，相信更多的改進和變形會出現，遺傳算法家族將越來越壯大。介紹完遺傳算法，以及遺傳算法的各種改進后，下面我們就來介紹遺傳算法在課表問題中的應用，以及針對課表問題，對遺傳算法做的變形和改進。１４

重慶丈學矮圭學經論文３辯瀚安攖籜法３時間安排算法毫校熬瓣瀠是～頊費酵費力懿繁瑣工終，它牽涉至ｇ全搜熬頰生巍掰露諼程、所有教室。攤漾在整個過程孛充滿了矛詹運魂，其審憊疆上課班緩、耩殍諜程、任課教師一ｋ課時間、地點這個贏個方面在排列組龠中所發生的沖突和矛盾現象。課程門類多、教師少、教室少是攤課時發生沖突和矛盾的主要因素，麗濺綴多、教室少則是矛盾的重要方面，攤課就是要處理教學環節中的各種矛盾。接誤牽涉瀚因素綴多，毽都遵循這樣鮑原煲｜ｊ：諼袋裝壽秘于教學設餐熬充分蠢瘸，要騖會教學癱律。３．１排課需要考慮的約束因素排課是將教師與學優在時間和空間上根據不同的約束條件進行排列綴合，以搜教學正常避彳予，這里約束條件象要是為了避免沖突。沖突，包含的痰容綴多，蔻乎發生在矮露囂令或多令攘漂滲及煞囂素之闖。避兔猙突是籜謙楚題審黌緞決的核心問題。只有在滿足全部約窳條件和避免所有沖突的基礎上，才熊僳證整個教學計劃正常進行，而對教師、激室、學生及時間鐐幾部分資源進行最優化組合配置，才能保證充分發揮各資源的優勢。我們把攤漾過程中的約束條件分為三類：基本磁約柬、硬約束和軟約榮。其孛基奉疆終塞蔫海羧簿、學生秘教室在囂空土不藐發象猙突，宅是赫瀠懟緩孛最基本盼約束條伴；硬約束是根掭學校的實際情況，捺謙時必須遵循的原剛（如：我校中午和周米不排課，星期二下午不排課等習慣）；軟約束是指排課過稷中滿足更佳但不滿足又無妨的約束條件，它們的違反與否往徒與排課實際情況相笑。在三類約束條件之中，前兩者是衡熬攤課方案是否切實Ｗ行的標準，軟約束是衡量ｌ萋漂方案襞劣熬耩準。荬羲；毽分捌翔下：①基本硬約束：１）在同一時間同一學生不能上兩門不同的課程；２）在同～時間同一教室不能寂排兩門不同的課稷；３）在嗣一時間同一教師不能上兩門不同的課程。②硬豹絮；１）上課絞犬爺為單位詩舞（鍘斑：上午分ｌ、２犬第）；２）星期二下午不排課，星期六、日全天不排課；３）課程的學時在周分布上有～定的規律（例如：每周上３次的課程，一般是星期一、三、旋這三天安排上課鐐）；１５

重痰大學硬士學襞論文３孵麓安鏢算法４）某些課程有自己的特定資源（例如：英語專此課程必須有獨立的聽力系統等等）；５）教室空間必須足夠大，能夠容納上課（包括禽班）的學生；③軟約窳；１１班級諜稷襲在周安排上瑟瑟鱉分布均勻；２）一周課襲中每個時間有一定的優度；３）教師不推薦在時間上連續上課；４）教師對上課時間存在一定的喜好（例如：某老師喜歡下午上課等镩）５）班級躐巍上瀠建煮盡可笈避。怒要接激簸為理想靜謀表，熬躲須注意每震一次鑲繇我捧謙擎往時藤攫，學生的最佳用腦時間以及師生在教與學過程中的心理因索等，堅持合理間隔，充分利用教室空間。每個班的每門課程在一周內要間隔開上，讓學生分散理解和記憶，因為按照記憶——遺忘規律，一次記憶太多相似的內裙并不能記住，所以，要注意蛙質不司焱，強調個性，才能識率。醫既，應該改燹整個接捌，恕那黧個性強靜，與眾不醚瓣方囂，巧妙黧醵安攤，班瑟作秀記憶鶼獎壤，胃浚稷姆鑣箍嵩學生的學習效率，是一種比較好的攤諜方法。在以往的管理中，傳統的排課經驗很值得繼承和發揚，它反映了教學涌動的特點，遵循了教學規律，具有醬謫的實用性。判定一令漾表是否科學臺理，除了繼承傳統編攤外，還應該按照教學心理學懿基本藩理，辯有效薅闖痰入箍熬記憶特點、舞生懿教學心理特熹耬瀑纛鑫雋戇特點，進行科學豹綜合分析，選擇鬣優的方案。攤課方案是否最優有下麟的評判標準：①時間間隔大腦對“彈頭”和“結尾”的事物識褥最清楚，我們可以運用這個規律來安攤學習懿囂，毽藏怒褥瀠翟安接在歪鬻戇５轉分錚內，不要港續主，毒逶當豹瀠潮傣怠，以增加“開頭”鄹“結尾”，以曉來掇麓學習效果。②時間冗的選擇早上是～必中最好的學習時間，人經過一夜的睡眠，緊張的精神得到放松，神經系統的疲憊也隨之消失，上午入的思想最集中，容易接受和記憶知識。蔗下午效率會穗慰辮鬣，醞鞋上午戇辯麓俊予下午，教忿，疲器量跨重要幫羧贍靜瀠程安排在上午＋③時間元順序以每周需隳安排兩次課的課稷為例，從星期一到凝期五中選擇兩天泉進行安排，這兩天中可以任意安排兩節諜，有銀多種安排方式，但不同的安排方式之間

重慶大學碩士學位論文３時間安排算法也是存在優劣差異的，在安排時要選擇一個較為合適的時間。３．２人工排課的工程分析和模擬人類思維過程是非常復雜的行為至今仍未能被完全解釋，但我們可以按照人類的思維過程來編制計算機程序，從而實現計算機模仿人類的行為。計算機對課表的求解實際上是對人工排課過程的模擬。根據我們學校的實際情況，作如下設定：每日最多上５次課，其中上午２次（第一、二大節），下午２次（第三、四大節），晚上１次（第五大節），如表３．１所示。表３．１一周上課安排表Ｔａｂｌｅ３．１Ｔｈｅｔｉｍｅｔａｂｌｅｆｏｒａｗｅｅｋ星期一上午第二大節第三大節下午第四大節晚上第五大節第一大節星期二星期三星期四星期五每課次２學時，不分單雙周。教學計劃中有的課程每周上１次，有的每周上２次，有的每周上３次，我們分別將它們叫做１類、２類和３類課程。舉例如下：當前課表如表３．２所示，現在需要將一門３類課Ｃ填入其中。表３．２當前課表安排情況Ｔ｛｜ｂｌｅ３．２Ｔｈｅｃｕｒｒｅｎｔｔｉｍｅｔａｂｌｅｆｏｒａｗｅｅｋ星期一上午第一大節第二大節下午第三大節第四大節星期二星期三星期四星期五晚上第五大節排課人員根據要求，認真分析課表后將課程Ｃ填入表中，如表３．３所示：１７

重慶大學碩士學位論文３時間安排算法表３．３課程ｃ的一種排法Ｔａｂｌｅ３．３ＯｎｅｏｆｔｈｅａｒｒａｎｇｅｍｅｎｔｆｏｒｃｏｕｒｓｅＣ星期一上午第一大節第二大節下午第三大節第四大節晚上第五大節課程Ｃ星期二星期三星期四星期五課程Ｃ課程Ｃ我們知道，３類課在課表中的編排方案有很多種，在眾多的方案之中，排課工作人員會記住一些比較成功的典型方案，當開始排３類課程時，他們第一時問所考慮到就是那些典型方案（如表３．４）：表３．４課程Ｃ的另一種排法Ｔａｂｌｅ３ＡＡｎｏｔｈｅｒａｒｒａｎｇｅｍｅｎｔｆｏｒｃｏｕｒｓｅＣ星期一上午第一大節第二大節下午第三大節第四大節晚上第五大節課程Ｃ旱期二星期三課程Ｃ星期四星期五瀑程Ｃ。一但是表３．４的方案是無法實施的，因為星期五的位置已經排課，這會引起沖突，必須放棄這個方案，然后繼續找其它方案，這個過程不斷重復，直到找到如表３．３的成功方案。該方案沒有時間沖突，而且符合最優時間。分析人工排課的過程，可以得出如下其特點和結論，其特點為：扎無沖突性。按照上述人工排課的步驟，編排的課表不存在沖突，即沒有～個教師同時上一門以上課程、一個班級同時上一門以上課程、一個教室同時上一門以上課程的沖突。．ｂ．較好的局部最優搜索能力。人工排課過程中，對于當前的排課課程，在班級課表、教師課表和教室課表中，能夠搜索出目前最好的排課時間和教室，即較好的教學效果時間、合理的教室、滿足教師的需求等ｃ．缺乏全局最優搜索能力。排課問題屬組合優化問題，排課班級、排課課程

重痰大學醺士擎使論文３蠟麓安撰舅法和任課教師的數量較多，所有的諜程都在教師、教室等資源上共享，前期排課與后期的課程安排有著密切的聯系，人工排課在局部范圍內能夠將課程安排在最佳的時間和教巍凝，但在全局范圍璧菇不具有這種能力，即前期的排課對于羼期的接漂壤囂沒蠢寵分夔舔詩，霉憩逡成瓷源在整轉分繇上熬不平鴦，會逢羧愛蘩｛鏨的謀程可孬德不合理。結論為：亂方案的選擇過程不是按課液的空間順序，而怒按照方案的優劣順序選擇。ｂ．課表的編排方案具有多樣化的特點，可以同時有好幾種方案供選攆，最后只是選擇了襞貔戇一秘方案露基。ｃ．在攤漾辯除了考慮方案零鴦豹優劣程度之強，述要考慮謀程的娥荔程度等其它因素。ｄ．方案的好壞除了一些公認的規律之外，有些魁童觀上的喜好而已。￡人工排漾的標準是“可行、☆理’’，一般沒有定義最優方案的標準。３．３鐮表的不確定性和維會游題根據分析人工排課的過程，災際上是一種數學上的組合問題，主要依靠約束條件來實現，如果約束條件充分，組合數就唯一被確定，但在實際工作中，隨著組合方案數的增加，問題變得十分復雜。我們前面說過課程有ｌ類、２類和３類，為了數學上襲達方便，我｛『ｊ將諜類定義如下：１類為ｘ炎，２類為Ｙ類，３類為ｚ類，全蜀鶼漾袋空鞲ｒｌ共有５×５＝２５穆（每溺按星麓～至星麓五詩霧），閑忿產生的組合數如下：Ｘ（ｎ）＝Ｉ‰１Ｙ（ｎ）＝Ｃ，Ｚ（ｎ）《搿其串ｎ＝ｌ，２…。，２５扶上面可娃褥出：①如果課類相同（譬如都為每周１次課的ｘ擻），則課表空格越多，相應的編排方案也越多；②如果瀑類越高（譬如每周３次課的ｚ類比每周１次課的ｘ類離），則隨課表熬空貉增麓，壤捧方案數迄瀵熬德越俠；③如栗漾裘空格數相兩，剛諜類越高，裙應的編攤方案也就越多。編排方索越多，從中選擇最優方案時需要的約束條件就越多，求解就越難。如果約束條件不充分，解就可能不是唯一解，而是一個集合，并且各個方案之間的差異將被忽略，這種忽略稱為方案優劣差異的融合，藏是這種融合，使得課表

重痰大學硬士學攮論文３囂重麓安接算法出現不確定性。課表集怒矢量集，計算公式為：Ｆ＝Ｃ。＊－－ｍ！／（ｎＩｘ（ｒｎ—ｎ）！）其中Ｆ為方案數，ｎｌ為空間向量數，Ｎ為每周的諜次數。計算結果如襲３．５獲示：襲３．５課表方案數Ｎｌ２３４５Ｆ（ｍ＝１５）１５１０５４５５１３６５３００３Ｆ（ｍ＝３ｍ３０４３５４０６０２７４０５１４２５０６麩上表可鞋餐蹬：當Ｎ＝ｌ時，Ｆ（ｍ＝３０是Ｆ（ｍ＝１５）的２倍，Ｎ＝３時，Ｆ（ｍ＝３０）是Ｆ（ｍ＝ｌＳ）的９倍，但當Ｎ＝５時，Ｆ（ｍ＝３０）是Ｆ（ｍ＝１５）的４７倍。Ｎｌ蝴時，Ｆｌ＝１０５．Ｎ２ｍ５時，Ｆ１－－－－－１４２５０６；所以，Ｎ２是Ｎ１的２．５倍，而Ｆ２是ＦＩ的１３５７倍。這秘空嬲；憊璧數稍徽增期，或密漂程震次數稍微增宓曩就弓ｌ起課表編攘方案數量急尉增燕鶼凌象，稱為‘‘綴合攥盔擘”，在解決深表闋簇辯是無法霞逶“綴會爆炸”的，因此，怎樣解決這個問題是課袋編排中一個重騷經務。同時，排課空間向量數少量減少（或者課程周次數少爨減少）會引起組合方案的急劇減少的現象稱為“組合塌陷”。上面這兩種情況都要想孫法解決。由翦囂的分輯褥知，課表閥艨實質上是一個組會艘劃潤題，如果怒找剿浸撓解，必須存懋夠戇終束象｛孛，餐瓣學部分屬于天文藏耱翁瀠表竭踅，不爵熊我囊充足的約束條件，而且由于課表方案優劣差異的融合，能夠找到的解將會怒～個解的集合，并熙這個集合中所有的解都是可行的。因此，我們必須放棄“絕對最優”解的方案，除了最基本的“教師、學生、教室在任一時間的安排只能出現一次’’的硬性約束條件強，課表只要能滿足“Ｗ行，合理’’的要求魏行了。受｜筵，我霧】霹輟確定詩算蘩‘簿諜饔嶷凌豹死令基標：①課襲怒沒有沖突的，是可行的；它表示課襲符合基本的原則騷求，沒有無法執行的沖突，不會出現諸如一個教室同時上兩門以上的課程的情彤。②課裘鼴青較高的質量；２０

重痰大學碩士學像論文３酵鞫蜜捺算法課表的斌量高低根據下面幾個標準來評判：１１各門諜程在一周之內應間隔安排；動重要的、繁難的課程應安攤在上午１，２節遴紓，次之豹課程安排其它時瘸；３）俸育諜應安排在上午的３、４節或者下午，兩鼴體育謀之屢不宣孬安排上謀：４、避免綮難的課程連續上，成間隔和穿插安排；５）對連續的課程安排豹教室不能問隔太遠，以方便師生及時到達教室；國實驗、童覆等實黢毪漯瑕旋該安攆在下午或浚上進辱；乃對令羽老師盼酶殊要求要器量滿足。③課襲中不存在或僅有很少的“漏課”。所謂“漏課”是指因教室安排問題使得某課程沒有辦法安排教室上課。３。４萎｝課閹題的數學模型排課藏瑟楚～令寄約束豹多瓣標健純霹題，囂藏攆漾蠲逶貔穰鍪是蠢約束鰒多目標優他橫嬲，其中約束條件可以通過約束滿足模濺來說明。３．４．１排課問題的優化求解橫型假設排課問題中，有ｎ個決策變量參數、ｋ個目標函數和ｍ個約束條件，目標蘧數、約束祭傳籟決蓑交量之淘爨綴數關系。劉赫諼翊題的最優純模型麴下：ＭａｘｉｍｉｚｅＳｕｂｊｅｃｔｔｏＦ嚷ｘ兩《ｘ＞是￡ｘ），．．。，ｆｋ（ｘ）啾）＝（ｅｌ（ｘ），ｅ２（ｘ），．．．‰（ｘ））９《３．１）（３．２）其中ｘ＜ｘｌ渤，¨．，ｘｎ）∈）（＇ｙ＝（ｙｌ，ｙ２＇…，ｙｋ）∈Ｙ。這里ｘ滏示排課問題的決策向量，ｘ表示決策向凝Ｘ形成的決策空間。ｘ的元素ｘ，，Ｘ２…。，ｘ赫出影響捧課方寨餞劣的因素的各個變量組成。主要是融闖和教室囂方囂熬掰豢，爨翔在薅凌方瓣，踅栗蔣薅舞接瀑凌縫織形式來麓分，爨ｌｌ皴安排時間所處的節ｈｉ，時段ｐｉ、天ｄｉ釉周次ｗｉ等，都Ｗ作為決策向量的元索；再例如在教室方麗，教室的類型鵬、襻蕊ｒｑ、所在的校區域碣等也都是決策向量的元素。決策向爨的元素個數是變化的，一般來說，隨著嗣標向量維數的增加，決策向量的元素個數也增加。由上面可以看出，由于ｊ｛｝課黢素之間的關聯導數了ｘ的維鼗霉零｛爨大。終衷條磐《ｘ）反獲了接滌蘑題懿壤接娥潮，礁定７決策隨爨豹霉行的取值范圍。Ｙ表示目標向量ｙ形成的目標空間。維數隨實際對乏解問題情況以及課襲評定準則的變化而變化。

重慶大學矮±學鼴論文３黠麓安捧算法３．４．２排課問題的約束滿足模型教師集合Ｔ－－｛Ｔｌ，Ｔ２，．．．，Ｔｔ）班級集合Ｃ＊｛Ｃｉ，Ｃ２，…Ｉｃｃ）詩翻集會ｌ產｛玨，ｂ，…，ｂ）（３．３）（３。４）《３．５）（３．６）（３．７）教室集合舡ｌＲｌ，Ｒ２，…，＆＇合班集合Ｇ＝（Ｇｌ，Ｇ２，．．．，Ｇｇ）一般地，如果教師Ｔｉ被指定絳合班集合中的Ｇｉ授課，則定義粕＝１，否則ａｌｊ－－０；同樣，如果教９ｉｌｉＴｊ被指定給班級ｃｉ授課，貝１ｊｂ礦ｌ，磷則定義ｂ霉＝０。定義礴個需求矩蓐。ａｌｌａ２１撐１２ａ２２…ｇｋ…４２，Ａ＝（３．８）ａ西ａ９２…口掣ｂｌ｛ｂ１２…氣…％…ｋ◇．劣‰如ｋ釓：上面的Ａ、Ｂ矩陣可以確定班綴的合班情況和教師的授課情況，也就怒猩數學豹意義上說明了當前所有的教師麓班級之聞的關系。懿采簇交漂襲土豹王雩箏天數凳ｄ，一天黟節數秀ｓ，驥褥弓｜入漂表冬ｙｌｌ癆喲矮薄Ｍ§而１Ｘ１２蔗就…‘ｄ…Ｘ２ｄＭｓ＝Ｘ２１（３，１０）＂ｇｓｌＸｓ２…Ｚ括其中Ｘｉ３滾承在ｊ’周的第ｉ’節蠢漾，否剡稅為空閑·如果按照矩陣Ａ中開課計劃進行排課，在課表矩陣中實時記錄當前教師、班級和教師的時間段占用情況，則塒得教室安排矩陣№和教師—班級安排綴陣ＭｔＸｔｌｌ—Ｉ：…而博鼉２１萎２２…而“ｘｔｎｘＩ｜２…ｘｔｄ尚（３．１１）Ｓ，

重痰大學頸士學位論文３瓣怒定｛囂算法Ｘｌｌｌ２…囂‘ｌｉｄ五１２２…Ｘｌｌ２ｄＳ１２···５＇１－Ｍｔｃ＝Ｘ｜１ｊ２￥２１···Ｘｔｌｓｄ（３．１２）ｓ趕…Ｓ２ｔＳｃｌ其中Ｍ，中ｘｉｌｆ－１表示教室Ｒｉ在周ｊ’的第ｉ’節已經被占用，否則認為空鬣。Ｍ。中茍《一１襲承教師弓繪班級ｃｉ豹授課安排時間中有周ｊ’的第ｉ’節，否則認為沒有。毒了上甏瓣撬透，裂教努每繇令舞藏（周ｊ’豹第ｌ’蔫）至多安蓑｝一次援瀠霉以表達為：∑ｘ∥，莖ｌ同理，班級ｃｊ譙時間（ｊ’周的第－ｉ，節）至多安排一次Ｊ：課可表達為（３．１３）∑ｘ∥，’ｓｌ對手教室戳凌辯閹≈，羯魏第ｉ一嗲≥楚多安攆一次上漾逡騫ｘｎ蟠＿ｌ（３．１４）（３。１５）（３．１３）、（３．１４）、（３．１５）式給出的只是排課問題中最樸素的數學模型，宦們的滿足僅僅是保誕丁教師、學生和教庭不發生沖突。其中（３．１４）保證每個班級在每個時間最多上一次課的同時也杜絕了當有多個班級參加嗣一次授課時可能襻猩沖突熬現象。網３．１排課算法圖Ｆｉｇｕｒｅ３．１Ｔｈｅｔｉｍａａｂｌｉｎｇａｌｇｏｒｉｔｈｍ

重慶大學碩士學位論文３時間安排算法有了上面的情況介紹，我們可以設計課表的編排方法，其主要分兩步，先是對課程進行時間分配，然后對課程進行教室分配，算法見圖３．１根據排課算法圖可以看到，排課算法的作用就是將無序的原始數據（也就是教學任務）進行一系列加工操作，進而生成有序的最終課表，在這其中包括了兩個主要算法：教室安排算法和時間安排算法，正是這兩個算法分別把時間和教室的約束加入到教學任務中。從而使生成的課表有效。同時我們看到，基礎數據庫、排課知識庫和策略庫都為排課算法提供了有效的策略依據，其中排課知識庫和策略庫是排課工作人員的長期排課經驗的結晶。３．５課表問題中的遺傳算法設計課表問題中，遺傳算法應用在了兩個層面，第一個層面是局部上，基于某一單門課程的時間安排，它的工作是從所有的課節空間中選取近似最優的組合解，我們稱這個層面上的問題為局部課表問題。對一門課程找到了近似最優的組合安排方案以后，并不能代表為整套課表找到了近似最優的安排方案，課程安排的先后次序同樣決定了整套課表的質量，因此，第二個層面就是基于整套課表，按照怎么的順序來排課，能夠得到一套滿意度最大的課表，我們稱它為全局課表問題。３．５．１局部課表問題的遺傳算法設計：計算公式為：Ｆ＝Ｃｍ＂－－ｍ！／（ｎｉｘ（ｍ—ｎ）！）其中Ｆ為方案數，Ｍ為空間向量數，Ｎ為每周的課次數表３．６組合數隨周課次的變化Ｔａｂｌｅ３．６ＴｈｅｃｏｍｂｉｎａｔｉｏｎｎｕｍｂｅｒｗｉｔｈｔｈｅｃｌａｓｓｃｈａｎｇｅｆｏｒａｗｅｅｋＮ１２３４５Ｆ（ｍ＝２５）２５３００２３００１２６５０５３１３０對于局部課表問題，就是在每周的課節空間（天數Ｘ節次：５ｘ５＝２５個課節）中，尋找一種合理的、滿意度較高的課節組合。表３．６列出了全部組合數。從上表可以看到，當Ｎ達到５時，組合數Ｆ達到了５ｘ１０４，這個規模會隨著Ｎ的增長極度膨脹，在如此龐大的搜索空間中尋求最優解，對于常規方法而言，存

重痰夫學頸圭學經論文３封瓣安撰籜法在著諸多的計算困難，而遺傳算法的搜索能力可以解決課表問題，因此，我們引入了遺傳算法。①編碼（Ｅｎｃｏｄｉｎｇ）綻碼方式必緩斃夠毽含這轉鑲慧。垂于漂表超囂瓣獨特縫，采懲磚綾逡傳算法中的二遴制編碼并不是綴適合，囂為課表空間是二繚鮑，包含星期和節次，焉一個二進制串很難表示出這兩種信息，因此，需要一種新的編碼方式來襲豕遺傳基因。我們采用了一種叫做布爾綴陣的表示方法來對課表基因進行編碼，如表２，這個布爾矩陣襲示對一門課程的一種分配方式。矩降掇坐標為星期，縱嫩標為節次，萁串０凌零沒有安簿課程，ｌ凌示安囂瀠程。表３．７謀表染色體編碼Ｔａｂｌｅ３．７ＯＯＯＯ０１Ｏ０Ｏ０ＯＯ０ＯＯＣｈｒｏｍｏｓｏｍｅｃｏｄｉｎｇｏｆｔｉｍｅｔａｂｌｅ１ＯＯ０Ｏ０ＯＯＯＯｌ０Ｏ０ＯＯＯＯ０它表示，該門課程安排在了周：第一節、周四第一節和周六第二節。出糍爾矩瘁囊表示豹緩璐空藏與解空瓣怒一一對應豹，任露一耪漾表靜舞鬻安接方案繇可以在這個編碼空間中找到一個對應。②適應魔函數（ＦｉｔｎｅｓｓＦｕｎｃｔｉｏｎ）課表問題中，對一種安排方寨優劣的判定很復雜，其中包含眾多來自課程、教師、教室的艦她和要求，一類為規則，另一類為要求。適應度函數的設計是課表露逶邃簧霧浚設詩夔關鍵，囂雋它走法象受藤攆瓣遴那么燕擎瓣懲一令凌達式就可以表示，謙表方案的適應度體現在很多方面。大多數綴合優化問題中，適威膨函數都是固定的，但是在課表問題中，固定的適應度函數鼴然是不能適用的，因為隨著排課的進行，遺傳環境（課表黧間）在不斷變化，同樣一個個體，放在不閼的環境中，它的適艨程度是不同完全的，甚至穩差縵大，黧魏，磐露設詩一令莢蠢鑫逶應瞧熬適黷發囂數裁是最關鍵戇。①適應度溺數中的參數適應度函數中需要包含的參數信息包括：節次優魔ａ、日組合優度ｂ、帶綴合優度ｃ、組合可行性ｄ、分布優化度ｅ、資源優化度ｆ等。這些信息都保存在課表知識庫中。

重慶大學碩士學位論文３時間安排算法１）節次優度ａ節次優度是對一節課“有多好”的量化表示，是大部分同學愿意上這節課的程度，或者上這節課效率的高低。表９則是由一份社會調查得到的節次優度結果，當然這個結果含有一定的人為因素，每個人的評價可能有些差別，這也正是為什么課表千差萬別的原因之一。在我們的排課算法中，該信息是由排課人員自己維護的，它可以實時地體現不同人、不同學期的要求。表３．８節次優度Ｔａｂｌｅ３．８ｓｌｏｔ－ｓｕｐｅｒｉｏ星期一上午第一大節第二大節下午第三大節第四大節晚上第五大節Ｏ．９５Ｏ．８５Ｏ．６５０．５５Ｏ．３５星期二０．９８０．８９Ｏ．６９０．５９０．３９星期三０．９７０．８７０．６７Ｏ．５７Ｏ．３７星期四０．９４０．８４０．６１０．５ｌ．０３１星期五０．９２Ｏ．８２０．６２Ｏ．５２Ｏ．３２節次優度是將大部分同學愿意上這節課的程度，或者上這節課的效率的高低進行量化的結果。上例中，周一第１節課的優度為０．９５比較高，表示這節課效率較高。２１日組合優度ｂ日組合優度，是日組合方案優劣程度的量化表示。假如某門課一周上兩次課，那么哪兩天的組合比較好？每周上兩次課（一天只能上一次課），五天中所有的兩天組合數為Ｃ５２＝１０，例如：周一和周二的組合為：表３．９日組合情況一Ｔａｂｌｅ３．９Ｐａｒｔ１ｉｎｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ－ｄａｙｆ星期三目目＊———。。。Ⅲ日——．——＿ｌ＿＿目＿目目Ｈ＿＿日目＿目日＿嘲ｌ零期一ｌ星期二星期四星期五周三和周四的組合為：表３．１０日組合情況二Ｔａｂｌｅ３．１０Ｐａｒｔ２ｉｎｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ—ｄａｙＩ星期一星期二早期三旱期四星期五圈一對每種組合進行優度判定，例如：周１周２組合（１１０００）的優度為１．０，周３周

重慶大學碩士學位論文３時間安排算法４組合（００１１０）的優度為０．８，等等。３）節組合優度Ｃ。節組合優度Ｃ，表示這兩天中的哪種節次組合比較好。在日組合的基礎上，進行課次的安排組合。上面的例子中己經確定了每周兩次課，假如按照傳統的大課（２小節）安排，那么所有的課排組合數應為５ｘ５＝２５，例如：表３．１ｌ節組合情況一１ｈｂｌｅ３．１１Ｐａｒｔｌｉｎｓｌｏｔ－－ｅｏｍｂｉｎａｆｉｏｎ星期一星期二星期三星期四星期五上午第一大節第二大節下午第三大節第四大節晚上第五大節表３．１２節組合情況二ｍｆｂｌｅ３．１２Ｐａｒｔ２ｉｎｓｌｏｔ－ｅｏｍｂｉｎａｔｉｏｎ星期一星期二星期三星期四星期五上午第一大節第二大節下午第三大節第四大節隧隧翻黼隧晚上第五大節對上面每種組合進行優度判定：第一天的第２大節和第二天的第４大節組合，優度為１．０，第一天的第２大節和第二天的第３大節組合，優度為Ｏ．８，等等。４）組合可行度ｄ。組合可行度表示當前的安排是否存在班級或教師的沖突，如：是否有的班級在當前時間已經安排了其它課程。它只有０和１兩個取值。５）分布優化度ｅ。分布優化度ｅ是以Ｏ～１之間的浮點數來表示的。分布優化度是指當前的安排是否滿足課表的一些要求，如難度間隔，文理間隔，以及是否滿足上課教師或者課程本身的一些特殊要求等等，它是Ｏ～１之間的浮點數，因為事實上，一套課表肯定無法保證全部的難度間隔和文理間隔，因此我們設置分布優化度來表示問隔程度。

重慶大學碩士學位論文３時間安排算法６）資源優化度ｆ資源優化度ｆ也是介于Ｏ～１之間的浮點數，它的目的是為了追求排課的第三個目標而設置的，是對付“漏課”的第一道防線。我們在前面介紹過，“漏課”的問題是課表問題中的難點。為了更好的理解資源優化度ｆ，首先，我們來分析一下，由于課程無法安排教室而造成的“漏課”是怎么產生的，這其中的原因有很多種，其中與時間安排有關的原因之一是對有限的某種教室過度集中使用，而造成某個時間該類教室負荷過重，使后面待安排的課程在這個時間無法獲得足夠的教室選擇空間。資源優化度的判定相對復雜一些，它涉及到教室資源分布圖的計算，削峰填谷等方面的內容，簡單的說就是判定是前的安排否當會導致某一類教室在一個時間的使用過于集中，而其它的時間空閑很多，繼而使后面的課程在安排教室資源的時候過度緊張，從而不得不進行教室范圍擴展，浪費了本來就很有限的教室資源。在自動排課算法中，資源優化判定是避免出現“漏課”的第一道防線，它就是為了阻止對某一類教室在一個時間過度使用。教室數星期一（第１節）時間圖３．２有波峰非均勻的教室資源分布曲線Ｆｉｇｕｒｅ３．２ＴｈｅｄｉｓｔｒｉｂｕｔｉｎｇＣＵＩ、，ｅｏｆａｓｙｍｍｅｔｒｉｃｃｌａｓｓｒｏｏｍｎ№ｕｒｃｅｓｗｉｔｈｗａｖｅｃｒｅｓｔ教室資源分布曲線圖直觀地表示了一種教室（適合多少學生一起上課的教室），在各個時間段的使用分布情況，從這種圖上，我們可以看出哪個時間的負荷過重（失去平衡），在排課過程中（而不是排課結束后）及時地發現并進行糾正。事實上，這是一種在安排教室之前就進行的預防手段，它并不能絕對避免“漏課”出現。當“漏課”出現后，我們還會有可選的幾個方法來自動稱補，這些方法將在后

重慶大學碩士學位論文３時間安排算法面介紹。在圖３．２中，在周三出現了非常高的峰值，它導致了后面人數相近的課程在周三沒有足夠的教室選擇余地，而其它時間該類教室卻有很多空閑。假如這時有一門課程需要在周三第１節課從該類教室中選擇，那么就會出現無法安排的問題，那么系統將會自動降低時間組合優度，轉而向其它時間段進行搜索以期避開周三第１節這個時間，如果能找到則可以解決這個問題，可是時間組合優度是會否降低很多呢？是否會有其它沖突產生呢？例如：難度大的課程沒有得到較高的時間優度，或者違反了其它常規規則等，這些問題我們都無法保證不出現。因此，通過在排課過程中動態的計算資源分布優度，及時地發現并摒棄這種不合理安排，可以在很大程度上避免“漏課”出現。教室數星期一（第ｌ節）時間圖３．３相對平均的教室資源分布曲線Ｆｉｇｕｒｅ３．３ＴｈｅｄｉｓｔｒｉｂｕｔｉｎｇｇＵＩ＂ＶＣｏｆａｖｅｒａｇｅｃｌａｓｓｒｏｏｍ“∞ｕｎ：ｅｓａｂｓｏｌｕｔｅｌｙ在圖３．３中沒有明顯的波峰和波谷，表示教室的分配比較均勻。類似的課程在任意時間都可以安排，這是比較理想的狀態。資源優化度ｆ的計算公式為：仁（Ｔ－－Ｍａｘ）／（Ｔ－－Ｍｉｎ）其中，Ｔ為全部教室總數，Ｍａｘ是組合產生的峰值，ＭｉＩｌ是谷值。當資源分布曲線越趨平緩，即Ｍａｘ與Ｍｉｎ越接近的時候，ｆ就越大，最大值為１，出現在Ｍａｘ＝Ｍｉｎ的時候，即曲線是一條水平線。②適應度函數基于以上參數，我們設置單門課程的課表問題遺傳算法的適應度函數如下：Ｆ＝（Ａｘｗｌ＋ｒｂ。ｑ１＋ｃｘｑ２）ｘｗ２）ｘｄｘｅｘｆ

重慶大學硬圭學愛論文３酵鞠安接簧法其中Ａ襲永當前組合方案的帶次優度的平均值，Ａ＝（（ａｘｂＩｃｌ）＋（ａｘｂｌｃ２）＋（ａｘｂ２ｑ）＋（ａＸｂ２ｃ２））／ｎ，公式是以上述的每周兩次課為例，其中ｎ表示上課的次數（這里ｎ＝２），ｂｌ是第一次課的目組合優殿，ｂ２是第二次課的豳組合優度，ｃＩ是第一次課豹：籜組合魏度，ｃ２是第二次瀑戇蓼綞合筑度，錘秘璉２袋苯基緩會魏度黟繁綴合錢度所占的投黧，ｑｌＩ＋ｑｆｌ，囂ｖｒｌ秘ｗ２表示節次優度和綴合優度各占的權熏，ｗｌ＋ｗ２＝ｌ；適應皮函數Ｆ的最高值為ｌ。③選擇操作（Ｓｅｌｅｃｔｉｏｎ）在局部課襲闖題中，我們采用了輪盤賭豹方法來進彳子選擇操作，并對此做了撰投奪生境豹羧送。輪鑫賠方法交琢圭是莰蕹蒙特豢羅（ＭｏｎｔｅＣａｒｌｏ）方法浚謗熬。蒙特卡羅方法，或稱計算稅隨梳模撅方法，蔗一靜基于“隨梳數”熬計算方法，它的基本思想很早以前就被人們所發現和利用。早在１７世紀，人們就知ｊ鰒用事件發生的“頻率”，來決定事件的“概率”。１９世紀人們用投針試驗的方法來決定圓周率，本世紀４０年代電子計算機的出現，特別是近年來離速電子計算機的出現，使褥躅數學方法凌詩算輥上大量、俊速遣模蘇這樣茲試驗藏為霉能。鍘如，考慮平瑟上懿一個逡長免ｌ靜正方形及箕內部的一個形狀零麓煲｝ｌ靜“圖形”，魏謗求澎這個“圖形”的面秘睨？蒙特卡羅方法怒這樣一種“隨機化”的方法：向該正方形“隨機地’’投擲Ｍ個點，落于“圖形”內的點為Ｎ，則該“圖形”的麗積近似為Ｎ；Ｍ。露３．４不閹令體戇逶痤痍Ｆｉｇｕｒｅ３．４ＴｈｅｆｉｍｃｓｓｏｆｄｉｆｆｅｒｅｎｔＩｎｄｉｖｉｄｕａｌｓ輪盤賭方法類似于博彩游戲中的輪盤賭，輪盤被劃分為不同比例的區域。這里的比例是根據個體適應度大小分配的，適應度高的個體由于在輪盤中矗攢較大

重痰大學碩士學經論文３辯弱安接算法比例的區域，閣此被選中的概率就犬，得以生存的概洙大，相反，適應殿較低的個體則被淘汰的概率較大。選擇算法的過程是隨機的程輪盤中投下落在的區域所代表的個體將被選中并得以生存，蟲Ｈ圈３．４所示。翔囂瑟奔緩熬，基于奪生境技術夔選擇操薛將受瓣予健令搏與父霞令傣逶廳適應度醴：較，如栗父代個體遙應度離，剛復皋ｌ父代個體劐當前子代釋群中，否則不復制。前面我們融經討論過了遺傳算法的缺陷，其中一個缺陷是初始種群的不均勻分布。在這爨，為了改進它，我們采用了分區域的初始種群選擇，即，將整個解空闖劃分或ｎ令囂域，襲魏純耪群辯，分裂在每令小區域孛疆瓿選擇１／ｎ接個個體，最后將ｎ個小釋群合并殘櫥始耪群，這樣產生靜靜群麓本覆蓋了整個熬空閹，保證了初始種群的均勻分布．④交叉擻作（Ｃｒｏｓｓｏｖｅｒ）課表問題中，每個個體需要遵鍵的規則是周課次數是固定的，無論怒交叉還是變異都不麓造鶩該怒贈。囂致，我髑設計豹交叉攝傳必須要考慮這個綴索，斃舞矩薄夔交攥髂或者并操終裁蠢無法滿足這個魏囂ｆｌ瑟舉纜采瘸。我們這熙采用的交叉操作類似乎二迸制串中的單點交叉操作，單點交叉是隨機產生一個交義點，然后將兩個父個體在交叉點右側的部分相互交換，從而產生兩個不同的乎個體。對于課表問題的矩陣表示，我們將隨機交換兩個父個體的第ｒ１個‘ｌ’位，箕巾ｎ隨規產生，對于繇蠲三課次豹課程，假設ｎ＝ｌ，鄹交換父個俸ｌ與父令薅２戇第一令霞進孬交叉綴會殘子令體。鑲懿：襲３．１３父個體１ＯＯｅＯＯ１Ｏ８ＯＯＯＯＯＯｌＯＯＯ０００ｌＯＯＯＯ００ＯＯ０Ｏ００襲３．１４父個體２０ＯＯＯＯＯｌＯ０００ｅＯＯＯＯＯｌ０Ｏ０ｌＯ§０ＯＯＯＯ００Ｏ００

重慶大學碩士學位論文３時間安排算法交叉產生兩個子個體：表３．１５子個體１Ｔａｂｌｅ３．１５０ＯＯ００Ｏ１００Ｏ０００Ｏ０ｌ００００ＯＯＯＳｏｎＩｎｄｉｖｉｄｕａｌ１００ｌＯＯ０Ｏ０ＯＯ０表３．１６子個體２Ｔａｂｌｅ３．１６Ｏ０００Ｏ１０００Ｏ０ＯＯＯＯＯ０ｌ００Ｏ００ＳｏｎＩｎｄｉｖｉｄｕａｌ２０ｌＯＯ００００Ｏ０Ｏ兩個子個體分別保留了來自父個體的部分特征。⑤變異操作（Ｍｕｔａｔｉｏｎ）變異操作相對比較簡單，由于我們設計的矩陣為布爾矩陣，而且矩陣中的‘ｌ點個數不能變化，因此，我們采取了“１點跳轉”的變異方法，即矩陣中的某個‘ｌ＇點由原來的位置隨機跳動到另外一個一０點上，而原來的‘１’點自動變為‘ｏｔ。例如：表３．１７父個體Ｔａｂｌｅ３．１７０ＯＯＯＯ１Ｏ００ＯＯ００Ｏ０１０ＯＯＯ０ＯＯＦａｔｈｅｒＩｎｄｉｖｉｄｕａｌＯ０１００Ｏ０Ｏ００Ｏ變異為：表３．１８子個體Ｔ曲ｌｅ３．１８Ｏ１０ＯＯＯＯ０ＯＯ０Ｏ０ＯＯ１００ＯＯＯＯ０ＳｏｎＩｎｄｉｖｉｄｕａｌＯＯ１００００ＯＯＯ０

重痰大學碩士掌經論文３孵溺安接舞法３．５．２局部課表問題遺傳算法的結束條件假如我們不考慮遺傳算法的結束問題，那么遺傳算法將無限地執行下去，因為算法本身弗不知道該怎樣結束，所以，我們必須設鼴遺傳算法的停止讖純條件。騫三秘較黲懿逅窶逮煲算法戇方式，善競，當耱瓣墨不毒騫交純對，羧霹敦決定退出，這黌要一個專門饜來稔凌釋群差冥的模塊，它耨對任意兩個個體進行差異檢查。第＝種方式是，如果達到了適應度的目標，也可以退出，這需婺適應度函數設囂的非常好，它基本上能夠體現個體的絕對適應度，或者需要綴歷一定次數的測試，了解了適應度的情況之后，就可以設鬣翻標適應度。第三，在迭代了一定豹次數袋者說經歷了一定數囂熬“鼗’，之囂，瑤叛退出。在基予犖門謙程靜捧謀算法巾，由于適應度瓣鑲與當前遺傳環境毒穰滅靜關系，不能夠縱向進行比較。例如，對于空的課表空間，適應度為Ｏ．９８的安排方案是最好的，但魑當課表空間已經被占用了很多的時候，適應度為０．８的安排方案是當前環境中最好的，而且是可以被接受的，因此我們不能設置一個統一的目標適應度來衡量。程這里我髓采取了努三秘方式來終止遺傳算法，鄯設置一個“代”數，達妥該“鼠”數之囂，籜壹遽簧避純，并置取當藏最饒虢ｎ（ｎ由用戶鑫蠢鑲定）今個體為最終解，之所以取ｎ個最終個體是因為教室安排會對時間安排產嫩回溯調整，可能最優的個體并不能和教意安排很好的合作，因此必須存在多個候選個體，這些會在后面詳細介紹。３。５．３全局諜表問題的遺傳算法設計經逑鼴幫漾表閆蘧戇算法運移，辯每門諜程我辯舔甏數我鷲一個遙釹袋儻我謀表安排，假是這卻無法確保整套諜表就是近似最優的，因為課表空間和教室空間都是一定的，先安排的課程無疑會搶奪最優，后安排的課程則只好選攆次優，這就是優度搶奪的問題，即，無論怎樣編排，都不可能使各個課程的安排在優度上絕對平衡。這是課表編排的主要灝難之一，也是慕本艘鋒之一。在漂表瀚瑟夔藤弱孛毒蔻條涉及鬟次彥勰題，魄黧先撰燕麥寒懿課纛、先｛霎公共謀等，健怒僅僅有這幾條嘏則楚遠遠不夠的，蔡中還涉及至４課程對教鲞和時間的要求問題，要求嚴格的課程威該先排，或者條件姆刻的課程應先排，由于～個學期的課稷很多，所以這些條件很難在排課之前就能夠確定，這里我們采用遺傳算法來尋找～條近似最優的課稷安排序列。課表閩題屬于ＮＰ完全問題，它的搜索空闋夔謄渫糕數纛豹璦麓瑟憊測瀵大，瑟有夔課程攆磺數走（》１）！／２，麴魏凌大的援索空聞需要用遺傳算法來解決，下面我們分櫥鞠設計在全局課表闊趲中遺傳算法的應用。①編碼采用路徑襲示法。路徑表示法是表示旅程對應的簇圓編碼最自然，最簡單的

重慶大學碩士學經論文３辯溺蜜攆莠法表示方法，窀是把旅程依次經過的城市的順序記錄下來。這種編碼方式必須保證編碼中不能有重復的因子出現。例如：設置順序表Ｃ＊（１，２，３，４，５，６，７，８，９），旅程順序為５一ｌ一７—８—９—４—６—２—３，用路徑表示法就可以直接襲示為：５１７８９４６２３。②選簿撩作幫適應度函數在這里我們仍然采用與局部課表問題的選擇操作榴類似的選擇策略——基于小生境技術的輪盤賭方法。適應度聰數的設計問題是全鯔漾表闖題中的一個難題，為此，我們采用了一耱霪單一點熬方法，藏是將每一門漾程在弱部安捧貉瑰豹最終適應度避紓警均，由斃來對整令路徑進行評價。僅儀～門課程安終褥好，并不能健表整個渫襲安｛菲得好，而所肖課程安排得好的話，那么整個課表安排樗就一定好，所以，所有課程適應度的平均值基本可以體現熬套課表的適應度函數。因此，Ｆ。（Ｆ１＋Ｆ２＋…＋Ｆｎ）／ｎ，１１是種群中課程的門數。③交叉搽侮采用鼴衽襲示黲編璐方式決定了在逮傳算法中逡符交叉揉饞生成豹令棒染色體中不允許肖熬復的基因碼。這樣，基本的遺傳算法的交叉操作生成的個體～般就不能滿足這～約束條件，在這嫩我們采用順序交叉。順序交叉是在１９８５年由Ｄａｖｉｓ等針對經典的貨郎擔問題（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，ＴＳＰ翹題）提出豹基予路徑表示靜顳序交叉操作，它能保密排列菸融合不同捧捌茲蠢澎縫萊蕈元，秀令父令缽交叉懿，逶避選擇父個俸ｌ熬一幫分，僳存父個體２中基因碼的相對順序轍成子個體，這樣就繼承了來自兩個父個體的部分特征。例如，對下面兩個父個體的襲示，隨機的選擇兩個交叉點“ｌ”Ｐｌ：１２３｛４５６７ｌ８９Ｐ２：４５２｜１８７６｜粥首先，兩個交叉點之聞的中間段保持不變，得到：Ｓ１：ＸＸＸＳ２：ＸＸＸＩＩ４５６７１８７６ｘＸｌＸｘ其中ｘ襲示暫時沒有定義基裰碼。然囊，誕瑕父令落２軟第二令交哭贏囂始款基囂褥豹蓑｝裂ｊ矮｜亭，姿嬲達表遑時，返回襲頭繼續記錄基因碼，贏到至《達第二個交叉熙結束，這樣就獲褥了父個體２從第二個交叉點開始的基因排列順序：９３４５２１８７６。對于父個體ｌ，融有的基因碼為４、５、６、７，將它們從個體２的基因碼排列順序中去掉，得到排列順降９３２１８，再將這個排列順序復制給父個體ｌ，復制起點也是從籀二個交叉點開始，以此決定

重慶大學碩士學位論文３時間安排算法子個體１對應位置的未知碼ｘ，這樣子個體１生成為：Ｓ１：２１８４５６７９３調換父個體ｌ和２的順序，同樣可以生成子個體２Ｓ２：３４５１８７６９２④變異操作變異操作有很多種適用于順序表達法，比如反轉變異、插入變異、移位變異等等。這里我們使用反轉變異。反轉變異是在染色體上隨機地選擇兩點，并將兩點之間的子串反轉：１２３４５６７８９一１２３６５４７８９３．５．４全局課表問題遺傳算法的問題和改進①染色體編碼過長如果單純地把課表問題簡化成ＴＳＰ問題，會產生一個很大的問題，一個學期的全部課程有１０００多門，如果把它們當作一個整體看待，每條染色體基因將有１０００多位，雖然有的理論認為編碼應該符合實際變化，但是這樣龐大冗長的編碼表示，違反了編碼靈活的原則，而且給理解和操作都帶來了困難。這個問題的解決方案是劃分子群體。事實上，仔細觀察之后可以發現，一個學期的課程中，各個系之間存在著很強的獨立性（除少數的公共課以外，而這些少數的公共課程具有最高的優先級，他們并不應該參與普通個體的選拔），每個系的課程參與的教師、班級和教室往往是相互獨立的，不同系的課程之間并不存在優度搶奪。而且單個系在一個學期中的課程在２０門以內，這樣的基因編碼就合理很多。因此，我們采取的解決方法是，將種群分割成不同的子種群，遺傳算法分別在各個子種群中獨立的進化，各個子種群之間不進行任何通信，當各個子種群都已經搜索到了局部近似最優的個體，然后在子種群之間進行比較和合并，選取出全局最優的個體。這種方法恰恰發揮了遺傳算法的并行性優勢。②適應度函數計算量過大全局課表問題中遺傳算法的另一個問題是適應度函數的計算費時太大，假如一個子種群中包含２０門課程，那么對于任一個體，計算其適應度需要執行２０次局部遺傳算法，這種適應度計算方法需要的計算量過大，會影響整個算法的運行效率，目前我們能夠采用的緩解方法是采用并行遺傳算法的思想。并行遺傳算法的實現方案大致有三種：１）主從式（Ｍａｓｔｅｒ－ＳｌａｖｅＭｏｄｅｌ）在這種模型下，并行系統分成一個主進程和若干個從進程．主進程監控整個染色體種群，并荃于全局統計執行選擇操作，各個從進程接受來自主處理器的個體進行重組交叉和變異，產生新一代個體，并計算其適應度，再把計算結果傳給主

重慶大學碩士學位論文３時間安排算法進程。這種模型在適應度計算很費時并且遠遠超過通信時間的情況下才有效，否則通信時間超過計算時間，反而會降低速度。而且這種方法要求有進程同步機制，這就會導致主進程忙而子進程閑或者相反，引起負載不平衡，效率不高。２）分布式（ＤｉｓｔｒｉｂｕｔｅｄＧｅｎｅｔｉｃＡｌｇｏｄｔｈｍｓ，ＤＯＡ）這種方式是將種群分成若干個子群并分配給各自對應的進程，每個進程不僅獨立計算適應度，而且獨立進行選擇，重組交叉和變異操作，并定期地相互傳送適應度最好的個體，從而加快滿足終止條件的要求。分布式遺傳算法是目前采用最多的并行遺傳算法。３）分散型（Ｆｉｎｅ．ＧｒａｉｎｅｄＭｏｄｅｌ）分散型遺傳算法是為種群中的每一個個體分配一個進程，每個進程進行適應度計算，而選擇、重組交叉和變異的操作僅在與相鄰的一個進程之間傳遞個體中進行。我們最后采用了分布式的并行遺傳算法來解決適應度計算量過大這個問題。將種群劃分成相互獨立并且相差較大的若干個子群，每個子群中都獨立的進行選擇、交叉、變異等操作，達到一定代數之后，相互之間進行最優個體交換，以達到全局最優收斂。３．５．５全局課表問題遺傳算法的結束條件圖３．５遺傳算法停止條件Ｆｉｇｕｒｅ３．５ＳｔｏｐｃｏｎｄｉｔｉｏｎｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

重慶大學硬±學拯論文３黠鶿蜜罄算法在局部渫表問題中，遺傳算法的結束條件是達到了進化的代數，就停止算法，那是因為局部課襲問題的適應度澈法縱向的進行比較，因而無法設置一個統一的適應度尺度來衡量是否可以停止遺傳。在全是瀠凌窩懲孛，事實上麓囂耱方法罄可以摻麓籌法續震愆條｛譬。我秘這里采爝了兩犖孛方式相結合的方法，先進行適應度條饞橡查，如果找到了達剿指定適應度的個體，則停止進化，否則，如果進化代數爵經超過了指定的代數限制，但還沒有找到符合適應度要求的個體，則也停止進化，從最后一代種群中選擇最優個體作為最艏的解，如圖３．５所承。３．６算法褪絮從宏觀上看，我們所設計的諜襲問題解決方案怒兩層的遺傳算法嵌套運行，內層遺傳算法的運行結果傳遞給外層遺傳算法作為邋皮度函數的一部分，外層遺傳算法以此為依據來搜索近似最優解。圖３．６就體現了整個算法結構。

重慶大學碩士學位論文３時間安排算法圖３．６遺傳算法流程圖Ｆｉｇｕｒｅ３．６ＦｌｏｗｃｈａｒｔｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

重褒大學碩士學繾論文４教室安攙算法４教室安排算法教室安攥舞法豹基豹是為諜糕選擇一個教室，它是簿渫軟傳豹一令獯點，這個算法靜優劣楚整個簿謀算法成功豹一今關毽，因為瓣翡高校課表安舞｝的～個最突出的矛盾怒不斷增長的學生入數和有限的教室資源之間的矛盾。很多ｊｊ｝諜軟件在這個問題上都沒有找到很好的解決方法，出現太多光法安排教室的課程，是造成“漏課”現象的最重要的一個因索。如何有效的安排使用這些固定的教室資源，在技術上是一令鼴題，囂在實際應嬲巾其有綴重要匏意義。４．１教室安排流程教室安排算法的流程圖如圖４．１所示，其中ｎ為優先教室的個數。教室安排算法的輸入數據包耩；課程ｃ、上課人數ｇ、課程要求和教窳類型ｈ。首先，麩知識黲Ｋ中取出當前諼程豹優先教室表Ｒ，默認情況下，ｋ書所包含的教室集合蕘溧戇掰藩系掰在熬系褸教室，蕉戶可顫菇漾鹱縫套一個更漆確豹范圍。在這個教室范潮中，對教室座位數燕和教室類型避彳予過濾，得出符合當瀚諜程要求的更小的教勰范圍。其中教室魔位數ｅ：ｇ＋Ｍｉｎ＿＜ｅ＿＜ｇ＋Ｍａｘ其中Ｍ如ｊ鞫Ｍａｘ分別是座綴數多于人數的下限覯上限，系統默認２０釉５０，著霉更改維護。這辯蔟懿教室表甏孛黲每令教室籜熊壤壤驁會當蘸漾蘸鶼簧求，當Ｔ口中的教燕沒有可利用的時候，系統將首先采用教室擴展來解決這個覯遂。這里的擴臌包括兩步，首先對教室座位數的擴展，即對上面式子中的Ｍｍ和Ｍａｘ之間的范圍進行擴大，使符含器求的教室范圍增犬，從這個擴展后的教室范圍中尋找目標教室．第２步是對教窳類型的擴展，即，愛求醬通教室的課瑕可以擴震弱多媒薅教嶷，或者授影教室，這囂彈霉強健囂據數蹇蓬垂壤太，毽怒攀實主往往多媒體教室和投影教室數量黧繃有限，因ｊ鞋：，勢舉攘薦使用第二靜擴越。在兩種擴腰都無法找到符合隳求的目標教室的時候，“漏課”問題就出現了，下面將討論如何解決“漏課”問題。

重慶夫學碩圭學靛論文４教室安簿算法圖４．１Ｆｉｇｕｒｅ４．１教室安排算法的流稷圈Ｆｌｏｗｃｈａｒｔｏｆｃｌａｓｓｒｏｏｍ－ａｒｒａｎｇｅｄａｌｇｏｒｉｔｈｒａ４．２“漏課”翡三種解決算法前面已經介紹了“漏課”問題，以及這個問題的產繳原因。如果理論上學校的教室資源是可以滿足教學任務的要求的話，那么則一定存在一種課表解決方案可以沒有‘‘漏課”阿題，可是，追求絕對沒有“漏課”閩題將逃成算法的無限期運行，或者４０

重痰大學硬士學緞論文４教室安接算法死循環產生，湖此，我們放棄絕對追求，而追求力爭將“漏課”問題減少到鼴低限度。排課算法中，我們運用了３種算法來避免和排除‘漏課”問題，第一種辣法運用在對間安排冀法中，也就是說，農時閱安排時期則己綴野始考慮教室安排的情況。算法一：旋懿蠲囂安萎｝過程巾，盡量遺受囂要類秘教室熬漂程過愛集串在菜個時聞，這裁怒在時聞安捧算法巾笑子資源分布優純度判定部分的內容。這令算法首先能夠從底層避免“漏課”，它屬于一種預防手段。由于算法一僅僅是一種預防乎段，它只能夠降低“漏課”出現的幾率，似并不能夠阻止“漏課”閱題的出現。例如，即使時間分布很均勻，可是對于那些本來就很有羧熬特豫教囊，仍然可能由予握驁饅爰，瑟導致那壁必須壤習它靜漂覆炙浚安攙教室。當出現這樣靜情況的時媛，我ｌｆｊ采蘑７“強溺”髑熬筋方式來解決這個闖蘧，以求盡量滿足課程對教室的要求。排課的過程也是對有限資源使用的過程，開始的時候資源相對豐富，可以擇“最優”進行安排，隨著排課的進行，資源慢慢變得很緊張，可選擇的余地巍越來越小，當出璦蘢浹安接熬“死蹙”的對候，攤漂過程遇至ｌ了簿薅，這個漳礙勢囂一定是因為教室資源沒竅了造戒懿，露瑟多建是垂手“美鍵”爨潦羧提茲使矮７，這囂重候，向前尋找可以將“關鍵”資源釋放的地方，撤銷其現有蜜排，以非關鍵資源替代關鍵資源，那么前顧遇到的障礙則會得到排除。這個過程就是我們所采用的“回溯”調整，簡單的說，“闡溯”就是當匹配遇到障礙的時候，撤銷以前的決定，重新進杼～次新豹選擇。由予攤課中豹試探具有一定的盲目性，產生不合理安排是不可避兔的，瑟“強溺”能夠楚系統殼騷這令袋杰，囂瑟“瑟溯’’在這受馨鬻重簧，是鼴狹翊遴豹一個重要手段。算法二和算法三分別是回溯調整的兩種不同方式。算法－－宅回溯改變當前課稷融經確定了的時間安排，來尋找可滿足教室要求的時間組含，這個改變有可能會降低時間組合的優殿，但是如果優度降低范圍在認可黥范滋叛疼，那么班較小熬拜尊藏爨度來換取教窳安接上豹空閆，媳鼴霹取豹一穗方案。算法二將從時間排課算法所產生的ｎ個候選個體（時間分配方案）中，按照適應度由大Ｎｄ，的順序對個體進行試攆，這里的試探不僅黌進行組合可行性、分布優化度、資源優化度的判定，還要讖行當前的時間組合怒否能夠進行教室蜜排的判定，只有能夠進行教室安排的個體才是符合要求的搜索結果。致交爨闕綴會葳造成熬霹蠲臻發下簿是這靜算法瓣一令弊囊，一般壤滋下我們只允許較小瓣優度下降，當下降游常大的時候，蹩個諜表的質量也將下降很多。因此，對算法麓，我們加入了一個優度降低限制參數ＤｅｃＬｉｍｉｔ，它將監視每次時間組合改變所造成的優度降低是蔭在限制之內，如果一旦超過該限制，則放棄算法二。４１

重慶大學碩士學位論文４教室安排算法圖４．２回溯算法二流程圖Ｆｉｇｕｒｅ４．２ＦｌｏｗｃｈａｒｔｏｆＢａｃｋｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｉｃ．－２算法二的流程圖如圖４．２所示。按照算法二的思路，較大的時間優度往往不能夠獲得足夠的教室可安排空間，回溯的成功率則不會很高，可是如果保證該算法一定回溯成功，則必定會造成時間組合的優度過低，而導致課表質量的下降，因此，我們準備了第三個算法。算法三也是一種“回溯”方式，它將在算法二仍然無法成功的基礎上觸發，與算法二不同的是，它的回溯對象不是當前課程的時間安排，而是其它已排課程，調整其時間或者教室安排。流程圖如圖１３．算法三有兩種“回溯”算法，第一種是回溯調整已排課程的教室安排，第二種是回溯調整已排課程的時間安排。當出現“漏課”的時候，暫時保留當前課程的時間安排，而向前回溯己排課程，

重慶夫學碩士學髓論文４教室蜜攘算法查找可以進行很小調整則能滿足當前課程教室要求的已排課程。第一步，計算調整目標課程集合。要搜索娃：鞠當前課程在當前辯間具有沖突交集的嬲標課程集合，該集合中的諼程輯占矮熬教室郝篷含在當蠢萋漾毽弱霞先教室集會巾，繇改交這些瀠耬懿安接受４會改變當前課程靜安排空闖，虢有可能會產生可利用豹教室。這個算法就楚在目標課程集會中尋找－－ｆ－］課程，改變它的安排（時間或者教室），而使當前諜程可以在不改變時間安排的情況下獲得Ｗ用教室。第二步，鲇每門目標課程計舞“波及范圍”在這里，勢苓是蓬輥熬獲己接滌程孛選擇一門諼凝※終鑲整，囂是蘞鬃一個計算“波及范麗”靜佶值丞數ｆｆ鐳餓丞數ｆ為每門已稀諜翟計算出一個俊，它代表若改變該課程的安排整套課表中將會有多少門課程受到波及影響，他們都宵可能要作出相應的改變。第三步，依“波及范圍”從小黧犬的順序對目標課耩避行試探調整。一般壤況下，調整菜一門楣莢漾程之磊，裁鏈夠鱗決“瀑苗Ｐ’，毽是在萊焦情琵下，需要霹辯諼整－ｆ－ｊ甚至更多瓣諜程，才可敬“挪懣”一個可震教室空闋。繼篷丞數對多于兩門課程的計算為：ｆ（ｅｌ，ｃ２）＝ｆ（ｃＯ＋ｆ（ｃ９－Ｏ（ｃ，ｃ２）其中函數Ｏ（ｅｌ，吩為課程ｅｌ和ｃ２之間波及范圍的激疊部分。回溯的原則是，依次選擇波及范圍最小的課程進行試探調整，直到調熬成功或者所有囂櫟謙程全都試探完畢為止。由予調熬囂標謀程耱辯麓綴念會雩｜莛囂闥霞褒瓣鬻低，因筵，冀法將營先試圖調整目標課程的教室，來尋找Ｗ安排空間。每次試閣調整都檢查是否可以滿足當前課程的教黧安排，如果能，則瑪上退出，進入第四步。如果在搜索究全部目標課程后，發現僅調整教室無法滿足要求，那么算法將從頭開始進行調熬時間安接的試探，這～步與算法二相似，瞬樣要進行時闖優璇降低限度的檢查，一個原翔是，課程懿溪整凌不盎誨辯窩綴會餞度降低虱霜產瑟求戇囂瘦疆下。第四步，對由第三步產生的Ｗ調整目標課程避行調整，同時對當前諜程進行教室安排。

重慶大學磋七學技論文４教室安攆舞法強４．３靼溯算法三滾程強Ｆｉｇｕｒｅ４．３ＦｌｏｗｃｈａｌｔｏｆＢａｃｋｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｉｃ·３