歐拉型光線尋優(yōu)算法

沈繼紅，李加蓮，李焱

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

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

1 光線尋優(yōu)算法

1.1 算法描述

以如下優(yōu)化問題為例:

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

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

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

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

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

當(dāng)光線射到網(wǎng)格的豎直邊上時(shí)，類似的可推得位置和方向的迭代公式.

1.2 算法流程

根據(jù)上述分析，LRO算法具體實(shí)現(xiàn)步驟如下:

1)選定矩形網(wǎng)格的寬h和高τ，對(duì)搜索區(qū)域G進(jìn)行劃分.

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

3)判斷光線射到所在網(wǎng)格的哪一邊上，從而計(jì)算下一個(gè)迭代點(diǎn).

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

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

6)停止優(yōu)化搜索并輸出最優(yōu)值.

2 算法收斂性的基本理論

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

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

證明 因?yàn)?

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

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

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

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

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

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

其中，

因?yàn)?/p>

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

考慮二維情形，則

在LRO算法中，如圖2，以在水平邊上發(fā)生折射的情形為例，因?yàn)?

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

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

定理3 LRO算法的尋優(yōu)路徑與光線路徑的局部截?cái)嗾`差為O(λ).

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

其中，ξxm∈(sm，sm+1).因?yàn)榭紤]局部截?cái)嗾`差，所以假設(shè):

則

同理:

其中，ξym，ξum，ξwm∈(sm，sm+1)，則局部截?cái)嗾`差為

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

3 改進(jìn)光線尋優(yōu)算法

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

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

因?yàn)?/p>

其中:

同理可得

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

其中，

略掉式(27)中的O(λ2)項(xiàng)，即為ILRO的迭代公式，則由式(20)～(23)，可得ILRO算法的局部截?cái)嗾`差:

所以ILRO的局部截?cái)嗾`差為O(λ2)，其迭代公式可推廣到n維:

以下給出ILRO算法的流程:

1)給定步長(zhǎng)λ，隨機(jī)選定初始點(diǎn)和初始方向，令m=0.

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

4)令m=m+1，轉(zhuǎn)步驟2).

5)停止優(yōu)化搜索并輸出最優(yōu)點(diǎn).

4 改進(jìn)算法與其他算法的對(duì)比仿真實(shí)驗(yàn)

為了檢驗(yàn)ILRO算法的的性能，對(duì)文獻(xiàn)［8］中的6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，測(cè)試函數(shù)如表1所示.

表1 測(cè)試函數(shù)Table 1 Test functions

表1中f1～f3為單峰函數(shù)，f4～f6為多峰函數(shù)，f5、f6為2維函數(shù).采用文獻(xiàn)［9］中的函數(shù)變換法，選擇適當(dāng)?shù)腗值加到各函數(shù)中，使得它們最優(yōu)值均變?yōu)?.所有實(shí)驗(yàn)均在處理器為E5400@2.70 GHz 2 G內(nèi)存的PC機(jī)上運(yùn)行.

4.1 ILRO中步長(zhǎng)對(duì)尋優(yōu)精度的影響

優(yōu)化函數(shù)為f1、f2，步長(zhǎng)分別為1、0.1、0.01，最大迭代次數(shù)分別為100、1 000、10 000，對(duì)不同的函數(shù)及步長(zhǎng)，ILRO分別獨(dú)立運(yùn)行100次，因?yàn)榫S數(shù)越高時(shí)，網(wǎng)格越小精度越高的優(yōu)勢(shì)更加明顯，所以給出40維函數(shù)的數(shù)值實(shí)驗(yàn)結(jié)果，見表2.可知，隨著步長(zhǎng)的減小，精度提高，但步長(zhǎng)越小，迭代次數(shù)越多，相應(yīng)的運(yùn)行時(shí)間將越長(zhǎng).所以在精度要求范圍內(nèi)，選取適當(dāng)大小的網(wǎng)格是很重要的.

表2 步長(zhǎng)對(duì)精度的影響Table 2 The influence of step length on accuracy

4.2 ILRO與LRO的比較法

優(yōu)化函數(shù)為f1、f2，以二維為例(與LRO相比，ILRO計(jì)算速度的優(yōu)勢(shì)在低維時(shí)很明顯)，ILRO步長(zhǎng)0.1，LRO網(wǎng)格寬和高均為0.1.2種算法最大迭代次數(shù)均為1 000，分別獨(dú)立運(yùn)行100次，結(jié)果見表3.可見ILRO的平均迭代時(shí)間遠(yuǎn)遠(yuǎn)小于LRO.

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

4.3 ILRO與EGA和SPSO的比較

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

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

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

5 結(jié)論

光線尋優(yōu)算法是一種模擬光在變折射率介質(zhì)中的傳播路徑進(jìn)行最優(yōu)值搜索的智能算法.作為一種新的算法，它為智能計(jì)算用于解決最優(yōu)問題提供了新思路，并且具有可調(diào)參數(shù)少，結(jié)構(gòu)簡(jiǎn)單容易實(shí)現(xiàn)等優(yōu)點(diǎn).研究了光線方程歐拉數(shù)值解法和光線尋優(yōu)算法迭代公式的關(guān)系，通過將與歐拉法相差的項(xiàng)加到光線尋優(yōu)算法中進(jìn)行算法的改進(jìn)，從而達(dá)到提高精度，加速收斂的目的.選用6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)光線尋優(yōu)算法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明:

1)改進(jìn)光線尋優(yōu)算法中步長(zhǎng)越小，精度越高，搜索時(shí)間越長(zhǎng).

2)與光線尋優(yōu)算法相比，改進(jìn)光線尋優(yōu)算法收斂速度的優(yōu)勢(shì)在低維時(shí)就很明顯.

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

4)與標(biāo)準(zhǔn)粒子群算法相比，改進(jìn)光線尋優(yōu)算法的收斂成功率較高，求解二維函數(shù)的收斂速度較慢，30維函數(shù)的收斂速度較快.

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

［1］姚啟鈞.光學(xué)教程［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］沈繼紅，李焱.基于正六邊形網(wǎng)格的光線尋優(yōu)算法［C］//中國(guó)運(yùn)籌學(xué)第十屆學(xué)術(shù)交流會(huì).北京，中國(guó)，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］劉得森.變折射率介質(zhì)理論及其技術(shù)實(shí)踐［M］.重慶:西南師范大學(xué)出版社，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］秦洪德，石麗麗.一種新型的被動(dòng)啟發(fā)式粒子群優(yōu)化算法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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.