混合型算法范文

混合型算法范文（精选12篇）

混合型算法 第1篇

物联网的出现,改变了传统的网络信息传输的方式,并将其覆盖范围延伸到了更为广泛的物理世界,因此得到了世界各国的广泛关注。我国已持续数年将物联网发展列为国家发展规划之中,由此可见其重要性。而无线传感器网络(WSN)则是物联网中的关键组成部分,属于外延的感知层,负责监测物理世界中的各类信息,并将其通过节点的不断跳转传输至远端,因此可以将WSN看作整个物联网体系的神经末梢,其性能的优劣对物联网的运转质量产生了直接且重要的影响。

出于布设成本和维护成本的考虑,WSN基本都属于自组网络,即在该网络中并不存在独立的路由设备和相关的服务器,而是将路由查询工作分摊到各个通信节点来完成,这使得WSN的路由协议明显有别于其他网络,如何在节约能耗的前提下充分利用节点群进行协调工作,是该领域内研究的热点。

人工智能技术在大规模解集的快速收敛问题方面具有明显的计算优势,而在WSN庞大的节点群内找到一条快速有效的通信信道,同时兼顾到诸如节点能耗均摊等约束条件的影响,正属于该类问题的范畴。因此,采用智能算法来对WSN的路由查询进行优化,是非常合适的。

2 WSN的基本构成与特点

从结构上划分,可将WSN分为三个主要构件:①传感器单元,负责对物理世界中的各种信息进行采集和分析;②控制器,用来对采集到的数据信号进行处理和整定③无线收发装置,遵循不同的无线通信协议(如IEEE802.15.4协议),将数据通过存储转发的方式,经过一系列的节点跳转,传输至远端。图1为一个典型的利用WSN搭建监控网络的结构图。

WSN以其特殊的组网方式和路由查询机制而同其他网络差异较大,这使得WSN在工农业、军事、医疗、社区安全、智能家居、环境监测等领域内得到了广泛的应用,其特点有以下几条:

1)网络设备成本较低,无线传感器节点本身价格很低,即使可以大规模使用也不会带来高昂的布设成本,并且节点具有一定的数据融合能力,使得整个网络可以维持一个较低的能耗水平下正常运转。

2)自适应性强,WSN属于自组织网络,即网络中的节点可以无需其他控制设备而自己独立适应网络拓扑,当某节点因能量耗尽或出现故障而无法工作时,会导致网络中出现“黑洞”,此时其他节点可以在不需要任何人工干预的情况下自动搜索替代路由,完成网络的修复工作。

3)节点本身就具有计算功能,可完成一定计算量的分析工作,因此可就近利用节点来实现较为复杂的监测以及分析任务,从而使得数据的准确性和有效性大大提高了。

3 基于混合型智能算法的WSN路由优化

3.1 蚁群算法

蚁群算法从自然界蚁群行为模式演变而来。蚁群在外出寻找食物时,其行动路线是随机分布的,而当其中某只蚂蚁找到食物回返时,会在其行动路线上留下信息素,附近的蚂蚁根据信息素迅速汇集成一条蚁线,并在此轨迹都留下自己的信息素,于是后续的蚂蚁根据不同轨迹上信息素浓度的高低,来判断路径的优劣。这是一种非常有效的收敛算法,尤其适合运用在大规模节点群中进行路由查找,因此将此策略应用到在WSN路径优化过程中,为各个节点之间的链路设定度量值,模拟信息素,最终通过度量值的高低来判断出最优化WSN路由。具体优化策略如下:

1)对于某个已铺设好的WSN节点群,设蚁群数量为m,dij为节点i和j之间距离,τij为t时刻(i,j)间信息素浓度。

2)设某蚂蚁k所经过的节点轨迹为tabuk(i=1,2,3...m),该轨迹可动态改变,以应对蚁群信息素的变化。

3)当某条路径上的信息素浓度超过原有路径时,还需要考虑到局部峰值问题,因此并不能保证这条路径一定优于原有路径,应采用转移概率pkij(t)来决定是否采用,而此概率同信息素浓度的变化相关,具体关联由式(1)给出:

其中,ηij为路径(i,j)描述了节点i和j之间的可达概率;α和β表示信息素权值,随着时间的推移而下降,allowedk为蚂蚁k允许达到的节点群。于是有:

当路由推进到某个节点上的时候,下一步的节点选择即可根据信息素浓度来判别,如式(3):

4)信息素的浓度必须根据网络实际状况而灵活改变,如由于某节点能量耗尽而导致某条优先级高的路由作废,或由于某个较优节点承担通信负荷较大而导致处理时延过长。因此在算法中需要及时体现信息素浓度的变化,在t+n时刻,路径(i,j)执行公式(4):

ρ为信息素残留因子,表示之前的信息素的挥发程度,若某条较优路由长时间没有新的信息素增加的话,则其优先级别会逐渐下降;Δτij为浓度增量,以描述在的一段时期内信息素的变化幅度。

通过对蚁群算法在WSN路由优化中的应用模式可以看出,该算法适合在大规模解空间中根据动态变化的信息素查询到目前最符合网络状况的最优路由,但其本身也有一些缺陷,例如其收敛速度较慢等。因此本文提出将遗传算法同蚁群算法相结合,形成一种新型的混合型智能优化算法,利用遗传算法快速收敛的特点加快WSN路由查询速度,以提高网络系统的响应速度。

3.2 遗传算法设计

1)适应度函数

适应度函数是遗传算法中为某个被控对象建立的数学模型,通过对该模型的调节,达到最优的控制效果,本文参阅了大量文献,确定适应度函数为:

其中,i+1为选定的下一跳节点,再加上节点能耗这一约束条件,故设Eαi+1为节点i+1的剩余能量,nx表示某条路由x所包含的跳转次数。

2)选择操作

适应度函数即为算法判别下一代群体选择的依据,通过该函数实现每代的筛选,最终实现优化收敛。遗传算法在这方面表现优异,可将收敛时间大大压缩。在每代的群体节点中,个体节点xi按照公式(7)给出的选择函数进行筛选:

3)交叉算子

虽然遗传算法收敛较快,但容易陷入局部峰值而导致收敛失败,因此必须增加群体的多样化程度,交叉运算承担了这一任务。该步骤随机地从种群中选择两个个体,然后对个体中对应位置的参数进行随机交换。如,设两个个体为X1和X2,:

在进行交叉操作后,得到的新个体为:

综合上述可知,混合计算智能的WSN路由工作流程如图2所示。

4 总结

经过仿真验证,新的混合型智能算法表现出了较好的性能水平。在平均时延方面,当节点群规模较小时,本算法并未体现出明显优势,但当模拟WSN节点群规模超过200个节点以上时,该算法明显耗时更少,因此可以证明遗传算法的快速收敛性能同蚁群算法的大规模搜索优势得到了有效的结合。相信随着人工智能技术的不断发展,会有更多的研究成果同WSN路由优化相结合,进一步提高WSN的工作效率。

摘要：目前无线传感器网络(WSN)在我国发展迅速,作为物联网感知层的重要单元,无线传感器网络承担着信息采集和传输的双重任务。无线传感器网络属于自组网络,因此其路由协议同无线局域网有所区别。如何在保障数据传输质量的前提下,加快路由查询过程,减少网络通信时延,以提高该类型网络的实时性,是近年来网络通信领域研究的热点。该文提出将蚁群算法同遗传算法相结合,形成一种新的混合型智能算法,并将其用以无线传感器网络的优化工作中,取得了较好的效果,具有一定的参考价值和推广意义。

关键词：WSN路由协议,混合型算法,优化

参考文献

[1]孙扬,何建忠.WSN自适应负载均衡集簇分层路由协议[J].计算机工程与设计,2013(2):423-427.

[2]何永刚.无线传感网路由空洞问题的研究[D].苏州:苏州大学,2010.

软件安全中混合加密算法 第2篇

【关键词】网络安全;加密;密码

一、前言

随着计算机网络技术的飞速发展，计算机系统的安全问题也越来越引起世界各国的广泛关注，信息网络的大规模全球互连趋势，以及人们的社会生活对计算机网络依赖性的与日俱增，使得计算机网络的安全性成为信息化建设的核心问题。

二、网络安全概况

1.网络安全的基本概念

一种多目标混合进化算法的研究 第3篇

摘 要：针对遗传算法的不足，提出将禁忌搜索方法、免疫算法、遗传算法融和的多目标混合进化算法。该算法引入禁忌搜索法，避免了传统遗传算法早熟现象的发生；引入基于浓度的自适应变异操作，克服算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免最优解的丢失，通过ZDT系列测试函数的仿真实验并与NSGA-Ⅱ算法进行比较，验证了算法的有效性。

关键词：多目标优化；遗传算法；多目标混合进化算法；ZDT测试函数

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

Abstract：A multiobjective hybrid evolutionary algorithm （MHEA） was put forward aiming at the shortcomings of the traditional genetic algorithm， which combines taboo search algorithm， immune algorithm and genetic algorithm. This algorithm avoids the premature phenomenon of the traditional genetic algorithm through importing the taboo search algorithm. The operator of adaptive mutation based on the density overcomes the problem of long solving process caused by the constant mutation probability and bad diversity of the solution. Then external elite set was introduced to avoid the loss of the optimal solution. Finally the simulation of ZDT series test functions and the comparison with NSGA-Ⅱ algorithm verifies the effectiveness of the algorithm.

Key words：Multiobjective optimization；genetic algorithm； MHEA； ZDT test functions

2.3 算法简介

遗传算法[4，5]因其高度的并行处理能力、强鲁棒性和全局搜索能力而被广泛地应用于诸多领域。理论上遗传算法依“概率1”收敛于问题的最优解，然而实践应用中，遗传算法会表现出早熟现象、局部寻优能力较差等不足，所以一些常规遗传算法并不一定是针对某一问题的最佳求解方法。

禁忌搜索法[6]具有灵活的记忆功能和藐视原则，并且在搜索过程中可以接受劣解，因而具有较强的爬山能力，搜索时能够跳出局部最优解，从而增强获得更好的全局最优解的概率。但其搜索性能完全依赖于邻域结构和初始解。

免疫算法[7]可以通过细胞的分裂和分化作用，对抗体的产生进行促进或者抑制，体现了自我调节功能，保证了个体的多样性。

由于遗传算法、禁忌搜索法、免疫算法各有优缺点，因此将三种算法相结合，互相取长补短，则可能设计出性能优良的新的全局搜索算法，可以加快算法的收敛性同时提高算法的多样性。

3 多目标混合进化算法（MHEA）

本文引入禁忌搜索法[8]，避免早熟现象的发生，提高了局部搜索能力；采用基于浓度的自适应变异操作，克服了算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免了最优解的丢失，下面介绍算法的实现：

3.1 算法的设计

1）将部分精英集中的个体加入到种群POP0中并进行选择操作，可以提高种群的收敛速度。

2）交叉操作：

由于交叉算子在搜索最优解的进程中是一个破坏性同时也是产生新解的过程，因此遗传算法常常很快收敛到比较好的解，但是往往不能收敛到最优解，本文采用单点交叉算子。

3）禁忌搜索法：利用遗传算法与禁忌搜索法相结合，克服遗传算法早熟和收敛慢的缺点，具体步骤如下：

（1）对选择操作产生的新种群的个体进行禁忌搜索；

（2）查找禁忌表中是否有此个体记录；

（3）如果有，再看是否满足特赦准则；

（4）如果满足特赦准则，再看是否满足收敛准则；

（5）满足收敛准则，继续进行交叉操作，产生新种群，然后转到1）；

（6）如果不满足特赦准则，禁忌表中也没有此个体记录，则放人禁忌表；

（7）继续查看是否满足收敛准则，满足后输出结果，否则进行上述的交叉操作。

4）基于浓度的自适应变异算子

相比变异概率不变情况下，自适应变异更加符合生物遗传规律，有利于提高种群多样性。借用免疫算法中对抗体产生进行促进或者抑制，可以自我调节，从而保证个体多样性的思想，本文提出了一种基于浓度的自适应变异算子。

3.2 外部精英集

由图1可知，最初的精英集由初始群体中适应度最高的个体填充，随后由交叉和变异操作产生的最优个体对精英集进行更新，如果个体的数量超过档案规模，则依据适应度值大小对精英集进行修剪。在种群外设置一个精英集合用于保存种群进化每一步搜索到的非支配解。精英集合的使用将有效防止算法在搜索过程中由于随机因素而丢失最优解，并且能加快算法收敛速度。

3.3 多目标混合进化算法的步骤

（如图1）可描述为：

1）初始化算法的参数（包括种群规模POP、禁忌表及其长度、迭代次数等），随机产生初始群体POP0。

2）计算种群中每个个体的适应度值，并将适应度最高的个体存入精英集1中。

3）将精英集中的部分个体加入到种群中，进行选择操作得到种群POP1。

4）对POP1进行禁忌搜索同时进行交叉操作得到种群POP2，将POP2中适应度最高的个体存入精英集2中。

5）对POP2进行基于浓度的自适应变异操作得到种群POP3，将POP3中适应度最高的个体存入精英集3中。

6）更新精英集，如果个体数量超过档案规模，则对精英集进行修剪。

7）如果满足终止条件，执行步骤8，否则，转到步骤3。

8）输出最优解。

4 仿真实验

4.1 仿真测试

为了验证MHEA算法解决多目标优化问题的性能优劣，将该算法与目前解决多目标问题较好的NSGA-Ⅱ[10]算法进行比较分析。本文选取一组具有不同特征的benchmark问题ZDT1、ZDT3和ZDT6作为测试函数，其中ZDT1具有Pareto最优前沿，ZDT3具有非连续Pareto最优前沿，ZDT6具有非凸性且非均匀Pareto最优前沿。

测试过程中，MHEA算法和NSGA-Ⅱ算法均采用实数编码，浓度阈值γ=0.7，交叉概率pm=0.9，变异概率pc=1/n（n为变量个数），种群规模M=200，迭代次数gen=300。在同一台计算机上分别独立运行20次，从中选取最优结果进行比较，试验结果如图所示。

4.3 实验结果分析

由表1可知，所提算法MHEA在优化测试函数ZDT中的收敛性能、分布性能及多样性均优于算法NSGA-Ⅱ，说明算法引用禁忌搜索法及基于浓度的自适应变异算子是可行有效的，它能够提高收敛性，增加群体的多样性，但MHEA的平均运行时间却较长，这是它在提高算法搜索性能的同时所付出的代价。

5 结 论

本文有效的结合了遗传算法、禁忌搜索法和免疫算法的优点，提出了一种多目标混合进化算法，提高了收敛性，同时保证了多样性。通过仿真实验验证了算法的有效性。

参考文献

[1] 雷德明，严新平.多目标智能优化算法及其应用[M].北京：科学出版社，2009：31-33.

[2] 张勇德，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策，2005，20（2）：170-173.

[3] COELLO COELLO C A，PULIDO G T.Handing multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

[4] GOLDBERG D E.Genetic Algorithm in Search， Optimization and Machine Learning[J].NJ： Addtion Wesley，1989.

[5] 王娜，向凤红，毛剑琳.改进的自适应遗传算法求解0/1背包问题[J].计算机应用，2012，32（6）：1682-1684.

[6] 张文化，刘素华，侯惠芳.一种用于特征选择的禁忌搜索算法[J].计算机应用于软件，2010，27（5）：125-127.

[7] 崔逊学.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能，2001，14（3）：291-296.

[8] B T G TAN，S M LIM.Automated Parameter Optimization for Double Frequency Modulation Synthesis Using the Genetic Annealing Algorithm[J].J Audio Eng Soc.1996，44（1）.

[9] 王洁，高家全.一种新的的免疫遗传算法及应用[J].计算机应用与软件，2010，27（12）：89-91

[10]Deb K，Prata A，Agarwal S，Meyarivan T.A fast and elitist multiobjective geneticalgorithm： NSGAⅡ[C].IEEE Transactions on Evolutionary Computation， 2002， 6 （2）：182-197.

[11]郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.

基于自由落体算法的混合遗传算法 第4篇

由于存在早熟收敛现象,遗传算法有可能得到的只是一个满意解,而非全局最优解,为弥补这个缺陷,已出现了多种改进遗传算法,例如:小生境遗传算法、自适应遗传算法、并行遗传算法、混合遗传算法等。

混合遗传算法就是将遗传算法与其它启发式的搜索算法相结合,从而弥补单一优化方法的某些不足之处。由于GA具有开放式的结构,与问题的关联性不大,很容易和其他算法进行结合。比较常见的混合遗传算法有:模拟退火遗传算法、免疫遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法等。本文中是将遗传算法与自由落体算法相结合进行求解二维装箱问题。

2 二维装箱

二维装箱问题有不同的描述方法,本文讨论条形装箱问题(strip bin packing)。描述是:给定n个矩形,设其长和宽分别为Li和Wi(i=1,2..n),现有宽度一定,高度不限的矩形箱子(假设矩形物体的宽度均不大于箱子的宽度),则如何放置这些矩形物体,使放完这些物体后,放置最后物品的总计高度最小,这里假定物体不能重叠和90度旋转圈。

3 算法设计

3.1 自由落体算法简介

自由落体算法也称为自由下坠算法,它是一种典型的不分层算法,其基本思想是:对于每一个物体,在装箱的时候寻找位置最低的合适区间装入。显然这是一种较好的装箱模式。但它仍然存在一些缺点,比如对于高度相同的各个方案,算法没有指出该如何选择。

针对上述算法存在的问题,本文对其进行了改进,其具体描述如下:

第一、从左到右进行扫描,对于扫描得到的各区间进行判断:如果该区间的宽度小于物品的宽度,则依次与右侧区间进行合并,直到合并的区间的宽度大于等于物品的宽度,并取所合并区间的最大的高度与物体的高度之和为合并后区间的高度,类似的,该区间也依次与左侧区间进行合并;第二、所得到的所有区间组中,寻找高度最小的区间组,如果高度相同,优先使用浪费面积最小的方案。

3.2 基于改进后自由落体算法的混合遗传算法

这里把新自由落体与遗传算法相结合,来解决条形装箱问题。

1)染色体的编码方法

假设k个箱子的编号分别为B1,B2,,Bk,n件物品要装入这k箱子中,要说明的是,有时几件物品可以装入同一个箱子中,所以不一定要全部用完这k个箱子,各个物品ui(i=1,2,,n)所装入箱子之编号的顺序排列就构成该问题的染色体编码,即我们使用的是等长度的字符代码编码方法,例如B1B3B4B4B1B2B2B3表示第1,5号物品装入箱子B1中,第6,7号物品装入箱子B2中,第2、8号物品装入箱子B3中,第3、4号物品装入箱子B4中。初始群体可以由B1,B2,B3,B4随机排列产生,由个体的染色体编码串可统计出某一装箱方案用了几只箱子。

2)适应度函数

这里以Max Maxheight-h作为适应度函数,其中Maxheight为较大的常数,h为装箱后的高度,这样保证了装下该物品后,箱子所剩空间为最大的情况。

3)选择

选择操作是建立在群体中个体的适应值的评估的基础上,在本算法中采用按正比与适应值的轮盘赌的方式进行随机选择,为了提高效率,选择轮盘时采用折半查找的方法,这样就能有效地减少比较次数,确保该过程的时间复杂度为0(log n)(n为种群大小)。

4)交叉

交叉是对两个配对的染色体以某种方法相互交换部分基因,从而形成两个新的个体,它是产生新的优良基因的主要方法,但这样会产生无效染色体。为了避免这种情况,需要对交叉出的结果做特殊的处理。在这里,用Grefenstette提出“巡回路线编码方法”的基本思想进行交叉操作,具体实施如下:

假设有十个物品为ui(i=1,2,...,10),欲装入一个大箱子,我们对装箱顺序进行编码,设现有如下两种装箱方案:

A1=(2,6,1,3,4,8,10,5,9,7)

A2=(1,5,8,3,2,7,9,6,4,10)

方案1表示根据自由落体算法装入物品的顺序为2,6,1,3,4,8,10,5,9,7;方案2表示根据自由落体算法装入物品的顺序为1,5,8,3,2,7,9,6,4,10。

下面我们对上述两种装箱方案进行编码,以A1方案为例,在此方案中8号物品装箱顺序排在了第六位,在此之前编号为2、6、1、3、4的物品已装入箱中,物品编号均小于8,即共五个数均小于8,故我们对其编码为:8-5=3。设方案A1编码后为A1',方案编码后为,按照此法得:

A1'=(2,5,1,1,1,3,4,1,2,1)

A2'=(1,4,6,2,1,3,3,2,1,1)

然后,对红题字部分进行交叉,即A1'中的1和A2'中的4进行交叉,得两种新的编码方案,设为T1、T2。则:

T1=(2,5,6,1,1,3,4,1,2,1)

T2=(1,4,1,2,1,3,3,2,1,1)

然后对其进行解码,便得到另外两种装箱方案:

T1'=(2,6,8,1,3,7,10,4,9,5)

T2'=(1,5,2,4,3,8,9,7,6,10)

可以看出采用这种方法,不管在哪个位置交叉,交叉后每一个装箱方案中物品没有重复。

5)变异

这里我们采用基本位变异的方法,即随机在一个染色体中取出一位,进行改变,但应该保证产生的染色体是一个有效染色体,因此该位的取值应该有一定的范围,它只能在(1,2,3,...,n-1-i)中选取。

4 实例检验

论文参见相关的资料,随机摘取一组数据进行验证:a(15,4),b(2,6),c(5,6),d(9,6),e(13,6),f(16,5),9(1,4),h(5,4),i(9.4),i(13,2),k(16,2),1(l,2),m(4,2),n(8,2),o(12,1)。(其中箱子宽度为20,物体第一个数据为宽度,第二个数据为高度)

交叉率:Pc=0.8;变异率:Pm=0.1;代数:Gen=40

采用改进后的自由落体算法与遗传算法相结合,可得到较优秀的装箱结果,装箱顺序为j m h a b g f k n d i e l o c,高度为26,装载率为89.9%(阴影为浪费面积),如图1所示。

5 结束语

二维装箱问题在工业领域有着广泛的应用,例如:切割问题,服装裁剪,装运问题,电路板设计问题,排版问题等。一种好的解决方案,能够节约生产成本,提高效益。遗传算法由于存在早熟收敛现象,有可能得到的解决方案并不是全局最优解,为此,本文利用基于自由落体算法的混合遗传算法进行求解,从而得到最优解。

参考文献

[1]姜义东,查建中,何大勇.集装箱装载矩形货物的布局研究仁[J].铁道学报,2000.

[2]邓向阳,等.算法分析与设计[M].北京:冶金工业出版社,2006.

[3]E G Coffman,M R Garey,D S Johnson.Approximation Algorithms for Binpacking:A survey[A].In:D Hochbaumed.Approximation Algorithmsfor NP Hard Problems[C].Boston:PWS Publishing,1996,46-93.

[4]Keqin Li,kam Hoi Cheng.A heuristic algorithms for On Line Packing in Three Dimensions[J].Journal of Algorithms,1992,(13):819-828.

[5]Gehring H.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research,1990,44(2):277-288.

[6]赵素芬.几何布局问题及其应用(一)[J].呼和浩特科技,1993,(2),12-19.

[7]武晓今,朱仲英.二维装箱问题的一种实现方法[J].微型电脑应用,2003.

[8]Yanasse H Hetal.Two-dimensional cutting stock with multiple stock sizes[J].Journal of Operationa Research Society,1991,42(8):673-683.

混合型算法 第5篇

混合免疫算法求解对称TSP的仿真分析

针对对称TSP,将局部搜索方法与免疫算法相结合,构造了混合免疫算法.数值实验结果表明,混合免疫算法求解对称TSP是可行的.;新的算法既具有局部搜索方法较快的收敛速度和较强的局部寻优能力,又具有免疫算法的全局收敛特性.

作 者：张全兴 王海莉 Zhang Quanxing Wang Haili 作者单位：长安大学,理学院,陕西,西安,710064刊 名：宁夏大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF NINGXIA UNIVERSITY(NATURAL SCIENCE EDITION)年，卷(期)：29(3)分类号：O224关键词：免疫算法 混合免疫算法 局部搜索方法 对称TSP

混合型算法 第6篇

关键词：视频处理；背景建模；混合高斯模型；历史背景

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

背景减除是自动视频对象分析的一项关键技术，他在智能视频监控等领域中有着非常广泛的应用。对视频场景进行背景建模，将存储好的背景模型和新观察到的图片进行背景减除来提取运动目标是较为常用的方法＼[1＼]。原理虽然简单，但是真实世界中像素在时域和空域中的复杂变化，使得背景建模变得很困难。比如阴影检测、亮度的缓慢或剧烈改变等都是现在背景建模的难点＼[2-3＼]。近年来，国内外学者提出了许多建立背景模型的方法，包括针对含有纹理的动态场景，采用一种新的模糊色彩直方图特征来减弱运动背景造成的色彩改变＼[4＼]；为每一个像素点建立一个由4层前馈神经网络组成的背景模型＼[5＼]；结合颜色、梯度、不同特征来构建背景模型，采用支持向量机来进行背景分类＼[6-7＼]等。

湖南大学学报（自然科学版）2015年

第10期肖进胜等：一种基于历史背景的混合高斯背景建模算法

高斯模型是近年发展起来并得到广泛应用的一种技术。Stauffer等＼[2＼]提出利用混合高斯模型来建立背景模型，在每帧中对各个像素点建立由多个高斯分布组成的背景模型。自此以后，该方法以其能较为鲁棒地描述多峰分布的背景而被广泛应用，但其仍然具有处理速度较慢、无法应对突变背景等缺点＼[8＼]。此后的研究者对混合高斯背景建模方法做了各种改进。Zivkovic Z＼[9＼]针对自适应高斯混合模型的个数和参数问题进行了改进，利用最大似然估计进行高斯模型个数的选择。文献＼[10＼]考虑到全局抖动造成的运动目标检测不准确的问题，提出基于分区灰度投影稳像的高斯背景建模算法。文献＼[11＼]针对亮度场景的变化，建立亮和暗不同的模型进行亮度场景变化的检测和估计。文献＼[12＼]为了解决场景中存在的突变，提出基于记忆的混合高斯模型（Memory-based GMM， MGMM）的前景检测算法，取得了很好的检测效果，但是该算法中每个像素都要经过瞬时记忆、短时记忆和长时记忆3个空间的传输和处理，影响了算法效率和实用性。上述方法对混合高斯模型的修改多数集中在提高模型的处理效率与收敛速度方面。当现有的混合高斯建模算法应用到实际场景中时，若背景场景重复性出现时，如被重复性的遮挡与显露，受模型学习速度的影响，重新显露出的背景场景的变化不能被立即学入背景模型中，依然会被检测为前景，从而产生大量误判。

本文针对视频中背景经常重复性地被遮挡与显现的场景（如智能视频监控场景中），提出了一种基于历史背景的混合高斯模型（History Background-based GMM， HBGMM）。经过模型学习，基于历史背景的混合高斯模型对重复出现过的背景具有记忆功能；当重复性背景再次出现时，能及时判决出背景与前景，从而使被误判成为前景的背景快速消融至背景中。

1混合高斯模型原理分析

经典的混合高斯模型＼[2＼]对视频图像中的每一个像素点定义K个状态，其值一般取3～5。若每个像素点的像素值用Xt表示，则对应的概率密度函数可用K个高斯函数来表示：

f（Xt=x）=∑Ki=1ωi，tη（Xt，μi，t，Σi，t）。 （1）

式中：η（Xt，μi，t，Σi，t）为t时刻的第i个高斯模型；ωi，t为时刻t第i个高斯模型的权重，且有K个权重的和为1。 这里假定视频各帧图像中各点的像素值在R，G，B3个颜色通道＼[13＼]是相互独立的，并且具有相同的方差，σi，t为标准差，那么协方差矩阵可以取值为：

Σi，t=σi，t2I。 （2）

其中I为单位阵。所有K个高斯模型首先按照ωi，t由大到小排序，然后从首端选取B个高斯模型作为背景模型。其中B满足：

B=argminb（∑bi=1ωi，t>Thershold）。 （3）

式中：Thershold为预先给定的权重阈值，是用于选择模型个数的阈值，一般取值为0。7～0。9。对于新的一帧图片，若当前图片中点的像素值与其中某个高斯模型的均值和标准差满足：

Xt+1-μi，t<δσi，t。 （4）

则认为该像素值与高斯模型匹配（通常δ设为2～4）。高斯分布的参数采用在线K均值近似算法进行更新＼[9＼]，对于第1个匹配上的高斯模型，更新其所有参数，而对于其他K-1个高斯模型，仅更新权重，权重更新公式为：

ωi，t+1=（1-α）ωi，t+αOi，t+1。 （5）

对于首次匹配的模型，Oi，t+1取1，对于其他模型，Oi，t+1取0。ωi，t和ωi，t+1分别为更新前和更新后的权重。均值与方差更新的公式为：

μi，t+1=（1-α）μi，t+αXt+1； （6）

σ2i，t+1=（1-α）σ2i，t+α（Xt+1-μi，t+1）T×

（Xt+1-μi，t+1）。 （7）

式中：μi，t和μi，t+1分别为更新前后的均值；σ2i，t和σ2i，t+1分别为更新前后的方差；α为学习率，取值为0。002～0。005。如果当前像素点无法与所有模型匹配，就用一个新的均值为Xt+1、高方差和低权重的高斯分布取代尾端的高斯分布。

传统高斯模型应用于复杂的现实环境中时计算复杂，其计算量与所用的高斯模型的个数成正比，而且模型参数难以调整＼[14＼]。同时在有重复性的背景场景出现时，背景点则会因为像素值的突然变化，而被误检为前景点，造成误判。一个理想的背景减除系统应具有一定的自适应能力，其背景模型应可以根据场景的变化自适应地保持与更新背景模型。

2基于历史背景的混合高斯模型

针对经典混合高斯模型的问题，如果在使用混合高斯模型对背景进行建模实现背景减除的过程中，对曾经判断成为背景的模型进行标记，标记其为历史模型。在之后的更新与匹配过程中，对历史模型记录其匹配次数，在一个周期内，若匹配次数超过用户设定门限，则在下次匹配成功之后，额外为该模型增加T倍的α，通过模型的权重降序排列，使其迅速增长至模型队列前端，落入背景模型的背景权重范围内，从而被判决为背景而不是前景。就能够在一定程度上解决前面提到的问题。

本算法对经典的高斯模型改进有以下2点：

1）对历史背景进行标记，以P帧为周期，记录该周期内历史背景的匹配次数，若匹配次数超过用户设定门限N，则在下次匹配成功之后，额外为该模型增加T倍的α。权重更新公式（5）更改为如下所示。

ωi，t+1=（1-α）ωi，t+αOi，t+1+αci，t+1。 （8）

式中：α，ωi，t和ωi，t+1与式（5）含义相同。对于满足历史背景更新条件的模型，ci，t+1取值为T，对于其他模型，ci，t+1取0。这里历史背景更新条件是指：若当前模型被匹配上，且该模型权重处于前景范围，在周期P内匹配次数超过N次。P与N若取值过小，会对图像中的噪声较为敏感；若取值过大，建模算法又无法及时适应视频图像中前景对象与背景的变化，因此，本文中取P为10，N为5。符合该条件的模型，会在原始权重更新的基础上，再加上Tα的新权重。实验表明，当T≥3时，前景过快消融，而当T<2时，对重复背景的处理效果不明显，因此将T设为2。

2）当模型权重小于某一门限时，对于历史模型和非历史模型进行区别处理。非历史模型将会被删除；而历史模型仅将其权重置为0，并不删除。

算法的具体描述如下：

步骤1第1帧时初始化记忆空间，用当前帧的图像像素（Ri，Gi，Bi）创建每像素点的第1个高斯模型，将其权重赋为1，并分配初始方差。

步骤2对每一帧新的图像，将每个像素点的K个模型按权值从大到小排序。根据式（3）从首端选取B个高斯分布作为候选背景模型，Thershold为用户自定义的阈值。

步骤3将新的采样值Xt+1（R，G，B）依次与原有K个高斯模型进行匹配，若δ=3时，式（5）成立，则认为该点匹配当前模型，若匹配上的模型落在步骤2中的B个模型内，则判断该像素点为背景，同时将当前模型标记为历史模型，否则，该像素点为前景点。找到匹配模型后不再寻找其他匹配模型，执行步骤4；若当前点未匹配上任何模型，转步骤5。

步骤4如果找到匹配模型，按照式（8），（5），（6），（7）更新匹配模型的权重、均值和方差，若该模型为历史模型，则记忆其匹配次数。在固定周期内（如10帧），匹配次数超过N次，则权重额外增加T倍的α。其他未匹配模型只更新权重，同时对所有模型按权重进行降序排列。 在模型的权重更新完成后，若该模型的权重小于某给定值αCT，当其未被标记为历史模型时，删除当前模型；否则，只将当前模型权重置为0，不删除该模型。

步骤5如果当前点未匹配上任何模型，按照式（8）更新所有模型的权重。在模型个数未达到用户设定上限时，生成一个新的模型加入模型队列；否则，用这个新模型取代权重最小的模型。同样，最后对所有模型按权重进行降序排列并归一化。

根据上面的模型分析，基于历史背景的混合高斯背景建模算法流程如图1所示。

在传统混合高斯模型更新过程中，引入曾经是背景模型的标记，并根据这一标记，对历史背景模型进行不同的更新处理，则有可能实现记忆背景的作用，在背景重复出现时，避免将其误检为前景。

3实验结果及讨论

为验证本文所提历史模型算法的有效性，在2。4 GHz酷睿i3双核处理器上，VS2005编程环境下，用序列进行了测试，并与传统GMM方法＼[2＼]以及文献＼[12＼]的MGMM方法进行了对比。为保证方法比较的有效性，3种方法基本参数取值相同，分别为Thershold=0。75，ω =α，其中GMM和本文算法K

=5，σ=20；MGMM算法中K=4，N=1，σ=25。

学习率计算方法为：

α=1/（2frame），frame<500；0。002，frame≥500。 （9）

式中：frame为帧数。

图1像素级算法流程图

Fig。1Flow chart of the pixelwise algorithm

为了更好地测试重复性背景问题，在序列“fast move”中叠加一个每隔400帧出现的色块，用该色块来模拟重复出现的运动目标，初始50帧用于模型学习，不叠加色块。色块消失后，由原位置被误检为前景的部分消失所需的帧数来定量判决不同背景建模算法处理重复背景的能力。

图2（a）显示了用于测试的视频原始图像，图2（b）为原始视频叠加色块的效果。图3从左到右依次给出序列分别为608，612原始帧，采用经典GMM方法、文献＼[12＼]的MGMM方法以及本文提出的HBGMM方法的前景检测结果。 表1为3种方法在测试帧中重复出现的色块检测为前景的帧数。

由表1可见，有色方块在视频的51～200帧与601～999帧出现，当其第2次在600帧出现时，由于之前出现过，该像素值曾被学习入背景模型中，此时重新出现的色块应该快速地被吸收入背景，而不应被检测为前景目标。但传统的混合高斯模型经过了12帧才将其吸收成背景，而本文所用方法仅用了8帧。由图3可知，本文算法的检测结果被误检为前景的目标更少，消失速度更快。由此可见，在重复性背景出现时，本文方法能够更快地将其吸引消融成背景，而不会长时间内仍被检测为前景。

图2“Fast move”序列背景变化

Fig。2Background changes in “Fast move”

表13种背景建模方法检测效果对比

Tab。1Comparison of the three background

modeling methods

帧数

实际方块

GMM方法

MGMM

方法

HBGMM方法

51～200

51～81

51～200

51～81

601～999

601～612

201～700

601～608

为了更精确地测试建模算法的效果，本文选用了两段带有真实前景（Ground truth）的视频序列，并采用F1得分来评估检测出的前景与真实前景的相似程度。F1得分的计算方法为：

F1=2prp+r，p=tt+f，r=tt+n。 （10）

式中：F1为得分值；t，f，n分别为正确检测、错误检测和未检测出的前景点个数。检测出的前景点是否正确，可以通过与Ground truth对比得知。F1得分的最高分为1，最低分为0，分值越高表明检测出的前景越准确，建模效果越好＼[12＼]。

“Office”序列中，当人物离开站立位置，其身后的墙壁再次显露出来，根据Ground truth，此时该处墙壁应被检测为背景。因此，对此时视频序列的前景检测结果计算F1得分。图4分别给出了第2 002（上图）和第2 006帧（下图）的前景检测结果。

图3“Fast move”序列前景检测结果

Fig。3 The segmentation results of “Fast move”

图4“Office”序列前景检测结果

Fig。4 The segmentation results of “Office”

由图4可见，本文提出的HBGMM建模算法比GMM算法和MGMM算法能够更快地将重复出现的墙壁吸收为背景。3种建模算法检测结果的F1得分如表2所示。由表2可知，HBGMM算法的F1得分均高于GMM算法与MGMM算法，可见，当重复背景出现时，HBGMM算法检测出的前景更为准确。

表2对“Office”序列3种方法检测结果的得分对比

Tab。2Comparison of score for “Office” sequence

with three methods

帧号

F1

GMM方法

MGMM

方法

HBGMM方法

2 002

0。546 9

0。421 8

0。566 4

2 006

0。525 9

0。415 0

0。548 6

为了进一步测试HBGMM算法的效果，本文选用了另一段室内监控视频“Sofa”，当人物将原本置于沙发上的行李移走时，原被行李遮盖后显露的沙发应被检测为背景。图5显示了在该场景中的两帧画面（第2 471，2 486帧）及相应建模算法的检测结果。表3为该3帧前景检测结果的F1得分。

表3对“Sofa”序列3种方法检测结果的得分对比

Tab。3Comparison of score for “Sofa” sequence

with three methods

帧号

F1

GMM方法

MGMM

方法

HBGMM方法

2 471

0。737 1

0。527 3

0。746 7

2 486

0。782 6

0。658 5

0。784 1

由表3可知，相较于GMM和MGMM建模算法，HBGMM算法的F1得分最高。同时，由图5可知，HBGMM算法在处理重复背景问题时，能够更快地将误检为前景（见重新显露出的沙发部分）的像素点吸收为背景。

图5“Sofa”序列前景检测结果

Fig。5The segmentation results of “Sofa”

4结论

本文在传统混合高斯模型更新过程中，引入曾经是背景模型的标记，并根据这一标记，对历史背景模型进行不同的更新处理。同时，与传统的GMM方法及MGMM方法进行重复性背景的对比实验。结果显示，本文所提出的方法实现了记忆重复背景的功能，从而更快地适应场景的变化，减少前景误判，适用于存在重复性运动场景的建模。

参考文献

[1]BRUTZER S，HOFERLIN B，HEIDEMANN G。Evaluation of background subtraction techniques for video surveillance ＼[C＼]//IEEE Conference on Computer Vision and Pattern Recognition。Providence， RI，2011：1937-1944。

＼[2＼]STAUFFER C，GRIMSON W E L。Adaptive background mixture models for realtime tracking＼[C＼]//IEEE Conference on Computer Vision and Pattern Recognition。 Fort Collins，1999。

＼[3＼]WU Chuan，WANG Yuanyuan， KARIMI H R。 A robust aerial image registration method using Gaussian mixture models＼[J＼]。 Neurocomputing， 2014，144： 546-552。

＼[4＼]WONJUN Kim， CHANGICK Kim。 Background subtraction for dynamic texture scenes using fuzzy color histograms＼[J＼]。 IEEE Signal Processing Letters， 2012， 19（3）： 127-130。

＼[5＼]王志明， 张丽， 包宏。 基于混合结构神经网络的自适应背景模型 ＼[J＼]。 电子学报， 2011，39（5）： 1053-1058。

WANG Zhiming， ZHANG Li， BAO Hong。 Adaptive background model based on hybrid structure neural network ＼[J＼]。 Acta Electronica Sinica， 2011，39（5）： 1053-1058。（In Chinese）

＼[6＼]HAN B， DAVIS L S。 Densitybased multifeature background subtraction with support vector machine ＼[J＼]。 IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（5）： 1017-1023。

＼[7＼]YAO J，ODOBEZ J M。 Fast human detection from video using covariance features＼[C＼]//The Eighth International Workshop on Visual Surveillance。Marseille，2008。

＼[8＼]LIN Hornghorng， CHUANG Jenhui， LIU Tyngluh。 Regularized background adaptation： A novel learning rate control scheme for gaussian mixture modeling＼[J＼]。 IEEE Transactions on Image Processing， 2011， 20（3）： 822-836。

＼[9＼]ZIVKOVIC Z。 Improved adaptive Gaussian mixture model for background subtraction＼[C＼]//IEEE International Conference on Pattern Recognition。 IEEE，2004：28-31。

＼[10＼]肖进胜，单姗姗，易本顺， 等。基于区分灰度投影稳像的运动目标检测算法＼[J＼]。湖南大学学报：自然科学版，2013， 40（6）：96-102。

XIAO Jinsheng， SHAN Shanshan，YI Benshun， et al。 Moving targets detection based on subzone gray projection video stabilization＼[J＼]。Journal of Hunan University：Natural Sciences， 2013，40（6）：96-102。（In Chinese）

＼[11＼]CHENG Fanchieh，HUANG Shihchia，RUAN Shanqjang。 Illuminationsensitive background modeling approach for accurate moving object detection＼[J＼]。 IEEE Transactions on Broadcasting， 2011， 57（4）：794-801。

＼[12＼]齐玉娟， 王延江， 李永平。 基于记忆的混合高斯背景建模＼[J＼]。自动化学报， 2010， 36（11）： 1520-1526。

QI Yujuan，WANG Yanjiang， LI Yongping。 Memory based Gaussian mixture background modeling＼[J＼]。 Acta Automatica Sinica， 2010， 36（11）： 1520-1526。 （In Chinese）

＼[13＼]XIAO Jinsheng， LI Wenhao， LIU Guoxiong，et al。Hierarchical tone mapping based on image color appearance model＼[J＼]。IET Computer Vision， 2014， 8（4）： 358-364。

混合型算法 第7篇

关键词：路径诱导,自适应遗传算法,微种群遗传算法,最优路径选择

0 引言

目前,由于缺乏高效的路径诱导系统(Route Guidance System,简称RGS),交通拥挤和交通事故正越来越严重地困扰着世界各国的大城市。根据统计资料显示,西方发达国家由于公路堵塞而造成的直接或间接经济损失十分惊人。随着我国交通运输事业的迅速发展,如何研究一套适合我国国情的路径诱导系统,使之能够为路网上的出行者提供必要的交通信息,为其指出当前的最佳行驶路线,从而避免盲目出行造成的交通阻塞,达到路网畅通已成为全社会的共识,并且对我国的国民经济建设有重要的现实意义和经济价值。鉴于此,本文研究了一种基于混合遗传算法的动态路径诱导系统,并验证了其有效性。

1 自适应遗传算法及参数选择

自适应遗传算法(Adaptive Genetic Algorithm,简称AGA)是由Srinvivas等提出的,该算法中交叉率Pc和交叉率Pm能够随适应度自动改变。当种群个体适应度趋于一致或趋于局部最优时,交叉率Pc和交叉率Pm增加;而当群体适应度比较分散时,Pc和Pm减少。同时对适应值高于群体平均适应值的个体,对应于较低的Pc和Pm,使该解得以保护以进入下一代;而低于平均适应值的个体,相对应于较高的Pc和Pm,使该解被淘汰掉。因此,自适应的Pc和Pm能够提供相对于某个解的最佳Pc和Pm。自适应遗传算法在保持群体多样性的同时,保证遗传算法的收敛性。

基于AGA遗传算法的最优行车路径选择算法流程如下:

(1)随机产生初始种群,个体数目一定,每个染色采用实值编码方式进行编码;

(2)计算个体的适应度,并判断是否符合优化准则。若符合,输出最佳个体及其代表的最优解,并结束计算;否则,转向第(3)步;

(3)采用自适应交叉率,生成新的个体;

(4)依据适应度,适应度高的个体被选中的概率高,适应度低的个体可能被淘汰;

(5)采用自适应变异率,生成新的个体;

(6)采用最优保存策略来进行优胜劣汰操作,即当前群体中适应度最好的几个个体不参与选择、交叉和变异操作,而用它们替换掉本代群体通过选择、交叉和变异之后产生的适应度较低的几个个体,生成子代,返回到第(2)步。其整个算法流程如图一所示。

2 微种群遗传算法及参数选择

在一般SGA计算中,经过理论研究,当种群规模超过200或更大时,处理速度会因为计算量的过大而迅速减慢;种群规模小时,信息处理不充分,容易陷入局部非最优结果,但种群小,无疑有计算简单、速度快等优点。为了尽快获得最优解,有人提出了微种群遗传算法(Micro-group Genetic Algorithm,简称μGA)。其基本思想是不按平均特性来评价种群的行为,而是根据至今最好的个体(字符串)来评价和完成算法。μGA随机产生小种群,对它进行遗传运算并收敛之后,把最好的个体传至下一代,产生新的种群,再进行遗传算法,如此反复,直到完成总体收敛。μGA的具体算法流程如下:

(1)随机选择规模为5的种群,或者4个是随机选择,1个来自前一次搜索;

(2)计算适应度并确定最好的字符串,将其标记为5,传到下一代(精英策略),这样保证优良的信息不丢失;

(3)按照确定性竞赛选择策略选择其余4个串以进行复制;

(4)以概率1施加交换运算,以加速产生适应度高的串。显然,通过新的种群,每次收敛后有足够的种类,因此变异率为零;

(5)检验收敛条件,如收敛转步骤(1);否则转步骤(2)。

μGA在进化过程中,以合理的间隔通过“启动再启动”过程,不断地引入恒定数目的新种群,寻求较好的个体,可避免早熟收敛,并有较快的收敛速度。其整个算法流程如图二所示。

3 基于AGA与μGA混合算法的最优路径选择算法

基于AGA与μGA混合算法的最优路径选择算法是先用AGA优化初始种群,使种群中的无效染色体大部分变成有效染色体,然后用μGA对A-GA操作得到的由有效染色体组成的种群进行优化,最后得到最优路径。算法流程如图三所示。

3.1 最优路径选择算法参数确定

(1)自适应遗传算法的染色体的编码、编码长度、种群规模、适应度函数的确定和群体更新的方式上与普通遗传算法完全相同,不同的是:

(1)交叉率Pc和变异率Pm:采用自适应交叉算子和自适应变异算子进行染色体的交叉和变异计算,其中,Pc1=0.9,Pc2=0.6,Pm1=0.1,Pm2=0.001。设T=15,本文对选择率Pc和变异率Pm进行了实验研究,结果如图四和图五所示。

(2)本文AGA的终止条件有两个:一个是终止代数T达到某一给定值时结束。通过仿真实验证明,当遗传代数T超过15时,染色体的适应度基本不发生变化,并且当T从10增加到15时,适应度提高速度已经很慢,因此,为了使算法达到更好的实时性,选择T=10。终止代数选取的仿真实验结果如图五所示。另一个终止条件是当7T<10时,新种群中有效染色体数目超过90%时终止遗传操作。

(2)微种群遗传算法染色体的编码、编码长度与SGA相同,不同的是:

(1)群体规模:μGA的种群来自AGA的结果,理论上应该不小于400*90%。

(2)适应度函数:因为通过AGA操作得来的种群中的个体都是有效个体,所以适应度函数只使用普通的适应度函数。

(3)交叉率Pc和变异率Pm:μGA的交叉率Pc=1,变异率Pm=0。

(4)终止条件:通过多次仿真实验证明,终止条件是μGA的外层循环结束。

3.2 仿真结果及分析

如图六所示,以沈阳市一环内一级干线马路路网为研究对象进行仿真实验。该路网包含74个结点,262条有向路段。其中,路网中距离最远的结点对是14和56,两点间直线距离为10.98千米。

对基于AGA与μGA混合算法的最优路径选择算法,采用MATLAB仿真语言进行了仿真实验,共仿真计算390次,对于大部分结点对遗传算法都能准确地找到最短路径,但有些结点对找到的不是最短路径,而是接近于最短路径的路径,这样的路径共有17条。这17条路径虽然并非最短路径,但可能是第n(n=2,3,)短路径,对于路径诱导仍具有一定的利用价值。对于任意一个OD对,通过遗传算法的计算找出一条路径所花时间小于5秒,因此,AGA与μGA混合算法的最优路径选择算法满足了智能交通路径诱导的实时性要求。

4 结束语

本文提出了基于AGA与μGA混合算法的最优路径选择算法,通过仿真实验验证了其用于交通系统最优路径诱导计算的有效性。结果显示,基于AGA与μGA混合算法的最优路径选择方法更有效,具有更好的适用性和实时性。

参考文献

[1]Azaron A.,Kianfar F..Dynamic Shortest Path in Stochastic Dynamic Networks:Ship Routing Problem[J].European Journal of Operational Research,2003,144(01):138-156.

[2]Julie M.Annino,Robert Cromley.Intelligent Transportation Systems and Travel Behavior in Connecticut[J].The Professional Geographer,2005,9(01):106-114.

[3]徐长斌,刘艳梅.动态路径诱导算法研究[J].公路交通科技(应用技术版),2007,(10).

[4]韩忠华,刘春光,戴敬,等.城市交通短时交通信息自适应遗传预测方法[J].沈阳建筑大学学报(自然科学版),2009,(02):390-394.

[5]吴义虎,李宁,王正武.蚁群算法在车辆路径诱导系统中的应用[J].系统工程,2007,(02):27-31.

混合遗传算法及其应用 第8篇

遗传算法是近年来发展起来的一种新型优化算法, 是基于自然选择和遗传学机理的迭代自适应概率性搜索方法。它通过模拟生物进化的途径问题的解域中定向搜索最优解, 在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用。

遗传算法的实现涉及5个主要因素:参数编码、初始群体的设定、评估函数 (即适应函数) 的设计、遗传操作的设计和算法控制参数的设定。对于传统方法较难求解的一些NP问题, 遗传算法往往能得到更好的结果。但对传统方法已能较好解决的问题 (如一般的非线性优化问题) , 它并没有较强的优势。遗传算法主要采用群体搜索技术, 通过对解的不断组合、随机改变以及对候选解的评估和选择来完成求解过程。在达到全局最优解前, 它尚存在收敛慢的问题。设计遗传算法时往往需要在其通用性与有效性之间折衷。设计针对问题的特定遗传算子, 可以更有效地求解问题, 但缺乏通用性。另一种途径是将遗传算法与问题领域中一些传统的寻优方法 (如爬山法、模拟退火法、牛顿法等) 结合起来, 可在保持算法一定的通用性时提高算法的效率。

本文考虑一类非线性函数优化问题, 即:

其中f (x) 是n元连续函数, D是Rn的有界子集。本文探讨将梯度法与遗传算法相结合的算法, 梯度法对初始解的构成具有较强的依赖性, 算法执行过程中难于发现新的可能存在最优解的区域。通过将它与遗传算法相结合, 一方面可以利用其局部搜索能力, 另一方面可通过遗传算法来不断“发现”新的更有希望的搜索区域, 并动态调整可变多面体法的搜索方向, 从而使算法具有更好的灵活性, 也使算法更易于并行化。实验表明, 对于求解上述非线性优化问题, 混合遗传算法具有比传统遗传算法和梯度法都好的性能。

1 混合遗传算法

1.1 编码方式

编码的实质是在问题的解空间与算法的搜索空间之间建立一个映射。传统遗传算法一般采用一种将实数空间离散化的二进制编码方式。这种方式存在编码长度影响求解精度、操作费时、不直观等缺点, 因而提出了实数的直接编码方式并表明可以获得更好的性能。在实数编码方式下, 每个个体用一个n维的实向量来表示, 这种方式具有直观、易操作的优点, 且可以针对它设计非传统的交叉算子。本文采用此编码方式。

1.2 交叉和选择操作

正交遗传算法在非线性优化问题及其他组合优化问题中已显示出其有效性, 我们的算法采用了正交交叉算子。由两个父本交叉操作产生一组个体, 从新个体和两个父本中选择最优的进入下一代群体。由于采用局部选择而不是全局选择, 在一定程度上保持了群体的多样性。

1.3 变异操作

在实数编码方式下, 变异操作对个体X的每个分量X[i]作用一个随机偏差量, 即:

X′[i]=X[i]+δ, i=1, 2, , n

在进化规划和进化策略中, 广泛采用了高斯变异算子, 用正态分布的随机变量来作为变异操作中的偏差量。

1.4 局部搜索

在本文中, 我们采用梯度法进行局部搜索, 梯度法步骤如下:

(1) 选定ε>0为终止限。选定初始点X (0) , 令k=0。

(2) 计算△f (X (k) ) 。如果‖△f (X (k) ) ‖<ε, 迭代停止, 取近试最优解X*=X (k) , 否则, 令S (k) =-△f (X (k) ) , 从X (k) 出发沿S (k) 作一维搜索, 求得λk使得mλ>i0nf (X (k) +λS (k) ) =f (X (k) +λkS (k) ) 。

(3) 令X (k+1) =X (k) +λkS (k) , k+1k, 返回步骤 (2) 。

1.5 终止准则

算法运行停止的条件包括以下的一种或它们的结合形式:

(1) 算法收敛到一个不动点或连续几次迭代所获得的改变量小于要求的精度值。

(2) 达到算法规定的最大迭代次数、或最大执行时间、或函数的最大调用次数 (对解空间的最大采样次数) 。我们用最大采样次数和最大迭代次数来控制算法的终止。

1.6 算法描述

混合遗传算法的主要步骤为: (1) 初始化:随机产生一个分布均匀的初始群体 (包含N个初始解) ; (2) 交配:按两两配对的原则将群体中的个体配对并执行第1.2节的正交交叉操作; (3) 变异:群体中每个个体以Pm的概率进行变异; (4) 局部搜索:采用梯度法反复进行局部寻优操作; (5) 终止:若终止条件满足, 则算法中止, 否则转向步骤 (2) 。

2 实验结果

我们用实验的方法来比较标准遗传算法和混合遗传算法的性能。标准遗传算法采用与混合遗传算法相同的交叉和变异操作。在实验中, 我们选择了下面的函数:

该函数存在多个极值点, 其中x*=0.1275是唯一全局极大点, f (x*) =19.8949。

在我们的仿真中, 采用16位二进制编码, 群体规模取50, 试验40次, 迭代次数为100代, 结果如表1所示。

3 结束语

本文给出了一种求解非线性全局最优化问题的混合遗传算法, 它将梯度法与正交交叉算子结合起来, 既可利用遗传算法的全局搜索能力, 又能通过局部搜索加快算法的收敛。实验表明, 本文提出的混合遗传算法能有效地处理一些传统遗传算法和寻优方法较难处理的函数优化问题。

参考文献

[1]GOLDBERG D E.Genetic Algorithms in Search, Optimization and Machine Learning[M].Reading, MA:Addison-Wesley, 1989.

[2]RENDERS J-M, FLASSE S P.Hybrid methods using genetic algo-rithms for global optimization[J].IEEE Transactions on Systems, Man, and Cybernetics (Part B) , 1996 (2) .

[3]WRIGHT A H.Genetic algorithm for real parameter optimization.In:Rawlins G ed[D].Foundations of Genetic Algorithms.San Francis-co:Morgan Kaufmann, 1991.

[4]ESHELMAN L J, SCHAFFER J D.Real-coded genetic algorithms and interval-schemata[J].Foundations of Genetic Algorithms, 1993 (2) .

[5]陈国良, 王熙法, 庄镇泉.遗传算法及其应用[M].北京:人民邮电出版社, 1996.

[6]张晓缋, 戴冠中, 徐乃平.遗传算法种群多样性的分析研究[J].控制理论与应用, 1998 (1) .

混合型算法 第9篇

P2P僵尸网络的混合模型[3]如图1所示,主要分为控制模块和被控模块(Bot)两大部分,其中Bot终端按照宿主机网络连接类型的不同又分为两类:一类是可以从Internet直接访问的Bot终端(称为servent Bot),这类Bot终端组成核心P2P网络;一类是位于防火墙或者NAT(network address translation,网络地址转换)之后等无法直接从Internet访问的Bot终端(称为client Bot),这类Bot终端形成外围Bot网络。

该混合模型主要通过本地的节点列表来完成与其他Bot的通信以及接收和下达中控命令等,该列表是实时动态的,不再是固定的地址列表,文献[3]中提出了一种列表更新算法,通过随机的替换和更新路由列表来达到隐藏和实现网络均衡等目的。

2 自适应淘汰机制和列表路由算法

2.1 问题分析

目前P2P僵尸网络效率和韧性较差的主要原因是通信机制的不稳定、不隐蔽,问题的关键有以下几个方面:

(1)通信报文没有加密,整个连接和通信过程没有经过加密机制的处理,使得报文在网络传输中容易被截获分析。

(2)网络结构不均衡,由于目前的P2P僵尸网络对Servent Bot的依赖性过重,随着僵尸网络的规模慢慢扩大,部分Servent Bot会有大量的网络流量出入,负载变大,导致网络平衡性差,使得节点易暴露。

(3)节点列表的适应性较差,列表的更新容易产生数据冗余,诸如Nugache的Botnet对初始定义的列表依赖性太大。

其中,列表的适应性差是导致僵尸网络效率和韧性低下、节点易暴露以及被溯源的最主要原因。

2.2 自适应淘汰机制

将下列定义写入列表信息:IP地址、列表浮动上限M、TTL值以及更新时间Tu,其中,Servent Bot发送广播通信报文时,在本地列表相应的更新一个发包时间T0,在相应IP的Servent Bot发回响应报文时,记录响应时间T1,Tu=T1-T0令,然后更新本地列表项Tu。结合各个变量,用L来表示列表,在文献[3]基础上扩充列表内容,那么Bot A的节点列表可以表示为:

构建的更新列表如表1:

当列表项数P=Mmax(当前列表数达到预设最大值)时,拒绝一切Bot间的通信,并按下列淘汰策略开始重新整合列表,优先级由高到低排列为:

(1)定期以正常网络服务为通信手段与列表中的节点进行通信,更新列表项的值Tu,机制启动时,若某列表项中Tu=T0,则说明发出去的报文没有得到响应,判断此项为不可达,令Tu=∞,并淘汰此项。

(2)通过TTL值的大小来对列表进行排序,TTL值越大则先写入栈,此时,列表整合为TTL数值最小的在栈顶,最大的在栈底。将栈底P-M的的路由列表中随机淘汰个列表项,此时列表项数达到M+个。

(3)上一步结束后,根据此时列表中各列表项的Tu值大小,对列表再一次进行排列,Tu值越大,则先写入栈,将列表整合为Tu值最小的在栈顶,最大的在栈底。从栈底淘汰个列表项(以上各式的P值均为达到淘汰原则的当前值),完成淘汰机制。

进一步要说明的是,淘汰机制在进行过程中以及在随后的△T内,停止接受和请求任何其他Bot的连接。

2.3 改进的列表路由算法

沿用Nugache型僵尸网络的初始化过程,预定义一定数量的Servent路由列表项,以代码方式写入Bot程序当中。显然,在僵尸网络构建之初,主要是利用预置的Servent Bot做通信流节点,新加入的Bot都按照本身程序内部的路由列表来寻找网络中的Servent Bot,随着僵尸网络的不断蔓延和扩大,一些新的主机被选为Servent Bot加入整个网络架构中,相应的路由列表也做出更新。

具体算法流程如下:

(1)当有新感染的Bot A主机加入时,按照预定义路由列表,寻找servent主机,此时Bot A的路由列表LA时间项更新为:Tu=T0。

(2)Servent Bot B收到来自Bot A的请求报文,根据其报文内容,首先判断其Bot类型,当Bot A属于Servent Bot时,添加一条路由表项:此时T的取值为收到请求报文的时间,然后在自身的路由表TB中,随即选取R(R

(3)Bot A收到来自Servent Bot B的响应报文,将Bot B连同收到的R个路由信息(R可能包含Bot B的路由信息)一同存入列表LA。同时,将新的Tu=T1-T0更新到相应的列表内容中。

(4)随着网络结构的不断扩大,列表逐渐增多,如果当前列表数P=Mmax时,拒绝所有Bot节点的请求连接,同时停止向其他Servent Bot的通信请求,执行自适应淘汰机制,对列表进行更新,直到列表数重新回到浮动上限M。

(5)更新完毕并在△T时延后,打开连接信道,开始新的请求和接受来自其他Bot的连接。

2.4 算法分析

本算法主要利用提出的淘汰机制,来加强Bot主机在网络中的自适应能力,减少僵尸网络master对各节点做出调整的指令数,从而减少了中控与被控模块之间的连接次数,使得中控模块更加隐蔽难查。

通过自适应淘汰机制,将存在于Bot主机的路由列表里的各路由项进行了优化,主要是在列表中添加了TTL值与回连更新时间Tu。通过优化,使得列表在一段时间内,自动更新为网络拓扑中与自己较相近以及回连速度较快(可能TTL值很大)的Servent Bot主机。

优化后的列表完成的功能如下:

(1)尽可能地将网络拓扑中相邻的主机的划分在一个小的区域当中,这么做的目的在于使得中控指令的下达更具有时效性,同时,当一个小区域中的Servent Bot被截获时,减少了从列表取得和劫持大面积范围Bot的可能性,提高了整个僵尸网络的韧性度,使得整个僵尸网络不会因为小区域主机的丢失而导致大面积网络功能的瘫痪。

(2)通过淘汰机制,筛选网络回连速度较快的主机来更新自己的路由列表。一方面是同样要达到提高指令传输时效性的要求,使得中控master在下达命令后,能够尽快地传达给各个Bot节点(包括Servent Bot和client Bot),减少指令时延,提高效率;另一方面,由于淘汰机制发生在当前列表数P=Mmax的时刻,从侧面反映出当前的Servent Bot的连接负载已经比较严重,此时的机制在进行以及完成后的△T内是不会接受和请求任何连接的,例如,Bot A节点频繁对Bot B发出请求,会因为得不到正常的响应,使得Bot A的路由列表TA中,关于Bot B的列表项中的TU值变大,使得自身在下一次淘汰机制进行中,淘汰出当前的负载过重的Bot B节点。比较有效地控制了个别节点的由于网络负载过重导致的流量拥塞,减少了流量分析系统发现的可能。

(3)浮动上限M的存在,是为了便于中控master控制和调整网络规模。通过下达更新命令,重新构造M值来达到控制列表数的目的,从而在一定程度上可以限制网络规模,优化网络路径,以及筛选命令下发节点。

3 模拟实验与仿真数据分析

由于没有实际网络环境来验证算法,采用网络模拟器来构建虚拟互联网。通过模拟实验数据,来验证算法的性能。

利用基于NS2的P2P模拟实验平台,在应用层很传输层上进行P2P协议扩展,并配置相关参数,用网络拓扑生成工具自动生成实验所需的网络拓扑环境。初始化Servent Bot超级节点以及Bot程序各项参数,令各节点每两分钟进行一次通信请求,预置M=5,R=2,Mmax=10,淘汰机制时延△T=1分钟。

实验表明,当网络环境自由运行7分钟时,第一台Servent Bot S1进行第一次列表自适应淘汰机制,然后关闭通信通道,拒绝其他连接。9分钟时,第二台Servent Bot S2列表LS2列表项数达到Mmax,而此时的S1在过了△T时间后,已经重新开始建立通信,随着Bot的不断延伸,若干Servent Bot陆续进行了列表的淘汰更新,同时初始化的几台Servent Bot已经维持了通信平衡状态,通信流量不断地向新加入的Servent Bot进行分流。到30分钟时,各Servent Bot主机列表基本在M值与Mmax值之间上下浮动,并未出现流量过载情况,整个网络拓扑趋于均衡,网络拓扑也规整成跳数相近的若干主机为一个小的自治域,各自治域之间互有联系,未发生网络失效的情况。

通过实验,利用自适应淘汰机制更新路由列表,可以很好地发展僵尸网络拓扑,同时将网络流量基本均衡给各servent Bot主机,并且,跳数相邻的主机规整成了一个小的自治域,提高了网络传输的时效性,也使得整个网络更加隐蔽和坚韧。

参考文献

[1]诸葛建伟,韩心慧,周勇林,叶志远,邹维,等.僵尸网络研究[J].软件学报,2008,19(3):1-3.Zhuge Jianwei,Han Xinhui,Zhou Yonglin,Ye Zhiyuan,ZouWei,et al.Research and Development of Botnets[J].Journalof Software,2008,19(3):1-3.

[2]Reinier Schoof,Ralph Koning,Detecting peer-to-peer botnets[EB/OL].http://staff.science.uva.nl/~delaat/sne-2006-2007/p17/report.pdf,2007.

[3]Wang P,Sparks S,Zou CC.An advanced hybrid peer-to-peerbotnet.In:Proc.of the 1st Workshop on Hot Topics in Under-standing Botnets(HotBots 2007).2007.

[4]Li J,E hrenkranz T,Kuenning G,Reiher P.Simulation andanalysis on the resiliency and efficiency of malnets.In:Proc.of the IEEE Symp.on Measurement,Modeling,and Simulationof Malware(MMSM 2005).Monterey:IEEE Computer Soci-ety Press,2005:262-269.

[5]Yang Yun,Hu Guyu,Guo Shize,Yu Saisai.An Improved Hy-brid Peer-to-Peer Routing Algorithm.The First InternationalConference on Pervasive Computing,Signal Processing andApplications(PCSPA 2010),2010.

[6]R.Bhagwan,S.Savage,and G.M.Voelker,“Understandingavailability,”in Proceedings of the 2nd International Work-shop on Peer-to-Peer Systems(IPTPS),2003.

混合编码遗传算法及其应用 第10篇

遗传算法是近年来一种全新的借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的随机搜索与优化算法,在许多领域的理论与工程实践中都有成功的应用,混合编码遗传算法也在不断发展,并在相关领域的优化应用中取得了很好效果。本文系统分析了混合编码的理论,论述了不同问题应采取的混合编码方案,解析了混合编码的具体运用方法,为解决复杂问题提供了参考方案。

1 混合编码原理

编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键步骤。遗传算法的进化过程是建立在由二进制符号0和1组成的编码机制基础上,以后又发展了浮点型编码、符号编码等等,编码对于算法的效能,如收缩能力和种群多样性等影响很大。Hol l and[1]提出的编码方法是二进制编码,即编码符合许多遗传算法的应用,这种简单的编码方法很难直接描述问题的性质,不便于反映所求问题的特定知识,对于解决复杂问题也存在局限性。近十年来,针对特殊问题和复杂问题,人们提出了混合编码方法。

混合编码即多参数编码。由于在应用遗传算法解决优化问题中可能会出现多个决策变量,对这种含有多个变量的个体进行编码的方法就称为多参数编码方法。多参数编码码制可以是二进制、格雷码、浮点数编码或符号编码等。

多参数编码方法包括两种最常用的方法:多参数级联编码方法和多参数交叉编码方法。

多参数级联编码是将各个参数分别以某种编码方法进行编码,然后再将它们的编码按一定顺序连接在一起就组成了表示全部参数的个体编码,各参数的上下界可以不同,码长或编码精度也可有所不同。例如,假设一种个体含有n个参数,每个参数li用i(i=1,2n)位的二进制编码,则该个体可表示为:

该编码串的总长度为:。这是多参数二进制级联编码的一种通用形式。

多参数交叉编码是将各个参数中起主要作用的码位集中在一起,这样不容易被遗传算子破坏,在进行参数交叉编码时,可对各参数进行分组编码。假设有n个参数,每个参数都采用码长为m的二进制编码,取各参数编码串中的最高位联接在一起,作为个体编码的前n位编码,再取次高位联接在一起,作为个体第二组n位编码,,再取最后一位联接在一起作为编码的最后n位,这样组成的长度为mn位的编码串就是多参数的一个交叉编码串。各参数的编码如下所示:

个体编码串为:

在多参数的级联编码方法中,各种参数的编码值集中在一起,这样各个参数的局部编码结构就不容易被遗忘算子破坏掉,它适合于各参数之间的相互关系较弱,特别是某一个或者少数几个参数起主要作用时的优化问题。而多参数的交叉编码方法特别适合于各个参数之间相互关系较强,各参数对最优解贡献相当时的优化问题[2,3,4]。

2 混合编码方案

目前比较成熟的编码方法有二进制编码、十进制编码、格雷码、浮点数编码等,混合编码就是将这些成熟的编码方法按照混合编码原则结合起来。在实际应用中,最常用的混合编码方式有以下几种:

(1)二进制和浮点数混合编码

二进制编码具有编码及解码操作简单易行、交叉及变异等遗传操作便于实现等优点,但精度受到一定的限制。实数编码是遗传算法在解决连续参数优化问题时普遍使用的一种编码方式,不需要进行解码,比较直观,具有较高的精度,免去了二进制转换时引起的误差,在表示连续渐变问题方面具有优势。该混合编码方法既可以加快遗传操作,进行大范围的全局搜索,又可以解决连续参数优化问题,提高了优化的精度,用于解决非线性程度较高,多解性以及函数表达的不确定性等问题。传统的遗传算法在解决这些问题时不能取得预想的效果。

(2)浮点数和格雷码混合编码

浮点数编码具有可取得搜索空间的任意精度、局部搜索能力较强的特点,而格雷码编码具有全局搜索能力较强的特点。先用格雷码编码进行较大空间的遗传搜索,进化后期,再用浮点数编码进行小范围的寻优,该混合编码方法不易陷入局部收敛,具有很强的跳出局部极值能力,且收敛速度较快。

(3)二进制和十进制混合编码

对于二进制编码机制,它比非二进制编码机制得到的模式多,因而所能搜索的范围大,但是通过二进制编码间接运算,人为将连续空间离散化,影响优化精度,使得问题求解更复杂。另外,二进制编码变异的最小量受到编码长度的影响,变异操作也不能保证遍历到最优解,而十进制编码机制表达直观,节约存储空问,变异量可以任意小,从而保证了父个体与新个体充分接近,提高种群的稳定性。因而这种混合编码方式不仅能有效提高遗传算法搜索和产生“新”有效基因物质的能力,而且在克服群体“早熟”,避免落入局部最优方面都将有显著改善。

3 混合编码遗传算法的实现过程

混合编码由于其编码的特殊性和复杂性,又因为求解问题以及遗传操作的多样性,因而具体的实现过程也是各自不一,下面是几种常用的实现方法:

(1)转换法

混合编码遗传算法中,同时采用两种编码方法。在算法进行过程中,根据需要设置“调节参数”,进行两种编码方法的转换:当进化代数t小于进化最大遗传代数的参数倍时,采用一种编码方法,并采用与这种编码方法对应的交叉、变异算子进行遗传操作;当进化代数t不小于进化最大遗传代数的参数倍时,采用另一种编码方法,并采用与此种编码方法对应的交叉、变异算子进行遗传操作。具体实现如图一所示。

(2)并行法

这种方法的基本要点在于两种编码并行。在算法进行过程中,首先对所有参数进行一种形式编码,形成个体基因串。然后选择一种主要的编码方式,大部分情况下,都按照这种编码方式存在,只有在遗传操作(选择,交叉,变异)中根据具体的问题,进行两种编码的转换,转换成另一种编码,最后再把编码转换为主要形式且必须要保证这两种编码方式是可以互相转换的。例如:二进制编码和十进制编码的应用,在选择,交叉时以二进制编码为主,当某个参数所对应的码段被确定要进行变异时,进行两种编码的转换。先将该参数转换成十进制编码,然后对该基因进行随机变异,最后再将变异后的新参数逆变为二进制编码[5]。实现过程如图二所示。

(3)其他方法

混合编码遗传算法在进行遗传操作的过程中,对两种编码不作区分、按杂交率作单显或多显杂交、倒位杂交或者选定起主导作用的编码基因,当主要编码基因完成杂交操作后,维持不变,然后对次要编码基因作杂交变换。同样,对于变异操作,对两种编码不作区分,按变异率作单点或多点变异,选定起主导作用的编码基因,当主要编码基因完成变异操作后,维持不变,然后对次要编码基因作变异变换。

4 混合编码遗传算法的应用

混合编码遗传算法较为成熟的应用主要有函数优化、图像处理、神经网路优化、模型识别问题等。

(1)函数优化

函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样复杂形式的测试函数,用这些各具特色的函数来评价遗传算法的性能,而这些函数中有很多会涉及两个或多个变量,因而适合用混合编码方法来实现遗传算法。例如:六峰值驼背函数优化问题,就含有两个变x和y,适合用混合编码方法来实现函数的优化。

(2)图像处理

图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中,如特征提取、图像分割,匹配跟踪等会不可避免的存在一些误差,从而影响图像的效果。混合编码遗传算法在最大降低图像处理中的误差以及优化计算方面发挥了很大的作用,使图像达到较好的视觉效果。目前已在图像匹配、图像恢复、图像边缘特征提取等方面得到了应用[6]。

()3神经网络优化

混合编码遗传算法在神经网络优化方面得到了初步的应用,并显示出良好的效果。关于神经网络的优化主要集中在权值和结构的分开执行,二者的优化应该同步进行才能使系统最好地适应外界环境,从而在各种网络结构中寻求一种网络权值的最佳逼近。最早的研究结果是Bhat[7]等人引入网络结构复杂度函数的概念,并以BP算法为网络训练手段,然而难以直接处理非连续函数形式,故没有形成太大的影响。因此有研究者采用一种混合编码方案,运用“结构编码”和“权值编码”来实现优化的并行,能以较快的收敛速度搜索到全局最优解,在优化出性能优越的神经网络结构的同时,又得出了较好的神经网络权值分布[8,9]。

(4)模型识别

基于遗传算法的进化模型是研究人工智能的重要基础理论,当前运用混合编码遗传算法已在模型识别、参数辨识等方面得到了初步的应用。模型识别的目的就是根据模型系统所提供的信息,在某种准则意义下,估计出模型的未知参数。在现有的文献中,人们常用的大多还是基于最小二乘的遗传算法。即先用遗传算法辨识结构,再采用最小二乘法辨识结构的参数,但是这样的方法会存在一定的误差,使得辨识的最终结果不准确,也没有发挥遗传算法作为一种全局寻优算法的能力。而混合编码遗传算法就可以结合两种编码的优势解决这些问题,采用结构基因和参数基因相结合的办法,从而使模型结构和模型结构参数同时辨识出来[10]。

5 结束语

遗传算法能否求解问题,其前提是对求解问题的合理编码。本文分析了混合编码遗传算法中染色体的编码原理,列举了比较常用的混合编码方式,简述了混合编码的一般实现方法,并介绍了混合编码遗传算法在各个研究领域中的应用。混合编码遗传算法是一个十分活跃的研究领域,开拓更广泛的应用领域是今后应用研究的主要任务。混合编码遗传算法的研究正在从理论的深度、技术的多样化以及应用的广度不断地探索,朝着计算机拥有甚至超过人类智能的方向努力。

摘要：遗传算法中编码机制对交叉和变异的搜索能力有重要影响,为了弥补单一编码遗传算法求解复杂问题时所带来的局限性,混合编码遗传算法受到越来越多的研究者关注。本文重点介绍了混合编码遗传算法中的混合编码问题——多参数级联和多参数交叉编码,分析了由二进制,十进制和浮点数等编码组成的混合编码遗传算法的几种实现过程以及混合编码遗传算法在各行业的应用。

关键词：遗传算法,混合编码,交叉,变异

参考文献

[1]Holland J.H.Adaptation in Natural and Artificial systems.Ann Arbor:University of Michiganpress,1975.

[2]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社.1999,6.

[3]余有明,刘玉树,阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用,2006,(3).

[4]张晓绩,方浩,戴冠中.遗传算法的编码机制研究[J].信息与控制.1997,26(2):134～139.

[5]陈超,陈家联,余丰.混合编码遗传算法及其在非线性反演中的应用[J].计算机应用与软件,2004,(3).

[6]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,(2).

[7]BHAT N V,MCAVOY T J.Determining model structure for neural models by network stripping[J].Computers and Chemical Engineering,1992,16(4):271—281.

[8]Joachins.Parallel Cenetic Algorithms:Theory and Applications[J].ISO press,1993.

混合型算法 第11篇

本文将遗传算法与模拟退火算法相结合，从而优化模型设计过程，提高求解效率，克服传统遗传算法的缺陷，避免陷入局部最优。

1 遗传算法与模拟退火算法的结合

1.1 遗传算法和模拟退火算法的原理

遗传算法是借鉴适者生存、优胜劣汰的生物界进化规律而演化出的随机搜索算法，是由美国密歇根大学HOLLAND教授于1975年首先提出的新型全局优化搜索算法。遗传因子经过迭代能启发式地自适应搜索具有全局最优解的较小区域，并以较大的概率趋向于全局最优解。利用该原理能够有效解决许多常规优化方法难以解决的复杂优化问题。

模拟退火算法最早于1983年由KIRKPATRICK等用于组合优化领域，是基于蒙特卡罗迭代求解策略的随机寻优算法，基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解中概率性地跳出并最终趋于全局最优解。

1.2 遗传算法和模拟退火算法的局限性

遗传算法处理的对象不是参数本身，而是对参数集进行编码后的个体。由于应用了编码技术，可直接对结果对象进行操作，不存在求导和函数连续性的限定，因此适用于各类优化问题。然而，由于遗传算法采用根据适应度值大小来决定个体是否被复制的选择机制，容易出现来源于同一种群的个体被大量繁衍的情况，形成近亲繁殖，造成算法的局部搜索和过早收敛。由此可见，遗传算法具有一定的局限性，主要表现如下：（1）遗传算法属于启发式算法，求得的是近似解，求解效率有限；（2）需针对问题设计合适的编码方式，编码方式的优劣直接影响求解质量；（3）除非模型能提供最优解参考值，否则不能确定演算结果是否最佳；（4）由于此方法为群体同步搜寻，因此会占用计算机内存空间，影响演算速度。

理论上模拟退火算法以1的概率收敛，但局限性也较明显[1]，主要表现如下：（1）实际设计算法时算法结果存在波动性；（2）为寻找最优解，通常要求较高的初温、较稳的降温速率、较低的终止温度以及各温度下足够多次的抽样，优化过程较长，受计算速度和计算时间的限制，难以保证计算结果为全局最优点，优化效果不理想；（3）由于马尔可夫链的长度不易控制，在每一温度下很难判定是否达到平衡状态，反映到计算过程中就是实现Metropolis准则的次数不易控制。

1.3 构造混合遗传—模拟退火算法

遗传算法与模拟退火算法相结合是解决两种算法各自局限性问题的有效途径，具体来说有以下四方面的结合。[2]

（1）优化结构的互补 模拟退火算法采用串行优化结构，而遗传算法采用群体并行搜索方法，两者结合能使模拟退火算法成为并行算法，在提高自身优化性能的同时作为自适应的变异操作，增强和补充遗传算法的进化能力。

（2）优化操作的结合 模拟退火算法每一时刻仅保留1个解，缺乏冗余和历史搜索信息；而遗传算法的复制操作能在下一代中保留种群的优良个体，交叉操作能使后代在一定程度上继承父代的优良模式，变异操作能增强种群中个体的多样性，这些不同作用的操作相结合，丰富了优化过程中解空间的搜索结构，增强了全空间的搜索能力。

（3）优化行为的互补 由于复制操作对当前种群外的空间无搜索能力，种群中个体分布“畸形”使交叉操作的进化能力有限，而小概率变异操作很难增加种群的多样性，因此，若收敛准则设计得不好，则会出现进化缓慢或早熟收敛的现象，结合后并行化的抽样过程可优化算法的时间性能。

（4）削弱参数选择的苛刻性 设计算法时需依靠大量的试验和经验来确定两者相结合后算法各方面的搜索能力均得到提高，因此，对算法参数的选择不必过分严格。研究表明，混合算法在采用单一算法参数时，优化性能和鲁棒性均有大幅度的提升，尤其是针对较大规模的复杂问题。

2 利用混合遗传—模拟退火算法求解班轮航线配船问题

2.1 班轮航线配船问题描述及模型建立

参考文献：

[1] 段姹莉，陈波．VB环境下的模拟退火算法求指派问题[J]．电脑知识与技术，2008，4（8）：2153-2155.

[2] 丁香乾，韩运实，张晓丽．自适应遗传算法解决集装箱装载问题的方法探讨[J]．中国海洋大学学报：自然科学版，2004，34（5）：844-848.

混合型算法 第12篇

云计算作为一种计算、存储资源的新型商业模式而出现, 具有按需访问大量、潜在的远程数据、计算中心的功能。随着云计算的发展日趋成熟, 相关的服务和应用正在逐年递增, 云计算为之配备的服务器数量规模也在高速增长。为了达到负载均衡、降低成本以及节能的目的[1], 云计算任务分配调度已经成为当今研究的热点课题。

云计算是从网格计算的基础上发展而来, 但网格计算一般用于科学研究, 而云计算则更多的是面向广大用户, 应用场景的不同使得两者的任务分配方法存在着非常明显的差异[2]。网格计算多是针对应用与科学研究领域, 以计算密集型应用为主, 更注重的是效率, 比如最短时间完成任务, 所以传统的网格程序性能预测模型往往只考虑程序的运行时间效率, 而忽略了其他硬件方面的开销。而云计算应用范围的广泛化就决定了必须在效率和各种资源开销之间寻找一个平衡, 这些开销就包括时间开销、CPU利用率、内存使用大小、I/O使用大小, 为了降低成本就要使以上各种硬件资源得到充分的使用而减少任务所需主机的总数量, 同时为了保证Qo S (Quality of Service) 必须避免出现资源征用情况的发生。

目前, 许多云计算任务分配调度方法的目的主要为了减少任务的运行时间[3], 或者任务运行的利益最大化[4], 却较少地关注到任务运行所消耗的资源以及能耗。Pandey等[3]使用优化粒子群算法寻找出云计算环境下最优的资源分配策略, 使得任务的执行总时间以及通信量最低;徐骁勇[5]通过对云计算资源进行调度, 缩短了云计算任务的运行时间, 同时也达到了降低能耗的目的;Srikantaiah[1]发现当计算机CPU和硬盘处在某一利用率时可以达到处理平均事务所消耗的能量最少, 并通过调整硬件资源的利用率来达到节能的目的;Duy[6]将计算机状态分为运行、等待、休眠和关机, 再结合数据中心的电源管理办法, 通过将计算机在这四种状态之间互相转换来达到节能的目的, 但并没有影响到计算机内部资源的利用率, 而且也没有解决资源使用不充分的问题;已有的三种绿色任务调度算法是STF-OS、LTF-OS、和RT-OS算法[7], 这三种算法虽然能够达到节能的目的, 但却只考虑了CPU的调度, 而没有兼顾到计算机的内存、I/O和带宽等资源的整体调度, 可能导致资源的不充分利用或者资源的争用, 从而影响Qo S。

根据云计算任务调度的特点, 本文提出了一种基于混合遗传算法的云计算任务分配策略, 实验表明, 这种方法能够有效地降低任务运行的总能耗, 降低任务成本。

1 云计算任务分配模型

1.1 任务分配问题的描述

假设一个数据中心包含m台主机, n个任务等待分配, {Cj, Mj, Dj, Nj}四元组分别对应第j台主机的CPU、内存、硬盘I/O、网络带宽四种资源, {ci, mi, di, ni}为第i个任务对四种资源的需求量, 则四元组{Cj, Mj, Dj, Nj}即为背包问题中第j个背包容量, {ci, mi, di, ni}为第i个物品的大小, 由此任务分配问题就转化为四维背包问题的求解, 如何将n个任务分配到m台主机, 同时保证每台计算机的资源使用率在四元组{Cj, Mj, Dj, Nj}的限定之内, 这是对一个多维多背包问题的求解。

1.2 任务分配问题的数学模型

背包问题是一种组合优化的NP完全问题[8]。问题可以描述为:给定n个物品, 每种物品都有自己的重量和价格, 第i个物品的重量为wi, 价格为vi, 在限定的总重量c内, 应该如何选择, 才能使得物品的总价格最高。其数学模型可表示为:

其中, xi表示物品是否被选装入:

多维多背包问题是背包问题的一类子集[9], 其中表示背包容量和物品大小的变量有多维表示, 而且物品放入的背包可有多个选择[10], 在任务分配问题中可用主机的各种硬件资源{Cj, Mj, Dj, Nj}表示为背包问题中第j个背包容量, 每个任务对各种硬件资源的需求量{ci, mi, di, ni}表示为第i个物品的大小, 则任务分配问题的数学模型可表示为:

其中, {Cj, Mj, Dj, Nj}表示第{Cj, Mj, Dj, Nj}台主机的CPU、内存、硬盘I/O以及网络带宽四个维度的容量, xij表示第i个任务是否被分配至第{Cj, Mj, Dj, Nj}台主机, 用公式表示如下:

2 混合遗传算法

遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法, 是进化算法的一类分支。这种启发式的研究思路通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而衍生发展起来的, 这些现象包括遗传、突变、自然选择以及杂交等。而鉴于基本的遗传算法存在着局部搜索能力差以及容易产生早熟现象的缺点, 结合云计算任务分配问题的特点, 本文采用了遗传和贪心相结合的混合遗传算法, 该算法克服了基本遗传算法局部搜索能力差以及容易产生早熟现象的缺点[11]。

2.1 遗传算法的基因编码

传统的遗传算法基因编码方式多采用二进制编码, 考虑任务分配问题可转化为0/1规划问题的特点, 可以将问题的解直接映射成一个mn的矩阵, 以此作为遗传算法的基因编码, 这种方法存在的缺点是基因长度为mn, 当问题规模较大时不利于搜索问题的优化解。

因为任务分配问题中, 一个任务只能分配到一台主机, 二进制编码中将会存在大量的冗余, 所以本文中直接采用整数编码的方式, 问题的解可表示为X={x1, x2, , xn}, (xi∈{0, 1, 2, , n}) , 例如将第i个任务分配至第j台主机, 则xi=j, 当xi=0时, 则表示没有多余的资源可以执行第i个任务, 任务未被分配。

采用整数基因编码方式优化解的搜索空间为O (mn) , 而采用二进制编码方式的搜索空间为O (2mn) , 当问题规模较大时, 采用整数编码的遗传算法搜索空间要远小于采用二进制编码的搜索空间。

2.2 修正种群个体

种群的个体在经过交叉和变异之后都会产生新的个体, 但是这个个体不一定是可行解, 所以要将种群中的不可行解修正为可行解, 并且为了加快算法收敛的速度, 要将可以优化的可行解进一步优化。在这里采用贪心算法实现这一功能, 其算法流程如图1所示。

2.3 目标函数与适应度函数

为了达到节能的目的, 采用计算耗能作为目标函数, 主机的能耗可表示为:

其中, T为主机的运行时间, p为主机运行的实际功率, p为主机的额定功率, 一般情况下都会满足pP, 但在文中修正种群个体的过程中会保证各运行主机的硬件资源得到充分的利用, 在这种情况下p≈P, 所以选取目标函数为:

其中, Pj为第j台主机的额定功率, Tj为第j台主机的运行时间, 由于云计算中一台主机可以运行多个任务, 所以Tj为第j台主机上最长任务的执行时间, 当主机未被分配任何任务时, 则处于休眠状态, 休眠状态下的主机耗电量为0。个体适应度函数选取目标函数的倒数:

2.4 选择与遗传操作

遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体, 被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体, 遗传到下一代群体。本文中选择算子采用轮盘赌选择方法, 设种群中共有N个个体, 个体xi被选中遗传到下一代的概率为:

个体杂交方式采用单点杂交方式, 其主要过程如下:

(1) 在染色体上随机选择一个交换点;

(2) 确定是在交换点前面部分或者后面部分的基因进行交换;

(3) 根据上述原则将两父本的染色体基因进行交换重组, 从而形成新的个体。

2.5 算法流程

改进后的混合遗传算法流程如下:

(1) 初始化。t←0进化代数计数器;T是最大进化代数;随机生成M个个体作为初始群体Population (t) ;

(2) 修正个体。使用贪心算法对个体进行优化和修正;

(3) 个体评价。计算Population (t) 中各个个体的适应度值;

(4) 选择运算。将选择算子作用于群体;

(5) 交叉运算。将交叉算子作用于群体;

(6) 变异运算。将变异算子作用于群体, 并通过以上运算得到下一代群体Population (t+1) ;

(7) 终止条件。判断t≦T:t←t+1转到步骤 (2) ;t>T:终止输出解。

3 算法仿真与结果分析

本文使用Cloud Sim[12]模拟了大规模云计算数据中心, 并对基于混合遗传算法的任务分配策略进行了仿真和测试。实验中模拟了一个包含1 000台主机的与计算数据中心, 对1 000个任务分配问题进行了仿真。1 000台主机和1 000个任务的数据为随机生成, 为有利于仿真, 数据完全按照Cloud Sim中主机和任务的量化标准生成。

3.1 算法正确性验证

虽然任务分配问题是NP完全问题, 在问题规模较大时得到最优解是非常困难的, 但在问题规模较小时还是可以得到最优解的。为了验证算法的正确性, 选取任务和主机都较少的情况进行验证, 实验选取的3个任务、5台主机的任务分配问题进行验证, 任务数据和主机数据如表1和表2所示, 任务分配的结果如表3所示。

由表3可以看出, 所有3个任务全部分配给了第三台主机。从表2可以看出第4台主机能耗较低, 但其计算能力较弱, 如果将任务全部分配给第四台主机就会出现资源争用的情况, 降低程序运行的效率, 为避免出现这种情况就必须开启其他主机, 这样却会使能耗大大增加;第二台主机也能够完成三个任务的计算, 但其功率相比第三台主机要大, 完成任务所需的能耗更大, 所以算法将三个任务全部分配给第三台主机是能耗最优的选择。

3.2 算法收敛效果比较

为了验证改进的混合遗传算法在解决任务分配问题是否具有更好的性能, 将其与基本的遗传算法和贪心算法做了比较, 实验结果如图2所示。

图2中三条线分别为混合遗传算法、基本遗传算法和贪心算法计算所得优化解, 因为本文中目标函数为能耗最低, 所以值越低, 说明该值越接近最优解。从图2中可以看出, 混合遗传算法搜索优化解的结果要远优于贪心算法和基本的遗传算法。贪心算法虽然开始时搜索局部优化解的速度较快, 但其对全局优化解的搜索能力却比较差, 基本遗传算法搜索全局优化解的能力要比贪心算法强, 但其搜索局部优化解的能力较弱, 所以向最优解收敛的速度较慢, 而混合遗传算法则结合了基本遗传算法和贪心算法的优点, 其收敛速度较快。在实验中使用50个任务, 1 000台主机, 混合遗传算法种群进化1 000代的耗时为2.7s, 基本遗传算法耗时1.8s, 贪心算法为0.3s, 算法执行时间有所增加, 但仍在可以接受的范围内。

3.3 仿真结果分析

Cloud Sim提供了资源的监测、主机到虚拟机以及虚拟机到任务的映射功能[13], 并且提供了能耗的仿真和计算模块, 可以方便地模拟主机或者虚拟机的能耗, 而且能够根据任务运行所占的资源量和所用时间给出任务执行所耗费的成本。

实验模拟云计算数据中心包含1 000台主机, 任务数量从0到1 000不等, 分别对随机任务分配算法、Cloud Sim能量感知任务分配算法[14]及基于混合遗传算法的任务分配算法的能耗和任务执行成本做了对比。对比结果如图3和图4所示, 从图3和图4的对比结果可以看出, 基于混合遗传算法的任务分配方式能够大大降低任务执行的总能耗, 并且由于充分利用了计算机的硬件资源, 避免了运行主机的空闲资源浪费, 所以大幅降低了任务执行总成本, 在任务总量越多时节能和节约成本的效果越明显。

4 结束语

本文使用基于混合遗传算法对云计算数据中心任务分配策略进行了优化, 优化后的任务分配策略能够有效地减少任务运行的总能耗, 减少任务运行的成本。这种任务分配策略在解决云计算的任务调度、负载均衡、节能减排、成本最小化等问题时有着良好的应用价值。

摘要：云计算中主机和任务的数量都是十分庞大的, 如何通过任务分配调度来减少成本开销和降低能耗是当前云计算和绿色计算领域研究的热点问题。根据云计算任务以及运行环境的特点, 将云计算任务分配问题抽象为多维多背包求解问题, 并采用改进的混合遗传算法对该问题进行求解。实验结果表明, 改进的混合遗传算法能够在较短的时间内找到问题的优化解, 并且根据该算法实现的任务分配策略能够有效地减少任务执行的成本开销和能耗。