基于模擬退火算法特征選擇軟件的設計與實現

王晗，劉維生，李輝，王輝＊

（1.盤錦高級技工學校，遼寧 盤錦 124000；2.盤錦職業技術學院，遼寧 盤錦 124000）

0 引言

特征選擇是人工智能、模式識別和數據挖掘等領域的重要研究問題，在數字圖像分類、數字圖像檢索、客戶關系管理、入侵檢測和基因分析等方面已經得到了廣泛應用。一般情況下，樣本數量是有限的，用大量特征來構建分類器是不合時宜，此外，特征向量和模式分類器的性能之間并不是線性關系，當特征向量維數超過一定限度時，將會導致分類器范化能力反而降低，從而正確有效地進行特征選擇便成為模式識別中亟待解決的問題，因此，本文設計了一種基于模擬退火算法特征選擇軟件。

1 特征選擇和模擬退火算法

特征選擇問題主要需要解決兩個方面，一方面是確定特征選擇算法，在允許的時間內，以能夠接受的代價找出最小的、最能表達類別特征的特征參數組合。另一方面是確定特征評價標準，衡量特征組合是否最優，以便確定特征選擇操作的停止條件[1-2]，其算法的基本結構如圖1所示。

圖1 特征選擇算法的基本結構

模擬退火算法（Simulated Annealing Algorithm，簡稱SA）是80年代發展起來的一種用于求解大規模優化問題的隨機搜索算法。利用Metropolis準則并適當地控制溫度的下降過程實現模擬退火過程，從而達到在多項式時間內求解近似全局優化問題的目標。本文將最近鄰分類器的整體識別率作為子集評價函數，給出了一種基于模擬退火算法與最近鄰分類器識別率的特征選擇方法軟件MATLAB實現方法。實踐證明本文算法具有較強的特征參數篩選能力，能在多項式時間內給出問題的近似最優解[3-4]。本文特征選擇算法的偽代碼流程圖如圖2所示。

圖2 本文特征選擇算法的偽代碼流程圖

2 基于模擬退火算法特征選擇軟件的MATLAB程序設計

2.1 函數程序和軟件使用方法

軟件主函數為function [MAX_OPT_VALUE,MAX_OPT_POS]=main(Y0,data_sort)，函數返回值為MAX_OPT_VALUE,MAX_OPT_POS，其中，最優組合為MAX_OPT_VALUE，最優值為MAX_OPT_POS。Y0代表原始數據集合，data_sort代表數據類型，可根據實際需要自行設定，或默認。軟件子函數：（1）function Yxin=neighbor2(Yuan,n)為2變換鄰域程序，產生一種鄰域結構；（2）function Yxin=neighbor3(Yuan,n) 為3變換鄰域程序，產生一種鄰域結構；（3）function T0= Setting_initial_temp(Yuan,X0,n,data_sort)為設置初始溫度函數，設置初始溫度T0，n是參數的總個數，也稱為問題的規模，X0是初始接受率。（4）function [MAX_K_CLASS_END1,CLASS_END_MIN1]= K_neigbor_Final (test_para,data_sort)為最近鄰分類器函數[5-6]。

軟件使用方法如下：（1）將文件置于MATLAB軟件默認調用函數目錄中；（2）打開MATLAB程序，在命令窗口中，分別給Y0和data_sort賦初始值；（3）在命令窗口中，輸入“[MAX_OPT_VALUE, MAX_OPT_POS]=main(Y0,data_sort)；”即可運行程序。待彈出窗口后，程序結束，在命令窗口中，顯示程序運行時間、最優組合為MAX_OPT_VALUE、最優值為MAX_OPT_POS、起始溫度和終止溫度等程序運行結果信息[7-8]。

2.2 主函數程序程序代碼

3 結語

本文使用MATLAB語言設計了基于模擬退火算法和和最近鄰類器整體識別率特征選擇軟件，給出了軟件算法在MATLAB開發平臺上程序的源代碼。該軟件可應用于人工智能、模式識別、智能控制等相關研究領域，對于給定的樣本數據集合，該軟件能夠直接應用特征度量中的準確性度量(分類器整體識別率)，能夠較直接地評價特征參數組合的優劣，再通過結合優化的模擬退火算法使用，能夠確保該軟件最終收斂到近似全局最優解。技術特點：該程序用戶使用方便靈活，輸入樣本數據格式兼容范圍廣，輸出為最優組合和最優值及其他相關參數。較同類軟件，該程序運行速度較快、移植性、開放性好，程序執行效率較高，調試方便，并預留了程序升級接口，能夠解決人工智能和模式識別特征分析問題的需求，同時能夠滿足電子信息技術類專業課程與科研實驗的需要。實踐表明，該軟件所求解的質量優于模式識別中傳統的特征選擇方法，具備良好的噪聲容忍性，具有一定的工程實用價值。