基于組合優(yōu)化問題的多目標(biāo)模因算法的研究.pdf

1、組合優(yōu)化問題，如旅行商問題(TSP)，車間調(diào)度問題(JSP)和軟件版本發(fā)布問題(NRP)等在現(xiàn)實(shí)世界中具有廣泛的應(yīng)用。由于這類問題擁有巨大的搜索空間和眾多局部最優(yōu)等因素的影響，沒有精確算法能夠保證獲得此類問題的最優(yōu)解。模因算法(MAs)是針對(duì)此類復(fù)雜優(yōu)化問題的一類進(jìn)化算法，它采用了全局搜索定位好的區(qū)域，再采用局部搜索定位好的最優(yōu)解。本文主要針對(duì)組合優(yōu)化問題，研究多目標(biāo)下的模因算法。本文包括以下幾個(gè)方面：
　　1、分析了具有代表性的

2、多目標(biāo)優(yōu)化算法，包括基于帶精英策略的快速非支配排序遺傳算法(NSGA-II)、基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)等，為后續(xù)的研究提供了支撐。
　　2、在基于分解的多目標(biāo)優(yōu)化框架下，本文采用了基因算法(GA)作為全局搜索，并使用了模擬退火算法(SA)作為局部搜索算法，便于在可能的最優(yōu)解的區(qū)域能夠進(jìn)行更加精細(xì)化的搜索，以保證算法具備更好的收斂性能。
　　3、本文分別使用了兩種自適應(yīng)性機(jī)制，通過分析歷史收斂性和多樣性信息，指

3、導(dǎo)局部搜索的過程，從而進(jìn)一步提高算法的效率。這兩種自適應(yīng)機(jī)制分別為基于子問題收斂實(shí)效信息的自適應(yīng)局部搜索和基于外部集信息的自適應(yīng)局部搜索。
　　4、將算法使用于軟件版本發(fā)布問題(NRP)和車輛路徑問題(VRP)；與其他算法的對(duì)比實(shí)驗(yàn)表明，提出的模因算法非常具有競爭力。此外，根據(jù)真實(shí)數(shù)據(jù)的NRP模型，分別建立了約束條件下的單目標(biāo)NRP和2個(gè)目標(biāo)NRP優(yōu)化模型（將約束違反程度作為第二個(gè)目標(biāo)），再分別采用多目標(biāo)算法與state-of-a