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

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


    

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

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

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