（系统理论专业论文）基于光学原理的最优搜索方法研究.pdf

哈尔滨t 程大学硕+ 学位论文 摘要 随着应用领域的拓展，最优化问题的时空复杂性使其求解非常困难，传 统的优化算法己很难满足问题需要。智能优化算法的诞生给最优化技术提供 了新的思路和手段，并在科学研究、经济及工程技术问题中得到广泛应用和 发展。 光线寻优算法是2 0 0 8 年提出的一种通过对自然界光线折射现象的模拟 而进行寻优的优化算法。本文详细地介绍了它的基本原理和算法流程。通过 数值实验对固定网格的光线寻优算法进行了参数分析，并且做了相应的算法 改进，提出变网格的光线寻优算法，改进原有算法的不足。本文主要研究内 容可归纳为： 1 详细分析光线寻优算法中蕴含的最优化理论的数学思想以及光线寻优算法 的基本原理、计算步骤。数值实验表明，光线寻优算法简单易行，并可在大 范围内较快地搜索到极值点。阐明了算法中重要参数对算法性能的影响。 2 。通过系列的数值实验，给出了光线寻优算法参数选择的合理建议。为研究 本文算法性能，在4 个具有代表性的基准测试函数上，进行了算法的数值实 验。并且针对参数网格步长的大小提出变网格的光线寻优算法，通过系列数 值实验表明，网格的等比递减和等差递减这两种改进算法能有效地提高算法 局部搜索能力，从而很大程度地改善算法性能。 3 针对目标函数值域只能恒正的局限，提出了大m 参数法，来解决这一问题， 从而研究改进算法性能。在3 个具有代表性的测试函数上，进行了算法的数 值实验。实验结果显示，大m 参数法使得光线寻优算法突破目标函数值域只 能恒正的局限。 关键词：优化算法；光线寻优算法；光学折射原理；变网格；大m 法； 哈尔滨下稃大学硕士学何论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fa p p l i e df i e l d s ，o p t i m i z a t i o no ft h ep r o b l e mi sv e r y d i f f i c u l tt os o l v ei nt e m p o r a la n ds p a t i a lc o m p l e x i t y , t h et r a d i t i o n a lo p t i m i z a t i o n a l g o r i t h mh a sb e e nd i 伍c u l tt om e e tt h er e q u i r e m e n t b u ti n t e l l i g e n to p t i m i z a t i o n a l g o r i t h mi san e ww a y ，i tp r o v i d e sn e wm e a n st o b eu s e d e c o n o m i ca n d t e c h n i c a la s p e c t so ft h ep r o j e c ti sw i d e l ya p p l i e da n dd e v e l o p e d p r o f e s s o rp r o p o s e san e wo p t i m i z a t i o na l g o r i t h m - l i g h tr a yo p t i m i z a t i o n , w h i c hs t i m u l a t e st h en a t u r a lp h e n o m e n o no fl i g h tr e f r a c t i o n t h e r ea r et h eb a s i c t h e o r y a n da l g o r i t h ms t e p so ft h el i g h tr a yo p t i m i z a t i o n i nt h i s p a p e r p a r a m e t e r so fl r oa r ea n a l y s e db yn u m e r i c a le x p e r i m e n t so nt h ef i x e dg r i dl i g h t r a yo p t i m i z a t i o n ，a n d t h ea l g o r i t h mi s i m p r o v e d v a r i a b l eg r i dl i g h tr a y o p t i m i z a t i o ni sp r o p o s e d ，i ti so v e r c o m e df o rd i s a d v a n t a g eo f t h ef i x e dg r i dl i g h t r a yo p t i m i z a t i o n t h em a i nw o r k sg i v e ni nt h e d i s s e r t a t i o na r ea sf o l l o w s 1 t h el i g h tr a yo p t i m i z i o ni sd e t a i l e d l ya n a l y s e d ，a n dt h em a t h e m a t i c a li d e ai n t h ea l g o r i t h mi si n t r o d u c e d t h eb a s i cp r i n c i p l e so fa l g o r i t h mc a l c u l a t i o ns t e p sa r e a l s oi n t r o d u c e d t h ef e a s i b i l i t yo fa l g o r i t h mi sv e r i f i e db yn u m e r i c a le x p e r i m e n t n u m e r i c a le x p e r i m e n t ss h o wt h a tl i g h tr a yo p t i m i z a t i o ni ss i m p l e ，a n di nt h e l a r g es c o p eo ft h es e a r c hq u i c k l yt ot h ee x t r e m ep o i n t s w ee x p o u n d t h ei n f l u e n c e o fi m p o r t a n tp a r a m e t e r st ot h ea l g o r i t h mp e r f o r m a n c eo fa l g o r i t h m sp r e s e n t e di n t h ed i s s e r t a t i o n 2 w e g i v e r e a s o n a b l es u g g e s t i o nt ot h ec h o o s i n go ft h ep a r a m e t e r si n t h e a l g o r i t h mb ys e r i e so fn u m e r i c a le x p e r i m e n t s i no r d e rt os t u d yt h ep e r f o r m a n c e o ft h ea l g o r i t h m s ，w ed i ds e r i e so fn u m e r i c a le x p e r i m e n t so nf i v er e p r e s e n t a t i v e b e n c h m a r kf u n c t i o n s g r i ds i z eo fl i g h tr a yo p t i m i z a t i o ni sv a r i a b l e ，t h ev a r i a b l e g r i dl i g h tr a yo p t i m i z a t i o ni sp r o p o s e d t h ed e c e n d i n gg r i di sc l a s s i f i e di n t o a l i n e a rt r e n do fd e c e n d i n ga n dn o n 1 i n e a ro fd e c e n d i n g ，t h ed e c e n d i n gt r e n d so f t h e t w om a t hi t e r a t i v ef o r m u l a sa r eg i v e n t h r o u g hc o m p a r i n gt w om e t h o d s i n 哈尔滨t 捍大学硕+ 学位论文 a r eg i v e n t h r o u g hc o m p a r i n gt w om e t h o d si nn u m e r i c a le x p e r i m e n t s ，a l g o r i t h m o f 鲥do fg e o m e t r i cd e s c e n d i n ga n da r i t h m e t i cd e s c e n d i n gg e n e r a t eb e t t e r n u m e r i c a lr e s u l t s a l g o r i t h m sc a ne f f e c t i v e l ye n h a n c el o c a ls e a r c hc a p a b i l i t y , t h u s i m p r o v ea l g o r i t h mp e r f o r m a n c eg r e a t l y 3 t h e o b j e c t i v e f u n c t i o nv a l u ec a l l o n l yb eap o s i t i v en u m b e r al a r g em p a r a m e t e rm e t h o di sp r o p o s e dt os o l v et h i sp r o b l e m w ed i ds e r i e so fn u m e r i c a l e x p e r i m e n t sw i t ht h ei m p r o v e da l g o r i t h mo nt h r e eb e n c h m a r kf u n c t i o n s t h e e x p e r i m e n m lr e s u l t ss h o wt h a t ，t h ep r o b l e mo fc o n s t a n tf o rt h ep o s i t i v ei ss o l v e d b yt h i si m p r o v e da l g o r i t h m k e y w o r d s ：o p t i m i z a t i o na l g o r i t h m ；l i g h tr a yo p t i m i z i o n ；p r i n c i p l eo f r e f r a c t i o n ；v a r i a b l eg r i d ；b i gmm e t h o d 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。、 作者( 签字) ：绑g 必 日期： 、，年石月穆日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：搬 - , - - 9 p i t i ( 签字) ：沟i 主 日期：矽习年6 月，矿日d 一夕年6 剧泊 哈尔滨t 稃大学硕十学位论文 1 1 引言 1 1 1 研究背景 第1 章绪论 随着科学技术的飞速发展，最优化理论与算法在人们社会活动中发挥了 重要的作用，它研究的问题是讨论在众多的被选方案中采用什么样的方案最 优以及如何用恰当的方法找到最优方案或计算最优解的问题。计算智能是借 助现代计算工具模拟自然界某些现象来求解问题的方法和理论。经过学者们 的努力探讨，人们在一些大自然的生命现象和物理现象中得到启发，提出了 一些新颖的优化算法。而且，这些算法在各种实际问题中得到了广泛应用并 发展迅速。例如粒子群优化算法是由鸟群、鱼群觅食过程得到的启发而提出 的一种群智能优化算法，遗传算法是模拟生物遗传变异机制，人工神经网络 ( a n n ) 在一定程度上模拟了人脑的组织结构。因此，追求更高效的优化算 法成为科学工作者的研究目标之一。 本文研究的光线寻优算法( l i g h tr a yo p t i m i z a t i o n ，简称l r o ) 是匿名教 授提出的一种智能优化算法。 1 1 2 课题意义 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、 遗传算法、模拟退火、禁忌搜索、蚁群算法及其混合优化策略等，通过模拟 或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、 生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了 新的思路和手段。这些算法独特的优点和机制，引起了国内外学者的广泛重 视并掀起了该领域的研究热潮，且在诸多领域得到了成功应用。因此智能算 法在优化领域的研究日趋活跃。 智能算法的实用性表现在：对判断是否能够求解优化问题的前提条件的 要求很低，智能算法比传统算法能在更多的情况下能够求得有用的( 即近似 哈尔滨t 程大学硕十学位论文 的、次优的和在精度许可范围内的) 优化解。智能算法的通用性是指：通过策 略、参数、操作以及算子的调整，能够更广泛地适应不同领域的优化求解问 题，尤其是对多目标、大规模、高维数、非线性以及带有不可转化约束条件 的复杂优化问题，具有更强的适应性。智能算法的灵活性是指：通过策略、参 数、操作以及算子的短时间的调整，能够很快提高寻优求解的性能( 效率和质 量) ：更重要的是智能算法能够通过自身的改良以及同其它方法的交叉融合， 在不长的时间内快速“进化”，这一点是智能算法仿生、仿自然的内在特性。 然而为了解决更复杂的优化问题，现有的求解算法在求解效率上存在着这样 或那样的不足，因此对智能算法进一步研究是非常必要和紧迫的。基于这个 迫切的需求，本文对基于光学折射原理的光线寻优算法进行了深入的分析和 研究。 1 2 国内外研究现状 大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启 发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些 受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们 常常称之为启发式算法。启发式算法有不同的定义：一种定义为，一个基于 直观或经验的构造的算法，对优化问题的实例能在可接受的计算成本( 计算 时间、占用空间等) 内，给出一个近似最优解，该近似解与真实最优解的偏 离程度不一定可以事先预计；另一种是，启发式算法是一种技术，这种技术 使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解 和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 1 2 1 几种常见的启发式算法 下面介绍几种常见的启发式算法。 1 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟达尔文的遗传选择和自然 淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解 的方法，它是有美国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 ni 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 2 哈尔滨。1 i 程人学硕十学位论文 这个名称爿逐渐为人所知，j h o l l a n d 教授所提出的g a 通常为简单遗传算法 ( s g a ) 。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群 则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特 征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表 现( 即基因型) 是某种基因组合，它决定了个体的形状的外部表现，如黑头 发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开 始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作 很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者 生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根 据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进 行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自 然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经 过解码，可以作为问题近似最优解。 与传统优化算法不同，遗传算法不依赖于问题的梯度信息，而是通过模 拟自然进化过程来搜索最优解。遗传算法以群体为基础( 不是以单点搜索为基 础) ，能同时从不同点获得多个极值，因此该方法不易陷入局部最优；由于遗 传算法是对问题变量的编码集进行操作，而不是问题变量本身，这样可以有 效地避免了对变量的微分操作运算。遗传算法只是利用目标函数来区别群体 中个体性能好坏而不必对其进行过多的附加操作。而大多数古典优化算法是 基于一个单一度量函数( 评估函数) 的梯度或较高次统计，以产生一个确定 性的试验解序列。由于遗传算法的本质特点，使得遗传算法能够解决复杂问 题的优化求解，例如非线性约束计算问题。此外，遗传算法具有并行特点， 能同时在多个处理器上进行并行计算，并且各子种群之间可以按照一定的规 则交换个体，避免早熟现象和增加解的 尽管遗传算法有其优点和特点，但其使用过程中仍然存在许多问题与不 足，主要在于： ( 1 ) 适应度标定方法多种多样，无简洁通用方法。 ( 2 ) 遗传算法的早熟现象到目前为止仍是难以处理的问题。 ( 3 ) 接近最优解时存在左右摇摆，收敛较慢。 哈尔滨i ：程人学硕十学位论文 ( 4 ) 运行速度较传统方法缓慢。 2 神经网络算法( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 是一种模仿动物 神经网络行为特征进行分布式并行信息处理的算法数学模型。这种网络依靠 系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处 理信息的目的。人工神经网络具有自学习和自适应的能力，可以通过预先提 供的一批相互对应的输入一输出数据，分析掌握两者之间潜在的规律，最终 根据这些规律，用新的输入数据来推算输出结果。 人工神经网络特有的非线性适应性信息处理能力，克服了传统人工智能 方法对于直觉，如模式、语音识别、非结构化信息处理方面的缺陷，使之在 神经专家系统、模式识别、智能控制、组合优化、预测等领域得到成功应用。 人工神经网络与其它传统方法相结合，将推动人工智能和信息处理技术不断 发展。近年来，人工神经网络j 下向模拟人类认知的道路上更加深入发展，与 模糊系统、遗传算法、进化机制等结合，形成计算智能，成为人工智能的一 个重要方向，将在实际应用中得到发展。将信息几何应用于人工神经网络的 研究，为人工神经网络的理论研究开辟了新的途径。神经计算机的研究发展 很快，已有产品进入市场。光电结合的神经计算机为人工神经网络的发展提 供了良好条件。 3 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，又称蚂蚁算法，是一 种用来在图中寻找优化路径的机率型技术。它由m a r c od o r i g o 于1 9 9 2 年在 他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正 反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。蚁群算法是从真 实蚁群的觅食行为中受到启发而发展起来的一种新型的模拟进化算法，具有 并行运算的特点，所有“蚂蚁”独立行动，没有监督机构。人工蚂蚁通过间 接通讯、相互协作来寻找问题的最优解；目前，该算法在组合优化、函数优化、 机器人路径规划、数据挖掘等领域的应用己显示出其求解复杂优化问题的优 势。 蚁群算法具有以下一些特点： ( 1 ) 系统性。作为系统元素的蚂蚁是相异的个体，算法每次循环它们都各自 独立完成一次搜索过程体现了系统的多元性；蚂蚁之间通过信息素相互联系、 4 哈尔滨。i ：程人学硕十学佗论文 传递经验进而指导搜索的行为体现了系统的相关性：而由多只蚂蚁组成的蚁 群的搜索性能明显优于单只蚂蚁也反映了整体大于部分之和这一系统的整体 性。因为蚁群算法的系统性因而适一于求解系统问题。 ( 2 ) 分布式计算。多只蚂蚁在问题空间的多点同时独立地进行搜索，问题的 求解不会因为部分个体的缺陷而受到影响，算法不仅具有了较强的全局搜索 能力，也增强了可靠性。 ( 3 ) 自组织性。系统论中的自组织行为是指系统在获得时间的、空间的或者 功能的结构过程中没有受到外界的特定干扰，其组织力或组织指令来自于系 统内部。抽象来说，自组织就是在没有外界作用下使得系统嫡增加的过程， 也就是系统从无序到有序的进化过程。蚁群算法的寻优过程恰恰体现了这种 自组织性，而自组织性也大大增强了算法的鲁棒性。 ( 4 ) 正反馈。控制论中正反馈指的是以现在的行为去加强未来的行为，蚁群 算法是通过信息素的不断更新来实现正反馈的，将反映当前局部最优解特性 的参数作为增量来提高这些解的构成元素上的信息素浓度，使得更多的蚂蚁 有机会选择这些元素去构建更好的解。便于利用问题的启发信息更快找到更 优的解。 二十世纪九十年代早期，蚁群算法作为一种求解复杂组合优化问题的算 法被提出随后迅速引起人们的关注，其应用领域已拓展到旅行商问题、车间 调度问题、车辆路线问题、图着色问题、有序排列问题、网络路由问题、管 线敷设问题等多种组合优化问题。蚁群算法的特点使得它在理论上比其它算 法求解单机调度问题时有更大的优越性，但在实际应用中蚁群算法面临一些 问题，概括起来就是：运算时间较长，容易陷入局部极小，参数选取过程比较 复杂，算法的智能化程度( 即自适应能力) 较低等。 4 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由k e n n e d y 博 士和e b e r h a r t 博士提出的一种基于群智能方法的算法。该算法首先于1 9 9 5 年提出。粒子群优化算法是基于群体的演化算法，p s o 即源于对鸟群觅食行 为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找 到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从这样的模型中得到启示而产生的。p s o 从这种模型中得到启示并 用于解决优化问题。p s o 中，每个优化问题的解都是搜索空问中的一只鸟。 哈尔滨t 程大学硕七学何论文 我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值 ( f it n e s sv a l u e ) ，每个粒子还有一个速度决定他们飞翔的方向和距离。然后 粒子们就追随当前的最优粒子在解空间中搜索。与其它进化算法类似，p s o 算法通过个体间的协作与竞争，实现复杂空间的搜索能力。算法中表示问题 潜在解的集合称为种群，种群的个体称为粒子，表示问题的一个可行解。用 速度和位置来描述粒子，并用目标函数确定粒子的适应度( f i t n e s sv a l u e ) 。 在每一代中粒子通过追踪两个极值，一个是粒子自身迄今找到的最优值 p b e s t ，一个是种群迄今找到的最优值g b e s t 。这样粒子追随当前最优粒子，逐 步迭代( 进化) ，实现强大的搜索能力。 粒子群算法自提出以来，由于其在解决复杂的组合优化类问题方面所具 有的优越性能，在诸如工程设计与优化、机器人设计与控制、工业生产优化 等取得了成功的应用。但是由于目前p s o 算法存在早熟收敛和晚期收敛较慢 的问题，仍然使得粒子群算法在许多应用中受到诸多限制。 1 3 本文的主要工作及内容安排 1 3 1 主要工作 根据本文提出的问题，对光线寻优算法进行了较深入的研究。本文将主 要进行以下几方面的工作： 1 介绍光线寻优算法理论依据和算法的主要原理，并且对现有研究成果加以 总结，并根据数值实验详细分析了算法的参数性质。 2 对算法的参数设置问题进行了深入的研究。特别是初始点，初始方向，网 格大小等参数设置进行详细分析，描述了对算法影响的重要参数。 3 提出变网格的光学寻优算法，并在此基础上，通过与一些著名基准测试函数 的对比实验，分析了本文算法的性能。 4 通过数值实验分析了光线寻优算法在求解最优化值为负值的优化问题时， 研究采用大m 法的可行性。 6 哈尔滨1 二程人学硕十学何论文 1 3 2 内容安排 第l 章简要介绍了光线寻优算法，说明了课题的研究背景与意义以及论 文的主要工作，群智能算法的一些知识。 第2 章介绍与光线寻优算法研究的相关内容的国内外研究现状及相应的 优化基础知识，介绍了相关的光学原理，阐明光线寻优算法原理和流程。 第3 章通过数值实验，给出合理参数选择的建议并通过一些经典测试函 数的对比实验，分析本文算法的性能，同时分析l r o 算法中的参数设置等相 关问题。 第4 章研究基于光线寻优算法，提出变网格的光线寻优算法，通过在一 些著名基准测试函数上的对比实验分析了改进算法的性能。 第5 章针对一般函数将其转化为大m 问题，并提出解决问题的一般方法。 最后，对全文工作进行了总结并且对光线寻优算法的研究前景加以阐述。 7 哈尔滨t 程大学硕十学何论文 第2 章光线寻优算法简介 2 1 光学基本原理简介 2 1 1 费马原理 1 6 5 7 年，费马提出的这个原理概括了光线的传播所遵循的规律。原理表 述为：在a 、b 两点间光线传播的实际路径，与任何其它可能路径相比，其光 程为极值。即在两点之间光沿着所需时间为极值的路径传播。 讨论费马原理前，须先引入一个概念一光程。光程可表述为：在均匀介 质中，光程l 为光在介质中通过的几何路程，与该介质折射率玎的乘积，即 l = 疗， 而光线在介质中传播时间为 ltn 卑l t = 一2 了2 y c 式中刀为介质折射率，c 为真空中的光速，1 ，为光在介质中的传播速度，我们 定义介质折射率与光经过的几何路程的乘积为光程，并记作，则光程可表 示为： l = 玎木，= c 宰f 上式表明光在某种介质中经过一段几何路程1 所对应的光程，等于在相 同的时间内光在真空中经过的几何路程。若光经过几种不同的介质，则光程 为 l = 碍厶+ n 2 1 2 + 一 如果介质的折射率连续变化，则上述求和变为积分 & l = i n d l a 费马指出：光在指定的两点间传播，实际的光程总是一个极值，也就是 说，光沿光程值为最小、最大或恒定的路程的传播，这就是几何光学中的一 8 哈尔滨f ：稃大学硕十学何论文 个基本原理费马原理，其数学表达式如下： f ：即d ，= 极值( 极小值、极大值或恒定值) j 。 由于光从a 点传播到b 点这段路程l 所需要的时间t ，与该路段相应的 光程l 有简单的比例关系： r = l c( c 为真空中的光速) 上两式是费马原理的数学表达式，可以理解为：光从空间的一点传到另一点 是沿着光程为极值的路径传播，也就是说是光沿着光程为最小、最大或常数 的路径传播。这是一个非常有趣而极奇妙的现象，光从一点出发到达另一点， 它自己会事先计算出沿哪一条路径所花的时间是最短，可以想象光的“计算” 速度是何等之快，因为我们现在知道光的传播速度已经是足够快的了。在一 般情况下，实际光程大多是取极小值，费马本人最初提出的也是最短光程。 根据直线是两点间最短距离这一几何公理，从费马原理可以证明：光通过两 种不同介质的分界面时，所遵从的折射定律也是费马原理的必然结果。 2 1 2 光学折射原理 设两均匀介质的分界面是平面，它们的折射率分别为碍和n ：。光线通过 第一介质中指定的a 点后经过界面而达到第二介质中指定的b 点。为了要确 定实际光线的路径，通过a 、b 两点作平面垂直于界面，0 0 是它们的交线( 图 2 1 ) ，则实际光线在界面上的折射点c 就可用费马原理来确定。 y 图2 1 光线的折射 9 哈尔滨：1 ：程大学硕十学何论文 首先根据费马原理，可以确定折射点c 点必在交线o o 7 上，首先根据费 马原理，可以确定折射点c 点必在交线0 0 上，这是因为，如果有另一点c 位于线外，则对应于c ，必可在0 0 线上找到它的垂足c ”。由于 a c a c , c b c ”b ，故光程( a c b ) 总是大于光程( a c ”b ) 而非极小值， 这就证明了入射面和折射面在同一平面内。 其次再来确定c 点在0 0 上的位置，在图2 1 中，作z ，y 坐标轴。指 定点a 、b 的坐标分别为( _ ，y i ) 和( x ：，y 2 ) ，未知点c 的坐标为( x ，0 ) 。c 点 在a 、b 之间时，光程必小于c 点在a b 以外的相应光程，即x l x o 。 ( i ) 光线垂直方向折射情况，如图2 5 哈尔滨t 程大学硕十学位论文 m ( x o ，y 。 i 卵厶 尸c m ( 五，乃) 卢1 图2 5 光线垂直方向折射情况 为入射角，当光线从m o 点出发沿方向p o 射到水平线厶上，交点为 必。( 五，乃) ，显然有结论z ( m 。) s i n a , ，说明搜索方向在偏向于最优 值点。 ( i i ) 光线水平方向折射情况，如图2 6 光线从m o 点出发沿方向p 射到水平线岛上，交点为m ( 而，乃) ，显然 有结论z ( m i ) s i n a , ，说明搜索方向在偏向于最优值 点。 1 6 哈尔滨下程大学硕士学位论文 厶m ( x o ，懿) 口。 埘( 而，m )石矗 ok：i f 图2 6 光线水平方向折射情况 更进一步说明利用光学折射原理进行局部极小值的搜索过程。假设x 是 函数f ( x ) 的局部极小值点，选取x ( o 为初始向量。显然，如果我们能够选 取搜索方向p 0 = x 。一x ，则很自然搜索到局部极小值点z 。但是，般 我们选取的搜索方向p o x 一x ，搜索方向偏离极小值点x 。我们可以 在x 与x + 中间设置一个临界面三，将平面分成两部分。将这两部分看成是 两种介质，光线在这两种介质中传播的速度不同，下平面的速度小于上平面 的速度。在图2 7 中，如果一束光线从x ( 出发，沿着方向p ( o 走会出现什 么结果呢? 按照光线的折射定律，由于上下两种介质不同，光线在临界面上 产生折射。从图中我们容易看出，从水平的角度讲，折射产生的搜索点x ( ：比 沿原方向p ( o 产生的搜索点x ( 1 更靠近极小值点x 。 哈尔滨t 稃火学硕十学位论文 x c o ) - q z c 2 ix c l ) 图2 7 搜索方向更迭 为了使折射产生的搜索点x ( 2 更加靠近极小值点x ，我们可以更多的设 置临界面。，将平面划分成充满多种介质的区域。如果函数厂( x ) 具有沿垂 直方向向下下降的趋势，在图2 8 中我们看到，x ( 3 比x ( 2 更接近极小值点 x 。一般地，划分的区域越多，则经过第f 次折射得到的搜索点x ( 将越靠 近x 。 z c o ) - q 沁 ? 氕 x z c 3 ix c 2 iz c l ) 图2 8 搜索方向的更迭 1 8 哈尔滨t 程大学硕十学位论文 可能会出现另外一种情形，就是初始方向p c o 的选择不当而使每次折射 的搜索点x 离极小值点x 越来越远，如图2 9 所示： z o z c l ) z ( 2 l l 弋。 | 3 一x 1 图2 9 垂直搜索方向远离最优点 但是在图2 1 0 中，如果函数f ( x ) 沿水平方向也有越来越小的趋势，我 们设置竖直的临界线，然后按照折射原理搜索，生成的x ( 。离极小值点x 越 来越近。 z o ) x 图2 1 0 水平搜索方向远离最有点 1 9 哈尔滨一f ：程大学硕十学何论文 因此，真，l l 我l j 分平面需要用水平和竖直线，也就是说，将平面划分称矩 形网格，每个矩形区域中充满某种介质，这种介质的光速以来于在这个矩形 域的目标函数值。依据上面的演示过程，只要矩形网格比较密，搜索方向将 会是沿竖直和水平方向不定期的交换次序，则经过水平和竖直方向的不断调 整，通过光线的折射原理生成的点x ( ，将向极小值点z 靠拢。如下图2 1 1 、一 i 、 s 疆! 图2 1 1 搜索方向的更迭 2 3 光线寻优算法具体流程 允为表示步长，p 表示方向，s 停止迭代的阈值 第一步设置初始方向r ，初始点k ，精度s ，网格大小。 第二步沿方向昂前进，当达到方块边界时，计算该点五的数值彳。 第三步彳与五做对比，是否满足停止条件。 第四步根据折射原理，按公式罢：粤得出下一次折射的方向0 。 s i n q + i，“l 第五步如此循环下去，直到满足迭代停止条件。如图2 1 2 2 0 哈尔滨t 挥大学硕十学位论文 图2 1 2 光线寻优算法流程图 2 4 算法简单数值验证 针对上叙述的算法，验证其可行性。例如最优化问题 r a i n f ( x ，y ) = x 2 + y 2 ，( x ，y ) r 2 进行求解。选取初值及初始方向，网格长度的1 1 0 0 0 ，宽度为1 1 0 0 0 = ( y ) = ( - 1 0 , 1 2 3 ) ，= ( 而1 ，一而1 0 ) 选取水平步长办2 斋l _ ，纵向步长r2 斋矗，最终我们得到搜索的极小值点 2 l 兰尘鋈i ；至尘耋2 ：簦兰銮 y , j ( 一10 2 5 9 1 0 。3 ，5 0 4 5 l o 。) ，结果如图2 1 3 d a t a l i ，= 二谨1 、 簟、 、 1 0987，6543- 2i0 图2 1 3 测试函数的寻优路径 25 光线寻优算法的优势 光线寻优算法是由光线折射原理启发而提出的一种智能的优化算法，在 优化领域有很好优越性。 1 浚算法和其他群智能算法不同之处在于算法无需通过大量粒子随机 性来保证优化结果的精确性。 2 算法运行无需任何导数信息，只需目标函数值，具有很强的通用性。 3 算法原i 哩简单，程序易实现，比其他智能算法操作更方便。 冈而，改进算法性能、拓宽算法应用领域、完善算法体系对l r o 这种新 算法的发展具有重要作用。所以，对光线优化算法的研究是一个同时具有理 论意义和应用价值的重要课题。 首先，光线寻优算法，虽然形式简单易于实现，但是，该算法的收敛情 况与各参数的耿值有着密切关系，如何选取合适的参数仍然是一个亟待解决 的问题。 其次，光线寻优算法应用时，常常会出现陷于收敛的局部极小点问题， 哈尔滨i ：程大学硕十学何论文 也就是算法在没有找到全局最优点时光线停止折射现象。这些收敛点，可能 是局部极小点，也可能是局部极小点邻域内的点。研究收敛问题可为改进算 法设计奠定基础。 针对上述问题，本文做了细致的研究，提出了算法的改进方案，并做了 大量的数值实验分析，详细分析了改进算法参数选择的问题以及算法性能。 2 6 本章小节 本节详细介绍了光线寻优算法的基本原理以及算法的具体流程。 哈尔滨t 程人学硕+ 学位论文 第3 章算法参数设置 3 1 参数设置的理论分析 3 1 1 初始点和初始方向与最优点的关系 初始点的选取，不宜过于靠近最优点，这样会造成算法过早收敛；初始 点过于远离最优点会对算法的收敛速度造成影响，可能陷于局部最优值，无 法达到全局最优点。 由算法的流程图可知，如果下一次迭代的函数值大于本次函数值，算法 停止迭代。如果初始方向背离最优点方向，无疑将加大算法运算的时间，带 来不必要的麻烦。一般情况下选取初始点与最优点连线方向9 0 度范围内的初 始方向。如图3 1 初始点 。 l 7 吵 初始方向的 选择范围 。一一 最优点 v 图3 1 初始点与初始方向的关系 3 1 2 网格大小对算法收敛速度的影响 大的网格，有利于算法在寻优过程中不易陷入局部最优点，并且大大加 快搜索的速度；而小的网格，由于搜索方向的充分调整，可以得到比较精确 哈尔滨：1 ：程大学硕十学位论文 的结果，但是以牺牲搜索速度为代价的。而这也是为第五章提出变网格光线 的寻优算法提供了依据。 3 2 数值实验 3 2 1 基准测试函数 就函数优化而言，目前文献中常用的b p 胛f 办所口以测试函数大约有2 0 多种。 本文作者综合其他优化算法的文献，选择了该领域常用的几个著名的基准测 试函数。对于每个基准测试函数，优化的目标是求它们的全局最小值。基准 函数的标准形式如下： 对于给定的函数f ：r ”。r ，寻找x r ”，使得 f ( x + ) 厂( x ) ，v x r ” 本文用于测试算法性能的函数分别为： ( 1 ) s p h e r e 函数( 也称p a r a b o l a 函数) 厂( x ) = x j z ( 3 一1 ) f - - | 连续单模态函数，全局最优点x = ( 0 ，0 ，0 ) 7 ，最优值f ( x 。) = 0 。 其三维函数图像如图3 2 所示。 竺尘鋈矍查：翌土兰竺鎏兰 o 5 图32s p h e r e 函数三维图像 ( 2 ) r o s e n b r o c k 函数( 也称d e j o n g f 2 函数) ，( x ) = ( ( x 。一z + ( 一1 ) 2 ) ( 32 ) o l 连续单模态函数一全局最优点x = ( 1 ，l ，1 ) 7 ，最优值f ( x ) = 0 。从其 i 维图像图33 可以看出其极值点隐藏在一道狭长的细谷中，因此寻优 相当刚难。 蜘 柏 加 o o 堕垒鎏；! 堡查耋些圭兰堡篁兰 i r 砧r 、，。，。，j 。f m | j “哪 图3 3r o s e n b r o c k 函数 ( 3 ) r a s t r i g r i n 函数 ，( x ) ：主( x 卜l o c o s ( 2 m ：, ) + 1 0 ) 2 ( 3 - 3 ) 连续多模态函数，有很多f 弦凸起的局部极小点，各变量相互独立。全局最 优点z ：( 0 ，o ，0 ) 7 ，最优值，( x ) =