（计算机软件与理论专业论文）基于属性论的01背包问题算法研究.pdf

摘要 背包问题是一个在运筹学领域里常见的典型n p c 难题。工厂里的下料问题，管 理中的资源分配，资金预算，投资决策，装载问题等均可建模为背包问题。对该问题 的求解方法的研究无论是在理论上，还是在实践中都具有重要意义对于背包问题， 己有的求解方法可分为精确算法( 如动态规划，分支定界等) 和近似算法( 如贪婪法，蚂 蚁算法，遗传算法等) 两大类。因为精确算法的时间复杂性都是呈指数增长的，所以 从六十年代逐渐提出了一些近似算法。 属性论方法是冯嘉礼教授提出的人工智能领域的一种新的理论。目前在组合优化 问题、模式识别、非线性分类、质量评估模型、股票预测以及网络攻击探测等领域都 已经得到广泛的应用 在阅读了大量中外文献的基础上，本文提出了背包问题的一种基于属性论的启发 式算法文章在开篇综述背包问题的一些基本情况后，接着介绍了属性论的一些基本 观点、方法和理论，包括定性映射模型，人工神经元模型与定性映射模型的关系，量 质转换程度函数等等。随后结合贪婪算法和背包核问题的思想，我们给出了物件基于 核的一个定性映射在根据背包的核问题的具体情况对属性论中传统的g a u s s 型转换 程度作了必要的改进之后，我们给出了背包问题基于属性论的一个近似转化优化算法 并且根据此算法用j a v a 语言设计了背包问题软件包。软件包的设计充分结合了j a v a 语言的特点，具有高性能和高的可扩展性，提供了可扩展的接口以方便其他应用程序 扩展和调用。 作为软件包开发的一部分，我们结合背包问题实例的四种类型，设计了测试实例 生成器及背包问题优化程序。本文在文章的后面给出了实例运行的结果，从运行结果 来看，本算法的运行效率非常高，特别是对于最大子集和问题( s u b s e t - s u mp r o b l e m ) ， 我们求得一个1 0 万维最大子集和问题的9 9 7 满意度解的平均时间仅为9 5 “毫秒。 关键字：背包问题，核问题，属性论方法，定性映射，转化程度函数 ( a ) a b s t r a c t k n a p s a c kp r o b l e mi sat y p i c a ln p - h a 州i nt h eo p e r a t i o nr e s e a r c hf i e l d p r o b l e m si nc a r g ol o a d i n g ，c u t t i n gs t o c k 。b u d g e tc o n t r o la n df i n a n c i a lm a n a g e m e n t m a yb ef o r m u l a t e da sk n a p s a c kp r o b l e m s t h er e s e a r c ho fa ne 怖c i e n ta l g o r i t h m w i l lb es i g n i f i c a n tb o t hi nt h e r o ya n dp r a c t i c e g e n e r a l l ys p e a k i n g ，a l lt h ea l g o r i t h m s c a nb ec l a s s f i e di n t ot w ok i n d s ，o n ec a nb ec a l l e dt h ee x a c t a l g o r i t h m s s u c ha st h e d y n a m i cp r o g r a m m i n ga n db r a n c h - a n d - b o u n dm e t h o d t h eo t h e r sa r ea p p r o x i m a t e o n e s ，s u c ha st h ea n ta l g o r i t h m g r e e d ya l g o r i t h ma n de v o l u t i o n a r ya l g o r i t h m a s t h ee x a c ta l g o r i t h m sa l lr u n si ne x p o n e n t i a it i m e m a n ya p p r o x i m a t ea l g o r i t h m sh a s b e e nd e v e l o p e ds i n c e1 9 6 0 s a f t e rt h ei n ”o d u c t i o no fk n a p s a c kp r o b l e m ，w ef o c u so nt h eb a s i cp o i n t s 。 m e t h o d sa n dt h e r o j e so fa t t d b u t et h e o r y t h e n t h eq mo fi t e m so nt h eb a s i so ft h e c o r eh a sb e e ni n t r o d u c e dw i t ht h et h o u g h t so fg r e e d yt h e o r i e sa n dc o r ep r o b l e m 价e o t i e s a f t e rf h ea l t e r n a t i o no ft h eo r d i n a r yg a u s sc o n v e r t i o nd e g r e ef u n c t i o n w e p r e s e n ta na p p r o x i m a t ea l g o r i t h mb a s e do nt h ea t t r i b u t et h e o r y a n dt h e n a s o f t w a r ep a c k a g ei sp r e s e n t e di nj a v a t h ed e s i g na n di m p l e m e n t a t i o no ft h e p a c k a g ee m b o d ym a n yf e a t u r e so ft h ej a v ap r o g r a m m i n gl a n g u a g e a n dt h e p a c k a g ec a nb ee a s i l ye ) ( c e n d e dw i t hag o o da p i a sap a r to ft h ep a c k a g e ，w ed e s i g n e dt h ek n a p s a c kp r o b l e mi n s t a n c e g e n e r a t o ra n dt h ek po p t i m i z a t i o nt 0 0 1 a f t e rh u n d r e d so ft e s t s w eg i v eo u tt h e s t a t i s t i c so f 仇es o l v i n gr e s u l t so ft h e4k i n d so fk pi n s t a n c e s w h i c hs h o wt h e e f f i c i e n c yo fo u ra l g o r i t h m t h ea v e r a g es o l u t i o nt i m eo fak pw i t h1 0 0 t h o u n di t e m s i so n l y9 5 6 4m i n i s e c o n d s y a n g f a nz h e n g ( c o m p u t e rs o f t w a r ea n dt h e o w ) d i r e c t e db yp r o fj i a l if e n g k e y w o r d s ：k n a p s a c kp r o b l e m ，c o r ep r o b l e m ，q u a l i t a t i v em a p p i n g ，c o n v e r s i o n d e g r e ef u n c t i o n 论文独立性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中做了明确的声明并表示了谢意。 作者签名： 论文使用授权声明 日期： 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全文或部分内容，可以采用影印，缩印或其他复制手段保存论文。 保密的论文在解密后遵守此规定。 作者签名：。目蚰师签名：三越日期： 砖 8 基于属性论的o 1 背包问题算法研究 第1 章引言 本章将首先从背包问题的历史背景谈起，讲述什么是背包问题，各类背包问题的 数学模型与应用，随后讨论0 - 1 背包问题的代表性和重要理论价值，最后叙述文章的 结构和本文的主要工作和创新点。 1 1 历史背景 背包问题( k n a p s a c k p r o b l e m ) 在5 0 年代末期被d a n t z i 1 首次提出之后。在近年来 被广泛的研究。这不仅是因为背包问题在工业和金融投资领域能得到直接的应用，更 是因为很多理论上的原因。很多整数规划的问题的解决都依赖于一个高效的背包问题 解法( 在这些整数规划问题中，每当需要定界的时候我们都需要解决一个背包子问 题) 【z l ，因此，一个高效的背包问题解法就显得非常有必要。 所有的背包问题都可以定性的描述为，从给定的物品集合中选择出一个子集，在 不超出所有背包的负载的前提下，实现利益最大化。背包问题的不同种类的判定，是 根据物品和背包的类型1 3 1 ：在0 - 1 背包问题( o lk n a p s a c kp r o b l e m ) 中，每一个物品最 多被选择一次，而与之相对应的有界背包问题( b o u n d e d k n a p s a c k p r o b l e m ) 中能选择的 物品数则可以在某个范围内取值；再比如多选择背包问题( m u l t i p l e c h o i c ek n a p s a c k p r o b l e m ) 是说某几个物体必须选择一个或多个，而多背包的背包问题( m u l t i p l e k n a p s a c k p r o b l e m ) 则是说某些背包必须同时被装满。在这些背包问题家族中，最通用 的形式是多条件约束背包问题( m u l t i - c o n s t r a i n e d k n a p s a c k p r o b l e m ) ，而这在实质上就 是正系数的整数规划问题( i n t e g e rp r o g r a m m i n g ) 。在1 2 中我们将给出各种背包问题 的数学模型。 背包问题属于组合最优化问题1 4 一般的，最优化问题( o p t i m i z a t i o np r o b l e m ) 由 目标函数( o b j e c t i v ef u n c t i o n ) 和约束条件( c o n s t r a i n t s ) 两部分构成： 2 1 m i n i m i z e ，( x ) = ( 工l x 2 ，勘) s u b j e c t t o x = o n ，x 2 ，知) sc x ”一7 将满足所有约束条件的解空间s 称为可行域( f e a s i b l er e g i o n ) ，可行域中的解称 为可行解( f e a s i b l es o l u t i o n ) ；将可行域中使目标函数最小的解称为最优解( o p t i m a l s o l u t i o n ) 对于最大化问题，可将目标函数乘以( 1 ) ，转化为最小化问题求解。当x 或 s 为离散集合构成的解空间时，这类最优化问题称为组合最优化问题( c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m ) 1 2 1 基于属性论的o - 1 背包问题算法研究 衡量一个算法的好坏通常用算法中的加、减、乘、除和比较等基本运算的总次数 同实例在计算机中计算时的二进制输入数据的大小关系来度量嘲。我们对实例的二进 制输人长度和算法的基本计算总次数是粗略估计的，一般是给予个上限。一个求解 实例，的算法的基本计算总次数c 同实例，的计算机二进制输入长度a c x ) 的关系常用 符号c 圆= 甜功= 0 偿扛婀w 表示。它的含义是：求解实例，的算法的基本计算总次 数c 何是实例输入长度讲= 【i 的一个函数，这个函数被另一个函数删控制，即存在一 个函数删和一个正常d 使得： c ( j ) 口g ( d ( ，) ) ( 1 1 2 ) 其中g 例的函数特性决定了基本计算总次数的性能t o 。 定义1 1 1 7 1 ： 假设问题和解决该问题的一个算法己经给定，如给定该问题的一个实例l 存在 多项式函数g 似，使得成立，我们称该算法对实例，是多项式时间算法；若存在g 似 为多项式函数且对该问题任意的一个实例l 都有( 1 - i - 2 ) 成立，则称该算法为解决该 问题的多项式时间算法。 定义1 - 2 1 7 1 ： 对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项实函 数刖砂和常数a ，使得对给定优化问题的任何一个实例成立，则称给定的优化问题是 多项式时间可解问题，或简称多项式问题，所有多顶式问题集合记为p ( e o t y n o m i a o 。 并不是所有的组合最优化问题郁找到了求解最优解的多项式时间算法也就是 说，还不能肯定一些组合最优化问题是否属于p 经过几代数学家的努力，他们研究 整理了一类难以求解的组合最优化问题，迄今为止，这些问题还没有一个有能求得最 优解的多项式时间算法这一类组合最优化问题归为所谓的n p - h a r d , 受人类认识能力 的限制，目前人们只能假设这一类难解的组合最优化问题不存在求解最优解的多项式 时间算法。 所有的背包问题都属于n p - h a r d 问题1 8 1 ，这就是说我们设计出背包问题的多项式 时间算法的可能性非常小。也即是说对于背包问题而言，我们除了枚举整个解空间而 外就无法求得背包问题的精确解【3 l 。然而，下面的一些技术的应用，使得我们的枚举 可能变得相对容易一些，这些技术也是目前大多数算法设计思想的一个小结： 分枝定界1 ( b r a n c h - a n d - b o u n d ) ：几乎是一个完整的枚举嘲，只是使用上下界“剪 分支定界法由k o 如s a r 在1 9 6 7 年首次提出至今在背包问题研究中被频繁的使用 基于属性论的0 1 背包问题算法研究 枝”的方法避免扩展了一些不可能导出最优解的结点【1 0 1 1 1 i 动态规划( 功口咖p ，理，扭聊m 嘲f 1 2 l ：动态规划的方法是在宽度优先搜索的基 础上添加了一些优先规则。有的时候也可以加入边界测试，因此，动态规划 方法在某些时候可以看作分枝定界的改进版本i 堋。 状态空闻松弛( s t a t es p a c er e l a x a t i o n ) ：在可能牺牲优化质量的前提下，减少 状态空间的大小，从而极大地减少算法的时间复杂度和空间复杂度。目前背 包问题的很多高效近似解法都来源于此种思想。 预处理( p r e p r o c e s s i n g ) , 通过一些特别的测试能预先确定出在最终的最有的解 向量中某些决策变量的取值，从而事先把他们排除在外，减小问题的规模 与其它的算法设计者类似，本文作者在算法的设计中也用到了这些思想。 1 2 背包问题各种形式的数学模型 通过阅读文献，作者将在本节将给出七种类型的背包闻题的数学定义。这些类型 基本上涵盖了大多数的常规应用。 在这些类型的背包问题中，我们用力表示选择物品，获得的效益；用 i ! ，表示物 品，的重量；物品需要放在承重能力为c 的包裹中。同时我们还约定，所有这些系数 胁，晰和c 都是正整数。 ( 一)0 1 背包问题( d jk n a p s a c k p r o b l e m ) 1 1 8 l o 1 背包问题是从有p 1 个物品的物品集选取一个子集，在总体积不超过包裹 容量c 的前提下，使得相对应的利益实现最大化。可以用以下的公式进行形式化 的描述： f m a x i m i z e 乙p i x j 户l s u b j e c tt o 一_ s c ，( i - 2 1 ) 产i e o ，1 ) ，- ，= 1 ， 其中如果选择物品，那么决策变量习取1 ，否则取0 ( 二)有界背包问题”7 l ( b o u n d e d k n a p s a c k p r o b l e m ) 物品，最多可以选择竹个，那么有界背包问题可以描述为： 基于属性论的0 - 1 背包问题算法研究 m a x i m i z e p j x j j - i s u b j e c t t o 一_ s c ，( 1 - 2 2 ) 产1 0 , i ，0 ) ，= 1 ，卯， ( 三) 无界背包问题f 1 8 i ( u n b o u n d e d k n a p s a c k p r o b l e m ) 无界背包问题实际上是有界背包问题的扩展，每个物品可以任意的取。 m a x i m i z e 乃- j ，l s u b j e c t t o w , x j c ， t o 整数，_ ，- - 1 , ，n ， ( 1 - 2 - 3 ) 但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实 际上它仍旧是一个有界背包问题 ( 四) 多选择背包问题1 1 口l t 2 0 】( m u l t i - c h o i c e k n a p s a c k p r o b l e m ) 多选择背包问题是0 一l 背包问题的另外一种扩展。扩展不是针对数目进行的， 而是针对物品的类型也即是说，从k 类物品m f j = j ，夥中选择出物品，使得最 终的总获益最大。数学定义如下： m a x i m i z e 乃勃 州e c t 协善荟勤如，0 - 2 - 4 ) 士i ii e 地 b = l ，j = l ，k ， 而e o ，1 ，i = 1 ，七，m 这里如果物品，被从第f 类中选择出来，那么决策变量妒l 。限定条件 _ = l ，f = j ，j i 保证了每类物品能且只能选择一个 e 肌 ( 五)最大子集和问题1 2 1 l ( s u b s e t - s u mp r o b l e m ) 如果0 - 1 背包问题中每个物品的历都和它的 i ! ，相等，就构成了最大子集和问 题。数学定义如下： - 4 - 基于属性论的0 - l 背包问题算法研究 m a x i m i z e 一_ 川 s u b j e c t t o m _ s f ，0 - 2 5 ) , i - i x ， o ，l ，j = l ，玛 ( 六)换零钱问题【2 2 ( c h a n g e m a k i n g p r o b l e m ) 这是一类经常碰到的问题，要从一堆具有面值w 1 ，w 2 ，w 。的硬币中拿出c 个 货币单位的零钱找给顾客，目的是使得给出的硬币个数最少其数学模型是： m i n i m i z e x j j = l s u b j e c tt o wjxj=c，(1-261 j = l o 整数，= l ，玎， ( - t z )多条件约束背包问题诩以c b 珊打口船d 厢研瑚威肋6 缸埘) 在1 1 中我们已经提到，多条件约束背包问题是背包问题的一般形式，它在 形式上，就是一个正系数的整数规划问题其数学模型如下； 占 l n a x l m l z e2 一p j x j 。 j i l s u b j e c t t o x j q ，i = l ，m ，( 1 - 2 7 ) 扣l x 1 0 整数，_ ，；l ，n ， 以上的这些类型的背包问题无论在理论上，还是在实践中都具有非常多的应用。 在理论上，背包问题是很多组合优化问题的子问题，背包问题研究上的任何一个 进步都会使得这些问题的解决受益。 在实践环节上，背包问题并不局限于装箱问题在投资问题中，某投资者用c 个 货币单位去做投资，有n 个项目可供选择，其中第，个工程的投入 = ，而能获得易的 利润。这样的投资问题就是一个o l 背包问题 除了以上描述的简单的应用之外，背包问题还更主要的应用于货物装载，股票投 资，预算控制，财务管理【2 3 l 等问题d 功话和胁，z w 甜1 5 1 根据最大子集和问题设计了 背包公开加密算法。m a r t e l l o 和乃1 3 l 证明了计算机中双处理器任务分配问题也是一 个最大子集和问题。 基于属性论的o 1 背包问题算法研究 1 3o - 1 背包问题 在1 1 中，我们曾经谈过，背包问题可以看成普通整数规划问题的特殊形式。非 常有意思的是，相反的情况也是成立的，也就是说，任何一个多条件的整数规划问题 都可以等价的转化为一个单条件的整数规划问题，继而转化为0 - 1 背包问题。 我们考虑下面的整数规划问题2 ： 算法1 l 洲 令： m a x i m i z ey p , x , ，_ l 删m 善m ( 1 - 3 - 1 ) j i l、一1 ， x j - - - - c 2 ， 柚 o a x js ”x j 为整数，= ， g ( 砷= c l 一m ， 3 = 1 ( 功= c 2 一j _ 因此，我们可以用下式给出g 的上下界： 0 - 3 2 ) c 1 一w i j u ，g ( 功c l 一嵋甜，( 1 - 3 3 ) j = tj = l 其中，我们定义嵋= m a x ，o ) ，吒= r a i n ，0 ) 取正数，l ，满足 a m a x c i - z w t 。j i i ，- - c t + 吒”j 0 - 3 - 4 ) j z ll 因此，有i g ( 曲i 名，我们将( 1 3 1 ) 中的第二个约束乘上 并且加到第一个约束上， 2 此处之所以选择等式的形式，是因为不等式的情况可以通过忝加松弛变量成为等式( 此处的静没有要求大于o ) 基于属性论的o - 1 背包问题算法研究 就得到下面的问题： m a x i r i l i z e p j x j j 1 s u b j e c t t o ( w l ，+ 慨) - ；q + 他，( 1 - 3 5 ) j t 0 x q 一为整数，= 1 ，岛 定理1 1 2 4 】 如果选择满足( 1 3 4 ) 的j ，那么( 1 - 3 一1 ) 和( 1 - 3 5 ) 有相同的解集合。 l 证明】： 很明显，对于任意的因子 ，( 1 3 - 1 ) 的解都将是( 1 - 3 5 ) 的解因此我们只用证明 相反的情况。假设工是( 1 3 5 ) 的一个解，且令 0 ) = k ( 1 - 3 6 ) 很明显，置是一个整数，因为所有的系数都是整数。我们希望证明， 选择得出的 可以使得k = 0 注意，( 1 - 3 - 5 ) 中的约束条件也可以写成： g ( z ) + 砌( 力= 0 根据( 1 3 - 4 ) 0 - 3 - 7 ) 通过代入( 1 3 6 ) 我们可以得出g ( 砷+ 五k = 0 而根据( 1 3 - 4 ) ，有l g ( 列 a ，而且置 是整数，因此k = 0 根据0 - 3 6 ) ，风力卸，所以m 产o 因此，毒是( 1 - 3 - 1 ) 的可行解。 证毕。 我们反复的应用算法1 1 ，就可以将多个约束转化为单个约束。对于负系数的背 包问题，很容易转化为正系数背包问题【2 研，此处不加详述。 我们还可以看出算法卜l 的复杂度是线性的。因此，0 - 1 背包问题如果得到解决， 那么背包问题就能够得到解决。本文的研究就将基于o 1 背包问题，而不失一般性。 1 4 本文的结构和主要创新点 本文在研究了国内外大量文献的基础上，设计了一种基于属性论的背包问题近似 算法论文主要做了如下的工作： ( 一)对背包问题的实例进行分类，并在测试过程中设计相应的实例产生策略 ( 二)结合背包的核问题和属性论的相关理论，提出物件关于核的定性映射及 基于属性论的o 1 背包问题算法研究 核的模糊化 ( 三)给出背包近似核大小的估计。 ( 四)改进传统属性论中的g a u s s 型转化程度函数，以适应核问题的具体情况。 ( 五)充分运用转化程度函数和贪婪算法的思想，根据国外背包算法的统计规 律，设计转化优化算法。 o k )为算法运用j a v a 语言设计了易于扩展的软件包。 ( 七) 用大量测试实例验证了算法的有效性。 论文的创新点主要有以下五个方面： ( 1 ) 结合国内外背包的核问题的研究，提出物件关于核的定性映射模型。 ( 2 ) 给出近似核大小的估计 ( 3 ) 改进传统属性论的g 缸娜型转化程度函数。 ( 4 ) 运用转化程度函数和贪婪算法的思想，提出了核问题产生的原因的属性论假 设并根据此假设设计转化优化算法 ( 5 ) 提供了软件包的实现 本论文的结构安排如下： 第一章是引言部分，重点阐述背包问题的历史背景，数学模型，0 - 1 背包问题研 究的代表性和重要意义，背包问题的数据实例分析及论文的安排做论述； 第二章是论文的理论部分，主要对属性论方法做一个详细的论述，其中主要阐述 定性映射模型和转化程度函数； 第三章是论文的核心部分，着重讨论背包问题算法的设计原理，算法的过程，及 软件包的j a v a 语言实现。 第四章是给出测试实例产生策略及测试的结果； 第五章是算法的研究意义及下一步研究工作。 - 8 - 基于属性论的0 - 1 背包问题算法研究 第2 章属性论方法 本章将从属性论的定性映射模型谈起，继而讲述人工神经元与权重w 对定性基 准施行的内积变换，然后给出量质转化程度函数。而这一切，都是我们论文中背包问 题算法的理论基础。 2 1 引言 反映论认为，思维是外部事物状态、运动和变化规律在人脑中的反映，信息论则 认为思维是一个信息处理过程删我们的问题是：作为人脑思维信息的事物状态，运 动和变化规律是以怎样的形式和方法传递给人脑的? 或者说，人脑接收并处理这些信 息的机制是什么? 从哲学上讲，因事物有质和量的两种规定性，质是“使一事物区别于他事物的本 质特性( 性质) ”，“量是质的等级、规模和范围，是可用数和形加以表示的特性”所 以，不仅事物变化包括质变和量变两种，( 质量互变是它们之间的转化关系。) 而且， 人脑对外部事物的反映和认识也分定性和定量的两种。 而事物的质有多个方面，“事物在与其他事物发生关系时表现出来的质称做属性， 人们是通过观察，分析事物的属性来认识事物的质的。”所以，事物属性不仅表现着 它要表现的质特征( 或性质) ，而且，还拥有需要它界定和规范的量特征也就是说， 事物属性不仅具有质特征和量特征两种特征值，而且，事物的质变，量变和质量互变， 也只能以相应属性的质特征( 或性质) 变化、量特征变化，以及质量特征闻的转化 关系等形式分别表现或反映出来。 事实上，由于事物的任一( 空间、时间或其他某种指标) 状态可看作是事物的一种 属性( 性质) ，而运动和变化则可看作是事物的运动属性和相应属性质特征和量特征、 以及它们的某种变化，所以，我们可提出一个假设如下： 假设2 1 事物是以属性及其质、量特征变化反映自身状态、运动和变化等各种信 息的。 而感觉仅对其敏感的各种感觉属性做出反应的实验和经验事实则告诉我们： 命题2 1 人脑接收的信息只能是各种感觉属性 结合假设2 1 和命题2 i ，可得： 推论2 1 感觉属性是连接外部事物和人脑感觉的信息桥梁或纽带 推论2 2 人脑是在破译事物感觉属性，并将它们解读为关于事物的感觉映像、意 基于属性论的0 - 1 背包问题算法研究 识形象和记忆模式的基础上，再进一步加工和整理后，才建构起识别、判断、推理、 联想、评价、规划、决策、创造和发明等各种高级思维的。 如果以上述假设和推论作为本文的基本前提，则前面所提出的问题就可转化为： ( 1 ) 事物属性的质特征变化、量特征变化和质量( 特征) 互变的规律是什么? ( 2 ) 怎样对这些变化规律进行表示7 ( 3 ) 这些变化规律是怎样传递给人脑的? ( 4 ) 人脑接收、破译事物感觉属性的操作或机制是什么? ( 5 ) 人脑将事物属性及其变化信息解读( 或还原) 为关于事物的感觉映像、意识形 象和记忆模式的机制是什么? ( 6 ) 人脑调用事物感觉映像( i m a g e ) ，意识形象和记忆模式，并建构起各种高级思 维的机制是什么? 如果能弄清这些机制，就有可能提出一种既能描述事物通过其属性表现自身变化 规律的方法，还能用于模拟人脑解读事物属性变化、认识事物和世界，并智能地处理 各种事务的方法。我们称这种方法为思维建构和智能模拟的属性论方法，简称属性论 方法刚。 2 2 最简性质判断的定性映射模型 “对象无不具有一定的属性，判断对对象有所断定，就是肯定或者否定对象具有 ( 或不具有) 某种属性。”【33 】鉴于对象间的关系可看作是一种关系属性t 3 3 1 。或诸对象所 构成系统的一个整体属性1 3 3 1 ，所以本文所谓判断也包含关系属性和系统属性( 或性质) 判断。 性质分简单性质和复杂性质，所谓简单性质可定义为不能再对其进行分解的性 质，而复杂性质则可分两类：其一是由若干个简单性质p u ( o ) 合取而成的合取性质， 记为：p ，( o ) ：i 凡( o ) ，和可由若干个简单性质通过其它方式整合而成的复杂性质所 以，性质判断也分为简单性质判断和复杂性质( 或复杂关系) 判断 我们知道，事物有质和量的两种规定性，质和量之间有所谓质量互变规律：。只 有超过度的范围的量变才导致质的变化，而限于度的范围之内的量变不导致质变。” 【16 】该规律不仅诱导出事物属性量一质特征间的一个对应和转化关系，即：若属性量石 恰落在某质特征或性质p 的“度”或“基准”( c r i t e r i o n ，c 0 的范围内，则量x 所对 应的性质就是p ( 曲，而且还诱导出对象0 是否具有性质p ( 0 ) 的一个定性判断z p ( x ，印) ， 即：若对象。具有属性量z ，且j 恰落在质特征或性质p 的“度”岛范围内，则。具 有性质p ，记为p ( x ，0 ) 。否则口就不具有性质p ，记为! p 0 ，0 ) 在不产生混淆时， 基于属性论的o 1 背包问题算法研究 可分别简记为p & ) 和妒。 当性质昴g ) 的“度”或“基准”锄是一个区间( d ，酌时，所谓“限于度的 范围之内”可翻译为工( o 【f ，而研的定性判断则可表示为下述数学形式： 定义2 1 1 2 8 设a ( o ) 为对象( o 阳c o 的某属性，x e x _ r _ r ，为口( d ) 的某个量特征值， p ，( d ) p o ，是a ( o ) 的某质特征或性质，r - ( 嘶，酌i ( 嘞，酌是p t ( o ) 的定性基准 。 称t ：服r 一( 0 ，1 x p o 是以( a ，b ，) 为基准对x 进行的定性( 判断) 映射( q u a l i t a t i v e m a p p i n g ，q m ) ，如果对任意x e x , 存在( 口，d pe f 和以( a f ，b ，) 为定性基准的性质 p ，( o ) e p ，使得： f b ，( 0 。b ，) ) 吼( 嘶，1 3 , ) = q p ，( o ) ( 2 - 2 一1 ) 其中，q ( x ) = j 1 扩，e 似，只) 是量工所对应性质p a o ) 的真值，_ l 为关 【1 ( o )够，t 【口j ，属) 系“工( p i ) ”的检测操作，( 用“上”下的一横表示区间( 铆，d j ，一竖表示工在缸 p 的之间。) 又称量一质( 特征) 转化算子，或质特征( 或性质) 定性算予因“石( 蛳， 酌”营“n f 臼 ”和“ 0 ) ”，故有： 定理2 1 设区间，m ) 是性质p l ( o ) 的定性基准，带有x 的对象d 具有性质p l ( 0 ) ， 当且仅当，萨( 1 - t ) a ，柏( 0 鱼o ) ，或工可用( 脚，既) 的重心坐标( ( 1 - f ) ，f ) 表达。 特别地，若t = l 2 ，则有：x = ( i 2 ，1 2 ) ，若令；i 0 f ( p ，a ，) 2 ，因( i f , 。p ，) 是一个以 岛为球心，以6 产( b 广a ，) 2 为半径的拓扑邻域( 8 t ) ，则有： jj ( 口，卢- ) = ，( ，j ，) i j f ，i 一( 2 - 2 4 ) 【j # 似，反) = ( 茧，j ，) i j 一磊耻j j 于是，最简判断的定性映射( 2 2 1 ) 或( 2 2 2 ) 可改写为t ：融r 一 0 ，1 i ，使得； t g ，( 昏，8 1 ) ) = x l ( e j ，西) 1 ， ( 2 - 2 5 ) 或t 0 ，孙6 f ) = i r 岛ij - 8 , - j ( x ) 。 ( 2 - 2 6 ) 其中，q = j 1i x 一i d ，并分别称( 2 - 2 5 ) 是以邻域( b6 f ) 为基准的 【0扩1 ，一p j 性质a b ) 的定性映射，( 2 2 6 ) 是以昏和8 1 为( 定性) 参数的性质印( 曲的定性映射。于 是，例2 1 又可改写为： t ( g 1 u ( j o h n ) ，5 o m m 讲，1 1 一或f l 锄( 椭卜，o 。团l - 。( g l u ( j o h n ) ) ( 2 2 - 7 ) 不难看出，最简判断的定性映射( 2 2 2 ) 中的( ，酌具有明确的边界嘶和肪，而 ( 2 2 - 5 ) 中的( b ，8 j ) 具有明确的中点白和半径6 f ，( 2 2 6 ) 具有明确的参数昏和8 t 。 显然，若盱b 或4 司，则( 2 - 2 1 ) 、( 2 - 2 2 ) 、( 2 - 2 5 ) 将分别变为： 毗a i ) = x j - c t r = t 胁( d ) = 掣0 ) 删芬嚣 z 删 和 毗的母 ：)h 吖鬈”。( 2 - 2 - 9 ) 或 t q ，劲2 f l 川岫 ( 2 2 1 0 ) 并称( 2 - 2 - 8 ) 、( 2 - 2 - 9 ) 和( 2 2 1 0 ) 分别是以特征量0 【，和岛为基准的定性判断。 值得指出的是，因若干区间的交仍是一个区间，所以，以若干区间的交为定性基 准的性质判断可用简单性质判断的定性映射表达。 由此可见，当区问( 即d j 或邻域( t 。8 ) 取各种不同形式时，定性映射可表达各 种简单性质判断的操作或过程。 基于属性论的0 - 1 背包问题算法研究 2 3 多维整合( 或合取) 性质判断的定性映射模型 2 3 1 基准叩为区间向量的定性映射 下面讨论当白分别取区间向量和区间矩阵时，定性映射f k 印所表示的判断操 作。 定义2 3 若岛为若干两两不相交区间的并，i l l c p = ( a 。，1 3 , ) u ，u ( ，) ， 且( ，既) n ( ，b ) = 刀，卢l ，胛，则称映射t ：歇r 一 0 ，1 ，使得： 旦 t ，( ( m ”b - ) ，( ，啪) ) 2 二。，。弓b ) 。m 。a x r ，( 工) ( 2 3 一1 ) 是以区间向量c r = ( ( a 。b 。) ，( 锄，) ) 为基准的定性判断其中，v 为不可 兼析取 由下例2 2 不难看出：这种表示与分段函数表示是等价的。 例2 21 - 1 2 0 随温度，d ) 变化有：i c e ( n 。d ) 、w a t e r 功和g a s ( h z d ) 等三种不 同质的态，若用c c 和矿分别表示未确知的下界和上界，并用t e ( a ，矿) 和f ( “，1 3 ) ) 分别表示c r o ) v “且( ) 21 3 疗f 叫) ( 帕2 1 荨上i o 三) 瓯) 2 1 ( 2 3 5 ) 例2 3 表明定性映射还可表达无穷大和无穷小判断 下面给出以若干区间的并为定性基准的性质判断的定义： 定义2 4 设( 嘶，艮) ，= l 。栉，是性质p a o ) 的定性基准，则以是它们的并( a ” 1 3 , ) u ，u ( 锄，9 0 为定性基准的性质办( 口) 的判断可用映射f ：放p 一 0 ，1 ) ，使得： f ( 础，届“，属) 】) = q t ) ( 】籼，v 属) ( 2 3 - 6 ) 基于属性论的o 1 背包问题算法研究 这时，称( 2 3 6 ) 是析取性质p r ( o ) = p ，( v 。v p ( o ) 的定性映射 例2 4 血糖不正常的性质判断操作可表示为： 郴如圳假，3 9 v 6 l 矿) 】) 2 龟删忡3 ( g 如伪 磅) v ( 州k 惭伽聊) ( 2 - 3 - 7 ) 或t ( g l u 砌) ，沁，3 9 ) f o j ( g l u ( j o h n ) ，( 6 1 ，印越神) ( 2 3 8 ) 因( 2 3 一1 ) 一( 2 3 8 ) 等除算术运算外，还须逻辑操作才能实现，故引入： 定义2 5 除算术运算外，还须逻辑运算才能完成的判断称为初等判断。 综上所述不难看出，结合各种逻辑符号，以工e ，p ) 为定性基准的各种定性映 射，不仅可表达最简性质判断，而且还可表达各种初等判断的操作或过程 2 3 2 基准印为区间矩阵的定性映射和合取性质的初等判断 本小节讨论基于合取的复杂性质的判断及其定性映射模型设口( d ) 2 互。n ，( 是 事物0 的聊个( 因子) 属性e ( o ) 的合取属性，萨，”x m ) 石x x = ，是a j ( o ) 的量特 征，若( ( 口届，) ，( 嘞，岛) ，缸氏，) ) 是属性a j ( o ) 的伪个两两不交的定性基准，砌( 口) 是由( a ，印确定的属性a j ( o ) 的质特征或性质，则称p a o ) 5 ；山( o ) ，i = l ，玎，是 这i , n 个酹侄蕨砌( d ) ，卢l ，m ，的合取性质，或口( o ) 的第i 个性质。 f ( 口1 ，卢。) ( 口。，声“) ( 口- - i 。，- 吐。) ( 口叭。，卢忆) 1 c p = l i ( 口，声，) ； i 设l ( a 一声- ) a 一声z - 忙一“，卢一) 似一，一一) j 是两两不 相交的定性基准区间( a f ，鼢构成的定性基准矩阵，取勺中不在同一行和同一列的m 个定性基准区间魄，岛) ，产l ，m ，f f l ，形为( p - - 行j 中) 不同列的标号， 构成一个区闻笛卡几积嘞2 魄”属) 。魄：，属2 ) ”“魄一助，记 为：龟2 ( 魄，属- ) ，一；，屈，) ， ( ，忍彬。它们将所维属性空间分割为 c ：x 。c ：嘲i x 个埘维的以盏2 ( 厶，免) 为球心，以磊2 ( 瓯，氏) 为半径 的球形邻域( b ，6 j 或超长方体，则以区间矩阵勺为定性基准的合取性质 研( d ) = i p ，( o ) 的( 定性) 判断可定义为下述定性映射的形式： 定义2 6 称以旷( ( 嘶，即) 为基准的定性映射t ：j p r ”一 o ，1 ) ，使得； 基于属性论的o - i 背包问题算法研究 ff 娩t ，属，