论文部分内容阅读
摘要：遗传算法NSGAII在引入快速非支配排序算法、拥挤度算子以及精英策略后重复个体产生的概率明显上升，降低了帕累托效率。针对这一缺陷进行了改进，去除了重复个体并保持种群数量不变。根据遗传算法基因交叉变异的方法和差分进化算法DE的思想，将改进后的NSGAII算法与DE算法进行有效混合构建一种新的多目标优化算法。通过MATLAB对优化后的算法进行验证，结果表明优化后的算法在分布性和收敛性上都有所提高，搜索解的能力也有所提升。然后利用优化后的算法完成对μC/OSII任务管理部分的软硬件划分。
关键词：遗传算法;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年代末有了快速发展，并在人工智能和控制系统等领域得到了广泛的应用。在应用中也逐渐暴露了遗传算法的缺点，研究者开始针对遗传算法在具体方向上的缺点进行一系列的改进[2-6]。其中，Deb在2000年对NSGA算法提出了改进，算法NSGAII降低了算法的复杂度。NSGAII算法在执行过程中，经过交叉、变异操作很容易在同代以及父代之间生成相同个体，算法搜索新解的能力也因此受到很大影响，这种情况将导致算法运行的结果很容易是局部最优，不仅使得解很可能会丢失而且也会对算法的收敛速度有影响。文章首先对算法产生重复个体的问题进行了改进，改进后的算法在分布性上较原算法有一定提高。
差分进化算法[7-10]是一种以群体智能理论为基础模拟生物进化的优化算法，简单且高效的将适应环境的个体保留下来。差分进化以其较强的收敛能力、鲁棒性和强大的全局寻优能力使得该算法得到了广泛应用。
文章将改进后的NSGAII算法与DE算法进行了混合[11-14]。结合两种算法各自的优点，不仅将大量的优质解保留了下来，提高了优化效率，保证解的多样性，而且能够使目标向量在解空间中更有效的搜索最优解。优化后的算法较原算法提高了收敛速度，分布效果有了进一步提升，并且能够在解空间内更有效的搜索最优解。然后将该算法应用到μC/OSII任务管理部分的软硬件划分[15-17]中，在实践中检验该算法。
1NSGAII算法的改进
11改进后算法的流程
NSGAII算法在运行过程中个体重复率问题不容忽视，文章针对这一问题对算法进行了改进[18-21]。可以将改进后的算法叫作INSGAII算法。INSGAII算法利用STL中的关联容器MAP的特性去除基础群体中的重复个体，新的问题是去除后种群数量可能因此达不到n，这时候需要对种群重新进行交叉变异操作来维持种群数量n。NSGAII与INSGAII算法流程图分别如图1、图2所示，从图中可以看出，算法改进的地方是在合并新种群之后先进行了去重复操作。当种群数量小于n时，就会再一次进行交叉、变异等操作，然后再次执行去重复操作，这个过程循环执行，直到种群个体的数量满足条件后，再执行其他步骤。 12INSGAII算法测试结果及分析
文章使用MATLAB分别对NSGAII算法和INSGAII算法进行代码实现，参数的设置如表1所示。
2INSGAII与DE混合型优化算法
21混合算法的流程
文章借鉴了遗传算法和DE算法各自的优点。NSGAII算法在多目标优化问题的情况中，在算法运行后期容易陷入收敛缓慢的尴尬境地，而DE算法恰好具备较好的全局收敛能力;同时，DE算法由于其自身特性，如果子代的解不优于父代的解时，会有很多Pareto解丢失，而NSGAII算法的快速非支配排序和种群多样性保持策略也能很好的解决这一问题。以此作为切入点将两种算法进行混合。优化后的算法称为DEINSGAII算法。DEINSGAII算法流程图如图4所示。
22DEINSGAII算法测试结果及分析
采用MATLAB实现DEINSGAII算法，参数的设置也如表1所示。采用实数编码，初始种群个体为0～1之间的任意实数。测试函数与上相同。
算法实现结果如图5所示，分别为INSGAII算法和DEINSGAII算法的測试结果，对比左右两张结果图可以发现优化后的算法在分布性上有了明显的提高。
3DEINSGAII算法的应用
文章利用DEINSGAII算法对μC/OSII任务管理部分进行软硬件划分。首先要收集任务管理各个模块的数据，包括软件运行时间、硬件运行时间、软件运行所需内存空间、硬件实现所需硬件资源、软件运行功耗和硬件运行功耗。将收集到的数据应用到优化后的算法中，实现软硬件划分。
31解在三维空间的展示
同样利用MATLAB对算法进行实现，只不过使用收集到的数据代替原来的测试函数，完成对任务管理模块的软硬件划分。算法的约束条件设置如表2所示。
在图中X轴Time为时间值，Y轴Space为空间值，Z轴Power为功耗值。图中点的分布相对来说比较分散，重复的也不多，很好的验证了INSGAII算法降低重复率的能力。
32解在二维空间的显示
为更方便观测数据特性，可以考虑将上述三维空间的图像投影到二维空间中，这样能更直观的对数据进行显示。考虑以时间功耗较小为目标。时间和功耗在二维空间的描绘如图7所示，优质解为靠近坐标轴和原点的点。图像的显示只能定性的观察，并不能定量计算结果，所以将划分的结果以文档的形式保存下来，根据实际需要选择适当的划分结果。文档中每一个结果点由时间、空间、功耗和划分编码组成。
选择的编码结果为36785，转化成二进制编码为1000111110110001。其中，1表示对应模块用硬件实现，0表示对应模块用软件实现，根据选择的编码结果，μC/OSII任务管理模块的一种实现方式为：OS_TCBInit、OSTaskStkinit、OSTaskStkChk、OSTaskDelReq、OSTaskDel、OSTaskSuspend、OSTaskQuery、OS_TaskStat和TaskStkClr用硬件实现;OS_Sched、OSTaskCreate、OSTaskCreateExt、OSTaskResume、OSTaskChPrio、OSTaskNameSet和OSTaskNameGet用软件实现。
4结语
文章首先对NSGAII算法在执行过程中可能存在重复个体的缺陷进行改进。利用MAP一对一不重复的特性去掉种群中的重复个体，同时利用交叉、变异等遗传操作使得种群总数量保持不变。然后利用改进后的算法与差分进化算法进行混合，将两种算法的优势发挥出来，优化后的算法不仅具有更好的分布性，收敛速度也有了提升，而且能够对解空间进行全面搜索。利用优化后的算法对μC/OSII任务管理部分进行软硬件划分，将改进后的算法应用于实践中。软硬件划分算法有很多种，并各具优点，已有很多将两种算法进行混合使得算法的收敛速度和精度有所提高，并具有很好的收敛速度和稳定性的案例。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，France，IEEE：2000
[3]高媛非支配排序遗传算法的应用与研究[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]范瑜， 金荣洪， 耿军平， 等 基于差分进化算法和遗传算法的混合优化算法及其在阵列天线方向图综合中的应用[J].电子学报，2004，12（12）：1997-2000
[8]王林， 陈璨 一种基于DE算法和NSGAII多目标混合进化算法[J]. 运筹与管理，2010，19（6）：58-64
[9]詹腾，张屹，朱大林，等基于多策略差分进化算法的元胞多目标遗传算法[J]. 計算机集成制造系统，2014，20（6）：1342-1351
[10]关志华，面向多目标优化问题的遗传算法的理论及应用研究[D].天津：天津大学，2002
[11]韩素娟， 李兰英 基于遗传和模拟退火混合的软硬件划分算法[D]. 哈尔滨：哈尔滨理工大学，2011
[12]邬峰，黄丽亚 自适应模拟退火遗传算法的改进与应用[J].微型机与应用，2010（9）：49-57
[13]谷萍萍嵌入式操作系统软硬件划分及设计[D].哈尔滨：哈尔滨理工大学，2012
[14]邓定胜 基于混合遗传算法和神经网络的软硬件划分算法[J]. 西南师范大学学报（自然科学版），2015，40（10）：29-33
[15]徐明，夏新军，陈吉华SOC设计中一种软硬件划分的性能评价方法[J].计算机工程，2004，30（21）：58-60
[16]高健，李涛 三种软硬件划分算法的比较分析[J]. 计算机工程与设计 2007， 28（14）：3426-3428
[17]陈小庆，侯中喜，郭良民，等 基于NSGAII的算法改进多目标遗传算法[J]. 计算机应用 2006， 26（10）：2453-2455
[18]孙泽宇，魏巍 一种改进蚁群算法组合优化问题的研究[J].计算机仿真2010（8） ：136-144
[19]郭广寒，王志刚 一种改进的粒子群算法[J]. 哈尔滨理工大学学报，2010，2（2）：31-34
[20]黄超，胡德敏，于星 一种基于向量空间模型的NSGAII改进算法[J].小型微型计算机系统，2015，2（2）：220-221，266
[21]周雁，陈盈，张敏，等 粒子群优化在嵌入式软硬件划分中的应用[J].计算机应用与软件，2011（9）：162-171
（编辑：关毅）
关键词：遗传算法;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年代末有了快速发展，并在人工智能和控制系统等领域得到了广泛的应用。在应用中也逐渐暴露了遗传算法的缺点，研究者开始针对遗传算法在具体方向上的缺点进行一系列的改进[2-6]。其中，Deb在2000年对NSGA算法提出了改进，算法NSGAII降低了算法的复杂度。NSGAII算法在执行过程中，经过交叉、变异操作很容易在同代以及父代之间生成相同个体，算法搜索新解的能力也因此受到很大影响，这种情况将导致算法运行的结果很容易是局部最优，不仅使得解很可能会丢失而且也会对算法的收敛速度有影响。文章首先对算法产生重复个体的问题进行了改进，改进后的算法在分布性上较原算法有一定提高。
差分进化算法[7-10]是一种以群体智能理论为基础模拟生物进化的优化算法，简单且高效的将适应环境的个体保留下来。差分进化以其较强的收敛能力、鲁棒性和强大的全局寻优能力使得该算法得到了广泛应用。
文章将改进后的NSGAII算法与DE算法进行了混合[11-14]。结合两种算法各自的优点，不仅将大量的优质解保留了下来，提高了优化效率，保证解的多样性，而且能够使目标向量在解空间中更有效的搜索最优解。优化后的算法较原算法提高了收敛速度，分布效果有了进一步提升，并且能够在解空间内更有效的搜索最优解。然后将该算法应用到μC/OSII任务管理部分的软硬件划分[15-17]中，在实践中检验该算法。
1NSGAII算法的改进
11改进后算法的流程
NSGAII算法在运行过程中个体重复率问题不容忽视，文章针对这一问题对算法进行了改进[18-21]。可以将改进后的算法叫作INSGAII算法。INSGAII算法利用STL中的关联容器MAP的特性去除基础群体中的重复个体，新的问题是去除后种群数量可能因此达不到n，这时候需要对种群重新进行交叉变异操作来维持种群数量n。NSGAII与INSGAII算法流程图分别如图1、图2所示，从图中可以看出，算法改进的地方是在合并新种群之后先进行了去重复操作。当种群数量小于n时，就会再一次进行交叉、变异等操作，然后再次执行去重复操作，这个过程循环执行，直到种群个体的数量满足条件后，再执行其他步骤。 12INSGAII算法测试结果及分析
文章使用MATLAB分别对NSGAII算法和INSGAII算法进行代码实现，参数的设置如表1所示。
2INSGAII与DE混合型优化算法
21混合算法的流程
文章借鉴了遗传算法和DE算法各自的优点。NSGAII算法在多目标优化问题的情况中，在算法运行后期容易陷入收敛缓慢的尴尬境地，而DE算法恰好具备较好的全局收敛能力;同时，DE算法由于其自身特性，如果子代的解不优于父代的解时，会有很多Pareto解丢失，而NSGAII算法的快速非支配排序和种群多样性保持策略也能很好的解决这一问题。以此作为切入点将两种算法进行混合。优化后的算法称为DEINSGAII算法。DEINSGAII算法流程图如图4所示。
22DEINSGAII算法测试结果及分析
采用MATLAB实现DEINSGAII算法，参数的设置也如表1所示。采用实数编码，初始种群个体为0～1之间的任意实数。测试函数与上相同。
算法实现结果如图5所示，分别为INSGAII算法和DEINSGAII算法的測试结果，对比左右两张结果图可以发现优化后的算法在分布性上有了明显的提高。
3DEINSGAII算法的应用
文章利用DEINSGAII算法对μC/OSII任务管理部分进行软硬件划分。首先要收集任务管理各个模块的数据，包括软件运行时间、硬件运行时间、软件运行所需内存空间、硬件实现所需硬件资源、软件运行功耗和硬件运行功耗。将收集到的数据应用到优化后的算法中，实现软硬件划分。
31解在三维空间的展示
同样利用MATLAB对算法进行实现，只不过使用收集到的数据代替原来的测试函数，完成对任务管理模块的软硬件划分。算法的约束条件设置如表2所示。
在图中X轴Time为时间值，Y轴Space为空间值，Z轴Power为功耗值。图中点的分布相对来说比较分散，重复的也不多，很好的验证了INSGAII算法降低重复率的能力。
32解在二维空间的显示
为更方便观测数据特性，可以考虑将上述三维空间的图像投影到二维空间中，这样能更直观的对数据进行显示。考虑以时间功耗较小为目标。时间和功耗在二维空间的描绘如图7所示，优质解为靠近坐标轴和原点的点。图像的显示只能定性的观察，并不能定量计算结果，所以将划分的结果以文档的形式保存下来，根据实际需要选择适当的划分结果。文档中每一个结果点由时间、空间、功耗和划分编码组成。
选择的编码结果为36785，转化成二进制编码为1000111110110001。其中，1表示对应模块用硬件实现，0表示对应模块用软件实现，根据选择的编码结果，μC/OSII任务管理模块的一种实现方式为：OS_TCBInit、OSTaskStkinit、OSTaskStkChk、OSTaskDelReq、OSTaskDel、OSTaskSuspend、OSTaskQuery、OS_TaskStat和TaskStkClr用硬件实现;OS_Sched、OSTaskCreate、OSTaskCreateExt、OSTaskResume、OSTaskChPrio、OSTaskNameSet和OSTaskNameGet用软件实现。
4结语
文章首先对NSGAII算法在执行过程中可能存在重复个体的缺陷进行改进。利用MAP一对一不重复的特性去掉种群中的重复个体，同时利用交叉、变异等遗传操作使得种群总数量保持不变。然后利用改进后的算法与差分进化算法进行混合，将两种算法的优势发挥出来，优化后的算法不仅具有更好的分布性，收敛速度也有了提升，而且能够对解空间进行全面搜索。利用优化后的算法对μC/OSII任务管理部分进行软硬件划分，将改进后的算法应用于实践中。软硬件划分算法有很多种，并各具优点，已有很多将两种算法进行混合使得算法的收敛速度和精度有所提高，并具有很好的收敛速度和稳定性的案例。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，France，IEEE：2000
[3]高媛非支配排序遗传算法的应用与研究[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]范瑜， 金荣洪， 耿军平， 等 基于差分进化算法和遗传算法的混合优化算法及其在阵列天线方向图综合中的应用[J].电子学报，2004，12（12）：1997-2000
[8]王林， 陈璨 一种基于DE算法和NSGAII多目标混合进化算法[J]. 运筹与管理，2010，19（6）：58-64
[9]詹腾，张屹，朱大林，等基于多策略差分进化算法的元胞多目标遗传算法[J]. 計算机集成制造系统，2014，20（6）：1342-1351
[10]关志华，面向多目标优化问题的遗传算法的理论及应用研究[D].天津：天津大学，2002
[11]韩素娟， 李兰英 基于遗传和模拟退火混合的软硬件划分算法[D]. 哈尔滨：哈尔滨理工大学，2011
[12]邬峰，黄丽亚 自适应模拟退火遗传算法的改进与应用[J].微型机与应用，2010（9）：49-57
[13]谷萍萍嵌入式操作系统软硬件划分及设计[D].哈尔滨：哈尔滨理工大学，2012
[14]邓定胜 基于混合遗传算法和神经网络的软硬件划分算法[J]. 西南师范大学学报（自然科学版），2015，40（10）：29-33
[15]徐明，夏新军，陈吉华SOC设计中一种软硬件划分的性能评价方法[J].计算机工程，2004，30（21）：58-60
[16]高健，李涛 三种软硬件划分算法的比较分析[J]. 计算机工程与设计 2007， 28（14）：3426-3428
[17]陈小庆，侯中喜，郭良民，等 基于NSGAII的算法改进多目标遗传算法[J]. 计算机应用 2006， 26（10）：2453-2455
[18]孙泽宇，魏巍 一种改进蚁群算法组合优化问题的研究[J].计算机仿真2010（8） ：136-144
[19]郭广寒，王志刚 一种改进的粒子群算法[J]. 哈尔滨理工大学学报，2010，2（2）：31-34
[20]黄超，胡德敏，于星 一种基于向量空间模型的NSGAII改进算法[J].小型微型计算机系统，2015，2（2）：220-221，266
[21]周雁，陈盈，张敏，等 粒子群优化在嵌入式软硬件划分中的应用[J].计算机应用与软件，2011（9）：162-171
（编辑：关毅）