歐拉型光線尋優算法

沈繼紅，李加蓮，李焱

(1.哈爾濱工程大學理學院，黑龍江哈爾濱150001;2.哈爾濱工程大學自動化學院，黑龍江哈爾濱150001)

優化問題存在于科學研究和工程應用中的各個領域.傳統優化方法存在諸多的局限性，難以解決日益增多的復雜問題，而以生物智能或自然現象為基礎的智能算法，通過模擬自然界的物理或生態過程以及其各自算法本身的尋優機制，對最優化問題進行求解并實現全局收斂，具有簡單通用、魯棒性好、適于并行處理等特點，因此成為解決復雜優化問題的一種新途徑.這方面的研究很多，如遺傳算法、模擬退火算法、蟻群算法、粒子群算法等.受啟發于費馬原理［1］，沈繼紅于2007年提出一種新型的智能優化算法——光線尋優算法［2］(light ray optimization algorithm，LRO).LRO算法通過模擬光線在不均勻介質中的傳播過程進行優化搜索，它不依賴于函數梯度信息，需要調整的參數少，簡單容易實現［3］.該算法將搜索區域設想為填充了不同折射率的介質區域，把介質區域劃分成很多小區域(如矩形網格、正六邊形網格［4］)，光在此小區域的傳播速度為小區域中心點所對應的目標函數值，即此小區域被近似看成均勻介質.當搜索區域被分成足夠多的小區域，即每一小區域足夠小時，LRO的尋優路徑實際是光線路徑的近似［5-6］.LRO中位置的更新是通過求解光線和其所射到網格邊的交點，所以每迭代一次，都要判斷光線射到網格的哪一邊，而且隨著目標問題維數的增加，判斷的次數增多，尋優速度減慢.本文針對LRO推廣到高維收斂速度慢的問題，研究了光線方程歐拉數值解法與LRO迭代公式的關系，將與歐拉法相差的項加到LRO中得到一種改進LRO算法(improved light ray optimization，ILRO)，這不僅使精度提高一階，而且大幅提高了收斂速度.

1 光線尋優算法

1.1 算法描述

以如下優化問題為例:

其中，對于?(x，y)∈G，均滿足f(x，y)＞0.用水平及豎直的直線劃分搜索域G，這樣得到很多小矩形網格Di.如圖1，以第m次迭代為例，設從點(x(m)，y(m))以方向(p(m)，q(m))發出的一束光射到網格水平邊上的點(x(m+1)，y(m+1))，則

式(2)是通過計算光線與所射到邊y=Yk+1的交點而得.(p(m)，q(m))與(p(m+1)，q(m+1))的迭代關系滿足以下2點:

圖1 模擬反射和折射的最優搜索路徑Fig.1 The optimal searching path simulating reflection and refraction

1)如果滿足全反射條件，即vm+1sin αm＞vm，發生反射(如圖1)，方向的迭代關系滿足反射定律: α'm+1=αm，其中αm為入射角，αm+1為反射角，則

2)如果vm+1sin αm≤vm，發生折射(如圖1)，方向的迭代關系滿足折射定律其中αm為入射角，αm+1為折射角，則

當光線射到網格的豎直邊上時，類似的可推得位置和方向的迭代公式.

1.2 算法流程

根據上述分析，LRO算法具體實現步驟如下:

1)選定矩形網格的寬h和高τ，對搜索區域G進行劃分.

2)隨機選定初始點(x(0)，y(0))和初始方向(p(0)，q(0))，記錄光線所在的網格.

3)判斷光線射到所在網格的哪一邊上，從而計算下一個迭代點.

4)如果滿足停止條件，轉步驟6)，否則，轉步驟5).

5)判斷是否滿足全反射條件，如果滿足，按照反射定律計算下一個搜索方向，否則，按照折射定律計算下一個搜索方向.記錄光線所在的下一個網格，轉步驟3).

6)停止優化搜索并輸出最優值.

2 算法收斂性的基本理論

設光在折射率n=n(x，y)連續變化的區域傳播，其所滿足的微分方程［7］:

定理1 設二維搜索域G中光的傳播速度為v(x，y)，如果v(x，y)二階連續可導，那么任意選定G中的初始點，任意給定初始方向，可確定與它們相對應的唯一一條光線路徑.

證明 因為:

式中:c為光在真空中的速度.將式(9)代入光線微分方程(8)得

令r=(x，y)T，U=(u，w)T，方程組(11)可化為

由定理已知條件v(x，y)二階連續可導，可知方程組(12)的右端函數具有連續偏導數，因此滿足微分方程組解的存在唯一性定理，即由初值可以確定方程組(12)的唯一解.

在定理1中，v(x，y)取為目標函數f(x，y)，即v(x，y)=f(x，y)，以下的討論中也是如此.

定理2 在LRO算法中，如果第m次迭代光線在網格水平邊上發生折射，得到的方向迭代公式與光線方程歐拉數值解法相差，如果光線在豎直邊上發生折射，得到的方向迭代公式與光線方程歐拉數值解法相差，其中λm為LRO算法第m次迭代的步長.

證明 用歐拉法解微分方程組(11).

其中，

因為

將式(14)代入式(13)得

考慮二維情形，則

在LRO算法中，如圖2，以在水平邊上發生折射的情形為例，因為:

式中:λk為LRO算法第k次迭代的步長.由式(17)及折射定律得

由LRO得到的式(18)和歐拉法解光線方程得到的式(16)相差同理可以得到，當光線在豎直邊上發生折射時，相差為

定理3 LRO算法的尋優路徑與光線路徑的局部截斷誤差為O(λ).

證明 光線路徑滿足微分方程組(12)，則

其中，ξxm∈(sm，sm+1).因為考慮局部截斷誤差，所以假設:

則

同理:

其中，ξym，ξum，ξwm∈(sm，sm+1)，則局部截斷誤差為

為了更清楚和直觀的表述觀點，定理1～3以二維為例進行闡述，實際上這些理論都可平行的推廣到n維介質的情形.

3 改進光線尋優算法

LRO算法中位置的更新是通過求解光線與其所射到網格邊的交點，二維情形下，網格有4條邊，所以每迭代一次都要做4次判斷，從而確定光線射到哪一條邊上.三維情形下，網格有6個面，需要判斷6次.以此類推，n維情形需要判斷2n次.隨著維數的增加，判斷的次數增多，所以計算時間增多，收斂速度變慢，這是LRO推廣到高維遇到的主要困難.根據定理2，將與歐拉法相差的項加到LRO中，從而得到一種改進的LRO算法(ILRO)，不僅將精度提高了一階，而且使得尋優速度大大加快，解決了LRO推廣到高維運行速度慢的問題.具體推導過程如下.

首先將與歐拉法相差的項加到LRO中，并固定步長，可得如下迭代公式:

因為

其中:

同理可得

將式(25)、(26)代入式(24)得

其中，

略掉式(27)中的O(λ2)項，即為ILRO的迭代公式，則由式(20)～(23)，可得ILRO算法的局部截斷誤差:

所以ILRO的局部截斷誤差為O(λ2)，其迭代公式可推廣到n維:

以下給出ILRO算法的流程:

1)給定步長λ，隨機選定初始點和初始方向，令m=0.

3)判斷是否滿足停止條件，如果滿足，轉步驟5)，否則轉步驟4).

4)令m=m+1，轉步驟2).

5)停止優化搜索并輸出最優點.

4 改進算法與其他算法的對比仿真實驗

為了檢驗ILRO算法的的性能，對文獻［8］中的6個標準測試函數進行仿真實驗，測試函數如表1所示.

表1 測試函數Table 1 Test functions

表1中f1～f3為單峰函數，f4～f6為多峰函數，f5、f6為2維函數.采用文獻［9］中的函數變換法，選擇適當的M值加到各函數中，使得它們最優值均變為1.所有實驗均在處理器為E5400@2.70 GHz 2 G內存的PC機上運行.

4.1 ILRO中步長對尋優精度的影響

優化函數為f1、f2，步長分別為1、0.1、0.01，最大迭代次數分別為100、1 000、10 000，對不同的函數及步長，ILRO分別獨立運行100次，因為維數越高時，網格越小精度越高的優勢更加明顯，所以給出40維函數的數值實驗結果，見表2.可知，隨著步長的減小，精度提高，但步長越小，迭代次數越多，相應的運行時間將越長.所以在精度要求范圍內，選取適當大小的網格是很重要的.

表2 步長對精度的影響Table 2 The influence of step length on accuracy

4.2 ILRO與LRO的比較法

優化函數為f1、f2，以二維為例(與LRO相比，ILRO計算速度的優勢在低維時很明顯)，ILRO步長0.1，LRO網格寬和高均為0.1.2種算法最大迭代次數均為1 000，分別獨立運行100次，結果見表3.可見ILRO的平均迭代時間遠遠小于LRO.

表3 ILRO與LRO的仿真結果比較Table 3 Comparison of simulation results of ILRO and LRO

4.3 ILRO與EGA和SPSO的比較

優化函數為f1～f6，30維(其他優化算法文獻中經常選用的維數).為了比較的合理性，通過粗略地調節相關參數來獲得合適的性能.測試中算法的參數設置如下:ILRO算法步長h為0.1;EGA交叉概率0.6，變異概率0.001，30維函數的編碼長度20，群體規模80，2維函數的編碼長度10，群體規模20; SPSO學習因子c1、c2均為1.4，慣性權重w=0.9，30維函數的粒子數100，2維函數的粒子數20.比較方法:設定最大迭代次數10 000，各測試函數的目標值(見表4第2列)，如果算法在達到最大迭代次數后仍未達到目標值，則認為算法沒有成功收斂.針對不同的優化函數，3種算法分別獨立運行50次，成功收斂實驗的平均迭代時間及相應成功收斂率見表4.

由表4可知，對于30維函數f1～f4，無論從平均迭代時間還是成功收斂率角度考慮，ILRO均優于EGA和SPSO，這說明ILRO的收斂速度較快，收斂可靠性較高.對于2維函數f5～f6，從2個方面考慮ILRO都優于EGA，收斂成功率和SPSO持平，平均迭代時間要多于SPSO，這說明低維時，ILRO的收斂速度并沒有SPSO快，其收斂速度的優勢在高維時體現的較明顯.EGA和SPSO通過參數的不斷調整，也許能以更快的運行時間達到更高的精度，但這需要有一定的經驗，并且不同的研究者可能得出完全不同的結果.ILRO只有步長一個參數需要調節，并且從理論上講，步長越小，精度越高.所以作為一種新的智能算法，ILRO具有一定的優越性以及尋優潛能.

表4 ILRO與SPSO和EGA的仿真結果比較Table 4 Comparison of simulation results of ILRO，SPSO and EGA

5 結論

光線尋優算法是一種模擬光在變折射率介質中的傳播路徑進行最優值搜索的智能算法.作為一種新的算法，它為智能計算用于解決最優問題提供了新思路，并且具有可調參數少，結構簡單容易實現等優點.研究了光線方程歐拉數值解法和光線尋優算法迭代公式的關系，通過將與歐拉法相差的項加到光線尋優算法中進行算法的改進，從而達到提高精度，加速收斂的目的.選用6個標準測試函數對改進光線尋優算法進行測試，實驗結果表明:

1)改進光線尋優算法中步長越小，精度越高，搜索時間越長.

2)與光線尋優算法相比，改進光線尋優算法收斂速度的優勢在低維時就很明顯.

3)改進光線尋優算法的收斂速度和收斂成功率均優于保留精英遺傳算法.

4)與標準粒子群算法相比，改進光線尋優算法的收斂成功率較高，求解二維函數的收斂速度較慢，30維函數的收斂速度較快.

深入分析算法的尋優機理和收斂性，改進算法(如考慮變步長)，提高算法的收斂性能，拓寬算法的應用范圍，將是今后研究的重點.

［1］姚啟鈞.光學教程［M］.北京:高等教育出版社，2008: 154-157.

YAO Qijun.Optics course［M］.Beijing:Higher Education Press，2008:154-157.

［2］SHEN Jihong，LI Yan.An optimization algorithm based on optical principles［J］.Advances in Systems Science and Applications，2009，9(4):647-655.

［3］SHEN Jihong，LI Yan.Light ray optimization and its parameter analysis［C］//Proceeding of the 2009 International Joint Conference on Computational Sciences and Optimization.Sanya，China，2009:918-922.

［4］沈繼紅，李焱.基于正六邊形網格的光線尋優算法［C］//中國運籌學第十屆學術交流會.北京，中國，2010:21-22.

SHEN Jihong，LI Yan.Light ray optimization algorithm based on hexagon grid［C］//The 10th Academic Conference of Chinese Operational Research Society.Beijing，China，2010:21-22.

［5］SHEN Jihong，LI Jialian.The principle analysis of light ray optimization algorithm［C］//2010 Second International Conference on Computational Intelligence and Natural Computing.Wuhan，China，2010:154-157.

［6］SHEN Jihong，LI Jialian.Light ray optimization algorithm and convergence analysis for one dimensional problems［C］//2011 International Conference on Fuzzy Systems and Neural Computing.Hong Kong，China，2011:103-106.

［7］劉得森.變折射率介質理論及其技術實踐［M］.重慶:西南師范大學出版社，2005:14-26.

LIU Desen.Theories and technologies of gradient refractive index medium［M］.Chongqing:Southwest Normal University Press，2005:14-26.

［8］YAO X，LIU Y，LIN G.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［9］SHEN Jihong，LI Yan.Light ray optimization with function transform［C］//The 8th International Conference on Optimization:Techniques and Applications.Shanghai，China，2010:21-22.

［10］MAJUMDAR J，BHUNIA A K.Elitist genetic algorithm for assignment problem with imprecise goal［J］.European Journal of Operational Research，2007，177:684-692.

［11］EBERHART R C，KENNENEDY J.Particle swarm optimization［C］//Proceedings of IEEE International Conference on Neural Networks.Perth，Australia，1995:1942-1948.

［12］秦洪德，石麗麗.一種新型的被動啟發式粒子群優化算法［J］.哈爾濱工程大學學報，2010，31(10):1298-1302.

QIN Hongde，SHI Lili.A new passive heuristic particle swarm optimization algorithm［J］.Journal of Harbin Engineering University，2010，31(10):1298-1302.