（检测技术与自动化装置专业论文）gacca混合优化算法及其在神经网络应用中的研究.pdf

g a - c g a 混合优化算法及其在神经网络应用中的研究 专业：检测技术与自动化装置 硕士生：刘文谊 指导教师：李晓东副教授 摘要 当前，计算智能算法作为人工神经网络、模糊系统和进化计算三种算法的融 合，被越来越多的学者研究，成为人工智能的一个新的研究领域。 为了进一步扩展计算智能算法的性能，在深入分析的基础上，本文首先介绍 一种传统的优化算法共轭梯度法( c o n j u g a t eg r a d i e n ta l g o r i t h i n ，简称 c g a ) ，并且对该算法进行改进，然后对计算智能算法之一遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 进行改进，最后将改进g a 和改进c g a 有机结合，提出了一 种新型的g a c g a 混合优化算法。为了验证该g a c g a 混合优化算法具有良好的优 化性能，本文将该混合优化算法用于神经网络的权值训练。 另外，为了进一步验证c a c g a 混合优化算法在神经网络的应用领域内同样 具有良好的性能，本文将其用于系统辨识及盲信号分离中神经网络模型的训练， 取得了理想的训练效果，达到了优化的目的，为计算智能算法的应用研究提供了 一种新途径。 关键词：g a 算法，c g a 算法，g a c g a 混合优化算法，盲信号分离，系统辨识 h y b r i dg a c g ao p t i m i z a t i o na l g o r i t h ma n dr e s e a r c h o fi t sa p p l i c a t i o ni nn e u r a ln e t w o r k m a j o r n a m e s u p e r v i s o r d e t e c t i o nt e c h n o l o g ya n da u t o m a t i o nd e v i c e w e n j y il i u a s s o c i a t ep r o f e s s o r , x i a o - d o n gl i a b s t r a c t n o w a d a y s ，c o m p u t i n gi n t e l l i g e n c e ( c i ) h a sb e e ns t u d i e db ym o r ea n dm o r e r e s e a r c h e r s a sac o m b i n a t i o no f a r t i f i c i a ln e u r a ln e t w o r k 、f u z z ys y s t e ma n de v o l u t i o n m y c o m p u t a e o n ，c ii san e w s c i e n t i f i ca p p r o a c hw i t ht h ed e v e l o p m e n to f a r t i f i c i a li n t e l l i g e n c e i no r d e rt of u r t h e rf a c i l i t a t et h eo d 6 m i z i n go fc i ，t h i st h e s i sp r o p o s e sa ni m p m v e d c o n j u g a t eg r a d i e n ta l g o r i t h m ( c g a ) ，b a s e do na ni n - d e p t ha n a l y s i st oo r i g i n a ls t a n d a r d c g a 。t h e n ，a ni m p r o v e dg e n e t i ca l g o r i t h m ( g a ) a sak i n do fc ii sp r o p o s e d 。f i n a l l y , a n n o v e lh y b r i dg a c g a a l g o r i t h mi sp r e s e n t e db yo r g a n i c a l l yc o m b i n i n gt h en 鲫i m p m v e d c g aa n dt h en e wi m p m v e dg a t ov a l i d a t et h ep e r f o r m a n c eo ft h ep r o p o s e dh y b r i d g a c g a a l g o r i t h m t h ea l g o r i t h mi sa p p l i e dt ot h et r a i n i n go f a r t i f i c i a ln e u r a ln e t w o r k 。 m o r e o v e r ，t h i st h e s i si n v e s a g a t e st h ea p p l i c a t i o n so ft h ea r t i f i c i a ln e u r a ln e t w o r k b a s e do nt h ep r e p o s e dh y b r i dg a c g a ，s u c ha sb l i n d s i g n a ls e p a r a t i o n ，s y s t e m i d e n t i f i c a t i o ne t c g o o do p n m i z e dp e r f o r m a n c e sa r ea l s oo b t a i n e d t h e r e f o r e ，t h eh y b r i d g a _ c g aa l g o r i t h mp r o v i d e san e wd i m e n s i o nf o rr e s e a r c ho fc ia l g o r i t h m - k e yw o r d s ：g e n e t i ca l g o r i t h m ( g a ) ，c o n j u g a t eg r a d i e n ta l g o r i t h m ( c g a ) ，h y b r i d g a - c g a a l g o n t h m b l i n ds i g n a ls e p a r a t i o n ，s y s t e mi d e n t i f i c a t i o n i i 中山火学硕l 学位论文 第1 章引言 1 1 论文研究的意义和目的 1 9 9 4 年，关于人工神经网络、进化计算及模糊系统的3 个i e e e 国际学术 组织在美国奥兰多联合举行了首届计算智能世界大会，原本属于3 个不同学科 的学者们聚集在一起，提出了计算智能的概念。按照j a m e sc b e z d e k 的观点， 计算智能系统”即：“当一个系统仅仅处理底层的数据，具有模式识别的部分， 并且不使用人工智能意义中的知识，那么这个系统便是计算智能系统。” 计算智能系统具有自组织、自适应、自学习等明显的智能特征，计算智能 系统优化算法通过“拟物”与“仿生”的方式来解决实际工程问题，已在复杂 系统的智能控制、信息安全、工程设计、图像处理、调度规划、优化理论等领 域发挥重要应用“，其中以神经网络与进化算法应用最为广泛。神经网络由于 并行性和非线性映射能力，目前在函数逼进、模式识别、系统辨识、信号处理 等方面有了广泛的应用“；进化计算“主要是指遗传算法( g e n e t i ca l g o r i t h m ， 简称g a ) ，由于其良好的全局搜索能力，常常被用于神经网络权值训练上，同神 经网络模型共同交叉用于计算智能系统中。 对于优化算法，共轭梯度法“”( c o n j u g a t eg r a d i e n ta l g o r i t h m ，简称c g a ) 是优化算法中最传统的方法之一，它具有算法简便，收敛速度快、存储需求小等 优点，十分适合于大规模优化问题。这就可以解决智能算法由于是“仿生”而造 成计算复杂，优化时间慢的不足，目前在石油勘探、大气模拟、航空航天、信号 检测等领域出现的大规模优化问题常常利用c g a 来优化。 对计算智能优化算法的改进，要么在单一领域内提高性能，最终结果就是要 提高优化算法的收敛性能、时间性能( 优化效率) 两个方面，要么就扩大某种单一 算法的应用领域，这两个研究方向必然是计算智能算法研究方向之一。但是随着 科技的发展和工程问题范围的拓宽，实际问题的规模和复杂度越来越大，单一算 法的优化效果往往不够理想，同时单一算法理论研究的落后也导致单一算法性能 中山大学硕士学位论文 改进程度的局限性，而基于自然机理来提出新的优化思想是一件很困难的事。基 于这种现状，算法混合的思想已发展成为提高算法优化性能的一个重要且有效的 途径，其出发点就是使各种单一算法相互取长补短，产生更好的优化效率和优化 性能，这也是符合计算智能提出的初衷。 另外，通过不同的算法混合，又可以将各自的适用范围统一起来，这样相对 扩大了单一算法的应用范围。这正是本文所要达到的目的，既能获得在单一应用 领域内有良好性能的改进算法，又能扩展单一优化算法的应用范围，一举两得。 1 2 论文研究的主要内容及成果 论文研究重点集中在设计有良好收敛性能与时间性能的计算智能算法上。由 于传统的g a 算法是一种概率性的并行寻优算法，群体缺少明确的寻优方向，将 其用于寻优计算，虽然全局收敛性好，但是寻优速度慢，局部搜索能力差。作为 非智能优化算法的c g a 基于共轭方向并行搜索方向，寻优方向明确，数据计算虽 小，搜索速度相对于g a 来说要快，正好可以取长补短。将共轭方向引入到g a 算 法中，这样就形成了一种新的计算智能算法。本文分别针对g a 、c g a 的缺点进行 改进，最后将共轭方向引入改进g a 中，提出g a c g a 混合优化算法，并将上述二 种算法用于神经网络的权值训练中，统一比较优化性能。 计算智能算法应用研究才刚刚起步，日前还没有完善的理论及应用体系，许 多应用问题还处于研究阶段。由于神经网络的应用领域相对较广泛，本文对基于 g a - c g a 混合优化算法的神经网络进行应用研究，从而在神经网络的应用领域， 该混合优化算法也能涉及，并町能取得良好的优化性能。本文选取神经嘲络在控 制领域及信号检测领域中具有代表性的系统辨识问题和盲信号分离问题来进行 混合算法应用研究。 围绕改进计算智能算法，扩展单一计算智能算法的应用领域的目的，论文研 究的主要内容及成果有： ( 1 ) 提出一种新型改进c g a 算法，围绕重启策略、寻优方向两个c g a 的核心 内容提出相应改进策略。并文现了该改进算法，并用丁神经网络权值训练，作为 其性能测试的标准。 中山大学硕士学位论文 ( 2 ) 提出改进g a ，围绕参数编码、适应度函数设计、交叉、变异算子四个 g a 的主要因素提出相应的改进策略，并将其用于神经网络的权值训练上，作为 其性能测试的依据。 ( 3 ) 在新型改进c g a 及改进g a 的基础上，提出一种新型的g a c g a 混合优化 算法的设计思想，并且基于该设计思想，本文实现了g a c g a 混合优化算法的设 计，并同上述两种算法在神经网络平台上进行性能对比测试。 ( 4 ) 为了验证g a - c g a 混合优化算法在神经网络的应用领域中的优化性能， 本文将该算法在系统辨识和盲信号检测问题上进行了初步的应用研究，得出了比 较好的优化效果。 论文内容共分成五章，在接下来的内容中，第二章介绍了c g a 及其改进：第 三章介绍标准g a 及其研究现状，提出改进的g a ；第四章介绍基于改进g a 、改进 c g a 的混合优化算法及其实现，且对比三种算法的优化性能，验证c a c g a 混合 优化算法的良好性能。第五章将基于g a c g a 混合优化算法的神经网络应用于系 统辨识及盲信号检测这两个工程实例上，进一步验证g a - c g a 混合优化算法的有 效性与实用性。 中山人学硕 = 学位论文 第2 章非线性共轭梯度法( c g a ) 及其改进算法 c g a 是最优化算法中最传统、最简单的算法之一，在所有需要计算导数的 优化方法中，拟牛顿算法收敛速度很快，被广泛认为是非线性规划的最有效的 方法。但拟牛顿算法需要存储矩阵以及通过求解线性方程组来计算搜索方向， 这对大规模问题几乎是不可能办到的。而近年来随着计算机的发展，许多应用 领域如电力分配、信号检测、石油勘探等提出来的无约束优化问题规模也越来 越大，这时由于拟牛顿算法需要存储大型矩阵往往失效。而非线性c g a 算法简 便、存储需求小、收敛速度不比拟牛顿法慢很多，特别适合求解大规模问题。 在上述领域中出现的大规模优化问题常常利用非线性c g a 来求解的“。 2 1 非线性c g a 的数学描述 共轭向量的定义如下： 设有n 个非零向量d 。，一，以一，和一个对称阵a ，若对任意的f ，j ( i _ ，) 有 ( a i ) 1 彳d ，= o ，f ，j = 0 ，肝一1 ( 2 一1 ) 则称矾，矾，以一，是相互a 共轭。a 称为系数矩阵。 非线性c g a 最早是由计算数学家h e s t e n e s 。1 和几何学家s t i e f e l 。1 在二十世 纪五十年代初为求解线性方程组 a x = b x r + 而独立提出的”。，1 9 6 4 年f l e t c h e r 和r e e v e s 将此方法推广到非线性最优化，得 到了求一般函数极小值的c g a 。：。 求解无约束优化问题 m i n f ( x ) ，x r “ ( 2 - 2 ) 本文考虑线搜索( 即精确线搜索) 型的c g a ，其具有如下形式： 4 - 中山大学硕t 学位论文 x k + l = x k + 矾， 巩： 一， 4 【一g i + 羼巩 k = i ； k 2 ： ( 2 3 ) ( 2 - 4 ) 其中g k = v f ( x k l ，d k 为搜索方向， a k o 是通过某种线搜索获得的步长。纯 量舷的选取应满足共轭性，即当f ( x ) 为严格二次函数且采用精确线搜索时，由 式( 2 4 ) 产生的搜索方向d 。关于f ( x ) 的海赛阵共轭。此外，当f ( x ) 为严格凸二 次函数时，c g a 在精确线搜索下具有限步终止性，但对一般连续可微函数，这 一性质很难保证。 羼的不同取法构成了不同的非线性c g a “，比较常见的屏的计算公式有 冉器， ， 日g t 7 ( g i g k - i ) 矿2 眢 屈”= 玎g k r ( 百g k - 雨g * - i ) 展。= 霜- i i g i , i i 对于无约束问题( 2 2 ) ，我们假定其中的目标函数_ 厂( 曲满足： 假设2 1 ：( 1 ) ，( x ) 在水平集上= 仁r i ， ) 厂( 五) 上有下界； ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 ) 在上的一个邻域n 内，( x ) 连续可微且其导数w ( x ) 满足 l i p s c h i t z 条件，即存在常数m 0 ，使得 l l 盯( x ) 一1 盯( 譬) 【l m h x i i l ，v x ，譬n ( 2 9 ) 2 2 非线性c g a 的算法流程 在实际应用中，进行c g a 循环时，每输入一次训练样本称为一个周期，循 环是一个周期一个周期地进行，直到目标误差e 达到最小值( 即不再减小) 或小 中山大学硕：学位论文 于某一给定值。目标误差e 一般取平均误差的均值，如公式( 2 一l o ) 所示，或取 为平方误差和，如公式( 2 一1 1 ) ： m s e = 万1 著n e 2 ( s s e = p 2 ( 七) k = i 其中n 是循环次数，k 为循环步数。 ( 2 1 0 ) ( 2 一1 1 ) 非线性c g a 可综合概括如下； 算法2 1 ： 非线性c g a 优化流程图如图( 2 - 1 ) ，非线性c g a 步骤： ( 1 ) 选取初始权值坼。 ( 2 ) 给定z i r n , 占( 0 , 1 ) ； d t = 一g l = 一v f ( x ) ，k = 1 ( 3 ) 在第，步，利用某种方法求，并计算。= 也+ 吼以。 ( 4 ) 计算凰和l b l | ，如果满足条件恬。忙占算法则停：s 是初始设定的，在实际 运行中为目标误差。 图2 - 1c g a 优化流程图 中山大学硕l 学位论文 ( 5 ) 计算新的梯度：g ( 6 ) 利用某公式计算尾 d k + 1 = 一g + 屏+ i d k ：k = k + 1 转步2 。 由算法可知，一个线搜索型的算法的每步迭代主要由两部分组成；第一是 搜索方向d 。的计算；第二是步长因子瓯的计算。其中搜索方向d k 已给出，其 中屏分别按照( 2 5 ) ( 2 - 6 ) ( 2 - 7 ) ( 2 - 8 ) 取值，则称相应的算法为f r 算法、p r p 算法、h s 算法、c d 算法。而对于步长因子的确定有多种方法，线搜索可分 为精确线搜索和非精确线搜索两大类，精确线搜索包括极小化原则和c u r r y 原 则，非精确线搜索包括w o l f e 原则、强w o f e 原则、a r m i j o 原则。 本文采用精确线搜索中的极小化原则，即沿射线k + 耐。【口 o 求，( x ) 的极 小，即选取瓯 0 使得：低托t 4 ) = 商j l ，魄+ 峨) l a 0 。 2 3 非线性c g a 的特点及主要缺点 2 3 1 非线性c g a 的特点 非线性c g a 计算导数，但采用共轭方向进行优化，它具有同其他计算导数 的优化方法有不同的特点。 ( 1 ) 共轭方向能将一个n 元线性方程组化为n 个单元线性方程组，这样就 降低了算法的复杂度，算法简便，存储需求小，对解决大规模问题有良好的性 能。 ( 2 ) 另外采用精确线搜索的c g a 具有有限终止性，即在第一个搜索方向是 最速下降方向时，可证明不超过r 1 次迭代就可能找到最优点，这使得c g a 不会 陷入平台，能够自动寻找到最优点。 ( 3 ) 由于非线性c g a 搜索方向明确，数据运算量小，其收敛速度相对来说 比较快。 中山大学硕t ：学位论文 2 3 2 非线性c g a 的主要缺点 非线性c g a 本质上也是基于梯度的寻优算法，必然也存在许多自身的不足。 ( 1 ) 非线性c g a 的全局搜索能力差 非线性c g a 第一步也是基于梯度信息的非线性优化方法，不可避免存在局 部极小问题。而且实际问题的求解空间往往是极其复杂的多维曲面，存在许多 局部极小点，更使这种陷于局部极小点的可能性大大增加。 ( 2 ) 搜索参数的选择 非线性c g a 的两个搜索参数a 。和成的选择决定了c g a 的搜索速度和搜索精 度，屈选择不好将无法达到数值表现和全局收敛性上的最优，f r 方法理论上有 很好的全局收敛性，但该方法在计算中不是很有效，存在很大误差；p r p 方法 是数值表现最好的非线性c g a 之一，但采用精确线搜索也不一定收敛；c d 方法 的收敛性能也不好。所以如何选择合适搜索参数目前主要是靠经验或试探，没 有系统的理论指导。 ( 3 ) 由于舍入误差破坏了寻优方向的共轭性，因此采用重开始策略势在必 行。 2 4 一种新型改进c g a 由于非线性c g a 的一些不足，本文提出了一种新型的改进c g a ，该算法在 精确线搜索的基础上，以再开始策略和寻优方向为主要改进目的，将收敛速度 与全局收敛性的协同为设计重点，始终作为新型改进c g a 的主线。 在c g a 的优化过程中，良好的寻优方向决定了算法的收敛速度，要提高c g a 的收敛速度，又要保持其收敛性。因此，在共轭梯度的前提下寻求更好的下降 方向，显得尤为重要，新的下降方向的寻找成为新的算法设计的重要坏节之一。 改进c g a 的另一重要环节就是再升始策略，由于舍入误差的影响，使寻优 方向的共轭性得到破坏，无法达到全局最优，因此必须选择一种再_ 开始策略。 但是由于算法要进行重开始，如果与搜索方向结合的不好就会造成收敛速度减 8 中山大学硕l 学位论文 慢，这就牺牲了收敛速度来换全局收敛，所以寻找合适的算法结构也非常重要。 2 4 1 算法改进的设计步骤 一、寻优方向 在精确线搜索条件下，对寻优方向的改进主要有预条件c g a “1 、多信息 c g a 、自调比c g a ”1 。合适的下降方向，有利于提高c g a 的收敛速度，改善收 敛精度，提升该算法的整体性能。寻优方向的改善主要考虑到下述两个方面：一 是要保持寻优方向的共轭梯度性，这才能保持其算法简便、存储量小等优点。 二是希望寻优方向能包括更多的目标信息，提高c g a 的全局收敛性。 基于以上两点考虑，参照文献 4 1 3 提出的寻优方向公式，提出改进c g a 的寻优方向的设计公式如下： d t = 一h g i + 屁以一1 + p k d t ( 2 - 1 2 ) d 。作为再开始方向，p k = 乳t y t 一，4 一。7 j ，。，这里k h ，f 是再开始位置，其中 ，h 为条件预优矩阵，它的选择应该使矩阵 2 v 2 f ( x 。) h2 的条件数尽可能小。 二、再开始策略 再开始策略就是为了保持寻优方向的共轭性，这对扩大收敛范围，提高收 敛精度有重要作用。目前常用的再开始策略有f l e t c h e r r e e v e s 策略。3 、p o w e l l 策略”1 两种。f l e t c h e r r e e v e s 策略是第一个再丌始策略，其思想就是在每t 次 或t + 1 次迭代后，以该点的负梯度方向作为寻优方向实行重新开始，该方法简 单易行，但过于”机械“，而且作为单纯的梯度方向，不易扩大优化范围，容 易陷入局部最优当中。p o w e l l 提出了新的再开始准则： 设 r ：丛生( 2 一1 3 ) g 。b i g k 一1 若，0 2 ，则迭代被再开始。这种再开始策略只提供了一种开始判决准则， 群 ，鱼 中山人学硕l ：学位论文 没有新的寻优方向，将本文提出的新的寻优方向与p o w e l l 准则结合，作为新的 优化方向，这样应该能收到良好的数值效果。 2 4 2 改进c g a 的算法流程 一、算法流程 参照传统非线性c g a 的流程，本文设计一种改进c g a 算法，其流程如图2 2 所示，其步骤如下： ( 1 ) 给定参数c ，c 2 ( o ，1 ) ，岛( 1 ，) ，s 0 , 1 ) ，初始化值x 。r ”；令搜索方向 d 1 = g l ；k = t = 1 。 ( 2 ) 若k = 1 ，转步骤( 5 ) ，若k f ”，令f = k 一1 ：否则，若k 2 且 l g r _ , g 。【 c l l l g 。8 2 ( 2 川) 也令r = k 一1 ： ( 3 ) 若k t + 1 ，按如下公式计算以并转步骤( 4 ) ： d = 一i + f l k d t 一1 十p k d , ( 2 - 1 5 ) 其中参数由以下两式定义： 屈= 差端和p k = g k r y , - , 吐q 7 y h 。 否则，若k = t + 1 ，在( 2 一1 5 ) 式中令p 。= 0 计算巩。转步骤( 5 ) 。 ( 4 ) 如果 一c 3 t l g 。1 1 2 d 7 t g 。 ，( x ) ，所以叫上界构造法。 下界构造法的公式为： f i t ( f ( x ”= 而1 ( 3 3 ) 其中f ( x ) 是待求解函数，善是f ( x ) 的一个可行解，f i t ( f ( x ) ) 是适应度函数，其 中c 0 和c + ，( 力0 ，且当一c 是f ( x ) 的下界m i n f ( x ) 时，f i t ( m i n f ( x ) ) = 1 。另 外c 一和c 都是事先设定的估计值，不可能精确。 ( 3 ) 线性定标；为抑制早熟，保持群体的多样性，必须缩小超级个体得适应 度，而对于漫游现象，应该放大较优个体的适应度，这种适应度得缩放调整称为 适应度定标1 。一般采取线性调整法来调整适应度，其表达式如下： f i t 。( 厂( x ) ) = a f i t ( f ( x ) ) 十6 ( 3 - 4 ) 其中期。( 厂( 功) 是调整后的适应度，f i t ( f ( x ) ) 为原适应度，a 和6 可通过多种途 径设置，但必须满足f i t ( ，( x ) ) 与- f i t ( f ( x ) ) 的甲均值相等且而( 八z ) ) 是f i t ( f ( x ) ) 的指定倍数。 四、g a 的基本操作 在g a 中，问题的解称为个体( i n d i v i d u a l s ) ，个体对环境的适应稃度用适 应度( f i t n e s sv a l u e ) 表示( 一般对应于目标函数) 。个体的适应度决定于它 中山大学硕学位论文 本身的染色体( c h r o m o s o m e ) ，在算法中染色体一般用某一长度的二进制编码表 示，编码中的每一个位称为一个基因( g e n e ) 。一定数量的个体组成一个群体 ( p o p u l a t i o n ) 。g a 是群体型的操作，该操作以群体中的所有个体作为对象， 将他们置于问题的环境中，根据适者生存的原则，从中选择出适应环境的个体( 即 适应度较高的个体) ，进行复制。通过交换、变异两种基因操作产生出更适应环 境的新的一代( n e wg e n e r a t i o n ) 群体，这样一代一代地不断进化，最后收敛到 一个最适合环境的个体上，求得问题的最优解。 标准g a 的基本操作包括选择复制( s e l e c t i o n r e p r o d u c t i o n ) 、交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) ，称之为遗传操作( g e n e t i co p e r a t o r ) 或 遗传算予。1 。 ( 1 ) 选择复制 选择过程是模仿自然选择现象，从父代群体中选出优良个体。个体的适应度 值越大，在子代中将有更多的机会作为父代产生一个或多个子代个体。常用的选 择复制算子主要有三种：适应度比例法。1 ( 赌轮方式， r o u l e t t ew h e e l e ) ，该法 中的各个体选择概率和其适应度值成比例；排序选择方法( r a n k b a s e d m o d e l ) ，排序选择法是指在计算每个个体的适应度后，根据适应度大小顺序对群 体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概 率。故选择概率与适应度无直接关系而仅与其序号相关；联赛选择方法 ( t o u r n a m e n ts e l e c t i o nm o d e l ) ，该方法十分简单，其操作思想是，从群体中 任意选择一定数目的个体( 称为联赛规模) 将其中适应度最高的个体保存到下一 代，这一过程反复执行，直到子代群体规模达到预先设定的数目为止。 排序选择方法以及联赛选择方法以选择压力的均衡为出发点，以达到保持群 体的多样性，防止早熟的目的。然而只要适应度函数设计合理，选择赌轮法仍能 达到选择压力均衡而防止早熟的目的。文献 2 1 通过对这三种选择方法比较后， 认为赌轮法具有比其他两种方法更好的性能。 ( 2 ) 交叉。“ 交叉操作可分为两步进行，首先将复制产生的群体作为交配池( m u t i n g p 0 0 1 ) ，从中进行个体随机两两配对，并为每一对个体取一个 o ，l 】的随机数，当 ， p c ( 儿称为交叉概率) 时，该对个体参与交叉，否则保留原个体不交叉；第二 中山大学顾二学位论文 步进行交叉。一般情况下，编码方案决定交叉操作类型，凼此交义策略一般可分 为二进制的交叉策略和实数交叉策略。 1 、二进制交叉 一点交叉( o n e p o i n tc r o s s o v e r ) 最简单的交义操作就是单点交叉( 也称一点交叉) 。首先，对父代个体进行随 机配对；然后，配对个体随机设定交叉位置：最后，交换配对个体的部分信息。如 下圈所示，当染色体长度为f 时，有卜1 个交叉位置，单点交叉可实现卜1 种不 同的交叉结果。 ( 4 彳z 4 4 “4 ) j ( 4 彳2 4 眈“马)( 3 5 ) ( e 最眈色十1 一马)( 马岛眈4 + i 一4 ) 二点交叉( t w o p o i n tc r o s s o v e r ) 二点交叉与一点交叉类似，不同的是设置了二个交叉点，交叉点位置也是随 机设置的。对于二点交叉来说，若染色体长为f ，则可能有( 卜r 2 ) q 一3 ) 中交叉点 的位置。 多点交叉( m u l t i p o i n tc r o s s o v e r ) 多点交义是前述两种交叉的推广，有时也称为广义交叉( g e n e r a l i z e d c r o s s o v e r ) 。操作的方法是先随机产生多个交叉点，然后将两个个体不同的交叉 段互换。 一致交义( u n i f o r mc r o s s o v e r ) 一致交叉是指通过设定屏蔽字( m a s k ) 来决定新个体的基因继承两个父代个 体中哪个个体的对应基因的交叉方法，屏蔽字由随机产生的0 或1 字符串组成， 长度为，。 2 、实数交叉 由于点式交义是分量值的交换，而实数个体每位代表的空间大，表达的精细 度差，因此，实数采用点式交叉方法的搜索效率会降低，一般地，数值型交叉在 实数g a 中应用较多，目前已有多种实数交叉算子，有代表性的几类算子如下： 算术交叉( a r i t h m e t i cc r o s s o v e r ) 算术交叉算子是实数交叉方法的基本算子，是对父代个体的线性组合。存第 n 代，设随机选择参与交叉的两个父代个体为x ”t 和x ”z ，交叉产生的子代个体为 中山大学硕t 学位论文 x “和x “2 ，其线性组合表达式为“8 ： j x n + 1 1 2 7 。”i + ( i - r ) z “2 ( 3 - 6 l 3 - b 、) i x n + 1 2 = ( 1 一r ) x ”l + ，x “2 其中r 取 o ，1 之间的随机值，由上式可见，算子实现了父代参数范围内随机取 值的功能，有较强的开发能力。 启发式交叉( h e u r i s t i cc r o s s o v e r ) ” 启发式交叉算子的进化方向不是利用代间适应度的差异，而是利用代内不同 个体的适应度差异。参与交叉的两个父体之问的适应度一般是不相同的，两父体 的适应度不仅在复制过程中有贡献，它们之间的差异可能为生成更好质量的子代 指示潜在的搜索方向。因此，利用适应度差异生成子代的过程可以增加遗传信息 的利用。定义搜索方向d 为： d = ( 岛一，乙) 厶劝 ( 3 7 ) 其中赢和龙。分别是参与交叉的两父体中较高和较低的适应度。利用搜索方向d 提出启发式的交叉策略如下： n + l “即( x h a “”卅。( 3 - 8 ) 【x n + 1 2 = i n h + a 2 ( i n 恸一x ”l o w ) d 其中a 是【o ，1 】上均匀分布的随机数，d ：是【l ，2 】上均匀分布的随机数，这样x ”1 t 将 处于h ”m ，x “一恸】界内，而x n + i z 有可能处于界外，提高算子的探测能力。 需要指出的是上述启发式交叉算子产生的子代都有可能超出寻优参数定义 域的范围，因此，必须在交叉产生子代后，即对子代加以判断，对于超出定义域 的个体丢掉不用，并重新进行一次交叉。 近亲交叉回避 采用数值型交叉方法，当参与交叉的个体相同时，交叉操作将失效，不能产 生新的子代个体。针对这一现象，必须采用近亲交叉回避策略2 ”，该策略规定只 对那些适应度差异值或变量空间的距离大于给定值的配对个体才进行交叉，否则 重新配对。由于给定值是事先预定的，不随进化代数和本代平均距离的变化，上 述的近亲交叉回避策略不利于产生多样性的群体。 ( 3 ) 变异 中山大学硕 二学位论文 g a 的有效性主要来自选择复制和交叉操作，尤其是交叉在g a 中起着核心的 作用，尽管它们很重要，但不能保证小会遗漏一些重要的遗传信息。在g a 中， 变异主要用来防止这种不可弥补的遗漏，维护和挖掘群体中个体的多样性，克服 可能陷于局部最优解的弊病，使算法具有全局收敛性。变异是指个体的某位基因 从一个状态跳变到另一个状态，对于二进制编码的个体来说，是指个体的某位由 o 变为l 或l 变为0 。变异操作也分两步进行，第一步是确定个体是否参与变异， 先为群体中每个个体产生 0 ，l 】间的随机数r ，当r p 。时，那么该个体参与变异； 第二步是对于参与变异的每个个体产生 1 ，明问的随机数以确定变异的位置，实行 变异操作。一般情况下，编码方案也决定变异操作类型，因此变异操作策略一般 可分为二进制的变异策略和实数变异策略。 l 、二进制变异 二进制变异算子比较简单，主要有基本变异和逆转变异两种3 基本变异( b a s i cm u r a t i o n ) 基本变异算子是指对变异个体随机挑选一个或多个基因值做变动，称为一 点变异或多点变异。如随机挑选第二和第四个基因值做变动，则其操作如下所 刁x ： 变异 变异前1 0 1 i 0 1 l 1 l i 0 0 1 l 变异后 逆转变异( i n v e r s i o nm u t a t i o n ) 逆转变异是变异操作的一种特殊形式，它是在个体中随机挑选二个逆转点， 然后将两个逆转点间的基因值以逆转概率n 逆向排序。 2 、实数变异 与实数交叉相似，二进制的变异策略并不适合实数编码的变异，因此，人 们提出了许多适合于实数变异的策略，具代表性的主要有以下两种： 一致变异( u n i f o r mm u r a t i o n ) 一致变异被认为是实数编码的基本变异算子，首先在确定变异的个体中随 机选取一个参数作为变异对象，并在该参数定义域内选取一随机值作为变异值 代替原参数值。若选取的不是随机值而是该参数定义域的边界值。即最小值或 最大值，那么这种变异操作也称为边界变异。4 ( b o u n d a r ym u t a t i o n ) 。 中山人学硕l 学位论文 以上一致变异算子只选取个体中一个参数作为变异的对象，可称为一点一 致变异，为提高变异算子的随机搜索能力，可以同时采用一点、多点和全部一 致变异的方法1 2 6 1 ，参与变异的个体通过变异产生三个变异子代，有利于提高算 法的搜索能力，使算法大大减少陷入局部解的可能性。 非一致变异( n o n u n i f o r mm u t a t i o n ) 一致变异的变异值都是取定义域内的随机值，作为辅助算子，变异能使g a 超出局部搜索区域，增加群体的多样性，对g a 的全局搜索起一定作用，在g a 进化的初期阶段，这种变异对全局搜索起了积极的作用，但在g a 的进化的后期 阶段，g a 已经搜索到了最优区域，这是一致变异的随机取值却不利于局部搜索， 因此，人们提出了改进的变异算子，即变异取值随进化代数而改变的非一致变 异1 2 q 。 设x 。是变异个体x 要变异的参数，非一致变异公式为： a = 0 ( 3 9 ) a = l a ( n ，y ) = j ，( 1 一r ( i - n n ) b ) 其中u b 和l b 分别是该变异参数定义域的上界和下界，z 和为当前的进化代 数和最大代数，a 为随机值，决定变异的方向。a ( n ，y ) 取值范围为 o ，y 】，随着 进化代数的递增，其值逐渐趋于零，使非一致变异在进化的后期有较好的局部 搜索能力。r 取【0 , 1 】的随机数，b 为变异量与进化代数的调节参数，一般可取 b = 5 。 g a 依据每个个体的适应度并利用选择复制、交叉、变异操作对个体进行 更新换代，产生新一代群体。 五、g a 控制参数设定 g a 所使用的控制参数包括群体规模m 、交叉概率p 。、变异概率p 。、二进 制串长z 、总进化代数，这些对g a 的性能都有重要的影响，目前这些参数的 ) ) 以肋 一 一嘧 + 一 x r ，、l = x 中山大学硕学位论文 选取没有理论性的指导，经实际运算比较3 ，一般m 取2 0 1 5 0 ；n 取0 5 l ； p 。取0 0 0 1 o 0 5 ；l 由求解问题要求解的精度即公式( 31 ) 确定；而对于， 当群体规模m 较小时较大，否则选较小，可取为3 0 1 0 0 “。 3 3g a 的特点及主要缺点 3 3 1 标准g a 的特点 g a 利用了生物进化和遗传的思想，具有与传统优化算法不同的特点： 一、g a 不是直接作用在参变量集上，而是利用参变量集的某种编码g a 的 处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作，使g a 可直接对结构对象进行操作。这一特点，使得g a 具有广泛的应用领域。 二、g a 不是从单个点，而是从多个点的群体开始搜索，传统方法都是单点 搜索，从一点移到另一点。这种点对点的搜索常常会陷入局部最优解：而g a 采用 同时处理多个点的方法，对多个解进行评估，具有全局搜索性能，同时也易于并 行化。 三、g a 利用适应度信息，无需导数和其他辅助信息的g a 适应度函数不仅 不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是， 对于输入可计算出正的函数值。这使得该算法的应用范围大大扩展。 3 3 2 标准g a 的主要缺点 标准g a 算法作为优化搜索算法，在各种问题的求解和应用中表现了它的特 点和魅力，同时也暴露出了在理论和应用技术上的许多不足和缺陷。 一、g a 的收敛性问题 在优化理论中，一个算法是收敛的是指算法产生了一个解或函数值的数列， 而全局最佳是该数列的极限值。即收敛性问题是指算法能否找到全局最优解的问 中山大学硕上学位论文 题脚1 。文献 3 0 采用齐次有限马尔科夫链( m a r k o vc h a i n ) 证明了标准g a 不能 保证每次都收敛于全局最优解。 二、标准g a 的早期收敛与群体的多样性问题 早期收敛( p r e m a t u r ec o n v e r g e n c e ) 又称早熟，是指在搜索的初期阶段， 由于优良个体急剧增加，使群体失去多样性的想象。通俗一点说，在g a 未搜索 到全局最优点，而当前的父代通过遗传操作不能再产生比他们更优的子代时，这 时候算法就发生了早熟现象。应用g a 求大范围具有复杂地形问题的最优解时， 早熟现象很普遍而且很难克服。 三、g a 本质上还是一种随机搜索优化算法，当接近最优点时，标准g a 不 能自适应改变搜索的步长，还是大范围的搜索，浪费了大量的时间，影响了收敛， 尤其当问题规模较大时或者问题较复杂时( 即多参数寻优问题) ，往往造成搜索 空间非常的庞大从而导致g a 的收敛速度很慢，加之g a 本身存在着群体分散性和 收敛性之间的矛盾，这使得如何在搜索空间内较快的找到最优点成为g a 算法研 究的一个热点之一。 四、控制参数设定难于把握 为解决早熟及局部搜索能力差的问题，许多改进都集中于遗传算子的改进 上，但实际上这两种现象并不是仅仅由遗传算子产生的，控制参数选择不当同样 也会造成群体多样性下降而发生早熟现象。 关于g a 控制参数的选取问题，目前主要还是靠经验或试探，部分文献对g a 的参数进行定性的分析，但缺乏理论性的支持与指导和定量的分析。如何选择合 适的参数，寻找多样性和寻优速度、全局搜索能力和局部搜索能力的折衷方案， 找出潜在的平衡点，以最大限度地发挥算法的寻优性能，是有待进一步解决的问 题。 3 4 一种新的改进g a 算法 现有的g a 还具有值得改善的地方，尤其体现在搜索速度和局部搜索能力 的提升上，如何保持g a 本身具有的多样性同收敛速度、全局与局部搜索能力 的结合，成为本文设计新的g a 的宗旨。 中山人学硕l 学位论文 在g a 的进化过程中，容易发生早熟，其主要原因就是缺少多样性，个体丢 失，表现就在遗传算子( 选择复制、交叉和变异) 对个体的破坏作用k ，其中起 主要破坏作用的就是选择操作，选择压力容易使部分含有优良基因的个体来不 及进化就被淘汰，因此作为选择操作的唯一依据适应度函数的选择尤为重要。 如何选择合适的适应度函数的设计是新型改进g a 的重要一方面。 影响多样性的另一重要方面是交叉，交叉类似于生物繁殖过程中的基因交 换，是被认为是影响g a 全局搜索性能的重要因素。因此，为了改进g a 的全局 搜索能力，本文基于交叉策略改进的基础一k ，提出了一种新的交叉策略。 3 4 1 新型改进g a 的设计方案 根据标准g a 设计步骤，现提出改进g a 算法的设计方案。 一、采用实值编码方案。 实值编码方案由于省略了编码与解码的方案，所以运行时间比较短，收敛 速度比较快，符合设计的宗旨，因此新的算法采用实值编码方案。 二、产生初始群体 同样基于收敛速度的考虑，尽量减少设计参数降低设计的复杂度，拟采用 在寻优定义域内随机取值，另外，采用随机取值的方法产生的群体，个体的空 间分布是比较均匀的，不会产生群体集中在某一局部区域的现象，因而用r a n d 函数产生初始群体的方法是可行的。 三、适应度函数 合理的适应度函数选择，有利于保持群体的多样性，改善g a