基于遗传算法计算弹道节省参数最优节点

基于遗传算法计算弹道节省参数最优节点（共7篇）

篇1：基于遗传算法计算弹道节省参数最优节点

基于遗传算法计算弹道节省参数最优节点

提出了计算弹道节省参数模型最优节点的`遗传算法.将采样时间范围视为染色体,利用实测数据与弹道节省参数模型拟合的误差设计适应度函数,当种群中最大的适应度经过n次迭代后不再变化时,将其作为算法终止条件,计算出最优节点序列.通过仿真计算表明,该算法计算量小、方法稳定.

作 者：周慧 孙艳英  作者单位：92941部队96分队,辽宁,葫芦岛,125001 刊 名：飞行器测控学报  ISTIC英文刊名：JOURNAL OF SPACECRAFT TT&C TECHNOLOGY 年，卷(期)： 28(5) 分类号：V557 关键词：节省参数模型   遗传算法   B样条  

篇2：基于遗传算法优化的节点定位技术

遗传算法计算简单,采用并行式处理方式,具有超高的的全局搜索能力,特别适用于节点定位优化函数的求解要求[1]。目前遗传算法被应用于优化处理、最优求解等多个方面[2~4]。遗传算法在求解最优解方面具有很大的优势,但也存在收敛速度慢,精度差等缺点。为保证算法的优越性,很多文献也做了许多的工作,文献[5]在算法中采用个体繁殖次数作为选择策略的评价因素,以保证算法的收敛性。文献[6]通过设计实现动态改变交叉概率和变异概率,提高进化能力和收敛速度。本文采用的定位算法首先用遗传算法优化节点间距离,再进行算法定位计算。

1 遗传算法

遗传算法简称GA (Genetic Algorithms)由美国Michigan大学的Holland教授首次提出,该算法模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。该算法采用种群进化描述所求问题的解,发挥群体搜索优势,运用遗传算子的方式产生后代,通过周而复始的进化,求解全局最优解。

1.1 遗传算法的求解步骤[7]

第一步:系统初始化分析,确定研究的个体及决定个体的因素,建立系统的矩阵空间;

第二步:初始化种群的确定,确定种群生成的方法和规模;

第三步:确定染色体编码方法;

第四步:确定解码方法;

第五步:确定个体适应度的函数;

第六步:确定交叉方法和变异方法;

第七步:计算适应度的值,运用选择、交叉和变异的方法选择适应度高的个体;

第八步:生成新的种群,返回第三步,直到达到计算次数或是计算目标。

1.2 遗传算法的处理流程

遗传算法的处理流程如图1所示。

2 遗传算法的基本构成要素确定

1)参数的编码和解码方案

编码方案的设计影响到算法运算效率,目前采用的编码方案基本分为两大类,基于符号的编码和基于进制的编码。本文采用符号编码方式,用实数符号表示节点状态。

2)种群的初始化

种群的初始化大多采用随机生成的方法,种群规模的大小具有较大的影响,规模过大,算法的复杂度增加,效率较低;规模过小,算法搜索空间受限,容易局部最优。在实际规模确定时,根据系统问题的需求和算法运行的实际效果对其进行调整。

3)适应度函数

本文的适应度函数为其中yij为决策变量,当染色体所包含的基因片段(i,j)顺序不变则yij=1,否则yij=0。如果染色体中出现环路,则该条染色体的适应度值为0。

动态路权矩阵W(t)越小,路径花费越小,染色体适应度越高, 则个体被遗传至下一代的可能性越高。本文的权值计算采用动态调整的方式,初始化设置为0.5,增大W的值,在一次训练完成后,如果最大的适应度值增大,则继续增大W的值。反之,则减小W的值。

4)遗传算子的设计

(1)选择算子

(1)选择算子目前选择算子的选择方法主要有排序选择法、分级选择法和赌盘选择法和随机遍历抽样法等[8]。本文选择方法采用赌盘选择法,该方法将每个染色体被选中的概率与其适应度值的大小成正比,当种群规模为N,第i个个体的适应度值为f(i),则该个体被选择的概率为:

个体适应度高的个体被选择的概率较大,方法简单,容易执行。可是如果在个体适应度差距不大时,容易陷入早熟和停滞问题。为了避免这一问题的发生,本文在赌盘选择法的基础上,添加最优遗传策略,将适应度最大的染色体直接进入下一代,以确保算法收敛。

(2)交叉算子

目前常用的交叉方法有单点、多点和循环等方法,本文采用单点、算术交叉的方法产生新的个体。父代个体为f1、f2,交叉后的子代用s1,s2表示,交叉的表达式为:

α是交叉系数,数值由进化代数所决定。

(3)变异算子

变异算子是用于辅助选择和交叉算子搜索最优解,可以保持种群的多样性,避免算法局部最优[9]。变异算子应避免变异后的路径中不包含环路、短路。根据变异概率pm选中进行变异的染色体,变异算子表示为:

其中ri为随机变量,vi和v'i为变异前后的值,本文变异算法采用保留最优个体的方法。

3 节点定位算法的数学模型

定位系统固定安装了n个锚节点,锚节点的位置信息包含在信息帧中。当未知节点需要进行网络定位时,向外广播发送信息帧,收到信息帧的锚节点将自身的位置和RSSI的平均值应答给未知节点。节点定位的实质就是根据周围m个建立通信的锚节点位置(xi,yi)和距离di,求取未知节点坐标值。定位的数据模型如下所示。

距离d是与RSSI相关的数值,本系统的RSSI与距离的公式计算采用遮蔽型,公式如下所示。

其中:

1λ为路径损耗系数,一般取2~5;ξ为随机数,符合高斯分布,平均值为0,其标准差一般取4~10;d0为参考距离;d为估计距离;Pr(d0)为参考距离的接收信号强度;Pr(d)为估计距离的接收信号强度。

定位算法分为二个阶段,第一步用遗传算法对节点接收到的RSSI的信号值进行距离的优化,第二步根据确定的距离值采用质心定位算法进行未知节点的计算。

4 仿真实验

本文使用Matlab7.0作为仿真工具,对本文提出的基于遗传算法修正的定位算法进行仿真实验。本文的实验环境设定在100×100范围内,首先布置25个锚节点,随机生成50个未知节点,取个体数目为30个,Pc取0.6,Pm取0.05,其中锚节点比例根据实验需要进行动态调整。左下角节点坐标设定为(0,0),通信半径设定为50m。

定位平均误差定义为在锚节点设定好后,对布局后的环境范围内的m个节点进行节点定位,xreal、yreal为未知节点的实际坐标,x、y为未知节点的估计坐标,r代表了定位环境的通信半径。

锚节点的初始布局如图2所示,锚节点的布局对于节点定位的影响是比较大的,本文采用初始均匀的布局方式,在定位的后续调试中,在误差较大或是多径影响较大的地区,增加锚节点的个数。遗传算法的种子的数量和迭代的次数由图3所示,迭代的次数受种子数量的影响不大,有一定的随机性。平均定位误差如图4所示,锚节点个数增加能够降低平均定位误差值,但是增加了系统的成本,可根据定位精度要求确认最佳的锚节点个数。对比添加了遗传算法的定位算法,可以发现在定位误差上有了明显的下降,提高了系统的定位精度。

5 结束语

节点定位技术是无线传感网络研究的重点内容之一,本文针对于基于距离的节点定位技术,为提高节点定位的精度,将遗传算法用于节点定位。充分利用遗传算法在求解最优解方面的优势,用遗传算法首先进行基于距离的最优解的求解,然后进行质心定位。仿真结果表明,通过增加锚节点的数量和遗传算法的优化处理都能够提高节点定位的精度,该方法可用于节点定位的优化处理。

摘要：针对于基于距离的节点定位技术,为提高节点的定位精度,将遗传算法用于距离的优化处理。本文首应用遗传算法进行基于距离的最优解的求解,然后将求解后的结果用于质心定位算法。仿真结果表明,应用遗传算法优化后的定位算法,节点定位精度明显提高,可用于节点定位技术的优化处理。

关键词：ZigBee网络,节点定位,遗传算法

参考文献

[1]王开郁.遗传算法在无线传感器网络中的应用[J].信息技术,2009,32(7):81-84.

[2]王越,张宁.基于遗传算法的无线传感网络定位参数优化[J].计算机应用与软件,2010,7(27):91-93.

[3]章磊,段莉莉,钱紫鹃,黄光明.基于遗传算法的WSN节点定位技术[J].计算机工程,2010,36(10):85-87.

[4]廖萍,孔翠香.一种基于遗传算法的无线传感器网络节点定位技术的研究[J].井冈山大学学报(自然科学版),2011,32(4):71-75.

[5]杨溪.改进遗传算法和蚁群算法在电力系统问题中的应用研究[D].太原理工大学,2013.

[6]胡小兵,吴树范,江驹.一种基于遗传算法的求代数方程组数值解的新方法[J].控制理论与应用,2002,19(4):567-570.

[7]Baluja S,Davies S.Using optimaldepedency-trees for combinatorial optimization:Learning the structure of the search space.In:Proceedings of the 14th International Conference on Machine Learning[M].San Francisco,CA:Morgan Kaufman,1997:30-38.

[8]贺智明.基于改进型量子遗传算法的无线传感器网络定位研究[D].江西理工大学,2013.

篇3：基于遗传算法计算弹道节省参数最优节点

基于多光束干涉理论建立了单层薄膜的透射率模型，并且得到了薄膜透射率与厚度及折射率之间的关系的数学模型，进而利用遗传算法求解该数学模型。根据薄膜透射光谱数学模型的特殊性，按照实际的精度需求，有针对性地选取了遗传算法中种群大小、交叉概率和变异概率等关键参数，并且针对透射光谱的具体情况，设计了离散化的适应度函数。最终的拟合结果表明，基于遗传算法的透射光谱法能够快速、准确地得到薄膜的光学参数。

关键词：

透射光谱； 薄膜光学参数； 遗传算法

中图分类号： TN 20文献标志码： Adoi： 10.3969/j.issn.10055630.2016.06.013

Abstract：

Mathematic model of the transmitted spectrum of thin films was established by multibeam interference theory.The relationship of transmittance，thickness and refractive index was built. Then the mathematic model could be solved with the genetic algorithm. In consideration of the special character of the optical film value of key parameters of genetic algorithm would be a special choice. Key parameters included population size crossover probability and mutation probability. Fitness function was designed to be discretized. Finally the fitting results proved that the method could calculate the parameters of optical films at the same time.

Keywords：

transmitted spectrum； thin film optical parameters； genetic algorithm

引言

隨着现代光学技术的发展，光学薄膜成为提高各种光学元器件性能的一种重要手段。近几年新的薄膜技术的国家标准相应出台[1]，也使薄膜参数的检测方法受到更多的重视。目前，制备光学薄膜的主要工艺包括：物理气相沉积（PVD）、化学气相沉积（CVD）和溶胶凝胶法等。物理气相沉积主要包括：热蒸发、溅射、离子镀等[2]。

现有的薄膜参数测试方法很难同时测量薄膜的各个参数。测量薄膜厚度的常用仪器有：台阶仪、椭偏仪[3]。台阶仪通过金属探针在样品表面划动，检测出台阶状薄膜表面的高度差，因有物理接触会划伤样品表面，而且必须在样品表面构建台阶结构。椭偏仪通过测试透射的偏振光的偏振性变化，可以得到样品的厚度，虽然精度较高，但是需要已知材料的折射率。测量薄膜材料的折射率可以通过薄膜波导法，在一定的波长范围内，通过导模的泄露模虽然可以测得某确定波长的折射率和大致的薄膜厚度，但是需要薄膜的厚度达到一定的条件，并且只能测试某些特定波长的折射率。传统的光谱法测量薄膜的材料色散曲线，需要在已知薄膜厚度的情况下，通过单纯性法迭代优化后才能得到相应的折射率与波长的曲线模型[47]。在某些特殊情况下的薄膜透射光谱中，单纯性法并不能准确获得足够数量或者足够明确的极值点的数量，从而不能完成对薄膜参数的迭代测量。

面对生产加工中的实际需求，需要获得一种高精度的、快速方便的测量方法，同时获得所需光学薄膜的厚度、折射率波长曲线，尤其是针对某些不能通过预先测量获得折射率的薄膜。

1氧化物薄膜制备及光谱测试

本实验利用镀膜技术制备了多种常用薄膜材料。采用了OPTORUN的800式镀膜机，以厚度为3 mm的同一批次生产的K 9光学玻璃作为衬底，制作了多种薄膜材料样品。本文以氟化镁（MgF2）薄膜为例，由PE公司的Lambda1050紫外可见近红外分光光度计测得氟化镁薄膜透射光谱，如图1所示。

2理论计算

2.1透射光谱模型建立

利用多光束叠加的原理推导单层薄膜的透射光谱[8]。多光束干涉的示意图如图2所示。光波E0入射到第一层薄膜，反射光E1、E2、E3、…在无穷远处发生干涉，同理透射光E′1、E′2、E′3、…在无穷远处发生干涉。其中入射介质为空气，其折射率nk为1，薄膜的折射率为n，基底玻璃的折射率为ng。

假设入射光的振幅为E0，则各透射光束的振幅分别为

3利用遗传算法求解数学模型

由上述可知，利用透射光谱法求解薄膜参数的过程就是求解式（8）的数学模型，实际上是一个多元非线性回归问题的求解。单一使用最小二乘法或者其他遍历算法很难获得实际上的全局最优解，因此，采用遗传算法来求解该数学模型。

3.1遗传算法的简介

遗传算法（genetic algorithm，GA）是由Holland J教授于1975年首次提出的一种将达尔文的进化论与计算机技术结合的启发式算法，其本质是一种高效的全局搜索算法[10]。遗传算法相对于传统算法的显著优势有：1）GA搜索过程依靠的是适应度函数，而不依赖于某些函数的求导或者其他信息，所以与目标函数是否是线性函数关系不大；2）GA计算时不依赖于梯度信息，其在整个可行域范围内进行搜索；3）由于人工编码，可将参数值限定在合理范围内，避免出现不合理的解。

nlc202309090942

3.2遗传算法的实现

遗传算法的主要工作流程如图4所示。遗传算法的主要工作包括以下几个部分[11]：

1）初始化种群

以氟化镁薄膜为例，此处的初始种群由a、b、d共3个变量对应的二进制数组合所得。每个变量在种群中所占位数由其变量范围的上下限的差值除以精度要求，再转换为二进制数。转换所得二进制数的位数即为对应的该变量在种群中所占位数。

以厚度d为例，初始设定氟化镁薄膜的厚度初值范围为[600，650]，单位为nm，精度为0.001 nm。由于

所以，在初始种群中，厚度d所占的种群长度为16位。同理，a、b所对应的种群长度可以由实际范围计算得到。在得到总的种群长度之后，种群中的每一个个体都由程序随机生成对应长度的初始种群。

2）适应度函数设计

在遗传算法中，适应度函数属于自然环境参数，通过每个个体的适应度函数值来对其进行判定。

在氟化镁薄膜参数的测定中，针对薄膜光谱离散化的特性，并且在透射光谱中存在较多的毛刺，适应度函数也采用了离散点判定的方法。每个个体的适应度函数值为拟合函数值与原函数值相差小于0.1的点的个数。

3）选择性复制、交叉、变异操作

选择性复制、交叉、变异操作都是算法模拟正常生物染色体复制的过程。选择性复制保证了适应度较高的个体有较大的概率复制到下一代。交叉、变异的操作保证了遗传算法能够在全局寻找最优解，而不是收敛于局部最优值。

交叉、变异的频率决定了遗传算法收敛特性的好坏，此处取常用推荐值，交叉的概率为0.25，变异的概率为0.01。

4） 代數（Generation）

Generation参数决定了算法进行迭代的次数，代数越多越逼近于全局最优解，但是在充分收敛的情况下没有必要设置较多的代数。在此处为保证充分收敛，同时为节省运算时间，Generation取1 000。

4测试结果

在经过多次的测试后，利用遗传算法求解光学薄膜透射光谱的数学模型，能够求解出光学薄膜的光学参数，所得结果见表1。

将拟合所得结果与原始透射光谱相比较，见图5。可以看到，拟合曲线与原始透射光谱有着较好的重合度，该方法能够快速准确地算得光学薄膜的参数。

5结论

基于遗传算法的透射光谱法，通过构建薄膜透射光谱的数学模型，再利用遗传算法求解光谱模型的待定系数，进而得到薄膜的主要光学参数。以上拟合计算结果表明：由遗传算法求解出的透射光谱与实验测得光谱基本一致，求解模型能够反映薄膜透射光谱的分布情况；在选取恰当的核心参数、合理设计适应度函数后，遗传算法能够准确地计算出模型的全局最优解；基于遗传算法的透射光谱法能够快速、准确地同时计算出薄膜的主要光学参数。

参考文献：

[1]高鹏 阴晓俊 赵帅锋 等. 光学薄膜技术标准发展综述[J]. 光学仪器 2014，36（5）： 465470.

[2]唐晋发 顾培夫 刘旭 等. 现代光学薄膜技术[M].杭州：浙江大学出版社，2006： 207225.

[3]刘细成 王植恒 廖清君 等. 用透射光谱和模拟退火算法确定薄膜光学常数[J]. 激光技术 2003，27（2）： 9496.

[4]王芳宁 王植恒 刘细成，等.正确使用多次测量法提高椭偏测量精度[J]. 激光杂志 2004，25（1）： 3234.

[5]POELMAN D， SMET P F. Methods for the determination of the optical constants of thin films from single transmission measurements： a critical review[J]. Journal of Physics D： Applied Physics 2003 36（15）： 18501857.

[6]OHLDAL I FRANTA D，OHLDAL M，et al. Optical characterization of nonabsorbing and weakly absorbing thin films with the wavelengths related to extrema in spectral reflectances[J]. Applied Optics 2001 40（31）： 57115717.

[7]NENKOV M PENCHEVA T. Calculation of thinfilm optical constants by transmittancespectra fitting[J]. Journal of the Optical Society of America A，1998 15（7）： 18521857.

[8]顾晓明 贾宏志 王铿 等. 透射光谱法测试薄膜的光学参数[J]. 光学仪器 2009，31（2）： 8993.

[9]KAR M. Error minimization in the envelope method for the determination of optical constants of a thin film[J]. Surface and Interface Analysis 2010 42（3）： 145150.

[10]CARICATO A P， FAZZI A LEGGIERI G. A computer program for determination of thin films thickness and optical constants[J]. Applied Surface Science 2005 248（1）： 440445.

[11]陈国良.遗传算法及其应用[M].北京：人民邮电出版社，1999： 37.

（编辑：刘铁英）

篇4：基于遗传算法的最优化问题求解

1 遗传算法的求解过程

生物遗传物质的主要的载体称为染色体,在遗传算法中,染色体通常是一串数据(或数组),它用来作为优化问题的解的代码,但它本身并不一定是解[3]。应用遗传算法求解一般要经过这样的几个过程[4]:首先,随机产生一定数目的初始染色体,由这些染色体组成一个种群,其中,种群中染色体的数目被称为种群的大小或规模。然后,用评价函数来评价得到的每个染色体的优劣,即染色体对环境的适应程度(称为适应度),用来作为以后遗传操作的依据。接着,进行选择过程,选择过程的目的是为了从当前种群中选出优良的染色体,使它们成为新一代的染色体,判断染色体是否优良的标准就是它们各自的适应度,也就是染色体的适应度越高,它被选择的机会就越多。通过选择过程,产生新的种群。再对这个新的种群进行一定概率的交叉操作,这个操作是遗传算法中的主要操作之一,类似于生物的杂交。然后进行变异操作,以挖掘种群中不同个体的多样性,克服其有可能陷入局部解的问题[5]。这样,经过上边的各种运算后产生的新的染色体称为后代。然后再对产生的后代重复进行选择、交叉和变异这几个操作,在迭代到设定的次数后,把生成的最好的染色体拿来作为优化问题的最优解。

2 用遗传算法求解最优化问题实例

应用遗传算法求解极大化问题:

2.1 初始产生pop_size个染色体

用染色体V=(x1,x2,x3)来作为解的代码。解的可行性由下面的检验函数检验:如果(x1<0‖x2<0‖x3<0)则不可行;如果x12+x22+x32>1则不可行。可知此模型的可行集包含于下列超几何体中

这样,可以从这个超几何体中抽取初始染色体x1=u(0,1),x2=u(0,1),x3=u(0,1)

其中u(0,1)表示服从区间[0,1]上的均匀分布的随机数。如果生成的染色体不可行,则拒绝接受,再重新生成一个新的染色体,如果可行,则接受它作为种群的一名成员。经过有限次抽样后,得到30个(设定种群的规模为30,即pop_size=30)可行的染色体。

2.2 计算每个染色体的评价函数值

计算产生的30个染色体的的函数值,并按照由高到低的顺序排序,记函数值最大的染色体编号为V1,其余的顺次为V2,V3,…,V30。

定义基于序的评价函数为[6]

其中,a为给定的一个介于0到1之间的数据,例如a=0.05,当i=1时,意味着染色体是最好的,i=30时是最差的。

2.3 选择过程

选择过程可以通过如下四步给出[7]:

步骤1对每个染色体Vi,计算累积概率qi:

步骤2从区间(0,q30]中产生一个随机数r。

步骤3若qi-1

步骤4重复步骤2和步骤3共30次,得到30个复制的染色体。

2.4 交叉操作

定义参数Pc作为交叉操作的概率,从i=1到30重复执行如下步骤:产生一个[0,1]之间的随机数r,若r

c为在(0,1)区间中产生的一个随机数,如果产生的两个新的后代X和Y均可行,则用它们代替父代,否则再一次产生随机数c,再进行染色体的交叉,直到得到的X和Y均可行或循环到给定的次数后结束。

2.5 变异操作

定义参数Pm作为遗传系统中的变异概率,从i=1到30重复执行如下步骤:产生一个[0,1]之间的随机数r,若r

用V=(x1,x2,…,xn)表示上面的过程中生成的父代,再按照以下方法对生成的父代进行变异[8]。设M为在初始化的过程中任意定义的一个较大的数,在n维欧氏空间中任意产生一个d作为变异的方向,计算染色体V+M·d的值并将其代入约束条件中,如果判断后是不可行的,那么将M调整为0和M之间的任意一个随机数,再重新计算新染色体V+M·d的值,然后再判断它的可行性,重复上述过程直到得到的新染色体通过检验为止。若在设定的迭代次数内未能得到新的可行解,那么将M赋值为0。上述操作结束后,用X=V+M·d这个新得到的染色体替换原先的染色体V。重复进行选择、交叉、变异操作,直到给定的迭代次数为止。

2.6 结果

将上边的步骤用C语言写成程序,并在VC++6.0下运行,当设定交叉概率为0.3,变异概率为0.2,迭代1000次时,求得的最好解是(0.5767,0.5768,0.5786),函数值是2.2795。当设定交叉概率为0.3,变异概率为0.05,迭代3000次时,求得的最好解为(0.5817,0.5732,0.5771),函数值是2.2795。由此,可以看出,最优解并不唯一。

为了验证结果是否为最好,又将上述算法在VB6.0下编程运行,同样设定交叉概率为0.3,变异概率为0.2,迭代次数为1000,经过很长时间的运行后,显示的结果为(0.577,0.507,0.635),函数值为2.269。而且在用VB运行时,若在用生成随机数Rnd()函数前加上初始化种子数语句Randomize,则每次运行的结果都有一点差别。所以在编写涉及大量计算的程序时,还是选用执行效率高且结果更优的C语言为好。

3 结论

本文给出了遗传算法的基本原理与步骤。将其应用于最优化问题,结合实例给出了详尽求解过程,并同时采用VC和VB编程。结果表明,在应用遗传算法求解最优化问题时,选用C语言编程求解,结果更加接近最优解,其求解效率也比VB语言要高。

摘要：遗传算法是一种有效的解决最优化问题的方法,在解决复杂的全局优化问题方面,遗传算法已得到了成功的应用。对遗传算法的基本步骤进行总结,通过最优化问题求解实例描述了遗传算法的具体运行过程,包括产生初始染色体、染色体评价、选择、交叉、变异等。分别应用VC和VB两种语言进行编程实现,结果表明,VC语言在运算效率和结果优度方面均比VB语言要好。

关键词：遗传算法,最优化问题,最优解,求解步骤,运算效率

参考文献

[1]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[2]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2004.

[3]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.

[4]黄少荣.遗传算法及其应用[J].电脑知识与技术,2008,4(7):1874-1876.

[5]岳嶔,冯珊.遗传算法的计算性能的统计分析[J].计算机学报,2009,32(12):2389-2392.

[6]刘宝碇,赵瑞清,王纲.不确定规划及应用[M].北京:清华大学出版社,2003.

[7]周丽,张智顺.遗传算法求解函数极值的应用[J].电脑知识与技术,2007,4(21):802-803.

篇5：基于遗传算法计算弹道节省参数最优节点

基金项目：国家自然科学基金资助项目（60974091）

作者简介：夏化冰（1971—），男，安徽合肥人，副教授，硕士，研究方向：炮兵通信指挥、遗传算法应用等。

通讯联系人，E-mail：pan.w@126.com

文章编号：1003-6199（2014）03-0035-04

摘 要：针对节点高密度部署的炮兵通信网络中优化工作节点集的选取问题，提出一种基于参数可变遗传算法的覆盖控制优化方法。设计了密度检测机制优化初始种群，并设计了即考虑到进化代数对算法影响，又考虑到每代中不同个体适应度对算法作用的自适应交叉概率和变异概率。仿真实验及分析表明，该优化方法快速有效地实现了工作节点数目少、节点集覆盖率高的工作节点集的选取，可有效地降低能耗，延长网络生存时间。

关键词：炮兵通信网络；覆盖；工作节点集；参数可变遗传算法

中图分类号：TP31 文献标识码：A

Optimal Coverage Strategy Based on Alterable Parameter

Genetic Algorithm in Artillery Commutation Networks

Xia Hua-bing， Pan Wei

（Shenyang Artillery Academy，Shenyang，Liaoning 110867，China）

Abstract：An optimal coverage strategy based on adaptive genetic algorithm in wireless sensor networks is proposed for solving the problem of selecting the optimal coverage set of nodes for artillery commutation networks with high density nodes. The mechanism of density detection is designed to optimize the initial population. The adaptive crossover probability and adaptive mutation probability are proposed， which consider the influence of every generation to algorithm and the effect individual fitness in every generation. Simulation and analysis results show that the optimal coverage set of nodes with less nodes and high coverage percentage is achieved by the proposed algorithm. Under the condition， sleeping chance is ensured adequately， which decreases the energy expenditure effectively and prolongs the lifetime of the network.

Key words：artillery commutation networks；coverage；coverage set of nodes；alterable parameter genetic algorithm

1 引 言

未来信息化条件下，炮兵作为陆军的火力突击骨干力量，将担负更加繁重的作战任务，这要求炮兵部队必须具备良好的信息获取及处理能力，以便控制复杂的信息化战场。炮兵群通信系统由通信网和炮兵通信节点组成，主要应用于各级指挥单元和行动单元，完成信息的传输，是联接指挥控制等分系统的纽带[1]。

网络覆盖是炮兵通信网络的基本问题之一，反映了网络对被监测区域或目标对象物理信息的感知能力。网络覆盖问题近年来受到广泛研究[2]，由于通信节点的高密度部署特性，部分节点间的覆盖区域完全或部分交迭，如果所有节点同时工作会造成大量的能量消耗，缩短网络生存时间。因此，如何在实现极大化网络覆盖的同时采用尽量少的节点组成优化工作节点集，和调度各个节点集轮流工作是解决炮兵通信网络能量有限与延长网络生存时间之间矛盾的重要手段[3]。

2 问题建模

2.1 相关假设

目标区域A为二维矩形平面，N个通信网络节点随机部署于其中，网络中含有一个具有较强计算能力的汇聚（sink）节点，用于工作节点集选取的计算，且sink节点可以获得部署于网络内所有节点的位置信息；使用全向天线，节点的通信范围是以节点为圆心，半径为Rc的圆形区域，节点感知半径为Rs且Rc=2Rs，这样保证了网络的连通性，在此基础上的覆盖问题包含了连通问题；位于节点一倍感知半径内的邻居节点为第一类邻居节点，位于一倍感知半径与两倍感知半径之间的节点为第二类邻居节点；若点p与节点si之间的欧式距离d（si， p）满足d（si， p）≤Rs，则点p被si覆盖，且通信网络节点间互相独立。

2.2问题模型

炮兵通信网络优化覆盖问题是一个典型的目标优化问题。网络有效覆盖率、工作节点数目是衡量工作节点集选取的重要指标，综合考虑二者设计适值函数F（x）与优化模型Fopt分别为

F（x）=α×Pcov +β×xsize3Rs×2×ysize3Rsnumworknodes（1）

Fopt=max F（x）（2）

式中，α，β为调节系数，其值取决于网络设计者对网络性能指标的综合要求，Pcov为工作节点集的有效覆盖率，numworknodes为工作节点集的节点数目，xsize为目标区域长度，ysize为目标区域宽度，符号[ ]表示取整，xsize3Rs×2×ysize3Rs为覆盖目标区域所需要的最少节点个数[4]。

为了计算Pcov，将目标区域划分为m×n个网格，以网格中心被覆盖的程度代表网格被覆盖的程度，△s表示一个网格的面积，As表示矩形的面积，则有

Δs=Asm×n=xsize×ysizem×n（3）

网格G（xl， yω）被节点i覆盖的概率为

pRi=Pc（xl，yω，i）=

1，（xl-xi）2+（yω-yi）2≤Rs

0，others（4）

式中，（xl， yω）为网格中心点坐标。

节点间彼此独立，则有

RRi∪Rj=1-pi∪j=

1-pipj （5）

网格被节点集覆盖的概率为

p∪numworknodesi=1R=1-p∩numworknodesi=1i=

1-∏numworknodesi=1Pc（xl，yω，i）（6）

则工作节点集的有效覆盖率Pcov为

Pcov =节点集覆盖的面积总面积=

∑ml=1∑mω=1p∪numworknodesi=1RΔsAs（7）

3 遗传算法求解步骤

3.1 初始种群优化

1）密度检测

节点计算由第一类邻居节点覆盖形成的近似扇形区域对应的圆心角并集θ，若θ=360°，该点处密度较大，节点冗余；若θ=0°，该点处密度过小；若θ∈[0°， 360°]，计算第一类邻居节点中距离该点最近距离α及圆心角并集形成扇形的边与节点感知圆周的交点，在扇形两边上分别取得与对应交点距离为α的关键点，由关键点及交点组成判定点，若判定点能够被第二类邻居节点覆盖，则该节点处密度较大，该点冗余。密度检测如图1所示，图1（a）中节点A为密度检测点，θ为第一类邻居节点覆盖形成的近似扇形区域对应的圆心角并集，G、H为近似扇形的两边与点A感知圆周的交点，G1、H1为关键点，G、H、G1、H1构成判定点；若第一类邻居节点覆盖形成的区域由两部分独立的近似扇形区域构成，即θ=θ1∪θ2，如图1（b）所示，对两组判定点G、H、G1、H1，E、F、E1、F1进行密度检测原理同上。

2）优化过程

密度检测识别出冗余节点并获得所有节点被邻居节点覆盖的圆心角度后，根据密度检测的结果及节点间的位置关系设定节点及邻居节点的工作概率，保证初始化种群的质量，使算法在较少的迭代次数获得较高的适值个体。优化过程如下（c为优化比例，G为初始种群规模）：随机初始化G（1-c）个随机个体，对个体中节点进行密度检测，若节点非冗余，且密度检测获得的圆心角为0，则将节点工作概率置1；若密度检测获得的圆心角非0，找出该节点的第一类邻居节点，并根据圆心角及第一类邻居节点的数目设置节点工作概率；若密度检测得到节点冗余，则设置节点工作概率为0.5；经过工作概率设置后，若节点被选为工作，继续检查该节点第一类邻居节点的工作状态，若第一类邻居节点工作概率非1，相应降低第一类邻居节点的工作概率，完成每个随机个体中所有节点及第一类邻居节点的工作概率设置，即完成个体优化；循环直至优化个体比例达到要求。

3.2 遗传操作

遗传操作包括选择、交叉、变异三种操作算子，本文采用标准遗传操作，选择操作是排序选择+最佳个体保存法，交叉操作是依据交叉概率的单点交叉，变异操作是依据变异概率的单基因突变。选择操作是遗传算法的基础，变异操作是遗传算法的核心，交叉操作是遗传算法的补充[5]。

3.3 交叉概率的自适应确定

交叉算子在遗传操作中起核心作用，主要用来产生新个体，实现算法的全局搜索能力。从群体整体进化过程来看，交叉概率应该能随进化过程逐渐变小，到最后趋于某一稳定值，以避免对算法后期的稳定性造成冲击而导致算法不能收敛，或收敛过程加长；而从产生新个体的角度来看，群体中的所有个体在交叉操作上应该具有同等地位，相同概率，从而使GA在搜索空间具有各个方向的匀性[6]。因此，本文设计了与进化代数相关的交叉概率：

Pc=11+eαG+β（8）

其中，G为进化代数，α、β为定常系数，α代表交叉概率的变化曲率，β代表交叉概率的收敛极限。

3.4 变异概率的自适应确定

变异算子在遗传操作中起辅助作用，主要用来维持群体多样性，防止出现未成熟收敛。在算法早期，群体中个体多样性丰富，此时的变异概率应该小些，以提高算法的运行速度；而随着进化的进行，个体越来越向适应度高的个体靠近，致使个体越来越单一，此时的变异概率就应该大些，以维持群体的多样性。同样的原因，同一代群体中个体的变异概率应该随个体的优劣而变化，即加大优质个体变异概率。为此设计了如下的与遗传进化代数和个体适应度相关的自适应变异概率：

Pm=k11+e-αG-ffmax-f>

k2f≤ （9）

其中，f为当前个体适应度值，fmax为当前群体中最大个体适应度值，为当前群体平均适应度值，G为进化代数，α、k1、k2为定常系数。α代表变异概率的变化速度；k1与具体问题有关，是为保证遗传算法不退化为随机搜索，pm所能取到的最大值；k2为一个比较小的变异概率，一般取0.001。

3.5 实施步骤

初始化覆盖控制优化中各参数，包括节点数目N，种群优化比例c，遗传算法的种群规模G，工作节点集的有效覆盖率阈值Pcovm。

步骤1 采用二进制N位编码方式对初始种群进行编码，0表示节点不工作，1表示节点工作，每个工作节点集即种群中每个个体用N位编码表示；根据密度检测进行初始种群的优化；

步骤2 根据式（1）计算种群内个体适值、判断终止条件，若满足，则转入步骤5，否则转入步骤3；

步骤3 遗传操作；

步骤4 构成下一代种群个体，转入步骤2；

步骤5 获得优化工作节点集，覆盖控制结束。

4 仿真实验

采用MATLAB仿真平台，对在GA、采用密度检测机制优化种群的GA（GA+密度检测）、APGA三种算法下工作节点集选取的性能进行验证，仿真实验中各参数采用通信网络研究的通用设置。

APGA比GA算法的复杂度高，但APGA经过合理设计后优化性能优于GA算法且优化速度较快。进行50次独立的随机拓扑实验，得到APGA与GA算法的平均最优适值、平均计算时间和平均迭代次数关系，如表1所示。

表1 50次独立优化实验的平均性能

可见，APGA的优化效果优于GA算法，且优化速度较快。这主要是由于GA算法具有容易陷入局部最优的特点，参数可变遗传操作可以跳出局部极小值陷阱和避免循环搜索，从而使得APGA算法快速的获得了更优的工作节点集。

图2给出优化工作节点集适值的性能，可见，在遗传迭代稳定后，APGA算法的适值总体性能明显优于其它两种算法，大约可以高出GA算法50%，高出GA+密度检测算法28%。算法的全局寻优能力更强，且优化速度较快，有效地减少了算法迭代次数，使得算法以较少的迭代次数获得了更优的工作节点集，有益于降低能耗，延长网络生存时间。

图3给出优化工作节点集中工作节点数目的性能，可见，在满足有效覆盖率98%阈值条件下，APGA算法下选取的工作节点集中工作节点数目最少，约为GA的50%，约为GA+密度检测的75%。APGA算法获得了最少的工作节点，有利于充分休眠冗余节点，从而降低能耗，延长网络生存时间。

5 结 语

本文以网络覆盖率、工作节点数目构成优化目标，研究了节点高密度部署的炮兵通信网络中优化工作节点集选取的问题，提出了一种基于参数可变遗传算法的覆盖控制优化方法。理论分析和实验数据表明，该方法通过密度检测机制优化了种群质量，提高了优化速度，通过自适应遗传操作增强了全局寻优能力，从而快速有效地实现了工作节点数目少、节点集覆盖率高的工作节点集的优化选取，在较高的覆盖质量条件下休眠了更多的冗余节点，有效地降低了能耗，延长了网络生存时间。

参考文献

[1] 刘树海. 军队指挥自动化系统[M]. 北京：解放军出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

[5] 潘伟. 基于参数可变遗传算法的多普勒雷达目标识别方法 [J]. 计算技术与自动化， 2011， 30（2）： 105- 108.

步骤1 采用二进制N位编码方式对初始种群进行编码，0表示节点不工作，1表示节点工作，每个工作节点集即种群中每个个体用N位编码表示；根据密度检测进行初始种群的优化；

步骤2 根据式（1）计算种群内个体适值、判断终止条件，若满足，则转入步骤5，否则转入步骤3；

步骤3 遗传操作；

步骤4 构成下一代种群个体，转入步骤2；

步骤5 获得优化工作节点集，覆盖控制结束。

4 仿真实验

采用MATLAB仿真平台，对在GA、采用密度检测机制优化种群的GA（GA+密度检测）、APGA三种算法下工作节点集选取的性能进行验证，仿真实验中各参数采用通信网络研究的通用设置。

APGA比GA算法的复杂度高，但APGA经过合理设计后优化性能优于GA算法且优化速度较快。进行50次独立的随机拓扑实验，得到APGA与GA算法的平均最优适值、平均计算时间和平均迭代次数关系，如表1所示。

表1 50次独立优化实验的平均性能

可见，APGA的优化效果优于GA算法，且优化速度较快。这主要是由于GA算法具有容易陷入局部最优的特点，参数可变遗传操作可以跳出局部极小值陷阱和避免循环搜索，从而使得APGA算法快速的获得了更优的工作节点集。

图2给出优化工作节点集适值的性能，可见，在遗传迭代稳定后，APGA算法的适值总体性能明显优于其它两种算法，大约可以高出GA算法50%，高出GA+密度检测算法28%。算法的全局寻优能力更强，且优化速度较快，有效地减少了算法迭代次数，使得算法以较少的迭代次数获得了更优的工作节点集，有益于降低能耗，延长网络生存时间。

图3给出优化工作节点集中工作节点数目的性能，可见，在满足有效覆盖率98%阈值条件下，APGA算法下选取的工作节点集中工作节点数目最少，约为GA的50%，约为GA+密度检测的75%。APGA算法获得了最少的工作节点，有利于充分休眠冗余节点，从而降低能耗，延长网络生存时间。

5 结 语

本文以网络覆盖率、工作节点数目构成优化目标，研究了节点高密度部署的炮兵通信网络中优化工作节点集选取的问题，提出了一种基于参数可变遗传算法的覆盖控制优化方法。理论分析和实验数据表明，该方法通过密度检测机制优化了种群质量，提高了优化速度，通过自适应遗传操作增强了全局寻优能力，从而快速有效地实现了工作节点数目少、节点集覆盖率高的工作节点集的优化选取，在较高的覆盖质量条件下休眠了更多的冗余节点，有效地降低了能耗，延长了网络生存时间。

参考文献

[1] 刘树海. 军队指挥自动化系统[M]. 北京：解放军出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

[5] 潘伟. 基于参数可变遗传算法的多普勒雷达目标识别方法 [J]. 计算技术与自动化， 2011， 30（2）： 105- 108.

步骤1 采用二进制N位编码方式对初始种群进行编码，0表示节点不工作，1表示节点工作，每个工作节点集即种群中每个个体用N位编码表示；根据密度检测进行初始种群的优化；

步骤2 根据式（1）计算种群内个体适值、判断终止条件，若满足，则转入步骤5，否则转入步骤3；

步骤3 遗传操作；

步骤4 构成下一代种群个体，转入步骤2；

步骤5 获得优化工作节点集，覆盖控制结束。

4 仿真实验

采用MATLAB仿真平台，对在GA、采用密度检测机制优化种群的GA（GA+密度检测）、APGA三种算法下工作节点集选取的性能进行验证，仿真实验中各参数采用通信网络研究的通用设置。

APGA比GA算法的复杂度高，但APGA经过合理设计后优化性能优于GA算法且优化速度较快。进行50次独立的随机拓扑实验，得到APGA与GA算法的平均最优适值、平均计算时间和平均迭代次数关系，如表1所示。

表1 50次独立优化实验的平均性能

可见，APGA的优化效果优于GA算法，且优化速度较快。这主要是由于GA算法具有容易陷入局部最优的特点，参数可变遗传操作可以跳出局部极小值陷阱和避免循环搜索，从而使得APGA算法快速的获得了更优的工作节点集。

图2给出优化工作节点集适值的性能，可见，在遗传迭代稳定后，APGA算法的适值总体性能明显优于其它两种算法，大约可以高出GA算法50%，高出GA+密度检测算法28%。算法的全局寻优能力更强，且优化速度较快，有效地减少了算法迭代次数，使得算法以较少的迭代次数获得了更优的工作节点集，有益于降低能耗，延长网络生存时间。

图3给出优化工作节点集中工作节点数目的性能，可见，在满足有效覆盖率98%阈值条件下，APGA算法下选取的工作节点集中工作节点数目最少，约为GA的50%，约为GA+密度检测的75%。APGA算法获得了最少的工作节点，有利于充分休眠冗余节点，从而降低能耗，延长网络生存时间。

5 结 语

本文以网络覆盖率、工作节点数目构成优化目标，研究了节点高密度部署的炮兵通信网络中优化工作节点集选取的问题，提出了一种基于参数可变遗传算法的覆盖控制优化方法。理论分析和实验数据表明，该方法通过密度检测机制优化了种群质量，提高了优化速度，通过自适应遗传操作增强了全局寻优能力，从而快速有效地实现了工作节点数目少、节点集覆盖率高的工作节点集的优化选取，在较高的覆盖质量条件下休眠了更多的冗余节点，有效地降低了能耗，延长了网络生存时间。

参考文献

[1] 刘树海. 军队指挥自动化系统[M]. 北京：解放军出版社， 2002.

[2] WANG X， WANG S. An improved particle filter for target tracking in sensor system [J].Sensors，2007，7（1）：144-156.

[3] WANG X， MA J J， WANG S. Prediction-based dynamic power optimization in wireless sensor networks [J].Sensors，2007，7 （3）：251-266.

[4] JIA J，CHEN J，CHANG G R. Efficient cover set selection in wireless sensor networks[J].Acta Automatica Sinica，2008，34（9）：1157-1162.

篇6：基于遗传算法计算弹道节省参数最优节点

关键词：遗传算法,智能计算,最优路径的问题

0 引言

车辆路径诱导问题是智能交通系统ITS研究的一个重要方向, 它是基于电子、计算机、网络和通信等现代先进技术, 利用全球定位技术和电子交通地图使得车辆能够自动掌控自己的位置和道路交通情况, 并通过获得的实时交通信息, 给车辆显示出最优路径。此系统可给车辆的出行提供参考, 从而减少交通拥堵, 诱导车辆在路径上的合理分配。

针对用传统的搜索算法解决动态路径诱导问题时产生的困难和在解决问题方面性能的低下, 本文推出了智能的遗传搜索算法, 并通过合适的改进, 找到一种适合的处理路径诱导问题的方法。

1 遗传算法简介

遗传算法 (Genetic Algorithm-GA) , 是模拟自然界生物界系统优胜劣汰的一种智能搜索算法, 它是由美国的Michi gan大学的J.Holland教授于1975年首先提出的, 算法操作的主要的特点是群体并行搜索和群体之间的个体的信息交换, 它适用于处理传统搜索算法难以解决的复杂和非线性问题, 可广泛应用于组合优化、机器学习、规划设计和人工智能等科学领域, 是21世纪在智能计算领域中的关键技术之一。

2 遗传算法解决路径诱导系统问题

2.1 遗传算法原理

遗传算法的原理[1]:对于一个求解问题, 首先我们确定初始化种群, 这是我们求解问题的一个解空间, 我们称这一代种群为第一代。在第一代种群中, 由很多的个体组成, 每一个个体都是我们解决问题的一个可行解, 它是由一组字符串组成的, 我们也称之为染色体。组成染色体的每个字符, 我们称之为基因, 我们主要对基因进行操作来实现并行寻优。首先我们根据这个种群的环境确定每个个体的适应度, 然后以适应度为基础在种群中选择适应度较高的个体, 通过基因的交叉和变异来产生下一代个体, 从而产生下一代种群。通过一代又一代的繁衍, 适应度好的个体会生存下去, 而适应度低的个体会死去, 从而使种群的适应度越来越好, 同时也会收敛于问题的最优解。

遗传算法的工作原理图:

2.2 路径诱导问题的描述

对于一个给定的路径图, 如下图:

问题相应的数学描述是:在给定的节点以及给定的路径连接矩阵中, 找到一条最优路径, 使得路径的距离最短。

2.3 路径诱导问题的解决方案

编码及初始种群的表[2]:在解决这个具体的问题中, 我们节点编码采用普通的编码方法, 如图从左到右依次递增编码, 且无重复的码元。在路径表示方面我们则采用二进制编码, 因为二进制编码方式容易进行染色体的变异和交叉操作, 为此我们必须定义一个稀疏矩阵, 这个矩阵用于对应节点之间的连接关系。

选择初始种群:初始种群的选择对于遗传算法解决问题具有至关重要的作用, 对于一个一般的搜索算法, 我们需要遍历所有的路径, 首先将所有可能的路径列出来, 其次进行路径的求和运算, 然后进行对比找到最短的路径。而遗传算法的求解思路是, 找到几个有代表性的路径如最长的路径, 最短的路径等等, 但是一个原则, 就是路经集合应该包含所有的节点信息。

适应度函数:针对这个问题, 我们把适应度函数记为f。我们计算两个有连接节点间的距离为, 则每一条可能路径的距离为:。根据一些适应度函数的定义法则我们定义。

选择算子:选择算子对染色体进行第一次的优胜劣汰, 一般使用轮赌法找出种群中染色体适应度最大的和最小的, 然后用适应度最大的染色体代替最小的染色体进行下面步骤中的交叉运算, 从而保持优势群体的遗传基因。

交叉算子:在选择算子产生的两个父代染色体中, 我们采用基于顺序的交叉方式, 如下图，父代染色体：, 我们选择三号位为交叉点, 对于三号位后面的部分, 保留相同的基因, 交换不同的基因, 经过交叉操作后, 产生子代染色体:, 然后我们计算子代染色体和父代染色体的适应度, 保存适应度高的染色体, 淘汰适应度低的染色体使种群逐渐趋于优化。

终止条件:根据现在的经验来确定, 从严格的数学角度确定终止条件比较困难, 所以我们选取较大的迭代次数来作为算法的终止条件。但是为了便于观察, 我们这里通过比较适应度函数的值来终止搜索, 当种群达到最优解时, 适应度函数值会相对的趋于稳定。

3 关键算法设计

在本文中遗传算法的交叉算子的MATLAB程序设计为:

我们采用MATLAB 7.0来进行模拟对问题的求解, 可以得到以下结果:

4 结语

这篇文章, 我们首先介绍了路径诱导的一些知识, 从而引入了现在在动态路径引导时的遗传算法, 此算法在相比传统的算法时具有并行搜索的特点, 体现出很大的优越性, 从而开拓了我们在应对这种问题时的思路。从我们实验的结果来看, 遗传算法在解决这种问题时的有效性, 实现了我们最优路径的搜索目标。

在今后的工作中我们将加入更强的限制条件, 比如时间的动态因素, 从而进一步地研究动态路径的诱导问题。

参考文献

[1]李茂军, 朱陶业等.单亲遗传算法与传统遗传算法的比较研究[J].系统工程, 2001, 1 (1) :62-64.

[2]龙军, 袁鑫攀, 程天蝉.基于时间与费用双优化的虚拟企业调度算法[J].上海交通大学学报, 2011, 45 (12) :1813-1817.

[3]苑士立, 撒立.基本遗传算法设计及改进[J].软件时空, 2011, 27 (12) :133-135.

[4]Goldberg, DE.Genetic Algorithms in Searching, Optimiza-tion&Machine learning.Addison-Wesley Publishing, 1989.

[5]D.Goldberg, “Genetic Algorithm in Search, Optimization, and Machine Learning”, Addison-Wesley, Reading, MA, 1989.

[6]Davis, L.Handbook of Genetic Algorithms, Van NostrandRein-hold, 1991.

[7]蒋伟进, 彭召意, 许宇胜.基于混合遗传算法的多目标问题规划[J].微电子于计算机, 2004, 21 (7) :133-134.

[8]玄光男, 程润伟.遗传算法与工程优化[M].北京:清华大学出版社2004:252-260.

[9]韩瑞锋.遗传算法原理与应用实例[M].北京:兵器工业出版社.2010:328-341.

篇7：基于遗传算法计算弹道节省参数最优节点

人类在享受互联互通和信息共享带来的便捷与效益的同时，网络技术发展过程中对安全性的忽视，导致网络环境中存在各式各样的安全隐患，严重威胁着网络运营及合法用户的信息安全。因此，寻找并弥补威胁网络关键资源的脆弱性是提高网络安全性的一种有效方法。文献[1]基于逻辑推理的方法，首先将最优弥补求解问题转化为布尔表达式；然后求解该布尔表达式的析取范式，从而得到所有的弥补措施；最后通过分析比较得到最优弥补建议。该方法在最坏情况下具有不可避免的指数时间复杂度，无法应用于网络规模较大的真实目标网络系统。文献[2]提出采用归纳有序二元决策图（ROBDD）的方法求解最优弥补。该方法可以有效地获取攻击图的最优弥补，但在该方法中，未对脆弱性进行度量标准的说明，因此在实际应用上具有一定的局限性。

由于求解最优弥补问题是NP完全性问题，对于NP完全性问题，采用启发式搜索方法可以更快地获得结果。并行遗传算法[3,4,5,6]具有以下优势：覆盖面大，利于全局择优；对问题的依赖性较小，求解的鲁棒性较好；具有并行计算的特点，可以用大规模的并行计算来提高计算速度；特别适用于复杂大系统问题的优化求解，但其存在收敛速度慢、局部搜索能力差等不足之处。并行遗传算法可以克服经典遗传算法的不足，提高遗传算法求解的速度和质量。基于此，本文将攻击图与并行遗传算法相结合，提出了一种基于并行遗传算法的网络最优弥补模型（Optimal Network Hardening Model Based on Paralle Genetic Algorithm,PGA-ONHM）。

1 最优弥补问题的转化

虽然并行遗传算法可以克服经典遗传算法的不足，特别适用于复杂大系统问题的优化求解[7,8,9]，但在具体的实现过程中，其适应度函数不能有约束条件，适应度函数的值需大于0，其最终得到的最优个体适应度函数值为最大值。求解最优弥补是有约束条件的，即需要满足约束条件g(x)=0，然后在满足此条件的弥补策略中寻找最优弥补。

为了能够将攻击图与并行遗传算法相结合，从而找到适用于求解大规模复杂目标网络系统最优弥补的模型，本文首先通过建立相应的数学模型，将最优弥补问题转化成一个带有惩罚的非约束优化问题，然后利用并行遗传算法得到其最优弥补的近似解。

令c1,c2,⋯,cn为目标网络系统的初始属性点，cost(ci)(i=0,1,2,⋯,n)为弥补初始属性节点ci需付出的成本代价，通过总结分析，并进行大量的模拟实验，建立的数学模型为：

通过此数学模型，可以将带有约束条件g(x)的最优弥补问题转化成能够应用并行遗传算法的非约束优化问题。r为惩罚因子，目的是设法对违背约束条件的个体给予惩罚，即当弥补策略不能保证目标网络系统正常、安全运行时，给予该策略一定的惩罚，使该策略所消耗的成本代价适应度放大，这样更易于选择最优弥补。

2 PGA-ONHM模型的设计与实现

2.1 并行遗传算法设计

目前，并行遗传算法的模型主要有三种：主从式、粗粒度、细粒度。其中，粗粒度模型首先将初始群体按照处理器数量分割成若干个子群体；然后将子群体分配给不同的处理器相互独立地并行执行，每经过一定的进化代，各子群体间会交换若干个体以引入其他子群体的优秀基因，防止未成熟收敛的发生。由于该模型通信开销少，而且适应性强、应用广，因此本文采用并行遗传算法的粗粒度模型。

(1）初始化总群体及子群体参数

总群体大小的选取应适中，过小则不易全局最优解，反之则运算量过大，收敛速度减慢。通常取编码长度的2倍。若总群体的大小为N，依据处理器数量将总群体均匀划分为U个子群体，则各子群体的大小为M=N U,M>1。

(2）子群体间的通信方式

由于从进程都是各自独立地运行遗传算法，每个进程到达符合迁移条件所需要的时间是不同的，因此，为了消除等待同步耽搁的时间，本文采用子群体间异步通信的方式。当主进程收到从进程提交的个体后，将染色体存放在缓冲区，并将缓冲区中上次收到的染色体发送给它。这样不仅降低了迁移算子的复杂度，同时省去了等待进程同步的时间，提高了运算速度。

(3）子群体的迁移策略

迁移是并行遗传算法引入的一个新算子，它是指进化过程中子群体间交换个体的过程，迁移策略主要控制的参数如下：

(1)迁移规模：每次迁移个体的数量。

(2)迁移率：个体迁移的时间间隔，即进化几代迁移一次。

(3)迁移策略：在确定迁移规模和迁移率后，就要确定哪些个体进行迁移。对于迁移个体的选择，本文采用子群体中的最优个体向外移民的策略。

(4）终止条件

程序终止的方式有两种：一是根据目标网络系统的规模，设定最大迭代次数，当迭代次数达到最大迭代次数时，则程序结束；二是在进化若干代后，若新一代中存在某个染色体的选择概率超过80%（此概率由用户设定），或者新一代中所有的染色体都相同，则程序结束。

2.2 子群体参数设计

(1）编码

编码的基本要求是为染色体的基因型（代码串）和表现型（参数值）建立对应关系，从而决定初始化种群。根据实际的应用需求，本文采用二进制代码进行编码，则对应关系就是二进制与十进制的转换关系。

(2）适应度函数

适应度函数是经典遗传算法中进行选择、交叉和变异操作的依据，该函数的选取是一个技巧性很高，但理论上的研究又很不充分的复杂问题。通过大量的模拟实验和分析，本文采用的适应度函数ti为：

其中r采用动态惩罚函数法。该方法在遗传算法的进化初期，为了保证算法能在全局范围内进行搜索，选取较小的惩罚因子，但在遗传算法的后期，为了增强局部搜索能力，将选取较大的惩罚因子。

(3）遗传算子

选择为经典遗传算法基本的遗传算子之一，常用的选择方法有期望值法、适应度概率法以及最佳个体保存法。文献[5]对以上三种方法的遗传算法性能进行对比，实验表明，采用期望值法的经典遗传算法，其离线性能与在线性能均高于采用另外两种方法。采用适应度概率法时可能会产生随机误差，这种误差在群体数较大时更易发生。因此，本文采用期望值法，且计算选择概率的公式为Pi=ti∑ti，其中：∑ti表示适应度值的总和；ti表示种群中第i个染色体的适应度值。

交叉为经典遗传算法基本的遗传算子之一，即将两个染色体的基因进行互换产生新的后代。与选择操作相比较，该操作能使基因排序变化更加灵活，实现真正意义上的人为重组，适用于大范围操作。在具体操作中，交叉分两个步骤：第一步是选择两两匹配的对象，第二步是决定交换点及交换规则。常用的交叉方式有单点交叉、双点交叉、按序交叉和位置交叉等，根据实际应用情况，本文采用按序交叉。

变异为经典遗传算法基本的遗传算子之一。由于本文采用二进制代码进行编码，即就是将基因值取反。

2.3 PGA-ONHM模型的实现

利用PGA-ONHM模型求解目标网络系统的最优弥补时，首先由主进程设定总群体大小、初始化子群体、设定子群体的参数（交叉、选择、变异等），把生成的子群体分配给从进程；然后子群体在从进程中进行独立进化，当达到预定代数时，向主进程发出迁移申请，主进程执行迁移策略，当从进程满足终止条件时，向主进程输出最优解；最后主进程从所有从进程输出的最优解中选择一个最优解。算法主进程流程图如图1所示。

各从进程独立地运行遗传算法进行进化，首先根据子群体参数设计对个体进行染色体二进制编码，并利用式（2）和式（3）计算每个个体的适应度函数，得到每个个体的选择概率，然后对父本进行选择、交叉、变异操作，产生下一代个体。当进化的代数满足迁移率时，向主程序返回最优解。从进程算法流程如图2所示。

2.4 算法复杂度分析

设目标网络系统中初始属性节点数量为C，迭代次数上限为D。

在主进程中，首先根据初始属性节点数量，从所有弥补策略中平均选取N个个体组成总群体，然后将总群体划分为U个子群体，一般来说N=2C，所以时间复杂度为：

在从进程中，子群体的大小为M=N U，各个子群体独立运行遗传算法，其时间复杂度主要从以下几部分分析：

(1）二进制编码。对每个个体进行二进制编码，时间复杂度为O(M)。

(2）适应度函数计算。对每个个体进行适应度函数计算，因为式（2）的时间复杂度为O(C)，所以适应度函数计算的时间复杂度为O(MC)。

(3）选择。首先计算每个个体的选择概率，然后将选择概率小的个体替换为选择概率大的个体，时间复杂度为O(M)。

(4）交叉。随机选择父本中的两个个体进行交叉操作，从而产生新的个体，时间复杂度为O(M2)。

(5）变异。根据变异概率，对个体执行变异操作，时间复杂度为O(M)。

(6）迁移。根据迁移率，向主进程提交当前子种群中选择概率大的个体，时间复杂度为O(M)。

当每一代进化未满足终止条件时，算法进行迭代。因此，遗传算法的时间复杂度为O(MC)⋅O(D)=O(2DC2/U)。

3 实验结果与分析

为了验证PGA-ONHM模型的可行性、有效性和可扩展性，本文从不同分析角度做了两组实验，并对实验结果进行了分析。实验环境如下：服务器PowerEDGE R710，操作系统RetHAT V5.4，内存32 GB,CPU 2.26 GHz。

3.1 算法性能验证实验

由算法性能分析可知，该算法性能与目标网络系统中初始属性节点数量C,迭代次数D,子群体U等参数有关。为了验证不同网络环境下这些参数对算法性能的影响，在得到最优解的前提下，分别设计了如下两组实验。

第一组实验验证初始属性节点数量不同时，单次迭代的平均计算时间如图3所示。由图3可知，单次迭代的平均计算时间随着初始属性节点数量C的增加呈多项式增加趋势。

第二组实验验证子群体数量（即处理器数量）对算法性能的影响。令初始属性节点数量为500，当子群体数量不同时，单次迭代的平均时间如图4所示。由图4可知，单次迭代的平均计算时间随着U的增加呈减小趋势。

由上述两组实验结果可知，在PGA-ONHM模型中，算法CPU消耗的时间随着初始属性节点数量C的增加呈多项式增加趋势，随着子群体数量U的增加呈减小趋势，实验结果与算法性能分析结果一致。

3.2 算法对比实验

(1）经典遗传算法和并行遗传算法对比实验，实验结果如表1所示。表1列出了在初始属性节点数量不同的情况下，求解最优弥补时两种算法的平均迭代次数和单次迭代的平均计算时间。

从实验结果可以看出：一方面，针对同一目标网络环境，无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越，其主要原因是在并行遗传算法的具体实现过程中，首先将总群体分成若干子群体，然后将子群体分配到各自的处理机上，独立地进行遗传算法的进化操作，实现了从全局角度开发群体进化的并行性，从而提高了计算效率；另一方面，并行遗传算法具有良好的可扩展性，当初始属性节点数量达到2 000时，单次迭代的平均计算时间也不过7 ms。

(2）加速比实验。目前公认的评价并行遗传算法性能的指标是加速比，即并行遗传算法与经典遗传算法完成等量工作所耗时间的比例，它标志着一个并行遗传算法的好坏。本文在相同的硬件环境下，对同一目标网络环境通过改变处理器数量，进行了加速比实验，实验结果如表2所示。加速比和处理器数量的关系如图5所示。由图5可知，加速比与处理器几乎呈线性关系，因此，本文所提并行遗传算法可以得到较好的加速比，是行之有效的并行手段。

4 结论

PGA-ONHM模型通过建立数学模型将攻击图与并行遗传算法相结合，得到最优弥补的近似解。为了验证该模型的可行性、有效性和可扩展性，本文从不同的分析角度做了两组实验，实验结果表明：CPU消耗时间随着初始属性节点数量的增加呈多项式增加，随着子群体数量的增加呈减小趋势；无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越；加速比与处理器呈线性关系；能够克服局部最优解的问题，可以适用于大规模复杂的网络系统。

参考文献

[1]JHA S,SHEYNER O,WING J M.Two formal analyses of attack graphs[C]//Proceedings of 15th IEEE Conference on Computer Security Foundations Workshop.[S.l.]:IEEE,2002:49-63.

[2]NOEL S,JAJODIA S,O′BERRY B,et al.Efficient minimumcost network hardening via exploit dependency graphs[C]//Proceedings of 19th Annual Conference on Computer Security Applications.[S.l.]:IEEE,2003:86-95.

[3]WANG L Y,NOEL S,JAJODIA S.Minimum-cost network hardening using attack graphs[J].Computer communications,2006,29(18):3812-3824.

[4]HOMER J.From attack graphs to automated configuration management:an iterative approach[R].Kansas:Kansas State University Technical Report,2008.

[5]SI J Q,ZHANG B,MAN D P,et al.Approach to making strategies for network security enhancement based on attack graphs[J].Journal on communications,2009,30(2):123-128.

[6]CHEN F,WANG L Y,SU J S.An efficient approach to minimum-cost network hardening using attack graphs[C]//Proceedings of 2008 the 4th International Conference on Information Assurance and Security.Naples:IEEE,2008:209-212.

[7]CHEN F,ZHANG Y,SU J S,et al.Two formal analyses of attack graphs[J].Journal of software,2010,21(4):838-848.

[8]CHEN F.A hierarchical network security risk evaluation approach based on multi-goal attack graph[D].Changsha:National University of Defense Technology,2008.