[發明專利]一種基于禁忌搜索算法優化支持向量機的方法

無效

• 申請號: 201210575338.0
• 申請日: 2012-12-24
• 公開（公告）號: CN103164709A
• 公開（公告）日: 2013-06-19
• 發明（設計）人: 蘇華;孫學梅
• 申請（專利權）人: 天津工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京思創畢升專利事務所 11218
• 代理人: 劉明華

技術領域

本發明涉及一種支持向量機優化方法，特別地，涉及一種基于禁忌搜索算法優化支持向量機的方法。

背景技術

由于支持向量機在眾多領域應用廣泛，其重要性日益凸顯，而參數選擇直接影響支持向量機識別目標性能的優劣。如何確定支持向量機的參數是研究支持向量機的重要內容，也就順其自然成了研究熱點。目前，有很多智能算法被用于支持向量機參數的優化，而禁忌搜索算法以其較高的求解質量和效率以及在諸多組合優化鄰域顯示出的強大的尋優能力得到人們越來越多的青睞。

本發明將禁忌搜索算法用于支持向量機參數的優化，對禁忌搜索算法做了一些改進并基于標準數據集進行了測試，與基于結構風險上界的支持向量機參數選擇相比表明本發明算法有較好地性能。

禁忌搜索算法通過引入禁忌表和禁忌準則來避免迂回搜索，并通過特赦準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效搜索，最終實現全局優化。在文獻題目：《基于結構風險上界的SVM參數選擇》，作者：宋小杉，蔣曉瑜，羅建華，汪熙，科技導報2011，29(08)中，給出了結構風險上界的算法，提出了一種基于結構風險上界的SVM參數選擇方法，可以得到使SVM泛化性較強的參數。

但是支持向量機參數的選取至今仍然沒有一個統一的標準，參數選取大多依靠經驗采取試湊的方法，這樣不僅費時而且很難得到滿意的結果。

發明內容

在應用支持向量機解決具體問題時，首先考慮核函數的選取及參數的選擇。雖然目前關于核函數在理論研究和應用上取得了一定的成果，但尚未形成指導支持向量機參數選取的理論。本發明要解決的技術問題是：針對現有支持向量機選取參數時的盲目性和低效率，提出一種基于禁忌搜索算法優化支持向量機的方法。通過該算法，能夠更加有針對性和高效地選取支持向量機參數，通過禁忌搜索得到解空間內的近似最優參數，進而使得支持向量機的分類效果和全局尋優性能有一定程度上的提升。

本發明是通過以下技術方案實現的：

一種基于禁忌搜索算法優化支持向量機的方法，原始數據是經典的測試函數Shaffer’s?F6。

第一步首先使用禁忌搜索算法對支持向量機的懲罰因子和核函數參數進行優化。具體分為以下幾個部分來實現：

第一步A，給定算法參數，隨機產生初始參數c、γ，初始化禁忌表并將tab設定為空，分別對全局最優解best_glo和局部最優解best_loc進行初始化，置逃逸狀態es為0(即表明了初始處于非逃逸狀態)；

第一步B，判斷算法終止條件是否滿足。若是，則結束算法并輸出優化結果；否則，繼續以下步驟；

第一步C，計算當前參數取到的次數，據此設定鄰域半徑jump；

第一步D，記錄局部最優記錄best_loc連續未更新的步數，如果這一步數超過了預先設定的閾值，可以認為當前解陷入局部最優。算法開始逃逸，探索得到逃逸點，加入逃逸候選集es_para，置逃逸狀態es為1；

第一步E，判斷是否處于逃逸狀態(es＝1)，若是，鄰域半徑jump置為1，參數依次取逃逸候選集中的參數，否則，繼續以下步驟；

第一步F，基于鄰域半徑jump按照一定規則產生一定數量的鄰域解，作為候選解；

第一步G，通過SVM計算得到每個鄰域解的適配值，即該解產生對應的分類正確率，將對解按照正確率從大到小排序；

第一步H，依次對候選集中的元素做判斷：看該參數對應的正確率是否大于局部歷史最優記錄，如果大于，則替換局部歷史最優記錄，更新禁忌表，將該解作為下一步搜索的起始點；否則，繼續下面步驟；

第一步I，判斷該參數是否在禁忌表中，如果不在，加入禁忌表，將該參數作為下一步搜索的起始點；否則，判斷下一個解；如果沒有得到大于歷史最優記錄的或者不在禁忌表中的解，將最佳參數作為下一步搜索的起始點；

第一步J，轉步驟(1.B)。

第二步，利用得到的近似最優參數訓練得到最優支持向量機模型，并以此為基礎對測試函數進行實驗，驗證支持向量機的分類性能和搜索全局最優解的能力，使用禁忌搜索算法優化過的支持向量機模型對待尋優函數和分類樣本進行處理。