CEGA淺談
No-wait job-shop scheduling (NWJSS)問題是許多帶有無等待限制的行業中存在的經典排程問題，例如金屬加工、塑膠、化工和食品行業。交叉熵（CE）作為一種新的元啟發式方法，可以成為解決NWJSS問題的替代方法。這種方法已經被用于組合優化、多元優化和稀有事件模拟。在這些問題上，CE的實作平均需要較少的計算時間就能得到最優值。然而，使用原始的CE來解決大規模的NWJSS需要高計算時間。而CEGA即交叉熵與遺傳算法的混合算法能夠很好解決這一問題。
本文還将CEGA與模拟退火遺傳算法、混合禁忌搜尋進行了比較，最終發現CEGA在計算時間上要遠遠優于這兩種算法。傳統的模拟退火遺傳算法具有以下缺點：
參數敏感性：模拟退火遺傳算法涉及到許多參數的設定，如初始溫度、冷卻率、交叉率、變異率等。這些參數的選擇對算法的性能和結果有重要影響，但确定合适的參數值通常是一項具有挑戰性的任務。
收斂速度：模拟退火遺傳算法在初始階段可能需要大量的疊代和搜尋才能找到一個較優的解。算法的收斂速度可能相對較慢，特别是在處理複雜問題或大規模問題時。
局部最優解問題：由于模拟退火遺傳算法使用了随機性操作，例如交叉和變異，存在一定的風險陷入局部最優解。這可能導緻算法無法達到全局最優解，而隻能找到局部較優解。
資源消耗：由于模拟退火遺傳算法需要進行大量的疊代和搜尋，是以它可能需要較長的計算時間和更多的計算資源。特别是在處理複雜問題和大規模問題時，算法的計算成本可能會顯著增加。
參數調優困難：确定合适的參數值對于模拟退火遺傳算法的性能至關重要。然而，找到最佳參數組合通常需要大量的實驗和經驗，并且可能需要針對不同的問題進行調優。
而混合禁忌算法同樣存在明顯的弊端：
參數選擇困難：混合禁忌算法涉及到多個參數的設定，如禁忌清單長度、禁忌疊代次數、鄰域搜尋政策等。确定合适的參數值并進行參數調優可能是一項具有挑戰性的任務。
局部最優解問題：混合禁忌算法使用了禁忌搜尋和鄰域搜尋政策來避免陷入局部最優解。然而，由于算法的随機性和啟發式政策的局限性，仍然存在一定的風險陷入局部最優解。
計算複雜度高：混合禁忌算法在每個疊代中需要進行禁忌清單的更新、鄰域搜尋和禁忌政策的應用等操作。這些操作可能導緻算法的計算複雜度較高，尤其在處理複雜問題和大規模問題時。
調優過程漫長：由于混合禁忌算法的參數較多且互相關聯，進行參數調優可能需要大量的實驗和經驗。尋找最佳參數組合可能需要漫長的試錯過程，增加了調優的難度和時間成本。
鄰域搜尋受限：混合禁忌算法的性能很大程度上依賴于鄰域搜尋政策。如果鄰域搜尋政策不夠全面或無法有效地跳出局部最優解，算法的性能可能會受到限制。
而CEGA能夠很好克服上述缺點，并提供以下的優勢：
組合優勢：CEGA結合了交叉熵和遺傳算法的優點，充分發揮了它們在解決問題時的不同特點和搜尋政策。通過結合兩種算法，CEGA能夠更全面地探索解空間并找到更優的解決方案。
具備全局搜尋能力：遺傳算法作為CEGA的一部分，具有較好的全局搜尋能力。它能夠通過選擇、交叉和變異等操作，不斷探索解空間，并逐漸優化解決方案。
适應性強：CEGA的交叉熵部分可以根據問題的特性和搜尋過程中的情況，動态地調整機率分布模型，使其适應不同的問題和搜尋空間。這種适應性使得CEGA在解決不同類型的NWJSS問題時更加靈活和有效。
改進性能：通過引入遺傳算法的元件，CEGA能夠在大規模NWJSS執行個體中顯著改善計算性能。遺傳算法通過并行搜尋和自适應性操作，加速了解的收斂和優化過程。
綜合效果優良：通過與其他元啟發式方法進行比較，CEGA在NWJSS問題中提供了更好或至少相等的完成時間。這表明CEGA在解決實際行業中的NWJSS問題時具有競争力和有效性。
總體而言，CEGA的性能優于模拟退火遺傳算法和混合禁忌搜尋（HTS），尤其是對于小規模執行個體而言。在未來的研究中，需要修改CEGA以獲得更好的性能，尤其是針對大規模執行個體。使用較低級别的程式設計語言實作可能會提高CEGA的性能。另外，建議将該算法應用于其他問題上。
