论文研究-改进的NSGA-II算法及其在星座优化设计中的应用.pdf

所需积分/C币:25 2019-09-13 02:28:19 656KB .PDF

针对NSGA-II算法中的模拟二进制交叉(SBX)算子以及NSGA-II在收敛速度及多样性保持方面性能的不足,将反向学习机制(OBL)应用到NSGA-II的初始化和进化过程中,并引入一种改进的算术交叉算子。ZDT系列测试函数在收敛性和多样性两个方面的评价结果表明,改进的NSGA-II算法在收敛速度、收敛性和多样性上优于NSGA-II算法。将改进的NSGA-II算法应用于卫星星座优化设计中,仿真结果表明改进的算法在卫星星座优化设计中比较有效。
肖宝秋,刘洋,戴光明:改进的NSGAⅡ算法及其在星座优化设计中的应用 2012,48(10) 其中N为种群规模,D为解空间的维数,x(0)为初 (1-a) 始时种群P的第i个个体第j维变量值,U和L分 XR=aXr+(I-a)X 别表示解空间中第j维变量的上下界。 其中a为参数,当a为常数时,称为均匀算术交叉;否 (2)计算反向种群P中的个体,ax0)为初始时则,则称为非均匀算术交叉2 种群P的第个个休第j维变量x(0)的相反变量, 考虑到在进化过程中,希望种群中较优(rk值 较低),分布度较好(dist值较大)的个体,在后代个体 即种群P'的第i个个体第j维变量,Ox,(O)如下计算 基因中占据的比例较大,为此本文设计了以下交叉 Ox1(0)=L1+U-x1(0) 算子系数 (3)从种群P和反向种群P中选择N个最优个 B rank A.rank≠B.rank 休作为初始种群 Arank +Brank (9) 33基于反向学习的进化 Drank= B rank A dist+B dist 将反向学习机制应用到进化过程中,在进化过其中,A,nk表示当前代的个体A的非支配排序等 程的每一代屮,对其种群P,计算其反向种群P,并级,At表示当前代的个体A的拥挤距离。这样, 从种群P和反向种群P中选择N个最优个体作为在算法的前期,较优个体的基因得到更好的保留,因 下一代进化的种群。 此算法收敛速度加快了;同时,在算法的后期,分布 但是,考虑到算法的后期,种群P已经形成定度较好的个体的基因得到了更好的保留,因此提高 的规律,接近最优求解区域,因此,在算法后期求解了算法的多样性。 反向种群的意义不大且减缓了算法的运行速度,因3.5改进NSGA算法流程 此,本文设计了如下方法 基于以上分析,改进的NSGA算法伪码如下: 在进化的过程的每一代中,对其种群P,以一定 /*Opposition-based population initialization*/ 的概率O( (opposite rate)计算其反向种群P,并且在 Random initialization of population P P进化的过程中,O是线性递减的即 Calculate opposite population P Selecting N fittest individuals from P and OP as ini O=max Or-c(maxO, -minO. (7) tial population 其中G为最大进化代数,g为当前代,maxO,和 /*End of Opposition-based population initialization*/ Evaluate initial population; minO分别为O的最大值和最小值。这样反向学习 While( the halting criterion is not satisfied 机制的应用就能加速算法的收敛。 同时,为保持种群的多样性,在进化过程中,当 Tournamenet Selections routines 种群个体x(g)和反向种群个体x(g)互不支配时 Arithmetic Crossover routines 以一定的概率ack( (accept rate)接受axn(g),同理,概 Polynomial Mutation routines: Evaluate population P: 率accR也是线性递减的,即: If(rnd(0,1)<O.) aCCR= max acc、 (max accR-min accR)(8) 其中, max accR和 min accr分别为ac的最大值 Compute opposite population P; Select PopSize fittest Individuals from P 和最小值。 34交叉算子的改进 交叉算子是遗传操作中最重要的操作,在交叉 过程中优秀个体的基因模式得以迅速繁殖并在种群 中扩散,使种群中其他个体能向最优解的方向行进。4数值实验 相比于模拟二进制交叉算子,算术交叉算子具4.1测试两数、评价标准及参数设置 有更好的全局搜索能力,能更好地保持种群的多样 为了验证改进NSGA-Ⅱ算法的性能,选用经典的 性。算术交叉操作如下:设x4和X分别为第t代两ZDT系列函数(ZDT1,ZDT2,ZDT3,ZDT6)作为测试 个待交义的个休的决策变量的实数编码,则交义后函数。 两个体的相应的决策变量值为: 测试结果的评价标准采用测试结果的收敛性和 50 2012,48(10) Computer Engineering and Applications计算机工程与应用 表1测试函数决策空间和目标空间的维数 进的NSGA-程序运行150代后的结果与标准前沿 测试函数 决策空间维数H标空间维数 的比较图 ZDTI. ZDT2, ZDT3 30 由表2到表5的数据可知,改进的NSGA-算法 ZDT6 10 2 在收敛性上表现优异,在四个测试函数上收敛性都 多样性评价。 优于NSGA-Ⅲ算法;同时,改进的NSGAⅡ算法在多 实验的参数设置:种样大小100,最大代数200,样性方面也有较大的改善,除了在ZDT2函数上多样 交叉概率0.9,变异概率0.1。 性不如NSGA-外,其他测试函数上的多样性均优于 改进NSGA中的两个概率的上下界: NSGA-II由图1到图4可以看出,改进的 NSGA-II maxO.=0.8,minO,=0.5; 算法的收敛速度优于NSGA-Ⅱ算法。由此证明了改 max accR-1.0, min accR=0.0o 进算法的有效性 42实验结果及分析 实验结果为10次运算的平均值。 5区城覆盖卫星星座优化设计 为了便于比较NSGAⅡ和改进的NSGA-II算法 星座是由一群共同上作的卫星组成,这些卫星 的收敛速度和收敛效果,图到图4为NSGA-Ⅱ和改的轨道参数由他们的应用领域和实现的性能所决 表2NSGA-与改进NSGA-Ⅱ在ZDT1函数上收敛性与多样性 ZITI 算法 收敛性 多样性 NSGA-II 0.00277211+-0.00140097 0.372788+-0.108156 改进NSGA-l 0.00111181+-0.000172208 0.370298+-0.0815029 表3NSGAⅡ与改进NSGA-ZDT2两数上收敛性与多样性 ZDT2 算法 收敛性 多样性 NSGA-II 0.00297525+-0.00223656 0.386197+-0.0671831 改进NSGA-I 0.000852262+-0.000107841 0.4171861-0.10672 表4NSGA-Ⅱ与改进NSGA-Ⅱ在ZDT3网数上收敛性与多样性 ZDT3 算法 收敛性 多样性 NSGA-II 0.00184749+-0.000186385 0.685294+-0.0449552 改进NSGA-I 0.00107189+-301321E-05 0.58475+-0.0886773 表5NSGAⅡ与改进NSGA在ZDT6函数上收敛性与多样性 ZDT6 算法 收敛性 多样性 NSGA-II 0.0192366+-0.00406833 0.374652+-0.0639926 改进 NSGA-1I 0.00486568+-0.00232125 0.317342+-0.0793183 ZDT1-150 gen ZDT2-150 gen 1.4 1.4 PF PF 1.2 t NSGA-II nSGA 改进NSGA-I 改进NSGA-l 1.0 0.8 0.8 0.6 0.4 0.2 0.2 00.10.20.30.40.50.60.70.80.91.0 00.I0,20.30.40.50.60.70.80.910 图1改进的NSGA-算法与NSGA-算法 图2改进的NSGA算法与NSGA-I算法 测试结果在ZDT1两数上与标准前沿示意图 测试结果在ZDT2两数上与标准前沿小意图 肖宝秋,刘洋,戴光明:改进的NSGAⅡ算法及其在星座优化设计中的应用 2012,48(10) ZDT3-150 gen ZDT6-150 gen 1.0 PF PF NSGA-II NSGA-II 0.8 改进NSGA- 改进 NSGA-II 0.6 0.7 0.4 0.2 -0.6 0.1 0.8 00.1020.30.40.50.60.70.80.9 0.20.30.40.50.60.70.80.91.0 FI 图3改进的NSGAⅡ算法与NSGA-Ⅱ算法 图4改进的 NSGA-II算法与NSGA-Ⅱ算法 测试结果在ZDT3函数上与标准前沿示意图 测试结果在ZDT6函数上与标准前沿示意图 定。卫星星座优化是一个复杂的多目标优化问题,求解其覆盖特性是很难的。本文采用的覆盖判定方 其主要目的是通过对星座的空间构型、几何参数等法为网格点法,如图6所示。对于给定的区域,按照 进行优化配置,实现系统性能指标与建设成本的综一定的经纬度步长将该区域划分成荇干个小网格 合最优。 网格上的点即为特征点。 区域覆盖的星座的优化设计涉及多个特征点和 网格相交点为特征点 多项优化指标,是一种比较典型的多目标优化问题, 优化设计的重点是在对整个星座结构部署和性能的 相可权衡上,其分析与设计总是基于总体日标和约 束条件,以可能的最低成本满足任务要求和约束条件。 中51星座编码 理论上,星座内的卫星可以位于任何轨道上,只 要他们共同完成某一特定的空间任务就可以认为是 图6网格点法示意图 个星座。星座的轨道控制参数由其所包含的所有 假设特征点的总数为n,当星座在一个给定的时 卫星参数组成。一颗卫星可以通过6个轨道参数来间段T内,对该区域内的特征点覆盖数量为m,那么 描述13 认为在T时间内,星座对该区域的覆盖率为m/n Sat=(a, e,i, O, 22, M) 星座设计优化的目标则为使得各个区域的覆盖率尽 其中,a为半长轴,e为偏心率,i为轨道倾角,为 量人。 近地点幅角,g为升交点赤经,M为平近点角。 但是从实际应用出发,星座设计应具有较稳定53卫星星座优化流程图 的构型,还应考虑卫星的发射方式4,使卫星易于 综合以上分析,则卫星犀座优化流程图见图7。 布置,因此,对尾座卫星的轨道要素进行如下约束 54卫星星座优化算例 星座的卫星应具有相同轨道形状,即半长轴和偏心 为检验改进算法在卫星星座优化设计中的性 率相同。 能,本文设计了一个优化实例。 因此,从优化的角度考虑,每颗卫星需要优化的 541优化参数设置 参数包括a、e、i;,o,、Ω,、M ,J∈(1,2 覆盖区域的日标个数为3个,其经纬度范围如下: 因此一个卫星星座有4N+2个参数需要优化。其中 F1(0E-20E,10N-30N N为星座中卫星的个数。则一个卫星星座的基因编 F2(30E-50E,40N-60N 码可如下表示: 0E-80E,65N-80N) 覆盖计算时,划分网格的经纬度步长为1度。 ae 1 o Oem 星座中卫星颗数为10,卫星轨道高度设定为 图5卫星星座编码格式 1000km,轨道偏心率设定为0,且星的扫描带宽为 52区域覆盖计算 200km 由于区域覆盖问题的非对称性,通常解析方法 仿真的起始时刻为40270000(MD2000时间 2 2012,48(10) Computer Engineering and Applications计算机工程与应用 初始化 星座 染色体 生成星座 计算各个采样时刻卫星星历 评价区域1的覆盖性能 评价区域2的覆盖性 生成新群体适应度计算 评段 价的 遗传学操作 评价区域K的覆盖性能 结束 图7卫星星座优化流程图 表6改进的NSGA-算法优化结果示例 卫星参数 e 区域覆盖率 i/rad /rad Q/rad M/rad 26306321.8044294.7492592.073297 3.5287861.3127242.4215884.957364 36786244.28185960676745.383832F1=1.00000000 3.9198054.1491544.6888615.223632 2.5077093.9312210.2053581.559211F2=0.98639456 7378.1370 19792001.7455560.2599135.202946 28058250.86616920024610.39278F3-100000 5.5121991.7686981.7690360.835521 1.05199124717440.3766054.222255 52423144.9880976.2613023.029424 即2011-1-100:00:00),仿真结束时刻为40280000G算法计算结果的数目。例如:假设NSGA运 (即2011-110:00:00),仿真时长为1天;仿真时间行结果为如下左侧数据,改进NSGA算法运行结果 的步长为1秒。 如下右侧数据 优化算法的参数设置如下:种群规模20,演化代 0.50.60.5 0.60.50.7 数100,其他参数和41节中设置相同。 0.60.40.5 0.50.60.4 54.2优化结果 0.40.50.6 0.70.40.5 针对设置的区域参数和卫星参数,应用NSGAⅡ则A=1010=1,B=21011=3 算法和改进的NSGAⅡ算法进行区域覆盖的卫星星 通过A、B值的大小在一定程度上可以反映NS 座优化设计,实验次数为5次。 GA-I算法和改进的NSGA-算法运行结果的优 个改进的NSGAⅡ算法的优化结果的示例如劣。表8反映的是5次实验结果的A、B值 表6。 表7实验结果中非支配数目比较 实验结果中的非支配个体数目在一定程度上可 以反映算法运行收敛速度和结果的收敛度。表7中 实验 实验结果中数 NSGA-II 改进NSGA- 反映的是5次实验结果中非支配个体的数目。 实验1 18 另外,在某一次实验中,定义A表示NSGA算 实验2 20 实验3 19 法计算结果支配改进的NSGA-I算法计算结果的数 实验4 目;B表示改进的NSGA-Ⅱ算法计算结果支配NS 实验5 19 19 肖宝秋,刘洋,戴光明:改进的NSGAⅡ算法及其在星座优化设计中的应用 2012,48(10) 表8实验结果中A、B值比较 计算机学报,2005,28(8) 实验结果A、B值 [5]郑强带精英策略的非支配排序遗传算法的硏究与应用[D] 实验 NSGA-II 改进NSGA-Ⅱ 杭州:浙江大学信息科学与工程学院,2006. 实验1 5334 [6 Rahnamayan S, Tizhoosh H R, Salama MM A Opposi 实验2 tion-based differential evolutional algorithms[C]i/Proceed 实验3 16 实验4 ing of the IEEE Congress on Evolutionary Computa- 实验5 tion,2006:2010-2017. [7 Rahnamayan S, Tizhoosh H R, Salama MM AOpposition 通过表6可知,改进的NSGA算法在区域覆盖 based differential evolution for optimization of noisy 卫星星座优化设计中性能优越,能使三个给定的区 problens[C]/Proceeding of the IEEE Congresson Evolu 域都有很高的覆盖率。同时,根据表7和表8的数据 tionary Computation, 2007: 1865-1872 也可以看出,改进的NSGA-Ⅱ算法在区域覆盖卫星星8] Rahnamayan S, TizhooshH r, Salama m ma. Opposition 座优化设计中的性能优于NSGAⅡ算法。 based differential evolution[J]. IEEE Trans on Evolution ary Computation, 2008, 12(1): 64-79 6总结 9] Wang H, Liu Y, Zeng S, et al. Opposition-based parti- 本文针对NSGA-算法的不足之处,将反向学习 cle swarm algorithm with cauchy mutation[C]/Proceed 机制应用到算法的初始化和进化过程中,并引入了 ng of the IEEE Congresson Evolutionary Computation 2007:4750-4756 改进的算术交叉算子代替原有的性能不高的模拟二 [10]王晖基于柯西变异的混合粒子群算法研究[D],武汉:中 进制交叉算子,得到了一种改进的NSGA-算法,实 国地质大学(武汉)计算机学院,2008 验结果表眀:改进NsGA-I算法在收敛速度、收敛性 [11 Peng Lei, Wang Yuanzhen, Dai Guangming. A novel op 以及多样性的保持上都有不同程度的提高。将NS- position-based multi-objective differential evolution al GA-ⅡI算法和改进的NSGA-Ⅱ算法应用于区域覆盖 gorithm for multi-objective optimization[c]/Advances 的卫星星座优化设计中得到了良好的效果。 in Computation and Intelligence Lecture Notes in Com puter Science,2008,5370:162-170 参考文献: [12]刘旭红,刘玉树,张国英,等多目标优化算法 NSGA-II的 [1]曾喻江基于遗传算法的卫星星座设计[D]武汉:华中科技 改进门计算机工程与应用,2005,41(15):73-75 大学通信与信息系统,2007 [13]王励,王炎娟,张辉,等基于NSGA算法的区域覆盖卫 [2]郑蔚模型多目标演化算法(OMEA)在星座优化设计中的 星星座优化「计算机仿真,2009,26(4) 应用研究[D]武汉:中国地质大学(武汉)计算机学院,2007.[14]王瑞,马兴瑞,李明采用遺传算法进行区域覆盖卫星星 [3]谢涛,陈火旺,康立山多日标优化的演化算法[计算机学 座优化设计[宇航学报,2002,23(3) 报,2003,26(8) [5]刘文,张育林,刘昆基于多目标进化算法的卫星通信星 [4]雷德明,吴智铭.基于个体密度距离的多日标进化算法门] 座优化设计[宇航学报,2008,29(1) 上接19页) learning and dccision making by clustering[J]. Interna [5] Bachrach J, Taylor C. Handbook of sensor networks [M] tional Journal of Computers and Their Applications [S]1: Wiley,2005 1997,4(3):31-43. [6] Zadeh L A Fuzzy sets and information granulation[M] [9] Kaburlasos V G, Athanasiadis I N, Mitkas P A Fuzzy Lattice Reasoning(FLR) classifier and its applicalion [S 1.]: North Holland Publishing, 1979 for ambient ozone estimation [J]. International Journal of [7 Zadeh L A Toward a theory of fuzzy information granu Approximate reasoning, 2007, 45: 152-188 lation and its centrality in human reasoning and fuzzy [10 Liu H, Xiong S, Fang Zhixiang. FL-GrCCA: a granular gic[]. Fuzzy Sets and Systems, 1997, 90(2): 111-127 computing classification algorithm based on fuzzy lat- [8] Kaburlasos V G, Petridis V Fuzzy Lattice Neurocomput- ticesj].computerSandMathematicswithApplications ing(Fln): a novel connectionist scheme for versatile 2011,61(1):138-147

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐