（计算机应用技术专业论文）随机装卸工问题及其智能求解算法的研究.pdf

山东大学硕士学位论文 摘要 模拟退火算法、遗传算法、人工神经网络算法及蚁群算法、粒子群 算法是对问题求解的新型智能算法这些算法的主要应用对象是优化问 题中的n p - h a r d 问题，并在一些优化问题中的应用中取得了成功，成为 解决优化问题的一种有力工具是目前算法、人工智能研究领域中的前 沿研究 本文将进化计算中的遗传算法进行了改进，并将改进的遗传算法及 群智能计算中的粒子群算法应用到随机装卸工问题这一优化问题中 本文的主要创新点： 1 在基本的遗传算法的基础上，提出了解决随机装卸工问题的新型 的混合遗传算法，该算法引入新的种群择优交叉运算和变异运算，提高 了算法的收敛速度 2 因为这些算法都是基于个体之间的竞争，在提出的新型混合遗传 算法的复制、交叉和变异三种算子的基础上，引入了一个学习过程，实 现了进化过程中同代个体之间相互竞争与学习的结合从而得到一种弓 入学习过程的改进的混合遗传算法，将其运用到随机装卸工问题的求 解数值算例验证了该算法具有较高的求解程度和较快的收敛速度 3 基本的粒子群算法描述的是连续空间的算法，针对随机装卸工问 题是整数规划问题，因此在算法实现过程中做了相应调整和修改，使得 在求解随机装卸工问题上表现出理想的求解精度和速度，具有较好的实 用价值 关键词：计算智能：进化计算；群智能计算；遗传算法；粒子群算法 山东大学硕士学位论文 m o d i f t h ep s oa l g o r i t h mp r o c e s s ， w h i c ho b t a i n st h eh i g h e rs o l u t i o n p f e c i s i o n 蛐dc o n v e r g e n c ee f f l c i e n c y k e yw o r d s ： c o m p u t a t i o n a ii n t e i i i g e n c e ； e v o l u t i o n a l yc o m p u t a t i o n ； s w a r mi n t e i g e n c ec o m p u t a t i o n ： g e n e t i ca l g o r i t h m ； p a r t i c i es w a r ma l g o r i t h m m 原创- 陛声明和关于论文便用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：玉丝 日期：一垒! ! z ：f ! ：呈7 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 少 论文作者签名：王锺导师签名：2i 至日期：2 翌z ：! ! ：驾 v“ 山东大学硕士学位论文 第一章前言 2 l 世纪被人们称为是信息时代信息技术发展的主要特征是数字 化、网络化、智能化数字化可以认为是信息的表达形式特征，网络 化可以认为是信息传输的结构形式特征，而智能化则可以理解为对信 息处理的本质特征，正因为如此，在i f a c 第1 4 界国际自控联大会上， 我国著名科学家宋键院士的大会报告称：“2 l 世纪一一智能自动化时 代”， 智能化可以认为是智能自动化的简称，利用计算机实现对信息处 理的智能化，是信息时代的重要标志那么“智能”从何而来? 只能 从模拟人的智能而来，从模拟大脑的模糊逻辑思维建立了模糊逻辑： 模拟大脑神经系统建立了人工神经网络；从模拟人类进化过程建立了 遗传算法：模拟人工免疫系统建立了人工免疫算法；模拟鸟类聚集行 为建立了粒子群算法等这些算法都具有模拟智能及优化的特点，因 此，将这种通过软件计算形式的模拟智能又称为计算智能，或称智能 计算、智能优化算法1 1 随着计算机技术的飞速发展，智能计算方法的应用领域也越来越 广泛本文介绍了当前存在的一些智能计算方法，阐述了其工作原理 和特点，同时对智能计算方法的发展进行了展望智能计算也有人称 之为“软计算”，是人们受自然( 生物界) 规律的启迪，根据其原理， 模仿求解问题的算法从自然界得到启迪，模仿其结构进行发明创造， 这就是仿生学这是我们向自然界学习的一个方面另一方面，我们 还可以利用仿生原理进行设计( 包括设计算法) ，这就是智能计算的思 想这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火 山东大学硕士学位论文 2 1 智能计算概述 第二章智能算法 信息科学与生命科学的相互交叉、相互渗透和相互促进是现代科 学技术发展的显著特点生物信息学就是两者结合而形成的新的交叉 学科计算智能则是另一个有说服力的示例计算智能涉及神经计算、 模糊计算、进化计算、群智能计算和人工生命等领域，它的研究和发 展正反映了当代科学技术多学科交叉与集成的重要发展趋势 创造、发明和发现是千千万万科技开拓者的共同品性和永恒追 求人类的所有发明几乎都有它们的自然界配对物科学家和工程师 们应用数学和科学来模仿自然，扩展自然人类智能已激励出高级计 算、学习方法和技术毫无疑问智能是可达的，其证据就在我们眼前， 就发生在我们的日常工作和生活中 第一个关于计算智能的定义是由贝兹德克( b e z d e k ) 于1 9 9 2 年提出 的。他认为，从严格意义上讲，计算智能取决于制作者( m a n u f a e l u r e f s ) 提供的数值数据，而不依赖于知识；另一方面，人工智能则应用知识 精品( k n o w l e d g et i d b i t s ) 尤其值得提到的是，在人工智能发展过程中具有重要意义的计算 智能( c o m p u t a t i o n a l i n t e l l i g e n c e ) 的提出和兴起，使人工智能发展成为 一门具有比较坚实理论基础和广泛应用领域的学科生物和自然智能 在算法建模方面所取得的巨大成功，导致了计算智能系统的建立和应 用计算智能的出现是信息科学和生命科学相互交叉、相互渗透和相 互促进的产物，是生物信息学的主要研究内容之一计算智能研究始 于1 9 4 3 年麦卡洛克( m c c u i l o c h ) 和皮茨( p i t t s ) 提出的“似脑机器”，这 是人工神经网络研究的初步发展【2 】 本文只研究智能计算中进化计算与群智能计算的应用并在后两 节中给出进化计算和群智能计算的简介 山东大学硕士学位论文 动和响应范围不应太窄； 4 稳定性原则( s t a b i l i t yp r i n c i p l e ) ：群体不应在每次环境变化 时都改变自身的行为； 5 适应性原则( a d a p t a b i l i t yp r i n c i p l e ) ：在能够接受的计算代价 内，群体必须能够在适当的时候合理改变自身的行为 以上原则说明，实现群体智能的智能个体必须能够在环境中表现 出自主性、反应性、学习性和自适应性等智能特性群体智能的核心 就是，由众多简单个体组成的群体能够通过相互之间的简单合作来实 现某一较复杂的功能，完成某一较复杂的任务，其中，“简单个体” 是指只具有简单能力或智能的单个个体，而“简单合作”是指个体与 其临近的个体进行某种简单的直接通讯或通过改变环境因素问接与 其他个体通讯，从而实现相互影响和协同动作 群体智能具有以下特点： ( 1 ) 群体中相互合作的个体是分布式的，不存在直接的中心控制。 因而它更能够适应当前的工作状态，并且具有较强的鲁棒性，即不会 由于某一个或几个个体出现故障而影响群体对整个问题的求解： ( 2 ) 每个个体只能感知局部信息，不能直接拥有全局信息，并且 群体中每个个体的能力或遵循的行为规则非常简单，因而群体智能的 实现比较方便，具有简单性的特点； ( 3 ) 个体之间通过非直接通讯的方式进行合作由于群体智能可 以通过非直接通讯的方式进行信息的传输与合作，因而随着个体数目 的增加，通讯开销的增幅较小，即具有较好的可扩充性； ( 4 1 自组织性，即群体表现出来的复杂行为是通过简单个体的交 互而突现出来的智能( e m e r g e n g ti n t e l l i g e n c e ) 目前，对群体智能的研究尚处于初级阶段，但是由于其所具有的 分布式、自组织性、协作性、鲁棒性和实现简单方便等特点，使之在 没有全局信息的情况下，为寻找复杂问题的解决方案提供了快速可靠 的基础，为典型的系统复杂性问题( 如n p 问题等) 的求解，为人工 智能、认知科学等领域的基础理论问题的研究开辟了新的途径因此， 群体智能的研究具有重要意义和广阔的应用前景，它也越来越受到国 6 山东大学硕士学位论文 际智能计算研究领域学者的关注，逐渐成为一个新的重要研究方向 作为群体智能的典型实现模式，模拟生物蚁群智能寻优的蚁群算 法和模拟鸟群运动模式的微粒群算法正在受到学术界的广泛关注 【 2 4 智能计算在组合优化问题中的应用 随着2 0 世纪8 0 年代初期模拟退火算法、遗传算法、人工神经网 络算法及蚁群算法、微粒群算法的兴起，科学工作者对这些算法的模 型理论和应用技术等一系列问题进行着深入的研究，并将这些算法称 为智能算法或优化算法这些算法的主要应用对象是优化问题中的难 解问题，也就是优化理论中的n p - h a r d 问题正因为很多实际优化问 题的难解性，和智能算法在一些优化问题中的成功应用，使得智能算 法成为解决优化问题的一种有力工具科学工作者对这些智能算法报 以极大的热情和期望，在各种难解的优化问题中，他们都尝试这些算 法的应用和比较其应用效果” 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学方法的研 究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学 ( o p e r a t i o n sr e s e a r c h ) 中的一个经典且重要的分支，所研究的问题 涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领 域该闯题可用数学模型描述为： l l l i n ，( z ) s r g ( 功o 工d 其中，厂( 工) 为目标函数，g ( 功约束函数，苫决策变量，d 表示有限 个点组成的集合 山东大学硕士学位论文 第三章随机装卸工问题 3 1 随机装卸工问题的提出 随着物流业的发展，在车辆运输过程中，为减少车辆的空载里程， 提高车辆利用率，常常要组织循环运输这样每辆车从车场开出后， 中途会经过若干个装卸点由于在每个装卸点装卸的货物量不同，需 要的装卸工人数也不同如果将装卸工人按需求固定在每个装卸点 上，则当车辆数较少时，装卸工人大部分时间将无事可做，造成人力 资源的浪费；而如果安排装卸工人跟车走，倘若跟车人数太多，在某 些装卸点上可能超出需求人数，也会造成不必要的浪费现代物流业 的迅速发展，促成和推动装卸工问题的提出和研究晦1 ，正是以这一 问题为背景，唐国春于2 0 0 4 年提出了“装卸工问题”( l o a d e rp r o b l e m ) 5 1 问题描述如下： 运输公司有m 辆货车4 0 = l 2 ，呻向一个站点口，( ，= 1 2 ，帕装卸货 物运输公司要在每辆车上安排跟车的装卸工，也可以在每个站点上 雇佣当地的装卸工货车a 上跟车的装卸工必须装卸向所有n 个站点 装卸的货物，最多可以跟车的装卸工人数是岛，支付给每位跟车装卸 工的费用是a ：在站点b ，处雇佣的装卸工必须装卸所有血辆货车到这 个站点上装卸的货物，最多可以雇用的装卸工人数是d ，支付给每位 雇佣装卸工的费用是g ，蔫表示在货车4 上跟车装卸工的人数，毛为 一个跟车装卸工可以完成的装卸量用n 表示在站点口，处雇佣当地装 卸工的人数，f 表示一个当地装卸工可以完成的装卸量又已知货 车4 在站点b ，处执行装卸任务时的装卸量至少是，那么对 9 山东大学硕士学位论文 ，= 1 ，2 ，m ，= l ，2 ，月，必须满足 s 五+ t j y i e g 试求在每辆车4 上跟车装卸工的人数毛和在每个站点乃处雇佣装卸 工的人数) ，使总的装卸费用乞p ，毛+ 乙g j y j 最小 、11 1 f _ 1 卢1 我们把这个问题称为装卸工问题，装卸工问题是上个世纪6 0 年代 中国科学院数学研究所在研究运输问题“1 时提出“装卸工人的调配 问题”的推广和发展 该问题的整数规划“”模型为： m i l l a 葺+ 幻以， 墨_ + 7 ，0 勺，f = 1 ，2 ，埘；= 1 ，2 ，聆， 弓，扛1 ，2 ，脚， 0 哆，= 1 2 ，r ，力， 鼍o ，扣1 ，2 ，册， 巧o ，_ ，= l ，2 ，以， x l z ，y z 3 2 随机装卸工问题的研究概况 装卸工问题( 记为p 1 ) 是2 0 0 4 年4 月在全国运筹学研究生讲习班 ( 贵阳) 上提出来的“，这是一个新的n p 岫a r d 组合优化问题”1 文 献 1 3 也给出了这个问题的难解性自随机装卸工问题提出以来已受 到国内外数学、管理、计算机、物流等各个专业许多学者的关注该 问题目前已经取得的进展主要有： 1 ) 限制情况下的装卸工问题”1 山东大学硕士学位论文 将上述模型中的约束峨+ 奶2 勺改为等式约束气墨+ 协= 勺此时问 题称为限制情况下的装卸工问题，记为( p 2 ) 这一问题已被证明是多 项式可解的 2 ) 相同装卸工的情况 该情形是指满足条件毛= 1 ( j - 1 。，m ) 和j = 1 0 = 1 ，z ，帕的装卸工问题( 记 为p 3 ) 对这一问题，当q ，嘭，勺( i = l ，2 ，m ，= l 2 帕均为整数时，若将整 数约束去掉，将( p 3 ) 松弛成为线性规划后求得的任一个基本解的每一 个分量均为整数，从而最优解也一定是整数解。这结论说明可以使 用线性规划方法求解问题( p 3 ) ，即( p 3 ) 是一个p 问题对于相同装卸 工情况下是多项式可解的，文献 1 4 】研究了该情况下装卸工问题的最 优解 3 3 随机装卸工问题的求解策略 上节讨论的装卸工问题属于确定性问题，即货车4 在毋处执行装 卸任务时需要的装卸量铅是已知的但在实际的运输生产中，勺往往 随着需求的不确定性发生变化，通常是一个随机变量，记为白由此 提出随机装卸工问题如下： m i n 腑+ 乃巧， f = i j 1 1 山东大学硕士学位论文 墨薅w 力白，f = 1 z 朋_ ，= 1 ，z ，璃 蕾q ，f _ 垅朋 乃亏，= 】，z 凡 而o ，f = 1 ，z 册 y f o ，_ = 垅 x i z ，y j z 因为在约束条件中含有随机变量，故该模型是一个机会约束规划 模型其中不妨设白服从正态分布( 脚，刁) 因为决策是在观测到随 机变量的实现之前做出的，故所做决策在不利情况发生时可能不满足 约束条件为此，在实际求解时可以采取这样一种原则，即允许所做 决策可以在一定程度上不满足约束条件，但该决策应该使约束条件成 立的概率不小于某一置信水平 基于这一思想，本章求解随机装卸工问题时，首先根据事先给定 的置信水平，将机会约束转化为各自的等价类，得到与原问题等价的 确定性模型据 1 5 提出的思路，我们有下面的结论： 定理l 对于给定的置信水平唧( o 吩1 l 机会约束办k 畸埘力2 岛j 等 价于 毛村办z ，其中白满足p r 吻白 = 证明t 对于给定的置信水平q ，机会约束m 蔫w 所白可以写为 办 + ，勺白) 勺 另外必存在一个数，使 办 勺白j = 勺 当用一个较大的数代替磅时，上式左侧概率将变大，即 p r k i x i + tj y j 2 武2 a u s i x i + tj y j 2 k 口 山东大学硕士学位论文 第四章随机装卸工问题的两种改进的遗传算法 4 1 遗传算法简介 早在2 0 世纪5 0 年代和6 0 年代，就有少数几个计算机科学家独立 地进行了所谓的“人工进化系统”研究j ，其出发点是进化的思想 可以发展成为许多工程问题的优化工具早期的研究形成了遗传算法 ( g e n e t i c a l g o “t h m s ，g a ) 的雏形，如大多数系统都遵行“适者生存” 的仿自然法则，有些系统采用了基于种群的设计方案，并且加入了自 然选择和变异操作，还有一些系统对生物染色体编码迸行了抽象处 理，应用二进制编码。6 0 年代初期，柏林工业大学的i 。r e c h e n b e r g 和 h p s c h w e f e l 等在进行风洞试验时，由于设计中描述物体形状的参数 难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数 值，并获得了较好的结果随后，他们对这种方法进行了深入的研究， 形成了进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 的另一个分支一一进化策 略( e v o l u t i o n a r ys t r a t e g y ，e s ) ，如今e s 和g a 已呈融合之势2 0 世纪 6 0 年代中期，j o h nh o l l a n d 在a s f r a s e r 和h j b r e m e r m a n n 等 人工作的基础上提出了位串编码技术这种编码既适用于变异操作， 又适用于交叉操作，并且强调将交叉作为主要的遗传操作以后， h o l l a n d 等人将该算法加以推广，应 x 山东大学硕士学位论文 应的表现型和基因型的联系体现了个体的外部特性与内部机理间的 逻辑关系生物通过个体间的选择、交叉，变异来适应大自然环境生 物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色 体，有时也叫个体；适应篚力用对应一个染色体的数值来衡量；染色 体的选择或淘汰问题是按求最大还是最小问题来进行的 2 0 世纪6 0 年代以来，如何模仿生物来建立功能强大的算法，进 而将它们运用于复杂的优化问题，越来越成为一个研究热点进化计 算正是在这一背景下孕育而生成的，遗传算法是进化计算中的一种 遗传算法( g e n e t i ca l g o r i t h m s ) 是模仿生物遗传学和自然选择 机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进 行的一种数学仿真，是进化计算的一种最重要的形式遗传算法与传 统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了 一个解决方法同时，进化计算和遗传算法借鉴了生物科学中的某些 知识，从而体现了人工智能这一交叉学科的特点在7 0 年代初期由 美国密执根( m i c h i g a n ) 大学的h o l l a n d 于1 9 7 5 年在他的著作 “a d a p t a t i o ni nn a t u f a la n da r t i f i c i a ls y s t e m s ”中首次提出遗传算法 以来，经过近3 0 年的研究，现在已发展到一个比较成熟的阶段，并 且在实际中得到很好的应用遗传算法是模拟自然界遗传机制和生物 进化论而成的一种高效并行随机搜索最优化方法该算法已被广泛应 用到众多领域，在求解工程和数学中经常遇到的优化问题也显示了其 优越性应该说，2 0 世纪8 0 年代中期以来是遗传算法和进化计算的 蓬勃发展期，以遗传算法和进化计算为主体的多个国际会议在世界各 地定期召开我国有关遗传算法和进化计算的研究，从2 0 世纪9 0 年代以来一直处于不断上升的时期，特别是近年来，遗传算法和进化 计算的应用在许多领域取得了令人瞩目的成果“1 本节将介绍遗传 山东大学硕士学位论文 算法的基本机理和求解步骤，并评价遗传算法研究的进展和应用情 况 4 ，1 1 遗传算法的基本原理 h 0 1 l a n d 的遗传算法通常称为简单遗传算法( s g a ) 首先介绍主 要概念 1 编码与解码 许多应用问题的结果很复杂，但可以化为简单的位串形式编码来 表示将问题结果变换为位串形式编码表示的过程日q 做编码；将位串 形式编码表示变换为原问题结构的过程叫做解码或译码把位串形式 编码表示叫做染色体，有时也叫做个体 2 适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都 能进行度量的函数叫做适应度函数( f i t n e s sf u n c t i o n ) ，通过适应度函 数来决定染色体的优劣程度，它体现了自然进化中的优胜劣汰原 则对于优化问题，适应度函数就是目标函数适应度函数要有效地 反映每一个染色体与问题的最优解染色体之间的差距若一个染色体 与问题的最优解染色体之间的差距较小，则对应的适应度函数值之差 就较小，否则就较大适应度函数的取值大小与求解问题的对象有很 大关系 3 遗传操作 简单遗传算法的遗传操作主要有三种：选择( s e l e c t i o n ) 、交叉 ( c r o s s o v e r ) 、变异( m u t a t i o n ) 改进的遗传算法大量扩充了遗传操 作，以达到更高的效率选择操作也叫做复制操作，根据个体的适应 度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传一 1 6 山东大学硕士学位论文 般地，选择将使适应度较大的个体有较大的存在机会而适应度较小 的个体继续存在的机会也较小交叉操作的简单方式是将被选择出的 两个个体作为父体，将两者的部分码值进行交换变异操作的简单方 式是改变数码串的某个位置上的数码 4 1 2 遗传算法的求解步骤 1 遗传算法的特点： 遗传算法是一种基于空间搜索的算法，通过自然选择、遗传、变 异等操作模拟自然进化过程来寻找所求问题的答案。遗传算法的求解 过程也可看作是最优化过程 遗传算法具有以下特点；g 是对参数集合的编码而非针对参数本 身进行进化；g a 是从问题解的编码组开始而非从单个解开始搜索： 利用目标函数的适应度信息来指导搜索；利用选择、交叉、变异等算 子而不是利用确定性规则进行随机操作 2 基本遗传算法的一般步骤： 8 t e p l 随机产生初始种群，个体数目一定，每个个体表示为染色 体的基因编码 s t e p 2 计算个体的适应度，判断是否符合优化准则 s t e p 3 依据适应度选择再生个体，适应度高的个体被选中的概率 高，适应度低的个体被淘汰 s t e p 4 按一定的交叉概率和交叉方法，生成新个体 s t e p 5 按一定的变异概率和变异方法，生成新个体 s t e p 6 由交叉和变异产生新一代的种群，返回s t e p 2 4 。2 随机装卸工问题的一种新型混合遗传算法 1 7 山东大学硕士学位论文 4 2 1 新型混合遗传算法的提出 遗传算法具有自组织、自适应和自学习性，利用进化过程中获得 的信息自行组织搜索；算法的操作对象是一组可行解且同时有多条搜 索渠道，具有良好的并行性；不需要求导或其他辅助知识，而只需要 影响搜索方向的目标函数和相应的适应度函数但应用实践表明遗传 算法也存在一些问题，如局部搜索能力较弱、适应性较好的个体因选 择的随机性雨丢失、二遴制编码方法导致的计算速度下降等“1 为了克服上述缺陷，出现了多种多样的改进遗传算法本节给出 一种新的混合遗传算法，该算法引入新的种群择优交叉运算和变异运 算，提高了算法的收敛速度 4 2 2 新型混合遗传算法求解随机装卸工问题 求解随机装卸工闯鼷的新型混合遗传算法描述如下： s t e p1 初始化 采用实数编码，即直接采用原始变量构成染色体，记第f 代中第f 个 染色体为薯( f ) = 。( f ) 薯：( f ) ( f ) ，其中( ，) 为第，个基因，进化代数计算 器r ：= o ，最大代数为r ，随机生成个个体作为初始群体尸( o ) s t e p2 选择交叉运算 适应度较高的个体有更多的机会遗传到下一代群体中，而一般的 遗传算法中常用的选择运算往往由于选择的随机性而有可能将适应 度好的个体丢失，为克服这一缺陷并利用较多的适应值信息，我们 给出如下操作n 7 1 ： 1 8 山东大学硕士学位论文 孵姚鼢只 笔萨】 毛矧， 为方便准确的操作，我们利用 1 8 中的方法来决定日的值，e 和毛分别表示择优交叉后个体中的最大适应值及其对应的染色体 s t e p3 随机交叉 按照自适应概率以进行随机交叉运算 力一j 幽一堕掣舡厶， 只= 幽一瓦茅2 岛， 【 n t ， 厂 勺( 嘎 勺( ，+ 1 ) = 崎( f ) ，( r ) = 吻( f ) ， 【咯( r ) + r 。畸一吻o ) ) ，( ，) t e m p ，则随机的将a 1 中的一位用a 2 代替假设为第4 位，则 a 1 = 0 1 0 0 f1 ，a 2 = 1 0 1 l io ，a l n = 0 1 0 1 1 a l n 为学习后的新个 体较优个体向较差个体的学习方法类似此为单点学习，根据编码 的长度可考虑两点学习和多点学习，方法类似 2 1 山东大学硕士学位论文 引入学习过程的改进的遗传算法的算法步骤： 考虑如下形式的优化问题 1 1 1 i n ( 其中苴= ( 五，乜，) r ，巳弓，j = 1 ，2 ，m 算法步骤如下： s t e p l 初始化 8 t e p 2 个体适应性评价 s t e p 3 择优交叉运算 8 t e p 4 随机交叉运算 s t e p 5 相互学习 s t e p 6 变异运算 s t e p 7 通过上述操作产生下一代群体 4 3 2 引入学习过程的混合遗传算法求解随机装卸工问题 求解随机装卸工问题的引入学习过程的混合遗传算法步骤如下： l - 初始化 采用实数编码，邵直接采用原始变量构成染色体，记第f 代中第f 个 染色体为薯( f ) = ( f ) 薯：( f ) 靠( f ) ，其中峋( f ) 为第j 个基因，进化代数计算 器，：= o ，最大代数为r ，随机生成个个体作为初始群体尸( o ) 2 个体适应性评价 适应度函数为：曩( f ) = g 。一z o ) 山东大学硕士学位论文 z ( f ) 为第f 代中第j 个染色体对应的目标值 为适当的相对较大的常数 记e ( f ) 2 懋乓( f ) ，e ( f ) 表示第f 代群体中具有最大适应度的染色体- 3 择优交叉运算 文献 1 7 中给出的择优交叉算子： 薯o + - ) = 薯( r ) + 嘿 ：! i 5 ：；i 铲 f 毛( r ) 一再( r ) 】 其中岛：瓦 ；暑【( 1 一州+ 用】，勺 【 o ， = 勺 其中 彳= m a x 曰= l i l i n 一 剥矿 ，一 疵 嚣h h 剥一) 【一而l 9 j j 嚣卜) ) ，表示( o 1 ) 之间的随机数，g 表示一个较小的正常数，记录择优交叉 后个体中的最大适应值e 及其对应的染色体吒 4 随机交叉运算 继续进行随机单点交叉，在最好解以外的个体中进行两两随机配 对，随机设置某一基因位后的位置为随机交叉点，依设定的交叉概率 在交叉点处相互交换两个个体的部分染色体产生两个新个体，记录 新个体中最大适应值e 及其对应的染色体 5 相互学习 两个新个体毛、墨，依文献 2 0 中设计的学习过程相互学习，两 个学习概率儿l ( 较差的个体向较优秀的个体学习的概率) ，儿2 ( 较 优秀的个体向较差的个体学习的概率) 山东大学硕士学位论文 设定脱l 和儿2 初始值为儿1 。和儿2 0 p l l = 儿1 0 3 l l ：l ：1 1 j ，1 儿2 = 儿2 0 咒2 0 3 【l ：l ：明r 不妨设只 细矽，则随机将毛中的位用代替，即随机将毛中第 j 位用中的第j 代替，得新个体，对应的适应值c 向吒按概 率彪2 学习，方法如上，得新个体，对应的适应值f 6 变异运算 取前述的屯、毛、中适应值更好者赋值为毛，个体以一定的 变异概率按下述方式进行变异： f 岣( f ) 十r ( q 一嘞( f ) ) ，( f ) 嘞( f ) t 8 十1 ) = 吻) ，o ) 2 秘) 【啼( f ) + ，( 吩一勺o ) ) ， ( f ) ( f ) 变异步长r 为( 0 ，1 ) 间的随机数，变异后个体最大的适应值及其对应 个体k 取吒与中适应值较大者重新赋值为毛 7 通过上述操作产生下代群体 对f 赋值f + l ，若满足条件，终止搜索且输出最优解和最优值，否 则转到第2 步继续循环求解 4 4 数值算例与两种改进的逮传算法 匕较 算例1 某运输公司用四辆货车承担对五个需求地的运输任务， 岛= 5 ，岛= 6 ，q = 5 a n d c - = 4 ，a n 的值分别为 1 2 0 0 ，1 4 0 0 ，1 3 0 0 ，1 1 0 0 ， 山东大学硕士学位论文 嘞吼的取值分别为1 2 0 0 ，1 4 0 0 ，1 3 0 0 ，1 1 0 0 ，9 0 0 ，9 0 0 ，1 2 0 0 ，1 l o o ， 1 2 0 0 ， 毛= 3 ( f = 1 ，2 ，3 ，4 ) ，勺= 2u = 1 ，2 ，5 ) 6 = 1 5 ，气= 1 5 ，q = 2 5 ，吒= 2 5 ，白= 2 0 取置信水平= o8 = o 8 5 ，；o 9 5 ，= q ，= o 9 ，o 乩2 ，3 ，4 ) 各地需求 的装卸工人数是随机的，服从正态分布( 脚，面) ，具体取值如表l 所 示： 表1 需求分布 岛 j 皇1f = 2f = 3f = 4 户1 ( 5 ，4 )( 7 ，4 ) ，( 3 。1 )似2 。1 ) 户2( 2 。1 ) r ( 5 ，4 ) ，( 5 。1 ) ( 3 ，4 ) 卢3 ，( 8 ，9 )( 1 0 ，9 )( 1 2 ，4 )( 7 。4 ) 户4( 6 ，9 )( 1 0 。4 )( 8 ，9 )( 4 ，4 ) 户5( 8 ，4 )( 1 2 。9 )v ( 1 0 ，9 ) ，( 6 ，4 ) 要求合理安排跟车和在各需求点安排的装卸工人数，在以给定置 信水平满足各需求点对装卸工人数需求的前提下，使得支出的装卸工 费用最小根据给定的置信水平将随机装卸工问题转化为确定性模 型，该问题的精确解为：跟车装卸工人数为3 ，6 ，5 ，4 ；需求点装 卸工人数为6 ，2 ，1 6 ，1 1 ，1 5 ，对应总费用为7 9 4 0 0 元g a 种群规 模取为2 0 ，交叉和变异概率分别取为o 8 和0 1 ，采用轮盘赌方式 选择子代，最大代数为2 0 0 在相同条件下两个程序各运行5 0 次 基本的遗传算法和改迸的遗传算法相应参数与求解结果对比如表 2 所示 山东大学硕士学位论文 传算法相应参数与求解结果对比如表4 所示 表3 需求分布 磊 i = lf = 2f = 3f = 4f = 5i = 6f = 7f = 8j = 9f = 1 0 j - l( 6 ，4 )( 1 0 9 )( 。1 )( 7 )( 2 1 )( s 。)( 5 ，j )( 12 ，9 ) 9 4 )( 7 ，4 ) j 一2 ( 2 。i ) ( 3 ，1 )( 4 ，4 )g ，9 )( 2 。1 )8 。9 )( 6 ，4 )( 6 ，4 )( 1 0 9 )( 7 ) j 一，( 7 ，4 )( ，o ，9 )( ，4 )( 1 0 9 )( 3 1 ) 一4 ) ( 8 4 ) ( 1 ，9 )( 0 ，4 )( 8 ，9 ) j - ( 1 0 ，9 )( t ，1 6 】( 9 ，9 )( 1 ，1 6 )( 4 。1 )( 1 0 )( 1 0 ，”( 1 1 6 )( 1 2 9 ( 1 0 ，4 ) j - ，( 5 ，4 )( 1 2 。1 6 )( ，i )( j 。)( 2 1 )( 7 4 )“1 )( 9 )( 8 4 )( 6 。4 ) ，- 6( 8 4 )( 1 ，9 )p ，4 )( 1z ，9 )( 4 ，4 )( s 4 )7 ，1 )( 1 5 ，9 )( 7 ，4 )( 6 。4 ) j - 7 ( 1 0 ，9 ) ( 1 ，1 6 )( 8 ，4 )( 1 2 ”( 4 ”( s ，)o ，4 )( 1 ，)( 。4 )( ，1 ) j - 8 ( 1 2 。) ( 1 7 ，1 6 )( 1 0 )( 1 7 。9 )( 6 )( 1 2 ，9 )( 5 。4 )( 1 7 9 )( 1 ，)( 1 l ，9 ) ，9( 9 ，4 )( 14 ，p )( 8 。4 )( 1 5 ，1 6 )( 4 1 )( 1 ，9 )( 9 ，4 )( 1 ，9 )( 1 0 4 ( 1 2 4 ) j i o( 4 ，”( 7 4 )( 3 ，i )( ，)( 2 1 )( ，。h ，i )( 9 ，】 ( 8 4 ) ( 9 ，4 】 ( i2 。9 )( 1 4 。9 )( 9 ，4 )( 1 j 9 )( ，。) ( 1 4 ，9 ) ( 1 0 ，4 ) ( 1 6 ，9 ) ( 1 ，9 )( 1 6 。9 ) j l ：( 9 ，9 )( ”9 )( 8 ，4 )( i ，9 )( ”( 1 ，9 )( 9 9 ) ( 1 4 ，9 )( 1 2 ，4 )( 1 1 ，4 ) ，- 1 3( 2 ，1 )o 4 )( 4 。”( 7 4 ) ( 2 ，1 )( 9 4 )( 6 。4 )( ，4 )( 1 0 4 )( 1 0 ，4 ) j 1 4( 1 0 。4 )( 1 3 1 6 )( 1 2 ，4 )( 1 6 ，9 )( ，。”( 1 6 9 ( 1 0 4 )( 1 6 ，9 )( ”。4 )( 1 ，9 ) j - i ， ( i2 ，9 )( 1 6 )( 1 0 。9 )( 1 达到最优解次数 32 4o 4 4搜索成功率 808 8最大相对误差 64 山东大学硕士学位论文 第五章随机装卸工问题的粒子群算法 5 1 粒子群算法简介 自2 0 世纪9 0 年代以来，通过模拟生物群体的行为来解决计算问 题已经成为新的研究热点，形成了以群体智能( s w a r mi n t e l l i g e n c e ) 为核心的理论体系，并已经在一些实际应用领域取得了突破性进展 所谓“群体智能”是指一组相互之间可以进行直接通讯或间接通 讯的主体，能够通过合作对问题进行分布求解，即一组无智能的主体 通过合作可以表现出智能行为特征d o r i g o 等从生物进化的机理中受 到启发，通过模拟蚂蚁的寻径行为提出了蚁群优化方法：e b e r h a r t 和 k n n n e d y m4 1 于1 9 9 5 年提出的粒子群优化算法( p a r t i c l es w a r m 0 d t i m i z a t i o n ，p s o ) 是基于对鸟群、鱼群捕食行为的模拟 粒子群算法的思想来自社会认知理论根据社会认知理论，我们 可以将粒子群算法的问题求解概括为以下三个过程：评价、比较和模 仿” 评价过程是各种激励进行评估，根据正反馈或负反馈、吸引或排 斥等激励特性对其进行排序自然界中这是普遍存在的一种行为特 征有机生命只有通过对外界激励的评价，才能够完成对环境的学 习微粒群对环境的自适应学习过程也包含了这样一种评价过程 比较过程是指微粒群中的个体对其他个体标准进行测量，并与自 身条件相比较，确立自身的学习和修正动机 模仿过程是微粒群中的个体依据自身判断模拟其他个体行为的过 程，这是自然界中普遍存在的一种非常有效的学习模式，通常只模拟 山东大学硕士学位论文 5 1 1 粒子群算法的基本原理 粒子群优化算法( p s o ) 是一种模拟群集智能行为的优化算法，它 源于对鸟类捕食行为的模拟在鸟群的飞行中，每只鸟在初始状态下 处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始 处于随机状态的鸟通过相互学习( 相互跟踪) 自组织地聚集成一个个 小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集 到同一位置一一食源 在整个寻优过程中，每个微粒的适应值取决于所选择的优化函数 的值，并且每个微粒都具有以下几类信息哺1 ：微粒当前所处的位置； 到目前为止由自己发现的最优位置( p b e s t ) ，以信息视为微粒的自身 飞行经验：到目前为止整个群体值所有微粒发现的最优位置( g b e s t ) ( g b e s t 是p b e s t 的最优值) ，这可视为微粒的同伴共享飞行经验于 是，各微粒的运动速度受到自身和群体的历史运动状态信息影响，以 自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加 以影响，很好的协调了微粒自身运动和群体运动之间的关系 与遗传算法类似，p s o 是一种基于迭代的优化方法，系统初始化为 一组随机解，通过迭代搜寻最优值，粒子在解空间追求最优的粒子进 行搜索p s o 有着个体数目少、计算简单、鲁棒性好等优点，已经很 好地应用在函数优化、约束优化、极大极小问题和多目标优化等问题 上，并获得了成功“，同时在组合优化中也取得了成功眙”目前已 提出了多种p s o 改进算法“圳m m ”，如自适应p s o 算法、杂交p s o 算 法、协同p s o 算法等 在p s o 系统中，每个备选解被称为个“粒子”，每个“粒子”根 山东大学硕士学位论文 随机产生 ，个粒子构成初始粒子群体，每个粒子可以标识为 彳= ( n ，h ) ，a = l z ，) 其中a 表示几何位置，峙表示速度向量，即 x ( 0 ) = 【五( o ) ，置( o ) ，j ，( o ) ) = ( 锄( o ) ，v l ( o ) ) ，她( o ) ，v 2 ( o ) ) ，( 肌( o ) ，v ( o ) ) ) 置f ：= o s t e p2 寻优 求出每个粒子到目前为止找到的最优解，记为： z 碧 = 螂( f ) ，堙( f ) 求出当前种群z ( f ) 到目前为止所找到的最优解，记为( ，一似v p ( 哪 s t e p3 种群演化 对每个粒子置( f ) = ( ，( f ) q ( f ) ) ，令 a ( f + 1 ) = 辟( f ) + 嵋( f + 1 ) ， h ( f + 1 ) = m ( f ) + q ，d ( 1 ) 【p 箸o ) 一只( f ) 1 + 包，j 日”d ( 1 ) 【p 一( f ) 一只( f ) 】， 由此形成第( f + 1 ) 代粒子群 彳( f + 1 ) = ( 工i ( f + 1 ) ，如( f + d ，r ( f + 1 ) ) = “，( f + 1 ) ，吒( f + 1 ) ) ，( p 2 ( f + 1 ) ，v ：( f + 1 ) ) ， ( p ( f + 1 工 ( f + 1 ) ) ) ( 5 3 ) ( 5 4 ) s t e p4 终止检验 如果工o + 1 ) 已经产生满足精度的近似解，或已经达到进化时限的 要求，则停机并输出x ( f + 1 ) 的最佳个体为近似解；否则f ：= f + 1 转s t e p 2 在上述算法中，( 5 3 ) 式中的a 常称为步长因子，可参考无约束 优化方法中的搜索步长选取方式选取，( 5 ，4 ) 中的删( 1 ) 表示( o ，1 ) 山东大学硕士学位论文 间的随机数，w 称为惯性系数，c 。称为社会学习系数，c ：称为认知系 数，它们分别表示相信自己的程度、相信经验的程度和相信周围个体 的程度，通常c l = 巳= 2 由于没有交叉和变异运算，p s o 的突出特点是收敛速度快、求解质 量高，易于实现虽然p s o 最早是针对连续优化问题提出的，但目前 已被推广到各种离散优化问题m 7 m 。”，广泛应用于函数优化、神 经网络训练、模式分类、模糊系统控制以及其他的应用领域 5 1 3 粒子群算法的研究方向 尽管p s o 算法有着广泛的工程应用，但p s o 算法的研究还处于初 期，待研究的热点问题还有很多泓m 2 m “ 1 算法的数学分析 目前，大多数研究者主要还是致力于p s o 算法的应用研究，很少 涉及对算法内部机理的数学分析，表现为：p s o 算法中位置和速 度的构造及参数的设计理论不成熟：对p s o 算法中的参数分析，没 有实质性的认识，都处在实验分析阶段；p s 0 算法的改进算法及其 应用也都停留在实验阶段，缺乏理论支持：还没有给出收敛性、收 敛速度估计等方面的数学证明因此，开展一些对p s 0 算法机理的研 究，不但可以加深对p s o 算法机制的认识，而且对于扩展p s 0 算法的应 用领域也具有比较深远的意义 2 参数的选择与优化 参数w 控制了粒子的全局搜索能力与局部搜索能力之间的平衡， 为此如何构造一个惯性权重的自适应调整模型，达到控制粒子的全局 山东大学硕士学位论