（计算机应用技术专业论文）差分进化算法在组合优化问题中的应用研究.pdfVIP

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。本论文除了文中特别加以标注和致谢的内容外，不包含其他人或其他 机构已经发表或撰写过的研究成果，也不包含为获得南京信息工程大学或其他 教育机构的学位或证书而使用过的材料。其他同志对本研究所做的贡献均已在 论文中作了声明并表示谢意 、，1 学位论文作者签名：彝啤签字日期：2 咀牡 关于论文使用授权的说明 南京信息工程大学、国家图书馆、中国学术期刊( 光盘版) 杂志社、中国 科学技术信息研究所的 有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文，并 通过网络向社会提供信息服务。本人电子文档的内容和纸质论文的内容相一致。 除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京信息工程大学研究 生院办理 函公开口保密( 年一月) ( 保密的学位论文在解密后应遵守 此协议) 学位论文作者签名：习鲁扯 指导教师签名： 签字日期：丝! ! ：立：颦 签字日期：知l i f 1 ，g 件，采用传统的数学优化方法将很难求解。差分进化算法是近年提出的一种新 的自然计算方法，也是基于种群迭代的群智能优化方法，虽在求解带约束的组 合优化问题中得到较好应用，但在算法的精度和求解效率上仍存在着瓶颈。因 此针对具体优化问题，研究并设计高效的差分进化算法正受到国内外研究者的 普遍关注，也正逐步成为进化计算领域的研究热点。 本研究紧紧围绕经典的背包问题和等圆p a c k i n g 问题，它们是两类具有代表 性的组合优化问题，进行较深入的探索研究，并取得相应的研究成果： ( 1 ) 针对离散空间的组合优化问题，提出了一种基于置换策略的离散差分 进化算法。主要的工作有：一是将置换策略和差分进化算法相结合，提出一种 基于置换策略的单目标差分进化算法，并将该算法应用于求解单目标背包问题； 二是结合n s g a i i 的精英保留机制，在差分进化算法的基础上，给出多目标差 分进化算法；三是给出基于置换策略的多目标差分进化算法，应用该算法求解 多目标背包问题。实验结果和分析表明，该算法能够有效地解决背包问题，特别 是在大规模问题的求解上，算法优化性能明显优于n s g a i i 。 ( 2 ) 针对连续空间的大规模约束的组合优化问题，设计出求解问题的差分 进化算法，并验证算法的可行性。本文选取其中的等圆p a c k i n g 问题进行研究， 将等圆p a c k i n g 问题转换成多目标问题，设计出适合求解等圆p a c k i n g 问题的差 分进化算法，并通过大量实验，验证文中所设计算法的可行性。 本论文通过对离散空间和连续空间组合优化问题的研究，设计了基于置换策 略的离散差分进化算法、求解等圆p a c k i n g 问题的差分进化算法。这些工作不仅 对差分进化算法的研究有着重要的意义，也对差分进化算法的实际优化应用有 着重要的意义。 关键词：差分进化，置换策略，多目标优化，背包问题，等圆p a c k i n g 问题 a b s 仃a c t i ti sc o m m o nt of a c eal o to fc 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 m s w o r l d u s u a u y , t h e s ep r o b l e m sa r eo f t e nc o n s t r a i n e d s o i ti sh a r dt o p r o b l e m se f f i c i e n t l yb yu s i n gt r a d i t i o n a lm e t h o d s a san e wn a t u r a lm e t h o da n d r o b u s te v o l u t i o n a r y a l g o r i t h m s b a s e do n p o p u l a t i o n , d i f f e r e n t i a l e v o l u t i o n a l g o r i t h m sa r ep r o m i s i n gt o s o l v et h ec o n s t r a i n e dc o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m s b u tt h ep r e c i s i o na n de f f i c i e n c yo ft h ea l g o r i t h ma r es t i l l f a c e dw i mt h e b o t t l e n e c k t h e r e f o r e ，d i s c u s s i n ga n dd e s i g n i n gt h ee f f e c t i v ea l g o r i t h m sf o rt h e s p e c i f i co p t i m i z a t i o np r o b l e mh a sr e c e i v e dm o r ea n dm o r ea t t e n t i o n si nt h e w o r l d a n di t i sg r a d u a l l yb e c o m i n gt h er e s e a r c hf o c u si nt h ef i e l do fe v o l u t i o n a r y c o m p u t a t i o n t h i ss t u d yc e n t e r i n go nt h ec l a s s c i a lk n a p s a c kp r o b l e ma n dc o n g r u e n tc i r c l e p r o b l e m , w h i c ha l et w ok i n d so ft y p i c a lc 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 m ，a r e d e e p l ys u m m a r i z e da n dg e ts o m er e s e a r c hr e s u l t sa sf o l l o w s ： ( 1 ) f o r t h ec 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 o fd i s c r e t e s p a c e ，a p e r m u t a t i o n - b a s e dd i f f e r e n t i a le v o l u t i o n a r ya l g o r i t h mi sp r o p o s e db yu s i n gt h e p e r m u t a t i o ns t r a t e g y m a i nw o r k sa l es u m m a r i z e da sf o l l o w s ：1 ) an e wa l g o r i t h mo f p e r m u t a t i o n - b a s e dd i s c r e t ed i f f e r e n t i a le v o l u t i o ni sp r o p o s e d , w h i c ha b s o r b st h e p e r m u t a t i o ns t r a t e g ya n dd i f f e r e n t i a le v o l u t i o n a r ya l g o r i t h m a n dt h ea l g o r i t h mi s a p p l i e dt ot h es i n g l e - o b j e c tk n a p s a c kp r o b l e ms o l v i n g 2 ) an o v e lm u l t i - o b j e c t i v e d i f f e r e n t i a le v o l u t i o n a yi sp r o p o s e db yu s i n ge l i t er e t a i nm e c h a n i s mn s g a - i ia n di s i m p l e m e n tw i t h i nt h ef r a m w o r ko fd i f f e r e n t i a le v o l u t i o n a r y 3 ) an o v e la l g o r i t h mo f p e r m u t a t i o n - b a s e dm u l t i - o b j e c t i v ed i s c r e t ed i f f e r e n t i a le v o l u t i o ni sp r o p o s e da n di t h a sb e e na p p l i e dt os o l v et h em u l t i - o b j e c t i v ek n a p s a c kp r o b l e m e x p e r i m e n t a lr e s u l t s a n dt h ea n a l y s i so nt h ek n a p s a c kp r o b l e md e m o n s t a t et h ee f f e c t i v e n e s so ft h e a l g o r i t h m e s p e c i a l l yi ti ss u p e r i o rt oc l a s s i c a ln s g a - i ia l g o r i t h mi nl a r g e s c a l e p r o b l e m ( 2 ) f o rt h e 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 mo fc o n t i n u o u ss p a c ew i t h l a r g e s c a l ec o n s t r a i n t s ，aa p p r o p r i a t ed i f f e r e n t i a le v o l u t i o na l g o r i t h mi sd e s i g n e da n d al o to fe x p e r i m e n t sh a v eb e e nd o n et op r o v et h ee f f e c t i v e n e s so ft h ea l g o r i t h m i n t h i sd i s s e r t a t i o n , r e s e a r c hf o c u s i n go nt h ec o n g r u e n tc i r c l ep a c k i n gp r o b l e mi s d i s c u s s e d a n dan o v e ld i f f e r e n t i a le v o l u t i o na l g o r i t h mh a sb e e nd e s i g n e df o ri t i n t h en o v e la l g o r i t h mt h ec o n g r u e n tc i r c l ep a c k i n gp r o b l e mi sc o n v e r t e di n t o m u l t i - o b j e c t i v ep r o b l e m e x p e r i m e n t a lr e s u l t sc a np r o v et h a t t h i s a l g o r i t h mi s e f f e c t i v e i nt h i sd i s s e r t a t i o n , w i t ht h es t u d i e si nc 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 m a n o v e lp e r m u t a t i o n - b a s e dd i s c r e t ed i f f e r e n t i a le v o l u t i o na l g o r i t h ma l ed e s i g n e df o r d i s c r e t eo p t i m i z t i o ns p a c e ，a n dan o v e ld i f f e r e n t i a le v o l u t i o nf o rc o n g r u e n tp a c k i n g p r o b l e mi sd e s i g n e d t h ew o r k si nt h i sd i s s e r t a t i o na l ev e r yi m p o r t a n tt ot h er e s e a r c h o ft h ed i f f e r e n t i a le v o l u t i o n a r yo p t i m i z a t i o na n dt h eo p t i m i z a t i o na p p l i c a t i o n so fd e i nt h er e a lw o r l d k e yw o r d s ：d i f f e r e n t i a le v o l u t i o n ，p e r m u t a t i o ns t r a t e g y , m u l t i o b j e c t i v e o p t i m i z a t i o n ，k n a p s a c kp r o b l e m ，c o n g r u e n tc i r c l ep a c k i n gp r o b l e m m l k 目录 第一章绪论l 1 1 研究背景、目的及意义l 1 2 课题的国内外研究现状2 1 3 本文主要研究工作5 1 4 本文的组织结构6 第二章差分进化算法8 2 1 进化算法概述8 2 1 1 进化算法框架8 2 1 2 进化算法基本特征8 2 2 差分进化算法9 2 2 1 差分进化算法的基本思想9 2 2 2 差分进化算法的特征1 0 2 2 3 算法流程1 0 2 2 4 控制参数的选择1 3 2 3 多目标进化算法1 4 2 3 1 多目标优化问题的定义1 4 2 3 2 进化多目标优化的传统方法一1 6 2 3 3 性能评价指标1 6 2 4 约束处理机制18 2 5 本章小结2 0 第三章基于置换策略的差分进化算法应用研究一2 l 3 10 1 背包问题描述2l 3 2 置换策略2 2 3 3 基于置换策略的单目标差分进化算法2 3 3 3 1 算法设计2 3 3 2 3 实验结果2 5 3 4 多目标差分进化算法3 0 3 4 1 非支配精英选择机制3 0 3 4 2 基于拥挤距离和拥挤距离排序机制3 l 3 。4 3 算法设计3 2 3 5 基于置换策略的多目标差分进化算法一3 3 3 5 1 算法设计一3 3 3 5 2 评价指标3 5 3 5 3 测试结果。3 5 3 6 本章小结3 7 第四章差分进化算法在等圆p a c k i n g 问题上的应用研究。3 9 4 1 等圆p a c k i n g 问题概述3 9 4 2 等圆p a c k i n g 问题的研究概况4 1 4 3 算法设计4 1 4 3 1 基本思路4 1 4 3 2 编码。4 l 4 3 3 整体框架4 2 4 4 算法仿真和性能分析4 6 4 5 本章小结5 0 第五章：总结和展望51 参考文献5 2 致谢5 8 作者简介5 9 n 第一章绪论 第一章绪论弟一早瑁化 进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a s ) 是基于达尔文( d a r w i n ) 的进化论， 在计算机上模拟生命进化机制而发展起来的。差分进化算法作为一种新兴的优化算法，继 承了进化算法的所有优点，同时又具有自身的特点，其利用种群中个体之间的差异，通过 不断进化，最终收敛到全局最优解。差分进化算法以受控参数少、原理相对简单、易于理 解与实现等优点，逐步为广大研究人员所偏爱。目前差分进化算法已经应用于众多领域， 并且取得了较好的效果，自该算法被提出以来，引起了国内外研究人员的普遍关注，正逐 步成为进化算法研究领域的热点课题。 组合优化是- i - j 古老而又年轻的学科，随着计算机技术的突飞猛进和在各行业的广泛 应用，组合优化已壮大成为运筹学的一个独立分支。一些数百年前数学家们偶然想到的问 题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用，这是他们当时 所不曾想到的，这从另一方面寓示了这一学科的巨大前景。 本章首先介绍课题的研究背景及意义，然后介绍课题的国内外研究现状，接着简要介 绍本文主要研究工作，最后是本文的组织结构。 1 1 研究背景、目的及意义 差分进化算法( d i f f e r e n t i a le v o l u t i o n ，简称d e ) 是一种新兴的智能搜索方法，结构简 单且性能高效，在科学研究和实际工程项目中得到广泛应用。由德国的s t o r e 和美国k p r i c e 于1 9 9 5 年提出【，其最初的设想是为了求解有关切比雪夫多项式的问题，经过研究发 现，差分进化算法同样能够高效地求解复杂的优化问题。差分进化算法是一种基于群体智 能的全局优化方法，其主要通过种群内个体之间的协同合作和互相竞争来产生种群智能， 以进一步指导进化过程的全局性搜索。该算法的基本思想是通过种群中个体之间的差异和 优胜劣汰的竞争策略来产生新的个体，并最终使种群达到或者接近全局最优解。在整个优 化过程中，差分进化算法不依赖被优化问题的信息，而是根据整个种群的动态变化来调整 种群的搜索策略，具有较强的全局搜索能力，因此能够解决常规数学方法无法求解的复杂 优化问题。 作为优化算法的一个重要分支，差分进化算法已经引起优化计算领域研究人员的普遍 关注。目前，差分进化算法已经广泛地应用于人工神经元网络、化工、电力、机械设计、 机器人、信号处理、生物信息、经济学、现代农业、食品安全、环境保护和运筹学等领域。 虽然差分进化算法得到了深入广泛的研究，但与其他群智能优化算法相比，其理论研究尚 处于起步阶段，缺乏系统性。因此，对于差分进化算法进行深入的理论分析、算法改进和 应用研究能够产生巨大的学术和实用价值。 背包问题( k n a p s a c kp r o b l e m ，k p ) 是经典的组合优化问题，在信息密码学、数论、投 资管理学、工业优化设计等领域中都具有极重要的应用价值，因而对该问题的求解无论是 南京信息工程大学硕士学位论文 在理论研究还是在实际应用都具有重大意义。目前存在的经典的求解背包问题的精确方法： 动态规划、分支界限、枚举法等，当问题规模日益变大时，这些精确算法已经无法满足计 算要求，或者说需要很长时间，造成大量资源的浪费，这就需要新的算法来解决这一类问 题。差分进化算法是一种基于种群的全局性搜索算法，具有简单通用、鲁棒性强、全局寻 优能力强等优点，能够解决复杂性优化问题，因而用差分进化算法求解背包问题，既是对 差分进化算法研究在优化空间上的拓展，同时也是一种比较新颖的求解组合优化问题方法 的探索。 p a c k i n g 问题有着悠久的研究历史。尤其是圆形p a c k i n g 问题，一直以来是数学界的热 点问题。圆形p a c k i n g 问题是一个高难度的大规模组合优化问题，如果仅仅采用数学分析 和理论证明的方法，在问题规模较大时，将很难得到求解。差分进化算法是一种近似算法， 在求解函数优化和组合优化问题上已经取得了较大的进步，尝试将差分进化算法应用到等 圆p a c k i n g 问题的求解上，将具有较大的研究价值。另外，p a c k i n g 问题在工业领域有广泛 的应用，应用需求驱动理论研究，理论研究指导应用，对差分进化算法的研究，特别是差 分进化算法在p a c k i n g 问题上的研究，将在很长一段时间内是具有较大研究价值的热点课 题。 1 2 课题的国内外研究现状 本课题的研究涉及差分进化算法的理论分析、改进和应用研究，特别是在组合优化问 题中的应用研究。由于差分进化算法是种结构简单而性能高效的优化方法，因此有必要 对差分进化算法的国内外研究动态进行分析，同时组合优化问题是差分进化算法的一个新 的应用研究领域。通过对差分进化算法的研究，提高算法的性能，并将其应用于组合优化 问题的求解，越来越受到关注，正成为新的研究热点。 自差分进化算法被提出以来，引起了国内外研究人员的极大关注，与之相关的研究工 作迅速开展，研究成果和文献不断涌现，并取得了很多优异的成果。尽管差分进化算法在 工程实践中获得了广泛的应用并且得到深入的研究，但与其他进化算法相比，对差分进化 算法的研究仍缺乏系统性。 ( 1 ) 差分进化算法 近几年，优化算法的理论分析逐步引起广大学者的学者关注，其研究内容主要包括： 优化算法的收敛性分析、进化策略的动力学分析、优化算法的时间和空间复杂度分析。 d a s g u p t a 等对标准差分进化算法寻优过程中的动力学特性进行了理论分析1 2 】，通过建立差 分进化算法的动力学系统( d y n a m i c a ls y s t e m ) 模型，并应用l y a p u n o v 稳定性理论研究该 模型的稳定性和收敛速度。贺毅朝等利用随机泛函中的随机压缩映射原理证明了差分进化 算法是渐近收敛的优化算法【3 】，并对差分进化算法各个模式中的共同特性与性能差异进行 分析。目前已经有很多学者在关注差分进化算法的理论研究，但与其他进化算法相比，但 还远远不够。 相对于差分进化算法的理论研究，差分进化算法的改进研究取得了突破性的进展，其 2 第一章绪论 研究的重点主要集中在以下几个方面：对差分进化算法的变异操作算子的改进研究、引入 新的策略提高差分进化算法性能、基于种群合作竞争思想的差分进化算法、以及差分进化 算法与其他进化算法相结合的混合差分进化算法等。 差分进化算法在进化过程中，算子对算法性能的影响很大，往往算子设置的不同，会 得到不同的优化效果，如何合理地设置进化操作算子，是解决优化问题的一个关键因素。 如果通过大量的反复实验来确定参数，势必花费大量的时间，那样差分进化算法自身的优 点就无法得到充分的发挥。s u g a n t h a n 等提出了操作算子的自适应策略1 4 1 ，该策略的提出在 一定程度上解决了进化操作算子的选取以及相关参数的设置问题。l i u 等提出基于模糊逻 辑的自适应差分进化算法【5 】，通过模糊逻辑控制器设置变异因子，和交叉因子c r ，根据问 题的信息，自适应调整f 和c r 的值。谢晓锋等【6 】将变异因子由原来的固定数值转化为随 机函数。c h i o u 等【7 j 提出一种可变的变异因子设置策略，有效克服了固定或者随机变异因子 的缺陷，无须选择变异操作的类型，同时提高了算法的性能。t h o m s e n 【8 】在差分进化算法中 引入小生境思想，求解多极值函数优化问题，通过删除小生境中相似的个体，使得算法具 有继续追踪和维护多个极值点的能力。 优化算法以独特的优势应用于不同问题，同时又都存在着某些缺陷和不足，如果能将 多种优化算法混合起来，实现优势互补，其性能往往优于单一的优化算法，因而如何将多 种优化算法有机结合起来，形成混合智能优化算法，已经并将继续成为进化算法研究领域 的一大热点。众所周知，差分进化算法以其全局搜索的特性而优于其他算法，如何将这一 优势进一步加以利用，以提高差分进化算法的性能。c h i o u 等1 9 j 利用蚁群搜索算法，实时地 从多种变异算子中为d e 选择合适的变异操作算子，以加速算法的寻优过程。h r s t k a 掣i o 】 将遗传算法的部分染色体通过d e 的变异操作产生，同时利用二元竞争选择策略选择子代。 z h a n g 等【l l 】将粒子群算法和差分进化算法相结合，通过差分进化算法的变异和交叉操作来 更新每个粒子，然后再通过粒子群算法的操作算子来更新算子，每次操作都是两种算法迭 代使用。 ( 2 ) 多目标差分进化算法 无论是在现实生活中，还是在科研项目中，都存在多目标优化问题。多目标优化是近 几年进化计算领域的一个新的研究课题，并且引起了世界各国研究人员的普遍关注。针对 多目标问题，多目标优化算法被相继提出，并在逐步完善。一系列以非支配排序的选择和 保持共享函数的多样性为主要特点的多目标算法 1 2 - 1 4 相继被提出，在习惯上人们称之为第 一代多目标进化算法。1 9 9 9 年至2 0 0 3 年间，以精英保留机制为特征的第二代进化多目标 优化算法相继被提出【15 。翻，其中，d e b 等口1 1 提出支配排序遗传算法( n o n d o m i n a t e ds o r t i n g g e n e t i c a l g o r i t h m ，简称n s g a i i ) 最为经典，在很多算法中应用到其p a r e t o 排序机制。 为了有效地解决多目标优化问题，对于优化算法也提出了较高的要求，首先要保证进 化算法具有较好的收敛能力，同时还需要进化算法能够保证群体的多样性，以达到进化算 法最优解均匀分布的目的。差分进化算法具有高效的搜索能力和较快的收敛速度，同时差 分进化算法在进行求解时可以进行并行搜索，因而用差分进化算法能够很好地解决多目标 优化问题。k u k k o n e n 等提出新的基于差分进化算法的多目标优化算法四】。在该算法中，在 3 南京信息工程大学硕士学位论文 选择的过程中判断新的个体与原个体之间的支配关系，然后处于非支配地位的个体进入下 一轮迭代，如果两者体之间没有支配关系，那么都要进入下一轮迭代，最后采用基于空间 距离的策略对新群体进行修剪，以保证群体的规模保持不变。与n s g a i i 2 1 1 相比，该多目 标优化算法得到的解不但能够很好地收敛于p a m t o 前沿，而具有良好的分布性。g o n g 等阱l 提出了一种基于占支配的自适应改进多目标差分进化算法，采用精英保留机制和占支配进 行选择，通过差分进化算法的变异规则进行交叉变异，从而优化得到最优解。a b b a s s 掣2 5 】 提出一种基于p a m t o 竞争的方法，子代与参与交叉操作的父代基向量进行比较，如果子代 个体不被支配，则子代代替父代进入种群，反之父代被保留。如果非支配解的数目超过一 定阈值，则利用基于最近邻域法的小生境技术对新群体进行裁剪。为了进一步提高算法对 于控制参数的鲁棒性，a b b a s s 2 6 】在文献【2 5 】中算法的基础上引入了自适应交叉和变异概率。 x t m 等 2 7 j 利用基于p a r e t o 排序的适应值分配方法，利用小生境p a r e t o 的概念确定个体适应 值降低的程度，同时使用了精英解保留策略和分散度维持策略。在此基础上，x u e 纠碉引 入贪婪概率、变异概率和交叉概率，将其拓展用于解决离散多目标优化问题，并用该算法 解决了商用电路板设计、供应和制造计划问题。 ( 3 ) 离散差分进化算法 在实际生活中和工程领域不但有连续空间上的优化问题，同时还有很多离散空间上的 优化问题，这就要求我们在研究优化问题不仅仅要关注连续空间的优化问题，也要关注离 散空间的优化问题。由于连续空间和离散空间优化变量不一致。差分进化算法是针对连续 空间提出的优化算法，无法直接地应用到离散空间优化问题中，需要一种转换机制。 目前，研究人员根据离散优化问题的特点，结合差分进化算法的内容，提出多种改进 差分进化算法用来求解离散空间的组合优化问题。g o d f r e y 等1 2 9 】针对离散空间的优化问题， 提出了一种基于序列的差分进化算法，采用一种转换机制，实现了离散空间和连续空间的 一一对应，文中提到的算法有效地解决了经典的组合优化问题旅行商问题( t r a v e l i n g s a l e m a np r o b l e m ，简称t s p ) 和工序安排问题，为用差分进化算法求解离散优化问题找到 了一条便捷的途径。在文献 3 0 】中，y u a n 等将二进制离散差分进化算法应用于求解电力系 统的机组启停问题。在该二进制差分进化算法中，群体中的个体全部被编码为二进制形式， 并且在变异操作算子中设计特定的策略确定个体的二进制位取0 或取l 的概率。张明明等 提出基于自适应离散差分进化的多目标优化算法【3 l 】。在该算法中，采用自适应差分进化操 作来提高算法的全局寻优能力，从而使得到的最优解能够更好地收敛于p a r c t o 前沿，同时 保持群体的多样性，因此能够使最优解在p a m o 边界上均匀分布。苗世清等提出基于贪婪 策略的离散差分进化算法，并将其应用于求解0 l 背包问剧翊。在该算法中差分进化算法 的变异操作是通过模运算实现的，同时应用贪婪策略以满足约束上限，并且通过几次迭代 之后重新初始化群体的方法以防止算法陷入局部最优。贺毅朝等提出求解多选择背包问题 的离散差分进化算法【3 习。该算法通过改进差分进化算法的三个基本操作算子，同时采用正 整数的编码方法表示群体中的个体。为了解决包含整数的非线性规划问题，吴亮红等m 1 将 取整操作嵌入到差分进化算法的变异操作中。 ( 4 ) 差分进化算法的应用 4 第一章绪论 与其他进化算法相比，差分进化算法具有一定的优越性，因此该算法在现实生活及科 学研究等诸多领域，具有广泛的应用。c h i o u 等【_ 7 】提出的改进d e 确定在一定负荷模式下的 合适的电网拓扑结构来有效解决电网重新配置问题，在降低电能损耗的同时使得分布式系 统的电压满足约束限制。除此之外，还有诸如：化工领域、机械设计、信号处理领域、生 物学、运筹学等。 在现实生活中，组合优化问题层出不穷，为了验证差分进化算法在求解组合优化问题 中的有效性，我们选取组合优化问题中的两个经典问题进行研究，背包问题和p a c k i n g 问 题。 ( 5 ) 背包问题 背包问题作为经典的组合优化问题，被很多研究学者用作检验算法在组合优化问题应 用研究的试金石，研究和解决背包问题不仅仅具有理论参考价值，同时还有较好的现实意 义。对于0 l 背包问题的求解，早期的精确算法有回溯法、动态规划法、分支界限法等， 后期随着启发式算法的提出，贪心算法、蚁群算法，模拟退火等算法逐渐成为求解背包问 题的主流算法。苗世清掣3 2 】提出基于贪婪策略的离散差分进化算法求解o 1 背包问题。贺 毅朝等提出离散差分进化算法求解多选择背包问题【3 3 】。h a r t 等i ，s - 翔s 采用量子学的理论，用量 子比特位进行编码，求解单背包问题和多背包问题。张翠军掣”】提出了贪心遗传算法，将 遗传算法与贪心策略相结合，求解背包问题。有关背包问题的求解，虽然已经取得很多的 研究成果，但这些工作还远远不够，需要更多的、更高效的算法来求解。 ( 6 ) p a c k i n g 问题 p a c k i n g 问题是一类组合优化问题，它们研究的是一组物体在较大区域内无嵌入的放置 方式，其最终目标是寻求最优放置方式，亦即最大化地减少资源的浪费。p a c k i n g 问题研究 的侧重点主要有矩形p a c k i n g 问题p s j 和圆形p a c k i n g 问题两类。 由于p a c k i n g 问题是公认的n p 难问题，如果使用严格的算法进行求解，在时间的花销 往往让人无法接受。近年来国外学者采用如遗传算法 3 9 4 0 1 、模拟退火算法1 4 “2 1 、禁忌搜索 1 4 3 算法等多种启发式算法对p a c k i n g 问题进行求解。在国内，黄文奇教授等洲1 利用受自 然界和人类社会智慧启发得到的拟人拟物算法，对p a c k i n g 问题进行求解。滕弘飞等h 7 5 刁 以航天器布局优化设计为背景，提出p a c k i n g 实验的启发式算法和布局拓扑模式迭换等方 法，对格外带动、静平衡等性能约束的旋转舱内p a c k i n g 布局进行了优化。本文研究的等 圆p a c k i n g 问题属于p a c k i n g 问题中的一类。 1 3 本文主要研究工作 差分进化算法在函数优化问题上的成功应用，引发了科研人员对该算法在离散空问和 组合优化问题上应用研究的思考：如何在不改变标准差分进化算法机制的基础上，实现差 分进化算法在离散空间和组合优化问题上求解。 背包问题和等圆p a c k i n g 问题是经典的组合优化问题，求解这两个问题的算法的研究 已经取得了较大进展，但在算法的精度和求解效率上存在着瓶颈，如何提高其精度和效率 5 南京信息工程大学硕士学位论文 将具有很高的研究价值。 针对上述存在的问题，进行了深入的研究和实践，主要工作包括： ( 1 ) 对已经存在的差分进化算法进行研究，弄清楚算法的结构和优化过程，并对进化 中操作算子的设置规则进行讨论分析，同时对待约束的优化问题的处理方法进行讨论分析。 ( 2 ) 提出一种置换策略，并将该策略应用于差分进化算法在离散空间的优化中。 1 ) 为了实现连续优化空间和离散优化空间的转换，同时保证转换后问题的本质不发生 改变，提出了一种置换策略，确保连续和离散空间的一一对应； 2 ) 针对离散空间的单目标优化问题，结合置换策略，提出了基于置换策略的单目标差 分进化算法，并成功将该算法应用于求解单背包问题中； 3 ) 针对离散空间的多目标优化问题，在多目标差分进化算法和置换策略的基础上。提 出了一种基于置换策略的多目标差分进化算法，成功将该算法应用到多背包问题的求解中。 ( 3 ) 将差分进化算法拓展应用于求解经典的n p - h a r d 等圆p a c k i n g 问题。根据等 圆p a c k i n g 问题的特点，通过将约束等圆p a c k i n g 问题转化为无约束多目标优化问题来求解， 同时设计一种类p a r e t o 随机选择机制，执行选择操作，设计出适合求解等圆p a c k i n g 问题 的差分进化算法。并通过大量实验，验证文中所设计算法的可行性。 1 4 本文的组织结构 本文深入地分析了差分进化算法的研究和应用，所涉及的内容主要可以分为两大部分， 他们之间的关系如图1 1 所示，第一部分( 第二章) 在全面分析差分进化算法的基础上， 结合多目标优化问题的特点，分析差分进化存在的不足，为第二部分研究差分进化算法的 性地提出了 问题的求解 通过大量实 望了下一步 第一章绪论 本论文其余各章节的组织如下： 第二章首先简单介绍了进化算法的基本框架，接着介绍差分进化算法的流程、特征以 及其中控制参数的选择等，给出多目标进化算法的定义，给出传统的多目标进化算法，最 后针对待约束的优化问题，给出约束处理几种约束处理机制； 第三章主要介绍差分进化算法在离散空间的应用研究，提出了置换策略，并将置换策 略和差分进化算法相结合，提出了基于置换策略的差分进化算法，并将算法应用到背包问 题的求解中； 第四章主要介绍了用差分进化算法求解等圆p a c k i n g 问题，首先给出等圆p a c k i n g 问题 的问题描述，然后结合等圆p a c k i n g 问题的特点，设计出求解等圆p a c k i n g 问题的差分进化 算法，最后通过实验验证算法的可行性。 在最后一章，我们给出了本文的总结与进一步的研究方向。 7 南京信息工程大学硕士学位论文 第二章差分进化算法 进化计算是一种新兴的搜索寻优技术，它根据生物中遗传和进化的原理，仿效基因、 染色体等物质表达的信息，遵循达尔文“物竟天择，适者生存”的原则，使随机生成的初 始解，经过一系列的复制、交换、变异等遗传操作不断迭代进化，逐步逼近最优解。随着 对进化算法研究的不断深入，进化算法在很多领域都起着非常重要的作用，引起了国内外 广大学者的极大兴趣。作为进化算法的一个重要分支，差分进化算法已经引起了进化计算 领域科研人员的密切关注。 本章首先对进化算法进行概述，然后分别介绍了差分进化算法、多目标差分进化算法 和约束处理机制，最后是本章小结。 2 1 进化算法概述 进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 是一类模拟生物自然选择与自然进化的随机 搜索算法，以其擅长于求解高度复杂的非线性问题而得到了非常广泛的应用。同时它因不 依赖于待求解问题的信息而具有较好的通用性。 2 1 1 进化算法框架 进化算法中，无论是遗传算法、遗传规划、进化策略或差分进化，都是从一组随机生 成的初始个体出发，经过选择、重组、交叉等操作，并根据适应度大小进行个体的优胜劣 汰，提高新一代群体的质量，再经过多次反复迭代，逐步逼近最优解。从数学角度讲，进 化算法实质上是一种搜索寻优的方法。传统的寻优方法有三种：基于导数的方法、穷举法 和随机搜索法。进化算法尽管也是一种搜索寻优的方法，但是它和传统的方法有很大的不 同，它不要求所研究的问题是连续、可导的，同时不需要依赖问题的信息，可以很快地得 出所要求的最优解。 进化算法是以达尔文的进化论思想为基础，通过模拟生物自然选择与自然进化的随机 搜索算法。生物进化是通过繁殖、变异、竞争和选择实现的，而进化算法则主要通过选择、 重组和变异这三种操作实现优化问题的求解或近似求解【5 3 1 。 2 1 2 进化算法基本特征 进化算法是一种基于群体搜索的智能优化方法，具有如下特征： ( 1 ) 有指导搜索。进化算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式的全 面搜索，它是有指导的搜索。指导进化算法执行搜索的依据是适应度，也就是它的目标函 数。在适应度的驱动下，使进化算法逐步逼近目标值。 ( 2 ) 自适应搜索。进化算法在搜索过程中，借助复制( 选择) 、交换( 重组) 、突变等 8 第二苹差分进化算法 操作，体现。适者生存，劣者消亡”的自然选择规律，无需添加任何额外的作用，就能够 保证搜索群体的品质。 ( 3 ) 渐进式寻优。进化算法从随机产生的初始可行解出发，一代一代地反复迭代，使 新一代的结果优越于上一代，逐渐得出最优的结果，这是一个逐渐寻优的过程。 ( 4 ) 并行式搜索。进化算法每一代运算都是针对一组个体同时进行，而不是只针对单 个个体。因此，进化算法是一种多点齐头并进的并行算法，大大提高了进化算法的搜索速 度。并行式计算是进化算法的个重要特征。 ( 5 ) 黑箱式结构。进化算法只研究输入与输出的关系，并不深究造成这种关系的原因， 因此便于处理因果关系不明确的问题。 ( 6 ) 全局最优解。进化算法由于采用多点并行搜