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

夏 輝

(沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

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

夏 輝

(沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

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

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

0 引 言

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

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

1 決策粗糙集模型

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

1.1 決策粗糙集理論研究

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

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

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

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

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

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

1.2 Pawlak約簡(jiǎn)理論模型[10-13]

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

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

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

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

2.1 并行計(jì)算模型框架

2.2 構(gòu)建OSAA模型

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

圖2 并行退火過(guò)程中馬爾可夫鏈的生長(zhǎng)與變化

3 仿真實(shí)驗(yàn)和結(jié)果分析

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

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

2) 優(yōu)化的代價(jià)最小目標(biāo)的簡(jiǎn)約屬性算法驗(yàn)證。

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

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

表1 2種算法運(yùn)行時(shí)間對(duì)比

表2 2種算法決策代價(jià)比較

4 結(jié) 語(yǔ)

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

[ 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]. 小型微型計(jì)算機(jī)系統(tǒng), 2013,34(11):2603-2606.

[ 5 ]王玉梅. 基于模擬退火算法的遞歸自動(dòng)閾值分割方法[J]. 光學(xué)與光電技術(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。

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

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

1673-5862(2017)03-0311-04

TN929

A

10.3969/ j.issn.1673-5862.2017.03.010