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

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

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

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