基于混合蟻群算法Job-Shop調(diào)度問題的研究與實現(xiàn).pdf

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

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

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