多目標考試時間表改進算法范文

本站小編為你精心準備了多目標考試時間表改進算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《西安電子科技大學學報》2016年第二期

1求解考試時間表問題的進化多目標優化算法

本文是在文獻12的基礎上，針對算法的種群初始化操作，引入了超啟發方法；在算法的克隆操作中，設計了一種新的資源分配模型，是一種關于多目標考試時間表問題的NNIA改進算法，所以除種群初始化操作與克隆操作外，算法中的其他所有操作算子，以及算法流程與文獻12完全相同，算法流程如圖1所示。

1.1資源分配模型NNIA是一種經典的進化多目標優化算法，在此算法的運行過程中，只是采用少數的非支配個體進行操作，考慮到本文采用的多目標考試時間表的建模方式，在算法運行過程中，當出現非支配解數量不足的情況時，必然會對NNIA框架下的算法性能產生十分明顯的影響。顧本文在采用NNIA算法框架的基礎上，在個體克隆階段，設計了一種基于博弈論的資源分配模型，通過動態控制優勢個體的克隆數量手段，更加合理的分配計算資源。在資源分配模型中，根據非支配排序關系，待克隆的個體首先被劃分為不同的等級（R1,…,Rn）。其中，Ri代表了第i等級的個體的數量。通常情況下，R1中的個體優于其他個體。根據R1個體在所有待克隆個體中所占的比例r，將資源分配模型分解為早期模型、中期模型和后期模型。算法在運行過程中，根據不同的模型，采用相應的克隆策略。早期模型(r≤1/3)：在此階段只有很少的優秀個體（R1個體）。根據博弈論的相關概念，需要抑制R2中個體的克隆數量，以保證其無法影響到R1中的個體。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示資源分配模型計算過后，克隆后第i級別的克隆規模。

1.2基于超啟發方法的種群初始化許多學者的研究及仿真實驗表明[1]，基于圖著色的超啟發方法十分適合處理單目標考試時間表問題。采用超啟發方法擁有更大幾率快速找到可行解或潛在的優勢個體。針對本文所面對的多目標考試時間表問題，若能快速得到可行解或潛在的優勢個體，在固定的算法迭代次數的條件下，則更加有利于得到更好的結果。因此，本文采用基于圖著色的超啟發方法生成初始種群。其中，初始種群是由一定數量的初始解(時間表)構成的。首先，隨機產生由不同圖啟發算法構成的啟發式鏈表，根據啟發式鏈表，產生初始解（考試時間表）。在產生初始解的過程中，每當產生一個新的考試時間表示，通過這些不同的啟發式算法，可以產生一個考試科目安排順序，在不違反硬約束的條件下，根據考試安排順序，每門考試隨機安排在時間段中。具體的超啟發方法請參看文獻[1]。另外，本文采用二進制編碼方式，其中每一列代表一個時間段，每一行代表一門考試，數字1表示在此時段安排某門考試，0表示在此時段未安排考試。

2仿真實驗

本文選取Carter標準數據集[14]進行測試。近幾十年來，幾乎所有關于考試時間表算法的研究都采用此數據集進行性能測試，但此數據仍是開放數據，理論最優解仍然未知。本文選取了該數據集中的十個具有代表性的數據，對提出的算法進行仿真實驗。以下仿真均為10次獨立運行實驗，運行環境為2.8GHzCorePersonalComputer。具體參數如表1所示：針對10個測試數據，算法經過10次獨立運行，隨機選取一組解集，其pareto前沿面如圖2所示。少數幾個測試集（car91,car92,ear83等）在個別區域沒有找到非支配解。除上述測試集，大部分的測試集基本上能夠完整勾勒出2目標優化的pareto前沿面，并且對于每一組數據的pareto解都可以較為均勻的分布在其前沿面上。表2記錄了現今這些測試集的最好的運行結果，需要注意的是，此結果均為在單目標優化(固定時間表長度，只優化考試間沖突關系)的環境下產生的。我們選取的運行結果則是根據單目標環境下的時間表長度(P),在我們的多目標算法運行的結果中，選取的對應結果。從對比結果來看，除數據集york83，我們的算法均能找到與單目標模型中相同的時間段。從具體結果上來說，我們的結果的確與其他幾種最優秀的單目標優化結果尚存一定差距，但差距并不明顯。重要的是采用本文提出的多目標優化算法，經過一次運行就可提供不同時間段的多個解，運行效率是單目標優化的數十倍。上述結果表明，將考試時間表問題按照多目標優化問題建模有效且可以極大地提高計算效率。本文在NNIA框架下，在克隆階段采用了資源分配模型，此模型對于整個算法的影響可由下列實驗得出結論。圖3為十組測試數據分別來自為采用資源分配模型的RA-NNIA和未采用此模型的原始NNIA進行十次獨立運行后，非支配解個數的統計盒圖。針對每一個測試數據，左邊采用RA-NNIA，右邊采用NNIA。我們可以明顯看出，采用資源分配模型的RA-NNIA的非支配個體數量明顯的好于未采用的NNIA。圖4為十組測試數據，分別采用RA-NNIA和NNIA，經過十次獨立實驗后，spacing指標的統計盒圖對比。由圖可知，除少數幾組數據(car92,ear83)，采用RA-NNIA算法的均勻性指標都要優于采用NNIA的運行結果。根據以上兩組實驗結果分析可知，對于如此建模的多目標考試時間表問題，非支配解的數量本身就十分的有限，傳統的NNIA僅采用當前的非支配個體進行克隆，而后進行進化操作，導致種群的多樣性難以保持，很有可能進一步導致最終的非支配解數目不足，而RA-NNIA克隆階段，在非支配個體數量不足時，還會利用少部分較好的支配個體，共同進行克隆操作，并且，資源分配模型還會根據當前非支配個體所占的比例，動態控制每一部分個體的克隆比例，此種策略在一定的情況下可以很好地改善傳統NNIA在這方面上的不足。所以，采用資源分配模型的NNIA是有利于非支配個體的產生與保留，有利于算法的多樣性的保持，此策略十分適合用于求解多目標考試時間表問題的多目標進化算法。

3結束語

本文提出了一種解決多目標考試時間表問題的NNIA改進算法。在非支配鄰域免疫算法的框架下，提出了一種資源分配模型，用來動態控制個體的克隆比例，利用超啟發技術構造初始種群。實驗結果表明，采用筆者所提出的改進的NNIA能夠更加有效的解決多目標考試時間表問題。另外，筆者也注意到，原始的解決此問題的NNIA方法的局部搜索策略可以在一定程度上改善種群的質量，但仍有提高的空間。因此，針對此問題，以及類似的調度問題，如何來設計更加合理、出色的局部搜索策略將是今后有待研究的重要問題。

作者：雷雨 焦李成 公茂果 李玲玲 單位：西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室