樊永生+熊焰明+余紅英

摘 要： 針對求解支持向量機反問題的效率較低，算法復雜度高以及運用傳統(tǒng)方法求解該問題容易陷入局部最優(yōu)出現(xiàn)早熟收斂的問題，提出一種基于改進差異的差異演化算法。該算法在標準差異演化算法的基礎上利用種群分類機制對算法進行改進，對改進后的算法與標準差異演化算法和K?means聚類算法進行實驗設計，并對算法最終實驗結果進行分析，改進的差異演化算法除在運行時間外，結果對比以及最大間隔次數(shù)比都有明顯的提升，有效地保護處于最優(yōu)解區(qū)域但是適應值低的個體，能夠提高算法局部搜索能力，有助于算法實現(xiàn)全局收斂。實驗結果表明，改進的差異演化算法在求解SVM反問題上能有明顯的提升。

關鍵詞： 支持向量機； 局部最優(yōu)； 差異演化算法； 全局收斂； 種群分類機制； IRIS數(shù)據(jù)庫

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2018）06?0141?04

Abstract： Since the traditional algorithm has the problems of low efficiency of support vector machine （SVM） inverse problem solving and high algorithm complexity， is easily to fall into local optimum， and is prone to the premature convergence， a new differential evolutionary algorithm based on improved difference is proposed. On the basis of normative differential evolution algorithm， the population classification mechanism is used to improve the algorithm. The experimental design was carried out for the improved algorithm， normative differential evolution algorithm and K?means clustering algorithm. The final experimental results of the algorithm are analyzed. The maximum interval numbers and average interval numbers of the changed differential evolution （CDE） algorithm beyond operation time are improved greatly. The algorithm can effectively protect the individual within the optimum solution region but with low adaptive value， improve the local search ability of the algorithm， and is conductive to the realization of global convergence. The experimental results show that the performance of the CDE algorithm is improved obviously for SVM inverse problem solving.

Keywords： support vector machine； local optimum； differential evolution algorithm； global convergence； population classification mechanism； IRIS database

0 引 言

支持向量機（Support Vector Machine，SVM）是機器學習領域中一個重要的研究熱點，因其具有優(yōu)秀的泛化能力和學習能力被廣泛地應用在模式識別、文本分類、信號處理、回歸分析等領域[1?3]。SVM是在統(tǒng)計學習理論的基礎上，提出最優(yōu)超平面間隔理論。該理論結合結構風險最小化原理，將原始訓練樣本進行提取壓縮，得到支持向量集合，通過這些支持向量子集學習新的知識。SVM出發(fā)點是根據(jù)已經給定的正負標簽的類別信息，尋找兩類樣本之間的最優(yōu)超平面。在尋找過程中，靠近當前最優(yōu)超平面最近的樣本點到超平面的距離盡可能的大，不同類別的樣本之間的間距也會越大，分類器的泛化能力也就越強。所以，SVM是一個在訓練樣本訓練之前賦予其標簽信息的典型監(jiān)督學習問題。

然而，如果訓練之前沒有已給定的任何類別信息，根據(jù)上述的SVM問題難以快速找到最優(yōu)超平面，為此，出現(xiàn)了SVM反問題，即無監(jiān)督學習。SVM反問題是一種訓練樣本在訓練之前不含有任何類別信息的無監(jiān)督學習問題，通過尋找樣本之間的最大間距（margin），完成學習[4?7]。差分演化算法是解決研究無監(jiān)督學習這一問題的最先進的算法之一[8?9]，本文提出應用改進的差異演化算法與聚類算法及標準差異演化算法進行實驗分析，結果表明，所提出的算法在總體上優(yōu)于其他最先進的進化算法。

1 算法設計

1.1 概 述

定義1 （SVM反問題） 假設存在數(shù)據(jù)集合[S=x1，x2，…，xn，]并且[xi∈Rni=1，2…，N，][Ω=][ff是從S到 [-1，1] 的映射函數(shù)]。給定函數(shù)[f∈Ω]，數(shù)據(jù)集分為兩個子類，然后計算間隔（margin）。用margin（f）表示某個分類方法的類間隔[10]，SVM反問題為：[maxf∈Ωmarginf]。endprint