基于优化模拟退火算法的智能决策模型

夏 辉

(沈阳师范大学 科信软件学院, 沈阳 110034)

基于优化模拟退火算法的智能决策模型

夏 辉

(沈阳师范大学 科信软件学院, 沈阳 110034)

决策理论在工业生产、管理决策、安全生产等越来越多的领域得到广泛应用,已经成为越来越多的研究者研究的重要课题。三支决策粗糙集模型作为一个重要的概率型粗糙集模型,在给定损失函数情况下可以导出多种概率型粗糙集模型,针对决策粗糙集模型构建的最优化问题,考虑到决策成本最小化,提出一个优化的模拟退火算法和启发式算法,从而得到代价最小的属性约简集,研究阐明了一种将粗粒度并行优化方法和启发式学习方法结合,解决粗糙集决策优化问题。实验证明提出的模拟退火的优化DTRS模型算法具有良好的有效性,运行时间也短于自适应算法,而且学习到的阈值能够得到较小的决策风险代价。研究揭示了优化表示带来的一些新的见解,对决策粗糙集模型的研究提供了新的思路。

决策粗糙集模型; 模拟退火算法; 代价函数; 决策阀值; 并行计算模型

0 引 言

实际应用中,决策粗糙集的代价函数的定义是有明确规定的,在决策粗糙集模型中需要六个代价函数值,而其他的一些概率粗糙集模型往往只需要一个参数即可,从实用性角度来看,决策粗糙集模型使用起来要比其他模型复杂得多,针对这一问题,Herbert等[1]从博弈论角度分析决策粗糙集模型,并且对代价函数值进行一些调解,使得目标函数逐步达到最优化。然而该方法有个缺陷:使用者首先要给出所关注的优化目标,而且需要在迭代中多次参与到学习中,这样就要求使用者具备一定领域的先验知识;为此,Yao[2]也提出了三支决策模型,但同样面临着阀值需要依靠经验和实验获取问题,因此对先验知识要求较高,这样就会导致现实中很难实现。Jia[3]提出了使用模拟退火算法解决决策代价,同时较好地解决了决策效率问题,因此决策问题就可以间接地转化为利用模拟退火算法进行解决,由于模拟退火算法具有较好的数学性质,即以概率1 收敛于全局最优值,而且算法也和具体问题无关,所以它被广泛地应用于各种组合优化问题。然而,模拟退火算法[4-5]也具有NP问题,它收敛速度较慢,运行时间较长,且算法性能和初始值有关等,这些缺点使它在实际应用中具有较大的瓶颈。

本文克服了模拟退火算法的缺点(内在串行性)并且与“下山法”相结合,同时综合了一些优化方法,使原来的模拟退火算法得到可扩展的并行效果,进而大大提升了算法的收敛速度,同时克服了算法性能对参数及初始值的过分依赖,最后得到了最优的决策阀值,进而提升了决策模型的应用效率。

1 决策粗糙集模型

根据贝叶斯决策流程和 DTRS模型[6-9]构建决策优化系统模型,并且构建决策阀值因子与决策代价的函数关系。

1.1 决策粗糙集理论研究

首先创建决策模型,根据决策模型最小代价表示出决策阀值;然后根据贝叶斯决策流程推导出最小化代价决策规则;然后通过一定的约简规则,表示出代价模型;最后根据设定条件的决策表达式和给定阀值,得到positive rule,boundary rule和negative rule三支决策规则的代价函数,并且累加这三支决策代价函数,从而得到总的代价函数。

1) DTRS决策模型参数

根据经验值,一般可以得到代价函数满足:λPP≤λBP<λNP和λNNλBN<λPN,即:对于属于W的对象w,把它划分到W正区域的风险代价要小于或者等于将它划分到边界区域的风险代价；而且二者的风险都要小于其划分到W负区域的风险代价,同理,对于不属于W的对象w,将其划分到W负区域的风险代价要小于或等于将其划分到边界区域的风险代价；并且二者的风险代价都小于将其划分到W正区域的风险代价。不妨可以令下面3个等式成立,并且损失函数之间的可以假定,α∈(0,1],β[0,1)和γ(0,1)。

其中,λPP,λBP和λNP分别表示当对象属于某个状态C时所采取P,B,N行动后的代价,同样λPN,λBN和λNN分别表示当对象不属于某个状态C时所采用的P,B,N行动后的代价。

2) 构建决策代价函数模型

图1 DTRS决策代价函数模型表示流程

1.2 Pawlak约简理论模型[10-13]

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

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

2 粗粒度并行计算的优化模拟退火算法

优化模拟退火算法基本思想:OSAA(优化模拟退火算法)决策模型是在原有经典模拟退火模型基础上做重大的并行化改进的同时,结合了下山法快速收敛的特点,它是一种可扩展的大规模并行计算方法。

2.1 并行计算模型框架

2.2 构建OSAA模型

参考经典退火算法思想,初始化 OSAA时间表,构建一个适应度函数f(R),R为约简属性集,设定一个初始温度t0, 记录退火次数N,通过比较COSTNEW和COSTOLD的大小关系确定当前解COSTc,每一次比较完后,都要以某个概率因子去调用下山函数DownHill(COSTc),设计模型策略为:多次退火无进展后找到的较优解采取高的下山概率,从而真正找到全局最优解,而不是局部最优解,并且要和其他的计算结点进行通信,比较彼此的最优解,从而达到并行运算的效果。本算法引入并行计算模型,本文算法对经典退火算法进行优化。该并行算法是在多个串行算法得到马尔可夫链中选择收敛速度最快的一个,同时去除了其他的链,基于此,从同一起点,又重新计算多条马尔可夫链,图2即为并行退火过程中马尔可夫链的生长与变化。

图2 并行退火过程中马尔可夫链的生长与变化

3 仿真实验和结果分析

使用UCI(University of California-Irvine)[14]数据集的若干组数据进行实验,将相应的算法集成实现在WEKA平台[15],进行数据的验证,实验主要验证以下决策理论的2个方面:

1) 优化模拟退火算法(OSAA)和自适应算法进行对比,分别从运行时间、最小代价、算法复杂度进行对比;

2) 优化的代价最小目标的简约属性算法验证。

实验采用的机器设备是IntelCore i7-3770处理器,8 G的内存,64位的Windows10操作系统,本系统算法使用的是基于Weka平台。平台实验数据是从UCI数据库中的5个数据集。实验结果如表1所示,使用了基于自适应算法Alcofa和模拟退火算法这2种算法来求得的决策阈值所作的决策风险代价,而表2体现出自适应算法以及模拟退火算法的平均运行时间(单位:ms)。

从表1的数据来看,本文提出的模拟退火算法在这5种数据集上运行速度都要比自适应算法的更快,展示了模拟退火算法具有更高的效率。然而对于自适应算法Alcofa,它是一种迭代的算法, 该算法的时间复杂度是O(n2),它需要计算训练集中每个样本。然而本文提出的模拟退火算法却是一种随机的算法,运行时间和参数的设置有关,如果参数设置合适,那么运行速度将很快。从表2中数据可以看出,本文提出的模拟退火算法在这5种数据集中可以获得很小的决策风险代价。

表1 2种算法运行时间对比

表2 2种算法决策代价比较

4 结 语

本文提出了一个优化的DTRS模型,优化的标准是基于最小决策代价,优化后的模型无需先验知识就可以学习到代价函数和决策阀值,和以往的学习方法相比具有较高的效率以及较低的决策风险,通过实验,本文提出的模拟退火的优化DTRS模型算法具有良好的有效性,运行时间也短于自适应算法,而且学习到的阈值能够得到较小的决策风险代价。

[ 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]. 小型微型计算机系统, 2013,34(11):2603-2606.

[ 5 ]王玉梅. 基于模拟退火算法的递归自动阈值分割方法[J]. 光学与光电技术, 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); 教育部“本科教学工程”本科专业综合改革试点专业(ZG0103); 辽宁省教育厅高等学校科学研究项目(L2012388,L2014441)。

夏 辉(1979-),男,辽宁沈阳人,沈阳师范大学副教授,硕士。

1673-5862(2017)03-0311-04

TN929

A

10.3969/ j.issn.1673-5862.2017.03.010