一类最小代购模糊决策系统模型

一类最小代购模糊决策系统模型

近年来，模糊模糊理论被广泛应用于人工智能、知识发现、决策分析等智能信息系统领域。该理论的完善已成为促进粗野理论方面的主要趋势之一。在模糊粗糙集理论的实际应用中,如何充分考虑信息系统中属性信息的获取代价(诸如时间成本、经济成本等),从系统分析中得到最小代价的决策规则,有着重要的研究价值。例如,某大型机电系统诊断信息的获取,应充分利用那些获取方式简单、采集成本低、实时性要求低的属性;避免应用那些获取方式复杂、采集成本高、实时性要求高的属性1最小成本预算模糊决策系统1.1模糊决策约简的生成定义1包含度刻画了2个模糊集合之间的关系,而粗糙模糊集的上/下近似只是包含度的特殊情形。包含度在实际应用中,可以根据需要给出具体的定义,例如:令论域U上模糊集合的全体为F(U),U上经典集合的全体为P(U)。定义2设S=〈U,R,V,W,f〉为一知识表达系统,U是论域;R=A∪D,A∩D=Ø,A∈P(U)为条件属性集,D∈F(U)为模糊决策属性集;V为属性值的集合;W为与条件属性的一一对应,且所有元素均为正实数的权值集合,它反映了条件属性的代价;f:U×R→V是一个信息函数,它指定U中每一个对象x的属性值。称S为属性加权模糊决策信息系统。对于加权模糊决策信息系统,令则R设D是F(U)的包含度其中,r为决策属性的个数。有模糊决策规则:对于x从决策协调集定义3S=〈U,R,V,W,f〉为属性加权模糊决策信息系统,若对于任意x定义4设最小代价模糊决策系统S的决策协调集构成的集合为S则称B命题最小代价模糊决策系统S的最小代价属性协调集B,则B一定是S的决策约简,且为最优决策约简。证明反证法。假设最小代价决策协调集B不是S的决策约简,则必存在决策协调集B′=B-{b1.2a推的a推理定理1最小代价模糊决策系统S=〈U,R,V,W,f〉,则B是S的决策协调集,当且仅当推论1分辨矩阵中所有元素Q证明B满足∪a推论1结合定义3和定义4,有以下推论。推论2集合B为最优决策约简的充要条件为:集合B满足∪令矩阵Q中元素的个数为m,条件属性的个数为n。上述问题可通过信息表进行描述:将集合S(a推论3如果变量y在集合B={a1.3属性的代价描述最小代价模糊决策系统模型同时包含了2个特点:一是能够对属性的代价进行描述;二是数据的重要性通过模糊隶属函数进行描述。这样使模型具有更加广泛的适应性。2般约简更难求解由于附加了代价最小的约束,最优决策约简比现有一般约简更难求解。最优决策约简为NP完全问题,从理论上讲它在多项式时间只能获得最优解或近似最优解,下面给出了3种算法并进行了分析比较。2.1最优决策约简的求解采用分辨矩阵与布尔运算结合的方法,极小析取范式中的所有合取即为系统的所有决策约简。将所有决策约简代入式(5),得到代价最小的决策约简,从而求得最优决策约简。采用基本算法可以获得最优解,但当论域中元素个数和属性较多时,计算量相当大;因此在实际应用中受到一定的限制。2.2市售出的最优决策是否会选择模式贪婪算法是解决最优化问题的一种基本方法,它将全局最优问题进行了转化,通过逐步构造最优解的方法,在每个阶段都做出一个在贪婪准则下的最优决策;而不考虑在最后看来这种选择是否合理。贪婪算法只能获得问题的最优解或近似最优解。求解最优决策约简的贪婪算法:在循环过程的每一步中,算法从当前从未选中的所有条件属性中,计算每个属性的有效代价α,并选择α最小的属性加入到约简Reduct中,直到满足∪a采用贪婪算法求解最优决策约简的优点在于该算法计算量较小,因而能够在实际应用中快速求解,尤其是当属性矩阵Q的维数较大时。2.3子梯度方法及求解由推论3求解最优决策约简,其实质是未知量为整数的线性规划问题,即整数规划。整数规划比通常的线性规划更难求解,迄今求解整数规划其基本求解思路都是按一定的搜索规则,在整数规划的线性松弛模型的可行域内寻找出整数最优解,因此需要更多时间。在此,研究如何通过基于拉格朗日松弛的子梯度优化算法求解最优决策约简。拉格朗日松弛法使用拉格朗日乘子向量将关联约束形成对偶问题,使关联约束解除,从而使问题简化。其中,Y=[y令列向量W这样才能保证式(9)中λ确定的情况下L(Y,λ)获得极小值。由拉格朗日对偶原理,将代价最小化问题转化为求使对偶函数最大的问题。子梯度法是通过对梯度的改进而产生的一种分步梯度法,它能够快速地收敛在最优解附近。L(Y,λ)为凹函数,若向量G=[g则G为L(Y,λ)在λ采用子梯度方法求解最优决策约简,步骤如下:步骤1根据2.2节中的定理和推论获得属性矩阵P,初始化拉格朗日乘子其中,P步骤2获得最优或近似最优的乘子λ:(1)根据拉格朗日代价,计算当前解Y;(2)计算当前的子梯度向量G;(3)更新当前拉格朗日乘子如下式所示:其中,L(4)步长调整及收敛判定:如果连续t次迭代L(Y,λ)的方差σ大于预设步长调整参数γ,则步长ρ缩减为0.5ρ,跳转到(1);如果方差σ小于预设收敛判定参数ξ或者迭代次数到达预设的最大迭代次数LP1,则认为拉格朗日乘子收敛。步骤3计算当前解Y:(1)判断是否P中所有行都满足PY≥1,若不满足,则对所有不满足条件的行,按照贪婪算法的原理逐个加入有效代价α最小的列,直至满足条件。(2)保存当前的解,及其对应的最小代价值。(3)算法终止判断:若从步骤2～步骤5的循环次数未到达预设次数LP2,继续;否则,从已保存的LP2个解中,代价最小的解为算法最终解,终止程序。步骤4对满足设定条件的列固定:从对拉格朗日代价小于阈值η的列中,选择必选列(如果P中某一列的所有数值为1的元素对应的所有行中,存在行和为1的行,那么给定列为必选列)进行固定。步骤5更新拉格朗日乘子λ:已固定列对应的拉格朗日乘子保持不变,对余下的乘子进行随机更新:其中,ε为在某个区间的随机数。步骤6跳转至步骤2。3求解质量分析实验在主频2GHz的P4计算机上进行,编程环境为Matlab6.1。随机生成满足行和大于等于1的属性矩阵P从图1可观察到:子梯度优化算法获得相对最优次数的百分比要高于贪婪算法,其平均值分别为79.80%和34.9%;因此,子梯度优化算法的求解质量要优于贪婪算法,但它需要更长的运行时间,如n=90时梯度优化算法与贪婪算法的平均运行时间分别为65s和0.1s。从总体趋势上,随着属性矩阵维