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

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

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

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

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