摘  要： Gilbert算法是求解最接近點(diǎn)對(duì)問題的一種算法，廣泛應(yīng)用于碰撞檢測,、數(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算法,；碰撞檢測；數(shù)據(jù)分類

    Gilbert算法[1]是一種求解最接近點(diǎn)對(duì)算法,，即求解凸包外指定點(diǎn)到一群點(diǎn)集組成的凸包的距離,，廣泛應(yīng)用于機(jī)器人領(lǐng)域,。Gilbert算法是一種迭代算法，屬于梯度下降算法,，具有很好的全局收斂性,，易被計(jì)算機(jī)實(shí)現(xiàn)，而且適用幾何的觀點(diǎn)來分析,。但是,，Gilbert算法的缺點(diǎn)也很明顯，特別是接近最優(yōu)解時(shí)收斂過慢,。
    針對(duì)Gilbert算法的改進(jìn)算法有MDM算法[2],、NPA算法[3]以及CHANG L[4]等人提出的改進(jìn)算法。MDM算法利用具有消極影響的訓(xùn)練樣本點(diǎn)改進(jìn)更新策略,，在迭代過程中,，一旦發(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í)收斂過慢的問題,，但仍需要多次迭代完成計(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ì)問題的最優(yōu)解一定出現(xiàn)在凸包頂點(diǎn)中兩點(diǎn)組成的邊上或者幾點(diǎn)確定的面上，根據(jù)此結(jié)論,，最優(yōu)解一定落在凸包邊界上,。CHANG L等人據(jù)此提出了一種改進(jìn)的Gilbert算法(下文簡稱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ì)算量大的問題,，本文分析了Gilbert收斂慢的原因,，當(dāng)新的迭代點(diǎn)越來越趨近于最優(yōu)解時(shí)，它一直在最優(yōu)解附近徘徊,，不能快速到達(dá)凸包邊界,。本文通過實(shí)驗(yàn)發(fā)現(xiàn),，在迭代的過程中，一旦迭代點(diǎn)出現(xiàn)在凸包的邊界上,，Gilbert算法會(huì)快速收斂,。據(jù)此，本文在Gilbert算法的基礎(chǔ)上提出一種新的迭代策略,，迭代過程中將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ì)算量小,，問題的求解速度更快,，與CQW算法相比，不需要人工設(shè)置迭代次數(shù),，更容易求出最優(yōu)解,。


    

    凸包邊界由邊和面組成，根據(jù)CHANG L[4]等人的結(jié)論,，最優(yōu)解一定落在凸包邊界上,。本文通過多次實(shí)驗(yàn)發(fā)現(xiàn)，算法迭代點(diǎn)到達(dá)凸包邊界之后就會(huì)快速收斂,。因此,，本文考慮每次選取迭代點(diǎn)時(shí)都與離O點(diǎn)最近的凸包邊界線段上的點(diǎn)作比較，盡可能將迭代點(diǎn)拉至凸包邊界上,，這樣可避免算法在凸包內(nèi)部最優(yōu)解附近徘徊迭代,，以此來改進(jìn)Gilbert算法的收斂速度。
2 本文方法
2.1 算法思路
    本文基于1.4節(jié)的分析,，在算法第一次迭代確定頂點(diǎn)D之后(見圖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算法原來的迭代點(diǎn)更近，則選取原來的迭代點(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算法收斂過慢的問題，可以非常高效地求解MNP問題,，改進(jìn)后的Gilbert算法與Gilbert算法一樣,，可用于NPP問題,，將具有更強(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ù)分類,、碰撞檢測,、機(jī)器人路徑規(guī)劃等領(lǐng)域。同時(shí),，它可以用作支持向量機(jī)的訓(xùn)練算法,，這是下一步將要展開的工作。
參考文獻(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.