基于改进量子遗传算法的入侵检测特征选择_刘晙
自动化测试
计算机测量与控制.2011.19(4) Com puter Measurement &C ontrol
·813·
收稿日期:2010-11-30; 修回日期:2011-01-10。
基金项目:河南省基础与前沿技术研究计划基金项目(082300410390)。
作者简介:刘 晙(1981-),男,湖北天门人,硕士,主要从事信息安全、软件技术及数据库方向的研究。
狄文辉,河南新乡人,教授,CC F 会员,主要从事数据库应用、计算机仿真和人工智能方向的研究。
文章编号:1671-4598(2011)04-0813-03 中图分类号:TP393
文献标识码:A
基于改进量子遗传算法的入侵检测特征选择
刘
,狄文辉
(河南机电高等专科学校计算机科学与技术系,河南新乡 453000)
摘要:针对入侵检测前必须分析输入数据的特征以及检测中数据维数较高的问题,根据入侵检测的特点,将特征选择问题作为优化问题来考虑,采用量子遗传算法对特征进行选择,充分利用其并行处理及全局搜索能力,提高数据分类质量、降低问题规模、消除冗余属性、加快数据处理速度;在KDD C UP1999数据集上进行实验,结果表明与遗传算法以及粒子群算法相比,该方法可以更有效地精简特征,提高分类质量。
关键词:特征选择;入侵检测;量子遗传算法;网络安全
Intrusion Detection Feature S election Based on
Improved Quantum Genetic Algorithm
Liu Jun ,Di Wenhui
(Depar tment o f Computer Science and T echno lo gy Henan M echanical a nd Eect rical
Enginee ring Co lleg e ,Xinxiang 453002,China )
Abstract :Analysis the characteristics of the input intrusion detection data ,and high er dimension s problem of intru s ion detection .Ac -cording to the ch aracteristics of in tru sion detection ,feature selection w ill be considered as an op timization p rob lem ,using quantum genetic al -gorithm to feature selection ,fu ll use of the qu antum genetic algorithm global search and parallel processing capabilities ,to eliminate redu n -dant attribu tes and reduce the scale of the problem and improve the data classification quality ,faster data processing speed .Data sets in KDD C UP1999Experimental results s how that genetic algorithms and particle sw arm algorithm ,this method can mo re effectively s tream line fea -tures ,improve the quality of classification .
Key words :Featu re selection ;intrusion detection ;quan tum genetic algorithm ;netw ork secu rity
0 引言
入侵检测是通过收集和分析网络行为、审计数据、安全日
志以及其它网络上可以获得的信息和计算机中若干关键点的信息,检查系统或网络是否存在违反安全策略的行为和被攻击的迹象[1]。特征选择是根据给定的准则从一组特征中挑选出一些最有效的特征以降低特征空间维数,无用的、冗余的以及最少使用的特征将被从特征集合中删除[2]。由于它是经典的NP -ha rd 问题,因而目前还没有高效的最佳特征选择算法[3-4]。
近年来研究者发现特征选择可以在保持原有网络数据信息完整性的基础上,去除其中的冗余特征,从而达到提高系统检测速度的目的。文献[5]中Jain 等人提出了诸如启发式搜索策略(heuristic sea rching stra teg ies )。文献[6]中K udo 等人提出了比启发式搜索更有优势的的随机搜索策略(sto chastic sea rching strateg y )。其后有使用遗传算法(G ene tic Algo -rithm ,GA )来自动选择适合特定攻击类型的属性集,利用遗传算法和前馈神经网络融合实现有效特征的选取,采用遗传算
法和支持向量机进行封装的方法进行特征子集的选择等[7-9]。
粒子群进化算法收敛速度虽然较快,但是收敛精度不高,而且容易早熟。文献[10]为了提高粒子群算法的收敛精度,提出使用免疫粒子群算法进行特征选择,在产生粒子时让粒子之间尽可能相异,以此来增加粒子的多样性,从而增加算法的收敛精度。然而在大规模数据集上的特征选择,这些搜索策略的计算资源耗用大,收敛速度慢,时间复杂度较高。而在文献[11]中提出的非搜索性策略,虽然其时间复杂度相对较低,但是所得到的特征子集中有较多冗余特征,严重影响了分类准确率。针对现有这些算法中所存在的缺点,提出了一种新的特征选择方法。将特征选择问题作为优化问题来考虑,使用量子遗传算法对特征进行选择,充分利用量子遗传算法的全局搜索及并行处理能力,消除冗余属性、降低问题规模、提高数据分类质量、加快数据处理速度。
1 相关概念概述
1.1 特征选择问题的数学模型
给定—个特征子集,F =[f 1,f 2,…,f N },N 是特征集合的大小,于是特征子集可以用一个二进制向量表示:s i =1表示第i 个特征f i 被选择,s i =0表示第i 个特征f i 不被选择。特征选择就是选择特征集合,使得:
G (Y )=max G (S ),Y S
(1)
其中:G 表示特征选择的评价函数,S 表示网络通信行为原始的特征集合,Y 表示选择的最优特征子集,Y S 。检测率(DR )和误报率(FPR )两个参数直接反映入侵检测算法的性
·814· 计算机测量与控制 第19卷能,分别设定1-DR和FPR作为检测精度的目标函数:
1-DR=1-
TP
T P+FP
=FP
T P+FP
(2)
FPR=
FN
T P+FN
(3)
其中,G表示正确检测到的异常数据样本数;F P表示被误报为异常的正常数据样本数;F N表示被检测为正常的入侵数据样本数。入侵检测的特征选择就是找到子集S＊S
S＊=ar gmin{G(X)}=a rgmin{[G1-D R(x),G FP X(X)]T}}
(4) 其中,S表示原始特征集合;G(·)表示包括两个最小化目标函数1-DR和FP R的向量函数。
1.2 量子遗传算法
量子遗传算法(QG A)是量子计算与遗传算法相结合的产物12]。在QG A中,染色体用量子位表示,一个量子位不仅仅表示0或1两种状态,而且同时表示这两种状态之间的任意中间态。这样用n个量子位就可以同时表示2n个状态,因而对于相同的优化问题,Q G A的种群大小可比传统G A小很多[13]。在Q G A中,一个量子位可能处于|1>或|0>,或者处于|1>和|0>之间的中间态,一个量子位的状态可表示为:
|ψ>=α|0>+β|1>(5) 其中α和β表示相应状态的概率幅,且满足下列归一化条件:
|α|2+|β|2=1(6) 在式(6)中,|β|2表示|1>的概率,|α|2表示|0>的概率。在QG A中,量子比特为最小信息单元,用量子比特编码的染色体称作量子染色体,第t代的量子种群表示为Q(t) =q t1,q t2,…,q t n,q t j为第t代种群中第j个量子染色体,其中n为种群规模,q t j描述为:
q j t=αt j1
βt j1
αt j2
βt j2
…
…
αt jm
βt jm
(7)
其中m表示量子比特的个数,j=1,2,…,n。
2 改进量子遗传算法的入侵检测特征选择方法设计
2.1 量子编码方案的设计
应用量子遗传算法首先面对的问题就是如何编码,同样编码也是设计量子遗传算法的一个关键步骤。它不仅决定了群体的表现形式,同时也确定了从群体的搜索空间变换到解空间的解码方法。编码方案是把问题的搜索空间中每个可能的点表示为确定长度初始特征群体。确定需要选择合适的字母表与串长。构成初始群体时选择的编码方式对算法的收敛性以及算法的效率有很大的影响。量子编码是最小字符集编码方案中的一种,它能包含最大的模式数,使得算法在确定规模的群体中能处理最多的模式,并且具有以下的优点:符合最小字符集编码方案原则,量子变异等操作易于实现;编码、解码操作简单。因此这种方法为我们所采用。当所求问题解的精度要求较高时,群体的字符串长度越长。精度要求较低时,字符串长度越短。在本文中我们考虑到种群初始化时编码的随机性,因此采用如下编码方案:
(8) 其中,m是种群规模,n是空间维数,rnd为(0,1)之间的随机数,θij=2π×rnd;(i,j=1,2,…,m)。
q i0=(co s(θi1),cos(θi2),…,cos(θin))(9)
q i1=(sin(θi1),sin(θi2),…,sin(θin))(10) 这两个位置分别对应量子态|0>和|1>的概率幅。为了表达方便,q i1为|1>态位置,q i0为|0>态位置。
2.2 适应度函数设计
遗传算法使用适应度函数来度量群体中的个体在优化计算中可能达到或者接近最优解的程度。适应度函数必须能够计算搜索空间中每个确定长度的特征群体的适应值。适应值高的个体遗传到下一代的概率相对较大,适应值低的则概率较小。合适的适应度函数对于构造良好的求解环境有很大的帮助。
特征选择的目的是找出分类能力最强的特征组合,需要一个定量准则来度量特征组合的分类能力。为了使特征选择算法独立于学习算法,考虑使用距离准则作为判据。各样本之所以能分开,是因为它们位于特征空间的不同区域。选择特征子集考虑类间距离越大、类内各样本间的距离越小,则分类效果越好,即适应性越好,更适应于所定义的生存环境能够更加提高IDS的整体性能。这个步骤将依据上一步生成的群体以及选定的适应性函数来求得群体中的最优解。
故定义式(11)为个体的适应度函数。
F(X)=S b-S w(11)
S b=∑
C i≠C j
||S i-S j||(12)
S w=∑
C
i
=C
j
=k
||X i-X j||(13)
S i=
1
n
∑
n
i
i=1
X i(14) 其中,n i表示属于这类的样本点个数。S b表示属于不同类别的类之间的欧式距离(S i∈C i,S j∈C j),S w表示属于同一个类的样本之间的距离(X i∈C i,X j∈C j)。对于一个类,使用均值向量来表示,均值向量可以通过式(14)求得。
2.3 量子门的更新
量子门的构造是QG A的关键问题,因为它直接关系到Q G A的性能好坏。在本文中,我们采用量子旋转门,即:
U=
co sθ-sinθ
sinθco sθ
(15) θ为旋转角。
2.4 变异算子
Q G A算法容易陷入局部最优,在许多情况下主要是因为种群多样性在搜索时的丢失。因此算法当中引入变异算子来增加种群的多样性,避免算法早熟收敛。本文改进的量子遗传算法中使用改进的量子变异操作,具体步骤如下:
1)以概率q m从种群中选取若干个个体;
2)对选中的个体按确定的概率确定多个或一个变异位;
3)对选中位量子比特的几率执行量子非门操作。
2.5 算法具体流程
基本算法流程如下:
Begin
(1)t→0,初始化种群Q(0)
(2)对初始种群中的各个体实施测量,得到一组状态P(0),并进行适应度评估
第4期
刘 晙,等:基于改进量子遗传算法的入侵检测特征选择 ·815·
(3)w hile 非结束条件do Begin a ) t →t +1
b ) 对Q (t -1)实施观测,对每个染色体观测,得到P (t ),并进行适应度评估
c ) 比较各解,选取局部最优解和全局最优解。
d ) 量子变异
e ) 利用基于量子门旋转策略更新Q (t ) E nd End
3 实验结果与分析
3.1 实验数据集与参数设置
为了对特征选择算法进行有效评价,本文所使用的实验数据是DA RP A (Defense A dvanced Research P ro jects A gency )为K DD (Know ledge Discover y and Data M ining )1999年竞赛建立的基准数据集。由于原始数据集太庞大,本文选择具有代表性的数据集,分别随机生成训练集、测试集与验证集,其中分别包含了6073、5564与10332条记录。在测试中,取100次运行算法的平均值作为实验结果。考察简单遗传算法(GA ),文献[10]的粒子群算法(P SO )和本文算法为特征选择算法时的性能差异。遗传算法的参数设置为:种群大小100,交叉概率为0.85,变异概率为0.1,采用赌轮选择。本文算法的参数设置为:种群大小为100,量子变异率为0.1,概率幅旋转角度delta =0.001＊p i ;两个算法中的遗传代数均设为500。粒子群算法的参数设置采用文献[10]的设置。图1 三种算法进化曲线对比
3.2 实验结果与分析
为了可以更为准确、清晰地验证本文所提出的特征选择方法性能,我们设计了以下两个实验。实验一:应用本文提出的方法在随机抽样后的数据集上,得到对应的特征子集,然后分别在训练集上基于所有41个特征和特征选择后的特征子集建立入侵检测模型。比较基于所有41个特征的入侵检测模型和基于特征选择后的特征子集的模型在检测时间以及检测准确率方面的性能。实验结果如表1所示。实验二:首先在数据集上应用本文所提出的特征选择算法,得到对应的特征子集,并基于该特征子集建立人侵检测模型,然后采用遗传算法和粒子群算法对同一训练数据集进行特征选择,最后分别对采用本文算法的入侵检测模型与应用遗传算法和粒子群算法的入侵检测模型在检测时间和检测准确率方面的性能进行比较。实验结果如图1,表2所示。
表1 特征选择前后检测时间以及检测准确率比较结果入侵检测方法检测时间
检测准确率所有特征特征子集所有特征特征子集DOS 1.0890.20183.4%98.3%PROBE 1.2140.26387.9%97.4%R2L 0.9970.19288.4%98.6%U2R
1.143
0.321
85.7%
98.0%
从表1中我们可以看出,基于本文所提出的特征选择方法的入侵检测模型在检测时间以及检测准确率方面的表现都要优于未经特征选择的入侵检测模型。
表2 三种算法性能比较
入侵检
测模型检测时间
分类准确率
本文算法PSO 算法GA 算法本文算法PS O 算法GA 算法DOS 0.210.35
0.45
98.3
94.2
93.0
PROBE 0.180.420.6197.595.894.6R2R 0.220.560.6598.994.797.4U2R
0.25
0.44
0.46
99.1
98.6
95.2
从图1、表2中可以看出,本文提出的特征选择方法和基本遗传算法以及粒子群算法所产生的特征子集作为分类样本的
分类准确率明显高于上述两种算法,并且差别很大;而在特征选择时间方面,本文提出的方法则是表现最好的。结合实验一、实验二的结果可以看出,本文提出的特征选择方法,有效地减少了网络数据信息的特征维数;在检测时间及检测准确率方面的表现明显优于未经特征选择的入侵检测模型,以及采用遗传算法与粒子群算法;可以看出本方法能够在保证较高的分类准确率的情况下,使特征选择的时间复杂度降低,较为有效地缩短特征选择的时间。
4 结束语
提出了一种用于特征选择的改进算法,和简单遗传算法以及粒子群算法相比。本文算法不仅可以实现全局收敛,而且算法可以在更大的解空间中进行搜索,在执行效率上比上述两种算法有一定的提高,能够在保证较高的分类准确率的情况下,使特征选择的时间复杂度降低,较为有效地缩短特征选择的时间,性能也有很大改善。
参考文献:
[1]B M u kherjee ,L T ,Heberlein Levitt .Netw ork Intrusion Detection
[J ].IEEE Netw ork ,2004,8(3):26-41.
[2]郑洪英,侯梅菊,王 渝.入侵检测中的快速特征选择方法[J ].
计算机工程,2010,36(6):262-264.
[3]于 泠,陈 波.入侵数据特征并行选择算[J ].电子科技大学
学报,2008,37(2):266-269.
[4]陈 友,沈华伟,李 洋.一种高效的面向轻量级入侵检测系统
的特征选择算法[J ].计算机学报,2007,30(8):1398-1408.
(下转第819页)
第4期包亚萍,等:基于权值协作和能量感知的频谱检测技术 ·
819·
图5 权值协作检测和O R协作检测ROC曲线
图6 去相关节点后虚警概率和检测概率ROC曲线
但权值协作和O R协作检测增益相差无几,而且一般C R系统给定的虚警概率较小。所以权值协作检测较O R有更好的检测性能。
6 结论
频谱感知是CR管理和共享等的技术前提,协作频谱感知为充分利用频谱、实现频谱动态接入和高效协作通信提供了技术保障[9]。本文构建了协作检测模型,对多个感知用户协作于认知系统中的情况进行了分析和比较,通过不同协作检测方案对检测性能进行了仿真研究。结果表明,当虚警概率较小时,权值协作能得到高检测概率,比O R协作获得近14%的检测概率,有效提高检测主用户的灵敏度。如何提高频谱感知的速度将是进一步研究的内容。
参考文献:
[1]Amir Ghasemi,E lvino S.Sousa.Collabo rative S pectrum S en s ing
for Opportunistic Acces s in Fading Environments[A].Firs t IEEE In ternational Sym posium[C].2005:131-136.
[2]Shridh ar M ub areq M ish ra,Anant S ahai,Robert W.Brodersen.
“C ooperative S ensing among Cognitive Radios[A].IEEE ICC 2006proceedings[C].1658-1663.
[3]Edward Peh,Ying-Chang Lian g.Optimization for C ooperative
S en sing in Cognitive Radio Netw ork s[A].W ireles s Commu nica-tions and Netw orking Conference,WC NC2007.IEEE[C].27-32,2007.
[4]M unehiro M ats ui,Hiroyuki Shib a,Kazunori Ak abane,et al.“A
cooperative sensing tech nique w ith w eighting based on distance be-tw een radio station s[A].14th Asia-Pacific Conference on Com-m unications[C].APCC,2008.
[5]Zheng Y,Xie X Z,Yang L L.Cooperative spectrum sensin g based
on S NR comparison in fusion center for cognitive radio[A].In ter-n ational C on feren ce on Advanced Compu ter Control[C].ICACC, 2009,27-32.
[6]Urk ow itz,H.Energy detection of u nknow n determinis tic signals
[J].In stitu te of Electrical and E lectronics Engineers(IEEE),New Yo rk,N Y,United S tates,1967,55:523-531.
[7]Bin S hen,Long-yang Huang,Chengshi Zh ao.Weighted Coopera-
tive S pectrum Sensin g in C og nitive Radio Netw orks[A].2008.
ICCI T08.Third International Conference[C].2008,1(1): 1074-1079.
[8]W ang L F,Williams C,Doufexi A,et al.W eigh ted cooperative
sen sing for pulse radar signals[A].Evaluating cu rren t Research and Development,2008IET S emin ar on[C].6-6Nov.2008, 1-5.
[9]孙 磊,安建平.认知无线电———智能的无线通信技术[J].计算
机测量与控制,2007,5(11):1419-1421.
(上接第815页)
[5]Jain A K,Zongker D.Feature s election:Evaluation,application,
and small s amp le perform an ce[J].IEEE Transactions on Pattern Analysis and M achine In telligence,1997,19(2):153-158. [6]Kudo M,S klansky https://www.sodocs.net/doc/0a4803380.html,parison of algorithms th at select leatu res
for pattern classifiers[J].Pattern Recognition,2000,33(1): 25-41.
[7]张 昊,陶 然,李志勇.基于KNN算法及禁忌搜索算法的特征
选择方法在入侵检测中的应用研究[J].电子学报,2007,37
(7):1628-1632.
[8]俞 研,黄 皓.基于改进多目标遗传算法的入侵检测集成方法
[J].软件学报,2007,18(6):1369-1378.
[9]蒋加伏,吴 鹏.基于多目标进化算法的入侵检测特征选择[J].
计算机工程与应用,2010,46(17):110-112,138.[10]倪 霖,郑洪英.基于免疫粒子群算法的特征选择[J].计算机
应用,2007,27(12):2922-2924.
[11]M itra P,M urthy C A,Pal S K.Un supervised feature selec-
don using featu re similarity[J].IEEE Trans Pattern Recognition and M achine Intelligence.2002,3(14):301-312.
[12]Han K H,Kim J H.Quan tum-Inspired Evolutionary Algorith m
fo r a Clas s of C om binatorial Optimization[J].IEEE T ran saction s on Evolutionary Computation,2002,6(6):580-593.
[13]杨俊安,庄镇泉.量子遗传算法研究现状[J].计算机科学,
2003,30(11):13-15.
[14]Nikola Kasabov.Neuro,Genetic and Quantum In spired Evolving
Intelligent Sys tems[C].International S ymposium on Evolving Fuzzy Sys tems,September,2006,63-73.
关于量子遗传算法(QGA)
关于量子遗传算法的杂七杂八 遗传算法确实太有名了，无论是数学建模的培训中还是机器学习的项目中，经常性能看到遗传算法（GA）活跃的身影，其用途十分广泛，而且MATLAB或者是Python的实现遗传算法功能的工具箱也很多，笔者就一度使用北卡罗莱纳大学提供的免费工具箱实现了对于BP神经网络的初始化权值与阈值的优化，效果十分不错，而且实现起来不那么费劲，所以还是挺受好评的，对于写毕业论文的同志而言，如果实在不知道强行套用第三方算法对于原本的算法进行升级该怎么做，有两个万金油组合，一个是AHP，另一个就是几乎无所不能的GA，当然了，如果需要对于矩阵进行降维操作首选一定是PCA。 1 关于GA算法的种种 1.1简介 顾名思义，学过高中生物的都应该可以理解“遗传”是什么，染色体变异、染色体交叉等术语应该也能够大概知道是什么意思。其实遗传算法主要就是模拟这一个过程。 不过，笔者觉得本算法中的核心部分中的变异与交叉的情节，其实达尔文这个姐控的贡献不是很大，最早提出相关的概念完成了相关的建模的是孟德尔 所谓物竞天择适者生存，这个对于现实生活中的生物适用，对于具有特定含义的矩阵肯定也是适用的，当然了，反映他们到底多么“适应”的函数就是所谓的适应度函数，虽然关于适应度函数的取法现在并没有十分固定的一以贯之的通用公式。相对的，一些套路多有相似之处的算法中的概念也大都没有万用公式，诸如ACA中的营养素函数等，这些算法仍然有待提升，这也是经常能在国内的中文核心期刊上依然能够看到不少惊为天人的论文的原因。因为中国特色——灰色模型、AFSA等算法第一个提出者是中国人。 1.2四个基本概念 遗传算法中，一个基本单位为“个体”，一个种群（系统）中拥有好多个体。每个个体携带两个内容：染色体与适应度。 当然了，这个时候上述的这些概念根本没有机器学习的含义，而全然为生物的含义 或者用生物上的话来说，每一个生物都有染色体，染色体决定了他们表现出来的性状是怎样的。所以说，染色体决定了每一个生物的肥瘦程度。 因此我们建立以下对应关系： 整个牧场对应的是一个种群，在机器学习中可以理解为具有实际项目含义的构成所有矩阵的cluster 一头羊相当于生物钟的一个个体，在机器学习的大背景下可以理解成矩阵，就是MATLAB里面的mat文件 某头羊决定肥瘦程度的染色体也就就是该个体的染色体，在机器学习的大背景下可以理解成mat文件中的某一行或者是某一列。题外话，MATLAB中相当一部分函数在编写的时候不知道是出于怎样的考虑，它们的参数有的时候行跟列的位置竟然是反的，于我们的习惯有很大
一种改进的遗传算法
第17卷第3期 辽阳石油化工高等专科学校学报Vol.17No.3 2001年9月 Journal of Liaoyang Petrochemical College September2001 一种改进的遗传算法 王亮申 王文友 吴克勤 江远鹏 谢 荣 (辽阳石油化工高等专科学校机械系,辽阳111003) 摘 要 给出的适应值标定公式能够解决对个体选择压力和标定后适应值非负问题. 对多极值函数的遗传算法所提出的改进措施可以增加群体的多样性,避免算法“早熟”,过早 陷入局部最优. 关键词 遗传算法;适应值标定;早熟 中图分类号 O224 由美国密执安(Michrgan)大学的Holland教授等人在1975年创立的遗传算法(G enetic Algo2 rithms简称G A),是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法.经过后人的不断改进使得遗传算法更加完善.由于遗传算法求解复杂优化问题的巨大潜力及其在各个领域(如布局优化问题、交通问题、图像处理与识别、结构设计、电力系统设计、可靠性计算等)的成功应用,这种算法越来越被人们所接受. 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其它进制码)即基因(gene),若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异运算,经过多次重复迭代(即世代遗传)直至得到最后的优化结果.习惯上,适应度值越大,表示解的质量越好.对于求解最小值问题可通过变换转为求解最大值问题.遗传算法是一种高度并行、随机、自适应搜索算法. 尽管遗传算法有许多优点,也有许多专家学者对遗传算法进行不断研究,但目前存在的问题依然很多.如(1)适应值标定方式多种多样,没有一个简洁、通用方法,不利于对遗传算法的使用; (2)遗传算法的“早熟”现象即很快收敛到局部最 收稿日期:2001-06-27优解而不是全局最优解是迄今为止最难处理的关键问题;(3)快要接近最优解时在最优解附近左右摆动,收敛较慢. 1 改进方法 1.1 适应值标定 初始种群中可能存在特殊个体的适应值超常(如很大).为了防止其统治整个群体并误导群体的发展方向而使算法收敛于局部最优解需限制其繁殖;在计算临近结束,遗传算法逐渐收敛,由于群体中个体适应值比较接近,继续优化选择困难,造成在最优解附近左右摇摆,此时应将个体适应值适当加以放大,以提高选择能力,这就是适应值的标定.文献[1]提出的标定方法有两个计算公式,不利于使用;文献[2]的标定方式虽然限制了适应值范围但将最大最小值颠倒.此外象幂律标定、对数标定等亦有应用.本文针对适应值标定问题提出以下计算公式. f’= 1 f max-f min+δ (f+|f min|) f′—为标定后的适应值;f—为原适应值;δ—为在(0,1)内的一个正实数,目的是防止分母为零和增加遗传算法的随机性;|f min|—是为了保证定标后的适应值不出现负值。
毕业设计--基于量子遗传算法的函数寻优算法设计
毕业论文（设计） 题目：基于量子遗传算法的函数寻优算法设计学院：数理与信息学院 学生姓名： 专业：计算机科学与技术 班级： 指导教师： 起止日期： 2014年11月16日至2015年6月12日 2015 年5 月13日
基于量子遗传算法的函数寻优算法设计 摘要 量子遗传算法(QGA)是20世纪90年代后期兴起的一种崭新的遗传进化算法。该算法主要是将量子计算的概念引入其中，将量子的态矢量表达引入了遗传编码，使一条染色体可以表达多个信息态的叠加，同时利用量子旋转门实现染色体的演化，实现了目标解的进化。相比传统遗传算法，量子遗传算法能够在较小的种群规模下，快速的收敛到全局最优解。 本文首先介绍了量子遗传算法的基本原理与算法结构，然后对量子遗传算法提出疑问。虽然量子遗传算法的优化性能大大优于传统遗传算法，但是，对于一些多峰函数的优化问题，该类算法依旧容易陷入“局部最优”。在实际的应用中有很多优化问题都是多变量的连续优化问题，现有的量子遗传算法不能有效的解决这些问题。针对量子遗传算法容易陷入局部最优和未成熟收敛的缺陷，我们提出了一种新的优化算法——含有退火操作的量子遗传算法，该优化算法能够以可变的概率选择性地接受恶化的优化函数解，使种群解集的进化方向改变，不在依靠当前解进行遗传演化。从而使算法不易“早熟收敛”。而且在该算法中加入了全干扰的量子交叉操作，使各染色体能进行遗传信息的交换，使种群染色体更具有代表性。最后根据改进后的方案，对改进的量子遗传算法进行了数值仿真。有效地证明了改进算法在函数寻优方面的优越性。 【关键词】量子遗传算法，量子编码，退火思想，量子交叉，函数寻优
遗传算法基本原理及改进
遗传算法基本原理及改进 编码方法： 1、二进制编码方法 2、格雷码编码方法 3、浮点数编码方法。个体长度等于决策变量长度 4、多参数级联编码。一般常见的优化问题中往往含有多个决策变量，对这种还有多个变量的个体进行编码的方法就成为多参数编码方法。多参数编码的一种最常用和最基本的方法是：将各个参数分别以某种方式进行编码，然后再将它们的编码按照一定顺序连接在一起就组成了标识全部参数的个体编码。 5、多参数交叉编码：思想是将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏掉。在进行多参数交叉编码时，可先对各个参数进行编码；然后去各个参数编码串的最高位连接在一起，以他们作为个体编码串前N位编码，同上依次排列之。
改进遗传算法的方法： （1）改进遗传算法的组成成分或实用技术，如选用优化控制参数、适合问题的编码技术等。 （2）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。 （3）采用混合遗传算法 （4）采用并行算法 （5）采用非标准的遗传操作算子 改进的遗传算法： （1）分层遗传算法 （2）CHC算法 （3）messy遗传算法； （4）自实用遗传算法（Adaptive Genetic Algorithm） （5）基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA）。 （6）并行遗传算法（Parallel Genetic Algorithm） （7）混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火算法相结合的混合遗传算法。 解决标准遗传算法早熟收敛和后期搜索迟钝的方案 （1）变异和交叉算子的改进和协调采用 将进化过程划分为渐进和突变两个不同阶段 采用动态变异 运用正交设计或均匀设计方法设计新的交叉和变异算子 （2）采用局部搜索算法解决局部搜索能力差的问题 （3）采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题 （4）收敛速度慢的解决方法； 产生好的初始群体 利用小生境技术 使用移民技术 采用自适应算子 采用与局部搜索算法相结合的混合遗传算法 对算法的参数编码采用动态模糊控制 进行未成熟收敛判断
量子遗传算法
量子遗传算法 1.遗传算法 遗传算法是一种模拟达尔文生物进化论和遗传变异的智能算法。这种算法具有鲁棒性（用以表征控制系统对特性或参数扰动的不敏感性）较强，实现的步骤规范、简单通用等优点，在人工智能、多目标决策、社会及经济等领域都有大量运用。但一般遗传算法存在一定得局限性：收敛速度慢、迭代的次数多，易过早收敛，容易陷入局部最优解。 2.量子计算 量子计算为量子力学与信息科学的综合交叉学科。量子计算具有量子力学的并行性，计算速度更快；同时，量子状态多种多样，在进行最优解的搜索时极少陷入局部的极值。 3.量子遗传算法 量子遗传算法将量子的态矢量引入遗传算法，利用量子比特的概率幅应用于染色体的编码。一条染色体是多个量子状态的叠加。并使用量子旋转门实现染色体的变异更新。因此量子遗传算法具有迭代次数少，运行速度快，能以较少种群进行遗传变异，搜索范围广，难以陷入局部的极值等优点。 4.操作步骤 1）运用量子比特初始化父代染色体 2）在量子遗传算法中，染色体采用量子位的概率幅进行编码，编码方案如下： 1212cos()cos()cos()sin()sin()sin()i i ik i i i ik P θθθθθθ??=??? ? k j n i rand ij ,...,2,1,,...,2,1,2==?=πθ 3）对初始化种群中的每一个个体进行测量。 4）对每个测量值进行适应度的评估，以适应度来选择最优个体，进行遗传变异。 5）使用量子旋转门进行下一代个体的更新，量子旋转门为逻辑门中一种较为常用的方法，具体表示为： ???? ? ?-=i i i i u θθθθθcos sin sin cos )( 6）进行迭代1+=y y 7）达到终止设定条件，输出最佳个体，得到最优解。
改进的混沌遗传算法
改进的混沌遗传算法 李辉 (计算机学院2004级研究生 04720746) 摘要：混沌遗传算法(chaos genetic algorithm, CGA)是基于混沌优化的遗传操作,将使子代个体均匀地分布于定义空间,从而可避免早熟,以较大的概率实现全局最优搜索.与传统的遗传算法相比较, CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具，但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的优点，大大提高了优化的效率。 关键词：遗传算法混沌混沌优化 Abstract：Chaos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditional GA,The results demonstrated that the CGA’s on-line and off–line performance was all superior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower convergence and the premature restrict its efficiency.And CGA which has the two strongpoint has promoted is efficiency in optimization. Key words: genetic algorithm chaos chaos optimization 1 引言： 遗传算法(GA)最早由美国Michigan大学的John Holland教授提出，通过模拟自然界中的生命进化过程，有指导地而不是盲目地进行随机搜索，适用于在人工系统中解决复杂特定目标的非线性反演问题。De Jong首先将遗传算法应用于函数优化问题的研究，他的工作表明在求解数学规划时，GA是一种有效的方法。但对于大型复杂系统，尤其是非线性系统优化问题的求解，GA仍有许多缺陷，如无法保证收敛到全局最优解，群体中最好的染色体的丢失，进化过程的过早收敛等。 混沌是自然界中一种较为普遍的现象，具有“随机性”、“遍历性”及“规律性”等特点，在一定范围内能按其自身的“规律”不重复地遍历所有状态的。在搜索空间小时混沌优化方法效果显著，但搜索空间大时几乎无能为力。 混沌遗传算法(CGA)的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值范围，然后把得到的混沌变量进行编码，进行遗传算子操作。再给混沌变量附加—混沌小扰动，通过一代代地不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。 2 传统遗传算法 传统遗传算法： population old_pop,new_pop;/*current and next population*/ int pop_size,generation; float p_cross,p_mutation; /*prob. Of crossover & mutation*/ 1 old_pop=initial random population={ind1,ind2,….indpopsize} 2 while(generation