（基础数学专业论文）基于共轭梯度法的混合遗传算法研究.pdf

r a b s t r a c t n o n l i n e a ro p t i m i z a t i o nc o m p u t a t i o n a lm e t h o di sac r o s s c u t t i n gr e s e a r c h i n ga r e ao f o p e r a t i o n a lr e s e a r c ha n dc o m p u t a t i o n a lm a t h e m a t i c s i n t e l l i g e n to p t i m i z a t i o nm e t h o di sa n a c t i v er e s e a r c hi nr e c e n ty e a r s t h e s et w om e t h o d sh a v eaw i d er a n g eo fa p p l i c a t i o n si nm a n y r e a ls e c t o r s ，s u c ha st h en a t i o n a ld e f e n s e ，e c o n o m i c ，e n g i n e e r i n ga n ds oo n t h e yh a v ea l l i m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c ee s p e c i a l l yi nu n c o n s t r a i n e da n ds u p e r l i n e a ro p t i m i z a t i o n p r o b l e m s i nt h i sp a p e r ，id os o m er e s e a r c h e so nm u l t i p l eh u m pf u n c t i o no p t i m i z a t i o np r o b l e m s a h y b r i dg e n e t i ca l g o r i t h mb a s e do nn o n l i n e a rc o n j u g a t eg r a d i e n ta l g o r i t h mi sp r o p o s e d t h eb a c k g r o u n da n dt h er e s e a r c ha c t u a l ! t yo fc g aa n dg aa r ep r e s e n t e di ni n t r o d u c t i o n t h e n ，t h eo r g a n i z a t i o n a lo ft h i sp a p e ri so f f e r e db r i e f l y i nc h a p t e r1 ，w ef i r s tp r o p o s es o m ec o n j u g a t eg r a d i e n ta l g o r i t h mt h e o r i e sa n dr e v i e wt h e d e t a i l so fs g a s o m em i l dc o n d i t i o n sa r eg i v e ni nt h i sc h a p t e r , w h i c he n s u r et h eg l o b a l c o n v e r g e n c eo ft h e s em e t h o d s i nc h a p t e r2 ，w ee m p h a s e sr e s e a r c ho nan e w h y b r i dg e n e t i ca l g o r i t h mw h i c hc a ns o l v e t h em u l t i p l eh u m pf u n c t i o n so p t i m i z a t i o np r o b l e mb e t t e r an e wh y b r i dg e n e t i ca l g o r i t h m w h i c hc o m b i n e st h eg o o dp r o p e r t yo fg l o b a ls e a r c ho ft h eg e n e t i ca l g o r i t h ma n dt h eg o o d p r o p e r t yo fr e g i o n a ls e a r c ho ft h ec o n j u g a t eg r a d i e n ta p p r o a c hi sp r o p o s e d t oe n s u r eg l o b a l c o n v e r g e n c e a n ds u p e r l i n e a rc o n v e r g e n c er a t eo ft h ec o n j u g a t e g r a d i e n ta l g o r i t h m ，w e i n t r o d u c et h en + 1s t e pr e t u r nm e t h o d i tc a ne n s u r et h a tt h ee a c hs t e pi sd e s c e n td i r e c t i o n t h e n ，w ep u tf o r w a r dg r a yc o d e dn o tb i n a r y c o d e dt oa v o i dh a m m i n gc l i f f i no r d e rt oe n s u r e t h ed i v e r s i t yo fp o p u l a t i o na n di m p r o v et h ev e l o c i t yo fc o n v e r g e n c ea n de f f i c i e n c y , t h en i c h e s k i l li s b r o u g h to u t ，b yw h i c ht h eb e s to p e r a t o ri s b e t t e rs h a r e da n dt h ef u n c t i o ni s s t r e n g t h e n e d i te x c e e d ss t a n d a r dg e n e t i ca l g o r i t h m ( s g a ) o nt h ea b i l i t yo fl o c a ls e a r c h i n g a n dp r e m a t u r ec o n v e r g e n c e t h eh y b r i dg e n e t i ca l g o r i t h mb yd e f i n i n ga na d d i t i o n a lo p e r a t i o nw h i c hi sd e s i g n e da s c g o p e r a t o ra n da c tt ot h eb e s ti n d i v i d u a li nt h ee v o l u t i o np r o c e s s e so fg a a f t e rs e l e c t i o n ， c r o s s o v e ra n dm u t a t i o no p e r a t o r , t h e nt h eo p t i m a t i o no fh y b r i da l g o r i t h mi sr e a l i z e d t h e c o n c l u s i o no fg l o b a lc o n v e r g e n c ei sa l s os h o w n i n c h a p t e r3 ，w ep r o p o s es o m e n u m e r i c a le x p e r i m e n t ，a n dt h er e s u l t ss h o wt h e f e a s i b i l i t ya n de f f i c i e n c yo ft h em e t h o d e x p e r i m e n t si n d i c a t et h a tt h eh y b r i da l g o r i t h mi s b e t t e rt h a ns g aa n dc g aa l o n e i ti sp r o v e di nt h ee x p e r i m e n t st h a tt h es c h e m en o to n l y c o u l ds t r e n g t h e ns e a r c h i n ga b i l i t yb u ta l s oc o u l da c c e l e r a t e t h ec o n v e r g e n ts p e e do f o p t i m i z a t i o n i nt h el a s tc h a p t e lw es u mu pt h er e s e a r c he f f o r t si nt h i st h e s i sa n dg i v ep r o s p e c t so ft h e f u r t h e rr e s e a r c hi nt h ef i e l d s k e y w o r d s ：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 ) ，g e n e t i ca l g o r i t h m ( g a ) ，n i c h e t e c h n o l o g y ，m u l t i m o d a lf u n c t i o n i l m 98叭7 呲44 7洲y 中文文摘 本文主要研究基于共轭梯度法和小生境技术的混合遗传算法，并用此求解多峰函数 优化问题。提出将共轭梯度法和遗传算法相互补充，针对共轭梯度法全局搜索难和遗传 算法一般只能得到全局范围内的近似最优解的缺点，又充分利用了遗传算法的全局搜索 能力和共轭梯度法的局部搜索能力的优点，综合两种算法，提出混合遗传算法。此混合 遗传算法在遗传算子中引入小生境共享函数，增加原有算法群体的多样性。详细分析了 所给算法的收敛性，并利用m a t l a b7 0 平台，对一些经典的多峰函数进行数值实验，得 出混合遗传算法优于标准遗传算法和共轭梯度法，以验证所做的理论分析。本文的组织 结构如下： 绪论部分，概述了问题的研究背景及意义和国内外研究现状，提出共轭梯度法和遗 传算法有着广泛的应用和实际价值。特别对大规模和高度非线性的函数优化问题有重要 的理论意义。之后介绍了本文的研究内容和组织结构。 第一章详细介绍了共轭梯度法和标准遗传算法重要理论知识。介绍非线性共轭梯度 算法迭代公式及几种的著名反的选取，后介绍几种常用的步长因子a 。的线搜索准则。 对于目标函数厂0 ) 是二阶连续可微，水平集l 有界，步长吼采用强w r o l f e 非精确搜索， f r 共轭梯度算法具有全局收敛性，此时f r 、p r p 、h s 可相互等价。 标准遗传算法( s g a ) 是一种基于群体寻优的方法，根据适应值的大小来选择和繁殖 个体，最终得到适应值最好的个体。可以证明s g a 不能以概率1 收敛到全局最优解， 但是s g a 的每代在选择操作前( 后) 保留最优解的s g a 以概率1 收敛到全局最优解， 即最优保存的s g a 是全局收敛的。本文对其收敛性给出证明。针对s g a 局部搜索能力 不足即“早熟 现象，本文提出基于小生境技术的遗传算法，更好的保持解的多样性， 同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。 第二章提出了本文的研究重点基于共轭梯度法的混合遗传算法研究。本文提出将共 轭梯度法和遗传算法相互补充，充分利用遗传算法的全局搜索能力和共轭梯度法的局部 搜索能力的优点，提出混合遗传算法，并用其解决多峰值函数优化问题。 在共轭梯度法改进中提出对一般的非线性函数，根据峰的特点：峰值点的函数值比 其附近点的函数值都高；越是接近峰，梯度就越接近于零。我们采用k 卅= x k + 吼畋， d t2 一g 。：麓d ，：呈用精确线搜索求步长口t2 a 唱m i n o ( ( * t + 谢t ， 展一躺，畋= 一( ，一锱) 敝，并采用刀+ 1 步返转策略，保证每步都 是下降方向，收敛速度提高到超线性收敛。在遗传算法的改进中引入小生境技术，引入 i l l 共享函数：s ，工) = 1 一【掣k 胭一 0 ， d “，工j ) s m a x ，保证原有种群的多样性。按下式计 算共享适应值或共享选择概率厂：f 瓴) 。i 盟；得到了每个个体的共享选择概率 s ( x i , x j ) 厂，接着再进行轮盘选择。若有 j i - 1 p o p _ s i z ef l 鼍s 瓤| 飞f i。j 。小静静 薯j j 则选择状态i 进行复制，其中五为个体i 的共享选择概率。使得优秀算子能够更好的共享， 提高了群体的整体搜索性和收敛效率。有效地克服了标准遗传算法中的“早熟 问题。 还提出了用格雷( g r a y ) 编码，避免了海明悬崖( h a m m i n g c l i f o 问题，二进制编码至：l j g r a y 编码的变换为 f 岛， 若i = 1 吒5 1 岛一。o6 j ，暂 1 。 其中。表示模2 加法。 混合遗传算法先由遗传算法经选择、交叉、变异得到种群，再用共轭梯度算子进行 局部寻优得到新群体，由于可行域是连通的。在加入共轭梯度算子的遗传算法求解多峰 函数优化计算时，负梯度方向是目标函数的下降方向，沿负梯度方向变异的遗传算子可 以更快达到可行域，并取得最优解。最后得到最优群体。本文给t b 混合遗传算法的收敛 性证明。若由混合遗传算法产生的序列“，工：，吒，) ，则f ( x 。) 以概率1 收敛到f ( x ) 的 全局最优值f ( x ) 。 第三章数值实验，本文给出几个典型的多峰函数，求其峰值( 极大值) 。所有程序 都为m 语言并在m a t l a b7 0 环境下运行。说明提出的混合遗传算法的可行性和优越性。 由实验结果比较分析了标准遗传算法和改进后的混合遗传算法，得出共轭梯度法和遗传 算法的结合不但有良好的搜索能力还有较快的收敛速度。在标准遗传算法里引入小生境 技术避免标准遗传算法的收敛速度慢和“早熟”的现象，还保障群体个体的多样性。 最后一章对本文研究工作的总结，介绍研究成果和创新点，并对将来的研究工作进 行展望。提出尚待解决的问题。 i v 目录 中文摘要i a b s t r a c t i i 。 中文文摘i i i 绪论1 第一章共轭梯度法和标准遗传算法基本理论。5 1 1 共轭梯度法的基本理论5 1 1 1 线性共轭梯度法5 1 1 2 非线性共轭梯度法6 1 2 标准遗传算法的基本知识1 0 1 2 1 标准遗传算法的组成1 0 1 2 2 标准遗传算法的重要知识1 3 1 2 3 标准遗传算法的缺点1 7 1 3 小生境遗传算法1 7 第二章基于共轭梯度法的混合遗传算法研究1 9 2 1 改进的共轭梯度法1 9 2 1 1 共轭梯度算法的返转策略。1 9 2 1 2 改进的h s 方法2 0 2 2 改进的混合遗传算法2 1 2 2 1 混合遗传算法设计步骤2 2 2 2 2 混合遗传算法具体操作。2 3 2 3 收敛性证明3 4 第三章数值实验3 6 第四章结论- 4 8 参考文献4 9 致谢5 2 v u 绪论 研究背景及意义 非线性优化计算方法f 1 。5 ，9 , 1 2 , 1 5 】是计算数学与运筹学的交叉学科，非线性优化在国 防、经济、金融、工程、管理等许多领域有着广泛的应用。如同化问题、蛋白质折叠问 题、模式识别问题都可归结为非线性优化问题。这些问题往往都是大规模和高度非线性 的。非线性优化计算法包括共轭梯度法，拟牛顿法、罚函数法等。本文主要研究共轭梯 度法求解非线性优化问题。 智能优化方法【4 6 ，7 , 8 , 1 0 , 1 3 , 1 4 l 是一个近年来发展起来的非常活跃的研究领域。系统工程、 自动化、计算机、管理工程等许多专业的学者都在广泛地采用智能优化方法。如，遗传 算法、禁忌搜索算法、模拟退火算法、蚁群算法等在国民经济的各个行业中都获得了广 泛的应用。本文主要研究遗传算法解决优化问题。本文提出将共轭梯度法和改进的遗传 算法结合的混合遗传算法来解决多峰函数优化问题。 共轭梯度法( c g m ) 【1 2 3 ，1 2 ，1 5 j 是无约束优化方法中较常用的算法之一，仅需要目标函 数值和梯度函数值，不需要计算h e s s i a n ( 海塞) 阵和矩阵存储，而且收敛速度快的方法， 克服了最速下降法收敛慢的缺点，又避免了牛顿法存储和计算量大的不足。对于一般的 非线性互补问题( n c p ) ，它具有计算公式简单，存贮量少，收敛速度快而得到广泛应用， 研究它有很强的理论和实际意义。共轭梯度法的实质是在每一步迭代过程中，新的搜索 方向为当前迭代点的负梯度方向与上一步的搜索方向的线性组合。基本思想是使得这些 方向在厂“) 是二次凸函数时相互共轭，从而将一个多维问题转化为等价的多个一维问 题，具有二次终止性。 但对于一般的非线性函数厂o ) ，共轭梯度法的收敛速度仅为线性，对较难求解的 n p 问题，共轭梯度算法由于其搜索方向阵几乎是奇异的而使得搜索缓慢，从而过早结 束迭代。它虽具有极强的局部搜索能力，但全局搜索能力却较差。近几年，戴或虹、袁 亚湘等【2 4 4 ，4 5 j 给出了新共轭梯度d y 法，降低了搜索条件，搜索能力也有所提高。由于 梯度型数值解法在迭代过程中过多依赖目标函数值和已知点的梯度函数值，而这些信息 只能反映函数值的局部变化情况，因而梯度型算法大多只能得到问题的局部最优解。若 要求全局最优解，则需要用多个初始点进行运算，在所得到的局部最优解中取其最优者 当作全局最优解。 遗传算法( g a ) 【4 ，6 ，7 8 ，1 0 ，1 1 】是由美国m i c h i g a n 大学的j h o l l a n d 于1 9 7 5 年受生物进化论 的启发提出的，在同年出版了( ( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) 一书中，系 统阐述了g a 的基本理论和方法。后来d ej o n g 和g o l d b e r g 设计了g a 执行策略和性能 评价指标，使之更加完善。第一个把g a 用于函数优化的是h o l l s t i e n i l 1 4 j 。 g a1 6 - 8 , 1 0 - 1 4 】是一种新兴的搜索寻优技术，仿效生物的进化与遗传，具有极强解决问 福建师范人学薛凌霄硕士学位论文 题的能力，根据“优胜劣汰”原则，使所要解决的问题从初始解一步步地逼近最优解。 g a 的自组织、自学习和群体进化能力使其适用于大规模复杂优化问题。它将问题的求 解表示成“染色体”适者生存的过程，通过“染色体”群的一代代不断进化，包括选择、 交叉和变异等操作，最终收敛到“最适应环境 的个体，从而得到问题的最优解或满意 解。g a 最初并不是专门为解决最优化问题而研究的，但却因为最优化问题而得以发展 和深入。 g a 作为一种智能化的全局搜索算法【3 5 3 7 ，3 8 1 ，自8 0 年代问世以来便在数值优化、系 统控制、结构优化设计等诸多领域的应用中展现出其特有的魅力，同时也暴露出许多不 足和缺陷1 4 8 】。如完全依赖概率随机操作，易出现“早熟”现象。虽然可以避免陷入局部 极小值，但受寻优条件限制，一般只能得到全局范围内的近似最优解，很难得到最优解。 标准遗传算法( s g a ) 【4 】是一个反复迭代的过程，反复选择交叉变异得到新种群，直至用近 似收敛准则来终止算法进程，最终得到适应度相对高的种群。s g a 在多维、多参数或参 数范围很大的优化问题中往往收敛速度很慢，效果不理想，因此需要对其改进。若采用经 典优化算法，如最速下降法，共轭梯度法，牛顿法，拟牛顿法等，都只能得到局部最优解，而不 一定是全局最优解，大大影响收敛效果。若采用g a , 理论上可得到全局最优解，但在g a 中群体( p o p u l a t i o n ) 进化的不同阶段，当前最优解适应值不同。在有限次的迭代中，g a 因局部搜索能力不足容易出现早熟，也就不能得到很好的最优群体。 如何构造一种优化算法，使之能搜索到尽量多的或者全部全局最优解和有意义的局 部最优解，已成为一个重要的研究领域。 国内外研究现状 在实际中对于优化问题的计算，不仅要寻找全局最优解，而且需要找多个全局最优 解和局部最优解。如何搜索到多个最优解，已成为一个重要研究方向。关于多峰( 或超 多峰) 值函数的优化问题有着广泛的实际应用背景，而学者对此问题的研究也有以下几 种算法【2 1 刀l ：热力学演化算法；人工免疫网络算法；自适应遗传算法；克隆选择算法； 人工免疫算法等。每个算法都要认真的分析多峰函数中“峰 的特点，针对其性质，每 个“峰”的优值都要找到，避免漏掉低峰的情况。共轭梯度法的研究现状将在第二章基 本理论中谈到。 遗传算法区别于传统优化算法，优越性如下【4 舯l ： ( 1 ) 算法进行全空间并行搜索，将搜索重点集中于性能高的部分，从而能够提高效率且不 易陷入局部极小。 ( 2 ) 算法具有固定并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。 目前有关遗传算法的研究主要集中在以下几方面【4 , 6 - 8 1 ： ( 1 ) 算法的数学基础。遗传算法的基础理论研究包括算法的收敛性、收敛速度估计、早熟 机理的探索与预防、参数设置对算法的影响等。目前大多数针对较简单的遗传算法， 对于杰出者选择、锦标赛选择、均匀交叉、多点交叉及非一致变异等非简单的操作研 2 绪论 究成果很少。此外，以矩阵和不动点理论为基础的v o s e l i e p i n s 模型等有一些研究结 果，也有局限性。1 9 6 8 年h o l l a n d 提出了著名的模式( s c h e m a ) 定理。1 9 8 1 年b e t h k e 应用w a l s h 函数分析模式。 ( 2 ) 算法的改进与深化。编码除了二进制和实数编码外，还有指数编码、符号编码、序列 编码、变长染色体编码等。1 9 8 3 年w e t z e l 用遗传算法解决了n p 难问题旅行商问题 ( t s p ) 。 ( 3 ) 算法策略研究与设计。利用遗传算法的大范围群体搜索性能，与快速收敛的局部优化 方法( 如最速下降法、神经网络、模拟退火法及列表寻优法等) 混合产生有效的全局 优化方法，从根本上提高遗传算法的性能。1 9 8 5 年s c h a f f e r 利用多种群遗传算法研究 解决了多目标优化问题；1 9 8 7 年g o l d b e r g 等人提出了借助共享函数的小生境遗传算 法。但小生境技术的设计和理论并不十分完善，大多数都是针对二进制编码的函数优 化。 ( 4 ) 算法的并行化研究。并行遗传算法主要有细粒度和粗粒度两种计算模型，具体方法有 同步主从式、异步并发式和网络分布等三种，这与通信开销构成矛盾。但只要保持多 个群体恰当地控制群体间的信息交换不使用并行计算机，也能提高执行效率。 ( 5 ) 算法的选择。一个特定的优化算法只能对于某特定领域的问题优于另一算法。在实际 中，对一个特定算法如何确定它的使用函数子集，或对于具体的优化问题如何选择和 设计适宜的算法，有着重大的意义。当前，这类研究尚处起步阶段。 本文的研究内容和组织结构 本文研究内容是对共轭梯度法和遗传算法的做了若干研究，特色与创新之处将共轭 梯度法和遗传算法相互补充，并在遗传算法中加入小生境共享选择技术，用此混合遗传算 法来解决多峰函数的优化问题。并在m a t l a b 7 0 环境下做数值实验，实验充分证明混合 遗传算法的可行性和优越性，有更强的搜索能力和更快的收敛速度。本文提出将遗传算 法与共轭梯度法相结合的混合遗传算法，即在遗传算法中加入共轭梯度算子。混合遗传算 法先由遗传算法经选择、交叉、变异得到种群，再用共轭梯度算子进行局部寻优得到新 群体，最后得到最优群体。 该算法具有共享选择算子、交叉算子、变异算子和共轭梯度算子四种基本运算方式。 定义了适合于非线性多峰函数优化问题的小生境共享函数的选择算子，保证种群的多样 性，提高多峰函数优化问题的混合遗传算法的通用性。本文的组织结构如下： 第一章介绍共轭梯度法( c g a ) 和标准遗传算法( s g a ) 基本理论。对其收敛性给出证 明。 第二章提出了本文的研究重点。研究目的解决多峰函数优化。研究方法将共轭梯度 法和遗传算法相互补充，充分利用遗传算法的全局搜索能力和共轭梯度法的局部搜索能 力，提出混合遗传算法。在共轭梯度法改进中提出，l + 1 步返转策略，保证每步都是下降 方向，收敛速度提高到超线性。在遗传算法的改进中采用格雷编码避免海明悬崖。并引 3 福建师范大学薛凌霄硕士学位论文 入小生境技术，增加原有算法群体的多样性，提高了种群的整体搜索性和收敛效率，避 免“早熟”现象。 混合遗传算法先由遗传算法经选择、交叉、变异得到种群，再用共轭梯度算子进行 局部寻优得到新群体，最后得到最优群体。并给出收敛性证明。 第三章数值实验，实验充分证明混合遗传算法的可行性和优越性，有更强的搜索能 力和更快的收敛速度。 最后一章结论是对本文的主要成果和创新进行总结，并展望将来的研究工作。 本文的关键问题：1 如何制订编码方案；2 如何利用小生境共享函数确定选择策略； 3 如何在混合遗传算法中嵌入了一个共轭梯度算子；4 如何保证混合遗传算法的下降方 向：5 如何用m a t l a b 7 0 工具实现混合遗传算法的可视化操作。 4 第一章共轭梯度法和标准遗传算法基本理论 1 1 共轭梯度法的基本理论 非线性优化计算方法1 1 3 】是计算数学与运筹学的交叉学科，在近二十年得到了快速 发展，新的理论和算法层出不穷。本文主要研究非线性共轭梯度法，用其来求解无约束 优化问题。本文先简单介绍线性共轭梯度法，后介绍非线性共轭梯度法的研究状况和丰 富成果，共轭梯度法也成为当前最优化方法的重要算法类。 1 1 1 线性共轭梯度法 线性共轭梯度法f 1 , 2 , 3 , 9 】于1 9 5 2 年h e s t e n e s 和s t i e f e l 为求解线性方程组 a x = b ，x e r “ 而提出的，他们的文章( ( m e t h o d so fc o n j u g a t eg r a d i e n t sf o rs o l v i n gl i n e a rs y s t e m s ) ) 己成为 研究共轭梯度法的重要文献。后经f l e t c h e r 等人研究并应用于优化问题，取得了丰富的成 果。设目标函数厂o ) 至少一阶连续，记 ；厂o ：) ，g 。- v f 瓴) ，g o ) = v 厂o ) ，q = v 2 f 瓴) ，g g ) = v 2 ， ) 易知，当系数矩阵a 对称正定时，上面的线性方程组的求解等价于求解的二次规划问题 m 斌i n 。f ( x ) 2 血一b r x ( 1 1 1 ) 所以，h e s t e n e s 和s t i e f e l 的方法可以看作极小化一个二次函数的共轭梯度法。线性共轭 梯度法的一般算法格式如下： 算法1 1 1 ( 线性共轭梯度法) 步o 取初始a x o r 4 ，搜索方向d o ，使 0 ，置七净0 步1 若恬t0 满足： 厂( z i + a t d t ) s 厂o t + a d i ) ，v 口0 ，( 1 1 8 ) 非精确线搜索步长规则 a r m u o ( 1 9 6 9 年) 线性搜索：给定p ( o ，1 ) ，口。m a x pj ，歹一0 , 1 , 2 ， 满足： f ( x t + 口t d i ) sf ( x t ) + 6 口i g r d t( 1 1 9 ) w o l f e ( 1 9 6 8 年) 线性搜索：取吼满足： ，( 石t + 口t d t ) s + a 1 口tg t t d i ( 1 1 1 0 ) 和 其中0 盯1s 盯2 1 d r g ( x i + 口t d t ) 芝仃2 d r g t ，( 1 1 1 1 ) 强w o l f e 线性搜索：取吼满足： f ( x t + a i d i ) s - i - o r l 口t g r d i( 1 1 1 2 ) 7 福建师范大学薛凌霄硕士学位论文 和 p f g k + a k d 。) 卜：d ：g 。i ， ( 1 1 1 3 ) 其中o o r ls 2 1 精确线搜索在理论分析时有重要意义，计算量却不容忽视。因为在有限步内要得到严格 意义下的精确步长几乎是不可能的，在实际计算过程中，一般采用a r m i j o 步长规则和 w o l f e 步长规则主要思想是沿搜索方向产生一个能保证目标函数值有满意的下降量的迭 代点。w o l f e 步长规则在可接受的步长范围中包含了最优步长。 定义1 1 1 若向量以尺”满足d f g 。 o ， ( 1 1 1 5 ) 且存在常数6 2s 三，使得 l d v f ( x + 以) 卜一蟛：v 厂阮) ( 1 1 1 6 ) 第一章共轭梯度法和标准遗传算法基本理论 对一切k 都成立，则f r 共轭梯度算法具有全局收敛性即 艘i m i n f g 。”o ( 1 1 1 7 ) 非线性共轭梯度法的收敛性已有很多工作【l ，2 9 1 。前期主要研究在精确线搜索下求解 二次凸函数极小化问题时收敛性分析。后期对于较难求解的计算规模比较大的n p 问题， 大家又把焦点集中在共轭梯度法的研究上，由g i l b e r t 和n o c e d a l 关于p r p + 方法的研究 推动了非线性共轭梯度法全局收敛性分析的又一高潮1 1 , 9 j 。之后d a i 和y u a n 9 j 提出了d y 共轭梯度法及三项共轭梯度法。求解信赖域子问题的截断共轭梯度法使得人们对传统的 非线性共轭梯度法进行更深入的研究。 现在介绍一下经典的f r 、p r p 方法的背景和已有结果。 ( 1 ) f r 方法 p o w e l l ( 1 9 8 4 a ) 在精确线搜索( 即吃一0 ) 的假定下证明了风方法求解二次连续可微函 数的全局收敛性。a 1 一b a a l i ( 1 9 8 5 ) 将p o w e l l 结果推广到非精确线搜索( 即也 去，此时算法可能产生上升方向而导致失败。如采用广义线搜索， 二 即允许在上升方向的反方向搜索以及在稳定方向走零步长，则可证明只要 v 厂瓴+ 吼d k ) 也d f 夥瓴) ，如( 去，1 ) ( 1 1 1 8 ) f r 方法就能保证全局收敛性【1 , 2 , 9 l 。很多学者将f r 方法结合遗传算法进行函数优化。 ( 2 ) p r p 方法 在实际计算中p r p 方法比f r 方法好，是数值表现最好的共轭梯度法之一。 p o w e l l ( 1 9 8 4 a ) 1 9 】给出例子：在精确线搜索下的p r p 方法产生的点列吒在6 点附近循环， 而这6 点中任何一点都不是目标函数的稳定点。若限定目标函数二次连续可微，则无论 是精确线搜索还是非精确线搜索的p r p 法均能产生一串点列 & ) ，k - - 1 , 2 ，使得 ! i m 。i n 唯。1 1 2 o ( 1 1 1 9 ) p o w e l l 的例子说明p r p 方法对一般非线性函数可能不收敛，从而破坏了其全局收敛性。 但对于一致凸函数厂o ) ，采用精确搜索的p r p 方法有全局收敛性。 g i l b e r t 和n o c e d a l 提出p r 尸+ 方法，本质上是p r p 方法和最速下降法的综合： 卢严+ = m a x 枷尸，0 ( 1 1 2 0 ) 可证明在适当的线搜索下，尸! r p + 法对求解非凸函数极小化问题时的全局收敛性。 利用综合的思想还有许多展的公式： 9 福建师范大学薛凌霄硕士学位论文 0 。；m a x m i n 8 ，母：r 、吨( 、1 1 2 1 ) k | m a x m i n 岱p ，、，一j | 3 、( 1 1 2 2 ) 展= m a x m i n f l h s ，群y 】，o 】( 1 1 2 3 ) 分别由t o u a t i a h m e d 和s t o r e y ( 1 9 9 0 ) ，g i l b e r t 和n o c e d a l ( 1 9 9 2 ) ，及d a i 和y u a n ( 1 9 9 9 ) 提 出。本文所用的h s 方法与p r p 方法类似，收敛性和数值表现差不多。 1 2 标准遗传算法的基本知识 遗传算法1 6 - 8 1 是根据问题的目标函数构造一个适应值函数，对一个由多个解( 每个 解对应一个染色体) 构成的种群进行评估、遗传操作、选择、经多代繁殖，获得适应值 最好的个体作为问题的最优解。是进化计算的主要框架之一。 1 2 1 标准遗传算法的组成 1 标准遗传算法的组织结构及算法描述 标准遗传算法( s g a ) 6 , 7 , 1 3 , 1 4 , 1 7 】使用选择( s e l e c t i o n ) 算子、交叉( c r o s s 0 v e r ) 算子和变异 ( m u t a t i o n ) 算子，它们使遗传算法具有了与其它传统方法所不同的特性。遗传算法中包 含了如下5 个基本要素： ( 1 ) 编码方案； ( 2 ) 初始群体的设定； ( 3 ) 适应值函数的设计； ( 4 ) 控制参数设定； ( 5 ) 遗传操作设计。 这5 个要素构成了遗传算法的核心内容。标准遗传算子可定义为一个八元组： s g a = d ，f ，p o ，n ，s ，m ，c ，t )( 1 2 1 ) 其中d 一个体的编码方式； p o 一初始群体； s 一选择算子； c 一交叉算子； f 一个体的适应值评价函数； n 一种群规模； m 一变异算子； t 一搜索终止条件 1 0 第一章共轭梯度法和标准遗传算法基本理论 图1 2 1 遗传算法的主要阶段 f i g 1 2 1t h ep r i m a r yp h a s e so fg e n e t i ca l g o r i t h m m 2 标准遗传算法的编码 s g a 采用二进制编码【6 】，将问题的解用一个0 - 1 字符串表示，如采用长度为珀勺二 进制串s 来表示扣，b 】区间内的变量x ，则 r c l x - a + 黝一口) ( 1 2 2 ) 二一l d ej o n g 依据模式定理( 定理1 2 1 ) ，提出编码准则： 1 、积木块规则：编码应当易于生成与所求问题相关的短距和低阶的积木块。 2 、最小字符集规则：编码应采用最小字符集以使问题得到自然的表示和描述。 主要的编码方法有：二进制编码、g r a y 编码、浮点数编码、多参数级联编码、多参数 交叉编码。编码的评估策略：完备性、健全性、非冗余性。 3 适应值( f i t n e s s ) 函数 适应值函数f 7 】也称评价函数，是根据目标函数确定的用于区分群体中个体好坏的标 准，生物体对环境的适应程度的不同而表现出不同的生命力。衡量字符串好坏的指标是 适应值函数，它是遗传算法的动力，也是g a 的目标函数。遗传算法对适应值函数的唯 一要求是，该函数不能为负。每个个体对应于优化问题的一个解x i ，每个解x ；对应于一 福建师范大学薛凌霄硕士学位论文 个函数值正。五越大，则表明t 越好，即对环境的适应值越高，所以可以用每个个体的 函数值疋作为它对环境的适应值。任何情况下都希望其值越大越好。 适应值函数的设计主要满足以下条件： ( 1 ) 单值、连续、非负、最大化。 ( 2 ) 合理、一致性。 ( 3 ) 计算量小 ( 4 ) 通用性强。 在遗传算法的不同阶段，还需要对个体适应值进行适当的扩大或缩小，成为适应值 的尺度变换，主要有几种调整方式f 7 】： ( 1 ) 线性调整 原适应值平均值要等于调整后的适应值平均值。 调整后适应值函数的最大值乙o ) 要等于原适应函数平均值的所指定的倍数。 即 ，懈 ) - c l 喀 ) ( 1 2 3 ) 其中c 为得到所期待的最优个体的复制数。不太大的群体可取c 为 1 2 2 0 ( 2 ) 幂调整 定义为 ， ) = 厂2 0 )( 1 2 4 ) 其中k 与待求解问题有关，在算法中可做修正。 4 遗传算子( g e n e t i co p e r a t o r ) ，7 l 定义1 2 1 【选择( s e l e c t i o n ) 算子】选择算子即从上一代种群中选择一定量染色体到新一代 种群的选择方法，选择算子的目的是为了避免基因缺失，提高遗传算法的全局收敛性和 搜索效率。选择算子的形式有很多种，不同的选择算子有不同的性质和适应范围。 定义1 2 2 【交叉( c r o s s o v e r ) 算子】交叉算子是遗传算法区别于其他进化算法的重要特 征，非常重要，是产生新个体的主要方法。一方面，它使得在原来的群体中的优良个体 的特性能够在一定程度上保持；另一方面，它使得算法能够探索新的基因空间，从而使 新的群体中的个体具有多样性。 交叉算子的设计和实现与所研究问题密切相关，交叉是随机对基因串中的染色体进 行随机配对，然后再配对染色体中随机选择交换位进行交叉。交叉的目的是为了产生适 应值更高的染色体，从而使后代优化。通常交叉的方式组合出新个体，在串空间进行有 效搜索，同时降低对有效模式的破坏概率。 1 2 第一章共轭梯度法和标准遗传算法基本理论 交叉算子的基本操作分两个步骤进行，首先将种群中个体进行两两配对，然后进行 交叉操作，产生一个或多个新个体。这些新个体组成新种群。一般有单点交叉和多点交 叉。 本文的混合算法采用的是多点交叉。首先随机确定多个交叉位置，然后对换相应的 子串。 定义1 2 3 【变异( m u t a t i o n ) 算子】变异算子的主要目的是使遗传算法有局部的随机搜索 能力，而且可使遗传算法维持群体的多样性，防止“早熟”现象。 遗传算法中，交叉算子因其全局搜索能力作为主要算子，变异算子因局部搜索能力 作为辅助算子。当产生的后代并不比前代优秀且又未达到可行性解，就会产生不成熟的 收敛。为了避免出现这种情况，只有依赖变异。变异的过程通常是在一定概率下进行， 而且只变动染色体中某一个或几个基因。变异算子也是产生新个体的辅助方法，决定 g a 的局部搜索能力。交叉和变异互相配合共同完成搜索空间的全局搜索和局部搜索。 变异操作是施加于种群内每个个体之上的，这一点就像施加于向量或者短阵上的点 运算一样。 1 2 2 标准遗传算法的重要知识 1 进化参数 遗传算法在搜索空间中进行高效的启发式搜索，算法的性能由深度搜索( e x p l o i t a t i o n ) 和广度搜索( e x p l o r a t i o n ) 的平衡性决定。而平衡性又取决于种群规模、最大进化代数、编 码长度、交叉概率、变异概率等参数，因此，这些进化参数的设置对于整个遗传算法的 搜索性能起