目標(biāo)空間分割多目標(biāo)進(jìn)化算法及其應(yīng)用研究.pdf

1、進(jìn)化算法是建立在自然選擇原理和自然遺傳機(jī)制上的新型優(yōu)化算法,有著簡(jiǎn)單、通用、健壯性強(qiáng)、適于并行處理等顯著特點(diǎn)。多目標(biāo)優(yōu)化問(wèn)題是科學(xué)和工程研究領(lǐng)域的一個(gè)難題和熱點(diǎn)問(wèn)題,得到了社會(huì)各界的廣泛關(guān)注。研究表明,應(yīng)用進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題比較合適。
　　 近幾年來(lái),為了克服進(jìn)化算法的早熟收斂問(wèn)題,保持解群體的多樣性,很多研究者通過(guò)引用目標(biāo)空間劃分的思想來(lái)優(yōu)化多目標(biāo)問(wèn)題。本文針對(duì)現(xiàn)有基于目標(biāo)空間分割思想的進(jìn)化算法計(jì)算時(shí)間復(fù)雜度高的缺陷,

2、提出了一種改進(jìn)的基于目標(biāo)空間分割的多目標(biāo)進(jìn)化算法(OSD-MOEA),并利用該算法的目標(biāo)空間分割的思想解決了一種網(wǎng)格任務(wù)調(diào)度中并行程序的調(diào)度問(wèn)題。本文主要工作如下:
　　 1、本文通過(guò)引用目標(biāo)空間劃分的思想來(lái)優(yōu)化多目標(biāo)問(wèn)題,提出了一種基于目標(biāo)空間分割思想的改進(jìn)的多目標(biāo)進(jìn)化算法(Improved MOEA based onobjectiv-space-divided,簡(jiǎn)稱OSD-MOEA)。該算法包含以下幾個(gè)方面:通過(guò)對(duì)解群體的目

3、標(biāo)空間分割特點(diǎn)的分析,提出了一種把個(gè)體之間的Pareto支配關(guān)系轉(zhuǎn)化成分割區(qū)間索引值的排序關(guān)系的目標(biāo)空間分割算法；在目標(biāo)空間分割算法的基礎(chǔ)上,設(shè)計(jì)了一種簡(jiǎn)單、高效的基于分割區(qū)間索引值的環(huán)境選擇操作算子。該算子不需要比較個(gè)體之間的支配關(guān)系,而是根據(jù)個(gè)體在當(dāng)前搜索目標(biāo)空間的分割區(qū)間索引值來(lái)完成多目標(biāo)進(jìn)化算法中的環(huán)境選擇操作。在對(duì)當(dāng)前搜索目標(biāo)空間進(jìn)行分割時(shí),無(wú)法避免在同一分割區(qū)間內(nèi)存在多個(gè)個(gè)體,為了保持群體的分布性,本文設(shè)計(jì)了一種快速的優(yōu)先選

4、擇最接近分割區(qū)間原點(diǎn)的個(gè)體擁擠機(jī)制。
　　 2、針對(duì)提出的OSD-MOEA算法,本文進(jìn)行了大量的仿真實(shí)驗(yàn),通過(guò)計(jì)算一組有代表性的測(cè)試函數(shù),與目前性能較好的多目標(biāo)進(jìn)化算法NSGA2和基于目標(biāo)空間分割的PSFGA進(jìn)行比較,分析了OSD-MOEA的各項(xiàng)性能。結(jié)果表明該算法提高了算法的運(yùn)行效率,降低了算法的時(shí)間復(fù)雜度。
　　 3、針對(duì)網(wǎng)格中相互獨(dú)立的多任務(wù)調(diào)度問(wèn)題,本文提出了一種基于費(fèi)用-時(shí)間的網(wǎng)格任務(wù)調(diào)度算法(C&T-OSD-