混合NSGAII和DE的優(yōu)化算法及應(yīng)用

李巖 張光武

摘要：遺傳算法NSGAII在引入快速非支配排序算法、擁擠度算子以及精英策略后重復個體產(chǎn)生的概率明顯上升，降低了帕累托效率。針對這一缺陷進行了改進，去除了重復個體并保持種群數(shù)量不變。根據(jù)遺傳算法基因交叉變異的方法和差分進化算法DE的思想，將改進后的NSGAII算法與DE算法進行有效混合構(gòu)建一種新的多目標優(yōu)化算法。通過MATLAB對優(yōu)化后的算法進行驗證，結(jié)果表明優(yōu)化后的算法在分布性和收斂性上都有所提高，搜索解的能力也有所提升。然后利用優(yōu)化后的算法完成對μC/OSII任務(wù)管理部分的軟硬件劃分。

關(guān)鍵詞：遺傳算法;NSGAII;差分進化算法;MATLAB;軟硬件劃分

DOI：10.15938/j.jhust.2018.05.013

中圖分類號： TP3162

文獻標志碼： A

文章編號： 1007-2683（2018）05-0075-05

Optimization Algorithm and Application of Hybrid NSGAII and DE

LI Yan，ZHANG Guangwu

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：Due to the introduction of fast nondominated sorting algorithms， crowding operators and elite strategy， the probability of repetition individual increased significantly in every population of NSGAII algorithm， reducing the Pareto efficiency It has been improved for this defect， removed the repeating individual and maintained the number of populations unchanged According to the genetic algorithm crossover and mutation method and differential evolution algorithm DE， the improved NSGAII and DE are combined to construct a new multiobjective optimization algorithm The algorithm takes DE as the main optimization method， and uses the basic idea and crossover and mutation method of genetic algorithm The optimization algorithm was verified by MATLAB The results show that the optimized algorithm has been improved in both distribution and convergence， and the capacity of search solution has also been improved At last ， the optimization algorithm is used to complete the hardwaresoftware partitioning of task management part in μC/OSII

Keywords：genetic algorithm; NSGAII; differential evolution algorithm; MATLAB; softwarehardware partitioning

0引言

遺傳算法[1]的研究始于20世紀50年代，在80年代末有了快速發(fā)展，并在人工智能和控制系統(tǒng)等領(lǐng)域得到了廣泛的應(yīng)用。在應(yīng)用中也逐漸暴露了遺傳算法的缺點，研究者開始針對遺傳算法在具體方向上的缺點進行一系列的改進[2-6]。其中，Deb在2000年對NSGA算法提出了改進，算法NSGAII降低了算法的復雜度。NSGAII算法在執(zhí)行過程中，經(jīng)過交叉、變異操作很容易在同代以及父代之間生成相同個體，算法搜索新解的能力也因此受到很大影響，這種情況將導致算法運行的結(jié)果很容易是局部最優(yōu)，不僅使得解很可能會丟失而且也會對算法的收斂速度有影響。文章首先對算法產(chǎn)生重復個體的問題進行了改進，改進后的算法在分布性上較原算法有一定提高。

差分進化算法[7-10]是一種以群體智能理論為基礎(chǔ)模擬生物進化的優(yōu)化算法，簡單且高效的將適應(yīng)環(huán)境的個體保留下來。差分進化以其較強的收斂能力、魯棒性和強大的全局尋優(yōu)能力使得該算法得到了廣泛應(yīng)用。

文章將改進后的NSGAII算法與DE算法進行了混合[11-14]。結(jié)合兩種算法各自的優(yōu)點，不僅將大量的優(yōu)質(zhì)解保留了下來，提高了優(yōu)化效率，保證解的多樣性，而且能夠使目標向量在解空間中更有效的搜索最優(yōu)解。優(yōu)化后的算法較原算法提高了收斂速度，分布效果有了進一步提升，并且能夠在解空間內(nèi)更有效的搜索最優(yōu)解。然后將該算法應(yīng)用到μC/OSII任務(wù)管理部分的軟硬件劃分[15-17]中，在實踐中檢驗該算法。

1NSGAII算法的改進

11改進后算法的流程

NSGAII算法在運行過程中個體重復率問題不容忽視，文章針對這一問題對算法進行了改進[18-21]?？梢詫⒏倪M后的算法叫作INSGAII算法。INSGAII算法利用STL中的關(guān)聯(lián)容器MAP的特性去除基礎(chǔ)群體中的重復個體，新的問題是去除后種群數(shù)量可能因此達不到n，這時候需要對種群重新進行交叉變異操作來維持種群數(shù)量n。NSGAII與INSGAII算法流程圖分別如圖1、圖2所示，從圖中可以看出，算法改進的地方是在合并新種群之后先進行了去重復操作。當種群數(shù)量小于n時，就會再一次進行交叉、變異等操作，然后再次執(zhí)行去重復操作，這個過程循環(huán)執(zhí)行，直到種群個體的數(shù)量滿足條件后，再執(zhí)行其他步驟。

12INSGAII算法測試結(jié)果及分析

文章使用MATLAB分別對NSGAII算法和INSGAII算法進行代碼實現(xiàn)，參數(shù)的設(shè)置如表1所示。

2INSGAII與DE混合型優(yōu)化算法

21混合算法的流程

文章借鑒了遺傳算法和DE算法各自的優(yōu)點。NSGAII算法在多目標優(yōu)化問題的情況中，在算法運行后期容易陷入收斂緩慢的尷尬境地，而DE算法恰好具備較好的全局收斂能力;同時，DE算法由于其自身特性，如果子代的解不優(yōu)于父代的解時，會有很多Pareto解丟失，而NSGAII算法的快速非支配排序和種群多樣性保持策略也能很好的解決這一問題。以此作為切入點將兩種算法進行混合。優(yōu)化后的算法稱為DEINSGAII算法。DEINSGAII算法流程圖如圖4所示。

22DEINSGAII算法測試結(jié)果及分析

采用MATLAB實現(xiàn)DEINSGAII算法，參數(shù)的設(shè)置也如表1所示。采用實數(shù)編碼，初始種群個體為0～1之間的任意實數(shù)。測試函數(shù)與上相同。

算法實現(xiàn)結(jié)果如圖5所示，分別為INSGAII算法和DEINSGAII算法的測試結(jié)果，對比左右兩張結(jié)果圖可以發(fā)現(xiàn)優(yōu)化后的算法在分布性上有了明顯的提高。

3DEINSGAII算法的應(yīng)用

文章利用DEINSGAII算法對μC/OSII任務(wù)管理部分進行軟硬件劃分。首先要收集任務(wù)管理各個模塊的數(shù)據(jù)，包括軟件運行時間、硬件運行時間、軟件運行所需內(nèi)存空間、硬件實現(xiàn)所需硬件資源、軟件運行功耗和硬件運行功耗。將收集到的數(shù)據(jù)應(yīng)用到優(yōu)化后的算法中，實現(xiàn)軟硬件劃分。

31解在三維空間的展示

同樣利用MATLAB對算法進行實現(xiàn)，只不過使用收集到的數(shù)據(jù)代替原來的測試函數(shù)，完成對任務(wù)管理模塊的軟硬件劃分。算法的約束條件設(shè)置如表2所示。

在圖中X軸Time為時間值，Y軸Space為空間值，Z軸Power為功耗值。圖中點的分布相對來說比較分散，重復的也不多，很好的驗證了INSGAII算法降低重復率的能力。

32解在二維空間的顯示

為更方便觀測數(shù)據(jù)特性，可以考慮將上述三維空間的圖像投影到二維空間中，這樣能更直觀的對數(shù)據(jù)進行顯示?？紤]以時間功耗較小為目標。時間和功耗在二維空間的描繪如圖7所示，優(yōu)質(zhì)解為靠近坐標軸和原點的點。圖像的顯示只能定性的觀察，并不能定量計算結(jié)果，所以將劃分的結(jié)果以文檔的形式保存下來，根據(jù)實際需要選擇適當?shù)膭澐纸Y(jié)果。文檔中每一個結(jié)果點由時間、空間、功耗和劃分編碼組成。

選擇的編碼結(jié)果為36785，轉(zhuǎn)化成二進制編碼為1000111110110001。其中，1表示對應(yīng)模塊用硬件實現(xiàn)，0表示對應(yīng)模塊用軟件實現(xiàn)，根據(jù)選擇的編碼結(jié)果，μC/OSII任務(wù)管理模塊的一種實現(xiàn)方式為：OS_TCBInit、OSTaskStkinit、OSTaskStkChk、OSTaskDelReq、OSTaskDel、OSTaskSuspend、OSTaskQuery、OS_TaskStat和TaskStkClr用硬件實現(xiàn);OS_Sched、OSTaskCreate、OSTaskCreateExt、OSTaskResume、OSTaskChPrio、OSTaskNameSet和OSTaskNameGet用軟件實現(xiàn)。

4結(jié)語

文章首先對NSGAII算法在執(zhí)行過程中可能存在重復個體的缺陷進行改進。利用MAP一對一不重復的特性去掉種群中的重復個體，同時利用交叉、變異等遺傳操作使得種群總數(shù)量保持不變。然后利用改進后的算法與差分進化算法進行混合，將兩種算法的優(yōu)勢發(fā)揮出來，優(yōu)化后的算法不僅具有更好的分布性，收斂速度也有了提升，而且能夠?qū)饪臻g進行全面搜索。利用優(yōu)化后的算法對μC/OSII任務(wù)管理部分進行軟硬件劃分，將改進后的算法應(yīng)用于實踐中。軟硬件劃分算法有很多種，并各具優(yōu)點，已有很多將兩種算法進行混合使得算法的收斂速度和精度有所提高，并具有很好的收斂速度和穩(wěn)定性的案例。INSGAII算法與其他算法進行組合在未來可以進一步研究。

參 考 文 獻：

[1]ZOU Y，I ZHUANG ZHEN QU AN，CHEN HU AN HUAN HW /SW Partitioning Based on Genetic Algorithm [J].Evolutionary Computation，2004（ 12）：628 - 633

[2]DEB K，AGRAWAL S，PRATAPA，et a1A Fast Elitist Nondominated Sorting Genetical Algorithm for MultiObjective Optimization：NSGAII[J]. Paris，F(xiàn)rance，IEEE：2000

[3]高媛非支配排序遺傳算法的應(yīng)用與研究[D].天津：天津大學，2009（3）：30

[4]For MultiObjective Optimization：NSGAII[A].Proc of the Parallel Problem Solving from Nature VIConf [C]//Paris，2010：849-958

[5]LYAN，L XIANYAO，G PINGPING，Z HONGJIEHardware Implementation of μC/OSII Based on FPGA[J].Proceedings of 2nd International Workshop on Education Technology and Computer Science，2010（6/7）：852-858

[6]L YAN，G PINGPING，W XIANSHANThe Implementation of Semaphore Management in Hardware Real Time Operating System [J].Information Technology Journal 2010，10（1）：158-163

[7]范瑜， 金榮洪， 耿軍平， 等 基于差分進化算法和遺傳算法的混合優(yōu)化算法及其在陣列天線方向圖綜合中的應(yīng)用[J].電子學報，2004，12（12）：1997-2000

[8]王林， 陳璨 一種基于DE算法和NSGAII多目標混合進化算法[J]. 運籌與管理，2010，19（6）：58-64

[9]詹騰，張屹，朱大林，等基于多策略差分進化算法的元胞多目標遺傳算法[J]. 計算機集成制造系統(tǒng)，2014，20（6）：1342-1351

[10]關(guān)志華，面向多目標優(yōu)化問題的遺傳算法的理論及應(yīng)用研究[D].天津：天津大學，2002

[11]韓素娟， 李蘭英 基于遺傳和模擬退火混合的軟硬件劃分算法[D]. 哈爾濱：哈爾濱理工大學，2011

[12]鄔峰，黃麗亞 自適應(yīng)模擬退火遺傳算法的改進與應(yīng)用[J].微型機與應(yīng)用，2010（9）：49-57

[13]谷萍萍嵌入式操作系統(tǒng)軟硬件劃分及設(shè)計[D].哈爾濱：哈爾濱理工大學，2012

[14]鄧定勝 基于混合遺傳算法和神經(jīng)網(wǎng)絡(luò)的軟硬件劃分算法[J]. 西南師范大學學報（自然科學版），2015，40（10）：29-33

[15]徐明，夏新軍，陳吉華SOC設(shè)計中一種軟硬件劃分的性能評價方法[J].計算機工程，2004，30（21）：58-60

[16]高健，李濤 三種軟硬件劃分算法的比較分析[J]. 計算機工程與設(shè)計 2007， 28（14）：3426-3428

[17]陳小慶，侯中喜，郭良民，等 基于NSGAII的算法改進多目標遺傳算法[J]. 計算機應(yīng)用 2006， 26（10）：2453-2455

[18]孫澤宇，魏巍 一種改進蟻群算法組合優(yōu)化問題的研究[J].計算機仿真2010（8） ：136-144

[19]郭廣寒，王志剛 一種改進的粒子群算法[J]. 哈爾濱理工大學學報，2010，2（2）：31-34

[20]黃超，胡德敏，于星 一種基于向量空間模型的NSGAII改進算法[J].小型微型計算機系統(tǒng)，2015，2（2）：220-221，266

[21]周雁，陳盈，張敏，等 粒子群優(yōu)化在嵌入式軟硬件劃分中的應(yīng)用[J].計算機應(yīng)用與軟件，2011（9）：162-171

（編輯：關(guān)毅）