（理论物理专业论文）混沌动力学在优化计算中的应用.pdf

c h a o t i c dy n a mi c s a n d i t s ap p l i c a t i o n s i n o p t i mi z a t i o n c o mp u t a t i o n ma j o r : t h e o r e t i c a l p h y s i c s a u t h o r : y a n g l ij i a n g ad v i s o r : c h e n ti a n l u n ab s t r a c t t h i s d i s s e r t a t i o n s t u d i e s t h e a p p l i c a t i o n s o f c h a o t i c d y n a m i c s i n o p t i mi z a t i o n p r o b l e m s . t h e m a j o r c o n t e n t s a r e r e l a t e d t o u s i n g c h a o s a s a k i n d o f h e u r i s t i c m e c h - a n i s m i n n e u r a l n e t w o r k s a n d g e n e t i c a l g o r i t h m s . a t fi r s t , w e b r i n g f o r w a r d a n e u r a l n e t w o r k mo d e l w i t h n o n l i n e a r s e l f - f e e d b a c k . i t s d y n a m i c a l b e h a v i o r s h o w s o b v i o u s c h a o t i c c h a r a c t e r i s t i c . t h e n w e r e a l i z e c h a o t i c a n n e a l i n g a l g o r i t h m b y i n t r o d u c i n g a k i n d o f p a r a m e t e r a n n e a l i n g m e t h o d i n t h e n e u r a l n e t w o r k m o d e l . t h e r e s u l t s o f t h i s a l g o r i t h m a p p l y i n g t o t s p p r o b l e m a r e b e t t e r t h a n o t h e r n e u r a l n e t w o r k a l g o- r i t h m s , w h i c h p r o v e t h a t t h e a l g o r i t h m i s e ff e c t i v e . i n a n o t h e r f a c e t , w e c o n s t r u c t a n e w t y p e o f c h a o t i c m u t a t i o n o p e r a t o r b a s e d o n s t u d y i n g o f c h a o t i c m a p p i n g . t h r o u g h a p p l y i n g t h e r e a l - c o d e d g e n e t i c a l g o r i t h m w i t h t h i s c h a o t i c m u t a t i o n t o s o m e c l a s s i c a l f u n c t i o n o p t i m i z a t i o n p r o b l e m a n d t s p , t h e g o o d h e u r is t i c a b i l i t y o f t h e c h a o t i c m u t a t i o n o p e r a t o r i s p r o v e d . f u r t h e r m o r e , w e a r e t h e fi r s t o n e s w h o p r e s e n t t h e i d e a o f a p p l y i n g o r b i t a l p o i n t s d i s t r i b u t io n t o c h a o t i c m u t a t i o n s c a p a - b i l i t y a n a s i l y s i s . b a s e d o n t h e a n a l y s i s o f d i ff e r e n t c h a o t i c m u t a t i o n s o r b i t a l p o i n t s d i s t r i b u t i o n , w e d e s i g n a c h a o t i c m u t a t i o n s s e l f - a d a p t i o n m e c h a n i s m w h i c h c a n i m - p r o v e t h e a lg o r i t h m s p e r f o r m a n c e v e r y n o t a b l y . k e y w o r d s : c h a o s , o p t i m i z a t i o n , c h a o t i c n e u r al g e n e t i c al g o r i t h m , c h a o t i c m u t a t i o n o p e r a t o r . c h a o t i c a n n e al i n g , 第一章绪论 早在公元前5 6 0 年左右， 中国古代思想家老子就有了关于“ 道可道非常道” 之说， 并初步提出了关于宇宙起源于混沌的哲学思想. 公元前4 5 0 年左右， 庄子 也曾说过 “ 南海之帝为倏. 北海之帝为忽.中央之帝为混沌” .庄子所说的倏、 忽， 就是迅速灵敏， 混沌有无知愚昧的意思， 分别代表三个皇帝. 而混沌竟在 中央. 应当说， 庄子说的是政治， 隐喻的是哲学. 但他的 “ 中央之帝为混沌” 的思 想是对人类行为的混沌性态的最早的哲学观点! 1 . 然而自 庄子之后数千 年， 混沌仍只是存在于人们脑中的一个哲学概念，人类对于混沌的理解并没有 实质的进步. 这种状况一直持续到上世纪初的1 9 0 3 年， 随着人类在科学技术领 域的不断发展与进步， 美国数学家j . h . p o i n c a r e 在 科学与方法一书中提出 了p o i n c a r e 猜想.他把动力学系统和拓扑学两大领域结合起来， 指出了混沌存 在的可能性， 从而成为世界上最先了 解存在混沌可能性的人.1 9 5 4 年， 前苏联 概率论大师a . n . k o l m o g o r o v 在探索概率起源过程中注意到了哈密顿函数中微 小变化时条件周期运动的保持. 该思想为如下结论莫定了基础， 即不仅耗散系 统有混沌，而且保守系统也有混沌. 接着1 9 6 3 年气象学家l o r e n t z 在数值实验 中发现，由确定性动力学方程描述的简化液体对流模型能呈现出非周期的、类 似随机的复杂行为一即混沌行为. 从此混沌动力学的研究深入到了自 然科学和 技术的各个领域， 甚至于社会科学的许多领域， 极大地改变和丰富了人们对自 然界及人类社会的认识.混沌动力学本身也已成为一个独立性很强的学科， 它 研究各个学科领域的具体间题的共同特征和规律， 发展了一整套关于系统的辨 识、 建模、动力学预测等等的理论和数值实验的方法.近年来， 人们开始关注 和探索普遍存在的混沌动力学的功能和应用. 探索混沌动力学在生物神经系统 的信息处理过程中的作用， 试图通过对生物神经系统及其模型的复杂动力学的 研究来揭示大脑的高级认知过程. 混沌动力学应用于复杂的优化间题也是混沌 应用的一个重要方向， 利用混沌的遍历性和确定性随机克服传统优化算法易陷 于局部最优的缺点，以提高算法的全局优化能力.这方面的研究方兴未艾，具 第一章 绪论 有非常重要的意义. 1 . l 混沌动力系统的一般理论和方法 动力系统是一个随时间发展演化的系统，一般地， 可以用动力学方程 、.声、于了 1191 : 11一.1 了胜、了、 =f ( x , t , c ) , x r 0 , c r 0 x ( t +1 ) =f ( x ( t ) , t , c ) 。 二 e r i , c e r 来描述系统的演化过程.其中 参数. 给定一个初始状态x ( 0 ) ， 足够长以后达到它演化的终态 x 是系统的状态矢量，。 是系统的一组 ( 可调) 系统状态的演化就由上述方程完全决定了， 时间 . 线性动力学系统的终态是简单的不动点( 平衡 态) 和周期解( 极限环) . 而非线 性系统则可能复杂得多， 会出现准周期或混沌 振荡. 至今也没有关于棍沌的确切的定义. 笼统地讲， 混沌是指在确定性动力学 系统中观察到的非周期的( 也不是由多个不可约周期登加而成的准周期) 、 类似 于噪声的复杂的动力学行为， 来源于系统内部的非线性相互作用.在观察到混 沌现象和提出混沌概念以前， 人们相信确定性动力学系统的行为是完全可以预 测的. 混沌的发展和提出， 根本地改变了这一可预测的信念， 开创了深入理解 自 然界复杂性和多样性的新时代. 对于混沌动力学， 一般有以下一些概念、 特征以及相应的对于这些特征的 量化刻划.下面我们就涉及到的作一些介绍. 号 1 . 1 . 1 吸引子， 奇怪吸引子 吸引子是系统的终态在相空间形成的一个确定的几何结构 !2 , 3 ， 它是一 个点或一些点的集合.系统从相空间一定的区域内的初始状态出发，最终都收 1 . 1混沌动力系统的一般理论和方法 敛到这一几何结构上， 这一区域称为吸引子的吸引域.吸引不动点、 极限环和 环面是分别具有为零维、 一维、和二维拓扑结构的 三种最常见的吸引子， 对它 们的辨别也相当直观. 而对于混沌系统来说， 其运动过程是非周期的演变，吸 引子的几何结构往往非常复杂， 是由无穷多的点构成的自 相似分形结构，称为 奇怪吸引子，也称混沌吸引子. 1 . 1 .2 毯定性， 对初值的敏感性， 长时间不可预测性 终态的稳定性是至关重要的， 因为只有稳定的终态才能在系统的数值模拟 或实验中观察到. 例如，当系统稳定到不动点态，若对它进行微小的扰动， 系 统将很快回到不动点态. 我们正是通过观察这种微小扰动的变化来研究终态的 稳定性的. 对于不动点的稳定性， 我们可以借助于l y a p u n o v 稳定性定理 冈: 设x 。 是系统1 = f ( x ) 的一个不动点( f ( x o ) = 0) ， 如果存在函数l ( x ) 满 足( i ) l ( x o ) 二 0 ， 但 在x 。 的 某一 邻 域 有l ( x ) 0 , ( i i ) 在 该 邻域内 有l o ， 那么x 。 是稳定不动点.拭劝称为l y a p u n o v 函数. 混沌系统对初始状态的改变是非常敏感的. 与不动点和周期解等稳定动力 学不同， 对混沌系统的初态的一个极微小的扰动将很快导致极为不同的动力学 轨迹. 为了 刻划微小扰动沿着轨迹的发展特征， 一般地， 我们可以定义l y a p u n o v 指数 1 , 2 “ 一 lime- 100 番 ln ll d f l (二 )u (x ) ( 1 .3 ) 其中d f ( x ) 是j a c o b i a n 矩阵，u - ( x ) 是f ( x ) 在二 处的 切空间的单位矢量. 可 见，。 维空间的l y a p u n o v 指数是由它的切空间各个方向上的平均发散或收敛 率来决定的. 两条初始有微小差别的轨迹将以 速度e a t 相互靠近( 人 0) . 如果a =0 ， 两条轨迹平均 地既不靠拢， 也不分离， 如准周期环 面上的轨迹; 或者以其它的， 如幕律的形式相互接近或分离. 在混沌动力学系统中， 吸引域内两个有微小差别的初始态虽然将导致极为 不同的运动轨迹， 但是， 这两条轨迹最终都落到相空间同一几何结构一混沌吸 第一章 绪论 引子上. 整体上看，混沌吸引子是稳定的，它的吸引域内的所有初态都要收敛 到混沌吸引子上. 因此， 混沌动力学系统至少有一个l y a p u n o v 指数大于零， 有 一个l y a p u n o v 指数小于零. 有多个l y a p u n o v 指数大于零的系统称为超混沌系 统. 从数学的意义上讲， 一个无限精确的初始条件将完全确定系统的一条演化 轨迹. 但是，由于系统对初始条件的变化是极为敏感的: 在实际的系统中， 任 何微小的扰动( 这是无法避免的) 将使系统很快偏离原先的轨道. 它的行为大 致可以预测的时间尺度为1 / h ， 其中h 是系统的k o l m o g o r o v - s i n a i ( k s ) 嫡， 它是 所有正的l y a p u n o v 指数之和， 长时间的行为将无法预测. 1 . 1 . 3 轨道的泊历性， 不毯定周期轨道 从吸引子上任一点出发的混沌轨道，只要时间足够长， 它能进入到吸引子 上任意其它一点的邻域. 因 此， 它在吸引子上是遍历的4 , 司. 对任一点尸， 轨道在一段时间以后会返回到它的邻域里来. 我们设想一个恰当的微小扰动能 使得轨道在 尸处闭合，形成一个周期解( 极限环) . 但由于系统是混沌的，这 种周期解是不稳定的. 又由于尸点并不是特殊之点， 因此， 不稳定周期轨道在 吸引子上是稠密的.同时， 从不同的角度观察，轨道的周期性是不变的.吸引 子上周期点邻域的结构和该邻域中 点的运动是由 周期点的切空间决定的6 . 从这个意义上讲，吸引子是所有不稳定周期轨道及其线性邻域的集合。周期解 及它的特征值是描述吸引子很 好的不变特征童7 . 而某些混沌吸引子可能具有 相同的一套周期解结构，因此， 反过来， 我们可以根据吸引子周期解的结构来 对 混沌动力 学系 统进行辨识、 分 类和 建 模. 混沌轨道具有通历性这一事实是发展各种混沌优化算法的基础. 混沌优化 的基本图象是基于混沌轨道的遍历性， 将优化间题的搜索空间映射到混沌系统 的分形空间，利用混沌动力学搜索间题的解. 互 1 . 2神经网 络 及其混 沌动 力学 研究 筒 介 1 . 1 .4 分岔. 通向混沌的路径 当参数c 发生变化时，系统的状态也随之发生变化.在某些参数区域，参 数的微小变化导致系统终态 ( 如不动点) 的位置和形状发生一些微小的变化. 而在某些地方，参数的微小变化则可能导致发生质变， 原先的终态失去稳定性 并产生新的终态. 这 种质变过程称为分岔 1 , 3 ， 它是由 系统的 结构不稳定性引 起的. 分岔包括多种形式， 如切分岔， 鞍点分岔， 叉式分岔，h o p f 分岔等. 人 们最熟悉的是倍周期分岔， 它是一个随着参数的变化周期不断加倍直到出现混 沌的分岔过程. 这种由周期加倍而导致混沌的方式称为通向混沌的倍周期路径. 其中 包含 一些普适的标度率$ , 9 . 还有其它一些通向混沌的路径， 如r u e l l e - t a n k e n s - n e w h a u s e s ( r t n ) 路径， 是指由 不动点叶极限环一二维环面一三维环面斗馄 沌的分岔过程 1 0 , 1 1 ; 或间 歇混沌路径 1 2 等. 通过计算一个系统随参数变化的分岔图， 结合其它的方法， 如建立相图， 计算 维数、l y a p u n o v 指 数 等特 征 量， 我们 可以了 解系 统在参 数空间的 动力学 结 构. 混沌动力学的研究很长一段时间致力于发展这些分析和数值实验的方法， 并把这些方法应用到各学科领域中具体系统的动力学结构的刻划上. 随着人们 对混沌动力学的理解越来越深入，人们已经在考虑和探索它的应用问题. 互 1 . 2 神经网络及其混沌动力学研究简介 随着混沌动力学的研究日 益深入， 它在各个具体的学科领域得到了广泛应 用， 其中人们对将混沌应用于智能信息处理的研究尤为关注. 脑神经系统是由 非线性神经元组成的复杂巨系统，它的非线性特性与混沌系统十分相似，因此 混沌动力学理论提出以后， 人们意识到研究神经系统的复杂动力学行为可能是 理解大脑的行为和功能的新途径. 第一章 绪论 盯. 2 . 1 生物神经系统 神经元即神经细胞构成了 遍布生物体全身的神经系统的些 本单元【 1 3 , 1 4 . 如图1 . 1 所示， 神经元由细胞体， 轴突， 树突组成. 细胞体是神经元的核心部分. 轴突能延伸很远，其上伸出的树枝状树突与其它细胞的树突或轴突相连结， 连 结处称为突触.神经元通过突触连结组成一个网络，称为神经网络. 神经元之 间的相互作用一般是通过电 脉冲的 形式来传播【 1 3 . 神经元有兴奋和静息两个 基本状态， 一个神经元处于兴奋状态时， 它就发放电脉冲， 脉冲发放的频率与 神经元所受的刺激的强弱有关， 刺激越强， 频率越高; 如果刺激较弱， 还没有达 到一个兴奋的阅值， 神经元将保持静息， 不发放脉冲.虽然神经元的基本状态 是相当简单的， 但是， 它对外界刺激的应激过程是一个非常复杂的动态过程， 较早提出的描述这种变化过程的h h ( h o d g k i n - h u x 1 1 e y ) 方程 1 5 就很复杂. 困1 .1 : 神经元的结构1细胞体 2 . 轴突3 . 树突 一个神经元的行为就已 经相当复杂， 那么由大量神经元构成的神经系统的 复杂度就更高了. 如人的大脑皮层约由1 0 1 1 _ 1 0 2 个神经元构成， 每个神经元 又与约1 乎、1 0 ” 个其它神经元通过突触相联系. 整个神经系统， 从分子到神 经元到网络， 各个层次都存在复杂的非线性相互作用. 大脑的所有智能活动， 如感知、 记忆、 推理等， 都是由神经元通过复杂的相互作用形成的网络来完成 互 1 . 2神经网络及共混沌动力学研究简介 的.可以设想， 复杂的动力学可能在大脑完成这些信息处理过程中起着至关重 要的作用. 用非线性动力学分析的方法， 在网络这样的层次来研究神经系统的 行为，可能是理解它的功能作用的有效途径. 1 . 2 . 2 人工神经网络棋型 模型化研究是探索研究对象的实质和规律的一种有效方法. 将神经网络模 型化首先必须建立合适的神经元数学模型.为建立神经元模型，必须先确定某 个性质作为神经元的基本状态变量. 一个自然的方案是将生物神经元电活动的 激活和静息当作模型神经元的基本状态【 1 6 . 也有人认为以神经元在单位时间 内 的 脉冲发放速率作为基本状态变量更符合生物系 统的 信息处理过程1 刀. 不 论是以脉冲发放与否还是以脉冲发放率作为状态变量， 神经元的状态都有如下 方程: s ( t ) = f ( v ( t ) 一夕 ( t ) )( 1 .4 )o w) 其中的s ( t ) 表示神经元在t 时刻的状态，b ( t ) 表示闽 值，v ( t ) 表示神经元的 内 部状态( 内 局 域场) . 内 部状态是一个很模糊的概 念， 它粗略表示神经元的 膜电位或电流， 包括从突触收集到的其它神经元的输人和外界环境的刺激.函 数f ( x ) 称为 激活函 数， 一般说来它是非线性的. 这种非线性是导致神经网 络有 非常复杂的动力学行为的重要来源之一 如果以 激活和发放作为状态，s 可以取为 二值变量( 取值f 1 或1 , 0) . 方 程1 .4 表 示当内电位超过阅值时， 神经元被激活， 发放一脉冲; 否则处于静息状 态. 这时激活函数常取符号函数f ( x ) = s i g n ( x ) . 如果以脉冲 发放率作为状态，s是有界的连续变量， 通常取自 区间- 1 , 1 或0 , 1 . 方程 1 . 4 意味着内电位越高神经元发放得越频繁. 这时激活函数是 s i g t n o i d 型上下有界连续单增的非线性函数， 如图1 .2 所示. 神经网络( 模型) 是由 多个神经元又 ( i =1 , 2 , . . . , n ) 通过相互作用联结而 成的网络系统. 相互作用的强弱用权重w; ( t ) ( 称w为互联矩阵) 来表示. 一 第一章 绪论 图1 . 2 : s i g m o id 型函数 个神经网络的动力学演化过程一般可以表示为: n h . ( t ) = 艺w ij s ; ( t ) + l i ( t ) , j 民 ( t )= f ( h i ( t ) 一 o i ( t ) ) - ( 1 .5 ) ( 1 .6 ) 网 络的演化可以采用并行或串 行的方式. 神经网 络 模型的 一个主要特征就是信息的 分布 式存 储【1 8 ， 它 是指 在神经 网络系统中， 信息是存储于神经元的相互作用矩阵w 中， 信息的处理过程是一 个并行处理的过程. 神经网络模型主 要是通过学习来改变相互作用权重 w ， 并同时将信息分布地存储到 w 中. 正是信息的分布存储和并行处理能力使得 神经网络模型在联想记忆、 棋式识别以及优化计算等领域中 得到了广泛的应用 1 s , 2 0 . 1 . 2 .s 混沌在神经网络中的应用 将混沌应用于神经网络的思想， 最初起源于生物学实验中观察到的单个神 经元呈现出的混沌行为2 1 , 2 2 , 2 3 . 在合理的生物学参数下，随着外输入的变 1 . 3演化计算及其应用简介 化，h h神经元模型会出 现从不动点到极限环到混沌的分岔过程 2 4 ， 这说 明混沌可能是神经元的内秉特征. 于是人们试图通过生物神经系统的实验研究 来揭示混沌动力学及其他复杂动力学的生物学含义. f r e e m a n与他的同事通 过对兔子的嗅觉系统的研究发现， 当兔子在学习新气味时， 嗅觉系统的电活动 是一个低维的混沌吸引子， 据此他们提出混沌动力学可能对兔子学习新的气味 是必要的!2 5 , 2 6 . b a b l o y a n t z 等对人在不同的精神状态下记录到的脑电波进 行分析， 表明在睡眠的 第二和第四阶段脑电 是低维的混沌吸引子2 刘， 癫痈病 人的脑电 也是低维的混沌吸引 子 2 8 . 他们指出， 混沌动力学可以 提高大脑的 共振能力， 大大地丰富了大脑对外刺激的应激性， 而简单的周期振荡则不可能 完成复杂的信息处理过程. 另一方面， 在神 经网络模型的研究中， 为服务于联 想记忆、 模式识别和优化处理等应用的目的而建立了具有不动点吸引子的神经 网络模型， 如全互联对称的 单层反馈 h o p fi e l d网络模型和多层前馈 b p ( b a c k p r o p a g a t i o n ) 网络模型. 当在模型中引入更加复杂的神经元模型或相互作用方 式，网络可能呈现混沌等复杂的动力学行为. 进而人们开始探索混沌等复杂动 力学在神经计算中的可能应用.i n o u e 等提出一个混沌计算机模型，用韧合的 混沌振子来构成神经元并连结成混沌神经网络， 来实现联想记忆搜索和优化处 理等2 9 , 3 0 , 3 1 .n a r a 等利用非对称反馈网络的复杂动力学来实现对具有某 种特征的 模式的搜索3 2 .h a y a k a w 等把混沌信号输人到h o p fi e l d 网 络中 来实 现优化处理 3 3 . 复杂的混沌动力学可望有利于解决简单动力学系统如不动点 网络和周期解网络无法解决的复杂的信息处理过程， 在人工智能以及其它的技 术领域具有巨 大的应用前景. 我们准备在第二章中更系统地介绍混沌神经网络 模型及其在优化问题中的应用. 1 . 3 演化计算及其应用简介 近代科学技术发展的显著特点之一是多学科的相互交叉、 相互渗透和相互 促进.比 如对于计算机科学与生命科学， 一方面由于计算机的发明， 大大推动 第一章绪论 了包括生命科学在内的诸多学科的发展以及人类生活、思维方式的改变;另一 方面， 计算机科学的进步，尤其是人工智能理论的发展， 又曾从生命科学中汲 取了养分.当人工智能的研究中，基于符号处理机制的传统方法在知识表示、 处理模式信息及解决组合爆炸等方面遇到了无法逾越的障碍时， 正是生物界的 进化现象又提供了我们解决问题的灵感， 从而发展出了演化计算这一崭新的方 法. 扒. 3 . 1 演化计算及其分支 演化计算是基于自 然界优胜劣汰的进化思想而建立起来的一种通用的问题 求解方法. 它采用简单的编码技术来表示各种复杂的结构， 并通过对一组编码 表示进行简单的遗传操作和优胜劣汰的自 然选择来指导学习和确定搜索的方向 3 4 . 由 于演化计算简单的 操作和较高的 效率， 使它引 起了 数学、 物理、 生 物、 化 学、 工程、 计算机科学甚至经济学等各个领域的学者的关注. 据德国d o r t m u n d 大学1 9 9 3 年末的一份报告报道， 根据不完全统计演化计算已 在1 6 个大领域2 5 0 多 个小领域中 获得了 应用3 司. 随着演化计算研究的进展， 其中逐渐派生出了四个不同的分支:遗传算法 ( g e n e t i c a l g o r i t h m， 简称g a) ， 演化规划( e v o l u t i o n a r y p r o g r a m m i n g ， 简称 e p) ， 演化策略( e v o l u t i o n s t r a t e g y ， 简称e s) 以 及2 0 世纪9 0 年代初发展起 来的遗传程序设计( g e n e t i c p r o g r a m m i n g ， 简称g p). 1 . 遗传算法: 遗传算法由美国m i c h i g a n 大学的j o h n h o l l a n d 教授在其1 9 7 5 年的开创 性著作 a d a p t a t io n in n a t u r a l a n d a r t i fi c i a l s y s t e m中 首先提出3 6 ， 并 将该算法加以推广并应用到优化及机器学习等问题之中.h o l l a n d 的遗传算 法常被称为简单遗传算法( s i m p l e g e n e t i c a l g o r i t h m ， 简称s g a) ，s g a的 操作对象是一群二进制串( 称为染色体) ， 即种群( p o p u l a t i o n) . 这里每个 染色体都对应于间题的一个解. 从初始群体出 发， 采用基于适应值比 例的选 互 1 .3演化计算及其应用简介 择策略在当前种群中选择个 体， 使用交叉 c r o s s o v e r ) 和变异( m u t a t i o n) 来产生下一代种群. 如此一代代演化下去， 直到满足期望的中止条件. 本文 第三章主要就是围绕遗传算法来讨论混沌在演化计算中的应用. 演化策略: 演化策略是由 德国柏林工业大学的1 . r e c h e n b e r g 和h . p . s c h w e f e 等最 早提出的3 刀. 早期的演化策略主要是利用生物变异的思想来进行搜索， 因而它只使用变异操作， 并且种群只包含一个个体， 即( 1 十 1 ) 策略. 但这 种形式的演化策略搜索效率低， 解的质量也不好. 于是又发展出了改进的 伽+ 1 ) 演化策略和扭+习演化策略.扣十1 ) 策略即在含有m 个个体的 种 群中， 随机地选取一个个体进行变异， 然后取代最差的个体.( # 十习中 则 引进了类似遗传算法中的交叉算子的重组操作， 演化是在a 个个体的种群 中通过变异及重组操作生成 入 个个体. 与遗传算法将原间题的解映射到位 申空间不同的是演化策略直接在解空间上进行操作， 它强调演化过程中从 父体到后代行为的自适应性和多样性. 从搜索空间角度来说，就是强调演 化过程中搜索方向和步长的自 适应调节. 演化规划: 演化规划最初由l . j . f o g e l 等提出!3 8 . 他们在人工智能的研究中 发 现， 智能行为即是要具有能预测其所处环境的状态， 并按照给定的目标作 出适当响应的能力.在研究中， 他们将模拟环境描述成由有限字符集中的 符号组成的序列.于是间题便转化为:怎样根据当前观察到的符号序列作 出响应以获得最大的收益， 这里收益的计算是按照环境中将要出现的下一 个符号及预先定义好的效益目 标来确定的. 遗传程序设计 遗传程序设计即是通过遗传算法的思想来实现自 动程序设计， 这一思 想 最 早由s t a n f o r d 大学的j . r . k o z a 提出3 9 , 4 0 . 它 采用分层结构来表示 解空间， 这些分层结构的叶节点是间题的原始变量，中间节点则是组合这 苏一章 绪论 些原始变量的函数. 这样的每一个分层结构对应问题的一个解， 也可以理 解为求解该问题的一个计算机程序. 遗传程序设计即是使用一些遗传操作 动态地改变这些结构以获得解决问题的可行的计算机程序. 虽然演化计算的这些不同分支在算法实现方面具有一些细微的差别， 但它 们具有一个共同的特点， 即都是借助生物演化的思想和原理来解决实际问题. 因此可以用一个通用结构来表示演化计算， 如图1 . 3 p r o ced u r e e v o l u t i o n a r y c o m p u t a t i o n b 叼 n 亡夺 ，a in i t i a l i z e p ( t ) e v a lu a t e p ( t ) w h i le ( n o t t e r m i n a t i o n - c o n d i t i o n ) d o b e g i n 云 +- 公 +l s e le c t p ( t ) fr o m p ( t - 1 ) a l t e r p ( t ) e v a l u a t e p ( t ) e n d 困1 .3 : 演化计葬的一般结构 任 1 . 3 . 2 演化计算的主要特点 演化计算与传统的算法具有很多不同之处， 但其最出要的特点体现在下述 两个方面: 1 . 智能性 演化计算的智能性包括自 组织、自 适应和自 学习性等. 应用演化计算求解 问题时， 在确定了编码方案、 适应值函数及遗传算子以后， 算法将利用演化过 程中 获取的信息自 行组织搜索.由于基于自 然的选择策略为: 适者生存、 不适 应者淘汰， 故而适应值大的个体具有较高生存概率. 通常适应值大的个体具有 互 1 . 3演化计算及其tk用简介 与环境更适应的基因结构， 再通过杂交和基因突变等遗传操作就可能产生与环 境更适应的后代.演化计算的这种自组织、自 适应特征同时也赋予了它具有能 根据环境的变化自动发现环境的特性和规律的能力. 自 然选择消除了算法设计过程中的一个最大障碍:即需要事先描述问题的 全部特点，并说明针对间题的不同特点算法应采取的措施.于是， 利用演化计 算的方法我们可以解决那些结构尚无人能理解的复杂间题. 2 . 本质并行性 演化计算的本质并行性表现在两个方面: 一是演化计算是内 在并行的( i n - h e r e n t p a r a l l e li s m ) ， 即 演化 算法 本身非常 适合大规模并行. 最简单的 并行方式 是让几百甚至数千台计算机各自 进行独立种群的演化计算， 运行过程中甚至不 进行任何通信( 独立的种群之间若有少量通信一般会带来更好的结果) ， 等到运 算结束时才通信比 较， 选取最佳个体， 这种并行处理方式对并行系统结构也没 什么限制和要求. 可以说， 演化计算适合在目 前所有的并行机或分布式系统上 进行并行处理，而且对其并行效率没有太大的影响.二是演化计算的内含并行 性( i m p l i c i t p a r a l l e l i s m ) ， 由 于 演化计算采用种群的方式组织搜索， 从而它可以 同 时 搜索解空间内的 多 个区 域， 并相互 交流信息， 这种搜索方式使得它虽 然每 次只 执行与种群规模n 成比 例的 计算， 而实质上已 进行了 大约o ( n 3 ) 次有效搜 索4 1 . 这使得演化计算能以较少的计算获得较大的收益. 写 1 . 3 . 3 混沌在演化计算中的应用 通常认为演化计算与混沌动力学是从不同领域中 发展起来的理论， 它们之 间 并没有什么直接的 联系. 但一些学者在研究了演化计算的自 现行为( e m e r g e n t b e h a v i o r ) 后声称， 演化计算与混沌理论和分形几何一道将成为人们 研究非线性 现象的复杂系统的新的三大方法4 2 , 4 3 . 这无疑就使演化计算与混沌理论走 到了同一领域内. 但是对这两种理论进一步联系的研究却一直没有多大进展. 直到 1 9 9 7 年 第一章 绪论 吴新余等构造了一种应用混沌的遗传算法， 他们认为演化计算中的演化操作并 不应随机确定，而应是内秉的.因而他们提出用一些典型的混沌系统代替遗传 算法中 用以确定交叉、 变异概率的随机机制!4 4 . 最近骆展钟等在文献4 5 中 则是另一种思路，他们直接改变变异算子，以用混沌构造变异算子的方法来将 混沌和演化计算结合起来. 本文将在第三部分和第四部分主要以构造混沌变异 算子的方法来讨论混沌在演化计算中的应用. 互 1 . 4 本论文内容安排 前面我们简要介绍了混沌动力学、 神经网络、 演化计算的发展和基本理论， 并讨论了混沌在神经网络以及演化计算中的功能应用的探索. 后面的章节将论 述我们在这些方面所作的一些工作. 第二章中， 我们先对目 前混沌神经网络模型及混沌动力学在神经计算中的 应用作了简单的分类介绍. 然后我们提出了一种非线性延迟反馈的混沌神经网 络模型， 着重研究了反馈项变化对网络的混沌动力学行为的影响. 我们进而分 析了网络的暂态动力学过程，提出了混沌退火的方法并应用于优化间题. 第三章和第四章研究混沌在遗传算法中的应用. 先比较系统的介绍了在遗 传算法的原理和遗传算法设计中的几个需认真处理的技术要素， 并着力分析了 简 单 遗传算法( s g a ) 中的 二进制编码困 难. 然后我们引 人了实数编码的遗传算 法， 并 构造了一类混沌变异算子. 在对混沌变异遗传算法的研究中， 我们主要 是通过讨论不同反馈项引入的混沌在算法中的功能， 来试图确定一种适合于构 造混沌变异算子的混沌系统. 我们将该算法应用于经典的函数优化间题和旅行 推销 员问 题( t s p ) ， 并分析了计算结果. 最后我们 进一步引 入了混沌映射轨道 点密度分布来分析混沌变异算子的性能， 并 设计了一种变异算子自 适应选择机 制， 从而大大提高了算法的性能. 第五章是对我们所做研究工作的总结以及对今后工作的展望. 第二章混沌神经网络及其在优化问题中的应用 如第一章所述，神经网络模型自提出以来，受到了广泛的重视，并且已应 用到了很多不同的实际领域.神经网络应用于优化计算就是神经网络的众多应 用中开始比较早， 也比较重要的一个方面. 八十年代初， 正是由于j . j . h o p fi e l d 等提出了一种全互联对称h o p fi e l d网络 1 9 ， 并将其应用到了经典的组合优化 问 题一旅行推销员向 题( tra v e l l i n g s a l e s m a n p r o b l e m ) 中， 才使当时正陷人困 境的神经网络研究重现生机.j . j . h o p fi e l d 等的工作当时引起了很大轰动， 因 为他首次提出利用神经网络的不动点动力学行为和网络大规模的并行运算能力 来进行优化问题的求解， 为我们提供了一个瑞新的解决优化间题的思路. 然而， 神经网络是一个非常复杂的非线性巨系统， 其中存在各种复杂的动 力学行为，而不仅仅是简单的不动点动力学行为.并且在作为神经网络模型原 型的生物神经系统中， 人们已观察到各种混沌行为 的高级功能与其复杂的动力学之间是有一定关联的 究神经网络中的复杂动力学，特别是混沌动力学， 2 5 , 2 6 , 2 7 1 ， 生 物神 经系 统 .因此这就激发了人们去研 揭示它在神经系统行为功能 中的作用，开发它在神经计算中的应用. 本章我们将就混沌神经网络在优化计 算中的应用作详细地介绍. 经 2 . 1 组合优化问题 写 2 . 1 . 1 .优化问.的定义 最优化问 题一般指在某种状况下作出 最好的 决策， 或者是从几个候选者中 选出最好的.由于它的应用能解决大量重要的工程实际问题以及产生巨大的经 济利益， 所以倍受重视， 例如，8 0 年代美国著名数学家p . l a x 教授在向美国政 府上书呼吁科学计算对美国国民经济的重要性时列举了三个重要的计算问题. 其中 之一就是在全美电力线路设计中成功应用了非线性优化的逐步二次规划方 法， 得到了最优方案， 取得了很好的效果 !5 2 . 最优化问题现在在工程设计、 第二幸 混沌神经网络及其在优化问翅中的应用 交通运输、 城市规划、自 动控制、 经济市场、 生命科学等方面都有着广泛的应 用， 是运筹学、 计算数学、 应用数学、力学以及众多其它应用领域的交叉. 2 . 1 . 2 组合优化问肠和旅行推梢员问肠 一般， 优化问题可以自然地分为两类:一类是连续变量的间题;另一类是 离散变量的问题，称其为组合优化间题. 旅行推销员问题( t r a v e l l i n g s a l e s m a n p r o b l e m， 简称t s p ) 就是一个典型的 组合优化间题. 它可以描述为: 有n个城市， 它们之间的距离已知， 有一货郎 要从某一城市出发走遍所有的城市， 且每一个城市只能经过一次， 最后回到原 处.问如何选择路线可使他所走过的路程最短. 用数学语言可将旅行推销员同 题描述为: 设有有限个城市集合c = c 1 , c 2 ， 二 ， ， 汤 ， 其每两个城市之间的距离为 d ( c , c ; ) z + ， 其 中c , c j e c ( 1 0 . 5 ( 2 . 1 5 ) 工 0 . 5 弓火八u 了，1.j、esset 一一 、.声 劣 产.、 ，. 此神经元模型的响应定性地复制了乌贼巨轴突实验中观察到的交错的周期一 混 沌响应序列. 第二章 混沌神经网络及其在优化问超中的应用