基于遗传算法的人工神经网络学习算法

第３８卷２００２年第２期　Ｖ　３８　Ｍ建　ｏ　２　西北师范大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏｒｔｈｗｅｓｔ　Ｉａｌ　Ｕｆｄ＊ｅｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｅｌｅｎｃｅ）　基于遗传算法的人工神经网络学习算法　李建珍　（西北师范大学教育技术与传播学院，甘肃兰”【７３００７０）　摘要：为了克服和陡连ＢＰ算法的不足．提出了一种基于遗传算击的神经网络学习算法体真结果表明．该算法具　有无比的优越性．可避免ＢＰ算法易于陷八局部极　：、值、　练速度陧、误差函数必须可导、受回络结构的限弗　等缺．唱　关键词：和垃网络；遗传算涪：权值：阁值；仿真　中图分类号：ＴＰ　ｔ８３　文献标识码：Ａ　文章编号：１００１　９８８Ｘ（２００２）０２－００３３　０５　Ａ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ａｒｔｉｉｆｃｉａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ＬＩ　Ｊｉａｎ　ｚｈｅｎ　（－ａｌｌｅｇｅ　ｏｆ｝　ｕｃｎ｛】ｔ　ＴｅｅｌｍｏｌｏＫｖ　ａｎｄ　Ｃｏｎｍｎｍｉｃａｔｉｏｎ，＼ｏｒｔｌｌ￣ｅｓｌ　Ｎｏｒｍａｌ　Ｕｔｉｖｅｔｆｓｉｔｙ　Ａｂｓｔｒａｃｔ：Ｉｎ　ｏ，＇ｄｅｒ　Ｉｏ　ｇｅｔ　ｏｖｅｒ　ｔｈｅ　ｉｎｓｕｆｆｉ￣。ｉｃｎｅｙ　ｏｆ　ＢＰ　ａｌｇｏｒｉｔｈｍ，ａ　ｎｅｗ　ｋｍｍｉｎｇ　ａＩｇ０ｒｉｔｈｍ　ｏｆ　ｍ￣ｔｉｆｉ｛‘ｉａｌ　ｎｅｕｌ￣］ｎｅｔｗｏｒｋ　｝　＊‘Ｉ（Ｈ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　Ｗｅｎ　Ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｅｍｕｌａｔｉｏｎ　ｓｈｏ￣：ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｌｈｍ　ｏｐｌｉｍｉｚａ＊ｗｅｉｇｈｔ　ａｎｄ　ＩｈＨ　ｓ　ｄ　ｕｆ　ａ￣ｉｆｉｃｉａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　１ｌＯｔ　ｏｎｌｙ　Ｃａｌｌ　ｐｕｔｔｅｄ　ｉｎｔｏ　ｐｒａｃｔｉｃｅ．ｂｕｔ　ｈａｓ　ｖｍＴ　ａｐｐｅａｌｉｎｇ　ａｄｖａｎｔａｇｅｓ　Ｆｈｃ　ｉｎｔｏ　ｋ￣，ａｌ　ｍｉｎｉｍｕｍ．ｓｌｏｗ　Ｆ　‘Ｉ　ｉｎ　ａ　ｖｉｆｌ￣ｍ　４＇ＯＪｒ１　ｇｅｔ　ｏｖｅｒ　ｔｈｅ　ｉｎｓｕｆｆｉｃｉｅｎｃｙ　ｏｆ　ＢＰ　ａｌｇｏｒｉｔｈｍ，ｓｕｃｈ　ａｓ：ｌｉａｂｌｅ　ｔｏ　ｔｒａｉｎｉｎｇ，ｄｅｒｉｖａｔｉｖｅ　ｅｒｒｏｒ　ｆｕｎｃｔｉｏｎ　ｒｅｑｕｉｒｅｄ，ｌｉｍｉｔｅｄ　ｈ）ｎｅｔｗｏｒｋ　ａｒｃ，ｈｉｔｅｃｔｕｒｅ．　Ｋｅｙ　ｗｏｒｄｓ：ａｒｔｉｉｃｉａｌ　ｎｅｕｒａｌｆ　ｎｅｔｗｏｒｋ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ：ｗｅｉｇｈｔ；ｔｈｒｅｓｈｏｌｄ；ｅｍｕｌａｔｉｏｎ　由于学习是神经阿络的一种最重要也是最令人　注目的特电，因此在神经网络的发展进程中，学习　算法的研究　直有着十分重要的地位ＢＰ算法的　出现弥补了神经网络在实际应用中难以确定权值的　不足，使得具有很强识别功能的前向多层神经网络　得以应用．但ＢＰ算法从本质上讲属于梯度下降算　法，困而不可避免的具有一些缺陷，如：易陷入局　部极小值、圳练速度慢、误差函数必须可导、受网　络结构的等　２ｏ世纪７０年代初期由美国密执根（Ｍｉｃｈｉｇａｎ）　大学的Ｉｆｏｌｌａｎｄ教授发展起来的遗传算法（ｇｅｎｅｔｉｃ　ａｌｇｏｎｔｈｒｎｓ１，是一种求解问题的高效并行全局搜索　由于一个ＡＮＮ模型可以由有限个参数：神经　元、阿络层数、各层神经元数、神经元的互连方　式、各连接的权重以及传递函数等描述，所以可以　对一个ＡＮＮ模型经过编码，用遗传算法实现神经　阿络的学习过程．而遗传算法又具有全局随机搜索　能力，能够在复杂的、多峰值的、不可微的大矢量　空间中迅速有效地寻找到全局虽优解，陷人局部最　小值的可能性大大减少．另外，由ｆ适应度函数无　需可导，因此进化学习算法可适用的神经元（激活　函数）类型更为广泛ｔ同时由于遗传算法使用简　单、鲁棒性强的特点，用遗传算法进化神经网络无　疑具有重要的意义．　方法．在过去的３０年中，在解决复杂的全局优化　问题方面，遗传算法已取得了成功的应用，并受到　ｒ广泛的关注在优化问题中，如果目标函数是多　１利用遗传算法设计神经网络的权值　和域值方案　由于一个ＡＮＮ模型可以由有限个参数描述，　因而可用有限长度的串编码表示把ＡＮＮ的参数　峰的，或者搜索空间不规则，就要求所使用的算法　必须具有高度的鲁棒性，以避免在局部最优解附近　徘锕　收稿日期：２００ｌ一０９—２１；修改稿收到日期：２０（Ｐ￣ｉｆ２—２８　作者简介：李逵珍（１９６卜），男，甘肃秦安人、讲师，硕士主要研究方向为人工智能、计算机酬络与信息处理　维普资讯 http://www.cqvip.com

西北师范大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏ￣ｈｗｅｓｔ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｔｒｒａｌ　Ｓｃｉｅｔ￣ｃｅ）　第３８卷　Ｖ（）ｌ　３８　编码成ＧＡ的串．并且选择一个合适的性能评价函　隐层节点的激活函数为ｔｍｘ＇ｓｉｇ　数，’（　）＝　（１一ｅ　）／（１＋ｅ　）；输出层节点的激活函数为　数后，可以利用ＧＡ在参数空间进行全局搜索，取　得较好的区域搜索与空间扩展的平衡．实现算法可　简要描述如下：定义一个表示？ｄＶＮ模型的编码方　案；随机产生　个编码，构成初始集Ｓ；　Ｒｅｐｅａｔ　Ｆｏｒ【＝１　ｔｏ　ｎ　ｄｏ　Ｂｅｇｉｎ　解码第ｉ个编码，得到一个反应ＡＩＸＴＮ　模型的参数组合Ｐ：　由Ｐ构成ＡＮＮ；　计算第ｉ个编码的适应值；　Ｅｎｄ　根据适应度值选择ｎ个下一代群体ｓ（有些个体可　能蘑复选择）：根据各个编码的适应度值和概率Ｐ．　在ｓ巾随机选择可进行交叉的后代，并随机配对　进行交叉：根据各个编码的适应度值和概率Ｐ　在　ｓ中随机选择可进行变异的父代，并进行变异；　Ｕｎｔｉｌ（满足性能评价标准）．Ｏｒ．（完成了指定代的搜　索）：解码ｓ中适应度值最大的串，构成ＡＮＮ．　２神经网络权值和闽值的编码及描述　对权值　进行编码：依据连接粳值数目，对　权值用相应维数的实数向量表示．对阈值　进行　编码：根据隐层和输出层神经元数产生一（ｓ＋ｎ）　维实数向量作为阈值向量，　为隐层节点个数，ｎ　为输出层节点个数．　在传统ＧＡ中采用的是二进制编码，在求解连　续参数优化问题时，需要将连续的空间离散化，这　个离散化过程存在一定的映射误差，特别是不能直　接反映出所求问题本身的结构特征．直接采用实数　编码的ＧＡ求解连续参数优化问题，自２０世纪９０　年代以来得到越来越多的重视和发展　．实数编　码是连续参数优化问题直接的自然描述，不存在编　码和解码过程，与基于二进制编码的ＧＡ相比，存　在许多优势：可以提高解的精度和运算速度，特别　是在搜索空间较大时更为明显；避免了编码中带来　的附加问题，便于与其他搜索技术相结台．　３基于遗传算法的神经网络学习算法　在基于实数向量编码的基础上，交叉操作采用　了凸集理论中的有关概念，变易操作通过随机产生　变易方向进行变易．　ｓｉｇｍｏｉｄ函数，（　）＝１／（１＋ｃ　）这里采用的函数，　可以根据输出数据的范围进行不同的选择适应度　＾　“　函数为网络的全局误差ｓ　＝∑∑（　一ｏ　）　，　Ｐ＝Ｉ　Ｊ＝Ｉ　其中，　．为标准输出，。　为实际输出，　为训练　集合中所含的输入模式数，ｎ为输出层神经元数．　步骤１　设定参数输人种群规模（ｐｏｐ　ｓｉｚｅ）、　交叉概率（Ｐ　）、变异概率（Ｐ　）、网络层数（不　包括输八层）、每层神经元数在算法的仿真当巾，　所使用的参数为：种群规模ｔｘ）ｐ　ｓｉｚｅ＝７０，交叉概　率Ｐ　０．１，变异概率Ｐ　＝０　６，　评价函数中的　参数ｎ为０．０５遗传算法对于这熙参数的设置有　非常好的鲁捧性，改变这些参数对所得的结果不会　有太大的影响　步骤２　初始化　随机产生初蛤种群Ｐ＝　．，　１．１一，　，任一　．∈Ｐ为　神经网络，它由　一个权值向量和一个闺值向量组成．杈值向量也为　维实数向量，ｎ为所有的连接杈的个数．阈值向　量为ｎ维实数向量（不包括输入层神经元）神经　元编号采用自低向上、自左向右的方法（包括输入　层神经元）．　可用正态分布的小随机数来初始　化，在后边的５Ｌ￣ＴＬａ，Ｂ仿真中使用ｍ×ｒａｎｄｎ（）函　数进行初始化，其中ｍ为一个足够大的数，以便　确定足够大的搜索空间　Ｒａｎｄｎ（）可产生一个０—１　均匀分配的随机数．　步骤３评估①根据随机产生的权值向量和　阈值向量对应的神经网络，对给定的输入集和输出　集计算出每个神经网络的全局误差作为适应度，即　，＝∑∑（　一　）　，其中　为输入第Ｐ个训练　口＝－ｉ　ｌ　样本时第ｉ个节点的输出值，　为期望的输出值，　为训练集合太小，　为输出层的神经元数②为　了进行排序选择，给已排好序的染色体设定选择概　率概率确定采用Ｍｉｃｈａｌｅｗｉｃｚ提出的指数排序法　ｅｖａｌ（　）＝Ⅱ（１一ｎ）‘一。，ｏ　Ｃ－（０，１），ｉ：１，２，－一．　ｐｏｐ—ｓｉｚｅ．ｉ＝１意味着染色体是最好的，　ｐｏｐ　ｓｉｚｅ说明是最差的．在后边的仿真中，取　ｎ：０．０５．　步骤４排序根据适应度从小到大排序，即　按染色体由好到坏排序，染色体越好，序号越小．　维普资讯 http://www.cqvip.com

２Ｏ００＿年第２期　２００２　２　李建珍：基于遗传算法的人工神经阿络学习算法　Ａ［ｅａｒｔｉｆｎｇ　ａｌｇ￣ｒｉｄａｍ　ｏｆ　ａｒｉｔｉｆｃｉａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｆｌ￣ｂａｓｅｄ　Ｏｉｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｆｆｍ］　并根据步骤３的结果给每个染色体按序号设定选择　概率．并保留最好的染色体．此最好染色体在后续　的进化中可被更好的染色体所替代．　步骤５保留最好染色体将适应度最小的染　色体（即最好的染色体）和当前已保留的最好的染　色体进行比较，如果误差变小，则保留薪的最好的　染色体．　步骤６　选择过程　选择过程是以旋转赌轮　ｐｏｐ—ｓｉｚｅ次为基础的，每次旋转都为新的种群选择　一个染色体，赌轮为每个染色体按序号设定的概率　选择染色体，同时保证最佳个体的选择　这样设定　选择概率，概率并不是正比于染色体的适应度值，　可避免在较早的代中一些超级染色体霸占选择过　程，而在较晚的代中种群集中在一起，染色体的竞　争减弱，变得像随机搜索．而保留最佳个体的选择　可使搜索过程收敛到全局最优解算法可表示如　下：　１１对每个染色体　计算累积概率ｑ　：　ｆ目。　０，　１　ｒ　、　＝∑ｅｖａｌ（ｖｊ．），ｉ＝１，２，…，ｐｏｐ　ｓｉｚｅ￣　２）从区间（０，ｇ　）中产生一个一致分布的　随机数ｒ；在ＭＡＴＬＡＢ中用ｒａｎｄ函数实现；　３）若ｑ　．＜ｒ≤ｑ　，则选择第ｉ个染色体　（１≤ｉ≤ｐｏＰ　ｓｉｚｅ）；　４）重复２）和３）共ｐｏＰ—ｓｉｚｅ次，这样可以得到　ｏｐＰ　ｓｉｚｅ个复制的染色体　如果在（ｐｏＰ　ｓｉｚｅ一１）次　选择过程中，没有出现第一个最好的染色体，则在　第ｐｏｐ　ｓｚｉｅ次选择时，直接选择第一个最好的染色　体　注：在上述过程中，并没有要求满足条件目卿岫＝１　实际上，可以用ｇ岬岫除以所有的　，　＝１，２…，ｐｏｐ—ｓｉｚｅ，　使９…：１，新得到的概率同样与适应度成比例，只要　不介意概率方面解释上的困难，这一点并没有在遗传过程　中产生任何影响　步骤７交叉并评估过程前面已经指定了参　数　作为交叉的概率，这个概率说明种群中有期　望值为Ｐ　ｐｏＰ—ｓｚｉｅ个染色体进行交叉操作．　为确定交叉操作的父代，从ｉ：１到ｐｏｐ　ｓｉｅｚ　重复以下过程：从区间　０，１］中产生一个一致分布　的随机数ｒ，如果ｒ＜Ｐ　，则选择　作为一个父　代．如果用　，　；，　，…表示上面选择的父代，并　把它们随机分成下面的对（　，　），（　．　ｊ），・　进　行交叉　以（　，　）为例对所进行的交叉操作解释　如Ｆ：从开区间（０，ｍ）中产生一个随机数　，在　ＭＡＴＬＡＢ中可用ｍ×ｒａｎｄ（）函数实现，ｍ可根据不　同的输出进行调节以便覆盖解集　交叉形式如下：　＝Ｃ　ｘ　＋（２一ｃ）ｘ　，Ｙ＝ｔ２一ｃ）×　＋ｃ　ｘ　，其中　和ｖ为后代，　和Ｙ的替换对象分别为　２个父代　和　．交叉完后，为了考察其优劣，　还原出对应的神经网络并进行性能评估对同一对　父代．为了尽可能交叉出好的后代，允许进行多次　交叉，在交叉中只要有一个后代优于或２个后代都　优于其对应的父代，则替换其父代，结束该对父代　的交叉，否则，对泼对父代进行下一次交叉在下　一次的交叉中，取ｍ＝　×ｒａｎｄ，直到找出优于其　父代的后代．　这里采用的交叉方法基于凸集理论　一般　地，２向量　和　加权平均计算如下：　＋　２　２．　ｌ＋　２＝Ｉ、　ｌ＞０，　２＞０，则加权形式为　凸组合；若去掉非负，则称为放射组合；如果　仅要求乘子为实数，则称为线性组合类似地，交　叉运算被定义成了２个向量（染色体）的如下组　合　＝　１　１＋　２　２，ｘ；＝　１＋　］　，按对乘　子的不同，可获得３种交叉，分别称为凸交　叉、放射交叉和线性交叉、几何解释如下：对于双　亲３７　和　：，其所有凸组合的集合称为凸壳　（（ｙｏｎｖ￣ｘ　ｈｕｌ１）．类似地，称所有放射组合的集合为　放射壳，所有线性组合的集合为线性壳．图１显示　的是２维空间的情况．　田１凸壳、仿射壳和线性壳　凸交叉产生的后代位于实线段，仿射交叉的后　代位于虚线段，而线性交叉的后代分布在整条直线　上．这里采用线性交叉，并乘子为＾．＋＾　≤　２，＾ｌ＞０，＾２＞０　即让ｍ＝２．　维普资讯 http://www.cqvip.com

西北师范大学学报（自然科学版）　Ｊｏｕｎａｌｒ　ｏｆ　Ｎｏｒｔｈｗｅｓｔ．Ｎｏｒｍａｌ　Ｕｒｄｖｅｒｓｉ￣（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　第３８卷　Ｖ０】３８　步骤８变异并评估操作前面已经给定了变　异概率Ｐ　，这个概率表明总体中有期望值为Ｐ　×　ｐｏｐ　ｓｉｚｅ个染色体用来进行变异操作　类似于交叉过程中父代的选择，由ｉ＝１到　ｏｐＰ　ｓｉｚｅ．重复ｒ列过程来选择变异的染色体：从　０，１］中产生随机数ｒ，如果ｒ＜Ｐ　则选择　作　为一个父代．　对选择好的每一个要变异的染色体．为ｌｒ尽可　能进行好的变异．允许进行多次变异．变异时．首　先随机生成一个与染色体的各权值、闽值同维数的　向量ｄ　和也作为变异方向（ｄ　和　可用产生正　态分布的随机数的函数ｒａｎｃＬｎ（）产牛）．然后用父代　染色体的权值　闽值对应的向量分别和向量ｍ×　ｄ．，　×ｄ　相加剥每次变异结果．还原出神经　络井进行性能评估如果后代优于父代则结束该父　代的变异．否则，对该父代进行下一次变异．在下　次的变异中，取　一　×ｒａｎｄ，直到找出优于其　父代的后代．　步骤９如果Ｊ列络误差满足要求，或达到　定　的进化代数，停止进化，输出进化结果；否则　转　步骤４．　３实验结果和分析　定理１　如果隐层的节点可　根据需要自由　设置，那么用３层（不包括输人层１的阈值网络可　以实现任意的二值逻辑．　根据定理１，为了考察算法的普适性，这里选　用２个２层网络和一个３层网络（不包括输人层）　在ｂｔ４ＴＬ￣，Ｂ环境中对优化学习算法是否收敛解、收　敛精度、最大世代数、变异和交叉概率等性能进行　测试，并与ＢＰ算法进行了性能比较．测试时，适　应度函数定义为误差平方和（ｍ　），激活函数隐层　使用ｔｍ￣ｓｉｇ函数，输出层使用ｌｏｇｓｉｇ函数　１）２异或同题和模式长度为３的奇偶问题．　这是一个容易陷入局部最小的问题，并且需要隐　层．ＸＯＲ问题采用一个全连接的单隐层前向网络，　输入层２个节点，隐层２个节点，输出层１个节　点　；模式长度为３的奇偶问题采用一个为单隐　层前向网络，输入层３个节点，隐层４个节点，输　出层１个节点　２）ＩＲＩＳ模式分类问题．ＩＲＩＳ类问题来源于著　名的ＵＣＩ机器学习数据库　，该问题的背景知识　包括：概念集｛Ｓｅｔｏｓａ，Ｖｅｒｓｉｃｏｌｃｕｒ，Ｖｉｒｇｉｎｉｅａ｝；连续属　性及取值范围：Ｓｅ　ｌｅｎｇｔｈ（４　３Ｏ～７．９０）．￣：ｐａｌ　ｗｉｄｔｈ　ｃ２．Ｏ０～４．４０），Ｐｅｔａｌ　ｌｅｎｔｈ（１．００～６　９０），　ｄｔｈ（０　１０～２．５０）一卜述数据为取自ＵＣＩ机器学习　数据库中心的数据集ＩＲＩＳ．它是Ｆｉｓｈｅｒ教授提出的　著名的花朵识别数据集（Ｉｒｉｓ　ｄａｔａ　ｓｅｔ）该数据集共　有１５０条设划分为３条决策的记录．每条记录包含　Ｌ述４个属性．　在各种人工神经刚络模型中，在模式识别中应　用最多的也是最成功的是多层前馈网帑．其中义以　采ｌ崩ＢＰ学习算法的多层感知器ｆ习惯１　也简称为　ＢＰ网络）为代表．在此采　：输八　４个节点，　第一隐层８个节点，第二隐层４　ｌ，、节点，输出层３　个节点的舣隐层全连接的｝垌络来验证（　算法枉２　个隐层和增加节点的情况Ｆ的性能。．蚪＿ｊ　ＢＰ算　法进行ｒ比较　埘每个测试问题连续测试】０次．测试结果　表１～３．　表１　２个输入的异或测试结果　算法——…　最好　最差　连代步数　６＿而　０：　３７　ｏ≮一７１３一Ｉ＿１０－　４０　ＢＰ　０　０００９　０　６７３　９　０　２３６　５　表２模式长度为３的奇偶问题的测试结果　算击一——一——　一——　最好　最差　平均　选　代步数　１５０　表３　ＧＡ和ＢＰ算法在ＩＲＩＳ问题上的性能比较　４结论　遗传算法发挥了它的优势，这是　为它和常规　的优化算法相比有几个方面的不同，可归纳如下：　１）ＧＡ不直接和参数打交道，而是处理代表参　数的数字串．　２）ＧＡ在解空间中不　ｌ是局限于　，而是同　时处理一群点，这样可　避免陷八局部解．　３）在寻优过程中，ＧＡ不需要目标函数的微　维普资讯 http://www.cqvip.com

螂ｌ２年第２捌　ｘ】２　，　２　李建珍：基于遗传算法的人工神经附络学习算法　＾ｌｅａｒｒｉｆｒ￣ｇ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ａｒｔｉｆｉｅｉ，￣ｎｅｔｕＭ　ｎＯｗｏｒｋ】】ａ　ｄ　ＯＨ￣ｅｎｅｆｉｅ山ｏｎｆｉｍ　分，只需月标函数的值．　４）（，Ａ的寻优规则不是定性的，而是由概率决　定的　是山Ｊ　上述特点，遗传算法枉多峰函数（即　有多个极值）的优化过程中，具有无比的优越性，　避免了ＢＰ尊法的不足．　参考文献　１　ｊ　Ｄａ、１一ｌ肌ｎ　∞　ｏｆ（Ｊｅｏｆｔｗ，４）ｇｏｎ￣＇ｈｒａ．ｔ［Ｍ－Ｎｅｗ　Ｙｏｒｋ　Ｖ　［１１　Ｎｏ￣ｒｍｕ｝Ｒｅｉｎｌｍｈ１．】９９】．　２』　Ｍｋ　ｈａｌｃＧｅｚ　ｚ．（　嘲　ｇ。ｒ（ｔｈｍ十ｎⅡⅡｓ　州　（上接第３：页）　】Ｉ　＜２　１　｛Ｉｆ（【Ｙ．是偶数且　：４ｉ＋，，　：】，２）ｌ】Ｔ　（　是奇数且　＝４　Ｌ　Ｊ，Ｊ＝０，３）且　）ｏｒ（（Ｙ　是奇数且　：＝４ｉ＋Ｊ．　＝Ｉ，２１　ｏｒ（　是偶数且ｔ＝４ｉ＋　，　＝Ｏ，３）且Ｙ．　Ｙ　）ｓｅ　（　）：　Ｅｌ∽ｉｆ△　是偶数Ｓｅｎｔ（一ｓｇｎ（　一　）　）；　Ｅｌｓｅ　ｉｆ　是奇数ｓｅｎｔ（ｓ　（Ｙ　一　）　）；　／＊　位于边界的特殊点上＊／　Ⅱ（（≈＝ｌ　ｏｒ冀＝　一２）且血是偶数）　Ｓ廿　（　）：　。＂￣＇ｋｉｆｌｅ（０≤　≤ｎ一１　ｏｒ０≤　≤ｍ～１）　关于算法的几点说明：　１）算法的初始，为了准确实现平二直一的最　短路径．对源点位置（Ｙ　，　）做了适当调整这个　调整在广播的前２步就可完成，之后不再改变，不　影响算法效路．　２）图３中　，ｓ．，　，ｓ　４个点的广播路径是相　Ｅｔｖ４ｚ￣ｔｉｏｎ　Ｐｒｑ￣ｗｎｓｌ　Ｍ　２ｎｄ　ｅｄ．Ｎｅｗ　Ｙｏ＆：ｓＰｎ　Ｖｅｒｌａｇ．１９９４　ｌ　３：　Ｂａｚａｒａａ　Ｍ，Ｊａｒｖｉｓ　Ｊ，Ｓｈｅ吼ｌｉ　Ｈ　ｌＪｅｔｅａ＊，　Ｈ　Ⅱ　洲，　妇　Ｆｌｏａ￣［Ｍ　Ｊ　２ｎｄ　ｃｄ　Ｎｅｗ　Ｙｏｒｋ　Ｊｏｔｍ　Ｗｉ］ｅｖ＊　ＳｏＩ１Ｓ，ｌ９９０　４　郑南宁　计算机视觉与模式识别【、１　北东：人【　邮电出　社　ｊ９９６　ｌ　５］王磊，戚　虎进化　＿　在神经＿卅终学　叶１的应　用Ｊ１计算机工程，１９９９，２５ｔｌＩ）：４１　４３．　一６　Ｊ　Ｆｉｓｈｅｒ　Ｉ］｜ｊ　Ｋｎｏｗｌｅｄｇｅ　ａｅｃ￣ｄｓｉｔｉｍ］、ｉａ　Ｊｎｅｒ￣［ｒ岫１ｔａｌ　ｃｏｎｃｅｐｔｕａｌ　ｃｈ￣ｔｃｒｉｎｇ　ｌｌ　、＾㈣　ｍ　＊　Ｉ９８７（２　】３９　１１１　同的，从它们引出的４条台阶式路径构成关键路径　【即圈　晟粗的路径），把ＳＭ分为４个逻辑ｒ刚　３）算法使每个结点恰好接收消包一次，无冗　余消息产生．　４）广播树的高度不超过阿络直径『ｊ，困而算　法的时间复杂度为０（　＋　）　５）网络中每个当前结点　根摊自己和源结点　的位置决定下　步的路由选择，减少ｒ消息携带的　网络状态信息，因此算法是基于局部信息的．　参考文献：　［１　１屈玉贵，粱晓耍并行处理系统结构［Ｍ］台肥：　中国科技大学出皈社，１９９＇９．２９＠３２０　［２］［美］Ｈｗａｎｇ　Ｋ高等计算机系统结构——并行性、可　扩展性、可编程性　Ｍ］王鼎兴．沈美明．邦伟民，　等译北京；清华大学出版社，１９９５．３０】～３１５　３　Ｊ　Ｃｈｉｎ　Ｇ　Ｍ，Ｗｕ　Ｐ　Ａ　ｆａｕｌｔ—ｔｏｌｅｒａｎｔ　ｒｏ￣ｒｔｉｔｔｇ　ｓｔｒａｔｅ￣，ｉＪ１　—ｈ？ｐｅｒｃｕｂｅ　ｍｕｌｔｉｅＯｍｌｌｕｔｅｒｓ【Ｊ　ＩＥＥＥ　Ｔｒａｍ（　，　１９９６，４５（２）：】４３＿Ｉ１５４　（责任编辑惠船骐）