光线寻优算法的研究及改进

优化问题大量存在于科学研究和工程应用中的各个领域，优化对象在复杂化和规模化等方面不断提高。以生物智能或自然现象为基础的智能算法因其具有简单通用、鲁棒性好、适于并行处理等特点，因此成为解决大规模复杂优化问题的有力工具。 基于费马原理，一种新型的智能优化算法——光线寻优算法被提出，它通过模拟光在变折射率介质中的传播过程进行寻优，为智能计算用于解决最优化问题提供了新思路。算法主要针对全局最优值不易搜索的难题，具有不涉及随机因素、可调参数少、结构简单、容易实现等优点。光线寻优算法首先用矩形网格划分搜索区域，并将每一网格填充进具有不同折射率的介质，即光线传播速度取为网格中心点所对应的目标函数值；然后将搜索路径设想为光的传播路径，并且认为光仅在各网格的边界上发生折射和反射，在各网格内部沿直线传播。当折射和反射同时发生时，取折射路径为寻优路径，仅当只发生反射时(即满足全反射条件)，取反射路径为寻优路径，按照此规则算法在搜索区域内自动搜索寻优。 优化方法的理论研究对完善算法体系、改进算法性能、拓宽算法应用领域具有重要作用，为此，本论文基于变分原理，对光线寻优算法的寻优机理、收敛性、稳定性进行分析，并将算法成功应用于求解函数优化问题。具体研究内容如下： 第一，对光线寻优算法的寻优机理进行分析，证明了光线会在水平和竖直分界线上交替进行折射，即设置矩形网格是有意义的；折射在算法中的作用是加速函数的变小趋势和减缓函数的变大趋势；搜索不会沿着函数值变大的方向一直进行下去，而会通过反射改变搜索方向。从理论角度上验证了算法的可行性。 第二，根据费马原理、利用变分法推导出基于折射的光线寻优算法最优化的实现过程，即对分层介质中算法的寻优功能做了具体的分析，得出了光具有偏向折射率增大方向、偏离折射率减小方向的自动寻优性质。从连续介质中的真实光线路径出发，通过分析光线所满足的方程，得真实光线同样具有寻优的功能，并分析光线寻优算法与光线方程所确定的寻优路径之间的关系，进而得出分块介质中算法亦具有自动寻优功能。 第三，对光线方程欧拉数值解法与光线寻优算法迭代公式的关系进行了研究，进而在光线寻优算法迭代公式中加入一项改进算法，这不仅使得精度提高一阶，而且加快了收敛的速度，解决了光线寻优算法推广到高维收敛速度变慢的问题。 第四，针对光线寻优算法局部搜索能力弱和收敛性理论完善困难的问题，提出了贪婪光线寻优算法，并通过理论推导证明该算法的局部收敛性。贪婪光线寻优与光线寻优算法的区别在于值变大即取反射路径为寻优路径，不接受“坏解”，适合求单极值问题。 第五，理论分析和数值实验表明：网格越小，求解精度越高，但相应的迭代次数增多，收敛速度变慢。针对这一问题改进算法，提出了基于变网格的光线寻优算法，算法搜索初期用较大的网格，确定全局最优点的大概位置后，换用较小的网格继续搜索。根据具体的精度要求，可以选择多次变小网格，从而达到提高收敛精度和速度的目的。 第六，将光线寻优算法用于求解2维、1维以及3维以上优化问题，与遗传算法、模拟退火算法、粒子群算法进行数值实验对比分析，并通过变分法分析了光线寻优算法用于求解1维优化问题时的局部收敛性。 第七，将模拟退火算法中的退火策略引入到光线寻优算法中而提出的一种新型混合优化算法—基于退火策略的光线寻优算法。通过引入无网格思想，即在算法寻优过程中无需生成网格，而是按照一定的规则直接确定折射或反射界面，提出了无网格光线寻优算法。并分别对这2种改进算法进行了数值实验的研究和对比分析。