（应用数学专业论文）粒子群进化方程与有关算法研究.pdf

摘要 在当今大规模生产中，多学科的交叉研究为解决优化问题提供了新的思路， 以生物智能或自然现象为基础的新型智能优化算法在研究与应用中表现出优异的 性能，现代智能算法也成为人工智能领域一个新的研究热点本文主要针对无约 束优化问题，研究了粒子群算法和人工免疫算法的改进方案 首先，通过对基本粒子群进化方程进行分析，得到一个通式进化方程在此 基础上，通过系数轮变的方法可以得到十二个类似p s o 方程的变式，其中包括基 本p s o 算法方程，本文研究了五个类p s o 方程变式实验效果证明这些方法是可 行的 其次，通过研究免疫算法的变异算子，在基于实数编码的形态空间上的模糊 控制免疫算法的基础上，提出了结合粒子群算法原理的变异函数，进而可以构建 混合免疫粒子群算法 关键词：优化算法粒子群算法免疫算法模糊控制混合算法策略 a b s t r a c t i h ec r o s sr e s e a r c h e s 锄o n gd i 丘e r e n ts u b j e c t so f 衙n e wi d e 舔t 0d e a l 谢t l l o p t i m i z a t i o np r o b l e m si nm o d 锄m a n u f a c t u r e a sp e r 廿l i si d e 钆t l l en e wi i l t e l l i g e m o p t 捌o na l g o r i t l l l n sb a s e do nb i o l o g i c a l 血e l l i g e n c e0 r 删p h e n o m 髓o na r c b r o u g h tf o r w a 耐，、) i ，! i l i c hp u tu pe x c e l l e mp e 面m 锄c e sd u 血gr e s e a r c ha i l da p p l i c a t i o n a sar e s u l t ，m o d 锄缸e l l i g e n ta l g o r i m ml l a sb e c o m ean e wr e s e a r c hf o c u so fa r t i f i c i a l i n t e l l i g e n c e t h ew o r ko ft h i sn l e s i sm a 湖yc o n t a j i l ss n l d y i n go fi i n p r 0 v i n gm e m o d so f p a n i c l es w a 哪 0 p 血l i 2 a t i o n 锄da n i f i c i a li m 删l n e 舢g o r i t l l l nf o ru i l c o n s 仃a i l l e d o p t i m i z a t i o np r o b l e m f i r b y 砒谢妯ge 、，0 l u t i o 加r ye q u a t i o no fp a n i c l es w 锄lo p t i i 】缸z a t i o na l g o r i t h m ac o n l 】 n o ne v o l u t i o n a 巧e q 删o nc 趾b e 酉v e n t h e n 觚e l v ee q u a t i o i l s 邪e v o l u t i o 彻巧 e q u a t i o i l so fp s oa l g o r i t l l ma r ed e s i 印e dw l l i c hc o n t a i l lt l 圮p s ob yt l l ew a yo ft l 蛐i n g a l t e l 证go ft h ec 衔c i e n tb a s eo nt 1 1 ec o 舢【1 1 0 ne q u a t i o n i i la d d i t i o 玛f i v ee q 岫t i o i l sa r e g n l d i e di nt h i st h e s i s n 啪耐c a le x p 耐m e n ts h o w st 1 1 e s em 劬o d sa r cf e a s i b l e s e c o n d l y b ys t i l d y i i l go fi i l u t 撕o ns t r a t e g yo fa 队硼i n gr e a lc o d i i l g ，ah y b r i d o p t 抽1 i z a t i o nm e m o d 、) ，! t l i c ht a k e se v o l u t i o n a r ye q u a t i o no fp s o 雒m em i n a t i o ns 们t e g y i sp r o p o s e db 嬲e do nf u z z yc o n 仃0 1a 认1 1 1 吼ah y b r i do 砸i 血z a t i o na l g o r i u i l 诵m a 。i aa n dp s oc o u l db ed e s i g n e d k 叻啊o r d s ：o p t i m 妇t i o na l g o r i t h m p a r t i c l eg w a mo p t i m i z a t i o n a n i 6 c i a l i m m u n ea l g o r i t h m f m z yc o n t m le v o i u t i o n a r y h y b r i da l g o n t h m 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书 日期兰坐! ：2 日期垄! ! ：兰：王蓑 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论弟一早三百下匕 本章首选综述了智能优化算法研究的研究背景、经典方法和研究现状，然后 针对本篇依次讨论了最优化若干问题，最后列出了本文的研究内容及结构安排 1 1 现代智能优化算法研究综述 1 1 1 现代智能优化算法研究背景、特点及意义 优化问题【l 巧】是描述自然界与社会系统的一个强有力的分析工具在工程、科 学、经济和社会等众多领域中，存在着大量的复杂优化问题，例如网络设计、生 物制药、最优控制、机械设计、经济模型、天线设计、大规模集成电路设计等优 化问题这些优化问题按不同的规则可分为不同的类型：按有无约束条件分为无 约束优化和约束优化；按变量是离散的还是连续的，可分为离散优化和连续优化； 按目标函数的个数可分为单目标优化和多目标优化；按变量的从属关系可分为单 层规划和多层规划；其它的分类方法从略 一般的优化算法还可以粗略地分为两大类【3 4 】：确定性方法，随机性方法或启发 式方法确定性方法大多是指基于梯度( 或导数) 的传统优化算法，如牛顿法， 拟牛顿法，共轭梯度法，变尺度法，广义乘子法，内点法，序列二次规划法，信 赖域法等，还有一些直接搜索法，如函数逼近法、区间法和积分法，隧道法和填 充函数法等也属于确定性方法通过分析问题的结构和特性，从一个初始点出发， 按照某种特定规则( 搜索方向) ，生成一系列确定性的搜索点序列，不断跳出一个 已知极小点的吸引域，进入到另一个更好的邻域内，搜索下一个改进的点，有规 律地反复迭代，直到停机规则满足传统优化算法具有理论完善，收敛速度快等 优点，但它们也有缺点，如大都是局部优化方法，优化结果与初值有关，许多算 法对函数的性态有要求，如连续性、可微性、凸性以及约束规格等最优性条件许 多工程实际和科学计算中的优化问题是大规模的、高度非线性的、多峰的，目标 函数是不连续的，甚至是不可微的，有的目标函数没有明确的数学形式，有的目 标函数受噪声的影响，有时还有许多局部最优解然而用户总是希望能够找到所 关心问题的可行域中的所有全局最优解，使得问题的求解趋于完善因此无法套 用较为成熟的局部优化理论和技术来处理高度非线性的全局优化问题，而使得基 于梯度的传统优化算法无能为力 为了解决这些问题，近几十年来，各种随机性( 或启发式) 的智能优化算法 应运而生智能算法l l7 j 是建立在生物智能或物理现象等基础上的随机搜索算法， 2 粒子群进化方程与有关算法研究 由于其自身作为启发式随机算法，具有比数学规划方法更优越的特性【1 7 】，其优点 是：( 1 ) 具有一般性及易于应用；( 2 ) 搜索最优化解的速度快且易于获得满意的结果 典型智能算法【1 9 】【2 l 】【2 q 有人工神经网络( a n i f i c i a ln e u r a ln e 铆o r k s ，删、进化 算法( g e n e t i c g o r i t h i n ，g a ) 、模拟退火算法等“人工神经网络”是在对人脑组织 结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统人 工神经网络突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人 们智能信息处理能力和模拟人脑智能行为能力的一大飞跃进化算法【2 7 】 ( e v o l u t i o n a 巧舢g o r i t h m ，e a ) 一种模拟生物进化过程和机制的自组织、自适应人 工智能技术该方法以体现群体搜索和群中个体之间信息交换两大策略的交叉、 变异算子为主，使整个群体在优胜劣汰选择机制下保证了进化的趋势遗传算法、 进化策略、进化规划共同构成了进化算法的主要框架迄今为止，遗传算法是进 化算法中最广为人知的算法近几年来，遗传算法主要在复杂优化问题求解和工 业工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注在 发展过程中，进化策略、进化规划和遗传算法之间差异越来越小遗传算法成功 的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、 设备布置与分配、交通问题等等 相对这些经典智能算法【1 7 】，现代智能算法包括人工免疫算法、粒子群算法、 蚁群优化算法、人工鱼群算法、分形算法等 这些智能算法基于生物、统计物理、社会行为等背景，以适应度为衡量手段， 采用概率、统计等随机方式，产生新群体时不需要导数信息，对函数的性态没有 要求，而且适用范围广，鲁棒性强，与传统算法具有很好的互补性，已成功地用 于求解各种优化问题但它们在理论也暴露出诸多不足和缺陷，如对某些复杂问 题而言，易趋于早熟收敛到局部最优解，另外，也存在收敛速度慢、计算量大等 问题因此对这类方法的研究也就成了最优化领域研究的重点，也格外具有了重 要意义 1 1 2 群体( 群集) 智能优化算法 现代智能算法中的一类算法是基于群体智能【2 7 】【3 刀的算法，其中典型的算法有 蚁群算法和粒子群算法 群体智能算法( s w a mi n t e l l i g e n c e 舢g o r i 廿l l n ) 的研究开始于2 0 世纪9 0 年代初，其 基本思想是模拟自然界生物的群体行为来构造随机寻优算法群体智能中的群体 ( s w 锄) 指的是“一组相互之间可以进行直接通信或者间接通信( 通过改变局部环 境) 的主体，这组主体能够合作进行分布问题求解”而所谓群体智能指的是“无 智能的主体通过合作表现出智能行为的特性群集智能在没有集中控制并且不 第一章绪论 3 提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础 群体智能的特点和优点是：群体中相互合作的个体是分布式的( d i s t r i b u t e d ) ， 这样更能够适应当前网络环境下的工作状态；没有中心的控制与数据，这样的系统 更具有鲁棒性b u s t ) ，不会由于某一个或者某几个个体的故障而影响整个问题的 求解可以不通过个体之间直接通信而是通过非直接通信( s t i i n e r g y ) 进行合作，这 样的系统具有更好的可扩充性( s c a j a b i l i 锣) 蚁群算法【3 6 1 ( a n tc o l o n y 砧g o r i n l i n ，a c o ) 在2 0 世纪9 0 年代由意大利学者m d 耐g o 受对真实的蚁群行为的研究的启发而提出蚂蚁、蜜蜂、飞蛾等群居昆虫，虽 然单个昆虫的行为极其简单，但群体却表现出极其复杂的行为仿生学家经过大量 细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素( p h c f o i n o m ) 的物质进 行信息传递的蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而 且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向因此，由大 量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的 蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息 的交流达到搜索食物的目的根据该原理提出的蚁群算法被用于解决旅行商问题 ( t s p ) 、背包问题、j 0 b s h o p 问题等组合优化问题，取得了较好的结果蚁群算法也 受到国内外学者越来越多的关注 本篇将主要分析介绍的是粒子群优化算法和人工免疫算法，及其混合算法研 究，以上两个算法将在下面单独介绍 1 1 3 粒子群算法研究现状 粒子群算法【刀【3 1 1 ( p a n i c l es w a n no p t j m i 动t i o n ) ，简称p s o 算法，是k e i l l l e d y 和 踟h 础于1 9 9 5 年根据鸟群、鱼群等搜捕食物的生物群体行为，利用f m n l 【h e p p e n e r 的鸟类模型进行建模和仿真作出的一种随机进化寻优方法 粒子群算法同遗传算法类似，是一种基于迭代的优化工具，系统初始化为一 组随机解，通过迭代搜寻最优解但是粒子群算法并没有遗传算法所采用的交叉 与变异操作同遗传算法比较【3 0 】，粒子群算法的优势在于需要调整的参数不多， 结构简单，收敛速度快由于粒子群算法具有思想简单、易于实现、应用效果明 显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机 器学习、人工生命、管理决策等领域得到了广泛的应用粒子群算法具有较强的 鲁棒性，特别是对于一些大型、复杂优化非线性系统，更显示出其独特和优越的 性能 国内外研究表明【9 1 【1 1 】【1 5 】【3 8 】【3 9 】，p s o 是解决复杂系统优化问题的一个有力工 具起初，p s o 算法主要用于连续函数的优化，后来也应用于组合优化等离散系统 4 粒子群进化方程与有关算法研究 的问题研究此外，对粒子群算法的改进也体现在很多方面如：二进制的粒子 群算法，惯性权重随进化代数线性递减的粒子群算法，参数自适应的粒子群算法， 以及和其他智能算法相结合的粒子群混合算法等等在具体应用方面：p s o 广泛应 用于神经网络的训练，各类连续问题和离散问题的参数优化( 在模糊控制器的设 计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果) ，还 应用于组合优化的问题当中除了以上领域外，p s o 在多目标优化、自动目标检测、 生物信号识别、决策调度、系统辨识以及游戏训练等方面也取得了一定的成果 虽然目前已经开发出了很多种类各不相同的改进型粒子群算法，其性能也不 断地得到提高，但是，作为一种优化算法，粒子群算法自身仍存在着许多难以解 决的问题，如早熟收敛、控制参数的选择等这些问题的存在，给粒子群算法的 实际应用带来了极大的不便这些算法的性能仍然有待于进一步改进以更好地满 足实际要求 粒子群算法作为一门新兴学科，各种理论、方法尚未成熟，有待进一步发展 和完善尽管在粒子群算法的研究和应用过程中会出现许多难题，同时也会产生 许多不同的算法设计观点，然而，目前粒子群算法的各种应用实践已经展现出了 其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把粒子 群算法的理论和方法运用到自己的工作实践中 粒子群算法在群体相互合作寻优中有自己独特的东西，而且收敛速度快，但 是粒子群算法的基本方程都也没有多大改变，因此也限制了粒子群算法的多样化 应用，因此研究类似粒子群算法基本方程就有了一定必要性本文第二章作出了 粒子群算法的一些带有权重的粒子群算法进化方程的研究与改进，增加了一些进 化方程的多样性 1 1 4 人工免疫算法研究现状 人工免疫算澍1 3 】【1 6 】【1 刀( m f i c i a li i n m 吼ea l g o r i t h m ，a 队) 是自然免疫系统在进化 计算的一个实现免疫系统【8 】【2 0 】是高等脊椎动物体内抵御病原体如细菌、病毒等人 侵，保护机体免受损害的极为复杂的生物学系统在自然免疫系统中，存在着大 量的淋巴细胞克隆( 为方便计，在不引起误解的悄况下文中称之为抗体) ，以致于几 乎每种病原体( 即抗原) 人侵生物机体时，免疫系统一般都能选择出一种或数种能识 别该种抗原的抗体使之活化、增殖，去抵御人侵的病原体当病原体被清除后， 这种能与病原体匹配的抗体在免疫系统中大量存在，浓度增大，自然免疫系统通 过抑制细胞对这种高浓度的抗体进行抑制，降低该种抗体的浓度，使免疫系统回 复到一个新的平衡状态，以免生物机体产生自身免疫病在a l 中，被求解的问题 及约束视为抗原，抗体则对应于问题的解，因此，在文中，为了讨论方便以及表 第一章绪论 5 明m a 与自然免疫系统的密切关系，在不致引起误解的情况下，抗体与a 认的解常 不作区分算法开始耐，趾a 随机生成给定数量的初始解群，加入了记忆机制，采 用克隆、突变、抑制等算子对解群进行操作，产生比父代优越的子代，这样循环 执行，逐渐逼近最优解为了防止出现成熟前收敛，姒的克隆算子模拟了自然免 疫系统基于浓度的抗体繁殖策略，抑制算子对亲和力低浓度较大的解进行抑制， 对亲和力高浓度较小的解进行促进，从而有效保持了解群( 对应于自然免疫系统 中的抗体) 的多样性，防止了成熟前收敛 目前在人工免疫系统与工程结合中，主要研究方向有免疫优化算法，免疫网 络，入侵检测，控制系统设计，故障检测、免疫a g e n t 等随着学者对免疫系统深 入的研究和隐含机制的发掘，用于优化算法的机制越来越多，但是国内外在研究 免疫算法时大多也是加入已有的经典算法、模糊或混沌等方法与免疫的机制进行 结合，而对免疫优化算法复杂性估计与收敛性证明等深刻而具有遍意义的研究成 果还很少 1 1 5 混合算法研究 现代智能算法优化方面研究的一个重要方向是把各种智能算法的机制进行优 势互补，互相结合，相互弥补不足 早在1 9 8 9 年g 0 1 d b e r g 就提出了混合算法，把遗传算法与传统的、基于知识的 启发式搜索技术相结合，来改善基本的局部搜索能力，使遗传算法脱离早熟收敛 状态而加速接近全局最优解算法在一定程度上可以提高遗传算法的优化质量和 收敛效率【小) ，4 l 】，因此，各种各样的混合遗传算法，如把遗传算法与模拟退火结合， 遗传算法中嵌入单纯形法【4 2 】，线搜索法【4 3 】等如同遗传算法一样，所有基于种群 的进化算法都时间长，收敛速度慢，容易陷入局部最优解等问题，原因在于它们 具有进化特性针对这些缺陷，许多文献表明，在原法中加入某些形式的知识， 如近似算法、局部搜索技术、特殊的组合算子极大地改善算法的搜索性能，特别 是将局部搜索技术加入到进化算法中是一种有效的途径【4 5 卅7 1 因此，借鉴较为成 熟的传统优化算法的思想进化算法的各种算子，或混合两种或多种搜索技术，扬 长避短，是解决问题的有效方法但需要考虑的问题是：( 1 ) 是否将两种或多种不 同算一起，就一定优于单一的算法? ( 2 ) 哪些算法适合结合在一起? ( 3 ) 如何将它们 有机结合? ( 4 ) 混合算法的计算量或计算效率如何? 几年来，设计高效的进化算法 求解各类复杂优化问题一直是众多领域关 免疫算法【1 7 】是有别于传统遗传算法的有效的优化工具，其诸多免疫机制如记 忆机制和群体多样性等对优化的研究和工程界有很深刻的借鉴价值由于免疫算 法的多样性好，但局部寻优能力弱，粒子群算法的搜索能力强，但易局部成熟， 6 粒子群进化方程与有关算法研究 因此两者的结合研究就自然成理 1 2 基本优化理论问题与实验研究方程 1 2 1 基本优化问题 最优化问题【1 】【4 】【1 7 1 可分为函数优化问题和组合优化问题两大类，其中函数优化 的对象是一定区间内的连续变量，而组合优化的对象是解空间中的离散状态这 两类问题皆包含约束优化及非约束优化下面分别简单介绍几个优化问题的定义 1 基于二进制编码的优化问题 设x 表示由o ，1 构成的字符集，所有长度为，的字符串构成的集合为 s = 臼i x x 。 ，厂：s 寸r 为目标函数，：s 专r ，鸟：s 一尺，扛1 ，2 ，= 1 ，2 ，m 皆为约束函数，则基于二进制编码的非约束极小化问题可描述为： n b p m i l l 趟( x ) 具有约束条件极小化问题描述为： c b p 而n 脚厂( x ) 多字符集上的优化问题 设x 表示由挖个不同的字符构成的字符集，个体长度为刀，每一个个体为x 中刀 个不同的字符构成的排序，s 表示由所有这样的个体构成的集合，目标函数及约束 条件与基于二进制编码的优化问题中描述相似，则相应的非约束极小化问题记为 n c p ，约束极小化问题记为c c p 3 函数优化问题 本文粒子群优化算法与形态空间免疫算法主要针对函数优化问题函数最优 化问题有几个基本要素：定义域( 变量) 、值域、约束和目标函数、最优值、局 部最优值在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为 约束，表示可行方案衡量标准的函数称为目标函数 设肜为刀维欧氏空间，dc 掣，厂：d 尺朋为目标函数或目标向量， 红( x ) ，吕( x ) 皆为d 上的约束函数，l f 厶1 ，m ，当埘= 1 时，对应于n b p 的 第一章绪论 7 问题称为单目标非约束函数优化问题，记为n f p ，对应于c b p 问题称为单目标约束 函数优化问题，记为c f p ，其中d 可为无界区域；当肌 1 时，对d 的限制与所= l 时的情形相同，非约束多目标极小化问题可描述为： n c m o 血，。d 厂( x ) = ( 石( x ) ，五( x ) ，无( x ) ) 含约束极小问题可描述为： c m o m i i l 榔厂( x ) = ( z ( x ) ，五( x ) ，厶( x ) ) 4 全局最优化问题及研究 本文重点考虑算法的改进，所以只考虑无约束全局最优化作为实例，下面简 单描述一下函数全局最优化问题 全局优化( g 1 0 b a lo p t h i l i z a t i o n ) 问题【4 】【4 8 1 通常具有无约束优化的形式，除了自变 量限制在某一感兴趣的区域外没有其它限制由于最大化问题和最小化问题可以 相互转化，不失一般性，本文仅考虑最小化问题一般来说，无约束优化问题在 数学上可以描述为： 幽厂( x )( 1 1 ) j ，弘 ，也，而) r e 口f 这里x 称为聍维决策变量，实值函数厂 ) 称为目标函数，可行域b 是r 珂的子 集，若b = r 刀表示完全无约束的情况在许多实际应用问题中，仅仅需要考虑b 是 足”特定子集的情况 令i l | i 表示e u c l i d 范数，若存在i 的s 邻域( i ，s ) = 扛i i l x i i i o ) ，使得 对厂( x ) ，都有厂( x ) 厂( i ) 成立，则称i 是问题( 1 - 1 ) 的局部最优解，厂 ) 称为局 部最优值若孤b ，对坛召，都有厂( x ) 厂( x ) 成立，则称x + 是问题( 1 - 1 ) 全 局最优解( 整体或总体最优解) ，( x ) 称为全局最优值 从某种角度上看，作者认为存在这样一种运动相互关系：在评价函数的标准 下，最优解促进最优值的产生，最优值会决定值域的边界，值域的变化会促进定 义域变化，定义域变化会促使局部最优解变化，局部最优解的变化包含全局最优 解的产生 自上世纪四十年代以来，由于生产和科学研究的迅猛发展，随着计算机技术 的日益广泛应用，使得全局优化问题的研究不仅成为一种迫切的需要，而且有了 8 粒子群进化方程与有关算法研究 求解的有力工具【7 j 优化理论和算法研究初期求解问题的规模较小，而且问题具有 较好的性态，如要求目标函数连续可微、凸性，有时需要目标函数的h e s s i a l l 矩阵、 l i p s c l l i t z 常数等，并且满足某种最优性条件放松对目标函数性态的限制后，出现 了一些直接搜索算法，如试探法中的黄金分割法、f i b o n a c c i 法、进退法等，函数 逼近法中的抛物线法、二次插值法、有理插值法等，还有边界搜索法、旋转坐标 法、单纯形法、p o w e l l 方法等，但它们收敛速度较慢、精度较差一般来说，确定 性算法还需要寻找高质量的初始点，即使这样，求出的最优解也往往是局部最优 解自二十世纪七十年代早期遗传算法出现以来，相继出现了许多种智能随机优 化算法，全局优化就是其主要应用目标之一，随机性算法( 或启发式算法) 在那 些对于传统爬山法和基于导数的方法来说性质差、不可微、不连续的函数优化方 面取得了很大的成功1 4 j 处理全局优化问题的随机性算法主要考虑从编码、参数设 置、搜索机制或进化算子的改进及实现方式，多种搜索机制的融合而构成混合算 法，以及从目标函数的特性和搜索空间入手来设计算法 1 2 2 常用测试函数【捌 下面是测试算法经常用的函数，前两个是单峰函数，后两个是多峰函数口引， 最优点均为或接近原点，其中x 代表一个实数类型向量，维数为刀，毛为第f 个元 素 第1 个为球面模型 彳( x ) = # ，一3 0 葺3 0 ( a ) ， 用来区分局部优化器的优劣 第2 个为i b s e i l b i 0 c l 【，也叫香蕉( b 觚锄a ) 函数 左( x ) = ( 1 0 0 ( 而一，一# ) 2 + ( 而一1 ) 2 ) ，一3 0 薯3 0 ( b ) 第3 个为r a s 们咖函数 石( x ) = ( # 一l o c 0 s ( 2 万薯) + 1 0 ) ，3 0 薯3 0 第4 个为s c h a 旋r 函数 六c x ，= 。5 + 芒罟军黯，2 毛2 第一章绪论 9 1 3 本文研究内容及结构安排 最优化理论与方法是一门应用性很强的新兴学科，它研究某些数学上定义的 问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案在最优 化理论与方法的研究中，解线性规划、非线性规划以及随机规划、非光滑规划、 多目标规划、几何规划、整数规划等各种最优化问题的理论的研究发展迅速，新 方法不断出现，实际应用日益广泛在电子计算机的推动下，最优化理论与方法 在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门 十分活跃的学科1 3 j 相对传统的最速下降法、牛顿法、共轭梯度法、拟牛顿法等算法，智能算法 更能满足当前的工程需要本文的研究主要集中于现代智能算法中基于群智能的 粒子群算法和带有新的进化机制的人工免疫算法及其混合算法的探讨上 本论文的结构和主要研究内容概括如下： 第一章为绪论部分，概述了智能优化算法的背景、经典方法和研究现状，然 后针对本篇依次讨论了最优化若干问题，最后列出了本文的研究内容及结构安排 第二章首先介绍了粒子群算法的基本理论，包括了基本原理，算法模型与其 典型发展方法然后主要针对粒子群算法核心进化方程进行了分析，并在得到一 个变式通式的基础上进行了再次的改变，得到了几个类p s o 算法方程，最后做出 实验，对结果进行了比较，并指明下一步要做的工作 第三章首先概述了免疫算法的概念、工作原理与一般框架，然后在实数编码 的形态空间上，基于模糊控制免疫算法，建立了有关粒子群原理的突变方式的联 结基函数，做了新的模糊控制免疫粒子群混合算法的初步研究 第二章粒子群算法研究 第二章粒子群算法研究 几年来很多学者专家都致力于改进粒子群算法并将其应用到多个领域本章 首先介绍带有权重的粒子群算法和近年来对粒子群算法的一些改进方案，然后从 进化方程的另一个角度着重讨论了对该算法的分析及几个新的算法方案 2 1 基本粒子群算法理论 2 1 1 粒子群算法的基本概念【7 】【1 1 】 粒子群优化算法是基于群体的演化算法k e y 皿e d y 对鸟群飞行的研究发现， 鸟是仅仅追踪它有限数量的邻居，但最终的整体结果是整个鸟群好像在一个中心 的控制之下，即复杂的全局行为是由简单规则的相互作用引起的p s o 即源于对鸟 群捕食行为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那 么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域p s o 就是从这种模型中得到启示而产生的，并用于解决优化问题另外，人们通常是 以他们自己及他人的经验来作为决策的依据，这就构成了p s o 的基本概念 p s o 算法在优化问题时，问题的解对应于搜索空间中一只鸟的位置，称这些鸟 为“粒子”o 枷c l e ) 或“主体( a g e n t ) 它们都有自己的位置和速度( 决定飞行的 方向和距离) ，还有一个由被优化函数决定的适应值各个粒子记忆、追随当前 的最优粒子，在解空间中搜索每次迭代的过程不是完全随机的，如果找到较好 解，将会以此为依据来寻找下一个解 2 1 2 带有权重的基本粒子群算法 1 算法模型【冽 将所优化问题的每个解视为一个粒子，每个粒子在疗维空间以一定速度飞行， 通过适应值函数来衡量粒子的优劣，粒子根据自己的飞行经验和其他粒子的飞行 经验动态调整飞行速度，自适应期望飞行到群体的最佳位置，找到优化问题的最 优解 设最小化目标函数，厂( x ) r ，x sc 足”，厂( x ) 连续，问题描述为： x = a r g r i l i n 厂( x )x = a r g 肌n ，l x ， 工e s 假定( x ) 的最优解不在s 的边界上设毛= ( t 。，薯2 ，) 为粒子f 的当前位置， 1 2 粒子群进化方程与有关算法研究 q = ( q 1 ，2 ，) 为粒子f 的当前飞行速度，只= ( a 。，b 2 ，) 为粒子f 所经历过的 最好位置，也就是粒子f 所经历过的具有最好适应值的位置，称为个体最好位置对 于该最小化问题，目标函数值越小，对应的适应值越好，则粒子f 的当前最好位置 由下式确定： 删，= 船嚣蒹2 震怒， 弘， 设群体中的粒子数为，群体中的所有粒子所经历过的最好位置为以( ，) ，称 为全局最好位置 则 段( f ) 只l ( f ) ，只2 ( 砒，o ) 且 厂( 以p ) ) = i i l i n 厂( 只。( ，) ) ，( b ：( f ) ) ，厂( ( f ) ) 由以上定义，基本粒子群进化方程描述为： o + 1 ) = 1 i ：f ( ，) + q ，i ，( f ) ( 岛o ) 一勃o ) ) + 乞吃o ) ( p ) 一嘞o ) ) 而o + 1 ) = 嘞o ) + v ：f ，o + 1 ) 其中，下标“”表示粒子的第j 维；“f 表示粒子f ，表示第f 代；q ，c 2 为加速常数，通常取值o 2 ，i ，一u ( 0 ，1 ) ，眨，u ( 0 ，1 ) 为两个相互独立的随机函数 为了能改善算法的收敛性能y s 1 l i 和r c e b e r l 斌提出带有惯性权重w 的以下 进化方案，通过调节w 值能有效的收敛，找到最优解，为方便起见以下用向量形 式描述 m o + 1 ) = w v o ) + q 吒o ) ( 易o ) 一薯o ) ) + 巳眨o ) ( 段o ) 一薯o ) ) ( 2 - 2 ) 薯o+1)=薯o)+ko+1)(2-3) 公式( 2 3 ) 中第一部分为微粒先前的速度，它使微粒有在搜索空间中扩张的趋 势，从而使算法有全局搜索的能力；第二部分为“认知( c 0 鲥t i o n ) 部分，表示微 粒吸取自身经验知识的过程；第三部分为“社会( s o c i a l ) 部分，表示微粒学习其 他粒子经验的过程，表现了微粒间信息的共享与社会协作这一“评价一更新 过程不断重复直至算法终止准则满足p s o 算法的搜索性能跟平衡全局和局部搜 索的能力有关，即与控制参数的选择有很大的关系主要参数包括：种群规模， 惯性权重，加速常数，最大速度和最大迭代次数等 下面主要就以上进化方程说明一下各系数的性能：惯性权重w 表明粒子原先 第二章粒子群算法研究 1 3 速度能在多大程度上得到保留，q 调节粒子飞向自身最好位置方向的步长，乞调节 粒子飞向全局最好位置飞行的步长，有研究者得到w = 0 7 2 9 8 ，q = 乞= 1 4 9 6 2 ， 搜索效果较好为了减少在进化过程中粒子离开搜索空间的可能性，通常限定 在一定范围内，即屹卜v 碾，】，如果问题的搜索空间限定义在【一，】内， 则可限定v m 瓤= 红一，0 1 后1 0 2 算法流程 上述粒子群算法的初始化过程为： ( 1 ) 设定群体规模； ( 2 ) 对任意f ，歹，在【一，】内服从均匀分布产生； ( 3 ) 对任意f ，歹，在 一v m 戤，矗】内服从均匀分布产生； ( 4 ) 对任意f ，设a = 薯； 粒子群算法流程如下： ( 1 ) 按上述初始化过程，对粒子群的随机位置和速度进行初始设定； ( 2 ) 计算每个粒子的适应值； ( 3 ) 对于每个粒子，将其所经历过的最好位置b 的适应值进行比较，若较好，则将 其作为当前的最好位置； ( 4 ) 对每个粒子，将其适应值与全局所经历的最好位置以的适应值进行比较，若较 好，则将其作为当前的全局最好位置； ( 5 ) 根据( 2 2 ) ，( 2 3 ) 式对粒子的速度和位置进行进化； ( 6 ) 如未达到结束条件( 通常为足够好的适应值或达到一个预设的最大代数 ( g o ) ) ，则返回步骤( 2 ) 2 2 1 粒子群算法的特点 2 2 粒子群算法的发展 粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作 与竞争产生的群体智能指导优化搜索与一般进化算法比较，粒子群优化算法是 一种更高效的并行搜索算法，其概念简单，容易实现，一般代码只有短短的几行， 1 4 粒子群进化方程与有关算法研究 优点显著 粒子群算法也是一种进化算法，但是它没有用遗传算子来更新染色体的基因， 而是类似梯度下降算法使得染色体向符合度函数值最高的地方群游粒子群算法 并没有能够给出严格的数学证明，但是在实际应用中被证明是有效的虽然粒子 群算法有很多优点，但是也存在着算法精度较低，易发散等缺点，尤其是当这种 算法在解空间内搜索时，有时会出现在全局最优解附近振荡的现象具体表现在： 首先，由于整个粒子群都是根据全体粒子和自身的搜索经验向着最优解的方向“飞 行，在较大的加速项系数作用下，粒子群有可能错过最优解，在远离最优解的空 间里发散，使算法不能收敛：其次，在算法收敛的情况下，由于所有的粒子都向 最优解的方向群游，所以所有的粒子趋向同一，失去了粒子间的多样性，使得后 期的收敛速度明显变慢，同时算法收敛到一定精度时，算法无法继续优化，算法 所能够达到的精度较低 针对以上的基本p s o 算法的优缺点，国内外的专家、学者做了大量的工作提出 了很多的改进【9 】【l l 】【2 3 】【3 5 1 主要的改进算法将在下面具体介绍 2 2 2 离散二进制p s o 算法 在粒子群算法中如何描述问题的可行解，即把一个问题的可行解从其解空间 转换到粒子群算法所能处理的搜索空间的转换方法就称为编码编码是应用粒子 群算法时要解决的首要问题，也是设计粒子群算法时的一个关键步骤粒子群算 法的编码方法主要分为两大类：二进制编码和实数编码 p s o 的基本算法最初是用来对连续函数进行优化的，所以一般采用实数编 码而实际中许多问题是组合优化问题，因此，k e 皿e d y 和e b e r h a n 博士在基本p s o 算法的基础上发展了离散二进制p s o 算法来解决这一类问题 离散二进制p s o 算法与基本p s o 算法的主要区别在于进化方程式( ( 2 - 2 ) ，( 2 3 ) ) ， 离散二进制p s o 算法的运动方程如下： m + l = m + ，耵刃( b 一薯) + ，l 耵刃( 玫一鼍) ( 2 4 ) i f 岛+ l 克隆选择 细胞克隆及记忆细胞演化 亲和突变 免疫选择募集新成员 新抗体群) 构成 的随机搜索链为进化过程，反映在数学上则为免疫算法 3 1 2 免疫算法的工作原理 免疫算法的工作原理如图3 1 ，这种算法是为解决最优化问题q m p ) 设计的此 图中的每一操作对应免疫系统中一种进化机制，这些操作相互作用便构成了免疫 算法，其反映在免疫学上，则为体液免疫应答过程，即抗体学习抗原并最终清除 抗原的过程将此进化过程中的抗体对应优化问题( n b p ) 的候选解，抗原被视为问 题洲b p ) ，进而获得寻求最优解的免疫算法 由图3 1 可知，免疫算法作用于抗体群，而抗体群以抗体为对象进行进化此 算法包含5 个基本要素，即抗体编码、亲和力、浓度、参数选择及免疫算子设计抗 体编码选择为二进制编码，目的是便于分析免疫算法的运行机制及对其进行理论 探讨，具体编码策略可参考文献f l6 】【1 8 1 抗体的字符长度为，每一个字符称为抗体 的基因，所有抗体构成抗体空间s ，则isl _ 2 ，抗体群的规模取定为，所有抗体 群构成的空间称为状态空间s 由于抗体群中的抗体可相同，因此根据可重组合 2 4 粒子群进化方程与有关算法研究 定理得到ls 川i 一掣+ 一1 抗体的亲和力及浓度在下一节作具体设计算法的主要 参数包括群体规模、克隆选择率、细胞克隆规模、克隆抑制半径、自我抗体插入 群体的比率 免疫算子由该图中各操作构成，在这里，记忆细胞演化意指将抗体细胞的部分 细胞做为记忆细胞加入记忆池，并清除相同，相似记忆细胞引入抗原识别及记 忆细胞演化的目的在于，对处理过的抗原或相似抗原的出现时，提高算法寻优的 快速性，若取消此两操作，对算法的收敛性无影响 图3 1 免疫算法工作原理图 在这些算子中，克隆选择将进化群体中较好的候选解确定性的选择参与进化， 提供开采更好候选解的机会细胞克隆及记忆细胞演化不仅为同类问题的解决提 供高效解决的机会，而且为算法的局部搜索提供必要的准备这一操作与亲和突 变共同作用，增强算法局部搜索能力，使算法有更多机会探测更好的候选解克 隆抑制促使突变的克隆群中相同或相似的克隆被确定性清除，其作用不仅在于保 存好、中、差的克隆，而且为免疫选择算子选择存活抗体减轻选中压力、免疫选 择的作用在于不仅给亲和力高的抗体提供更多选择机会，而且也给亲和力及浓度 皆低的抗体提供生存机会，使得存活的抗体群具有多样性，这一机制主要反映了 抗体的促进和抑制机理及抗体选择的随机性募集新成员的作用在于微调群体多 样性及增强全局搜索能力，促成算法具有开放式特点，即随时有自我抗体被引 入这些算子相互作用，共同合作能完成处理优化问题( n b p ) 的任务，该算法的特 点表现在如下几方面： 第三章免疫算法及其与粒子群算法混合研究 ( 1 ) 抗体的选择是确定性和随机性的统一 ( 2 ) 细胞克隆及亲和突变的协作体现了邻域搜索及并行搜索特性； ( 3 ) 抗体的选择及突变受其亲和力制约，突变概率被动态调节； ( 4 ) 搜索过程处于开采、探测、选择、自我调节的协调合作过程，体现了体液 免疫应答中抗体学习抗原的行为特性； ( 5 ) 搜索过程开放，随时有自我抗体被加入进化群体，因此不仅能增强群体多 样性，而且提供了产生更好解的机会； ( 6 ) 算法的收敛性对初始群体的分布无依赖性，且算法对问题( n b p ) 的目标函 数无连续性要求 3 2 形态空间上的免疫算法 上节基于体液免疫应答过程，建立了免疫算法的一般框架，但该算法是建 立在字符串编码基础上的，在用于函数优化方面，存在着与其他基于字符串编码 的智能算法所具有的同样不足是，算法存在编码和解码问题，以及字符串所描述 的解的基因( 即字符) 的突变有可能导致该解突跃性很大，从而使算法搜索速度 受到影响该节描述的是基于连续变量的函数优化问题( n f p ) 及( c f p ) ，可根据变 量取值的连续性特性，构造基于实数编码的免疫算法解决此类问题，以便提高算 法搜索最优解的速度 目前，在基于免疫学原理及实数编码的广义克隆选择算法研究方面文献【3 2 j 利 用克隆选择原理建立了基于实数编码的广义克隆选择算法 由于任何闭区间陋，6 】均可经过可逆变换变为区间【o