基于Pawlak算法的物流选址指标建模研究
- 格式：doc
- 大小：16.50 KB
- 文档页数：3
龙源期刊网 http://www.qikan.com.cn
基于Pawlak算法的物流选址指标建模研究
作者：张丽岩 马健 孙焰
来源：《物流科技》2014年第02期
摘 要：文章从物流节点选址指标体系的复杂性入手，提出以Pawlak算法对指标体系进行
约简，简化了物流选址的复杂性。并通过实例展示该算法在物流选址中的应用，结果表明该算
法是可行和有效的，并具有很好的实际应用价值。它为物流节点选址问题的解决提供了新的可
行途径和有效手段。
关键词：物流节点选址；指标建模；属性约简；Pawlak算法
中图分类号：F252.14 文献标识码：A
Abstract： The paper proposes simplified method about the index system of logistics node
location using the Pawlak algorithm， which can reduce the complexity of decision of logistics node
location. It demonstrates the algorithm by example in logistics application field， and the results show
that the algorithm is feasible， effective and good practical value. It provides a novel feasible way and
effective means to solve the logistics node location problem.
Key words： logistics nodes location； index modeling； attribute reduction； Pawlak
algorithm
0 引 言
物流节点选址属于物流系统规划的一个关键组成部分，它可能决定或者影响着物流系统的
层次结构、模式特点和网络拓扑等[1]。描述一个物流选址系统所采用的指标越多，描述就越
详尽，但是，若物流选址的指标体系过于庞大繁芜，便会使决策评价过程变得异常复杂；并且
过多的指标将占用大量计算成本，并增加问题的复杂性。通过属性约简将指标体系进行简化是
做出低成本的科学合理选址决策的重要途径之一，然而，寻求指标体系的所有约简或最小约简
已被证明是NP-hard问题[2]，这为解决该问题提出了新的挑战。Pawlak算法作为属性约简的
一种经典方法，为物流节点选址指标建模研究提供了有效手段。
在选址指标体系中，各个指标属性的重要程度通常是不一样的[3]。要确定某属性或属性
集的重要性，可以根据指标属性构成的变化所引起的决策表分类变化的程度来度量。若变化程
度大，说明该指标重要性大；反之，重要性低。这样就可以在不影响决策分类的前提下，用尽
量少的属性来简化决策表，以达到降低成本的目的。
1 Pawlak算法的基本原理
龙源期刊网 http://www.qikan.com.cn
利用指标属性重要性进行指标约简主要有“添加法”和“去除法”。“添加法”是从某一个指标
属性入手，逐次添加一个或多个指标属性形成不同的组合集，直至求出最小约简为止。“去除
法”是从所有指标属性构成的组合入手，逐次去除一个或多个指标属性形成不同的组合集，直
至求出最小约简为止。Pawlak算法属于“添加法”，在具体的求解过程中，需要利用知识的依赖
度等概念来确定指标属性的重要度，下面简单介绍该方法的一些基本概念：
（1）必要和不必要属性：R为一族等价关系，a∈R，如果：indR=indR-a，则称a为R中
不必要的；否则称a为R中必要的。如果每一个a∈R都为R中必要的，则称R为独立的；否
则称R为依赖的[4]。
（2）约简和核：设Q？哿P，如果Q是独立的，且indQ=indP，则称Q为P的一个约
简。P中所有必要关系组成的集合称为P的核，记作coreP。有coreP=∩redP，其中redP表示P
的所有约简，即所有约简的交集为核[4]。
（3）知识的依赖性和属性的重要性[4]：设δ为属性的重要度，k为知识的依赖度，知识
库为S=U，A，V，f，且P，Q？哿R，R为U上的等价类，当k=γ■Q=pos■QU时，称知识Q
为k0≤k≤1度依赖于知识P，记作P？圯■Q。其中γ■Q是Q和P间的依赖度；pos■Q为Q的P
正域；pos■Q、U分别表示pos■Q、U二个集合的基数；A=C∪D，C∩D=？覫，属性a∈C关
于决策D的重要性定义为：sig■a=γ■D-γ■D。
2 基于Pawlak算法的属性约简步骤
在利用Pawlak算法对选址决策表进行相关的属性约简操作时，是以属性重要性概念为基
础的。首先，需要计算出选址决策表的相对核；其次，比较相对核是不是选址决策表的一个约
简，如果相对核不是选址决策表的一个约简，则利用“添加法”，逐次优先添加重要性大的非核
属性，直至得到最小约简为止。具体步骤如下[5]：
输入：DT=U，C∪D，V，f
输出：相对约简B。
Step1：根据指标属性的重要性，计算得出决策表DT的相对核CORE■C。
Step2：将核CORE■C赋予约简B，即B=CORE■C。
Step3：判断上一步的结果是不是决策表的约简，pos■D=pos■D，若是，算法结束，跳到
Step7；否，执行下一步。
Step4：？坌c■∈C/B，计算sigc■B=pos■D-pos■D，求c■=arg■sigc■，B。
Step5：令B=B∪c■。
龙源期刊网 http://www.qikan.com.cn
Step6：如果pos■D≠pos■D，则跳至Step4；否则，跳至Step7。
Step7：输出B。
3 算法示例
针对某一物流节点进行选址，有6个候选节点can■，can■，can■，can■，can■，can■，
条件属性分别为a■，a■，a■，a■，a■，为方便问题分析，将问题进行简化，各个属性指标进
行了模糊化，假设条件属性的等级为0、1或2，分别代表低、中、高三个层次；而决策属性d
为评价结果，包括不推荐与推荐两种情况，分别用0和1表示。为了研究问题，将该问题描述
为：
设决策表：DT=U，C∪D，V，f，C∩D=？覫，C称为条件属性集，D称为决策属性集。
论域U
=can■，can■，can■，can■，can■，can■，条件属性集C=a■，a■，a■，a■，a■，决策属
性集D=d。具体数据见表1。
根据等价类和正域的定义可得：U/INDD=can■，can■，can■，can■， can■，can■；
U/INDC
=can■，can■，can■，can■，can■，can■；pos■D=can■，can■，can■，can■，can■，
can■。
（1）根据属性的必要性求决策表的相对核
U/INDC-a■=U/INDC，U/INDC-a■=U/INDC，U/INDC-a■=U/INDC，U/INDC-
a■=U/INDC，U/INDC-a■≠U/INDC。
得到属性a■在决策表DT中为必要属性，所以，核coreDT=a■。 （下转第21页）
