混合自适应遗传算法

2024-08-12

混合自适应遗传算法（精选八篇）

混合自适应遗传算法篇1

工作流挖掘 (Workflow Mining ) 又称过程挖掘 (Pro-cessing Mining) [1], 旨在从工作流日志数据中提取执行轨迹信息, 并分析这些信息从而自动建立工作流模型, 其主要目的是实现工作流的模型优化、智能管理和柔性管理。现有的工作流挖掘算法主要采用局部策略, 这些方法在综合处理各种复杂结构时存在不足且抗噪能力差, 而遗传算法能够从全局的角度综合解决各种复杂结构, 抗噪能力较优, 但其往往需消耗更多的时间获得解, 而且没有全面考虑影响任务依赖关系的度量及适应度函数定义的各种因素。针对遗传算法存在的问题, 在对任务依赖关系的度量、适应度函数以及遗传算子进行改进后, 本文提出了一种基于混合遗传方法的工作流挖掘算法, 仿真结果表明, 基于混合遗传方法的工作流挖掘得到的解更优且所消耗的时间更少。

1 基于混合自适应遗传方法的工作流挖掘算法

1.1 算法步骤

本文以遗传算法为主体, 结合模拟退火算法[2], 构建因果关系矩阵映射流程实例作为遗传个体[3], 每个因果矩阵对应一个工作流模型。在遗传算法的选择操作阶段, 采用锦标赛策略与精英保留策略相结合, 在交叉变异阶段运用混合自适应方法并将模拟退火思想引入其中, 有效地提高了解的质量。算法流程如图1所示。

本文算法执行过程如下:

(1) 初始化:1 读取事件日志, 按照编码机制和启发式规则创建初始化群体;2 确定退火算法中的初始温度temp0中的K和终止温度tempm, 降温系数θ:温度tempn=θtempn-1, 逐步降低温度最大降温次数d 。

(2) 对种群进行选择操作SelectionOperator () 、交叉操作CrossoveOperator () ;按Metropolis准则接收交叉操作产生的新个体, 进行变异操作MutateOperator () ;按Metropolis准则接收变异操作产生的新个体。

(3) 评价新产生的各个子种群中的个体适应度。

(4) 输出结果。

1.2 工作流模型编码———构造因果矩阵

描述一个工作流程应该包含如下3方面信息:工作流包含的任务、任务的上下文、如何组织任务之间的因果关系。遗传算法中使用因果矩阵来表示任务之间的因果关系, 本算法借鉴遗传算法因果矩阵[4]。

定理1:构造因果矩阵———遗传个体[5]。

初始化的过程对所有工作流日志进行遍历, 以构造遗传个体GI = (T, C, I, O) 。设T为一个任务集合, L:T*→IN为一事件日志, t∈ T , 即T = {t1, t2, …, tn}, n为日志中的任务数;CM为任务关系集合。

其中起点为ti, 终点为tj;O (ti) 表示任务ti的输出条件映射函数, I (ti) 表示任务ti的输入条件映射函数, 遗传个体定义为GI = (T, C, I, O) , 一个工作流模型对应于一个遗传个体, GI用任务因果关系矩阵来表示。结合文献[5]中表1的日志, 根据以上定义可得:T ={a, b, c, d, e, f, g, h};

确定CM后, 形成输出和输入条件函数O (t) 和I (t) 。根据表1所示的事件日志, 得到过程模型的因果关系矩阵。

注:根据文献[5]表1日志产生

1.3 初温设置

为了避免传统遗传算法“过早收敛”问题, 本文在遗传操作过程中引入模拟退火思想[8], 即采用Boltzmann生存机制[6], 避开过早收敛且使种群向前进化。设新产生个体的适应度值为f, 其中fw、favg分别为个体的最低适应度、平均适应度和最高适应度。当f>f′时, 在种群中随机选择一个适应度值小于f′的个体来取代;否则就按概率ps取代适应度值小于f′的个体, 其中temp为温度。选择temp0=K (fmax-fw) 为初始温度, 退火函数为tempn=θtempn-1, 其中K为充分大的数, θ∈ (0, 1) 。

1.4 遗传操作

1.4.1 选择操作

本文采用精英保持策略与锦标赛选择相结合的方法。锦标赛选择方法:首先随机抽取当前种群中的两个个体进行对比, 二者中适应度值较小的个体以1-ε的概率作为父本, 适应度值大的以概率ε作为父本[5], 经过交叉变异操作后, 当前种群中的精英个体极有可能会遭受破坏, 降低了种群的平均适应度, 影响了算法的效率。所以算法为保留住当前种群中具有最好适应度的个体, 采用精英保持策略, 避免这些最优个体参与交叉和变异操作, 直接进入新的种群。

1.4.2 交叉概率Pｃ与变异概率Pｍ

传统的遗传算法在交叉变异阶段, 交叉概率和变异概率是固定不变的, 这样就有可能导致种群进化过程停滞不前。对此Sriniva[7]等提出了自适应遗传算法, 该算法中的交叉和变异概率是按照遗传个体相似度的高低自适应地匹配, 但在种群进化的初始阶段, 该方法会影响进化效率。在文献[7]中指出交叉概率和变异概率应当自适应于各个进化阶段, 因此本文将进化阶段两个因素和相似度相结合, 并对交叉概率和变异概率进行自适应调整。改进后的混合自适应调整公式如下:

其中:pc、Pm分别表示交叉概率和变异概率;f′ 、favg、fmax分别表示要交叉的两个遗传个体中较大的适应度值、最大的适应度值和平均适应度值;f表示要变异个体的适应度值;k1、k2、k3、k4均取常数且都∈ (0, 1) ;pshift为进程因子, 随着进化阶段由0趋向于1;Sc是收敛性因子, 其值决定于pshift。

通过引入两个因子pshift和Sc, 混合自适应调节交叉和变异的概率, 保证算法的全局收敛性和种群的多样性, 并且提高收敛速度。

1.4.3 交叉操作

两个因果关系矩阵GI = (T, CM , I, O) 按照交叉概率pc进行交叉操作时, 二者的T是相同且确定的, 因此T不参与该操作, 采用的交叉方法为:随机选取一任务t为交叉点, 同时在输入集合I和输出集合O中随机选取一子集作为交换点, 接着从交换点开始的子集到末尾的子集依次进行交换。子集交换的主要策略:在一个I/O中删除两个子集的交集元素;子集合并到I/O中;引入新的子集。

交叉结束后可能出现的情况:某一个任务没有出现在另一个任务所对应的I/O中, 但CM中相应的位置却依然为1;所有交叉操作后应当检查所得到I/O的合理性 (因果关系矩阵的一致性) , 若存在, 将对CM和因果关系矩阵进行重新调整。

1.4.4 变异操作

种群中遗传个体的多样性主要是依靠变异操作来维持的, 以此避免算法陷入局部最优解。在传统遗传算法的变异操作过程中, 取任务作为主要操作对象, 根据变异概率对应的I/O执行相应的操作。本算法采用的策略有:1随机选择一个子集, 并为该子集增加一个任务t, t∈ T;2随机选取一个子集, 并从该子集中删除一个任务;3利用启发规则产生新的个体。

2 衡量标准

评价最终挖掘得到的工作流模型优劣, 应该衡量模型是否既完整又精确。完整性是指工作流模型匹配日志的程度, 精确性则是用于刻画工作流的细致程度。最终衡量标准为完整性适应度和精确性适应度的加权结合[5]。

衡量标准:设L:T*→IN为一工作流日志, 其中T为一个任务集合, GI是一个因果关系矩阵, SGI是所有因果关系矩阵的集合SGI ={GI }, 那么定义F :L×GI×SGI → (- ∞, 1]为个体的适应度函数:

F (L, GI, SGI) =PFcomplete (L, GI) -ψ*PFprecise (L, GI, SGI)

其中PFcomplete (L, GI) 为完整性适应度, PFprecise (L, GI, SGI) 为精确性适应度。权值ψ为个体精确性的微调因子, 0≤ψ≤1。该因子ψ的设置一般取决于具体的应用需要, 通过衡量精确性的重要程度来决定。

3 实验与分析

本算法在ProM平台进行了初步的实验并验证, 所用数据来自http://prom.win.tue.nl/tools/prom/中的日志集。对传统遗传算法参数设置如下:种群规模M=100, 最大运行代数G=100, 精英率=0.02, 交叉率=0.8, 变异率=0.2;本文算法的设置:M=100, G=100, 精英率=0.02, 退火过程最低温度Tmin=0.01, 创建初始种群的微调因子=1。

根据数据测试结果, 可见本文算法解的质量方面均比传统遗传算法更优。

4 结语

基于混合自适应遗传方法的工作流挖掘算法, 采用因果矩阵映射流程实例作为工作流模型编码, 在遗传算法的选择操作阶段采用锦标赛策略与精英保留策略相结合, 并将混合自适应思想引入参数设置中, 将模拟退火思想分别与交叉和变异操作相结合, 有效地提高了解的质量。但在交叉阶段, 交叉只发生在任务级别上, 另外本文算法没有考虑日志中的时间因素和日志流程增量的问题。

参考文献

[1]W M P VAN DER AALST, B F VAN DONGEN.Workflow mining:a survey of issues and approaches[J].Data and Knowledge Engineering, 2003, 47 (2) :237-267.

[2]宋炜, 刘强.基于模拟退火算法的过程挖掘[J].电子学报, 2008, 36 (4) :135-139.

[3]G SCHIMM.Generic linear business process modeling[C].Proceedings of the ER 2000 Workshop on Conceptual Approaches for E-Business and The World Wide Web and Conceptual Modeling.Lecture Notes in Computer Science, 2000, 1921:31-39.

[4]A K A DE MEDEIROS, A J M M WEIJTERS, W M P VAN DER AALST.Using genetic algorithms to mine process models:representation, operators and results[D].BETA Working Paper Series, WP 124, Eindhoven University of Technology, Eindhoven, 2004.

[5]杨雅芳, 黄紫成.带分级思想的遗传工作流挖掘算法[J].软件导刊, 2013, 12 (12) :57-60.

[6]BOSENIUK T, EBELING W.Boltzmann-darwin-and-heackel-strategies in optimization problems[C].Proc Int Conf on Parallel Problem Solving from Nature.New York, 1990.

混合自适应遗传算法篇2

用自适应伪并行遗传算法求解双准则三维运输问题

采用并行计算的思想,在单台计算机上应用自适应的`伪并行遗传算法,求解了双准则三维运输问题,最后通过实验验证该方法可产生适合需求的解,同时体现了该算法有较快的收敛速度.

作者：张春梅武钧梁治安 ZHANG Chun-mei Wu jun LIANG Zhi-an 作者单位：张春梅,武钧,ZHANG Chun-mei,Wu jun(内蒙古大学,理工学院,呼和浩特,010020)

梁治安,LIANG Zhi-an(上海财经大学,应用数学系,上海,33)

刊名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY 年，卷(期)： 37(11) 分类号：O1 关键词：伪并行自适应遗传算法运输双准则

自适应竞争遗传算法研究篇3

遗传算法具有良好的全局搜索性能，减少了限于局部最优解的风险，鲁棒性强，适用于并行处理，搜索不依赖于梯度信息。标准的遗传算法(SGA)收敛速度太慢，交叉率和变异率固定等缺陷，对提高控制系统的响应速度和控制精度不利，严重影响到遗传算法实际应用，Srinvivas等提出的一种使交叉概率pc和变异概pm随适应度自动改变的方法—自适应遗传算法 (AGA) 。本文研究了基于自适应竞争的遗传算法，采用保优竞争策略。保持最优个体算法就是在每一代的遗传操作中，保持当前一定数量的最优解，它们不参加变异和交叉操作。为了避免过早的陷入早熟，用当前代最优个体取代适应度最差个体，参与交叉变异。自适应竞争遗传算法是个体能够根据自身的适应度大小，自动决定交叉率和变异率且自动取舍是否直接转入下一代还是参与遗传操作。运用MATLAB对其进行仿真，结果显示该算法的有效性。

（二）自适应竞争遗传算法的实现

自适应竞争遗传算法实现过程如下：

1. 初始化：

确定遗传操作的参数：种群大小，染色体长度、进化代数、交叉率和变异率由自适应函数给出。

2. 编码：

本文采用二进制编码方式，二进制的长度由问题解的控制精度确定，这里选择其长度为20，采用二进制编码的优点就是遗传操作方便。

3. 计算各个体的适应度值：

这里的是求一函数的最大值，故可直接把函数实值作为其适应度，由二进制转十进制函数计算出个体适应度值和平均适应度fagv。

4. 保优竞争：

当个体适应度值大于平均适应度fagv的个体即被选中，共计为N个，再次计算该N个体的平均适应度fagv1，当选中的个体大于平均适应度fagv1，直接进入下一代。其中存在两次竞争，第一次和第二次竞争淘汰下来的进行交叉变异操作。

5. 确定交叉率fc和变异率fm自适应函数：

由各个体的适应度大小自行决定交叉率fc和变异率fm的大小，为了避免过早地陷入局部最优，采用两次竞争的最优个体替代最差个体，并给其较小的交叉率和变异率进行遗传操作，具体的确定法则见式 (1) 和式 (2) 。

其中，式2中，0

6. 进行交叉变异操作：

由第四步的公式编写交叉变异函数，分别对其进行调用，计算经过遗传操作的个体适应度，与第一次竞争的优胜个体进行重组操作。

第六步判断遗传操作是否结束：判断是否达到给定的遗传代数，是，给出最优个体，否，则返回第3步。

（三）Matlab编程实现

为了对比验证该算法的有效性，本文采用雷英杰编著的《MATLAB遗传算法工具箱及应用》第七章7.1的例题函数，并与之进行对比。

利用遗传算法计算下面函数的最大值：

选取和例题一样的初始条件，种群个体数目为40，每个种群长度为20，不使用代沟值，取而代之的是竞争操作。

编程环境是基于英国设菲尔德(Sheffield)大学的MATLAB遗传工具箱，标准的遗传算法的交叉率和变异率固定，这里用的是自适应，即各个体的交叉率和变异率是不一样的，要实现这一功能，必须扩展工具箱函数，使其交叉率pc和变异率pm能符合矩阵操作，即可满足自适应操作要求。

保优竞争操作实现代码如下:

（四）仿真结果分析

图1是采用自适应竞争遗传算法对式3进行寻优操作的最后结果图。

图2是自适应竞争遗传操作每代最优解和种群均值的变化曲线。

从图2中可以得出, 运用自适应竞争遗传操作, 在5代之内即可寻到该函数的最大值，运用标准的遗传算法须经过25代后才寻到最优解，如果选择函数选择sus函数时，还有可能陷入局部最优，如图3。

（五）结语

通过仿真发现自适应竞争遗传算法的有效性，时效性，对标准的遗传算法进行了优化，提高控制系统的响应速度和控制精度，对遗传算法实际应用起到一定帮助，但是遗传算法在最优解附近的精调能力较弱，解决办法可用遗传算法与神经网络进行结合，这在后面的研究工作有待体现。

摘要：遗传算法具有良好的全局搜索性能, 鲁棒性强, 适用于并行处理, 但标准的遗传算法 (SGA) 收敛速度太慢, 交叉率和变异率固定等缺陷, 对提高控制系统的响应速度和控制精度不利, 严重影响到遗传算法实际应用。文章主要研究了基于自适应竞争的遗传算法, 采用保优竞争策略, 仿真显示该算法的有效性。

关键词：自适应,遗传算法,保优竞争

参考文献

[1]刘战国, 童明俶, 王明渝, 黄萍.遗传算法在BP网络PID控制中的应用仿真[J].计算机仿真, 2009, 26 (10) :207-211.

[2]王焱, 孙一康.GA-BP网络混合建模方法及其在冷轧参数优化中的应用[J].济南大学学报 (自然科学版) , 2001, 15 (4) :319-322.

[3]吴琦, 胡德金, 张永宏, 徐鸿钧.GA-BP网络建模在套料钻性能预测中的应用[J].兵工学报, 2006, 27 (3) :494-497.

[4]姚有领.智能自适应解藕控制及其在板形板厚综合控制中的应用[D]:[博士学位论文].上海:上海大学机电工程与自动化学院, 2007.

基于梯度的自适应量子遗传算法篇4

以量子算法为代表的量子计算由于具有指数级存储容量、高度的并行性和对经典启发式算法的指数加速作用, 因而在计算复杂度、收敛速度等方面明显超过常规算法。将量子计算机制引入现有进化算法可以在很大程度上提升算法的各项优化性能。目前, 量子计算与进化算法的融合研究主要集中于进化策略的构造和编码方式。在量子进化算法中, 个体采用量子位概率幅编码, 用量子非门代替个体变异以实现群体的多样性, 用基于量子门的量子比特相位旋转实现个体进化。

本文根据量子计算原理, 对量子旋转门转角的确定方法做了改进研究, 提出了一种考虑目标函数梯度的自适应计算方法, 并对基于该方案的改进量子遗传算法进行了数值模拟。

1基本量子遗传算法

2000年, K.H.Han等人将量子的态矢量表达引入到遗传算法的编码中, 利用量子旋转门实现染色体基因的变换, 提出了第一种量子遗传算法 (Quantum Genetic Algorithm, QGA) , 并通过一类组合优化问题验证了算法的有效性。

QGA是基于量子叠加态和量子位的概念提出的。量子比特或量子位是量子计算中的最小信息单位。一个量子位可以处于|0〉态、|1〉态以及|0〉态和|1〉态之间的任意叠加态。一个量子位的状态可以描述为:

如果一个系统有个量子位, 则该系统可同时描述2m个状态, 然而在观测时, 该系统将坍缩为一个确定的状态。

传统进化计算的染色体编码通常有3种方式:二进制、十进制、符号编码。在QGA中采用基于量子位的编码方式, 一个量子位可由其概率幅定义为undefined, 同理, m个量子位可定义为:

其中, |αi|2+|βi|2=1, i=1, 2, …, m。这种描述的优点在于可以表达任意量子叠加态。

量子遗传算法的伪代码如下:

与GA相似, QGA也是一种全局性概率搜索算法, 它包括一个群休Q (t) ={qundefined, qundefined, …, qundefined}。其中, t表示进化代数, n是群体规模, qundefined为所谓量子染色体, 其定义为:

其中, m为量子位数, 即染色体的长度, j=1, 2, …, n。

2基于梯度的改进量子遗传算法

量子遗传算法中的关键技术之一是如何计算量子旋转角的方向和大小。迄今为止, 大多数已有的量子遗传算法均采用基于查询量子旋转角表的方法。这种算法要进行多路条件判断, 所以算法的效率不高。有些学者提出了一种基于自适应的确定转角的方法, 使迭代步长随着进化代数的增加而逐渐减小。不过, 此方法没有充分考虑各个染色体个体间的差别, 而对全部个体一视同仁。

本文提出了一种考虑目标函数梯度的量子旋转门转角的自适应计算方法, 并据此给出了一种改进的量子遗传算法GQGA。

2.1编码方案

在GQGA中, 根据量子位上对应的概率幅来编码。考虑到初始群体编码的随机性及量子态对应的概率幅要遵循的约束条件, 可采用双链编码方案:

其中, n为量子位数, m为群体规模, tij=2π×rand, rand为介于0和1之间的随机数。在GQGA中, 把每个量子位上的概率幅视为两个上下并列的基因, 每条染色体都包含并列的两条基因链, 而每条基因链即表示一个最优解。从而, 每条染色体便可以同时搜索寻解空间中的两个最优解:

其中, i=1, 2, …, m, Pis称为“正弦”解, Pic称为“余弦”解。这种处理方法的好处在于既避免了十进制与二进制的相互转换过程, 也避免了因测量而导致的随机误差。由于在每次的迭代过程中正弦和余弦解同时更新, 所以在群体规模保持不变的条件下, 可以增强对于解空间的搜索遍历性, 提高优化速度。同时, 还可以增加全局最优解的数量, 提高全局收敛性的概率。

2.2量子旋转门转角的确定

GQGA用于更新量子比特相位的量子旋转门为:

更新过程为:

undefined

确定量子旋转门转角大小的方法是:将目标函数在某个染色体处的变化趋势信息适当添加到转角步长的计算函数中。当目标函数在搜索点处变化率较小时, 适当增加转角步长, 否则适当减小转角步长。这样既保证了收敛速度, 又兼顾了全局收敛性。根据上述思想, 可构造转角步长函数如下:

undefined

其中, Δθ0为迭代初值, ∇f (Xundefined) 为目标函数f (X) 在点Xundefined处的梯度, A、∇fjmax和∇fjmin分别定义为:

undefined

α0和β0是迄今搜索到的全局最优解中的某个量子位的概率幅, α1和β1是当前最优解中对应量子位的概率幅。

2.3算法描述

实现上述梯度量子遗传算法的伪代码如下:

步骤1:初始化种群。根据 (5) 式生成由m条染色体构成的初始种群, 设初始转角步长为θ0, 变异概率为pm。

步骤2:变换解空间。把每个染色体表示的近似解, 从单位空间In=[-1, 1]n映射到解空间Ω, 算出每个染色体的适应度。记当前最优解为X0, 相应染色体为P0, 当代最优解为X0, 相应的染色体为P0。若fit (X0) >fit (X0) , 则P0=P0。

步骤3:对群体中的所有染色体上的每个量子位, 用P0中对应的量子位为目标, 根据“2.2”中的方法计算转角大小及方向, 采用量子旋转门确定新的量子位。

步骤4:对群体中的每个染色体, 根据变异概率用量子非门进行变异。

步骤5:转至步骤2, 直至达到最大进化代数或满足收敛条件为止。

3数值实验

下面选取两个常用的标准测试函数进行数值模拟计算, 并将计算结果与基本量子遗传算法CQGA和一般遗传算法CGA进行对比分析, 以检验上述算法的有效性。

(1) Shaffer’s F5函数。

其中, xi∈ (-65.536, 65.536)

undefined

该函数有多个局部极大值点, 最大值点为 (-32, -32) , 最大值为1.002。若目标函数值大于1.000, 则理解为算法收敛。Shaffer’s F5函数的图像如图1所示。

(2) Shaffer’s F6函数。

该函数有无穷多个局部极大值点, 但其中只有 (0, 0) 为全局最大值点, 最大值为1。自变量的定义域均为 (-100, 100) 。当优化结果大于0.995时认为算法收敛。该函数的图像如图2所示。

算法参数:种群规模m=50, 量子位数n=2, 交叉概率pc=0.8, 变异概率pm=0.1, 转角步长初值θ0=0.01π, Shaffer’s F5限定代数Lmax=200, Shaffer’s F6限定代数Lmax=500。在CQGA中, 编码长度取为20, 即每个染色体包含40个量子位, 适应度函数即取为目标函数。

对于上述两个测试函数, 分别用GQGA、CQGA、CGA进行10次计算, 优化结果见表1、图3和图4。

从表1、图3和图4中可以很清楚地看出, 基于梯度的改进量子遗传算法GQGA在优化精度、计算速度、收敛性等方面均明显优于普通量子遗传算法CQGA和普通遗传算法CGA, 这主要得益于考虑了目标函数的梯度以及确定量子旋转门转角的自适应机制。

摘要：根据量子计算原理, 提出了一种量子旋转门转角的自适应确定方案。该方案的基本思想是在设计量子旋转门转角大小时, 充分考虑目标函数的梯度, 当目标函数变化率较小时, 适当增加转角步长, 反之适当缩小转角步长。数值计算结果表明, 基于该方案的改进量子遗传算法比基本量子遗传算法有更佳的全局收敛性和更快的收敛速度。

关键词：量子遗传算法,目标函数梯度,量子旋转门转角

参考文献

[1]SHOR P W.Algorithms for quantum computation[C].DiscreteLogarithms and Factoring.Proc.of the 35th Annual Symp, 1994.

[2]GROVER L K.A fast quantum mechanical algorithm for databasesearch[C].Proc.of the 28th Annual ACM Symp, 1996.

[3]NARAYANAN A, MOORE M.Quantum-inspired genetic algo-rithms[C].Proceedings of IEEE International Conference on Evo-lutionary Computation, 1996.

[4]HAN K H, KIM J H.Genetic quantum algorithm and its applica-tion to combinational optimization problem[C].Proceedings of theInternational Congress on Evolutionary Computation, 2000.

[5]TALBI H, DRAA A, BATOUCHE M.A new quantum-inspiredgenetic algorithm for solving the traveling salesman problem[C].Proceedings of the International Conference on Industrial Technol-ogy, 2004.

[6]KHORSAND A R, AKBARZADEH M R.Quantum gate optimi-zation in a meta-level genetic quantum algorithm[C].2005IEEEInternational Conference on Systems, Man and Cybernetics, 2005.

[7]MOORE P, VENAYAGAMOORTHY G K.Evolving combina-tional logic circuits using a hybrid quantum evolution and particleswarm inspired algorithm[C].Proceedings of the 2005NASA/DoDConference on Evolvable Hardware, 2005.

[8]DREO J, SIARRY P.An ant colony algorithm aimed at dynamiccontinuous optimization[J].Applied Mathematics and Computa-tion, 2006 (1) .

[9]ZHANG G X, LI N, JIN W D.A novel quantum genetic algorithmand its application[J].ACTA Electronica Sinica, 2004 (3) .

基于自适应遗传算法的入侵检测方法篇5

入侵检测(Intrusion detection)是通过对系统数据的收集与分析,发现未经授权的攻击行为和网络访问,从而为网络安全提供有力的保障[1]。目前入侵检测智能性研究成为热点,这主要是因为智能优化算法、神经网络、模式识别等技术的引入[2]。例如刘永忠等[3]提出了一种基于模糊粗糙集的特征加权聚类算法(FRS-FCM),该方法能有效提高入侵检测的检测准确率,降低误检率,并较大地提高低频攻击的检测率。朱红萍等[4]提出一种基于遗传算法的入侵检测特征选择算法。该算法在保证特征分类精度和确保入侵检测漏检率、误检率尽量小的前提下明显提高了入侵检测的效率。胡明霞等[5]通过遗传算法找到BP神经网络的最适合权值,解决直接使用BP学习造成的训练样本数量过大而难以收敛的问题,与传统网络入侵检测算法相比,该算法的训练样本时间更短,具有较好的识别率和检测率。

智能算法、神经网络、模式识别等技术具有自适应(Self-adaptation)、自学习(self-learning)的能力,可以通过自适应、自学习从中提取正常的系统或用户活动特征模式,并检测出异常活动的攻击模式[6,7,8]。这些特性使得上述方法在入侵检测系统中得到了很好的应用[9,10]。遗传算法(Genetic Algorithm,GA)是一种全局启发式搜索 ,属于人工智能的进化计算分支[11]。现基于此提出一种基于遗传算法的入侵检测方法,该方法用自适应的适应度函数、交叉概率及变异概率取代固定的适应度函数、交叉概率及变异概率来改进遗传算法。

1 遗传算法简介

按照达尔文(Darwin)的进化论,地球上的任何一种生物从诞生开始就进入漫长的进化阶段。期间必存在生存斗争,生存能力强的个体存活下来比较容易,并有较大的机会产生后代;具有较弱生存能力的个体则较容易被淘汰,或者有较低的概率产生后代,直至渐渐消亡。

遗传算法主要就是根据达尔文的进化论以及孟德尔和摩根的遗传学理论而提出的一种基于生物进化机制的全局性概率搜索算法。可用于解决很多应用领域的问题。遗传算法用编码空间代替问题的参数空间,以适应度函数作为一个评价依据,依据一定的概率p重组编码位串,从而生成新一代的编码,群体中的个体不断得到优化,逐渐接近最优解,从而最终达到求解问题的目的。习惯上把Holland于1975年提出的遗传算法称为传统的遗传算法。其主要步骤如下[12]:

1) 给定群体规模N,交配概率Pc和变异概率Pm;

2) 随机生成一个N个初始解组成的初始群体;

3) 计算当前初始群体各染色体x的适应度函数值F(x);

4) 如果满足停止准则,则转10);

5) 对群体中的每一个染色体x计算概率p(x);

6) 依据概率值从群体中随机选择N个染色体,得到种群;

7) 依交配概率Pc按交叉算子进行交配,其子代进入新的群体,未进行交配的染色体直接复制到新群体中;

8) 依变异概率Pm从种群中选择染色体按变异算子进行变异操作,用变异后的染色体代替新群体中的原染色体;

9) 用新群体代替旧群体,代数加一,转3)

10) 进化过程中适应值最大的染色体,经解码后作为最优解输出;

11) 结束。

计算过程用流程图表示如图1。

2 自适应遗传算法设计与应用于入侵检测

2.1 基于GA的入侵检测模型

基于GA的入侵检测模型如图2所示。

2.2 自适应遗传算法

2.2.1 适应度函数

适应度函数在遗传算法中表示个体接近最优解的程度,因而要求设计的适应度函数保证适应度非负。在进化的初期,可能出现个别适应度很高的个体(接近或是局部最优解),而大多数个体适应度还很低,因此这样的个体被选择的概率远高于其它个体,可能充斥下一代群体,使得进化难以继续,出现早熟现象;而在进化的后期,群体中个体的适应度相近,较好的个体和较差的个体被选择的概率差不多,会使得进化缓慢,从而降低收敛速度。为解决这个问题,本算法采用适应度的差值衡量适应度的差异大小,具体定义为

$\begin{array}{l} β = Δ f / Δ F (1) \\ Δ f = f_{\max} - f_{\min} (2) \\ Δ F = F_{\max} - F_{\min} (3) \end{array}$

其中,ΔF为适应度的理论最大差值,Δf为本代群体适应度的差值,fmax为本代群体适应度的最大值, fmin为本代群体适应度的最小值, Fmin为适应度的理论最小值,Fmax为适应度的理论最大值,可知β的取值范围为[0,1]。如果采用适应度和平均适应度的差值的绝对值的平均值、差值的平方的平均值(即方差)等衡量,虽然更准确,但计算更繁琐,将影响运算速度,且最大平均值不好计算,以致与平均值的比值的取值范围(后面将要用到)难以确定。根据β对适应度进行变换

$f^{'} (x) = f (x) + k (β - 0.5) (4)$

式(4)中,k是常数,f(x)为变换前的适应度,f′(x)为变换后的适应度,根据具体情况设置, 越大则变换力度越大,但要尽量保证个体的适应度非负。

当群体中个体的适应度差异较大时 (β>0.5),个体的适应度都增大 k(β-0.5),但适应度小的个体增长的比例大,被选择的概率增大,有利于保持群体的多样性,以向更广的解空间搜索,避免陷入局部最优;当群体中的个体适应度差异较小时 (β<0.5),个体的适应度都减小k(0.5-β)(这时个体的适应度普遍较大,减少后应仍非负,如果有个别个体适应度太小,减少后为负,可补充定义为 0(意味着将其淘汰)或某个较小值(以增强群体的多样性)),但适应度大的个体减少的比例较小,被选择的概率增大,增加了搜索的导向性,避免盲目搜索。

2.2.2 变异概率

传统GA的变异概率是固定的,现采取动态的方式灵活调整,具体方法如下:当染色体个体差异较小时,应使得变异概率增大,这样能保持群体的多样性,以便向更广的解空间进行搜索,避免陷入局部最优。当个体差异较大时,应使得变异概率减少,达到减少计算量并保证群体的多样性。因此定义变异概率

$Ρ_{m} = 0.2 (1 - β) (5)$

因为变异运算也会破坏好的个体,变异概率一般取值较小(在生物进化中也较小),所以乘以0.2。可知Pm的取值范围为[0, 0.2]。

2.2.3 交叉概率

标准遗传算法的交叉概率是固定的,并不能很好体现变异的作用。在进化的初期,应增大交叉概率,这是因为初期个体差异较大,交叉产生更好个体的概率也较大;在进化的后期,个体差异较小 (相当于“近亲结婚”),交叉产生更好个体的可能性也较小,应减小交叉概率,减少计算量。因此定义交叉概率如下:

$Ρ_{c} = β (6)$

可知 Pc的取值范围为[0,1]。

3 对比实验与分析

在对比实验中,采用经典的KDD’1999数据集,该数据集包含DOS、PROBE、R2R、U2R等攻击类型数据[13]。

图3为遗传算法的误差平方和曲线和适应度曲线,图4为本文自适应遗传算法误差平方和曲线和适应度曲线,从图4可以看出大约经过了400迭代的搜索后染色体的平均适应度趋于稳定,收敛时间为11.413 seconds,误差为0.039。从图3可以看出在标准的GA中,大约经过500次迭代搜索后染色体的平均适应度将逐渐趋于稳定,收敛时间为13.987 seconds,误差为0.089。从表1中可以看出,本文提出的方法和遗传算法相比较,在检测时间方面,本文提出的方法则是表现最好的,入侵检测准确率明显高于上述算法,并且区别很明显。对不同类型的攻击检测具有良好的均衡性,并且能保证较高检测率。

4 结束语

提出一种基于改进的遗传算法-自适应遗传算法的入侵检测方法,算法显著提高了收敛性能,并且具有很强的自适应能力,并在保证较高检测率的基础上,对不同类型的攻击检测具有良好的均衡性。

混合自适应遗传算法篇6

关键词：遗传算法,配电网,定位

0 引言

配电网故障定位是配电网故障隔离、重构恢复供电的前提, 它对于提高配电网的运行效率、改善供电质量、减小停电范围有着重要作用。当配电网一旦发生单相接地、相间短路等故障时, 要求调度人员立即获知故障信息并作出相应决策, 因此, 研究配电网故障定位问题具有十分重要的意义。目前常用的配电网故障定位方法包括:矩阵算法、专家算法、神经网络、遗传算法、蚁群算法等。矩阵算法其程序简单, 运算速度较快, 但过多依赖于拓扑结构和故障信息[1,2]。专家算法需要定期更新决策表, 繁琐的工作对于配电网故障定位这一高容错性的要求, 不免限制了它在工程上的应用[3]。神经网络具有很强的适应性, 但它需要大量的样本进行训练, 其训练参数的选取决定了结果的精确性[4]。

1 自适应遗传算法

遗传算法 (GA) 是一种基于自然选择和自然遗传机理的概率搜索算法, 利用某种编码技术作用于称为染色体的串, 其基本思想是模拟这些串组成的个体进行遗传进化的过程。基本遗传算法的遗传操作主要包括选择、交叉、变异, 易出现“早熟”、全局收敛速度慢等问题, 因此, 本文把自适应遗传算法应用于配电网故障定位中。

1.1 遗传算法中选择算子的选取

选择操作方法包括适应度比例法、排序竞争法、最优保存策略、精英保留策略等, 传统遗传算法常采用适应度比例法。适应度比例法, 又称轮盘赌法, 是按照个体的适应度值与种群各个个体适应度值之和的比值来确定个体的选择概率。若种群数目为N, 个体的适应度为fi, 则可计算出个体的选择概率Pi和累计概率Wi, 由累计概率Wi和随机产生[0, 1]之间的随机数v来比较确定哪个个体被选择参与交配。公式 (1) 和 (2) 分别为个体i的选择概率Pi和累计概率Wi:

当随机数v≤W1时, 就选择第1个个体, 否则选第i个个体, 第i个个体满足Wi-1≤v≤Wi。

1.2 遗传算法中交叉、变异概率的自适应调整

对于整个遗传进化过程, 交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键, 为了维持种群的多样性, Pc越大, 新个体产生的速度越快, 当交叉概率过大时, 遗传模式被破坏的可能性越大, 则适应度高的个体结构被破坏的可能性越大;交叉概率过小时, 好的模式保留的可能性越大, 种群的多样性难以保证, 搜索停滞不前, 容易过早收敛。对于变异概率Pm, 如果Pm过小, 就不易产生新的个体结构;如果Pm取值过大, 那么遗传算法就变成了纯粹的随机搜索算法。对于优化问题来说, 需要反复实验来确定交叉、变异概率的取值, 而且很难找到适应每个问题的最优解。因此, 为了克服传统遗传算法中固定交叉和变异概率的选取问题, 将自适应调整的Pc和Pm引入到传统遗传算法中, 式 (3) 和 (4) 分别为Pc和Pm的计算公式:

式中, fmax为种群中最大的适应度值;favg为每代种群的平均适应度值;f1为需要交叉的2个个体中较大的适应度值。

根据前人的经验, 上式中的Pc1=0.9, Pc2=0.6, Pm1=0.1, Pm2=0.001。

2 配电网故障定位的自适应遗传算法

配电网线路发生故障时, 安装于配电网线路的分段开关和联络开关上的FTU或远程终端单元RTU将采集到的电流信息, 与整定的值进行比较后将开关过流信号上传至数据采集中心SCADA处, 经处理确定故障区段, 因此, 遗传算法全局优化, 快速收敛的优点满足配电网故障定位的要求。

2.1 编码方法

遗传算法以编码空间代替问题空间, 它只能对染色体进行运算, 因此, 在对问题进行求解时, 必须先将问题进行编码。遗传算法编码有二进制[0, 1]编码、实数编码、浮点数编码等, 配电网故障定位可采用遗传算法0、1编码方式, 当分段开关有故障电流流过时为1, 当无故障电流时为0。

2.2 适应度函数

利用自适应遗传算法进行配电网故障定位是从解空间里找到一个或几个元件设备, 当有故障发生时, 适应度函数最能解释由FTU上传至配电SCADA监控中心的开关故障电流信号。文献[5]采用的适应度函数, 即:

式中, Ij为第j个开关的越限信号, 由FTU直接采集到的信号, Ij=1说明有过电流流过, Ij=0说明没有过电流流过。由于公式容易出现误判, 因此本文对公式 (4) 进行改进, 即:

式 (6) 在式 (5) 的基础上加了后面一项是因为当假设的故障点为单点故障时, F (S) =0时得到的最优值, 即对应的故障点才为真正的故障, 否则出现多余一个伪故障点时, 公式 (2) 仍然可以为0, 但得到的最优值不一定是真正的故障。在遗传算法中, 由于存在适应度最大值或最小值变换问题, 但本目标函数得到的值是非负的, 因此, 无需进行转换。

2.3 开关函数

为了满足故障元件状态到开关设备有无故障电流状态的转换, 使得遗传算法能够通过开关故障电流信息来得到故障元件, 实现故障定位, 就要建立开关函数, 它反映了开关和元件间的关系。本文只讨论单电源情况, 单电源的开关函数采用文献[6]的形式, 即:

式中, Si代表设备 (馈线、负荷等) , Ij (S) 为第j个分段开关的开关函数, 当第j个分段开关后面的设备发生故障时, Ij (S) 为1, 否则为0。图1是一条单电源辐射状馈线, 它具有单电源树状的拓扑结构, 图1中S4为假设的故障点, 其中S1、S2、S3、S4、S5、S6、S7为设备, 包括负荷、线路等。1为进线断路器, 2、3、4、5、6、7为分段开关。当S4假设为故障点后, 进线断路器1, 分段开关2、3、4有故障电流流过, 当S3为故障点时, 进线断路器1, 分段开关2、3有故障电流流过, 其他设备发生故障情况时以此类推。设备和设备状态表示如表1所示。

设备1、2、3、4、5、6、7的开关函数为:

式中, Π表示逻辑或。

从式 (8) ~ (14) 可知, 当S4假设为故障点时, 设备S4的状态信息为1, 且设备S1、S2、S3、S4均有故障电流流过, S1、S2、S3、S4的越限信号都为1, 为了使得适应度函数值为最小, 则开关函数的值也应该为1, 由式 (4) 可知, 越限信号I1=1, I2=1, I3=1, I4=1, I5=0, I6=0, I7=0, 开关函数I1 (S) =1, I2 (S) =1, I3 (S) =1, I4 (S) =1, I5 (S) =0, I6 (S) =0, I7 (S) =0时, F (S) =0, 此时, 设备S4的状态信息为1的情况下, 设备S3的状态信息可以为0或1, 同理, 设备S1、S2的状态信息也可以为0或1, 这样就出现了伪故障点使得F (S) =0, 因此, 在式 (4) 的基础上, 加上一项, 使得线路发生单点故障时能准确地定位该故障点, 以避免伪故障点的产生。

2.4 遗传操作

本文算法的遗传算子可以分为选择算子、交叉算子、变异算子。其中, 选择算子按照最优保留策略法, 对好的个体保留, 差的个体抛弃;交叉算子和变异算子采用自适应概率, 自适应调整交叉、变异概率, 使各个个体进化过程获得最佳的概率, 以增加算法的收敛性能。

2.5 收敛判据

本文采用算法跳出迭代循环为收敛条件, 也就是设定最大的迭代次, 算法迭代一定次数后自主跳出循环, 算法终止。

2.6 配电网故障定位自适应遗传算法的程序流程

自适应遗传算法的工作流程如图2所示。步骤1:随机产生初始种群popsize, 进行initialization;

步骤2:对种群中的各个个体进行适应度评价, 若存在个体满足收敛准则, 算法收敛输出优值, 否则转向步骤3;

步骤3:随机产生[0, 1]之间的常数v, 与各个个体的选择概率进行比较来确定参与交叉、变异的父代个体;

步骤4:对选择后产生的两两父代个体进行自适应交叉、变异, 并将交叉、变异后的子代个体进行适应度评价, 若存在个体满足收敛准则, 算法收敛输出最优值, 否则转向步骤3。

3 算例仿真

3.1 故障仿真

在配电网线路发生单一故障的情况下, 采用本文图1的模型和自适应遗传算法编程进行仿真, 软件使用Matlab2010b, 编程语言为Matlab编程语言。其中初始交叉、变异算子为Pc1=0.9, Pc2=0.6, Pm1=0.1, Pm2=0.001, 初始种群设为50, 最大迭代次数设为100。

配电网故障可能发生在单点或多点, 故障过流信号模拟实际中各测控点汇集的故障信息, 故障电流信号与图1开关的编号顺序一致。故障信息如表2所示, 测试结果如表3所示。

表3是在表2有故障信号涌入后的故障区段诊断结果, 在发生单点故障时区段3发出错误信号, 自适应遗传算法仍能诊断到区段4发生了故障, 可以看出, 无论是单点故障还是多点故障, 自适应遗传算法都能准确地定位故障区段。

3.2 算法性能测试

为了比较自适应遗传算法的性能, 本文采用文献[6]的收敛速度进行比较, 对比结果如表4所示。

4 结语

本文将自适应遗传算法应用到配电网故障定位中, 并与文献[6]进行对比, 验证了自适应交叉、概率在改善遗传算法性能上是有效的, 且收敛速度是很快的。

参考文献

[1]许奎, 张雪松, 杨波.配电网故障定位的改进通用矩阵算法[J].继电器, 2007, 35 (3) :6～8

[2]王飞, 孙莹, 郑玉平.配电网故障定位的改进矩阵算法[J].电力系统自动化, 2005, 25 (5) :40～42

[3]杜一, 郁惟镛, 文华龙.采用神经网络和专家系统的变电站故障诊断系统[J].电力系统及其自动化学报, 2003, 15 (5) :28～29

[4]廖大发, 刘会金, 傅志伟.基于神经网络模式的故障定位[J].湖北电力, 2004, 28 (1) :9～11

[5]丁同奎, 张丽华.基于蚁群算法的配电网故障定位与隔离[J].继电器, 2005, 33 (24) :29～31

混合自适应遗传算法篇7

与有人驾驶飞机相比,无人机具有体积小、造价低、使用方便等优点。无人机轨迹优化可以达到节省燃油以节约成本和增加续航时间等目的,具有重要的实际意义[1]。无人机轨迹优化剖面包括爬升段、巡航段和下降段,其中爬升段作为飞行性能中的重要组成部分;其飞行速度、燃油消耗和所用时间都对整个飞行过程有着很大的影响。因此,本文主要针对爬升段轨迹优化进行研究。爬升段轨迹优化的任务是根据优化性能指标得到最佳参考轨迹,常用性能指标有:a)最快爬升,b)最省燃油爬升等。

轨迹优化已取得了一些成果,如吴丽娜[3]采用一种基于改进遗传算法的优化技术研究了最快爬升轨迹;张锦[4]利用遗传算法,以飞机纵向剖面最节省燃油作为性能指标,进行了最优参考轨迹设计;均取得了一定的优化效果。遗憾的是,这些都只是寻求单一的指标的最优化,无法同时达到时间既短、耗油量又少的优化目的。无人机的燃油率随速度的增加而迅速增大,若单独以最快爬升作为优化性能指标,就会导致爬升率过高,爬升速度过快,油耗较大;相反,若以最省燃油为优化指标,优化轨迹的爬升率较小,使得爬升时间较长。基于此,本文综合考虑爬升时间和油耗这两点因素,选择两者的加权和(即综合运营成本)作为优化性能指标,对无人机爬升段进行轨迹优化。

1 无人机轨迹优化问题数学模型

1.1 无人机模型

本文主要研究无人机纵向剖面(包括爬升段、巡航段和下降段)轨迹优化的问题。假设无人机在该阶段内做无侧滑的质点运动,并且忽略风的影响,其气动力学方程为:

$m \frac{d v}{d t} = Τ \cos α - L \sin α - D - m g \sin γ (1)$

$m v \frac{d γ}{d t} = Τ \sin α + L \cos α - m g \cos γ (2)$

$\frac{d x}{d t} = v \sin γ (3)$

$\frac{d y}{d t} = v \cos γ (4)$

γ=θ-α (5)

$\frac{d m}{d t} = q_{h} (6)$

其中,m为无人机的总质量,x和h分别是无人机的水平航距和高度变化,v为无人机的空速(因忽略风的影响,所以也是地速),θ、α和γ分别是无人机的俯仰角、迎角和航迹倾斜角,L、D和T分别是无人机的升力、阻力和发动机的推力,q是无人机在一定高度h时的耗油率。

1.2 结合性能指标的优化模型

首先,将爬升段(1 000 m—10 000 m)按等高度Δh=1 000 m为步长划分成9段。假设无人机从点hi飞到点hi+1,飞行速度、航迹倾斜角的变化分别是:vup,i→vup,i+1,γup,i→γup,i+1;然后,计算各段所用的时间、航距和油耗(用Δti、Δxi、ΔWfi分别表示无人机从高度hi爬升到高度hi+1的飞行时间、水平航距和耗油量),有

$Δ t_{i} = \frac{m (v_{u p, i + 1} - v_{u p, i})}{Τ \cos α_{i} - L s i n α_{i} - D - m g s i n γ_{u p, i}} (7)$

$Δ x_{i} = \frac{1}{2} (v_{u p, i} + v_{u p, i + 1}) Δ t_{i} \cos γ_{u p, i} (8)$

$Δ W_{f_{i}} = \frac{1}{2} (q_{h_{i}} + q_{h_{i + 1}}) Δ t_{i} (9)$

Ji=ctΔti+cfWfi (10)

从而得到整个爬升阶段所用的时间tup,水平航程xup、油耗Wup分别为:

${\begin{cases} t_{u p} = \sum_{i = 1}^{n} Δ t_{i} \\ x_{u p} = \sum_{i = 1}^{n} Δ x_{i} \\ W_{u p} = \sum_{i = 1}^{n} Δ W_{f_{i}} \end{cases} (11)$

爬升段的飞行成本是:

$J_{u p} = \sum_{i = 1}^{n} J_{i} (12)$

爬升段的轨迹优化问题就转化为:寻求使性能指标式(12)达到最小的各高度段的vi和γi。

2 基于自适应遗传算法的无人机轨迹优化

2.1 自适应遗传算法

遗传算法模拟基因重组与进化的自然过程[5]。一般遗传算法的交叉算子和变异算子都是固定的值,针对不同的优化问题,需要反复实验来确定pc和pm这两个重要参数,这是一件烦琐的工作,而且很难找到适应每个问题的最佳值。自适应遗传算法中,按照以下公式根据各染色体的适应度值自动调整pc和pm[6]:

$p_{c} = {\begin{cases} p_{c 1} - \frac{(p_{c 1} - p_{c 2}) (f^{'} - f_{a v g})}{f_{\max} - f_{a v g}} ‚ f^{'} > f_{a v g} \\ p_{c 1} ‚ f^{'} < f_{a v g} \end{cases} (13)$

$p_{m} = {\begin{cases} p_{m 1} - \frac{(p_{m 1} - p_{m 2}) (f_{\max} - f)}{f_{\max} - f_{a v g}} ‚ f > f_{a v g} \\ p_{m 1} ‚ f < f_{a v g} \end{cases} (14)$

式中,fmax是群体中最大的适应度值,favg是每代群体的平均适应度值,f′是要交叉的两个个体中较大的适应度值,f是要变异的个体的适应度值。pc1,pc2,pm1,pm2是(0,1)之间的常数,本文取pc1=0.9,pc2=0.6,pm1=0.1,pm2=0.001。

2.2 自适应遗传算法爬升段轨迹优化

根据1.2对爬升段轨迹优化的分析,该段主要是对每一个高度段的爬升速度vi和爬升角γi进行寻优计算,给出结合自适应遗传算法的轨迹优化的具体方法和步骤。

2.2.1 编码

既然是对每一个高度段的vi和γi进行寻优,就应该对所有高度段的vi和γi进行编码,即对v1γ1,v2γ2,…,vnγn进行编码,这样,每一个个体就对应一个爬升轨迹。其中每一个vi用7位二进制表示,每一个γi用7位二进制表示(这样速度等精度小于0.5 m/s,爬升角的精度小于0.1°),即每一个高度段的轨迹参数用一个14位的二进制串表示,则整个爬升段的轨迹参数(每个表示爬升轨迹的染色体)用一个126(14×9=126)位的二进制串表示。

2.2.2 种群初始化

若种群规模较小,则会使遗传算法的搜索空间范围有限,搜索有可能停止在未成熟阶段,因此,种群规模应适当增大(选为200)。同时,为了能够比较全面地搜索,应使初始种群随机且均匀地遍布解空间。

2.2.3 适应度函数的设计

爬升段轨迹优化的目标是使性能指标达到最小,而性能指标始终为正值,适应度函数应该保证使得优化问题是求解问题的正的最大值,这里在设定适应度函数时,只需对爬升成本式(12)取倒数即可,即

$F i t (f (x)) = \frac{1}{J_{u p}} (15)$

2.2.4 遗传算子的设计

遗传算子的设计主要包括:①选择算子,②交叉算子和变异算子。选择算子采用锦标赛选择,按照2.1节中自适应遗传算法中给出的式(13)和式(14)更新种群中各染色体的交叉算子和变异算子。

2.2.5 终止条件的判定

为了能够充分地搜索使得爬升成本更小地参考爬升轨迹,同时考虑到遗传算法有可能收敛速度慢的缺点,以达到一定的种群进化代数(如500代)为中止条件。

基于AGA进行爬升段轨迹优化的流程图如图1所示。

3 实例仿真

本文以某型无人机为例,应用本文所述算法对其爬升段进行轨迹优化。无人机以0.4 Ma的初始速度从1 000 m高度爬升到10 000 m,约束条件为:

0.4≤Ma≤0.581,0°≤α≤5°,0°≤γ≤8°。本文所选优化步长是Δh=1 000 m,优化结果如图2—图4所示。

图2中(a)～(f)分别显示了得到的最优参考爬升轨迹的相关参数随时间的变化关系,根据这些参数就可以确定最优的爬升参考轨迹。由(a)和(b)可以看出马赫数和空速都随时间逐渐增大。由(d)可以看出,初始时飞机有3.15°的迎角以使得爬升角能够迅速增大,爬升角较大后,迎角趋于0°,这符合无人机爬升的实际情况。由(e)可知爬升角先随时间增加,然后再逐渐减小,这样在爬升初始时刻,以较小的爬升角爬升,在爬到较高的高度时以较大的爬升角快速爬升,在接近目标高度时以较小的爬升角爬升,这样既能快速爬升到目标高度,又有利于爬升段到巡航段的过渡转化。由(c)和(f)可以确定水平航距和高度的关系,从而得到最终参考轨迹。

图3给出了每一代种群中最优的轨迹的最小爬升成本,可以看出:前100代收敛速度很快,200代以后爬升成本减小很慢,但还在继续朝着更优的轨迹发展,这说明自适应遗传算法的优越性。

图4给出了采用AGA算法和传统算法得到的参考爬升轨迹所需成本的对比关系,由图可以看出,采用AGA算法得到的参考轨迹成本明显小于传统方法得到的参考轨迹的成本,经计算采用AGA算法得到的爬升轨迹比用传统方法得到的参考轨迹在运营成本上节约了6.3%。

4 结论

本文应用自适应遗传算法研究了无人机爬升段轨迹优化的问题,并通过实例计算,验证了利用自适应遗传算法得到的参考爬升轨迹既符合无人机实际的爬升规律,又能大幅度地降低爬升的总成本,优化出来的轨迹的爬升成本比采用传统方法得到的参考轨迹在运营成本上节约了6.3%,这充分说明了自适应遗传算法在解决无人机爬升轨迹优化问题的优越性。

参考文献

[1]沈延航,周洲.无人机爬升航迹优化设计研究.飞行力学,2004;22(3):28—30

[2]张培培,王新民,陈晓,等.基于改进粒子群算法的无人机爬升轨迹优化.计算机仿真

[3]吴丽娜,王和平.基于改进遗传算法的最快爬升航迹的优化分析.科学技术与工程,2009;9(10):2669—2673

[4]张锦,王伟,宁东方.用遗传算法进行飞机节油轨迹优化.弹箭与制导学报,2005;25(4):453—455

[5]刘萍,陆宇平.一种基于遗传算法的航迹优化技术.计算机测量与控制,2007;17(7):961—962,971

模糊自适应混合退火粒子滤波算法篇8

关键词：粒子滤波,非线性,非高斯,粒子退化,模糊自适应,混合退火

0 引言

粒子滤波PF(Particle Filter)是一种基于蒙特卡罗思想的非线性、非高斯滤波方法[1,2],它突破了Kalman滤波KF(Klaman fliter)的局限,并广泛地应用在机动目标跟踪、图像处理等不同领域[3]。处理线性滤波问题最常用的是KF算法,在处理非线性滤波问题时,广泛应用的方法是扩展Kalman滤波EKF(expand Kalman filter)算法。但是EKF仅仅是利用了非线性泰勒展开式的一阶偏导部分,丢失了高阶信息,在实际中的系统多是非线性、非高斯的,在这种情况下,应用EKF估计系统状态和方差时误差会较大,甚至可能发散[1]。

1993年,Gordon等提出了自举粒子滤波(bootstrap particle filter)算法[4],随后粒子滤波PF得到长足发展,而后粒子滤波的许多改进算法被相继提出。粒子滤波( 又称为序贯蒙特卡罗方法)通过蒙特卡罗抽样和贝叶斯推理实现在线估计,目前已广泛用于非线性、非高斯条件下的参数估计和状态估计。其基本思想是根据系统状态向量的经验条件分布在状态空间产生一组随机样本,这些样本称为粒子,根据量测条件不断的在线调整粒子的位置和权重,然后用调整后的粒子修正起初的经验分布。通常对于一般的非线性系统,往往很难直接得到后验概率分布[5]。因此,标准的PF通常选用先验概率密度为重要性密度函数(即建议分布函数)。因此PF的性能即决定于所选择的建议分布函数的好坏。

另一方面,由于标准的PF的建议分布函数为先验概率密度函数,使重要性密度函数与直接从真实后验概率密度函数抽样得到的分布偏差较大,因此,经过几次迭代后粒子的权重集中到少数粒子上,而对后验估计几乎不起作用的粒子占用了大量的计算,结果就是后验概率分布无法用得到的粒子表示,这就是PF的退化问题。克服退化现象有效方法之一就是选取合适的重要性密度函数。

文献[6]对转移先验分布、似然函数以及最近的观察数据和噪声统计特性综合考虑来产生建议分布,提出了混合退火粒子滤波算法HAPF(The hybrid annealed particle filter)。文中实际应用的是自适应算法,本文在此基础上提出了一种基于模糊自适应算法的粒子滤波算法,称之为模糊自适应混合退火粒子滤波算法FAHAPF(The fuzzy adaptive hybrid annealed particle filter)。

1 粒子滤波算法

PF算法[7,8]就是对样本点进行求和运算以代替积分运算,用一个经验概率分布来近似表述状态概率密度分布,如下:

$\hat{p} (x_{0 ∶ k} | z_{1 ∶ k}) = \frac{1}{Ν_{s}} \sum_{i = 1}^{Ν_{s}} δ_{x_{0 ∶ k}^{i}} (d x_{0 ∶ k})$ (1)

式中, $x_{0 ∶ k} \overset{Δ}{=} {x_{0}, x_{1}, \dots, x_{k}}$ ,表示到第k 步时的状态向量, $z_{0 ∶ k} \overset{Δ}{=} {z_{0}, z_{1}, \dots, z_{k}}$ 表示到第 k 步时观测值向量; $p (x_{k} | z_{k - 1})$ 表示 z 观测条件下x 的概率密度,通常情况下,难以直接从 $p (x_{k} | z_{1 ∶ k})$ 抽样得到样本。这里引入一个已知概率密度分布函数 $q (x_{0 ∶ k} | z_{1 ∶ k})$ ,这个分布是容易抽样的,即为重要性函数。如何选择 $q (x_{0 ∶ k} | z_{1 ∶ k})$ 至关重要,选择的原则就是使得重要性权重的方差最小[7,9]。

由于标准的PF算法选择先验概率密度作为重要性函数,从 $q (x_{0 ∶ k} | z_{1 ∶ k})$ 中抽取Ns个粒子,当接受到新的观测值时,实时更新每个粒子的权值。就在这个更新过程中产生了粒子的退化问题。为了解决退化问题引入重采样的方法。重采样后,更新概率密度函数可以表示为:

$p (x_{k} | z_{1 ∶ k}) \approx \sum_{i = 1}^{Ν_{s}} ω_{k}^{i} δ (x_{k} - x_{k}^{i})$ (2)

PF具体的实现步骤如下:

Step1 初始化k= 0,采样x $_{0}^{i}$ ～p(x0),这里根据p(x0)的分布抽样得到x $_{0}^{i}$ ,i=1,2,…,Ns。

Step2 重要性权值计算。设定k:=k+1,采样 $x_{k}^{i} ~ q (x_{k} | x_{0 : k - 1}^{i}, z_{0 ∶ k}), i = 1, 2, \dots, Ν_{s}$ 。

计算重要性权值如下:

$ω_{k}^{i} = ω_{k - 1}^{i} = ω_{k - 1}^{i} \frac{p (z_{k} | x_{k}^{i}) p (x_{k}^{i} | x_{k - 1}^{i})}{q (x_{0 ∶ k}^{i} | x_{0 : k - 1}^{i}, z_{0 ∶ k})} i = 1, 2, \dots, Ν_{s} (3)$

归一化重要性权值:

$ω_{k}^{i} = ω_{k}^{i} / \sum_{i = 1}^{Ν_{s}} ω_{k}^{i}$

Step3 重采样。x $_{k}^{i}$ 从粒子集{x $_{0 ∶ k}^{i}$ } $_{i = 1}^{Ν_{S}}$ 中根据式(3)得到的权值,重新采样得到新的Ns个样本点{x $_{0 ∶ k}^{i}$ } $_{i = 1}^{Ν_{S}}$ ,并重新分配粒子权值: $ω_{k}^{i} = ω_{k}^{i} = \frac{1}{Ν_{s}}$ 。

Step4 状态估计:

$\hat{x}_{k} = \sum_{i = 1}^{Ν} ω_{k}^{i} x_{k}^{i}$ (4)

方差估计: $p_{k} = \sum_{i = 1}^{Ν_{s}} ω_{k}^{i} (x_{k}^{i} - \hat{x}_{_{k}}) (x_{k}^{i} - \hat{x}_{_{k}})^{Τ}$ (5)

Step5 根据具体应用,判断算法是否结束,若是,则终止本算法;若否,则返回Step2。

2 模糊自适应混合退火粒子滤波算法

混合退火粒子滤波[6]的基本思想是:首先将状态向量分解成两部分,然后建议分布采样样本分别选择为转移先验密度和后验概率密度。与后验建议分布相比,混合建议分布具有诸多优点如:权值更新容易、计算简单等。另外,最近得到的量测信息也没有被混合建议分布丢失,因此,其重要性权值具有更小的方差。由于依然是由用先验分布来产生表征状态的粒子来表征混合重要性函数,因此,仍然存在建议分布与似然分布存在较大偏差的问题。为此,在利用状态噪声和量测噪声统计特性之间的关系,引入了退火因子来解决这一问题。

在文献[6]中应用的是基于过程特征参数的自适应控制,实际上应用的是基于规则的自适应算法。本文根据文献[6]中给出的规则,引入模糊推理系统FIS(Fuzzy Inference System),得到形成模糊自适应混合退火粒子滤波算法,即FAHAPF算法。其优点是模糊系统根据输入的变化特征做出相应的决策,给出输出,不需要在线辨识被控对象的精确模型。这样模糊算法的引入,利于提高跟踪精度,降低计算量。

2.1 混合退火建议分布

将状态空间模型中的参数向量分解为两部分,即x={x1,k,x2,k},且可以产生服从 $p (x_{2, k} | x_{2, k - 1}^{(j)})$ 和 $p (x_{1, k} | x_{2, k}^{(j)}, x_{0, k - 1}^{(j)}, z_{0 ∶ k})$ 分布的样本,则可以采用以下形式的建议分布:

$q (x_{k} | x_{0, k - 1}^{j}, z_{0 ∶ k}) = p (x_{1, k} | x_{2, k}^{(j)}, x_{0, k - 1}^{(j)}, z_{0 ∶ k}) \times p (x_{2, k} | x_{2, k - 1}^{(j)})^{β}$ (6)

式中, $q (x_{k} | x_{0, k - 1}^{j}, z_{0 ∶ k})$ 为重要性概率密度; $p (x_{1, k} | x_{2, k}^{(j)}, x_{0, k - 1}^{(j)}, z_{0 ∶ k})$ 为条件概率后验密度 $p (x_{2, k} | x_{2, k - 1}^{(j)})^{β}$ 为转移概率密度;x $_{2, k}^{(j)}$ 是采自 $p (x_{2, k} | x_{2, k - 1}^{(j)})$ 的样本。由于转移先验密度与似然函数之间的关系由状态噪声统计特性∑d和量测噪声统计特性∑v间的关系决定,因此,建议分布函数的可根据这个关系来生成。式中的β称为退火因子,由状态噪声统计特性∑d和量测噪声统计特性∑v间关系决定。这时得到的重要性权值为:

$ω_{n}^{(j)} = ω_{n - 1}^{(j)} p (y_{n} | x_{2, n}^{(j)}, x_{0, n - 1}^{(j)}, y_{0 : n - 1}) \times p (x_{2, n}^{(j)} | x_{2, n - 1}^{(j)})^{α}$ (7)

式(6)和式(7)的详细推导请参见文献[6]的附录A。这里α= 1-β且0<<β<<2。退火参数α的选择原则为[6]:

1) 当∑d<∑v时,先验分布的图形大部分位于似然函数左侧,令0<β< 1 可使先验函数的形状更为平坦;

2) 当∑d≈∑v时,先验分布函数的图形大部分与似然函数图形重叠,令β= 1;式(7)退化为标准的混合重要性重抽样滤波;

3) 当∑d>∑v时,先验分布函数图形大部分位于似然函数右侧,令1<β<2。

2.2 模糊推理系统

根据上面的混合退火建议分布定义如下的模糊自适应混合退火粒子滤波算法的FIS,这里定义状态噪声统计特性∑d和量测噪声统计特性∑v的比值为b,称为调节因子,表示为:

$b = \frac{\sum_{d}}{\sum_{v}}$ (8)

可以通过b值来调节β的取值,当先验函数的大部分支撑域与似然函数重叠时,即∑d≈∑v时,b≈1,即β≈1;当先验分布的支撑域大部分位于似然函数的平坦区之外,即∑d< ∑v时,b<1,此时β较小(0<β< 1);先验函数较之于似然的尖峰来讲是平坦的,即∑d>∑v时,b<1,此时β较大(1< β< 2)。定义模糊子集 equal表示在1附近,more表示基本大于1 ,less表示基本小于1 ,调整系数β的FIS规则如下:

IF b∈equal then β∈equal

IF b∈more then β∈more

IF b∈less then β∈less

这里,b和β的隶属度函数分别如图 1和图 2所示。解模糊化方法选用中心法,FIS为单输入单输出系统,用单输入单输出模糊推理模型。

2.3 模糊自适应混合退火粒子滤波算法

FAHAPF算法的具体步骤为:

Step1 初始化,k=0。

由式(8)确定b,根据FIS确定退火因子β的值和建议分布。

Step2 重要性权值计算。

两个子状态的建议分布抽取样本,然后根据式(7)计算样本权值。然后对重要性权值进行归一化: $_{k}^{i} = \frac{ω_{k}^{i}}{\sum_{i = 1}^{Ν_{s}}} ω_{k}^{i}$ 。

Step3 重采样。

x $_{k}^{i}$ 从粒子集{x $_{0 ∶ k}^{i}$ } $_{i = 1}^{Ν_{S}}$ 中根据重要性权值ω $_{k}^{i}$ 重新采样得到新的Ns个粒子的集合{x $_{0 ∶ k}^{i}$ } $_{i = 1}^{Ν_{S}}$ ,并重新分配粒子权值: $ω_{k}^{i} = ω_{k}^{i} = \frac{1}{Ν_{s}}$ 。

Step4 状态估计:

$\hat{x}_{k} = \sum_{i = 1}^{Ν} ω_{k}^{i} x_{k}^{i}$ (9)

方差估计:

$Ρ_{k} = \sum_{i = 1}^{Ν_{s}} ω_{k}^{i} (x_{k}^{i} - \hat{x}_{_{k}}) (x_{k}^{i} - \hat{x}_{_{k}})^{Τ}$ (10)

Step5

判断k时刻是否为目标的最后时刻,若是,则算法结束,若否,则令k:=k+1,返回Step2。

上述结束条件要根据具体问题判断是否为目标最后时刻,如在列车组合定位中,则以列车到站关机为最后时刻。在招投标评标中以选中最佳单位为结束条件[10],在故障检测中以合理定位为结束条件[11]。

3 数值仿真与结果分析

本文选用纯角度跟踪模型BOM(Bearing Only Model)进行FAHAPF性能分析,这是评测PF滤波器性能时常用的一个基准[4]。下面用HAPF指文献[6]提出的混合退火粒子滤波算法,FAHAPF指本文提出的模糊自适应混合退火粒子滤波算法。

BOM模型的状态模型和观测模型如下:

xn=Φxn-1+ΓWnn=1,2,…,N (11)

$z_{n} = \tan^{- 1} (\frac{y_{n}}{x_{n}}) + v_{n}$ (12)

其中:

在BOM模型中,vx与vy的现在状态只与前一时刻的状态有关,而x,y与vx与vy的状态和自身状态相关,变化较为复杂,并且x和y决定着观测值。初始状态为xk=[4.5,0.5,4.5,0.5]T,进行演化操作时,不同算法的跟踪效果见图3所示。粒子数分别为100、500和1000时的均方根误差(RMSE)比较,如表1所示。

根据上述的仿真结果可以判断,在BOM模型中FAHAPF的跟踪精度要高于HAPF算法。

4 结语

本文在以往研究的基础之上将FIS引入的混合退火粒子滤波算法中来,得到的FAHAPF算法。由于采用了FIS系统根据状态噪声统计特性∑d和量测噪声统计特性∑v间的关系确定调节因子b。再根据b由FIS系统调节退火因子β,使得系统机动性更强,降低了HAPF算法的计算量,提高了跟踪精度在收敛速度和跟踪误差方面有了明显的提高。通过仿真验证了本算法是有效的。

参考文献

[1]朱志宇.粒子滤波算法及其应用[M].北京:科学出版社,2010.

[2]Kotecha J H,Djuric P M.Gaussian particle filtering[J].IEEE Trans-actions on Signal Processing,2003,51(10):2592-2601.

[3]胡士强,敬忠良.PF算法综述[J].控制与决策,2005,20(4):361-365.

[4]Gordon N J,Salmond D J,Smith A FM.Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J].IEEE Proceedings-F,1993,140(2):107-113.

[5]Doucet D,Godsill S,Andrieu C.On sequential Monte Carlo samplingmethods for Bayesian filtering[J].Statistics and Computing,2000,10(3):197-208.

[6]杜正聪,唐斌,李可.混合退火粒子滤波器[J].物理学报,2006,55(3):999-1004.

[7]Liu J S,Chen R.Sequential Monte Car lo methods for dynamical sys-tems[J].Journal of the American Statistical Association,1998,93(5):1032-1044.

[8]胡洪涛,敬忠良,李安平等.非高斯条件下基于PF的目标跟踪[J].上海交通大学学报,2004,38(12):1996-1999.

[9]Liu J S,Chen R.Blind deconvolution via sequential imputation[J].Journal of the American Statistical Association,1995,90(2):567-576.

[10]张晓宇,胡士强,梁国壮.粒子滤波算法在评标中的应用[J].河北科技大学学报,2008,29(4):341-346.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处