摘  要： Gilbert算法是求解最接近點對問題的一種算法，廣泛應(yīng)用于碰撞檢測、數(shù)據(jù)分類、運動規(guī)劃等領(lǐng)域。但是，Gilbert算法的最大缺點是在很多情況下，當(dāng)它接近最優(yōu)解時，收斂速度非常慢。在Gilbert算法的基礎(chǔ)上提出一個新的迭代策略，可以減少算法的迭代次數(shù)，加快收斂速度。實驗結(jié)果證明，改進(jìn)后的算法求解速度和收斂速度快。
關(guān)鍵詞： Gilbert算法；NPA算法；碰撞檢測；數(shù)據(jù)分類

    Gilbert算法[1]是一種求解最接近點對算法，即求解凸包外指定點到一群點集組成的凸包的距離，廣泛應(yīng)用于機器人領(lǐng)域。Gilbert算法是一種迭代算法，屬于梯度下降算法，具有很好的全局收斂性，易被計算機實現(xiàn)，而且適用幾何的觀點來分析。但是，Gilbert算法的缺點也很明顯，特別是接近最優(yōu)解時收斂過慢。
    針對Gilbert算法的改進(jìn)算法有MDM算法[2]、NPA算法[3]以及CHANG L[4]等人提出的改進(jìn)算法。MDM算法利用具有消極影響的訓(xùn)練樣本點改進(jìn)更新策略，在迭代過程中，一旦發(fā)現(xiàn)迭代點的組合中具有消極影響的訓(xùn)練樣本點，就直接在迭代點的線性組合中刪除或是降低該點對目標(biāo)函數(shù)的影響，并同時使得目標(biāo)函數(shù)邊緣下降。MDM算法解決了Gilbert算法接近最優(yōu)解時收斂過慢的問題，但仍需要多次迭代完成計算。NPA算法結(jié)合了Gilbert算法和MDM算法的特點，選取三角形區(qū)域作為迭代點的搜索范圍，擴大了迭代點的搜索范圍，實驗結(jié)果顯示，它比MDM算法收斂更快，但NPA算法仍存在計算量很大的不足。參考文獻(xiàn)[4]的研究證明了最接近點對問題的最優(yōu)解一定出現(xiàn)在凸包頂點中兩點組成的邊上或者幾點確定的面上，根據(jù)此結(jié)論，最優(yōu)解一定落在凸包邊界上。CHANG L等人據(jù)此提出了一種改進(jìn)的Gilbert算法(下文簡稱CQW)，當(dāng)算法迭代到一定次數(shù)時，如果發(fā)現(xiàn)算法重復(fù)選取幾個凸包頂點作為算法迭代選取的頂點，就直接計算凸包外指定點到這幾點組成的平面或兩點組成的線段的距離，它加快了Gilbert的收斂，但需要人工設(shè)置迭代次數(shù)，迭代次數(shù)的選取是一個難點。
    針對上述算法計算量大的問題，本文分析了Gilbert收斂慢的原因，當(dāng)新的迭代點越來越趨近于最優(yōu)解時，它一直在最優(yōu)解附近徘徊，不能快速到達(dá)凸包邊界。本文通過實驗發(fā)現(xiàn)，在迭代的過程中，一旦迭代點出現(xiàn)在凸包的邊界上，Gilbert算法會快速收斂。據(jù)此，本文在Gilbert算法的基礎(chǔ)上提出一種新的迭代策略，迭代過程中將Gilbert算法原有的梯度方向上的候選點與凸包邊界上的候選點進(jìn)行比對，選取離凸包外指定點更近的候選點作為新的迭代點，這樣的迭代機制一有機會即將迭代點拉到凸包的邊界上，有效避免了在凸包內(nèi)部最優(yōu)解附近不停徘徊迭代的情況發(fā)生，減少迭代次數(shù)，加快收斂速度。實驗結(jié)果表明，本文改進(jìn)后的算法與NPA算法相比，計算量小，問題的求解速度更快，與CQW算法相比，不需要人工設(shè)置迭代次數(shù)，更容易求出最優(yōu)解。


    

    凸包邊界由邊和面組成，根據(jù)CHANG L[4]等人的結(jié)論，最優(yōu)解一定落在凸包邊界上。本文通過多次實驗發(fā)現(xiàn)，算法迭代點到達(dá)凸包邊界之后就會快速收斂。因此，本文考慮每次選取迭代點時都與離O點最近的凸包邊界線段上的點作比較，盡可能將迭代點拉至凸包邊界上，這樣可避免算法在凸包內(nèi)部最優(yōu)解附近徘徊迭代，以此來改進(jìn)Gilbert算法的收斂速度。
2 本文方法
2.1 算法思路
    本文基于1.4節(jié)的分析，在算法第一次迭代確定頂點D之后(見圖5)，考慮包含D的凸包邊界線段AD和CD，選擇離O點最近的邊界線段AD，同時將P1D和AD這兩條邊作為迭代點的搜索范圍，分別計算O點到這兩條線段的最近點，選取兩者中較近的點作為新的迭代點：如果O點到AD邊更近，則選取O點到AD邊上最近點作為新的迭代點；如果O點到Gilbert算法原來的迭代點更近，則選取原來的迭代點作為新的迭代點。這樣每次迭代都有機會將迭代點拉到凸包邊界，可避免Gilbert算法不停地在凸包內(nèi)部最優(yōu)解附近選取迭代點，使得算法快速收斂。
2.2 算法步驟
    本文改進(jìn)后的算法步驟如下：
    (1)初始化。取t=1，在凸包U上任取初始迭代點z1，z1∈U，設(shè)定停止精度ε。

    本文算法每次選取迭代點時都與離O點近的邊界線段上的點作比較，有效避免了在凸包內(nèi)部最優(yōu)解附近不停地選取迭代點這種情況的發(fā)生，可以減少算法的迭代次數(shù)，加快收斂速度，提高計算效率。
3 實驗結(jié)果及分析
    為了證明本文算法迭代策略的有效性，將本文算法與CQW算法、NPA算法進(jìn)行實驗對比。設(shè)X=100×rand(50，3)，這是一個50乘以3的隨機數(shù)矩陣，它表示50個點，每個點的各個坐標(biāo)值均介于0～100，U是由這50個頂點構(gòu)成的凸包，利用上述3種算法求解坐標(biāo)軸原點O到凸包的最短距離，設(shè)置算法停止精度為10-10，由于精度較高，Gilbert算法很難求出最優(yōu)解，CQW算法需要人為設(shè)定迭代次數(shù)，這里設(shè)定為100次，3種算法執(zhí)行時間和迭代次數(shù)的比對結(jié)果如表1所示。求解的最終結(jié)果均為32.813 134 341 830 660。

    實驗證明，本文算法與CQW算法相比，減少了迭代次數(shù)，加快了收斂速度；與NPA算法相比，提高了計算效率和計算速度。
    本文針對Gilbert算法的缺點對其進(jìn)行了改進(jìn)，解決了Gilbert算法收斂過慢的問題，可以非常高效地求解MNP問題，改進(jìn)后的Gilbert算法與Gilbert算法一樣，可用于NPP問題，將具有更強的普適性。實驗證明，本算法與其他算法相比具有以下優(yōu)點：(1)算法的迭代次數(shù)不需要人為控制，依然可以快速收斂；(2)算法的執(zhí)行速度較快，最優(yōu)解的搜索范圍比NPA算法更優(yōu)；(3)算法非常有效地避免了迭代點在凸包內(nèi)部不停迭代的情況。改進(jìn)后的Gilbert算法可以用于支持向量機的數(shù)據(jù)分類、碰撞檢測、機器人路徑規(guī)劃等領(lǐng)域。同時，它可以用作支持向量機的訓(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] 周志華.機器學(xué)習(xí)及其應(yīng)用2007[M].北京：清華大學(xué)出版社，2007：62-63.