(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf_第1页
(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf_第2页
(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf_第3页
(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf_第4页
(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf_第5页
已阅读5页,还剩51页未读, 继续免费阅读

(计算机应用技术专业论文)蚁群算法求解mkp问题的设计与实现.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

蚁群算法求解m k p 问题的设计与实现摘要 摘要 背包问题( k p ) 是经典的n p - h a r d 难组合优化问题之一,多维背包问题( m k p ) 对背包问题增加多维的约束,大大增加了求解难度,该问题在资源分配和资金预算等 方面具有重要的应用。蚁群算法( a c o ) 作为一种比较新的元启发算法,目前在一些 路径选择优化问题上的应用效果显著,但是关于a c o 在m k p 问题上应用的论述还很 少。 本文通过对m k p 问题研究现状的分析,提出一个新的蚁群优化算法c o r e - a c o , 对问题实例的地形分析和基于效率函数的核心概念进行研究。通过利用适应度地形 分析m k p 问题解空间的特性,将适用于m k p 的解优化法和核心区局部搜索方法融 入a c o 算法中。通过向可能的收敛方向提高搜索的纵向探测,增强算法局部搜索能 力,成功的把c o r e - a c o 算法运用于解m k p 问题。通过实验发现,此算法在取得很好 所得解质量的前提下,有效减小搜索空间。 关键词:多维背包问题,蚁群算法,适应度地形分析,核心 作者:周宇 指导教师:钱培德、吕强 蚁群算法求解m k p 问题的设计与实现 a b s t r a c t a b s t r a c t 。j k n a p s a c kp r o b l e m i so n eo ft h et y p i c a ln p - h a r dc o m b i n a t o r i a lo p t i m i z a t i o np r o b - l e 血s m k pa d d sm u l t i d i m e n s i o n a lc o n s t r a i n t st ot h ekp w h i c hm a k eu sv e r yh a r d e r t o5 s o l v ei t ,a n dh a v eg r e a ta p p l i c a t i o n si nm a n yd o m a i n s ( s u c ha sr e s o u r c ea l l o c a t i o n , c a p i t mb u d g e t i n g ,e t c ) a sap o p u l a rm e t a ,- h e u r i s t i c ,a n tc o l o n yo p t i m i z a t i o n ( a c o ) h a sb e e ns u c c e s s f u l l ya p p l i e dt om a n yr o u t i n ep r o b l e m s ,b u tf e wd i s c u s s i o na b o u tt h e a p p l i c a t i o no fa c o f o rm k p b a s e do na n a l y z i n gt h ed e v e l o p m e n to fr e s e a c h i n gm k p , t h i sp a p e rb r i n g su pa n e wa c oa l g o r i t h m ( c o r e - a c o ) b ys t u d y i n gt h ea n a l y s i so ft h ed i s t a n c ea n dt h ec o r e b a s e do ne f f i c i e n c yf u n c t i o n a f t e rr e s e a r c h i n gt h ec h a r a c t e ro ft h es o l u t i o n ss p a c ew i t h t h ea n a l y s i so ff i t n e s s - d i s t a n c e ,b o t ht h em e t h o df o ro p t i m i z i n gt h em k ps o l u t i o n s a n dl o c a ls e a r c hm e t h o di nt h ec o r ea r e aa r ei n t e g r a t e dt oa c o a l g o r i t h m i ts o l v e s t h em k pb ye n h a n c et h ee x p l o i t a t i o ni nt h ec o n v e r g e n ta r e a ss oa st ot h ea b i l i t yo f a l g o r i t h mi nl o c a la r e a 8 。b a s e do na n a l y z i n gt h er e s u l t so b t a i n e db yc o n c e r n e de x p e r - i m e n t s ,w ef i n dt h a tt h ec o r e - a c oc a ne f f e c t i v e l yr e d u c et h es e a r c hs p a c e w h e n e v e r , 让d o e sn o ti n f l u e n c et h eq u a l i t yo fs o l u t i o n s k e y w o r d s :m kp a c oa l g o r i t h m ,a n a l y s i so ff i t n e s s - d i s t a n c e ,c o r e w r i t t e nb y :z h o uy u s u p e r v i s e db y :q i a np e i d e ,l i iq i a n g 1 1 1 蚁群算法求解m k p 问题的设计与实现插图 插图 1 1 m k p i ;- 题解的二进制表示,2 3 1 邻域、地形、解空间的关系, 1 8 3 2 1 0 2 8 规模的实例解的差异性 2 0 3 3 2 2 8 规模f d 关系图2 l 3 4 1 0 2 8 规模f d 关系图。2 1 3 5 1 0 2 8 规模f d 关系图( 去除交换操作) ,2 2 3 6 h c f - a n t 的搜索和解的构造过程2 5 3 7 5 1 0 0 规模的实例f d 关系图一2 8 3 8 5 1 0 0 规模的实例f d 关系图( 去除交换操作) 2 8 4 1 5 1 0 0 规模的实例解收敛情况3 6 1 蚂蚁搜索5 l 2 地形分析相关代码5 1 蚁群算法求解m k p 问题的设计与实现 表 格 表格 2 1 几类背包问题的衍生问题的区别 8 3 1 m k p i ;- j 题解排列:1 9 4 1m k p 问题5 1 0 0 实例结果比较3 7 4 2m k p 问题1 0 1 0 0 实例结果比较3 7 4 3m k p 问题5 5 0 0 实例结果比较:3 8 算法 a n ts y s t e m 。1 0 h c f - a n t 算法2 6 m k p 解的局部搜索 c o r e - a c o 解m k p m k p 解的修复操作 2 7 3 3 3 5 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明:所提交的学位论文是本人在导师的指导下,独立进 行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不含 其他个人或集体己经发表或撰写过的研究成果,也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体,均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名: ! 叠! 基 日期:兰2 2 2 垒! 自 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档,可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外,允许论文被查阅和借阅,可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名: t 乱睁 导师签名:匹三幺 蚁群算法求解m k p i n - 题的设计与实现第一章引言 1 1m k p 介绍 第一章引言 1 - 1 1m k p 的问题描述 组合优化问题的求解方法研究已经成为了当前众多学科关注的焦点,这不仅在 于其内在的复杂性有其重要的理论价值,同时也在于它们在现实生活中广泛的应用。 尤其是对于n p 完全问题,它们有精确的数学模型和复杂性度量,而且理论上也存在 最优解。但是即使在计算机技术高度发达的今天,我们仍然无法完成对许多组合优化 问题的求解,这无疑是对人类智慧的一种挑战。 大规模多维背包m k p 问题已经证明是n p h a r d 问题,无法在多项式时间内求 得最优解,本文便主要研究m k p 的求解。多维背包问题m u l t i d i m e n s i o n a lk n a p s a c k p r o b l e m ( m k p ) 描述如下:要将n 个物体装入存在m 个限制的背包中,在这些物体无法 全部装入的前提下,m k p 问题的目标是装入尽可能多的物体,让这些物体总的效益 最大化。 m k p 的数学描述如下:设定一个礼个物体的集合0 = 0 1 ,0 2 ,d n ) ,一个存 在m 个约束的背包c = c 1 ,c 2 ,) ,一个物体消耗矩阵r ,它的每个元素表 示物体d j 对背包的约束c i 的消耗,一个决定变量的集合x = 【z 1 ,z 2 ,z 。) ,每个 决定变量z j 表示物体d j 是否放入背包( 1 表示放入,o 则反之) 。一个物体效益的集 合p = 0 l ,p 2 ,孙 ,每个效益殇表示物体放入背包后产生的效益。求一个决定 变量序列s ,使放入背包的物体的总效益最大。 最大化 满足约束 乃 j = 1 m q , 江1 ,仇 【o ,1 ) , 歹= 1 ,n ( 1 1 ) ( 1 2 ) ( 1 3 ) 在维数较多时以背包和物体来解释就不太好理解,我们可以用资源和产品来 形象化的描述多维背包问题:给定有限数量的m 种资源b :资源i 的约束) ,可以生 产礼种产品( 二进制决定变量奶0 ,1 ,为l 时表示生产产品勺,o 则不生产,每种产品 生产。或1 个) ,每个产品都有一个效益( 乃:产品j 的效益值) 和对m 种资源的消耗值( r 巧: 产品歹对资源i 的消耗) 。m k p 的目标是在有限资源无法生产所有产品的前提下,选择 第一章引言 蚁群算法求解m k pi h - j 题的设计与实现 生产部分产品( 找到一个产品集合的真子集) ,在满足资源约束的条件下,使总效益最 大化。 , t t 、1 23。45 i:1 1 1 r i 嘲臣口】 王工互工二工二 互田 图1 1 :m k p i 司题解的二进制表示 公式( 2 5 ) 中1 2 1 个约束的每一个就是一个背包约束,这样m k p 名称为多约束背 包问题( m u l t i c o n s t r a i n e dk n a p s a c kp r o b l e m ) :m 个约束在数学上又可以看成是背 包的m 维数限制,因此问题也可以称为多维背包问题( m u l t i d i m e n s i o n a lk n a p s a c k p r o b l e m ) 。还有一些其他的名字作为m k p 的别称,如多背包问题m u l t i k n a p s a c k p r o b l e m 、多重背包问题m u l t i p l ek n a p s a c kp r o b l e m l 。也有作者将术语睢1 加入到问 题的名称中,称m k p 为m u l t i d i m e n s i o n a lz e r o o n ek n a p s a c kp r o b l e m ( 见f 1 1 ) 或t h e 口j m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ,简称m k p 0 1 ( 见2 1 ) 。 对于该问题含有多个可替换的名字,和几个非常容易混淆其他问题,在同一篇文 章中分散的提及,一方面毫无必要,也容易搞混。因此根据以前大部分论文的使用习 惯,本文使用多维背包问题( m k p ) 来表示所要研究的问题。 1 1 2m k p 的b e n c h m a r k 为大部分m k p 论文作者使用和结果比较的b e n c h m a r k 是由【c h u ,b e a s l e y 于1 9 9 8 年 在论文【1 】中产生,有文件名为m k n a p l ,m k n a p 2 ,m k n a p c b l ,m k n a p c b 2 ,m k - n a p c b 9 的共1 1 个m k p 问题的实例文件。 m k n a p l ,m k n a p 2 为零散的小问题集。m k n a p c b l m k n a p c b 9 的九个文件,分别对 应产品数( 物体数) 1 0 0 、2 0 0 、5 0 0 ;资源数( 约束数) 5 、l o 、3 0 九种组合。对应关系为 m k n a p c b l5 1 0 0m k n a p c b 25 2 5 0m k n a p c b 35 5 0 0 m k n a p c b 41 0 1 0 0m k n a p c b 51 0 2 5 0m k n a p c b 61 0 5 0 0 m k n a p c b 73 0 1 0 0m k n a p c b 83 0 2 5 0m k n a p c b 93 0 5 0 0 在m k n a p c b l m k n a p c b 9 d p ,每个文件都含有3 0 个实例,每个实例的任意一种资源 的约束与所有产品对资源的总需求的比率( t i g h t n e s sm 抚d ) q 器l 勺是固定的,3 0 个 实例按这个比率的值分成了三类,前十个为o 2 5 ,中间十个为0 5 0 ,最后十个为o 7 5 。 而在该论文 1 】中找到的最好解存放在m k c b r e s 文件中。 文件的具体数据格式参见【附录am k p 实例文件格式】 1 有些论文对这两个称呼另有解释,见2 2 5 2 蚁群算法求解m k p b 题的设计与实现第一章 引言 1 2研究内容 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ,a c o ) 目前在国内外已经取得了很多 研究成果,也有很多应用,证实其在解决组合优化问题中的优越性,目前的研究重点 是如何提高算法的性能,如对于特定问题的搜索空间的地形分析就是方法之一。 本课题着重研究的内容如下: 1 2 1解空问适应度地形分析 根据m k p 问题的实例,先在小规模问题上进行完全搜索,分析其地形和解空间 对搜索过程的影响,然后考虑到大问题集毕竟和小问题集存在差异,地形肯定要复杂 的多,有它特有的适应度地形,同时又无法完全搜索,可以采用对比一定量最好的局 部最优解的结构,分析其中较高质量的解的邻居区域的地形,指导启发算法的搜索。 在搜索过程中,对比得到的解结构和实例的具体地形,分析两者的关系,实现自动适 应和调整搜索空间,增加找到高质量解得概率。 1 2 2a c o 与m k p 问题特性的结合 m k p 区别于t s p 和q a p 问题的特殊性在于实际它是一个子集选择问题,像g a 、 a c o 等启发算法的做法是搜索得到解,并不是局部最优,通常需要局部搜索, 而m k p 解的结构是一个0 l 串,同时存在着多维的约束,局部搜索得到解并不都是可 行的,必须经过再次处理,增加或删除物体来转化为可行解。在转化的过程,选择标 准一般采用m k p 的物体效率函数来依次添加或删除。j a k o bp u c h i n g e r 【3 提出了基 于对偶方法求解效率函数的方法建立搜索物体的核心区,减小搜索空间和复杂性,并 在c p l e x 上求解获得了很好效果。本文将该方法与a c o 相结合,对物体的效益资源 比排序分析,寻找适合于a c o 的核心区,指导搜索的进行。 1 3研究意义 1 m k p 问题是一个n p h a x d 陋- 题,有许多重要的应用,例如信息密码学领域,数 论研究,货物装载f 4 】,分布式系统中的处理器( r e s o u r c em l o c a t i o n ) 和数据 库分配( a l l o c a t i o np r o c e s s o r sa n dd a t a b a s e si na d i s t r i b u t e dc o m p u t e l s y s t e m ) 【5 】,资金预算( c a p i t a lb u d g e t i n g ) ,下料问题( c u t t i n gs t o c kp r o b l e m ) 等等,此 外m k p 可以看作一种带正系数的二进制问题的通用模型【6 】f 7 】【8 】 9 】。对该问 题求解算法的研究无论在理论上还是在实践上都有一定的意义。 2 m k p 问题的地形适应度分析 3 蚁群算法求解m k p 问题的设计与实现 【t h o m a s l 9 9 7 在t s p 和q a p 问题上,进行地形适应度分析并取得了一定的成果。 在m k p 问题上,地形适应度分析相比则较少。对m k p 进行地形适应度分析,有 助于对该问题的求解。 1 4本文结构 本文的主要章节安排如下: 第一章主要介绍多背包问题、本文的研究内容、研究意义。 第二章主要介绍背包问题、各类背包问题衍生问题的简介和它们之间的区别,以 及多背包问题的研究现状。 第三章对多背包问题的小规模和中等规模m k p 问题地形加以分析,总结了解结 构的特征。 第四章通过分析m k p 问题的效率函数和静态核心,提出基于动态核心的c o r e - a c o 算法,提出了使用实例特性和地形分析得到的信息来对问题进行搜索,通过实 验证明了此方法的有效性。 第五章对所做的工作进行的总结,对将来的研究工作进行了展望。 4 蚁群算法求解m k p i 司题的设计与实现第二章各类背包问题的综述 奎1背包问题 第二章各类背包问题的综述 背包问题( k n 印s a c kp r o b l e m ) 有多种描述形式,一般的整数背包问题可以描述如 下:一个人上山带一个背包,其可以携带物品的总重量的限度焚j c k g 设有n 种物品可 供选择装入背包中,这n 种物品编号为1 ,2 ,n 。已知第i 种物品每件重量为叫i ,每件 价值为鼽,携带个数为戤 o ,1 】l 。问此人应如何选择携带物品,使总价值最大。, 最大化 满足约束 a 嘎 i = 1 蛳玩c i , 江1 ,诜 i = l z t i 。阻1 二次背包问题就是选择一项目子 集s 冬,使得在i s7 1 ) i c 的条件下,最大化总利润值z = x t p z ,其中z = r1 ;匕g ( z 1 ,z 2 ,z 3 ,z n ) t ,戥= :三二在工程定址、水文地理、编译器设计、集成电 【u 2 肇j 路设计以及图论中,q k p 都有重要的实用价值q k p 可在图论中找到直接的理论解 释,q k p 臣i 是c l i q u e l 6 j 题的一种推广形式。q k p 与m a xc l i q u e i h - 题具有同样的特征, 是一种比求解简单背包问题困难得多的组合优化问题,甚至不存在多项式的近似算 法。 【谢涛2 0 0 4 1 【1 1 在分析了二次背包问题( q k p ) 精确算法的计算效率随利润矩阵 密度下降的原因的基础上,提出了不受密度影响的q k p 快速解法一一利润欺骗 6 蚁群算法求解m k p 问题的设计与实现 第二章各类背包问题的综述 法在线性化q k p 的目标上界估计中,利润欺骗法通过引进一适当正常数对称扩 展l a 孕a n g i a n 乘子的变化范围,亚梯度优化算法能较快地找到一l a 零a n g i a n 乘子矩阵, 使对偶问题的解逼近线性化q k p i ;- 题的等式约束条件通过提高目标函数的估计精 度,利润欺骗法可以提高变量约简效率,降低分支决策深度实例计算表明,快速算 法的效率远高于精确算法,而且计算精度并不降低。 j 。2 2 3多目标背包问题m u l t i o b j e c tk n a p s a c kp r o b l e m 一般地,一个0 1 背包问题包含了由若干项物品所组成的集合,每项物品都有其 重量和效益值,而且背包具有容量上界。背包问题的目的在于:从多项物品中,选择 适当的物品子集,使得所选中的物品效益值总和最大化,同时使选中的物品重量总和 不超过背包容量上界。 若增加背包数目,则单一背包问题就被扩展为多目标阻l 背包问题。一个由顾 物品和k 个背包组成的多目标阻1 背包问题可以形式化定义如下: 最大化, ) = ( f l ( x ) ,2 ) ,f k ( x ) ) 满足约束 ( 2 9 ) ( 2 1 0 ) 其中五( z ) = 1p i j x j ,鳓为物品歹相对于背包i 的效益值,钳巧为物品i 相对于背包i 的 重量,q 为背包i 的容量。z = ( z 1 ,z 2 ,x l ,z n ) t o ,1 ) ”,= 1 ,表示物品歹被选中; 否则,= 0 ,表示物品歹未被选中。 2 2 4 多选择背包问题m u l t i p l e c h o i c ek n a p s a c kp r o b l e m 多选择背包问题讹z 既一c h o i c ek n a p s a c kp r o b l e m ( 1 2 】可以描述如下:一个人上山 带一个背包,其可以携带物品的总重量的限度为v k g 设有他种物品可供选择装入背 包中,这n 种物品编号为2 ,2 ,n 。己知第i 种物品每件重量为毗,每件价值为p l ,携 带个数为z i ( 孔o 且为整数) 。问此人应如何选择携带物品( 各几件) ,使总价值最大。 问题模型可以表述为 最大化鼽以 i = l 满足约束伽t z i q , i = 1 ,仇 戤0 且为整数 7 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 七2 l i i q 一 叼一啊 叫 。皿 第二章各类背包问题的综述蚁群算法求解m k p 问题的设计与实现 于永新,张新荣 1 3 提出了一种用蚁群系统求解多选择背包问题的优化算法。该 方法利用蚂蚁算法所具有的正反馈特性,再结合变异参数,使算法既有较快的求解速 度又有较高的求解精度。实验结果表明,采用此算法能快速有效地解决背包问题。 2 2 5 多( 重) 背包i = - 题m u l t i p l ek n a p s a c kp r o b l e r n 多( 重) 背包问题m u l t i p l ek n a p s a c kp r o b l e m 最大化 满足约束 z 谚 o ,1 ) , i = 1 ,m 歹= 1 ,礼 v i ,j ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 这个问题在相当多国内外的论文中与多维背包问题相混淆,甚至在一些有关 背包问题研究,引用率相当高也比较具有权威性的论文中,也会见到。比如f 1 1 将 多重背包问题m u l t i p l ek n a p s a c kp r o b l e m 作为多维背包问题的一个别称。而在【1 4 1 中 多重背包问题指的是公式组( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 表示的问题,它表示含有m 个 背包( 带约束c 1 ,c ,i ) ,n 个物体( 重量w 1 ,叫。和效益p 1 ,p 。) 。因为必须满足 公式( 2 1 8 ) 和( 2 1 6 ) ,即任意一个物体最多只能放在其中一个背包中。解实际是一 个0 、1 构成向量个数为m 的向量组。 2 2 6 容易混淆的几个问题与多维背包问题的区别 由于背包问题的各个条件稍一扩展放松,就能形成一类问题,这样就生成很多的 很容易混淆的问题,这些问题虽然有一些与多维背包很数学形式近似,实际上差别非 常大。比如多选择背包问题、多重背包问题等。 塞2 :! ;丛耋登鱼闻壁的堑生闻题笪匡型 标准条件背包有多个物体可以重复多个背包中物多个背包中物 约束条件选择体效益一定体的效益不同 8 一:i z 乃 。触 m 出 q 一 一= i z 嘶 。芦 1 上 0 。在大多数a c o 中,这个值较小( 例如介于【o ,1 】) ,在最大最小蚂蚁中例外, 通常会设置成一个相当大的数。 c o n s t r u c t s o l u t i o n ( 卵:在构造解的阶段,一只蚂蚁通过不断地将解元素添加 到当前构造的部分解( p a r t i a ls o l u t i o n ) s p 中来构造解。 ;一对于蚂蚁k 已经构造的部分解风= a 1 ,i 2 ,i 知) ,其选择下一个节点的公式如 l 下: s :a r g m a 以l e 如( ) ,如果q q 0 ; ( 2 1 8 ) l 最否则使用公式( 2 1 9 ) 、7 其中,q 是在 0 ,1 】区间均匀分布的随机数,q o 是一个参数( o q o 1 ) ,s 为根据公 式2 1 8 给出的概率选择所选出的一个解元素。 根据转移概率( t r a n s i t i o np r o b a b i l i t i e s ) 对t - - 个要增加的解元素作出类似轮盘赌 的概率选择。 p ( 鼋i s p ) = ( 一) 8 叼( 日) p = 一 e ( i f ) 口7 7 ( 鼋) 卢 窖n ( 摹p ) ,喝n ( ,)( 2 1 9 ) 佗( s p ) 代表可以被蚂蚁加入到当前构造的部分解s p 中的解元素的集合。转移概 率由一个状态转移规则( s t a 托t r a n s i t i o nr u l e ) 决定。它是信息素值和其它信息的函 数,窖信息素值和所有可行解元素的信息素值的总和的比率。 a p p l y p h e o m o n e u p d a t e ( t ,s l s n 口) :一旦所有蚂蚁构造了解,就应用下 面的规则更新信息素: 蠢卜( 1 - p ) 膏+ p f ( s )( 2 2 0 ) 。瓯衍i 5 ) 其中i = 1 ,n ,歹= l ,l d i l ) 。鼠,是当前迭代产生的解集。p ( 0 ,l 】是挥发 系数。f :shi r + 称为质量函数,与目标函数有关,! i i l f ( s ) f ( 8 7 ) 号f ( s ) f ( 8 ,) ,v s s s 。 节点i p 为下一个节点的概率为: 。p 乏( ) : 抟i p 。“。叫e d k t k ( 2 2 1 ) 其中气知是边( i 歹p ) 上的信息素量,为启发因子,口2 2 删甜( t ) 为剩余物体的集合a 因 此,知和的值越大,物体i p 被选择的可能性越高。 第二章各类背包问题的综述蚁群算法求解m k p 问题的设计与实现 蚂蚁在构造解的过程中,通过应用以下的局部更新规则改变访问过的边上的信 息素量: 气知卜( 1 一q ) 岛知+ 口角 ( 2 2 2 ) 其中0 o t l ,而为常量。 当所有的蚂蚁都完成旅程后,应用以下的全局更新规则更新最好解的路径上的 信息素量: i ,卜( 1 一p ) t i j i p + p a t i j 知 ( 2 2 3 ) 其中 a t i j 6 = 挈嚣。如知k 咖k e s m ; ( 2 2 4 ) 0 p l ,l g b 为目前为止最好解的目标函数值。 t h o m a s 【2 2 1 使用- j m a x - m i na n ts y s t e m ( m m a s ) ,并加入了两种局部搜索算 法t s 和2 一o p t 。m m a s 相对于a s 来说做了下面的三项改进: 1 在每代蚂蚁搜索过程中,仅有一个符合下列条件之一的蚂蚁来增加信息素:此 代搜索过程中发现最好解的蚂蚁或是从第一代蚂蚁搜索到当前代发现解最好的 蚂蚁。 2 为了避免搜索过程中的早熟和停滞现象,在构成解的各条路径段上的信息素的 强弱限制在【讯,霉】范围之内,如果信息素小于。,则强制赋值为和反 之如果路径上的信息素大于霉,则强制赋值为兀一。 3 在初始化信息素时,将信息素全部设为t r n a z ,通过这种方法,在算法运行的初始 阶段,能取得更大的横向搜索能力。 另外对于算法中讥和t m a x 的设定进行了比较详细的分析。如果一个解所有的信息素 都是,而其他所有可选解的路径段上的信息素值全是扪则认为m m a s 已经收 敛,通过选择所有信息素为。的路径段所构成的解将是典型的全局最优解。 很多学者已经使用蚁群算法特别是m m a s 解决m k p 问题上,按照蚂蚁算法构造 的完全图和释放信息素的位置,我们可以将求解m k p 的蚂蚁算法分为三类。 1 顺序边 把信息素放在每对被选中的物体o i ,o i + 1 ) , d i ,o i + 1 s ) 。这样增加在刚刚选 了d i 之后,选择o m 的概率。 f i d a n o v a 2 0 0 2 】 2 3 】选择这种方式求解m k p 问题,结 果只有一小部分实例找到最优解。 1 2 蚁群算法求解m k p 问题的设计与实现第二章各类背包问题的综述 2 节点 把信息素放在每个选中的物体o i 上。这种情况下,意在增加每个物体在构造解 时选中的概率。 l e g u i z a x a o n l 9 9 9 】【2 4 提出在构造图的节点上放信息素的a c o 算法,求解 子集选择问题,在5 1 0 0 和1 0 1 0 0 上证明了可行性、结果优于e a 方法,也优 于 f i d a n o v a 2 0 0 2 】 3 内部边 把信息素放在每一个解中的不同的物体对o i ,o j ) 上,这样增加解s 的内部物体的 概率。在构造新解s 7 时,如果包含越多的s 的物体,s 的其它物体则会有更高 概率被选取。 a l a y a 2 0 0 4 1 【2 5 提出在构造图的边上放信息素的a c o 算法,计算量有一定增长, 结果相应地优于 l e g u i z a m o n l 9 9 9 】 顺序边的思想直接继承自a c o 求解t s p 、q a p 问题,考虑至u t s p 等问题是路径 选择问题,其解可以看作为一组路径序列,存在先后顺序,因此使用顺序边存放信息 素,是比较合理的方法。但放到m k p 问题,就有问题了。m k p 问题的解实际实际是 物体的选择决定变量z j 的序列x ,其本身不存在确定的顺序关系,只是颠倒x l 和z 2 的 ,位置,不改变决定变量对应的物体,并不会改变解最后的目标函数值。因此,顺序边 j 作为信息素累积的位置,进而指导蚂蚁进行搜索,并不合理,容易为顺序关系所误导, 自然找到最优解和平均最优解都不理想。 节点,内部边的方法相比更适合m k p 问题,前者的问题在于收敛过快,几十代甚 至十几代之内就会收敛,导致在m k p 实例的地形比较复杂的时候,蚂蚁算法的搜索 停滞于一个非全局的最优解。使用较好的局部搜索算法,跳出这个局部最优解覆盖的 区域,可以解决这种情况。后者相对收敛比较慢,充分发挥了蚂蚁算法信息素指导启 发搜索的作用。 2 3 6m k p 问题分析 【f o n ta n a x i l 9 9 5 】( 2 6 首先研究了目标函数与背包地容量和数目地关系, p u c h i n g e r 2 0 0 6 】【3 】扩展了应用于单背包问题的c o r e 概念,提出依赖效率函数的 适应m k p 的c o r e 概念和基于此的检验学习。在b e n c h m a r k 上测试各种c o r e 大小范围。 将m e m e t i c 算法和r g v n s 方法应用于邻居搜索,结果显示在有限时间内使用了近 似c o r e 概念改进了整数线性规划的结果。 1 3 第二章各类背包问题的综述 2 4 本章小结 蚁群算法求解m k p 问题的设计与实现 本章介绍了标准背包问题,及由背包问题发展的一些经典的衍生问题,比较了他 们的区别,然后介绍了各种精确算法和启发算法求解m k p 问题的研究现状。 1 4 蚁群算法求解m k p 问题的设计与实现 第三章m k p 问题的地形分析 第三章m k p 问题的地形分析 3 1简介 , 组合优化问题搜索空间的分析主要是采用适应度地形( f i t n e s sl a n d s c a p e ) 2 7 的 概念。直观的说,适应度地形就象连绵不断的山脉区域,有山顶,有山谷。局部搜索 算法就是在这个山脉区域中进行探测,对于象q a p 、t s p 等求解最小值的问题,就是 找到一个最低的山谷,而山谷、山顶等在区域中的分布会影响局部搜索算法的效率。 元启发算法需要解决的比较重要的问题就是平衡两种趋势:纵向探测和横向搜 索,前者是向可能的收敛方向发展从而尽早找到最优解,后者是发现新的结构不同 结构的可行解。在基于群体( p u l u l a t i o n - b a s e d ) 的元启发中,这两种趋势分别被称 为e x p l o i t a t i o n 和e x p l o r a t i o n ;在基于轨道( t r a j e c t o r y - b a s e d ) 的元启发中,这两种趋 势分别被称为i n t e n s i f i c a t i o n 和d i v e r s i f i c a t i o n 【2 8 】。这两种概念一般可以通用,在本文 中我们设定e x p l o i t a t i o n 等价于i n t e n s i f i c a t i o n ,e x p l o r a t i o n 等价于d i v e r s i f i c a t i o n 。 适应度地形的分析首先可以帮助解决纵向探测和横向搜索的平衡问题,从而在 设计一个元启发的具体算法时,有目的性和有指导性的分配纵向探测和横向搜索的 算法步骤和执行时机。 适应度地形可以定义如下: 定义3 1 适应度地形:l = ( s ,d ) 其中s 表示所有可能的解集合,表示适应度函数,在m k p 问题中,我们采用目标 函数值( 见公式2 4 ) 代替,d 表示到最优解的距离。两个解7 r 和一之间的距离d ( 7 r ,丌,) 定 义为: d ( 7 r ,丌,) = 1 0 【1 ,2 ,佗) 1 7 r 0 ) 7 r 0 ) ) l( 3 1 ) 了解局部最优解的分布以及和全局最优解的相对位置在算法设计中是非常重要 的如果地形中具有很多的局部最优解,或者相邻解之间的相关性比较低,则适应 度地形被认为是“凸凹不平”的,【2 7 】提出了自相关函数( a u t o c o r r e l a t i o nf u n c t i o n ) 来 度量地形的凸凹不平度( r u g g e d n e s s ) ,采用执行随机步r a n d o mw a u 【s ) 的概念来考察 地形结构的相关性。一个时间序列,( z 。) 的随机步相关函数( r a n d o mw a l kc o r r e l a t i o n f u n c t i o n ) 【2 7 】【2 9 】f 3 0 定义为: r ( s ) 2 褊占( m t ) 一砌x t + a - - 7 ) ( 3 2 ) 1 5 第三章m k p i - 题的地形分析蚁群算法求解m k p i 司题的设计与实现 , 基于相关性函数,相地形的关性长度( c o r r e l a t i o nl e n g t h ) 3 0 定义如下: 1 。 k 一赢,r ( 1 ) o ( 3 3 ) 相关性长度直接反应了地形的凸凹不平度,z 值越低,地形就越崎岖。 另外一种度量地形的方法:适应度函数值和到最优解的距离的相关性由f 3 1 1 2 7 1 提出,在基因算法中,这种相关性一般叫做f d c ( f i t n e s s - d i s t a n c ec o r r e l a t i o n ) 【3 1 。 相关性可以通过适应度函数值和距离的相关系数来得到,相关系数定义如下: p ( 只。) = 万面c o v 丽( f , d ) ( 3 4 ) 其中c o v ( f , d ) 为f 和d 的协方差,v a t ( f ) 和v a r ( d ) 分别为f 和d 的方差。 f d c 对于算法设计的参考价值在于对于求解最小值的问题,相关系数越大的正 值表示可以获得更小的适应度函数值,也越接近全局最优。如果一个问题具有较高 的f d c 值,组合解构造和局部搜索的算法可能获得较好的性能。但是,如果没有相关 性存在,或者很差,如果f d c 相关系统出现负值,则适应度函数在找更好解的任务上 很少甚至不能给出指导,并且对于这些问题,a c o 的性能较差。 3 2基本概念 解空间搜索的关键是解和解之间距离的表示【3 2 1 ,距离的不同会使搜索空间发生 变化,搜索空间的变化则直接影响解空间搜索算法的性能。解空间分析是一个更好理 解算法、搜索空间结构和性能之间依赖性的工具,为了定义搜索空间的概念,理解下 面几个概念是必要的。 定义3 2 邻域( n e i g h b o u r h o o d ) :一个邻域结构是如下映射:5h 2 s ,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论