（计算机软件与理论专业论文）基于j2ee的物流软件系统——仓储管理系统的研究与设计.pdf

摘要 基于j 2 e e 的物流软件系统 仓储管理系统的研究与设计 作者简介：隋永。男，1 9 8 1 年7 月出生，2 0 0 4 年9 月师从于成都理工大学周家纪教授，于2 0 0 7 年7 月获硕士学位。 中文摘要 随着市场经济的快速发展，企业联系日益密切，社会分工也日趋细腻，物 流业已成为国民经济中一个重要的产业，而物流业中仓储管理已是影响物流效 率与质量的重要部分。物流业的发展促使零库存、物流联盟及物流供应链等理 论的出现，从而促使仓库所扮演的战略角色转变为以较短的周转时间、较低存 货率、较低的成本和较好的顾客服务为内容的物流目标。但仓储管理效率的提 高不仅仅是科学的管理方法以及员工的高效率，在信息化时代，一个更重要的 部分便是企业管理的信息化和网络化。 物流仓储管理信息化的最复杂的部分为物品的上架策略，上架策略关系到 物品的存放问题，合理的存放能够充分的利用库存，两这正是节约成本的必然 做法。遗传算法( g e n e t i ca l g o r i t h l n ，简称g a ) 作为模拟自然界生物进化 原理的一种随机性全局优化概率搜索算法，具有很强的全局搜索能力，特别适 合求出问题的近似最优解。因而用遗传算法解决装货上架问题是一个好的选择。 本文根据仓储管理的具体需要，创建了一个基于j 2 e e 框架的仓储管理系统 ( 删s ) 。并将遗传算法的思想融入到上架策略中。此系统得到当前国内一些有 名的物流公司的认可，因此。本文所做的探讨以及设计和实现的思路对物流企 业、第三方物流企业等具有较好的参考价值。 关键字：物流；仓储管理：遗传算法；j 2 e e 成都理工大学硕士学位论文 l o g i s t i c ss o f t w a r es y s t e mb a s e do nj 2 e e - - r e s e a r c ha n d d e s i g no fw a r e h o u s i n g m a n a g e m e n ts y s t e m a b s t r c t w i t ht h ed e v e l o p i n go f m a r k e te c o n o m y , g r o w i n gc o n n e c t i o na m o n gc o m p a n i e s a n di n c r e a s i n gs o c i a ld e p a r t m e n t s ，l o g i s t i c si n d u s t r yh a sb e c o m eac r u c i a lp a r ti n n a t i o n a le c o n o m y w a r e h o u s em a n a g e m e n t ，h o w e v e r , i nt h el o g i s t i e si n d u s t r y , h a sa s i g n i f i c a n ti n f l u e n c eo nt h ee f f i c i e n c ya n dq u a l i t yo f l o g i s t i e sm a n a g e m e n t l o g i s t i e s d e v e l o p m e n tp r o d u c et h ec o n c e p to f1 1 0s t o c k s ，1 0 9 i s t i e su n i o na n ds u p p l yc h a i n , w h i c hc h a n g et h er o l eo fw a r e h o u s i n gi n t op r o d u c i n gb e t t e rc u s t o m e rs e r v i c eb y r e d u c i n gt r a n s p o r tt i m e , l o w e r i n gs t o c k sa n dc o s t t oi m p r o v et h ew a r e h o u s i n g e f f i c i e n c yi n v o l v e sn o to n l ys c i e n t i f i cb u ta l s oi n f o r m a t i o n a lm e t h o d a m o n gt h ew a r e h o u s i n gm a n a g e m e n tw h i c ha p p l i e di n f o r m a t i o n a lm e t h o d ，t h e m o s tc o m p l i c a t e dp a r ti ss h e l fp o l i c y , w h i c hd e c i d e st h es t o r a g ee f f i c i e n c y a n da n a p p r o p r i a t em e t h o do fg o o d ss t o r i n gi sn e c e s s a r yf o rac o m p a n y t or e d u c ec o s t g a ， w h i c hs i m u l a t e st h en a t u r a le v o l u t i o n ，a sar a n d o mg l o b a lp r o b a b i l i t yo p t i m i z a t i o n s e a r c h i n ga l g o r i t h m , h a ss t r o n ga b i l i t yo fg l o b a ls e a r c h i n ga n d i ss u i t a b l ef o rg e t t i n g a p p r o x i m a t em o s to p t i m i z e da n s w e r , s oi t i sag o o dw a yt os o l v et h ep r o b l e m so f s h e l f p o l i c y t h i st e x ta c c o r d i n gt ot h es p e c i f i cr e q u i r e m e n t so fw a r e h o u s i n gm a n a g e m e n t , d e v e l o p e daw a r e h o u s i n gm a n a g e m e n ts y s t e mb a s e do n j 2 e ef r a m e w o r ka n ds o l v e d t h es h e l fp o l i c yp r o b l e m t h i ss y s t e mw a sa p p r e c i a t e db ys o m ed o m e s t i c w e l l k n o w nl o g i s t i c sc o m p a n i e s ，s or e s e a r c h ，d e s i g na n di m p l e m e n t a t i o nm e t h o d p r e s e n t e di nt h i sa r t i c l ei sv a l u a b l ef o rl o g i s t i e sc o m p a n i e s k e yw o r d s ：l o g i s t i c s ；w a r e h o u s em a n a g e m e n t ；g a ：j 2 e e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得成都堡王太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 ， 学位论文作者导师签名：凰瘩t 巳一j 学位论文作者签名： 隅肛 2 口d 7 年r 月z5 e t 学位论文版权使用授权书 本学位论文作者完全了解盛趣堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛都理三太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位敝作糍各陈拉 2 丽年y 只2 5 i t 第1 章引言 1 1 研究背景 第1 章引言 随着我国社会主义市场经济体系的建设、世界经济全球化进程的加快和科 学技术的飞速发展，物流业作为国民经济中的一个新兴的产业部门，已成为本 世纪我国产业和国民经济中新的增长点。中国一体化的物流服务业已逐渐成为 一个发展迅速的新兴的产业，并得到了极大的发展，形成了全方位立体的专业 物流网络体系。众多的运输、仓储、货代、联运等企业纷纷向物流领域拓展， 一批新兴的物流企业在市场中大量涌现，其中第三方物流逐渐成为我国物流行 业的发展趋势。 现代物流的发展趋势是信息化、自动化、网络化和智能化。我国物流各个 环节如运输、仓储、配送的成本以及劳动力和设备成本都远远低于发达国家， 而整个物流过程的综合成本却大大高于发达国家。其主要原因，就是物流各环 节信息化程度低，信息沟通不畅，造成库存大，运力浪费。为了降低物流成本， 实现“按需生产、零库存、短在途”的目标，我国物流行业已经达成共识，必须 大力发展现代物流，充分利用信息技术，让“信息流”主导“物品流”，通过信息 化来实现“物流”的准确配置，将生产地和流通过程中的库存降到最低。可以说， 现代物流就是“传统物流+ 信息化”，信息化成为现代物流的灵魂和关键。 现代物流通过信息化的手段进行运输，实现运输、仓储、配送的高效一体 化。其主要目的就是通过快速、准确地传递物流信息，使生产厂商实行准时制 生产，物流提供商实行准时制配送，以“信息”降低“物流”，将生产地和流通过 程中的库存降到最低，甚至达到“零库存”或“零距离”，由此降低物流费用。我 国物流企业的信息化建设起步较晚，目前距离物流信息化的目标还有很大差距。 随着我国经济的发展和信息技术的进步，我国物流信息化已进入了快速发展期。 而物流的发展、优化实际上归结为仓储的方案设计与运行控制。现代物流的发 展历史就是库存成本在总物流成本中所占比重逐步降低的历史。仓储管理已成 为供应链管理的核心环节，成为企业第三个利润源泉。现今仓库作业和库存控 制作业已十分多样化、复杂化，光靠人工去记忆去处理已十分困难。因而，“信 息化是现代仓储管理的核心”的理念已经成为企业及生产厂的共识。如何应用仓 储信息化管理，帮助我们合理有效地利用仓库空间，以最快速、最正确、最低 成本的方式为客户提供高效率、低成本的现代物流服务，已经成为新的利益增 长点。 为此，开发仓储管理系统( w m s ) 对于建立整个物流信息系统，解决物流 成都理工大学硕士学位论文 企业当前急需解决的问题具有非常重要的现实意义。本文就如何建设仓储管理 系统，试图找出适合物流企业的构建思路。同时将遗传算法的思想引入到上架 策略中，为优化上架策略提供了一种解决方案，并在此基础上设计实现了仓储 管理系统，希望本文所做的探讨以及设计和实现的思路能够对物流企业，和第 三方物流有一些参考价值。 1 2 物流与物流的信息化 1 2 1 物流的概念 物流可以从不同的角度进行定义，但最广泛的定义为：物流是供应链运作 中，以满足顾客要求为目的，对货物、服务和相关信息在产出地和销售地之间 实现高效率和低成本的正向和反向的流动和存储所进行的计划、执行和控制的 过程。 物流过程综合了运输、存货、管理、仓储、物料搬运系统及包装和其他相 关活动，包括在整个供应链( 从供应商开始，一直到客户) 的流动的成本与服 务水平的权衡取舍。 物流包含效率( e f f i c i e n t ) 和效益( e f f e c t i v e ) 两方面，物流管理的最终目 的是满足客户的需求与企业的目标。 1 2 2 物流的信息化 现代物流信息系统是以现代物流思想体系为基础，依靠现代科学技术，特 别是计算机和网络等信息技术，在计划、管理和控制以及作业环节等方面充分 利用信息，快速反馈信息，为决策提供依据并辅助决策，提高物流效率和优化 供应链的信息系统。 物流信息系统的目的是，提高物流业务的效率和降低成本的同时，支持提 高对顾客的服务水平。 物流信息系统的发展大致可以分为四个阶段： 1 ) 物流信息系统的开始阶段 2 ) 初步使用自动化设备阶段 3 ) 综合信息系统阶段 钔网络化的物流信息系统 1 2 3 现代物流信息系统的功能 物流业务是企业的根基业务之一。为了打好根基，建立强固的基础，物流 信息系统起着重要的作用。现代物流信息系统的基本功能有以下几个方面： 2 第1 章引言 1 ) 正确掌握订货信息并进行传送的功能 正确掌握订户信息是物流信息系统的入口。订货信息是企业从外部得到的 重要信息，根据订货信息能够掌握畅销商品和滞销商品，灵活的应用和分析订 货信息能够使企业得到大的发展。主要的信息包括：订货信息的出库业务、订 货信息的市场业务、订货信息的制造业和销售商。 2 ) 正确掌握物的移动并进行传送的功能 物流信息系统的最基本的功能是正确的掌握物的移动的功能。主要包括： 仓库业务中物的移动、运输业务中物的移动、出库业务中物的移动。 3 ) 对顾客提供信息的功能 信息不仅是在企业内部的应用，与顾客交换信息已是企业战略的重要部分， 对顾客提供的信息包括到货信息、订货信息、货物追踪信息及市场状况信息等。 钔控制各计划和实施的功能 主要涉及的方面是计划指标的制定、基础数据的收集等。 1 3 仓储管理 支撑物流产业大厦的全部物流活动可以分为六大类基本活动，即运输、储 存、包装、装卸、加工和物流信息。其中，有三大支柱性活动，即运输、储存 和加工。存储需要仓库，需要仓库管理，因此通常把仓库和存储合并起来，统 称为仓储。 1 3 1 仓储在物流系统中的作用和功能 从宏观上看，仓储是一项必要的功能，它为原材料、工业货物和产成品产 生时间效用。通过仓储，公司能在顾客要求的时间和地点将货物交到顾客手上。 随着顾客服务在物流行业中重要性的加强，仓储功能变得越来越重要。仓库在 物流系统中扮演了包括运输整合、产品组合、交叉收货、服务、等一系列增加 附加值的作用。 现代仓储的功能与传统仓储的功能相比已发生了很大变化。仓储在过去一 般起着长期存储原材料及产成品的战略角色，它们的存货水平较高。现代仓储 已转变为以较短周转时间、较低存货率、较低的成本和较好的顾客服务为内容 的物流目标。 仓库按照不同的标准可以分为不同的类型，但仓库基本的功能主要有以下 几个方面：储存保管、集散货物、衔接供需、客户服务、防范风险及物流中心 的功能。 成都理工大学硕士学位论文 1 ，3 2 仓储作业流程管理 仓储管理的一个非常重要的内容就是仓储作业管理。仓储作业是完成仓库 物资储存、入库、出库以及流通加工等不可缺少的手段。仓储作业是一个系统， 它是由各个环节、作业单位协调配合，共同完成的。仓储作业流程的管理不但 包括具体的作业实际流程管理，还包括作业信息流程的管理，即管理信息系统。 整个仓储作业，基本上包括进货入库、储存保管和出库发送三个阶段。三 个阶段相互衔接，共同实现仓库的所有功能。仓储作业的最根本的目的，就是 满足用户对商品的需要。流程如图1 1 图1 - 1 仓储作业流程 1 3 3 储存合理化管理 储存合理化就是建立合适的储存条件，对合适的储存品种进行合适的库存 管理的综合性系统工程。储存合理化具体包括储存条件合理化、储存品种结构 合理化、储存数量合理化和储存时间合理化。 1 ) 储存品种结构合理化 储存品种结构合理化就是要有一个合理的库存品种建构，要选择那些符合市 场需要、适销对路的品种，保证库存品种都能够在不太长的时间内销售出去。 2 ) 储存数量合理化 储存数量合理化就是要控制合适的库存数量，库存管理工作的核心就是要进 行库存控制。 3 ) 储存时间合理化 储存品不能超过额定储存期，一般要执行“先进先出”原则，保证各个产品 都能够正常流转，提高库存周转率和库存利用率。 4 ) 储存条件合理化 主要是要建立起一个完善合理的保管场所和条件。如仓库的地质地理条件、 温度湿度通风光照条件、防火防盗安全条件、仓储规划布局等等。 4 第1 章引言 1 4 本文简述 1 4 1 本文的工作和结构简述 随着i n t e m e t 的快速发展和广泛应用，物流企业越来越认识到企业信息化的 重要性，依靠计算机技术和科学管理己成为企业持续发展的必要环节。 本文所讲述的系统即是当前国内的某家物流公司在仓储管理方面的信息化 建设，该系统是根据该公司的实际需求，结合当前最新的计算机技术所设计完 成的。由于物流业务繁多复杂，因此物流公司需要一个统一的、安全的、可扩 展的、可靠的系统。本系统以j a v a 为基础，采用依托与j 2 e e 框架的 w e b w o r k s p r i n g h i b e m a t e 技术来实现的。因此它的可靠性和可扩展性都是值得 保障的。 本文的组织结构： 第一章：绪论，主要讲述了物流知识以及当前物流业的信息化。 第二章：j 2 e e 技术与遗传算法概述，讲述了本系统所依赖的技术平台以及 遗传算法的介绍。 第三章：系统的详细设计，主要讲述的是物流公司的具体需求以及根据该 需求对系统功能所作的要求。 第四章：系统的具体实现，主要讲述在程序上的实现。 第五章：总结与展望，主要讲述对本文的简单评价。 1 4 2 系统的优势和特点 1 、b s 为主的系统结构 在过去c s ( 客户器服务器) 结构的软件一统整个软件市场，但随着软件 技术和互联网技术的发展，b s ( 浏览器服务器) 结构的软件成为软件实现风 格的主流。采用b s 结构实现软件系统，给企业带来的最大好处就是： 1 1 大大降低企业对系统的维护成本，因为只要使用者的计算机上装有网络 浏览器，它就能运行系统，从而结束了c s 结构按点安装和维护的时代。 2 ) 大大增加了系统对企业业务发展的适应性，因为一个企业随着业务的发 展，可能要增加或改变系统中的功能。在c s 结构模式下的软件系统对客户的 这种变化，将反映迟钝，而且升级将对客户日常的工作带来很大的影响。在b s 结构模式下的系统，将可以对客户的变化，做出快速的反映，而且系统的升级 对使用者来说是透明的，很少会对客户企业的日常工作带来很大的影响。 3 ) 无缝的向电子商务企业信息化过渡，只要客户想建立自己企业电子商务 平台，建立在原有的b s 结构的系统之上，那只是整个企业信息化系统的扩充， 而不是整个企业系统的改造。从而让企业以最低的成本、最短的时间实现企业 5 成都理工大学硕士学位论文 电子商务化。在局部采用c s 模式开发的功能模块：可以弥补因主体b s 模 式下，现有技术无法实现的一些功能模块。但是在设计时，c s 模式将融入主 体b s 模式中，共享共同的数据资源。 2 、高保密性与安全性的实现 为了保证系统的安全，在设计系统时，按物流中心的组织结构和人员的工 作岗位设置权限角色。比如；仓库管理员、仓库作业员、业务经理、业务员等 等角色。然后把角色赋给具体的系统使用用户。物流中心的员工只有在输入正 确的用户名和登录密码才能进入系统，而且进入系统后，也只能使用自己角色 范围内的系统功能。 对于仓库，在系统中将对仓库操作进行控制，特别是对于多仓库的物流中 心，有仓库作业员角色权限的用户并不需要对每个仓库进行操作。系统提供仓 库作业员分配功能，作业操作员只能对自己被分配到的仓库进行作业，一个操 作员也可以对多个仓库进行操作。 3 、在上架策略中遗传算法的应用 物流企业中库存的大小是确定的，充分的利用库存是节约成本的必然做法， 上架策略关系到物品的存放问题，合理的存放能够充分的利用空间。遗传算法 ( g e n e t i ca l g o r i t h m ，简称g a ) 作为模拟自然界生物进化原理的一种随机 性全局优化概率搜索算法，具有很强的全局搜索能力，特别适合求出问题的近 似最优解，因而用遗传算法解决装货上架问题是一个好的选择。 6 第2 章j 2 e e 技术与遗传算法概述 第2 章j 2 e e 技术与遗传算法概述 1 9 9 9 年6 月，在旧金山召开的j a v a o n e 大会上，s u n 公司宣布了一种新的j a v a 体系架构，并针对不同类型的应用提供了不同的版本：j 2 s e ( j a v a2s t a n d a r d e d i t i o n , j a v a2 标准版) ，用于桌面和工作站设备；j 2 m eo a v a2m i c r oe d i t i o n , j a v a2 小型版) ，用于移动电话和p d a 等小型设备；j 2 e e ( j a v a2e n t e r p r i s e e d i t i o n , j a v a2 企业版) ，用于企业服务器。 j 2 e e 设计的目的是专门为了推动企业应用的开发和部署，它是通过对分布 式多层应用既提供客户方功能又提供服务器方功能来达到这个目的。从根本上 说，j 2 e e 是个企业应用开发平台，该平台是为开发人员提供应用程序编程接 口( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e , a p i ) 、服务和协议的个统一的集合， 这些a p i 、服务和协议一同提供对于构建分布式多层应用所必须的特性和功能。 2 1 分布式的多层应用程序 j 2 e e 平台使用多层分布式的应用模式。应用逻辑根据其功能分成多个组 件，各种不同的应用组件构成分布在不同的依赖于层的机器上的j 2 e e 程序( 如 图2 ) 。下面列出了位于不同层的组件 1 ) 运行在客户机上的客户层组件 2 ) 运行在j 2 e e 服务器上的中间层 3 ) 运行在e i s ( e n t e r p r i s ei n f o r m a t i o ns y s t e m ) 服务器上的企业信息层 中间层可以进一步划分为w e b 层和e j b 层，基于这种逻辑分离，再加上良 定义的接口，就可以构建具有客扩展性的应用。随着需求的增加，这些层次可 以得到分离，并分布在多个服务器上。 客户层包含浏览器和常规的g u i 应用，客户通过浏览器使用h t t p 与w e b 容器通信。中间层通过w e b 容器和e j b 容器提供客户服务。通过h r r p 与服务 器通信的客户可以使用w e b 容器中的组件，如s c r v l e t 和j s p 页面，以此作为 应用的入口点。e i s 层保存应用的业务数据，通常它由一个或多个关系数据库 管理服务器组成。 7 成都理工大学硕士学位论文 企业信息系 统( e i s ) 层 客户层 相层。向硇jb z 伺甄 l d a o 一_ d o m a i no b j e c t 这种模型的优点： 1 、各层单向依赖，结构清楚，易于实现和维护 2 、设计简单易行，底层模型非常稳定 这种模型的缺点： 1 、d o m a i no b j e c t 的部分比较紧密依赖的持久化d o m a i nl o g i c 被分离到s e r v i c e 层，显得不够面向对象 2 、s e r v i c e 层过于厚重 三、充血模型 充血模型和第二种模型差不多，所不同的就是如何划分业务逻辑，即认为， 绝大多业务逻辑都应该被放在d o m a i no b j e c t 里面( 包括持久化逻辑) ，而s e r v i c e 层应该是很薄的一层，仅仅封装事务和少量逻辑，不和d a o 层打交道。 s e r v i c e ( 事务封装) d o m a mo b j e c t 一d a o 这种模型的优点： 1 、更加符合面向对象的原则 2 、s e r v i c e 层很薄，只充当f a c a d e 的角色，不和d a o 打交道。 这种模型的缺点： 1 、d a o 和d o m a i n o b j e c t 形成了双向依赖，复杂的双向依赖会导致很多潜在的 问题。 2 、如何划分s e r v i c e 层逻辑和d o m a i n 层逻辑是非常含混的，在实际项目中，由 于设计和开发人员的水平差异，可能导致整个结构的混乱无序。 3 、考虑到s e r v i c e 层的事务封装特性，s e r v i c e 层必须对所有的d o m a i no b j e c t 的逻辑提供相应的事务封装方法，其结果就是s e r v i c e 完全重定义一遍所有的 d o m a i nl o g i c ，非常烦琐，而且s e r v i c e 的事务化封装其意义就等于把面向对象 的d o m a i nl o g i c 转换为过程的s e r v i c et r a n s a c t i o n s c r i p t 。该充血模型辛辛苦苦在 d o m a i n 层实现的面向对象在s e r v i c e 层又变成了过程式，对于w e b 层程序员的 角度来看，和贫血模型没有什么区别了。 四、胀血模型 基于充血模型的第三个缺点，有人提出，干脆取消s e r v i c e 层，只剩下d o m a i n o b j e c t 和d a o 两层，在d o m a i n0 _ b j e c t 的d o m a i nl o 百c 上面封装事务。 d o m a i no b j e c t ( 事务封装，业务逻辑) d a o 该模型优点： 1 5 成都理工大学硕士学位论文 l 、简化了分层 2 、也算符合面向对象 该模型缺点： 1 、很多不是d o m a i nl o g i c 的s e r v i c e 逻辑也被强行放入d o m a i no b j e c t ，引起了 d o m a i no j b e c t 模型的不稳定 2 、d o m a i no b j e c t 暴露给w e b 层过多的信息，可能引起意想不到的副作用。 在这四种模型当中，失血模型和胀血模型是不被提倡的。而贫血模型和充 血模型从技术上来说，都已经是可行的了。当前比较流行使用的是贫血模型。 其原因是： l 、参考充血模型第三个缺点，由于暴露给w e b 层程序拿到的还是s e r v i c e t r a n s a c t i o ns c r i p t ，对于w e b 层程序员来说，底层面向对象意义丧失了。 2 、参考充血模型第三个缺点，为了事务封装，s e r v i c e 层要给每个d o m a i nl o g i c 提供一个过程化封装，这对于编程来说，做了多余的工作，非常烦琐。 3 、d o m a i n o b j e c t 和d a o 的双向依赖在做大项目中，考虑到团队成员的水平差 异，很容易引入不可预知的潜在b u g 。 4 、如何划分d o m a i nl o g i c 和s e r v i c el o g i c 的标准是不确定的。 5 、贫血模型的d o m a i no b j e c t 确实不够强大。 2 6 遗传算法 2 6 1 遗传算法的基本概念 1 生物进化理论 遗传算法是借鉴生物界“适者生存”原则的一种优化算法。我们先了解有 关生物进化理论。 生命是进化的产物，其基本特征包括生长、繁殖、新陈代谢和遗传与变异。 达尔文用自然选择来解释物种的起源和生物的进化，其自然选择学说包括以下 三方面： ( 1 ) 遗传 这是生物的普遍特征，“种瓜锝瓜，种豆得豆”，亲代把生物信息交给子代。 子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的性状。 生物具有了这个特征，物种才能稳定存在。 ( 2 ) 变异 亲代和子代之问以及子代的不同个体之间总有些差异，这种现象，称为变 异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 ( 3 ) 生存斗争和适者生存 1 6 第2 章j 2 e e 技术与遗传算法概述 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行， 其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的 个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向 积累，于是性状逐渐和原先的祖先种不同，演变为新的物种。这种自然选择过 程是一个长期的、缓慢的、连续的过程。 2 遗传算法的基本概念 既然遗传算法是基于自然选择的生物进化，是一种模仿生物进化过程的随 机方法。故而在该算法中要用到生物遗传学的知识，下面给出几个在遗传算法 中很重要的基本概念和术语： ( 1 ) 染色体 遗传物质的主要载体，有多个遗传因子基因组成；在算法中为解的编 码( 字符串，向量等) 。 ( 2 ) 基因 d n a 或r n a 长链结构中占有一定位置的基本遗传单位；在算法中为解中每 一分量的特征。 ( 3 ) 个体 指染色体带有特征的实体；在算法中为解。 ( 4 ) 适应度 表示某一个体对于环境的适应程度；在算法中为适应函数值。 ( 5 ) 种群 染色体带有特征的个体的集合，该集合内个体数称为群体的大小；在算法 中为选定的一组解。 ( 6 ) 复制 细胞在分裂时，遗传物质d n a 通过复制而转移到新产生的细胞中，新的细 胞就继承了旧细胞的基因；在算法中为根据适应函数值选取的一组解。 ( 7 ) 交叉 有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即 在两个染色体的某一相同位置处d n a 被切断，其前后两串分别交叉组合形成两 个新的染色体。这个过程又称基因重组，俗称“杂交”。在算法中为通过交配 原则产生一组新解的过程。 ( 8 ) 变异 在细胞进行复制时可能以很小的概率产生某些复制差错，从而使d n a 发 生某种变异，产生新的染色体，这些新的染色体表现出新的性状。在算法中表 现为编码的某一个分量发生变化的过程。 成都理工大学硕士学位论文 2 6 2 遗传算法的基本原理 遗传算法是一种建立在自然选择和群体遗传机理基础上的自适应概率性搜 索算法，它根据“适者生存，优胜劣汰”等自然进化规则演化而来。与传统搜 索算法不同，遗传算法把优化问题的解的搜索空间映射为遗传空间，把每一可 能的解编码为一个称为染色体的二进制串( 也有其它编码方法) ，染色体的每一 位称为基因。每个染色体( 对应一个个体) 代表一个解，一定数量的个体组成 群体。 搜索时，首先随机地产生一些个体组成初始群休( 即问题的一组候选解) ， 初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越 好的近似解。在每一代，按预先根据目标函数确定的适应度函数计算个体的对 问题环境的适应度，再根据个体适应度对个体对应的染色体进行选择，抑制适 应度低的染色体，弘扬适应度高的染色休，然后进行选择、交叉、变异等遗传 操作。如此反复操作，一代一代不断向更优解方向进化，从而获得问题的最优 解。 遗传算法是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化， 具有广泛使用性的搜索方法，是借鉴自然选择和自然进化原理，模拟生物在自 然界中的进化过程所形成的一种优化求解算法。尽管这种自适应寻优技术可用 来处理复杂的线性、非线性问题，但它的工作机理却十分简单。标准遗传算法 的步骤如下： 1 构造满足约束条件的染色体。染色体是根据问题特点，选择适当的编码方 式，对应问题解的一种编码方案。 2 随机产生初始群体。初始群体是一组染色休的集合，其数量要根据问题的 规模及编码方案适当选择。 3 计算每个染色体的适应度。适应度是反映染色体优劣的唯一标准。遗传算 法就是要寻找适应度最大的染色体。在实际应用中即是最优解的编码形式，有 时也可能是次优解。 4 使用复制、交叉和变异等算子对初始群体进行变换产生新的群体。 5 重复步骤3 、4 直到新的群体中存在满足条件的染色体终止。 2 6 3 遗传算法的特点 为了解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形 法、梯度法、动态规划法、分枝定界法等。这些优化算法各有各的长处和限制， 有各自不同的适用范围。与普通的搜索算法( 如梯度算法) 一样，遗传算法也 是一种迭代算法。但是与其他一些优化搜索算法相比，遗传搜索要求两个存在 第2 章j 2 e e 技术与遗传算法概述 明显冲突的方向之间的平衡：挖掘最优解和探测搜索空问。爬山法是尽可能地 改进挖掘最优解策略的例子，但它忽视了对搜索空间的探测。随机搜索是一个 注重探测搜索空间而忽视挖掘最优解的典型例子。遗传算法则是在总体上寻求 挖掘和空间探测之问平衡的一类算法。 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法。与其他一些优 化算法相比，它主要有下述几个特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象( 函数优化中有时也采用决策变 量本身作为运算对象，可以视为简单的代数编码) 。传统的优化算法往往直接利 用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的 值，而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处 理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念， 可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传 操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优 化问题，编码处理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息，并不利用梯度信息，无需求 导运算。传统的数值优化算法不仅需要利用目标函数值，而且往往需要目标函 数的导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标 函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需 目标函数的导数值等其他一些辅助信息。这个特性对很多目标函数是无法或很 难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应 用遗传算法时就显得比较方便。因为它避开了函数求导这个障碍。再者，直接 利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较 高的部分搜索空间中，从而提高了搜索效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，是一种群体优化过程。传统 的优化算法往往是从解空间中的一个初始点开始，进行最优解的迭代搜索。单 个搜索点所提供的搜索信息毕竟不多，虽然搜索效率较高，但容易使搜索过程 陷于局部最优解而停滞不前。遗传算法从由很多个体所组成的一个初始群体开 始最优解的搜索过程，而不是从一个单一的个体开始搜索。对这个群体所进行 的选择、交叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很 多群体信息。这是遗传算法所特有的一种并行性。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性 的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系， 这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应 用范围而遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运 1 9 成都理工大学硕士学位论文 算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这 种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行， 新的群体中总会更多地产生出许多优良的个体，实践和理论都己证明了在一定 条件下遗传算法总是以概率1 收敛于问题的最优解。当然，交叉概率和变异概 率等参数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数 在其应用中是一个比较重要的问题。而另一方面，与其它一些算法相比，遗传 算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能地低。 2 6 4 遗传算法中的基本实现技术 l 、编码方法 在遗传算法中，首先要将搜索空间解的表示映射成遗传空间解的表示，这 一操作称为编码，其相反操作称为解码。对编码的基本要求是，两个空间的解 需一一对应，且编码应尽量简明。遗传空间的解又称个体或染色体。个体通常 由字符串表示，字符串的每一位称为遗传因子。多个个体组成一个种群供遗传 算法使用。值得一提的是，遗传算法不仅可以对数值符号集组成的字符串进行 操作，还能够直接对结构对象进行操作。所谓结构对象泛指集合、序列、矩阵、 树结构、图和表等各种结构形式的对象。遗传算法的这个特点使它具有广泛的 应用领域。 一 编码是连接问题与算法的桥梁、应用遗传算法是要解决的首要问题，也是 设计遗传算法时的一个关键步骤。编码方法除了决定个体的染色体排列形式外， 还决定了个体从遗传空间的基因型变换到搜索空间的表现型时的解码方法；编 码方法也影响到交叉算予、变异算子等遗传算子的运算方法。由此可见，编码 方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效 率。一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作可以简 单的实现和执行。反之，可能使得交叉运算、变异运算等遗传操作难以实现， 也可能产生很多无效解。 h o l l a n d 的编码方法是二进制编码，但对于许多遗传算法的应用，特别是 在工业工程中的应用，这种简单的编码方法很难直接描述问题的性质。近十年 来，针对特殊问题，人们提出了其它编码方法。例如：格雷编码、浮点编码、 符号编码。 二进制码编码、解码操作简单易行，不仅便于实现交叉、变异等进化操作， 而且便于利用模式定理对算法进行理论分析。雷码是二进制码的变形，具有与 二进制码相似的特点，其编码、解码操作相对复杂，但基于格雷编码的算法局 部搜索能力有较大提高。浮点编码方式编码长度等于参数向量的维数，达到同 等精度要求的情况下，编码长度远小于二进制码和格雷码。此外，浮点编码使 第2 章j 2 e e 技术与遗传算法概述 用的决策变量的真实值，不需反复进行数据转换。符号编码方法是指染色体编 码串中的基因值取一个无数值含义、而只有代码含义的符号集这些符号可以 是字符，也可以是数字。符号编码的主要优点是便于在遗传算法中用所求问题 的专门知识及相关算法。 对于非二进制编码，染色体编码与问题的解之间有三个主要问题：染色 体的可行性；染色体的合法性；映射的唯一性。可行性是指染色体编码 成为解之后是否在给定问题的可行域内。合法性是指染色体编码是否代表给定 问题的一个解。 2 、适应度函数 遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或 接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概 率就较大：而适应度较低的个体遗传到下一代的概率就较小。度量个体适应度 的函数称为适应度函数。 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利 用种群中每个个体的适应度值来进行搜索因此适应度函数的选取至关重要， 直接影响到遗传算法的收敛速度以及能否找到最优解，合理的适应度函数能引 导搜索向最优化方向进行，设计不当有可能会产生问题。此外，它对遗传算法 的终止搜索条件也有影响。值得提出的是，作为一种随机搜索方法，遗传算法 的适应度函数或目标函数不受连续可微的约束，而且函数的定义域可以是任意 集合。对目标函数的唯一要求是对于输入可以计算出能加以比较的输出。当然 适应度函数设计应尽可能简单，以减少计算时间和空间上的复杂性。一般而言， 适应度函数是有目标函数变换而成的。对目标函数值域的某种映射变换称为适 应度的尺度变换。常用的变换方法有：线性尺度变换、方差缩放技术、乘幂尺 度变换和指数尺度变换。基本遗传算法中采用的是线性尺度变换。 3 、选择算子 选择源于对自然界优胜劣汰竞争原则的模拟。在生物的遗传和自然进化过 程中，对生存环境适应程度较强的个体，将有更多的机会遗传到下一代，繁殖 下一代的数目较多；而对环境适应程度较差的个体将遗传到下一代的机会就较 少，甚至被淘汰。这样，就更容易产生对环境适应能力较强的后代。 遗传算法中所谓选择运算即从上一代种群中选择一定量染色体到新一代种 群的方法。优胜劣汰的选择机制使得适应值大的解有较高的存活概率，这是遗 传算法与一般搜索算法的主要区别之一。发展各种选择算子的目的是为了避免 基因缺失，提高遗传算法的全局收敛性和搜索效率。 选择策略对算法性能的影响会起到举足轻重的作用。不同的选择策略对算 成都理工大学硕士学位论文 法的性能也有较大的影响。不同的选择策略将导致不同的选择压力，即下一代 中父代个体的复制数目的不同分配关系。较大的选择压力使最优个体具有较高 的复制数目，从而使得算法收敛速度较快，但也较容易出现过早收敛现象。相 对而言，较小的选择压力一般能使群体保持足够的多样性，从而增大了算法收 敛到全局最优的概率，但算法的收敛速度一般较慢。 选择算子的设计的内容就是确定如何从父代群体中按某种方法选取个体遗 传到下一代群体中。常用的选择算策略包括：比例选择、最优保存策略、确定 式采样选择、无回放随机选择、无回放余数随机选择。比例选择方法简单，但 容易出现早熟收敛，速度慢现象无回余数随机选择降低了选择误差，保证优 秀个体的遗传，但操作相对复杂确定式采样选择降低了选择误差，操作相对 于无回余数随机选择简单。基本遗传算法中采用的是比例选择。 4 、控制参数 在进行遗传算法程序时，要对一些参数做事先选择，它们包括群体规模、 交叉概率、变异概率、最大进化代数、染色体的长度等。这些参数对遗传算法 性能有很重要的影响。这些参数的选择和设定目前尚无统一的理论指导，多数 都视具体问题而定。对一个具体问题，要想获得最优的参数设置，通常采取试 验法和二级演化算法( m e t a - - e a ) 两种方法之一，虽然这两种方法能就某一 类问题获得较佳的参数设置，但由于它们的计算量都比较大，从而在计算实际 问题时用得并不是很多。常用的方法是根据经验设定控制参数值，然后多执行 算法几次以获得问题的最优或近似最优解。 2 6 5 遗传算法在上架问题中的应用 遗传算法作为模拟自然界生物进化原理的一种随机性全局优化概率搜索算 法，具有很强的全局搜索能力，特别适合求出问题的近似最优解。由于遗传算 法在组合优化问