夏 輝

(沈陽師范大學 科信軟件學院, 沈陽 110034)

基于優(yōu)化模擬退火算法的智能決策模型

夏 輝

(沈陽師范大學 科信軟件學院, 沈陽 110034)

決策理論在工業(yè)生產(chǎn)、管理決策、安全生產(chǎn)等越來越多的領(lǐng)域得到廣泛應(yīng)用,已經(jīng)成為越來越多的研究者研究的重要課題。三支決策粗糙集模型作為一個重要的概率型粗糙集模型,在給定損失函數(shù)情況下可以導(dǎo)出多種概率型粗糙集模型,針對決策粗糙集模型構(gòu)建的最優(yōu)化問題,考慮到?jīng)Q策成本最小化,提出一個優(yōu)化的模擬退火算法和啟發(fā)式算法,從而得到代價最小的屬性約簡集,研究闡明了一種將粗粒度并行優(yōu)化方法和啟發(fā)式學習方法結(jié)合,解決粗糙集決策優(yōu)化問題。實驗證明提出的模擬退火的優(yōu)化DTRS模型算法具有良好的有效性,運行時間也短于自適應(yīng)算法,而且學習到的閾值能夠得到較小的決策風險代價。研究揭示了優(yōu)化表示帶來的一些新的見解,對決策粗糙集模型的研究提供了新的思路。

決策粗糙集模型; 模擬退火算法; 代價函數(shù); 決策閥值; 并行計算模型

0 引 言

實際應(yīng)用中,決策粗糙集的代價函數(shù)的定義是有明確規(guī)定的,在決策粗糙集模型中需要六個代價函數(shù)值,而其他的一些概率粗糙集模型往往只需要一個參數(shù)即可,從實用性角度來看,決策粗糙集模型使用起來要比其他模型復(fù)雜得多,針對這一問題,Herbert等[1]從博弈論角度分析決策粗糙集模型,并且對代價函數(shù)值進行一些調(diào)解,使得目標函數(shù)逐步達到最優(yōu)化。然而該方法有個缺陷:使用者首先要給出所關(guān)注的優(yōu)化目標,而且需要在迭代中多次參與到學習中,這樣就要求使用者具備一定領(lǐng)域的先驗知識;為此,Yao[2]也提出了三支決策模型,但同樣面臨著閥值需要依靠經(jīng)驗和實驗獲取問題,因此對先驗知識要求較高,這樣就會導(dǎo)致現(xiàn)實中很難實現(xiàn)。Jia[3]提出了使用模擬退火算法解決決策代價,同時較好地解決了決策效率問題,因此決策問題就可以間接地轉(zhuǎn)化為利用模擬退火算法進行解決,由于模擬退火算法具有較好的數(shù)學性質(zhì),即以概率1 收斂于全局最優(yōu)值,而且算法也和具體問題無關(guān),所以它被廣泛地應(yīng)用于各種組合優(yōu)化問題。然而,模擬退火算法[4-5]也具有NP問題,它收斂速度較慢,運行時間較長,且算法性能和初始值有關(guān)等,這些缺點使它在實際應(yīng)用中具有較大的瓶頸。

本文克服了模擬退火算法的缺點(內(nèi)在串行性)并且與“下山法”相結(jié)合,同時綜合了一些優(yōu)化方法,使原來的模擬退火算法得到可擴展的并行效果,進而大大提升了算法的收斂速度,同時克服了算法性能對參數(shù)及初始值的過分依賴,最后得到了最優(yōu)的決策閥值,進而提升了決策模型的應(yīng)用效率。

1 決策粗糙集模型

根據(jù)貝葉斯決策流程和 DTRS模型[6-9]構(gòu)建決策優(yōu)化系統(tǒng)模型,并且構(gòu)建決策閥值因子與決策代價的函數(shù)關(guān)系。

1.1 決策粗糙集理論研究

首先創(chuàng)建決策模型,根據(jù)決策模型最小代價表示出決策閥值;然后根據(jù)貝葉斯決策流程推導(dǎo)出最小化代價決策規(guī)則;然后通過一定的約簡規(guī)則,表示出代價模型;最后根據(jù)設(shè)定條件的決策表達式和給定閥值,得到positive rule,boundary rule和negative rule三支決策規(guī)則的代價函數(shù),并且累加這三支決策代價函數(shù),從而得到總的代價函數(shù)。

1) DTRS決策模型參數(shù)

根據(jù)經(jīng)驗值,一般可以得到代價函數(shù)滿足:λPP≤λBP<λNP和λNNλBN<λPN,即:對于屬于W的對象w,把它劃分到W正區(qū)域的風險代價要小于或者等于將它劃分到邊界區(qū)域的風險代價；而且二者的風險都要小于其劃分到W負區(qū)域的風險代價,同理,對于不屬于W的對象w,將其劃分到W負區(qū)域的風險代價要小于或等于將其劃分到邊界區(qū)域的風險代價；并且二者的風險代價都小于將其劃分到W正區(qū)域的風險代價。不妨可以令下面3個等式成立,并且損失函數(shù)之間的可以假定,α∈(0,1],β[0,1)和γ(0,1)。

其中,λPP,λBP和λNP分別表示當對象屬于某個狀態(tài)C時所采取P,B,N行動后的代價,同樣λPN,λBN和λNN分別表示當對象不屬于某個狀態(tài)C時所采用的P,B,N行動后的代價。

2) 構(gòu)建決策代價函數(shù)模型

圖1 DTRS決策代價函數(shù)模型表示流程

1.2 Pawlak約簡理論模型[10-13]

充分條件: POSπR(πD)=POSπC(πD);

必要條件: POSπR-{a}(πD)≠POSπC(πD),其中a∈R。

2 粗粒度并行計算的優(yōu)化模擬退火算法

優(yōu)化模擬退火算法基本思想:OSAA(優(yōu)化模擬退火算法)決策模型是在原有經(jīng)典模擬退火模型基礎(chǔ)上做重大的并行化改進的同時,結(jié)合了下山法快速收斂的特點,它是一種可擴展的大規(guī)模并行計算方法。

2.1 并行計算模型框架

2.2 構(gòu)建OSAA模型

參考經(jīng)典退火算法思想,初始化 OSAA時間表,構(gòu)建一個適應(yīng)度函數(shù)f(R),R為約簡屬性集,設(shè)定一個初始溫度t0, 記錄退火次數(shù)N,通過比較COSTNEW和COSTOLD的大小關(guān)系確定當前解COSTc,每一次比較完后,都要以某個概率因子去調(diào)用下山函數(shù)DownHill(COSTc),設(shè)計模型策略為:多次退火無進展后找到的較優(yōu)解采取高的下山概率,從而真正找到全局最優(yōu)解,而不是局部最優(yōu)解,并且要和其他的計算結(jié)點進行通信,比較彼此的最優(yōu)解,從而達到并行運算的效果。本算法引入并行計算模型,本文算法對經(jīng)典退火算法進行優(yōu)化。該并行算法是在多個串行算法得到馬爾可夫鏈中選擇收斂速度最快的一個,同時去除了其他的鏈,基于此,從同一起點,又重新計算多條馬爾可夫鏈,圖2即為并行退火過程中馬爾可夫鏈的生長與變化。

圖2 并行退火過程中馬爾可夫鏈的生長與變化

3 仿真實驗和結(jié)果分析

使用UCI(University of California-Irvine)[14]數(shù)據(jù)集的若干組數(shù)據(jù)進行實驗,將相應(yīng)的算法集成實現(xiàn)在WEKA平臺[15],進行數(shù)據(jù)的驗證,實驗主要驗證以下決策理論的2個方面:

1) 優(yōu)化模擬退火算法(OSAA)和自適應(yīng)算法進行對比,分別從運行時間、最小代價、算法復(fù)雜度進行對比;

2) 優(yōu)化的代價最小目標的簡約屬性算法驗證。

實驗采用的機器設(shè)備是IntelCore i7-3770處理器,8 G的內(nèi)存,64位的Windows10操作系統(tǒng),本系統(tǒng)算法使用的是基于Weka平臺。平臺實驗數(shù)據(jù)是從UCI數(shù)據(jù)庫中的5個數(shù)據(jù)集。實驗結(jié)果如表1所示,使用了基于自適應(yīng)算法Alcofa和模擬退火算法這2種算法來求得的決策閾值所作的決策風險代價,而表2體現(xiàn)出自適應(yīng)算法以及模擬退火算法的平均運行時間(單位:ms)。

從表1的數(shù)據(jù)來看,本文提出的模擬退火算法在這5種數(shù)據(jù)集上運行速度都要比自適應(yīng)算法的更快,展示了模擬退火算法具有更高的效率。然而對于自適應(yīng)算法Alcofa,它是一種迭代的算法, 該算法的時間復(fù)雜度是O(n2),它需要計算訓(xùn)練集中每個樣本。然而本文提出的模擬退火算法卻是一種隨機的算法,運行時間和參數(shù)的設(shè)置有關(guān),如果參數(shù)設(shè)置合適,那么運行速度將很快。從表2中數(shù)據(jù)可以看出,本文提出的模擬退火算法在這5種數(shù)據(jù)集中可以獲得很小的決策風險代價。

表1 2種算法運行時間對比

表2 2種算法決策代價比較

4 結(jié) 語

本文提出了一個優(yōu)化的DTRS模型,優(yōu)化的標準是基于最小決策代價,優(yōu)化后的模型無需先驗知識就可以學習到代價函數(shù)和決策閥值,和以往的學習方法相比具有較高的效率以及較低的決策風險,通過實驗,本文提出的模擬退火的優(yōu)化DTRS模型算法具有良好的有效性,運行時間也短于自適應(yīng)算法,而且學習到的閾值能夠得到較小的決策風險代價。

[ 1 ]LEE C Y,LEE D. Determination of initial temperature in fast simulated annealing[J]. Comput Optim Appl, 2014,58(2):503-522.

[ 2 ]JIA Xiuyi,LIAO Wenhe,TANG Zhenmin,et al. Minimum cost attribute reduction in decision-theoretic rough set models[J]. Inform Sci, 2013,219:151-167.

[ 3 ]YAO Y Y. Three-Way decisions with probabilistic rough sets[J]. Inform Sci, 2010,18(3):341-353.

[ 4 ]賈修一,商琳. 一種求三支決策閾值的模擬退火算法[J]. 小型微型計算機系統(tǒng), 2013,34(11):2603-2606.

[ 5 ]王玉梅. 基于模擬退火算法的遞歸自動閾值分割方法[J]. 光學與光電技術(shù), 2014,12(2):48-52.

[ 6 ]LI F,YE M,CHEN X. An extension to Rough c-means clustering based on decision-theoretic Rough Sets model[J]. Interna Approx Reason, 2014,55(1):116-129.

[ 7 ]AZAM N,YAO J. Analyzing uncertainties of probabilistic rough set regions with game-theoretic rough sets[J]. Interna Approx Reason, 2014,55(1):142-155.

[ 8 ]CHENG Y,ZHAN W,WU X,et al. Automatic determination about precision parameter value based on inclusion degree with variable precision rough set model[J]. Inform Sci, 2015,290(C):72-85.

[ 9 ]SUN B,MA W,ZHAO H. Decision-theoretic rough fuzzy set model and application[J]. Inform Sci, 2014,283(5):180-196.

[10] LIANG D,LIU D. Systematic studies on three-way decisions with interval-valued decision-theoretic rough sets[J]. Inform Sci, 2014,276(C):186-203.

[11]ZHENG K,HU J,ZHAN Z,et al. An enhancement for heuristic attribute reduction algorithm in rough set[J]. Expert Systems with Applications, 2014,41(15):6748-6754.

[12]WANG C,SHAO M,SUN B,et al. An improved attribute reduction scheme with covering based rough sets[J]. Applied Soft Comput, 2015,26(C):235-243.

[13]LI B,CHOW T W S,TANG P. Analyzing rough set based attribute reductions by extension rule[M]. Elsevier Science Publishers, 2014.

[14]AHA D. UCI Machine Learning Repository[EB/OL]. [2017-03-22]. http://archive.ics.uci.edu/ml.

[15]University of Waikato. Machine Learning Group at the University of Waikato[EB/OL]. [2017-03-22]. http://www.cs.waikato.ac.nz/～ml/weka.

Intelligent decision model based on optimization simulated annealing algorithm

XIAHui

(Software College, Shenyang Normal University, Shenyang 110034, China)

Decision theory is widely used in industrial production, management decision-making, safety and other fields, which has become more and more hot reserch issues for researchers. Three-way decision-theoretic rough set model is a probabilistic rough set model. It call derive several other probabilistic rough set models by setting corporate cost functions. Considering decision optimization of rough set constructing model and minimization cost of the decision, the research will give an optimized simulated annealing algorithm(OSAA)and an adaptive algorithm for a minimum cost attribute reduction. A heuristic approach combined with the coarse-grained parallel algorithm are proposed to solve the problem of optimization DTRS.Experiments designed for the optimization simulated annealing algorithm and adaptive learning method are in comparing with the running time and decision-making cost. The optimization representation can bring some new insights into the research on decision-theoretic rough set model.

decision-theoretic rough set model; simulated annealing algorithm; cost function; decision threshold; Parallel computation model

2017-01-16。

遼寧省科技廳自然科學基金資助項目(2014020118); 教育部“本科教學工程”本科專業(yè)綜合改革試點專業(yè)(ZG0103); 遼寧省教育廳高等學?？茖W研究項目(L2012388,L2014441)。

夏 輝(1979-),男,遼寧沈陽人,沈陽師范大學副教授,碩士。

1673-5862(2017)03-0311-04

TN929

A

10.3969/ j.issn.1673-5862.2017.03.010