摘 要: Gilbert算法是求解最接近點(diǎn)對(duì)問(wèn)題的一種算法,廣泛應(yīng)用于碰撞檢測(cè)、數(shù)據(jù)分類、運(yùn)動(dòng)規(guī)劃等領(lǐng)域。但是,Gilbert算法的最大缺點(diǎn)是在很多情況下,當(dāng)它接近最優(yōu)解時(shí),收斂速度非常慢。在Gilbert算法的基礎(chǔ)上提出一個(gè)新的迭代策略,可以減少算法的迭代次數(shù),加快收斂速度。實(shí)驗(yàn)結(jié)果證明,改進(jìn)后的算法求解速度和收斂速度快。
關(guān)鍵詞: Gilbert算法;NPA算法;碰撞檢測(cè);數(shù)據(jù)分類
Gilbert算法[1]是一種求解最接近點(diǎn)對(duì)算法,即求解凸包外指定點(diǎn)到一群點(diǎn)集組成的凸包的距離,廣泛應(yīng)用于機(jī)器人領(lǐng)域。Gilbert算法是一種迭代算法,屬于梯度下降算法,具有很好的全局收斂性,易被計(jì)算機(jī)實(shí)現(xiàn),而且適用幾何的觀點(diǎn)來(lái)分析。但是,Gilbert算法的缺點(diǎn)也很明顯,特別是接近最優(yōu)解時(shí)收斂過(guò)慢。
針對(duì)Gilbert算法的改進(jìn)算法有MDM算法[2]、NPA算法[3]以及CHANG L[4]等人提出的改進(jìn)算法。MDM算法利用具有消極影響的訓(xùn)練樣本點(diǎn)改進(jìn)更新策略,在迭代過(guò)程中,一旦發(fā)現(xiàn)迭代點(diǎn)的組合中具有消極影響的訓(xùn)練樣本點(diǎn),就直接在迭代點(diǎn)的線性組合中刪除或是降低該點(diǎn)對(duì)目標(biāo)函數(shù)的影響,并同時(shí)使得目標(biāo)函數(shù)邊緣下降。MDM算法解決了Gilbert算法接近最優(yōu)解時(shí)收斂過(guò)慢的問(wèn)題,但仍需要多次迭代完成計(jì)算。NPA算法結(jié)合了Gilbert算法和MDM算法的特點(diǎn),選取三角形區(qū)域作為迭代點(diǎn)的搜索范圍,擴(kuò)大了迭代點(diǎn)的搜索范圍,實(shí)驗(yàn)結(jié)果顯示,它比MDM算法收斂更快,但NPA算法仍存在計(jì)算量很大的不足。參考文獻(xiàn)[4]的研究證明了最接近點(diǎn)對(duì)問(wèn)題的最優(yōu)解一定出現(xiàn)在凸包頂點(diǎn)中兩點(diǎn)組成的邊上或者幾點(diǎn)確定的面上,根據(jù)此結(jié)論,最優(yōu)解一定落在凸包邊界上。CHANG L等人據(jù)此提出了一種改進(jìn)的Gilbert算法(下文簡(jiǎn)稱CQW),當(dāng)算法迭代到一定次數(shù)時(shí),如果發(fā)現(xiàn)算法重復(fù)選取幾個(gè)凸包頂點(diǎn)作為算法迭代選取的頂點(diǎn),就直接計(jì)算凸包外指定點(diǎn)到這幾點(diǎn)組成的平面或兩點(diǎn)組成的線段的距離,它加快了Gilbert的收斂,但需要人工設(shè)置迭代次數(shù),迭代次數(shù)的選取是一個(gè)難點(diǎn)。
針對(duì)上述算法計(jì)算量大的問(wèn)題,本文分析了Gilbert收斂慢的原因,當(dāng)新的迭代點(diǎn)越來(lái)越趨近于最優(yōu)解時(shí),它一直在最優(yōu)解附近徘徊,不能快速到達(dá)凸包邊界。本文通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),在迭代的過(guò)程中,一旦迭代點(diǎn)出現(xiàn)在凸包的邊界上,Gilbert算法會(huì)快速收斂。據(jù)此,本文在Gilbert算法的基礎(chǔ)上提出一種新的迭代策略,迭代過(guò)程中將Gilbert算法原有的梯度方向上的候選點(diǎn)與凸包邊界上的候選點(diǎn)進(jìn)行比對(duì),選取離凸包外指定點(diǎn)更近的候選點(diǎn)作為新的迭代點(diǎn),這樣的迭代機(jī)制一有機(jī)會(huì)即將迭代點(diǎn)拉到凸包的邊界上,有效避免了在凸包內(nèi)部最優(yōu)解附近不停徘徊迭代的情況發(fā)生,減少迭代次數(shù),加快收斂速度。實(shí)驗(yàn)結(jié)果表明,本文改進(jìn)后的算法與NPA算法相比,計(jì)算量小,問(wèn)題的求解速度更快,與CQW算法相比,不需要人工設(shè)置迭代次數(shù),更容易求出最優(yōu)解。
凸包邊界由邊和面組成,根據(jù)CHANG L[4]等人的結(jié)論,最優(yōu)解一定落在凸包邊界上。本文通過(guò)多次實(shí)驗(yàn)發(fā)現(xiàn),算法迭代點(diǎn)到達(dá)凸包邊界之后就會(huì)快速收斂。因此,本文考慮每次選取迭代點(diǎn)時(shí)都與離O點(diǎn)最近的凸包邊界線段上的點(diǎn)作比較,盡可能將迭代點(diǎn)拉至凸包邊界上,這樣可避免算法在凸包內(nèi)部最優(yōu)解附近徘徊迭代,以此來(lái)改進(jìn)Gilbert算法的收斂速度。
2 本文方法
2.1 算法思路
本文基于1.4節(jié)的分析,在算法第一次迭代確定頂點(diǎn)D之后(見(jiàn)圖5),考慮包含D的凸包邊界線段AD和CD,選擇離O點(diǎn)最近的邊界線段AD,同時(shí)將P1D和AD這兩條邊作為迭代點(diǎn)的搜索范圍,分別計(jì)算O點(diǎn)到這兩條線段的最近點(diǎn),選取兩者中較近的點(diǎn)作為新的迭代點(diǎn):如果O點(diǎn)到AD邊更近,則選取O點(diǎn)到AD邊上最近點(diǎn)作為新的迭代點(diǎn);如果O點(diǎn)到Gilbert算法原來(lái)的迭代點(diǎn)更近,則選取原來(lái)的迭代點(diǎn)作為新的迭代點(diǎn)。這樣每次迭代都有機(jī)會(huì)將迭代點(diǎn)拉到凸包邊界,可避免Gilbert算法不停地在凸包內(nèi)部最優(yōu)解附近選取迭代點(diǎn),使得算法快速收斂。
2.2 算法步驟
本文改進(jìn)后的算法步驟如下:
(1)初始化。取t=1,在凸包U上任取初始迭代點(diǎn)z1,z1∈U,設(shè)定停止精度ε。
本文算法每次選取迭代點(diǎn)時(shí)都與離O點(diǎn)近的邊界線段上的點(diǎn)作比較,有效避免了在凸包內(nèi)部最優(yōu)解附近不停地選取迭代點(diǎn)這種情況的發(fā)生,可以減少算法的迭代次數(shù),加快收斂速度,提高計(jì)算效率。
3 實(shí)驗(yàn)結(jié)果及分析
為了證明本文算法迭代策略的有效性,將本文算法與CQW算法、NPA算法進(jìn)行實(shí)驗(yàn)對(duì)比。設(shè)X=100×rand(50,3),這是一個(gè)50乘以3的隨機(jī)數(shù)矩陣,它表示50個(gè)點(diǎn),每個(gè)點(diǎn)的各個(gè)坐標(biāo)值均介于0~100,U是由這50個(gè)頂點(diǎn)構(gòu)成的凸包,利用上述3種算法求解坐標(biāo)軸原點(diǎn)O到凸包的最短距離,設(shè)置算法停止精度為10-10,由于精度較高,Gilbert算法很難求出最優(yōu)解,CQW算法需要人為設(shè)定迭代次數(shù),這里設(shè)定為100次,3種算法執(zhí)行時(shí)間和迭代次數(shù)的比對(duì)結(jié)果如表1所示。求解的最終結(jié)果均為32.813 134 341 830 660。
實(shí)驗(yàn)證明,本文算法與CQW算法相比,減少了迭代次數(shù),加快了收斂速度;與NPA算法相比,提高了計(jì)算效率和計(jì)算速度。
本文針對(duì)Gilbert算法的缺點(diǎn)對(duì)其進(jìn)行了改進(jìn),解決了Gilbert算法收斂過(guò)慢的問(wèn)題,可以非常高效地求解MNP問(wèn)題,改進(jìn)后的Gilbert算法與Gilbert算法一樣,可用于NPP問(wèn)題,將具有更強(qiáng)的普適性。實(shí)驗(yàn)證明,本算法與其他算法相比具有以下優(yōu)點(diǎn):(1)算法的迭代次數(shù)不需要人為控制,依然可以快速收斂;(2)算法的執(zhí)行速度較快,最優(yōu)解的搜索范圍比NPA算法更優(yōu);(3)算法非常有效地避免了迭代點(diǎn)在凸包內(nèi)部不停迭代的情況。改進(jìn)后的Gilbert算法可以用于支持向量機(jī)的數(shù)據(jù)分類、碰撞檢測(cè)、機(jī)器人路徑規(guī)劃等領(lǐng)域。同時(shí),它可以用作支持向量機(jī)的訓(xùn)練算法,這是下一步將要展開(kāi)的工作。
參考文獻(xiàn)
[1] GILBERT E G.An iterative procedure for computing the minimum of a quadratic form on a convex set[J].SIAM Journal of Control,1966,4(1):61-79.
[2] MITCHELL B F,DEM'YANOV V F,MALOZEMOV V N. Finding the point of a polyhedron closest to the origin[J].SIAM J.Contr.,1974,12:19-26.
[3] KEERTHI S S,SHEVADE S K,BHATTACHARYYA C,et al.A fast iterative nearest point algorithm for support vector machine classifier design[J].IEEE-NN,2000,11(1):124.
[4] CHANG L,QIAO H,WAN A,et al.An improved Gilbert algorithm with rapid convergence[C].Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems,Beijing:2006:3861-3866.
[5] 周志華.機(jī)器學(xué)習(xí)及其應(yīng)用2007[M].北京:清華大學(xué)出版社,2007:62-63.