（应用数学专业论文）近代算法在工程领域中的应用研究.pdf

摘要 摘要 本文作者利用现代优化算法和超限插值方法分别对于化学工程、生物物理、 艺术曲面造型等领域的问题进行了深入研究。分别回顾了遗传算法、人- r o o 经网 络、b 样条曲线插值拟合及超限插值的发展历史及其各自特点。 以贵金属为催化剂的一氧化碳催化速率是化学工程催化研究中一个重要研 究方向。考虑用b 样条曲线拟合一氧化碳催化速率数据使得最小二乘拟合误差 最小。一般有两种考虑，一种是保持b 样条基函数的节点不变，选择参数使得 拟合较优。参数的选择方法包括均匀取值、累加弦长法、c e n t r i p e t a lm o d e l 、 g a u s s - n e w t o n 迭代法等。另一种则是先确定好参数值( 一般用累加弦长法) ，然 后再用某一算法计算出节点，使得拟合较优。文中同时把两者统一考虑，用遗传 算法同时求出参数、节点使得拟合在最小二乘误差意义下最优。与g a u s s n e w t o n 迭代法、p i e g l 算法相比本方法具有较好的鲁棒性( 拟合曲线与初始值无关) 、较 高的精度及控制顶点少等优点。实验结果说明采用遗传算法应用b 样条曲线拟 合一氧化碳催化速率，得到的曲线逼近效果更好，一氧化碳催化速率过程的描述 更为准确。 为提高提纯塔二氧化碳出口纯度，需要建立其与进料纯度、进塔温度、 塔顶压力、塔顶温度、加热温度、塔釜压力、塔釜温度七个因素之间的模型。 根据实际生产数据运用人工神经网络方法建立了二氧化碳出口纯度与这七个 因素之间的非线性模型。用该方法建立的非线性模型能有效地描述二氧化碳纯 度与各因素之间的关系，同时通过训练好的网络能找到生产二氧化碳具有较高 纯度的最佳控制点，得到了令人满意的效果。与用传统方法的线性回归模型、 对数回归模型建立起来的模型相比，用人工神经网络方法建立的模型具有处理 非线性模型能力强，鲁棒性好，拟合精度高，计算速度快，预测、控制能力强 等优点。 荧光寿命法成像技术( f l i m ) 是一种非常有效、功能强大且能用来分析 复杂生物组织和细胞分子的成像技术。传统的荧光寿命成像的数据分析是采取 按某些具有不同寿命、离散的单参量指数模型来描述荧光衰减过程。在像生物 组织这样既复杂又不均匀的样品中，虽然多参量指数模型能提供比单参量指数 浙江大学博士学位论文 模型对实验数据更好的拟合效果，但是多参量的假定往往是随意。在本文中， 第一次提出了拟w e i b u l l 分布密度函数、人工神经网络可能是生物荧光分子团 衰减动力过程的真实再现，并且通过计算证明，这种新颖的荧光衰减模型函数 对于某些生化感兴趣的荧光分子团的多槽基面效价测定样品的数据，相对于单 参量指数与多参量指数衰减函数有更好的一致性。同时在文中讨论了将该荧光 衰减模型应用于荧光寿命成像的前景。 艺术曲面造型是计算机辅助几何设计和计算机图形学的一项重要内容。基于 偏微分方程( p d e ) 的曲面造型方法产生的曲面的形状完全由边界条件确定，需 要花大量的时间进行数值计算。而超限插值根据边界曲线、边界导矢的几何意义， 只需对几个参数进行调整就可以达到同样的目的，简单、易操作，计算时间大大 减少。本文集中讨论了超限插值及其特殊情况，特别，对于插值交叉线、插值边 界曲线及其导矢的情形给出了大量艺术曲面造型。在计算效率上远远高于基于偏 微分方程( p d e ) 的曲面造型方法。因此用超限插值方法构造艺术曲面造型不失 为一种高效的方法。 关键词：一氧化碳，催化，贵金属，遗传算法，最小二乘拟合，b 样条曲线，b 6 z i e r 曲线，二氧化碳，提纯，人工神经网络，拟合，生物医学光学，拟w e i b u l l 分布密度函数，荧光寿命法成像技术( f l i m ) ，荧光衰减过程，超限插 值，艺术曲面造型，h e r m i t e 插值 a b s t r a c t a b s t r a c t t h i sp a p e rs u m m a r i z e do u rr e s e a r c h e so np r o b l e m so fc h e m i c a le n g i n e e r i n g ， b i o p h y s i c sa n da e s t h e t i cs u r f a c e sm o d e l l i n gb yu s i n gg e n e t i ca l g o r i t h m s ，n u e r a l n e t w o r ka n dt r a n s f i n i t ei n t e r p o l a t i o n t h eh i s t o r ya n dr e s p e c t i v ec h a r a c t e r so fg e n e t i c a l g o r i t h m s ，n e u r a ln e t w o r k ，f i t t i n ga n di n t e r p o l a t i o no fb s p l i n ec u r v ea n dt r a n s f i n i t e i n t e r p o l a t i o nw e r eb r i e f l yr e v i e w e d t h es t u d i e so ft h ec a t a l y s i sr a t eo fc oo x i d a t i o nu s i n gs u p p o r t e dn o b l em e t a l c a t a l y s t sa r ev e r yi m p o r t a n ti nc h e m i c a le n g i n e e r i n g t oo b t a i nag o o da p p r o x i m a t i o n f o rl e a s ts q u a r ef i t t i n go fb - s p l i n ec u r v et ot h er a t ed a t ao fc o o x i d a t i o n ，p a r a m e t e r s a n dk n o t sh a v et ob ed e a l tw i t ha sv a r i a b l e sf r e q u e n t l y t h e r ea r et w ok i n d so f c o n s i d e r a t i o n s t h ef i r s ti st oc h o o s ep a r a m e t e r sw i t hw i t c ht h ef i t t i n ga r eb e t t e rw h i l e t h ek n o t so ft h eb s p l i n eb a s e sa r ei naf i x t h ec h o i c e so fp a r a m e t e r si n c l u d eu n i f o r m p a r a m e t e r i z a t i o n ，c u m u l a t i v e c h o r d l e n g t hp a r a m e t e r i z a t i o n ，c e n t r i p e t a l m o d e l p a r a m e t e r i z a t i o na n dg a u s s - n e w t o na p p r o a c h t h eo t h e ri st od e t e r m i n ep a r a m e t e r s i na d v a n c e ( g e n e r a l l yc u m u l a t i v ec h o r dl e n g t hp a r a m e t e r i z a t i o n ) a n dt h e nt oc o m p u t e t h ek n o t so fb - s p l i n eb a s e sb ys o m ea l g o r i t h m ss u c ht h a tt h ef i t t i n gb e c o m em o r e p r e c i s e i nt h i sp a p e rb o t ht h ep a r a m e t e r sa n dt h ek n o t so ft h eb - s p l i n eb a s e sa r e c o n s i d e r e ds i m u l t a n e o u s l yb yu s i n gg e n e t i ca l g o r i t h m ss u c ht h a tt h ef i t t i n gb s p l i n e c u r v et od a t aa t t a i n si t so p t i m u mi nt h et o t a l l e a s ts q u a r e ss e n s e w i t ht h i s ，t h e p a r a m e t e r sa n dt h ek n o t sc a nb ea p p r o p r i a t e l yd e t e r m i n e ds i m u l t a n e o u s l y t h e m e t h o dg i v e ni n t h i sp a p e rh a v ea d v a n t a g e so fr o b u s t n e s s ( t h er e s u l t i n gc u r v ei s i n i t i a l - v a l u e f r e e ) ，b e t t e rp r e c i s i o na n df e w e rv e r t e x e sc o m p a r e d 谢t 1 1g a u s s - n e w t o n a p p r o a c ha n dp i e g l sa l g o r i t h m t h ee x p e r i m e n t ss h o wt h a tg e n e t i ca l g o r i t h m s - b a s e d l e a s ts q u a r ef i t t i n go fb s p l i n et ot h er a t ed a t ao fc oo x i d a t i o na r eb e t t e ri n a p p r o x i m a t i o n t h ec a t a l y s i sp r o c e s sc a n b ed e s c r i b e dp r e c i s e l y t oi m p r o v et h ep u r i t yo ft h ec a r b o nd i o x i d ef r o mt h ep u r i f y i n gc o l u m n ，i ti s n e c e s s a r yt ob u i l dam o d e lo f t h ep u r i t yo fc a r b o nd i o x i d ew i t hs e v e nf a c t o r so ff e e d p u r i t y , f e e dt e m p e r a t u r e ，c o l u m nt o pp r e s s u r e ，c o l u m nt o pt e m p e r a t u r e ，c o l u m n r e a c t o rh e a t i n gt e m p e r a t u r e ，c o l u m nr e a c t o rp r e s s u r ea n dc o l u m nr e a c t o rt e m p e r a t u r e 浙江大学博士学位论文 t h en o n l i n e a rm o d e lb e t w e e nt h ep u r i t yo ft h ec a r b o nd i o x i d ea n dt h es e v e nf a c t o r s w a se s t a b l i s h e de f f e c t i v e l y , b u i l to nt h ea c t u a ld a t ai np r o d u c t i o nb yu s i n ga r t i f i c i a l n e u r a ln e t w o r k t h em o d e lc o u l dd e s c r i b ee f f e c t i v e l yt h er e l a t i o n s h i pb e t w e e nt h e p u r i t yo fc a r b o nd i o x i d ea n do t h e rf a c t o r sa n da tt h es a m et i m et h eb e s tc o n t r o lp o i n t f o r t h ep r o d u c t i o no fc a r b o nd i o x i d ec o u l db ef o u n db ym e a n so f ，t h et r a i n e dn e t w o r k a n dt h er e s u l tw a ss a t i s f a c t o r y t h em o d e lm a d eb yt h ea r t i f i c i a ln e u r a ln e t w o r kh a s a d v a n t a g e so fr o b u s t n e s s ( t h ef i t t i n g i si n i t i a l - v a l u e - f r e e ) ，b e t t e rf i t t i n gp r e c i s i o n ， s t r o n ga b i l i t yt ot r e a tn o n l i n e a rm o d e l ，f a s tc o m p u t i n g ，p o w e r f u lp r e d i c t i o na n ds t r o n g a b i l i t yt oc o n t r o lc o m p a r e dw i t hc o n v e n t i o n a ll i n e a rr e g r e s s i o nm o d e la n dl o g a r i t h m i c r e g r e s s i o nm o d e l f l u o r e s c e n c el i f e t i m ei m a g i n gi sar a t h e re f f e c t i v ea n dp o w e r f u lm e t h o dt h a tc a n b eu s e dt oa n a l y z ec o m p l e xb i o l o g i c a lt i s s u e sa n dm o l e c u l e s c o n v e n t i o n a la n a l y s e s o ff l u o r e s c e n c el i f e t i m ed a t ar e s o l v et h ef l u o r e s c e n c ed e c a yp r o f i l ei nt e r m so f d i s c r e t e s i n g l ee x p o n e n t i a lc o m p o n e n t s 谢t l l d i s t i n c tl i f e t i m e s i n c o m p l e x ， h e t e r o g e n e o u sb i o l o g i c a ls a m p l e ss u c ha st i s s u e ，m u l t i - e x p o n e n t i a ld e c a yf u n c t i o n s c a na p p e a rt op r o v i d eab e t t e rf i tt of l u o r e s c e n c ed e c a yd a t at h a nt h ea s s u m p t i o no fa s i n g l e e x p o n e n t i a ld e c a y , b u tt h ea s s u m p t i o no fm u l t i p l ed i s c r e t ec o m p o n e n t si s e s s e n t i a l l ya r b i t r a r y i nt h i sp a p e ri tw a sp u tf o r w a r dt h a tq u a s i w e i b u l ld i s t r i b u t i o n d e n s i t yf u n c t i o n a n da r t i f i c i a ln e u r a ln e t w o r k sw e r el i k e l yt o p r o v i d eat r u e r r e p r e s e n t a t i o no ft h eu n d e r l y i n gf l u o r e s c e n c ed y n a m i c s a sc o m p a r e dw i t ht h o s eo f s i n g l ee x p o n e n t i a la n dm u l t i - e x p o n e n t i a ld e c a yf u n c t i o n s ，t h en o v e lm o d e lc a ny i e l d t h eb e t t e rg o o d n e s so ff i tu s i n gd a t af r o mm u l t i w e l lp l a t ea s s a y so fc h e m i c a l l ya n d b i o l o g i c a l l yi n t e r e s t i n gf l u o r o p h o r e s i nt h es a m et i m e ，t h ep o t e n t i a la p p l i c a t i o no f t h e q u a s i w e i b u l ld i s t r i b u t i o nd e n s i t yf u n c t i o nt o f l u o r e s c e n c el i f e t i m ei m a g i n gw a s d i s c u s s e d a e s t h e t i cs u r f a c e sm o d e l l i n gi sa ni m p o r t a n tt a s ki nc o m p u t e ra i d e dg e o m e t r i c d e s i g na n dc o m p u t e rg r a p h i c s t h es h a p e so f s u r f a c e sb a s e do np d ea r ed e p e n d e n to n b o u n d a r yc o n d i t i o n sc o m p l e t e l ya n dc o m p u t a t i o ni st i m e c o n s u m i n g h o w e v e rs i m p l y a d j u s t i n gs o m ep a r a m e t e r si nt e r mo fg e o m e t r i cs e n s eo ft h eb o u n d a r yc u r v e sa n dt h e d e r i v a t i v eb yu s i n gt r a n s f i n i t ei n t e r p o l a t i o nc a nd ot h es a m et a s k t h em e t h o di se a s y i v a b s t r a c t t oo p e r a t ea n dh a sl e s sc o m p u t i n gt i m e i nt h i sp a p e rt r a n s f i n i t ei n t e r p o l a t i o na n di t s s p e c i a l t i e sa r ed i s c u s s e da n dal a r g en u m b e ro fa e s t h e t i cs u r f a c e sm o d e l e dw i t h i n t e r p o l a t i n gc r o s sc u r y e sa n dw i t hb o u n d a r yc u r v e sa n dt h e i rd e r i v a t i v e s t h em e t h o d i sm o r ee f f i c i e n tt h a np d ei nc o m p u t a t i o n k e yw o r d s ：c a r b o nm o n o x i d e ，n o b l em e t a l ，c a t a l y s i sg e n e t i ca l g o r i t h m s ，l e a s ts q u a r e f i t t i n g ，b 。s p l i n ec u r v e s ，b 6 z i e rc u r v e s ，c a r b o nd i o x i d e ，p u r i f y i n g ， a r t i f i c i a ln e u r a ln e t w o r k ，f i t t i n g ，b i o m e d i c a l o p t i c s ，q u a s i w e i b u l l d i s t r i b u t i o n d e n s i t yf u n c t i o n ，f l u o r e s c e n c el i f e t i m e i m a g i n g ， f l u o r e s c e n c ed e c a yp r o f i l e ，t r a n s f i n i t ei n t e r p o l a t i o n ，a e s t h e t i cs u r f a c e m o d e l i n g ，h e r m i t ei n t e r p o l a t i o n v 第一章绪论 第一章绪论 1 1 遗传算法历史及发展概况 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种基于生物自然选择和基因遗传学 原理的高效并行、随机全局优化搜索算法。由于有鲜明的生物背景和适用于任何 函数类等特点，进化算法计算自6 0 年代中期以来引起众多领域的普遍关注( 周 9 9 ) ，特别是1 9 7 5 年h o l l a n d 系统提出以后，遗传算法备受关注，成为持续深入 的研究热点，并已广泛应用于从自然科学、工程技术到社会科学的众多领域，尤 其是广泛应用于函数优化、组合优化、生产调度问题、自动控制、机器人学、图 像处理、人工生命、遗传编程、机器学习、数据挖掘、人工神经网络训练、程序 自动生成、专家系统的知识库维护等一系列超大规模、高度非线性、不连续、多 峰函数的优化( h 0 1 9 2 ，刘0 0 ，陈9 6 ，f o r 9 3 ，席9 6 ，贺9 8 ，郭9 8 ，张0 1 ，吉0 4 ) 。 2 0 世纪6 0 年代，j o h nh o ll a n d 教授和他的数位博士受到生物模拟技术的启 发，认识到自然遗传可以转化为人工遗传算法。1 9 6 2 年j o h nh o l l a n d 提出了利 用群体进化模拟适应性系统的思想，引进了群体、适应值、选择，变异、交叉等 基本概念。1 9 6 7 年，j d b a g e l y 在其博士论文中首次提出了“遗传算法”的概 念。1 9 7 5 年，h o l l a n d 出版了自然与人工系统中的适应性行为( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m ) 。该书系统地阐述了遗传算法的基本理论和方 法，提出了遗传算法的基本定理一模式定理，从而奠定了遗传算法的理论基础。 同年，d ej o n g ( d e j 7 5 ) 在其博士论文中首次把遗传算法应用于函数优化问题， 对遗传算法的机理与参数进行了较为系统地研究，并建立了著名的五函数测试平 台。2 0 世纪8 0 年代初，h o l l a n d 教授实现了第一个基于遗传算法的机器学习系 统一分类器系统( c l a s s i f i e rs y s t e m 简称c s ) ，开创了基于遗传算法的机器学 习的新概念。1 9 8 9 年，d a v i dg o l d b e r g 出版了搜索、优化和机器学习中的遗 传算法( g e n e t i ca l g o r i t h m si ns e a r c h o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) 。 该书全面系统地总结了当时关于遗传算法的研究成果，结合大量的实例，完整的 论述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础。1 9 9 2 年，j o h n r k o z a 出版了专著遗传编程( g e n e t i cp r o g r a m m i n g ) ，提出了遗传编 程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等 浙江大学博士学位论文 方面。随着遗传算法的不断深入和发展，关于遗传算法的国际学术活动越来越多， 遗传算法已成为一个多学科、多领域的重要研究方向( 陈0 3 ) 。 1 1 1 遗传算法的编码 编码是遗传算法要解决的首要问题。h o l l a n d 的编码方法是二进制编码，经过 几十年的发展，人们提出了各种编码方法来解决具体问题。 ( 1 ) 二进制编码( h 0 1 7 5 ) 它是遗传算法中最常用的一种编码方法。它具有编码、 解码操作简单易行：交叉、变异操作便于实现；符合最小字符集编码原则；便于 利用模式定理对算法进行理论分析等优点。 ( 2 ) 格雷码编码( 周9 9 ) 对于一些连续优化问题，二进制编码由于遗传算法的随 机特性而使其局部搜索能力较差。为改进这一特性，人们提出用格雷码进行编码。 格雷码编码方法是二迸制编码方法的一种变形。编码方法为连续的两个整数所对 应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。格雷码特 点是：任意两个整数的差是这两个整数所对应的格雷码之间的海明距离。这一特 点是遗传算法中使用格雷码来进行个体编码的主要原因。格雷码除了具有二进制 编码的优点外，还能提高遗传算法的局部搜索能力。 ( 3 ) 实数编码( 周9 9 ) 。对于一些多维、高精度要求的连续函数优化问题，使用二 进制编码来表示个体将会带来一些不利，例如，二进制编码存在着连续函数离散 化时的映射误差，同时不便于反映所求问题的特定知识。为克服这些缺点，人们 提出实数编码方法，即个体的每个基因值用实数表示。实数编码方法具有适合于 遗传算法中表示范围较大的数；便于较大空间的遗传搜索；提高了遗传算法的精 度要求；改善了遗传算法的计算复杂性，提高了运算效率；便于算法与经典优化 方法的混合作用；便于设计专门问题的遗传算子优点。 ( 4 ) 符号编码方法( 玄光o o ) 是指染色体编码串中的基因值取自一个无数值含 义、而只有代码含义的符号集。这些符号可以是字符，也可以是数字。例如，对于 旅行商问题，假设有n 个城市分别记为c 1 ，c 2 ，c n ，则 c 1 ，c 2 ，c n 】就可 构成一个表示旅行路线的个体。符号编码的主要优点是便于在遗传算法中利用所 求问题的专门知识及相关算法。 1 1 2 遗传算法的收敛性和参数调整 由于函数优化问题是许多领域中普遍存在的问题，因此在遗传算法的众多应 2 第一章绪论 用中，函数优化问题是首当其冲地成为主要应用。在遗传算法用于函数优化时， 有两个主要的问题需要研究：一是算法的收敛性和收敛速度估计，二是算法的改 进。 遗传算法已有的收敛性分析大都是在概率收敛意义下考虑的且基于算法的 遍历性分析。这种收敛性分析不确保算法在有限步内收敛到问题的全局最优解且 所获结果仅对带“杰出者记录策略”的算法有效。徐宗本等首次运用鞅论研究遗 传算法的几乎必然强收敛性，证明一大类不带“杰出者记录策略”的遗传算法能 以概率1 确保在有限步内达到全局最优解，所获结果为遗传算法的实际应用奠定 了理论基础( 【徐0 2 】) 。实际应用要求遗传算法的群体规模有限，迭代次数有限， 因此徐宗本等的这一最新研究成果为遗传算法的实际应用奠定了更为坚实的理 论基础。但总的看来，遗传算法的基础理论还处在进一步的发展和完善过程当中。 在大量的实际应用当中，人们发现遗传算法存在一些问题，主要有过早收敛、 局部搜索能力较弱从而导致求解效率低和求解精度不高，对遗传算法的改进因而 成为重要的研究课题之一。改进策略大致有以下几种：动态和自适应调整策略、 混合策略、分布式和并行化策略及其它策略( 周0 2 】) 。 动态和自适应调整策略主要通过调整算法的参数、个体的适应值和算子的作 用范围等来提高算法的性能。s r i n i v a s 等( 【s p 9 4 】) 提出了如下的自适应调整杂交概 率只和变异概率己的建议：按照个体的适应值自适应地改变和己，当群体陷 入局部最优点或过早收敛时增大只和己，当群体散布于解空间时减小只和匕。 高适应值的个体取小的和巴，低适应值的个体取大的e 和只。雷德明、金聪 ( 雷9 9 ，金0 1 】) 】也提出了类似的调整策略。徐宗本等( 徐9 6 ) 从理论上分析了 遗传算法过早收敛现象后指出杂交算子使遗传算法过早收敛的趋势与杂交概率 无关，因此算法过早收敛时增大没有理论依据。有的文献( 马9 8 ，李9 9 ，令狐0 1 ， 韩0 2 】) 提出了只调整变异概率的一些新方法也取得了比较好的效果。张金华等 ( 张0 2 ) 的方法除了可以自适应调整e 和匕外，还在改进的算法中使用竞赛选 择，使得选择压力也可以自适应调整。 群体规模是遗传算法的重要参数，太小容易过早收敛，太大搜索效率不高。 当采用自然数编码时，从理论上可以证明遗传算法的最优群体规模的存在性，并 浙江大学博士学位论文 给出相应的计算方法。种群规模影响到遗传算法的最终性能和效率。种群规模过 小将影响搜索范围，从而得不到最优解，种群规模过大则使搜索效率降低。在试 验中，种群规模的变化范围是从1 0 1 6 0 ，增量为1 0 ( 郑0 3 ) ) 。 个体适应值的标定或调整对克服算法的过早收敛和局部搜索能力弱的问题 是有帮助的( m i c 9 6 ，林0 0 ，玄光0 0 】) 。使用基于适应值比例的选择策略如赌轮选 择存在一些弱点，如在群体演化过程的初期，一些适应值较高的所谓超级个体， 会被多次选中，而适应值较低的个体则被淘汰掉，群体多样性因此而下降，容易 引起过早收敛。而在群体演化过程的后期，当群体相对集中于最优解附近时，个 体之间的适应值差别很小，对个体的选择过程退化为随机选择，从而导致算法局 部搜索能力减弱。个体适应值的标定或调整是解决这些问题的方法之一，其目的 是保持个体之间的适应值比的合理差距，在群体演化初期限制竞争，阻止超级个 体的快速增加，而在后期，则鼓励竞争( 【玄光0 0 】) 。标定或调整方式有：线性标 定、盯截断、幂律标定等。徐宗本等( 徐9 6 ) 从理论上分析了遗传算法过早收敛 现象后指出，通过动态改变适应性函数的方法来克服遗传算法的过早收敛是有理 论基础的。莫鸿强( 莫0 1 ) 通过理论分析和细致的实验比较指出，适应值标定能 否起作用决定于群体是否具备多样性，要改善遗传算法的搜索能力，关键不在适 应值标定，而在群体多样性。 调整算子作用范围的典型例子是m i c h a l e w i c z ( m i c 9 6 ) 提出的一种非均匀变 异算子，算子的变异范围随进化代数的增加而减小，在群体演化初期，均匀地搜 索解空间，而到了后期，变异范围非常小，使得新产生的个体局限在一个小范围 内，对提高算法的局部搜索能力是有帮助的。用数值实验测试了使用非均匀变异 的遗传算法和不使用该算子的遗传算法，结果表明前者的优化精度更高且收敛更 快。 1 1 3 ，遗传算法的策略 混合策略还可分为算法的混合和算子的混合。算法的混合就是将其它算法与 遗传算法结合起来得到一种混合遗传算法。经典的遗传算法只使用一种选择算 子，一种交叉算子和一种变异算子，算子的混合就是在算法中采用多种选择算子、 多种杂交算子、多种变异算子以及引进其它机制的算子从而构成一种混合遗传算 法。 4 第一章绪论 遗传算法与其它算法的混合研究主要是实验性的，没有形成理论( l g 9 7 】) ， 但是有一些指导性的原则( 【刘o o ) ，具体有三条： 1 尽量采用原算法的编码，以便利用原算法的有关知识： 2 利用原算法的优点，保证混合遗传算法的求解质量不低于原算法的求解 质量； 3 第三改进遗传算子，以便适应新的编码方式。 遗传算法的全局搜索能力较强，能较快地确定全局最优点的大概位置，但局 部搜索能力较弱，进一步精确求解要耗费很长时间。根据第二条原则，将局部搜 索能力强的算法与遗传算法结合可以相互取长补短。这方面的研究己有很多成功 的例子，主要有以下几个方面： 1 将遗传算法与传统的优化算法相结合。传统的优化算法中不乏具有较强 局部搜索能力的算法( 陈8 9 ) ，如使用导数的最速下降法、拟牛顿法，无需导数 的单纯形法、模式搜索法等。已有不少文献如报告了遗传算法与这类算法的混合 ( r b 9 4 ，r f 9 6 ，赵9 7 ，徐9 8 ，彭9 9 ，谢o o ，何0 1 ，向0 2 ) ，效果是比较好的。 2 模拟退火算法( 【k g v 8 3 】) ( s i m u l a t e da n n e a l i n g ，s a ) 是一种模拟固体退火过 程的启发式随机搜索算法，具有较强的局部搜索能力，算法虽使用了m e t r o p o l i s 接受准则，可避免搜索陷入局部最优解，但该算法全局搜索能力较弱，搜索效率 不高。将遗传算法与模拟退火算法结合起来是有可能得到性能较好的混合算法 的。这两种算法的结合方式比较灵活，a d l e rd ，吴志远等( a d l 9 3 ，吴9 7 】) 用模拟 退火变异( s a m ) 和模拟退火重组( s a r ) 算子替换原来的变异和杂交算子。s a m 算 子与原变异算子的工作原理相同，但模拟退火变异后的解要按m e t r o p o l i s 准则决 定是接受变异后的解还是变异前的解。s a r 算子的工作原理与s a m 算子类似。 这种作法的目的是要减轻来自选择算子的选择压力，将部分选择性转移给杂交和 变异算子。张讲社等( 张9 7 ) 用退火选择代替原来的比例选择得到了整体退火遗 传算法。周明等( 周9 9 ) 贝j j 提出了一种先通过选择、杂交和变异产生一组新的个 体，再独立对每一新个体执行模拟退火操作的方法。 。 3 禁忌搜索( t a b us e a r c h ，t s ) 是一种人工智能算法，具有记忆功能及局部搜 索能力强的优点，除了可以弥补遗传算法的局部搜索能力弱的缺点，还可以弥补 遗传算法因随机操作而无法避免的重复采样( r e s a m p l i n g ) 问题。李大卫等( 【李 浙江大学博士学位论文 9 7 ) 将禁忌搜索与遗传算法结合到一起，结合方法是用禁忌搜索变异( t s m ) 和禁 忌搜索重组( t s r ) 算子替换原来的变异和杂交算子( 李9 7 】) 。 4 遗传算法还可以和神经网络( 李9 9 ，曹9 9 ，陶0 1 】) 、其它数学方法如 正交设计法( l w 0 1 ， 史0 2 、统计推断( 张9 7 ) 等结合得到性能更好的混合遗传算 法。 算子的混合也是比较常见的一种混合策略。遗传算子的搜索都具有一定的倾 向性，某些算子搜索范围大，适合全局搜索，某些则较小，主要进行局部搜索 ( b a r 9 9 】) 混合使用多种算子的初衷就是要综合利用各种算子的特点，以期获得好 的搜索效果。 分布式和并行化策略属于基于空间分离的多样性保持法( i a l 0 0 】) 的两个典 型的遗传算法的实现方法。遗传算法本质上是并行的搜索算法，因此分布式遗传 算法和并行遗传算法是遗传算法更自然的实现。分布式遗传算法采用多个子群 体，每个子群体独立地串行执行遗传算法( h l 0 0 ) 。子群体间通过迁移机制交换 染色体( c t s 9 4 ) 。典型的例子如文献( 【h l 0 0 ) 的渐进分布式实数编码遗传算法， c r a i gp o t t sj 等( c t s 9 4 ) 的基于迁移和人工选择的改进遗传算法等。并行遗传算 法以群体的管理方式不同分为三种基本类型：全局单群体主从式、全局单群体细 粒度和多群体粗粒度并行遗传算法( 【李0 2 】) 。并行遗传算法具有求解大规模复杂 函数优化问题的强大能力，如文献( 刘0 0 ) 报告了一个并行遗传算法求出了 4 0 0 维r a s t r i g i n 函数的全局最小解。 以上只是列举了一些遗传算法的主要改进方法和策略，事实上，还有很多其 它的改进方法，这里不可能一一列举。对遗传算法的种种改进反映了人们寻找有 效解决复杂函数优化问题的算法的迫切愿望。 1 1 4 遗传算法的特点 遗传算法具有进化计算的所有特征，同时又具有自身的特点： 1 直接处理的对象是决策变量的编码集而不是决策变量的实际值本身，搜 索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。 2 遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性。 3 遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一 种概率方式来进行，从而增加了搜索过程的灵活性，同时能以很大的概率收敛于 6 第一章绪论 最优解，具有较好的全局优化求解能力。 4 遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较 好的普适性和易扩充性；同时，我们可以把搜索范围集中到适应度较高的部分搜 索空间中，从而提高了搜索效率。 5 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 1 2 人工神经网络的历史及发展概况 人工神经网络是在对人脑组织结构和运行机智的认识理解基础之上模拟其 结构和智能行为的一种工程系统。早在本世纪4 0 年代初期，心理学家m c c u l l o c h 、 数学家p i t t s 就提出了人工神经网络的第一个数学模型，从此开创了神经科学理 论的研究时代。其后r o s e n b l a t tf 、w i d r o w 和h o p f 、h o p f i e l dj j 等学者又先后 提出了感知模型，使得人工神经网络技术得以蓬勃发展。 1 9 4 3 年心理学家m c c u l l o c hw w 和数理逻辑学家wp i t t s 对生物神经网络 ( b i o l o g i c a ln e u r a ln e t w o r k ) 作了专门的研究，发表了关于神经网络的数学模型， 即m p 神经网络模型，由此正式开创了神经计算的时代。m c c u l l o c h * 口p i t t s 的研 究方法，大大地开阔了人们的思路。在这以后，1 9 4 9 年神经生物学家d o h e b b 从生理学角度提出了至今仍对神经网络有着重要影响的h e b b 学习规则 ( 【h e b 4 9 ) 。这一法则告诉人们，神经元之间突触的联系强度是可变的，这种可 变性是学习和记忆的基础。h e b b 法则为构造具有学习功能的神经网络模型奠定 了基础。 1 9 5 8 年，r o s e n b l a t t 在原有m p 模型的基础上增加了学习机n ( g o s 5 8 1 ) 。他提出 了感知器模型( 【r o s 5 8 ) 。这个模型由简单的阀值性神经元构成，初步具备了诸 如学习性、并行处理、分布存储等神经网络的一些基本特征，从而确立了从系统 角度进行人工神经网络研究的基础，首次把神经网络理论付诸工程实现，他的成 功之举大大激发了众多学者对神经网络的兴趣。r o s e n b l a t t 证明了两层感知器能 够对输入进行分类，他还指出了带隐层处理元件的三层感知器这一重要的研究方 向。r o s e n