基于混合蟻群算法Job-Shop調度問題的研究與實現.pdf

1、Job-Shop調度問題是許多實際車間調度問題的簡化模型，是一個典型的NP-Hard問題，已被證明在多項式時間內得不到最優(yōu)值。蟻群算法是近年來興起的一種優(yōu)化算法，特別在解決組合優(yōu)化問題中被越來越多的人所采用。為了更好的解決Job-Shop調度問題，通常將一些解決某類問題的較好算法組合起來。 本文采用鄰域搜索混合蟻群算法和自適應遺傳蟻群混合算法來求解Job-Shop調度問題。針對蟻群算法的早熟收斂及收斂速度慢等問題，設計了一種基于

2、鄰域搜索的混合蟻群算法。運用具有可變鄰域搜索的變異算子對搜索結果進行優(yōu)化，該算子除了具有通常的變異作用外，還具備步長為2和3的局部搜索功能。最后針對經典Job-Shop調度問題中的LA類部分問題進行了仿真實驗，實驗結果對比表明，該算法求解Job-Shop調度問題具有較快的尋優(yōu)速度和更好的全局搜索能力，同時增加了解的多樣性，減小了陷入局部極值的幾率。在充分分析自適應遺傳算法和蟻群算法的基礎之上，并根據兩種算法的特點，將自適應遺傳算法與蟻群

3、算法動態(tài)融合來求解Job-Shop調度問題。首先，利用自適應遺傳算法全局、隨機、快速搜索特性生成部分優(yōu)秀染色體，將其轉化為蟻群算法所需的初始信息素分布，然后利用蟻群算法的正反饋、高效性求取Job-Shop調度問題的最優(yōu)解；其次，確定自適應遺傳算法與蟻群算法的最佳融合時機，避免自適應遺傳算法過早或過晚結束而影響整體算法的性能。最后，本文針對Job-Shop調度問題中的11個經典問題進行了仿真實驗。結果證明了自適應遺傳蟻群算法具有更好的全局