基于链式智能体遗传算法的轮询式多准则特征选择算
法的研究1
李勇明，曾孝平，覃剑
重庆大学通信工程学院，重庆（400030）
E-mail：lymcentor@https://www.doczj.com/doc/3211879255.html,
摘要：特征选择是复杂模式分类系统中重要的预处理过程。本文针对filter模式下传统遗传算法特征选择精度不高，wrapper模式特征选择时间代价较高的缺点，提出了一种新的特征选择算法。该算法设计了搜索性能较好的链式智能体遗传算法为搜索算法，引入多个评价准则进行轮询式选择。实验将本文算法与filter模式下多种单准则特征选择算法以及wrapper模式下特征选择算法进行了比较。实验结果表明，本文算法具有比filter模式下单评价准则选择精度更高的特点，同时选择时间代价远远低于wrapper模式下的特征选择算法，因此，该算法可用于设计实用的高识别正确率的模式分类系统。
关键词：特征选择；遗传算法；链式智能体；轮询式；多准则
1 引言
特征选择是复杂模式分类系统中重要的预处理过程。在模式分类系统中,输入的数据往往含有大量的特征,但是只有其中少部分特征对分类有关,大量无关或作用较小的特征会造成“维数灾难”并降低信噪比。算法对于维数过高的情况会变得计算能力迅速下降。如果从中选择少量非常有用的特征作为特征子集,一些非常简单的分类器也可能获得很好的效果。因此,特征选择对于提高分类效率是非常重要的[1]。
特征选择方法的选择模式有filter模式和wrapper模式。前者采用预先设计的评价准则来指导选择，具有速度较快的特点。国内外许多学者设计了很多种评价准则进行特征选择算法的研究，取得了明显的效果[2-7]。但是，正如Ron Kohavi 所说，filter模式下的评价准则并没有考虑到不同分类算法的不同特点，不同待选特征集特点，因此无法全面评价特征子集的好坏，从而使得普适性较差，分类精度较低。基于此，他提出了wrapper模式的特征选择算法，并基于ID3和Na?ve-Bayes两种分类器进行了wrapper模式的特征选择算法的研究[8]。随后，国内外都进行了相关的研究，改进的地方主要是在搜索算法和分类算法两个方面，搜索算法如relief法、focus法、顺序法、遗传算法、粒子群算法等，分类算法如BP、ID3、Bayes、RBF、SVM等[9-11]。但是，由于wrapper模式每次选择子集后都需要进行学习训练, 这种方法非常耗时，因此对于许多模式分类系统的设计来说，显得难以实用。Huang Yuan提出了一种混合模式的特征选择算法，其大体思路是先采用filter模式进行特征选择，然后将得到的特征子集再用wrapper模式进行特征选择[12]。国内也有学者做了相似的研究[13-14]。这种方法可以通过filter模式大大减少特征维数，从而减少wrapper模式下特征选择的难度和运算时间，同时wrapper模式也可以使得最终特征子集的选择精度较高，尤其是对超大维数的特征选择（例如基因特征选择）效果是非常明显的。但是，这种方法仍然需要进行wrapper模式的特征选择，对于一些时间代价要求较高的特征选择问题来说就显得不太实用。例如文本识别、医学图像识别、运动目标识别等，其相关的特征选择问题都具有维数中等（大致在10－100维间）、特征分类能力相差不明显、特征集复杂、时间代价要求低等特点。此外，该混合模式的特征选择算法在采用filter模式进行特征选择时很可能将最佳特征子集中的某些特征给丢失掉，然后采用wrapper模式进行特征选
1本课题得到国家自然科学基金（30570473）和重庆市信息产业发展资金（200501022）的资助。
择时再也无法将这些丢失掉的特征找回，影响了特征选择精度。
从上面的研究可以看出，1、wrapper 模式特征选择精度较高，但耗时太大，无法满足一些对时间代价要求较高的场合；2、filter 模式的单个评价准则不能全面评价特征子集的好坏，选择精度较低，有待改进。既然单个评价准则无法全面评价特征子集的好坏，可以考虑综合多个评价准则来进行特征选择。我们在以往研究中采用了一种方法是：引入了多个评价准则，分别在filter 模式下通过遗传算法进行特征选择，将各自选择得到的最佳特征子集进行多票投选得到最终的最佳特征子集。该方法取得了比单个评价准则filer 模式特征选择更高的选择精度，并被成功的运用到了尿沉渣图像识别当中[15]。但是，随着引入的评价准则的数量增多，该方法的时间代价成倍增长。假如每一种评价准则进行选择所需时间代价一样的话，那么总共需要m 倍于单评价准则的特征选择算法，m 为评价准则数目。基于此，在保证选择精度的前提下，本文提出了另一种多准则选择算法－轮询式多准则链式智能体遗传算法的特征选择算法。该算法的主要思路是选择第一种评价准则进行特征选择， 当达到一定的选择精度后，再依次选择下一个评价准则进行特征选择，直到所有的评价准则全部遍历完为止。这个思路具有以下好处：1、从第一种评价准则过渡到后面的评价准则的过程部分类似于前述的Huang Yuan 提出的方法，逐步去掉冗余度较高的特征。但是本文方法中，前一种评价准则选择得到的是一个特征子集群（即种群），是一个近优解候选集，通过后面的特征选择，可以找回在前面的选择中丢掉的某个或某些优良特征；2、本文算法拚弃了wrapper 模式特征选择，可以大大减少时间代价；3、当采用了第一个评价准则进行特征选择后，将得到一个近优解群，因此后面的评价准则进行特征选择所需时间将大大减少，所以本文算法所需的时间代价将与单个评价准则所需的时间代价相当。
2 轮询式多准则特征选择算法的研究与设计
2.1 轮询式多准则思想
2.1.1 评价准则的一致性与偏离性
filter 模式下的评价准则具有和wrapper 模式下的评价准则（即识别率）非常强的一致性，对特征子集的选择指导方向是一致的。这里，以三种filter 模式下的评价准则为例加以说明（为了方便描述，这里是在两类识别的情况下加以讨论，多类问题原理一样）。 1) 评价准则1及其适应度函数
评价准则1所对应的适应度函数为：11
()2N
b
i w
i S
fitness corr S =
=
?∑。其中，
()2
12b S m m =?， ()()2
2
_1_2w M M S σσ=+，N 为特征数，1m 为某特征下类别1的样本的
均值，2m 为某特征下类别2的样本的均值，2corr 为特征间的相关度。_1M σ为某特征下类别1的样本的方差，_2M σ为某特征下类别2的样本的方差。
从上面的式子可以看出，类间方差表示类与类之间的距离，希望它们越大越好。类内方差表示了某特征下同类样本的差异，希望此差异越小越好。满足这两个要求越好的特征子集就越优良。显然，这样的特征子集也越可能带来更高的识别正确率。 2) 评价准则2及其适应度函数
评价准则2所对应的适应度函数为：'
'
21
()2N
b i w
i S fitness corr S =
=
?∑，其中，
'12b
S m m =?，()()
(
)
1
2
2
2
'_1_2w
M M S σσ=+。
从上面的式子可以看出，类间标准差表示类与类之间的距离，希望它们越大越好。类内标准差表示了某特征下同类样本的差异，希望此差异越小越好。满足这两个要求越好的特征子集就越优良。显然，这样的特征子集也越可能带来更高的识别正确率。 3) 评价准则3及其适应度函数
评价准则3所对应的适应度函数为： []31
()2N
b
i
i fitness tr S corr =
=
?∑，其中，
[]2
1
c
b i i i tr S n m m ==?∑，N 为特征数，i m 为某特征下i 类样本的均值，m 为某特征下
c 类
所有样本的均值，i n 为i 类样本数。
从上面的式子可以看出，该类间准则基于迹的准则，最大化了类间方差，也就最小化了类内方差。显然，这样的特征子集也越可能带来更高的识别正确率。
由上面的分析可知，filter 模式下的评价准则对特征子集选择的指导与特征子集的的真正好坏是有一定的一致性的，即变化大方向是一致的，这就是一致性原理，也是filter 模式特征选择算法得以应用的原因。
但是，不同的评价准则是人们对于模式分类的不同层面的理解而设计出来的，它们反映了趋势。随着评价准则的不同，特征子集的适应度函数是有所不同的，计为()i f x ，i 是指i 个评价准则。通过这些评价准则选择得到的特征子集送入分类器进行识别将得到其所对应的识
别率，因此建立了适应度函数值与识别率之间的映射关系，计为()()
i h f x ，令(
)i h f 映射
算子为()i q 。假设特征子集为自变量，其所对应的真正识别率为因变量y ，映射关系为()g ，则有()y g x =。()g x 显然与()()()()1i n q x q x q x L L 中的任何一个都不同，这也是为什么
filter 模式选择的特征子集与wrapper 模式选择的常常不一样的原因，也是前者选择的特征子集所获得的识别率较低的原因。因此，假设基于第i 个评价准则进行特征选择，即使得到了该适应度函数()i f x 的全局最优值，但对于真正的适应度函数()g x 来说，也是一个近优解或者局部最优解，识别率自然较低。参见图1，()1q x 和()2q x 表示通过两个评价准则建立的特征子集与识别率间的函数关系，()g x 表示特征子集与真正对应的识别率之间的函数关系。
123,,x x x 分别表示使得这三个函数取全局极值的最优解，即最佳特征子集。从图上，我们可以
看出()1q x 、()2q x 与()g x 的偏离性。假如使用评价准则1进行特征选择，其找到的最好的特征子集应为1x ，其识别率()1g x 较低。
图1 评价准则偏离性示意图
2.1.2 轮询式多准则思想的提出
基于此，根据最优化原理，为了在搜索过程中跳离局部最优解，可以采用多个评价准则，进行轮询式特征选择，这可以有利于跳出单个评价准则所寻找到的局部最优解。综合多个评价准则进行选择，可以充分利用多个评价准则的指导信息，使选择更准确，更稳定。
轮询式多准则选择的算法基本步骤：
表1 轮询式多准则思想
Step1：采用评价准则1进行特征选择，满足松弛停止条件即转向Step2； Step2：采用评价准则2进行特征选择，满足松弛停止条件即转向Step3； Step3：重复上面的操作直到最后一个评价准则n ，满足紧致停止条件结束。
注：这里的松弛条件是指并不严格的停止条件，满足获得一个近优的最佳特征子集群即可，其依据是：1、避免选择丢失一些重要特征，陷入局部极值不易跳出；2、根据评价准则的一致性。
2.2 搜索算法研究
本文引入了一种链式智能体遗传算法作为搜索算法(CAGA)，该算法将个体组织成为一个链式智能体结构，每个遗传个体被看成一个智能体与其他智能体相互交换信息，相互竞争和协作，以便于获得最优解。
定义 将位置()1,i 的智能体表示成1,i L ，1,2......i popsize =。popsize 为初始种群中
智能体的数目。
1,i L 的邻域为1,i Nbs 。 {}1,1,1
1,2i i i Nbs L L =。其中
1111i i i popsize i ?≠?=?=? 121i i popsize
i i popsize +≠?=?=?
2.2.1 动态邻域竞争选择
邻域竞争选择的原理叙述如下：设竞争选择在循环链上从左至右依次进行，当前智能体为
1,t i L ，其邻域为1,i Nbs ，{}1,1,1
1,2t
t i i i Nbs L L =， 1,2......i popsize =。1,t
i L 的更新
方法如式(1)：
()()
()
()()()
()()()
1,1,1,1,11,21,1,1,1
1,11,21,11,11,1,1,1,21,11,21,21,21,max ,max ,&max ,&t t t
i i
i i i t t t
t i i i i i i i i t
t t
t
i i i i i i i i L L fitness L fitness L L L L L L L L fitness L fitness L L L L L L L fitness L fitness L ??
=>????
==>????==>???
?
o o
(1)
)
识别率
)
式(1)中的o 表示智能体间的竞争运算。设智能体
1,t i L 与1,1t i L 竞争，则有：
(
)1,,1,2,,t
t t t t i i i i j
i length L c c c c =
K
K
，
()1,1
1,11,2
1,1,t t t t t i i i i j
i length L c
c c c =K K ，
,t i j c 表示位置为()1,i 的智能体的第j 个基因，1,t i j c 表示位置为()1,1i 的智能体的第j 个基因，
length 为单个智能体的基因数目即特征数。例如竞争运算1,1,1t t
i i L L o 可表示如下：
()t t t t
i,j i,j
i,j i1,j t t t
i,j i,j i1,j
c =c c =c c =U 0,1c c ???≠?? (2)
()U 0,1表示在(0,1)区间均匀分布下产生的随机数。
链式邻域竞争策略的步骤：
step1：定义空间为()12×的寄存器temp ， ()(
)
1,1,11,2,
max ,t
i i i temp L L L ←；
step2：根据式(1)来更新
1,t
i L ；
step3：判断i popsize =是否成立，如成立，则进入交叉阶段，否则，i i 1←+，转到step
1。
对于(
)
1,11,2max ,i i L L 的计算，我们采用了动态竞争策略，其主要思想简述如下。设
()1,1,1
1,2
max ,i
i i Max L
L =。在竞争过程中，竞争过程按照升序的顺序进行，当第1个智能体经
过竞争后将被立即更新。设第i 个智能体在竞争前表示为1,pre
i L ，竞争后表示为1,post
i L ，因此1,i Max 可表示为式（6）：
()()
()1,
1,1
1,1,11,1
1,11,1max ,1
max ,max ,popsize popsize pre pre L i post post
i L popsize post pre i i L L i Max L L i L L L else
+??+?=??==????
（3）
2.2.2 邻域自适应交叉
在交叉过程中，交叉概率c p 是自适应的。相应的公式如下：
1
'
(,)'max max
'1t GH i i t
i ave
t t c ave t
ave
f f f f p f f f f ??????
≥??
=?????
（4）
式中，()
',GH i i 为1,t i L 和1,i Max 的海明距离，1,i Max 为1,i Nbs 中适应度值较大的个体，'
i
f 为当前个体1,t
i L 的适应度值，'f 为1,t
i L 和1,i Max 适应度值中较大的适应度值，max t
f 为本代个体
的最大适应度值，t
ave f 为本代个体的平均适应度值。
交叉的具体操作是：产生一个0到1之间的随机数()0,1U 与c P 比较，确定1,t
i L 和1,i
Max 是否进行交叉，过程如下：
()() 0,10,1c
c
U P U P
≥??交叉不变 （5）
进行交叉的一对父代，随机在同一基因位进行交换，生成子代个体。 2.2.3 自适应变异
设变异概率为m p ，则()()0,10,1m m U p U p
≥??
变异不变。通常来说，m p 与染色体长度有关，m p 可由下式决定：1m p length =。
2.3 本文算法总结
综合上述研究的评价准则和搜索算法，现完整给出本文算法。算法流程如下：
表2 本文算法流程
Step1：种群生成； %每个遗传个体代表一个特征子集，1表示特征被选中，0表示特征未被选中 Step2：根据评价准则构造相应的适应度函数，计算遗传个体适应度值； Step3：根据适应度值对遗传个体进行动态邻域竞争选择； Step4：对遗传个体进行邻域自适应交叉； Step5：对遗传个体进行自适应变异；
Step6：判断是否是最后一个评价准则，若是，则判断是否满足紧致停止条件，若满足，则进行Step7，若不满足，则转向Step2；若不是，则判断是否满足松弛停止条件，若满足，则进行Step7，若不满足，则转向Step2。
Step7：判断是否使用完最后一个评价准则，若是，则输出最佳特征子集；若不是，则采用下一个评价准则，然后转向Step2。
如上面的算法可以看到，多个评价准则是轮询式采用的。利用评价准则的一致性，前面的评价准则可为后面的评价准则提供更好的特征子集群（即较好的种群），既为后面评价准则提供了较好的“初始种群”，也减少了后面评价准则的选择时间；利用评价准则的偏离性，后面的评价准则可更好的对前面的评价准则进行补充，并且有利于跳出前面的评价准则可能陷入的局部最优解。此外，就搜索算法而言，CAGA 引入了链式智能体结构，智能体邻域降为2个智能体，减小了计算代价，并减小了局部极值过渡扩散的可能性，同时引入了自适应交叉和变异操作，加快了搜索速度和精度。
3 实验结果与分析
为了验证本文算法的性能，本文组织了两个实验加以验证。第一个实验主要验证本文算法所采用的搜索算法（CAGA ）的搜索性能以及其用于特征选择的性能。第二个实验主要验证结合CAGA 的本文算法的特征选择性能。
3.1 搜索算法性能测试实验
我们将CAGA 与其它四种有代表性的遗传算法进行了比较，它们分别是：基于优良个体
保留策略的简单遗传算法（SGA ），自适应交叉、变异概率的遗传算法（AGA ）（参见文献[16]），海明交叉的遗传算法（HMGA ）（参见文献[17]），网格式多智能体遗传算法（MAGA ）（参见文献[18]）。
3.1.1 比较CAGA 与其它算法的函数优化能力
本文作者选用2个典型的基准函数来测试五种遗传算法的函数优化能力。这2个函数均为复杂多峰函数。现在比较五种遗传算法对这2个函数求全局最小值的性能。
()()()
()
()()()
12112
2
f1,*sin sqrt abs *sin sqrt abs x x x x x x =??，1
2
[-500,500],x x
∈
()()
(
)(
)
()()(
)()
121212 0.5*cos 2*pi*+cos 2*pi*+20+exp(1)
f2,20exp -0.2*sqrt 0.5*^2+^2exp x x x x x x =??，12[-32,32],x x ∈
f1和f2都是多峰函数，f1的最小值为0，f2最小值为-837.9。
实验参数说明：五个算法都采用了精英保留策略，种群大小都为64，自适应停止条件中，都设定K ＝30。由于所选函数的维数都不高，CAGA 的变异概率为0.05；SGA 的交叉概率为0.95，变异概率为0.05；AGA 的变异概率为0.05，HMGA 的变异概率为0.05；MAGA 的交叉变异概率都为0.1。比较的性能参数有四个：
平均最小值(MIN)：评估50次后的统计平均最小值；最优解出现平均代数(G1)：评估50次后的最小值第一次出现的代数的统计平均；平均遗传代数(G2)：评估50次后的统计平均遗传代数；平均执行时间(T)：评估50次后的统计平均执行时间。测试结果如表3 所示。
表3 五种遗传算法的函数优化性能比较表
函数 性能参数 CAGA
SGA
AGA HMGA MAGA
MIN -837.8658 -706.0390-747.7160-737.0889-828.2973 G1 112.2200 44.9800 65.5200 68.4400 117.7143 G2 142.2200 73.4200 93.6800 95.8000 147.7143 f1
T 14.07406 0.5575 0.65468 4.13062 12.93406 MIN 8.8818e-016 1.3519 4.2009 5.3490 9.0894e-006 G1 76.9400 122.460041.2000 55.2800 65.6939 G2 106.9400 151.340070.2000 84.2800 95.6939
f2
T 10.57626 1.1022 0.52532 3.47064 8.35094
从表3可以看出，对f1来说，CAGA 在最优解和迭代次数上都稍优于MAGA ，而SGA 、AGA 和HMGA 虽然迭代次数较少，但是得到的最优解远不如CAGA 得到的最优解。对f2来说，LAGA 得到的最优解明显优于SGA 、AGA 、和HMGA ，且在迭代次数上明显少于SGA 。在迭代次数相当的情况下，最优解优于MAGA 。由此可见，CAGA 是一种较优的搜索算法。 3.1.2 比较CAGA 与其它遗传算法的特征选择能力
本文选择了国际通行的机器学习数据集（UCI ）中的两个典型数据集。数据集1是letter-recognition ，包括了16个特征，共26个类别，这里选用了其中的a 类和b 类数据，a 选用全部的789个样本，b 选用全部的766个样本。数据集2是waveform ，包括了40个特征，共3个类别，这里选用了其中的wave0类和wave1类数据，wave0和wav1都有选用了各自的前1000个样本。两个数据集的出处为：https://www.doczj.com/doc/3211879255.html,/~mlearn/databases 。
基于数据集1，将CAGA 与SGA 、AGA 、HMGA 、MAGA 分别用于特征选择，五个遗传算法都基于单个评价准则，这里选用2.1.1节介绍的评价准则1。由于BPNN 分类器结构简单，运算速度较快，所以本组实验采用它来评估五种遗传算法分别搜索得到的最优特征子集的分类效果。
分类器：BP 网络结构是m n k ××，其中输入层神经元个数为m ，隐含层神经元个数为n ，输出层神经元个数为k 。m 为输入特征数，21n m =+，因为输出两类，所以2k =。规定BP 网络的训练目标是0.01MSE =。评估分类正确率的规则如定义2所示。 训练与测试：为了避免过拟合（overfitting ）发生，采用3 fold cross validation 法。
识别正确率定义：设置RBF 识别两类数据的输出目标分别为0和1，设第i 个测试数据输出为
P i ，则两类数据识别正误标准为：
() 1 P 0 else
i i N ??
?＝<=0.2
1，() 1 P 0 else
2 i i N ??
?＝>=0.8
其中，1代表分类正确，0代表分类错误，设两类样本的总测试数分别为1N 、2N ，则其识别
正确率分别为：
()11111*100%N i i N R N =??=????∑, ()22212*100%N i i N R N =??
=????
∑
为了便于通过图形描述CAGA 的特征选择能力，五种算法均基于同一个初始群体对数据集1进行特征选择，如图2所示。图中，sga 代表SGAE ，zsypc 代表AGA ，haimin 代表HMGA ，maga 代表MAGA ，chain 代表CAGA 。横坐标表示遗传代数，纵坐标表示每一代的最优适应度值变化的情况。
bestfit temp
generation
f i t v a l u e
图2 五种算法对于数据1的特征选择能力比较
从图2 可以得到以下结论：在遗传代数方面，CAGA 遗传的代数均比SGAE 、AGA 、HMGA 短，与MAGA 收敛速度相当并且比MAGA 先进入近优点；在选择精度（即特征子集适应度值）方面，对于该数据集来说，CAGA 得到的选择精度最高，明显高于MAGA 。
表4说明了五种遗传算法对数据集1进行特征选择的结果比较，表5说明了分别采用五种算法得到的特征子集进行BPNN 分类的结果比较。
表4 五种遗传算法对数据集1进行特征选择的比较表
CAGA SGA AGA HMGA MAGA
遗传代数18 24 30 24 12 选中的特征数10 10 9 10 11
选中的特征子集5,7-12,
14-16 5,7-9,
11-16
5-9,11,12,
14,15
5,7-12,
14-16
5-12,
14-16
最大适应值17.944917.707917.192117.944917.7852
执行时间21.51517.985019.484 29.922016.109
注：表4中相关的比较参数如下：遗传代数：算法结束时的代数；选中的特征数：被选中的特征的数目；选中的特征子集：选中的特征在原数据集中的顺序号（从左到右）；最大适应值：算法结束输出的最优适应值；执行时间：算法的运行时间。
表5 五种算法对数据集1进行特征选择的BPNN的比较
CAGA SGA AGA HMGA MAGA BP结构10*21*2 10*21*29*19*2 10*21*210*23*2 选择的特征数10 10 9 10 11 步数10 4 29 7 22
训练时间 5.575 3.281 13.765 4.42200015.672
测试时间0.016 0.032 0.016 0.0310000.015
运行时间 5.591 3.313 13.781 4.453 15.687
识别正确率
(%) R1 = 92.50
R2 = 100.00
R1 = 91.00
R2 = 94.50
R1 = 91.00
R2 = 99.00
R1 = 90.50
R2 = 99.00
R1 = 89.00
R2 = 98.00
注：表5中相关的比较参数如下：选中的特征数：最终特征子集S中特征的个数；步数：BP网络训练时到达目标MSE = 0.01的步数；训练时间：BP网络训练用的时间；测试时间：BP网络测试用的时间；运行时间：BP网络的训练时间加上测试时间；识别正确率：两类数据BP识别的正确率。
从表4 中可以看出，SGA和AGA虽然执行时间较短，但是适应值没有达到最大，HMGA 适应值达到了最大，但是执行时间较长。而CAGA不仅适应值达到了最大，而且所用的遗传代数也最小。说明CAGA进化效率高，特征选择能力强。CAGA比MAGA来说，选择时间较长，但其选择精度却更高。从表5可以看出，CAGA选择的特征子集所对应的BPNN的网络维数复杂度与其他算法相当，训练时间和步数都比AGA明显较少，总共的运行时间比AGA 明显较少。最关键的是，CAGA选择得到的特征子集进行识别的正确率最高。与MAGA相比，CAGA的选择特征数、训练步数、训练时间、识别正确率等都要好。表4和表5显示的CAGA 的优良特性正是因为其链式遗传个体结构和自适应遗传算子使得多样性得以较好的保持，从而获得较好的搜索精度。
3.2 本文算法性能测试比较实验
该组实验主要是验证本文算法与filter模式下单评价准则的特征选择算法以及wrapper模式下的特征选择算法的性能。
与3.1节不一样的实验条件介绍：
神经网络分类器：由于wrapper模式下BP神经网络进行特征选择耗时过大，因此该组实验采用了RBF神经网络；径向基函数的分布密度SPREAD=1.5。
搜索算法：为了便于比较，本组中各种特征选择算法均采用前述的链式智能体遗传算法(CAGA)，种群数为20，初始pc=0.6，初始pm=0.05。
评价准则：采用2.1.1节讨论的三个评价准则。
松弛停止条件：进化到连续5代代间最优适应值之差<10e-4时，转向下一个评价准则；
紧致停止条件：连续5代最优适应值没有变化就停止。
表6和表7为基于数据集1和2，采用本文算法与filter模式下分别采用三种单评价准则
特征选择算法以及wrapper模式下单评价准则特征选择算法的性能比较。为了使得数据更有意
义和说服力，每个算法进行了10次实验，取统计平均结果示于该表，因此，表中平均代数出
现了小数点。
表6 基于数据集1的本文算法与其他算法比较
轮循式单准则f1 单准则f2 单准则f3 wrapper 平均代数33.0 21.7 20.2 22.3 15.7 平均时间（s）7.7299 5.0033 4.9969 6.9373 2224.7
0.9635 0.9601 0.9665 0.9597 0.9469
识别正确率
0.9367 0.9167 0.9325 0.9578 0.9249
1.9002 1.8768 1.8990 1.8175 1.8718
表7 基于数据集2的本文算法与其他算法比较
轮循式单准则f1 单准则f2 单准则f3 wrapper 平均代数58.0 36.5 39.4 42.9 17.2 平均时间（s）20.0781 11.8204 18.6810 25.0562 6348.5
0.5181 0.4991 0.5409 0.5605 0.5033
识别正确率
0.4647 0.4792 0.4576 0.5116 0.5124
0.98278 0.9783 0.9785 0.9721 1.0157
从表6和7可以看出，对于特征较少的数据集1来说，本文算法得到的识别率高于任何
一种单评价准则，甚至还高于wrapper模式下特征选择算法，这说明了本文提出的轮询式多准
则方法对提高识别率是有效的；同时，本文算法所需运算时间大大低于wrapper模式的特征选
择算法，非常实用，与单评价准则所需时间相当，这说明了本文算法时间代价较低，轮询式
多准则方法所需时间代价不高；本文算法所需平均代数略微高于单评价准则，这说明轮询式
多准则方法充分利用了评价准则一致性，前后评价准则所需时间代价是快速降低的。对于特
征较多的数据集2来说，本文算法的识别率仍然高于单评价准则，仅比wrapper模式低一点；
其所需时间代价仍然远远低于wrapper，并且与单评价准则相当。
4 结论
本文针对filter模式下传统遗传算法特征选择精度不高，wrapper模式特征选择时间代价较
高的缺点，提出了一种新的特征选择算法－轮询式多准则特征选择算法。该算法采用了链式
智能体遗传算法作为搜索算法，引入了轮询式多准则思想，较快较好的进行特征选择。以往
文献常常是通过对搜索算法或单个评价准则进行研究，从而改进特征选择算法。本文的最大
贡献在于指出了一种新的改进特征选择算法的思路，即对评价准则进行组合使用，轮询式使
用多准则进行特征选择，从根本上突破了目前各个评价准则的局限性。此外，本文提出了一
种新的搜索算法用于特征选择。实验对本文算法进行了大量测试，统计平均结果表明了本文
算法具有比filter模式下单个评价准则特征选择算法更高的识别率，大大低于wrapper模式特
征选择算法的时间代价的优点，具有较高的实用性。下一步工作是搜集更多的评价准则，研
究对于某一类模式识别问题，采用哪些评价准则进行轮询式特征选择效果最好。
参考文献
[1]Huan Liu, and Lei Yu,Toward Integrating Feature Selection Algorithms for Classification and Clustering. IEEE
TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2005, 17(4):491-502
[2]Il-Seok Oh, Jin-Seon Lee, and Byung-Ro Moon. Hybrid Genetic Algorithms for Feature Selection. IEEE
TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26(11): 1424-1437 [3]王卫玲,刘培玉,初建崇.一种改进的基于条件互信息的特征选择算法.计算机应用，2007，27（2），433－
435
[4]张莉，陈恭和. 一种适合大规模数据集的特征选择方法. 计算机工程，2007，33（4）：184－186
[5]尚文倩，黄厚宽，刘玉玲，林永民，瞿有利，董红斌.文本分类中基于基尼指数的特征选择算法研究.计
算机研究与发展,2006，43（10）：1688－1694
[6]张葛祥, 金炜东, 胡来招.基于量子遗传算法的特征选择算法.控制理论与应用，2005, 22(5):810-813
[7]魏维，赵学龙，刘凤玉，许满武. 视频语义分类特征选择算法.系统仿真学报，2006，18(5):1143-1146
[8]Ron Kohavi, George H. John. Wrappers for feature subset selection. Artificial Intelligence, 1997, 97: 273-324
[9]乔立岩,彭喜元,彭宇.基于微粒群算法和支持向量机的特征子集选择方法.电子学报,2006, 34(3):496-498
[10]廖广兰,史铁林,姜南,刘世元.基于SOM 网络的特征选择技术研究.机械工程学报，2005，41（2）：46－
50
[11]Cheng-Lung Huang, Chieh-Jen Wang. A GA-based feature selection and parameters optimization for support
vector machines. Expert Systems with Applications, 2006, 31:231–240
[12]Huang Yuan, Shian-Shyong Tseng, Wu Gangshan, Zhang Fuyan. A Two-phase Feature Selection Method using
both Filter and Wrapper. 1999. IEEE SMC'99 Conference, USA: IEEE PRESS, 132-136
[13]任江涛，孙婧昊，黄焕宇，印鉴.一种基于信息增益及遗传算法的特征选择算法.计算机科学，2006，33(10):
193-195
[14]王新峰, 邱静, 刘冠军.故障特征组合选择方法.数据采集与处理，2005,20(2):181-185
[15]李勇明，曾孝平，陈燕飞，王靖，张晓娟，郑雅敏，搜索空间逐步缩小的遗传算法用于尿沉渣图像特征
优选的研究，中国生物医学工程学报，已录用
[16]M.Srinivas,L.M.Patnaik.Adaptive Probabilities of Crossover and Mu tation in Genetic Algorithms[J]. IEEE
TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, 1994, 24(4):656-659.
[17]巩敦卫，孙晓燕，郭西进.一种新的优胜劣汰遗传算法[J].控制与决策，2002，17(6):908-909.
[18]Weicai Zhong, Jing Liu, Mingzhi Xue, and Licheng Jiao. A Multiagent Genetic Algorithm for Global Numerical
Optimization [J].IEEE transactions on systems,man, and cybernetics-part B:cybernetics,2004,34(2):1128-1141.
The Research of Poll Mode and Multi-Criteria Feature
Selection Algorithm Based on Chain-like Agent Genetic
Algorithm
Li Yongming，Zeng Xiaoping，Qin Jian
College of communication engineering of Chongqing University，Chongqing (400030)
Abstract
feature selection is pretreatment process for complex pattern classification systems. According to the low precision of feature selection under filter mode and high time cost of feature selection under wrapper mode, this paper proposed one new feature selection algorithm. This algorithm designed chain-like agent genetic algorithm as searching algorithm, introduced several evaluation criteria for poll mode selection. The experiments were done to compare this algorithm and several other feature selection algorithms. The experimental results show that this algorithm can obtain better precise selection result than several single evaluation criterion feature selection algorithms under filter mode, and less selection time cost than feature selection algorithm under wrapper mode. Therefore, this algorithm can be used for designing feasible pattern classification system with high recognition rate.
Keywords：feature selection，genetic algorithm，chain-like agent，poll mode，multi-criteria
作者简介：
李勇明（1976-），男，博士，讲师，目前研究方向：智能计算，模式识别，信号处理；
曾孝平（1956-），男，教授，博导，从事通信、信号处理等研究。
[编辑本段] 遗传算法定义 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 [编辑本段] 遗传算法特点 遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为： ①首先组成一组候选解； ②依据某些适应性条件测算这些候选解的适应度； ③根据适应度保留某些候选解，放弃其他候选解； ④对保留的候选解进行某些操作，生成新的候选解。 在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。 遗传算法还具有以下几方面的特点： (1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 (2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。 (3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。
yj1.m ：简单一元函数优化实例，利用遗传算法计算下面函数的最大值 0.2)*10sin()(+=x x x f π，∈x [-1, 2] 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9， 最大遗传代数为25 译码矩阵结构：?????????? ??????? ???? ?=ubin lbin scale code ub lb len FieldD 译码矩阵说明： len – 包含在Chrom 中的每个子串的长度，注意sum(len)=length(Chrom)； lb 、ub – 行向量，分别指明每个变量使用的上界和下界； code – 二进制行向量，指明子串是怎样编码的，code(i)=1为标准二进制编码， code(i)=0则为格雷编码； scale – 二进制行向量，指明每个子串是否使用对数或算术刻度，scale(i)=0为算术 刻度，scale(i)=1则为对数刻度； lbin 、ubin – 二进制行向量，指明表示范围中是否包含每个边界，选择lbin=0或 ubin=0，表示从范围中去掉边界；lbin=1或ubin=1则表示范围中包含边界； 注：增加第22行：variable=bs2rv(Chrom, FieldD);否则提示第26行plot(variable(I), Y, 'bo'); 中variable(I)越界 yj2.m ：目标函数是De Jong 函数，是一个连续、凸起的单峰函数，它的M 文件objfun1包含在GA 工具箱软件中，De Jong 函数的表达式为： ∑ == n i i x x f 1 2 )(， 512512≤≤-i x 这里n 是定义问题维数的一个值，本例中选取n=20，求解 )(min x f ，程序主要变量： NIND （个体的数量）：＝40； MAXGEN （最大遗传代数）：=500； NV AR （变量维数）：=20； PRECI （每个变量使用多少位来表示）：=20； GGAP （代沟）：=0.9 注：函数objfun1.m 中switch 改为switch1，否则提示出错，因为switch 为matlab 保留字，下同！ yj3.m ：多元多峰函数的优化实例，Shubert 函数表达式如下，求)(min x f 【shubert.m 】
一、粒子群算法 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionary Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度.爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价
遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……
即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：
1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。
人工智能实验报告 学号： 姓名： 实验名称：遗传算法 实验日期：2016.1.5
【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理，熟悉遗传算法的运行机制，学会用遗传算法来求解问题。 【实验原理】 遗传算法（ Genetic Algorithm ）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化， 如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来 越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学 的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法程度流程图为：
【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理，熟悉遗传算法的运行机制，学会用遗传算法来求解问题。 【实验原理】 遗传算法（ Genetic Algorithm ）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化， 如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来 越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学 的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法程度流程图为：
matlab遗传算法工具箱函数及实例讲解 核心函数： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数 【输出参数】 pop--生成的初始种群 【输入参数】 num--种群中的个体数目 bounds--代表变量的上下界的矩阵 eevalFN--适应度函数 eevalOps--传递给适应度函数的参数 options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B], 如 precision--变量进行二进制编码时指定的精度 F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverO ps,mutFNs,mutOps)--遗传算法函数 【输出参数】 x--求得的最优解 endPop--最终得到的种群 bPop--最优种群的一个搜索轨迹 【输入参数】 bounds--代表变量上下界的矩阵 evalFN--适应度函数 evalOps--传递给适应度函数的参数 startPop-初始种群 opts[epsilon prob_ops display]--opts(1:2)等同于initializega 的options参数，第三个参数控制是否输出，一般为0。如[1e-6 1 0] termFN--终止函数的名称,如['maxGenTerm'] termOps--传递个终止函数的参数,如[100] selectFN--选择函数的名称,如['normGeomSelect'] selectOps--传递个选择函数的参数,如[0.08] xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover'] xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0] mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'] mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关
遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）．遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解． 下面给出遗传算法的具体步骤，流程图参见图1： 第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步：定义适应函数，便于计算适应值； 第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 第四步：随机产生初始化群体； 第五步：计算群体中的个体或染色体解码后的适应值； 第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步． 图1 一个遗传算法的具体步骤
WORD格式 人工智能实验报告 学号： 姓名： 实验名称：遗传算法 实验日期：2016.1.5
【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理，熟悉遗传算法的运行机制，学会用遗传算法来求解问题。【实验原理】 遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法程度流程图为：
【 实】 ：已知f(x)=x*sin(x)+1，x[0,2],求f(x)的最大值和最小值。 数据结构： structpoptype { doublegene[length];//染色体 doublerealnumber;//对应的实数x doublefitness;//适应度 doublerfitness;//相对适应度 doublecfitness;//累计适应度 }; structpoptypepopulation[popsize+1];//最后一位存放max/min structpoptypenewpopulation[popsize+1];// 染色体编码： x [ 因此 ，染色体由2 3位字节的二进制矢X 与二进）2之 间的映射如下： 22 i bb......bb2x '; 222102i i010 xx' 2 23 21 适应度函数： 由于要求f (x )的最值,所以适应 度函数即可为f (x )。但为了确保每个个体都有被选中的可能性，因此需要将所有适应为大于0的值。因此，设计 求最大值的适应度函数如下： eval max f(x)5xsinx6; 将最小化为求-f(x)的最大值，同理，设计最小值的适应度函数如下： evalfxxx min()5sin4; 种群大小： 本50，再进行种群初始化。 实验参数： 主要有迭代数，交叉概率，变异概率这三个参数。一般交叉概率在0.6-0.9范围内， 变异概率在0.01-0.1范主要代码如下： voidinitialize()//种群初始化 { srand(time(NULL));
第9章怎样研究算法:遗传算法示例 1、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题，回答下列问题。 (1)下列说法不正确的是_____。 (A) P类问题是计算机可以在有限时间内能够求解的问题； (B) NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题； (C) NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性的问题，被称为NP完全问题； (D)上述说法有不正确的； 答案：D 解释： 本题考核P类问题、NP类问题、NPC类问题的概念。 P类问题指计算机可以在有限时间内求解的问题，(A)正确；NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，(B)正确；NPC问题指NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算，称为NP-Complete问题，(C)正确；(A)(B)(C)都正确，所以(D)错误。 具体内容请参考第九章视频之“可求解与难求解问题”以及第九章课件。 (2)可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。 (A) P类问题是可解性问题，NP类问题是难解性问题。 (B) NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题； (C) NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题； (D)上述说法有不正确的； 答案：A 解释： 本题考核对可解性问题和难解性问题概念的理解。 P类问题指计算机可以在有限时间内求解的问题，所以是可解性问题；NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，但P类问题是NP类问题的一个子集，所以NP类问题不一定是难解性问题；NPC问题指NP问题的所有可能答案都可以在多项式时间
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
遗传算法程序（一）: 说明: fga.m 为遗传算法的主程序; 采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择, 均匀交叉,变异操作,而且还引入了倒位操作! function [BestPop,Trace]=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options) % [BestPop,Trace]=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation) % Finds a maximum of a function of several variables. % fmaxga solves problems of the form: % max F(X) subject to: LB <= X <= UB % BestPop - 最优的群体即为最优的染色体群 % Trace - 最佳染色体所对应的目标函数值 % FUN - 目标函数 % LB - 自变量下限 % UB - 自变量上限 % eranum - 种群的代数,取100--1000(默认200) % popsize - 每一代种群的规模；此可取50--200(默认100) % pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8) % pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1) % pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2) % options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编 %码,option(2)设定求解精度(默认1e-4) % % ------------------------------------------------------------------------ T1=clock; if nargin<3, error('FMAXGA requires at least three input arguments'); end if nargin==3, eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==4, popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==5, pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==6, pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==7, pInversion=0.15;options=[0 1e-4];end if find((LB-UB)>0) error('数据输入错误,请重新输入(LB 基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串： 《人工智能》课程学习体会兼论遗传算法在最优化问题的应用与发展 一、《人工智能》课程学习体会 1．课程学习历程 这学期，在《人工智能》课程学习中，我们以中国大学MOOC网上浙江工业大学王万良教授主讲的《人工智能导论》课程为主。课上老师给我们讲解了一些课程中的难点，课下老师发放了很多的人工智能课外阅读资料，供我们参考学习。 在学习的过程中，我们先对智能有了初步了解，之后再谈人工智能的概念。要想实现人工智能，就需要把我们人的思维形式化，于是学习了谓词逻辑知识表示，之后是产生式，然后是概率论和数理统计的一些内容。掌握了这些之后，我们就可以根据知识去解决问题了。可是怎么去解决，如何去推出结果，又是一个问题，于是我们学习了一些推理方法，如模糊推理等。按照智能的定义，那么现在已经基本实现智能了。即实现了智能=知识+智力，虽然不是真正意义上的智能。虽然现在可以去处理一些问题了，但是很明显的，它的效率非常的低，甚至于有些问题找到答案花费的时间特别长，是我们无法接受的。于是我们学习了如A*算法、遗传算法、粒子群优化算法、蚁群算法等一些加快处理问题的算法。最后，我们学习了神经网络、专家系统、机器学习和智能体系等内容。对于这些学习的知识，基本上还处于一个了解的水平，要想实际应用还需要更深入的学习。 课下，我们也看了一些和人工智能的书籍，诸如《浪潮之巅》，向我们讲述了科技公司像IBM，微软，英特尔等公司的兴衰；《智能革命》向我们讲述了AI 与我们的生活密切相关，并且越来越离不开智能。通过阅读这些课外读物，也使得我们对人工智能有了更深的理解与思考。 2．课程学习体会与感悟 学习完主要课程之后，给我的第一感觉就是：“哎！怎么还没有学呢！课程就结束了”。有这样的感觉主要还是受到疫情的影响，在家不能像在学校一样学的那么精细。很多的知识几乎是走一个概念便草草离场了，同时，人工智能这门课程本身涉及的知识面也比较广，如讲到神经网络的时候提到了生物学中的神经元、突触等这些结构，想一下子掌握这些内容是不可能的。 另一个方面则是，人工智能的应用领域非常之多，诸如机器学习，专家系统等，每一部分都是可以单独拿出来作为深入学习的方向的。因此，现在的学习，只是对人工智能有了一个初步的了解，想要入门还需要学习更多的内容，还需要投入更多的时间。 二、遗传算法在最优化问题的应用与发展 1.遗传算法简述 《基于遗传算法的智能组卷策略的研究》综述 姓名刘春晓 学号 2015216104 专业计算机技术 班级 3班 天津大学计算机科学与技术学院 2016年 6 月 基于遗传算法的智能组卷策略的研究综述 摘要随着计算机技术的日益发展和成熟，手工组卷已经不能满足现代的教学要求，组卷智能化在提高教学质量方面发挥着很重要的作用。文章对组卷策略进行了梳理，对比和总结，主要介绍了遗传算法的优点，从遗传算法的基本流程、编码方式、适应度函数和遗传算子方面进行了归纳。接着分析了目前智能组卷策略研究的不足和挑战，最后总结了未来的研究设想。 关键词智能组卷；遗传算法；适应度函数；遗传算子 1引言 在计算机技术发展飞速的今天，计算机应用已经慢慢的渗透到人类生活的方方面面，计算机的辅助教学功能也逐渐得到大家的重视。传统的手工组卷受到人为因素的干扰，导致考试的效率低下，组卷智能化已经成为不可或缺的一项研究。 近几年，智能优化算法倍受人们关注，如人工神经网络、遗传算法，为解决复杂问题提供了新的方法，并在诸多领域取得了成功。组卷问题是一个在一定约束条件下的多目标参数优化问题，针对传统的组卷算法具有组卷速度慢、成功率较低、试卷质量不高等缺点。 智能组卷算法在计算机辅导教学过程中之所以受到重视，是因为它把人工智能技术运用到了组卷中，能够智能的设计试卷的结构和内容，包括试卷的难易度，知识点，题型和题量等，使生成的试卷质量比较高。 遗传算法（Genetic Algorithm ,GA）基于达尔文的进化论和孟德尔的自然遗传学说,是通过模拟遗传选择和自然淘汰的生活进化的随机搜索和全局优化算法（张建国 2009：1）。由于该算法有智能的搜索技术和收敛性质，可以较好的满足智能组卷的要求。所以本系统选用遗传算法作为组卷算法，以试题章节、试题数量、试题知识点、试题题型、试题难度分布、试题曝光度、覆盖度、试题分数分配等约束为组卷条件，使试卷有更好的区分度。 基于遗传算法的智能组卷系统实现了组卷智能化，优化了其他组卷算法的不足，使教学更加自动化和公平化，提高了组卷效率。 2研究现状分析 在系统开发之前，应该首先选择适合本系统的组卷算法，组卷算法的选取对试卷的质量影响颇大。只有相对好的算法才能提高组卷的效率和成功率。组卷实质上就是在复杂的约束条件下的多目标求最优解的问题，保证试卷能够满足教学要求。随着计算机技术和人工智能理论的飞速发展，各种组卷策略层出不穷，选择适合的算法对系统运行有极其重要的作用。分析各种组卷算法的优缺点，找到最优的组卷算法是该系统开发的任务之一。这里我们就现阶段组卷算法进行分析和总结。 现阶段比较成熟的组卷算法有随机选取法、回溯试探法和遗传算法。随机选取法生成的试题重复率较高，难以达到预期效果。回溯试探法是一种有条件的深度优化法，对于状态类型和题量较小的题库系统而言，组卷成功率高，但占用内 目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19) 遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的 遗传算法实验报告 专业：自动化姓名：张俊峰学号：13351067 摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。 关键词：串集最优化评估迭代变异 一：实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。。 （2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止： a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一 个解。 二：实验要求 已知函数y=f（x 1,x 2 ,x 3 ,x 4 ）=1/(x 1 2+x 2 2+x 3 2+x 4 2+1),其中-5≤x 1 ,x 2 ,x 3 ,x 4 ≤5, 用遗传算法求y的最大值。三：实验环境 操作系统：Microsoft Windows 7 软件：Microsoft Visual studio 2010 四：实验原理与步骤 1、遗传算法的思想 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。 2、算法实现步骤 ①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合； ②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据； ③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。 ④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。 ⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异； ⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。 五：实验结果 实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。基本遗传算法及应用举例
人工智能导论学习体会及遗传算法应用
基于遗传算法的智能组卷策略的研究综述Word版
遗传算法基本理论实例
遗传算法实验报告
相关主题
文本预览