資源描述：
《求解置換流水車間調(diào)度問題的改進遺傳算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、502009，45（36）ComputerEngineeringandApplications計算機工程與應(yīng)用求解置換流水車間調(diào)度問題的改進遺傳算法涂雪平，施燦濤，李鐵克TUXue-ping，SHICan-tao，LITie-ke北京科技大學(xué)經(jīng)濟管理學(xué)院，北京100083SchoolofEconomyandManagement，UniversityofScienceandTechnologyBeijing，Beijing100083，ChinaE-mail：tuxueping1@126.comTUXue-ping，SHICan-tao，LITie-ke.Impro
2、vedgeneticalgorithmforpermutationflow-shopproblem.ComputerEngineeringandApplications，2009，45（36）：50-53.Abstract：Accordingtothefeaturesofpermutationflow-shopproblemandtheprematuredefectofGA，animprovedGAforthisproblemisproposed.IntheprocessofproposedGA，theNEHandthePalmerheuristicsareuse
3、dtoinitializethepopulationtoimprovethequalityoftheinitialsolutions，theMetropolisruleisemployedinchromosomeselectionforavoidingfallintolocaloptimum，andthetabu-searchalgorithmisembeddedtogetawayfromcircuitoussearch.Inordertosavethegeneticinformationofexcellentchromosomes，an“elitemechani
4、sm”ispresentedtoremembergoodgenes，andthebestsolutionswillbesavedineachrun.Theauto-adaptiveterminationruleissuggestedtofurtherimprovesolutionquality.Atlast，theeffectivenessoftheimprovedGAisverifiedbasedonsomebenchmarkproblems.Theresultsshowthatthesolutionqualityandtheconvergencespeedar
5、ebet－terthantheNEHandoriginalGAinitializedbyheuristicalgorithm.Keywords：permutationflow-shopproblem；GeneticAlgorithm（GA）；Metropolisrule；tabusearch；elitemechanism摘要：針對置換流水車間調(diào)度問題的基本特征和傳統(tǒng)遺傳算法易早熟的缺陷，設(shè)計了改進遺傳算法來求解此問題。采用NEH和Palmer啟發(fā)式算法進行種群初始化，以提高初始解的質(zhì)量；根據(jù)Metropolis準(zhǔn)則對染色體進行選擇操作，避免陷入局部最優(yōu)；在變異過程
6、中引入禁忌算法，避免迂回搜索；在算法迭代過程中引入了保優(yōu)機制，避免丟失優(yōu)秀染色體的基因信息；采用自適應(yīng)終止準(zhǔn)則，以保證解的質(zhì)量?；诘湫虰enchmark算例的仿真實驗結(jié)果表明，算法在求解質(zhì)量和收斂速度方面明顯優(yōu)于NEH算法和種群經(jīng)過初始優(yōu)化的傳統(tǒng)遺傳算法。關(guān)鍵詞：置換流水車間調(diào)度；遺傳算法；Metropolis準(zhǔn)則；禁忌搜索；保優(yōu)機制DOI：10.3778/j.issn.1002-8331.2009.36.016文章編號：1002－8331（2009）36-0050-04文獻標(biāo)識碼：A中圖分類號：TP181引言在現(xiàn)有研究中，文獻[5]將NEH算法和蟻群算法結(jié)合起
7、來進行置換流水車間調(diào)度問題廣泛存在于生產(chǎn)系統(tǒng)和服務(wù)系統(tǒng)求解，使用插入型局部搜索策略；文獻[6]介紹了一種基于分支中，是典型的組合優(yōu)化問題，也是典型的NP難問題[1]，工件加界定法的算法，這種算法采用逐對比較的形式來獲得較優(yōu)解；工順序的多樣性和每道工序開工時間的差異性都將大大增加文獻[7]介紹了微粒群優(yōu)化算法來求解此問題，該算法引入交換求解此問題的難度[2]。當(dāng)只有2臺機器時，可以用一個多項式解子和交換序的概念，利用實數(shù)進行編碼；文獻[8]采用了基于回決此問題；但是當(dāng)機器數(shù)達(dá)到3臺時，其調(diào)度問題就屬于強NP溯策略和關(guān)鍵工序鄰域搜索的并行禁忌搜索算法來進行求解，難題[
8、3]。鑒于
