传算法优化神经网络拓扑结构和权值

1、第21卷第1期2003年3月广西师范大学学报(自然科学版JOU RNAL O F GUAN GX INORM AL UN I V ERS ITYV o l .21N o.1M arch 2003收稿日期:2002204228作者简介:魏志成(1975,男,河北石家庄人,硕士研究生;周激流(1963,男,教授,博士生导师.遗传算法优化神经网络拓扑结构和权值魏志成,杨联祥,周激流(河北师范大学物理学院电子信息组,河北石家庄050016摘要:采用改进的串行遗传算法以各种变尺度搜索解空间,可以改变神经元输入和输出的映射关系,进而改变整个网络的性能,在高维解空间中自动寻找合适的解,并且验证了Si m p

2、 lex 的有效性.关键词:遗传算法;神经网络;遗传算子中图分类号:T P 183文献标识码:A 文章编号:100126600(20030120062204自从1943年第一个神经网络模型M P 模型被提出至今,神经网络的发展十分迅速,在模式识别、图像处理和工业控制等领域颇有成效.遗传算法的出现使神经网络的构造和训练有了一个崭新的面貌,本文用串行遗传算法优化神经网络的拓扑结构和权值.除了采用选择、交叉和变异算子外,还采用Si m p lex 算子1,另外在编码时还采用Gr 2anu larity24(粒度变长度编码,大大增强了对空间的搜索能力,同时也增强了算法的智能性和普适性.1本文算法用串行

3、遗传算法优化神经网络,主要有三方面的困难,首先是编码策略的确定;其次是使用什么样的遗传算子;第三是适应度函数的设计.111编码方法采用变长度的二进制直接编码.采用这种编码方法的原因主要有三个:二进制编码采用的是最小字符集0,1;二进制编码和直接编码都有利于形成有意义的积木块;变长度编码可以缩短码长,提高编码效率.神经元的Sigm o id 传递函数参数为.S 型传递函数的表达式如下:图1Sigmo id 函数在不同下的曲线f (x =11+e -x(1当取不同的值时,上式的图像如图1所示.从图1可以看到,=0.5时函数曲线相当平缓,而当=4的时候,S 型函数已经比较接近于阶跃函数了,不同的值,

4、反映了神经元的不同传递性质.112遗传算子(a 选择算子:本文采用的是两两竞争法5,而没有采用赌轮法6,原因是赌轮法很容易产生超级个体,使遗传算法收敛于局部最优.本文还采用了最优个体保存策略.(b 交叉算子:本文采用了两种交叉算子.一种是单点交叉,因为采用的是变长度编码,所以交叉前要在Connectivity 域是0的后面随机的补上相应长度的数值域,然后以交叉概率P c 再交叉.另一种是Si m 2p lex 算子1,Si m p lex 是一个三元算子,其算法如下:随机选择三个个体:x 1,x 2和x 3,并按适应度从大到小排列,即F itness (x 1F itness (x 2F it

5、ness (x 3.对于个体中的每一位执行步骤和.如果x 1i =x 2i ,那么x 4i =x 1i .(x 4是产生的新个体如果x 1i x 2i ,那么x 4i =(negate x 3i .表1是一个应用Si m p lex 算子的例子:表1Si m plex 算子应用实例,适应度是相应二进制编码的实数值个体编码适应度x 11100100100x 2100110177x 3001101026x 41100101101表2最佳参数设置n 225P c 014P m r0105012(c 变异算子:采用多点变异算子,以概率P m 变异,对于编码中不同的位,P m 又可以取不同的值.113适

6、应度函数本文的适应度函数是:F itness =1 E(2其中E 是网络的能量函数:E =6m6k(Y m k -Y m k 2(3Y m k 和Y m k 分别是第m 个训练样本的第k 个输出节点的期望输出和实际输出.114参数设置表2是本文经过大量试验得出的参数设置(n 是解群规模:2测试问题以下这三个测试问题均来自H in ton 和W illiam s 7:3优化结果及其分析311适应度比较表3给出了本文算法优化以上三个测试问题的结果,并和ANNA EL EONO RA 8算法,B P 算法的结果作了比较,ANNA EL EONO RA 算法的最大特色就是优化神经网络时使用了Granu

7、 larity 算子,但是它的范围项和Sigm o id 函数的传递参数都是凭经验人工确定的,分别是6和1.表3中ANNA 算法的优化结果来自文献4.遗传算法到目前为止并没有一个理论上的收敛条件,大都采用启发式收敛.对Xo r 这样比较简单的非线性问题,收敛条件选在1000代;对Parity 和Symm etry 收敛条件选在10000代.我们采用的是标准B P 算法,并没有对它进行改进,虽然这样做不太公平,但我们已经知道改进后的B P 算法可以在确定一个简单结构的前提下,有效的解决这些测试问题.在这儿只是想把本文的算法和B P 算法比较一36第1期魏志成等:遗传算法优化神经网络拓扑结构和权值

8、下.表3优化结果,这些F itness 都是程序执行10代的平均值问题串行GA :F itnessBP 算法ANNA 本文算法BP Xo r 161.9E +98Parity252.86.1E +2163.2表4Xor 问题优化后的输入输出关系x 1x 2y表3中的数据是式(2中的F itness (适应度,F itness 越高表示网络的能量函数越低,优化的结果越好.从上表可看到,本文算法得到的适应度远远高于ANNA 算法,主要原因是改进的遗传算法能更加有效的以各种尺度搜索解空间,就象变焦的照相机一样,在高维解空间中自动寻找合适的解.表5Par ity 问题优化后的输入输出关系x 1x 2x

9、 3x 4yx 1x 2x 3x 4y 表4,5给出了用本文算法优化后的网络得到的输入输出关系,表4是适应度为612E +9时Xo r 问题的输入输出关系,表5是适应度为823时Parity 问题的输入输出关系.312Si m p lex 算子的性能分析Si m p lex 是具有局部搜索能力的算子,它有助于算法在高维解空间的搜索,并提高收敛速度.图2,3给出了对Xo r 问题的对比结果,图2使用了Si m p lex 算子,图3没有使用.在这两幅图中,上面的曲线表示最优个体的适应度,下面的曲线表示解群中的平均适应度.可以看到,在开始的100代中,两种算法的进展相似;而基于Si m p lex

10、 的算法在100代和35代发生了两次跳变;另一种算法只是在300代产了一次类似的跳变,并且直到565代也没有再发生变化.图2使用Si m p lex 算子的Xo r 优化图3不用Si m p lex 算子的Xo r 优化313结论本文提供了一种优化神经网络拓扑结构和权值的算法.无论对最后的训练误差,还是对网络结构的优化,都取得了令人满意的结果.在这种高维的复杂解空间中,搜索效率主要来源于编码的长度,本文采用了变长度的二进制编码变范围搜索.另外,具有局部搜索能力的Si m p lex 算子和其他遗传算子也起到了一定的作用.编码长度是困扰二值编码的一个难题,当网络十分复杂时即使对变长度编码码长也会

11、变得很长,如何优化更复杂的网络将是我们今后进一步研究的方向.参考文献:1Bersin i H ,Seron t G .In search of a good cro ssover betw een evo lu ti on and op ti m izati on A .Parallel p rob lem so lving46广西师范大学学报(自然科学版第21卷from natu re 2C .1992.479488.2M an iezzo V .Granu larity evo lu ti on A .P roc of the 5th in t conf on genetic algo r

12、ithm s and their app licati on s C .1993.644.3M an iezzo V .Search ing among search spaces :H asten ing the genetic evo lu ti on of feedfo rw ard neu ral netw o rk s A .In tconf on neu ral netw o rk s and genetic algo rithm s ,GA 2ANN 93C .1993.635642.4M an iezzo V .Genetic evo lu ti on of the topo

13、logy and w eigh t distribu ti on of neu ral netw o rk s J .IEEE T ran s on N eu ralN etw o rk s ,1994,5(1.5Ho lland J H .Genetic algo rithm s and op ti m al allocati on of trials J .S I AM Jou rnal of Compu ting ,1973,2(2:88105.6Go ldberg D E .Genetic algo rithm s in search ,op ti m izati on &m

14、ach ine learn ing M .A ddison 2W esley Pub lish ing ,1989.7R um lhart D E ,H in ton G E ,W illiam s R J .L earn ing in ternal rep resen tati on s by erro r p ropagati on A .Parallel distr 2bu ted p rocessing :exp lo rati on s in the m icro structu res of cogn iti on C .1986.318362.8W ang Zhenn i ,M

15、assi m o Ch ristine D i.A p rocedu re fo r determ ing the topo logy of m u ltilayer feedfo rw ard neu ral net 2w o rk s J .N eu ral N etw o rk s ,1994,7(2:291300.O PT I M IZE TH E W E IGH T D ISTR I BU T I ON AND TO POLO GY O F N EU RAL N ETW O R K B Y U S I N G TH E GEN ET I C AL GO R ITHM (GA W E

16、I Zh i -cheng ,YANG L i an -x i ang ,ZHOU J i -l iu(E lectron ic D epartm en t ,Physics Co llege ,H ebeiN o rm al U n iversity ,Sh ijiazhuang 050016,Ch ina Abstract :T he i m p roved serial genetic algo rithm can search the so lu ti on sp aces .A nd the m ap of inp u t and ou tp u t of neu ral cell is i m p roved ,so the functi on of the neu ral netw o rk s i