（地图学与地理信息系统专业论文）webgis中基于遗传算法的最短路径求解方法研究.pdf

华东师范大学2 0 0 6 届顸i ：学位论文w e b g i s 中基于遗传算法的最短路径求解方法 i j l 究 摘要 空间分析功能是g i s 的重要特色。最短路径分析是g i s 空间分析中应用最为 广泛的分析功能之一，也一直作为计算机科学、运筹学、地理信息科学等学科的 一个研究热点。 我们通常所指的最短路径是找出给定的两点之间的最短路经。最短路径分析 已经在桌面g i s 中得到了很好的应用，但在w e b g i s 中的应用还较欠缺，w e b g i s 目前已经成为g i s 研究的一个亮点。用遗传算法来求解最短路径的相关研究也比 较少，作者参考前人的研究成果，在对前人的成果改进的基础上，结合遗传算法 的特点，设计出了自己的算法方案。本文在第四章对设计方案进行了详细的说明。 根据该方案，作者用j a v a 语言实现了该模块，并用一个简单的应用程序说明了 该方案的可行性及该模块的可用性。 论文共分六章。第一章绪论，说明选题背景、相关研究进展和介绍整个论文 的框架；第二章遗传算法及其基本理论简介，介绍了遗传算法的一些相关概念， 特点及相关的原理，为本文的提供了理论基础：第三章拓扑结构构建，说明了拓 扑结构构建的重要性，以网络图论、空间网络构成及m o 中拓扑结构相关理论为 基础，设计了拓扑构建方案，为最短路径算法提供数据基础；第四章基于遗传算 法的最短路径策略，本章是论文的核心部分，作者给出了最短路径方案设计流程， 并从算法各参数选择、算子设计和优化等方面对方案进行了说明。第五章算法实 现及应用实例，给出了算法实现的流程，并对模块和关键接口的功能进行说明， 最后用一个简单的实例说明该模块的可行性及效果。最后一章足结语，包括总结 和展望，指出了作者算法中有待进一步研究和扩展的些思考。 本文基于遗传算法以长度作为权重来求解最短路径问题，针对不同权重字段 的情况，可以参考作者的方案中等级分类的思想对点集做适当的分类，就可达到 良好的效果。作者对该问题进行了富有成效的研究，在理论方面有所创新，并用 j a v a 实现了算法，为最短路径在w e b g i s 中的应用提供了基础，同时给出了一些 应用方面的建议。 关镭! ：同：g i s ，w 曲g i s ，遗传算法，最短路径，拓扑结构 华东师范大学2 0 0 6 届硕士学位论文 w e b g i s 中摹于遗传算法的避短路径求斛方法研究 a b s t r a c t t h ef u n c t i o no fs p a t i a la n a l y s i si st h ei m p o r t a n tc h a m c t e r i s t i co fg i s s h o r t c u t a n a i y s i si so n eo ft h em o s tw i d e i yu s e da 1 1 a l y s i sf u n c t i o n si ng i ss p a t i a 】a 1 1 a l y s i s i ti s a l s oar e s ea 1 _ c hh o t s p o ti nc o m p u t e rs c i e n c e ，o p e r a t i o n a ir e s e a r c ha 1 1 dg e o g r a p h i c a l 1 1 1 f o m l a t i o ns c i e n c e t h es h o r t c u tw ec o m m o n l yp o i n t e di s t 1 1 es 1 1 ( ) r t c u tb e t w e e nt w op o i n t sg i v e nb y u s s h o r t c u ta n a l y s i sh a sb e e nu s e dv e r yw e l lo nd e s k t o pg i s ，b u ti ti sv e r yp o o r l y u s e di nw e b g i s w e b g i sh a sb e e nal i g h tp o i n ti ng i sr e s e a r c h t h er e s e a r c ho n s 0 1 v i n gs h 。r t c u tp i d b l e mb yu s i n gg e n e t i ca l g o r i t h m si sv e r yp o o lt h ea u t h o ro ft h i s a r t i c l ed e s i g n sh i sa 1 9 0 r i t l n sb l u e p r i n tb yi 1 1 t e g r a t i n gt h ec h a r a c t e r i s t i c so fg e n e t i c a l g o r i t h m so nm eb a s i so ft h ei m p r o v i n gt h er e s e a r c h 自j i to fm ep r e d e c e s s o r s c h a p t e rf o u ro fm i sa n i c l em a k e sad e t a i l e de x p l a n 撕o no ft h ed e s i g n j n gs c h e m e a c c o r d i n gt o t 士l i sd c s i 朗i n gs c h e m e ，m ea u t h o ri m p l e m e n t st h em o d u l ei nj a v a l a n g u a g ea n di l l u s t r a t e st h ef e a s i b i l i t yo f 也i sd e s i g i ls c h e m ea n dt h eu s 如i l i t yo ft h e m o d u l e t h i st h e s i sc o n s i s t so fs i xc h a p t e r s t h ef i r s tc h a p t e rs e e sa sa ni n t r o d u c t i o nt o e x p l a i nt h eb a c k g r o u n do ft h es u b j e c t ， r e l e v a n tr e s e a r c h d e v e l o p m e n ta n dt h e 丘a m e w o r ko ft h i sa n i c l e t h es e c o n dc h a p t e rd e a l sw i mg e n e t i ca l g o r i t l 珊sa n dt h e b r i e fi n 咖d u c t i o nt oi t sb a s i ct h e o r yi ti n t r o d u c e ss o m ec o n c e p t i o n s ，c h a r a c t e r i s t i c s a n dp r i n c i p l e so fg e n e t i ca 1 9 0 r i t h m s ，t h u sp r o v i d i n gat h e o r e t i c a ib a s ef b r t h et h e s i s t h e 也i r dc h 印t e rd e a l sw i t ht h ec o n s t m c t i o no ft 叩o l o g ys t m c t u r e i te x p l a i n st h e i m p o r t a l l c eo ft o p o l o g ys t r u c t u r e a n dd e s i g n si t ss c l l e m eb a s e do nn e t w o r k 铲印h t h e o r y ，s p a t i a ln e 艄r o r kc o m p o n e n t sa 1 1 dt h et h e o r yo ft o p 0 1 0 9 ys t r u c t u r ei nm o t h i s p r o v i d e sd a t ab a s ef o rs h o r t c u ta l g o r i t h m s t h ef o u 曲c h a p t e rd e a l sw i t hm es h o l l c u t s t r a t e g yb a s e do ng e n e t i ca l g o r i t h m s ，i ti st h ek e m e lp a r to ft h et h e s i s t h ea u t h o r g i v e st h ed e s i g n i n gn o wo ft h es h o r t c u ts c h e m ea n de x p l a i n si t 行o mt h ep a r 锄e t e r s e l e c t i o n ，a r i t h m e t i co p e r a t o r sd e s 吐；n i n ga n do p t i m i z a t i o n t h e 丘f t hc h a p t e rd e a l s w i 也m ea l g o r i m m si m p l e m e n ta 1 1 d 印p l i c a t i o ne x a m p l e i tg i v e sn o wo fa l g o r i t h m s i m p l e m e l l t ，e x p l a j l l st 1 1 em o d u l ea n dt h ef b n c t i o n so fk e yi n t e r f a c ea i l di 1 1 u s t r a t e st h e f 音a s i b i i i t ya n dm ee f 话c t so ft h em o d u i eb yu s i n gas i m p l ee x a m p l e t h e1 a s tc h a p t e r s e r v e sa sac o n c l u s i o nw h i c hs u m m a r i z e sa n d1 。o k sa l l e a da n db r i n g sf b r v v a r dw h a ti s g o i n gt od oa tn e x ts t e p i tp o i n to u ts o m ec o n s i d e r a t i o n sc o n c e m i n ga l g o r i t h m st ob e f h r t h e rs t u d i e da n dd e v e l o d e d 华东师范大学2 0 0 6 届硕士学位论文 w e b g i s 中基于遗传算法的最短路径求斛方泣1 1 _ | 艽 t h et h e s i ss 0 1 v e ss h o r t c u tp r o b l e mb yu s i n gl e n g ma saf a c t o rb a s e do ng e n 鲥c a l g o r i t h i n s g o o dr e s u 】t sc a nb ea c h i e v e d 衄o u g hf e l i c i t o u sc l a s s i f i c a t i o no fp o i n t sb y c o n s u 】t i n gt h ea u t h o r ss c h e m e t h ea u t h o rh a sd o n es o m e 行u i t 如1r e s e a r c ho nt h i s p r o b l e m ，a n d t h e r ea r es o m ei n n o v a i i 伽si nm e o r e t j c a l a s p e c t s t h ea u t h o r i m p l e m e n t sa l g o 打t si nj a v a1 a n g u a g e t h i sp r o v i d e sab a s ef o rt h eu s eo fs h o r t c u t i nw e b g i sa n dt h ea u t h o r 百v e ss o m ea d v i c eo na p p l i c a t i o n k e yw o r d ：g i s ，w e b g i s ，g e n c t i c a 1 9 0 r i t h m s ，s h o n c u t ，t 0 p 0 1 0 9 y 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个 人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集 体，均已在文中作了明确说明并表示谢意。 作者签名：盂鲤 学位论文授权使用声明 同期：竺丝3 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学 位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出 版。保密的学位论文在解密后适用本规定。 学位论文作者签名：香遒鼻 导师签名： 日期：型：i ：3 日期 华东师范大学2 0 0 6 届硕t 学位论文w e b g i s 中拱于遗传算法的最短路径求俐万法研究 第一章绪论 1 1 选题背景 中国经济的腾飞，科技起着举足轻重的作用，g i s 作为空间信息技术中一个 重要支撑，它的地位越来越为人们所重视。g i s 作为一个朝阳产业，在近十年蓬 勃发展，应用领域越来越广泛。g i s 的应用领域如此之广，最为关键的是g i s 所 独有的空间分析功能。网络分析是空间分析的核心。最短路径分析属于最优路径 分析的一种，均属于网络分析。最短路径分析也是g i s 空间分析中应用最为广泛 的分析功能之一，也一直作为计算机科学、运筹学、地理信息科学等学科的一个 研究热点 我们通常所指的最短路径是找出给定的两点之i 目的最短路经。最短路径算法 应用广泛，主要应用于公交路线查询、大型物流、邮政路线选择等方面，还有很 多待挖掘的应用领域。最短路径分析已经在桌面g i s 中得到了很好的应用，但对 于w e b g i s 而言，实现这个模块就不能像在桌面g i s 中那样灵活，它会受到网络 模式和开发语言等因素的影响，从而给基于w e b g i s 的最短路径分析功能实现带 来一定困难。随着网络技术飞速发展，网络已经融入到千家万户的生活中，w e b g i s 已经成为g i s 研究的一个亮点。因此在这样个大背景下，研究解决基于w e b g i s 平台的最短路径应用的问题很有现实意义。 目前最短路径求解方法有多种，并且已经有很多成熟的算法，但用遗传算法 来求解最短路径问题方面的研究并不多，相关的论文也很少，成功的应用案例更 是微乎其微。遗传算法( g e n e t i ca l g o r i t h m ，缩写g a ) 是一类模拟生物进化的 智能优化算法，很适合解决最优解问题。最短路径问题属于求解最优问题，它很 好地符合了遗传算法的思想。正是基于此，作者凭借顽强的毅力对该问题进行了 富有成效的研究，在理论方匿有所创新和突破，同时给出了一些应用方砬的建议。 1 2 相关研究进展 鉴于作者研究内容的复杂性，涉及到最短路径问题、遗传算法、拓扑结构、 g i s 等，作者对问题进行了归纳，从以下三个主要方面介绍相关研究进展，其中 遗传算法是本论文研究的核心。 1 2 1 最短路径算法 目前，最优路径问题的求解有很多种算法，其中最为经典的是踟j k s t r a 算 法，常用的也有f 1 0 y d 算法、船算法等。除了此之外，最近几年研究的比较多的 算法有：遗传算法、模拟退火算法、蚁群算法等。 华东师范大学2 0 0 6 屈颂：l 学位论文 w e b g i s 中批卡遗传算法的最短路杼求解方法州究 d i j k s t r a 算法是由b 。w d i j k s t r a 于1 9 5 9 年给出的标号法，它是目前应用 最多也是最为经典的一种最短路径求解算法。从算法提出至今，很多学者对该算 法进行了各种优化和改进。李元臣等采用二叉树结构来改进d i j k s t r a 算法“j ； 文献 2 和 5 中，均采用邻接结点的优化算法，节省了存储空间，实用范围更广； 王杰臣等采用点弧段联合结构表达图，节省空间，提高速度“：夏松等采用快 速排序和插入排序相结合的方式，改进原有算法中对最小权值的顶点的搜索策略 “1 。在作者用遗传算法求解最短路径问题中，受到了其中一些优秀方法的启发。 f l o y d 算法，又称传递闭包方法，是求解所有顶点对f 刮的最短路径问题的一 个经典的算法，其实质就是矩阵自乘n 次。目前研究f 1 0 y d 算法的学者较少，文 献更少，作者对收集到的文献做以归纳：胡桔州阐述了f o l y d 算法的原理并把 f l o y d 算法应用在配送中心选址上“；周炳生给出了图结构中f 1 0 y d 算法的一个 通用程序，并对f l o y d 算法进行了扩充和完善”1 ；程国忠给出了有向网络中每对 顶点间最短路径的变形f l o y d 算法，并对该算法进行详细说明”1 ；郭强作者给 f 1 0 y d 算法配置了一种更便于使用的路径标记方法，还给出了在无向网络上减少 f 1 0 y d 算法的计算量的方法。3 。相比较而言，f l o y d 算法研究成果较少，应用领 域也相对较窄。 a $ 算法是一项古老的技术，最初被用来解决各类数学问题。在人工智能的早 期研究中，它被用来解决寻路问题。胁算法的原理是设计一个评价函数，由该函 数可获得各点的代价，每次搜索时，通过评价函数对下一步可能到达的点逐一进 行评价，并取出代价最小的点继续往下搜索，那些没被选上的点就不会被继续搜 索。张前哨在其硕士毕业论文中对胁算法解决地图寻径进行研究，根据地图数 据的特点结合传统寻径方法，对a $ 算法进行改进，获得了较好的效果“”；黄文 生对a $ 算法及可采纳性进行了详细的论述和证明，并通过一个求最短路径的实 例说明了a 丰算法在实际中的具体应用l ；王德春等人用a 算法选择航船最佳航 线，对算法中的估价函数迸行定量描述，并与传统求解算法做比较，说明了浚算 法的优越性“；高庆吉等人利用改进的a 丰算法搜索移动机器人导航中的路径， 该算法对评估函数进行加权处理，并引入“人工搜索标志”，避免重复搜索无效 区域，能有效快速地逃离障碍物陷阱，取得较好效果“。文献 1 0 是栅格图中路 径的搜索研究，并不适用于矢量图，文献 1 l 一1 3 是具体问题中的应用，其中的 改进方法可以参考，但对于具体应用还要做适当的改进和优化。 遗传算法全局搜索的能力很强，在解决最优( 次优) 问题方面有天然的优势， 但局部搜索能力较差。在1 2 3 小节中作者对遗传算法的研究历史和现状做了详 细的归纳，其中包括遗传算法在求解晟短路径问题中应用的相关文献归纳，这里 不作过多说明。 华东师范大学2 0 0 6 届硕_ 一学位论文w e b g i s 中基f 遗传算法的蜮矧路径求斛方法研究 模拟退火算法的依据是固体物质退火过程和组合优化问题之问的相似性。物 质在加热的时候，粒子间的布朗运动增强，到达一定强度后，固体物质转化为液 态，这个时候再进行退火，粒子热运动减弱，并逐渐趋于有序，最后达到稳定。 作者列了几个模拟退火算法原理及纯算法改进方面的典型文献，谢云综合介绍了 模拟退火算法的原理、实现形式、渐近收敛性、应用及其并行策略，对模拟退火 算法给出一个简明、全面、客观的综合评价”；李文勇，李泉永等人针对优化问 题中的多极值的现象，提出了基于有记忆模拟退火的全局优化算法，并针对不同 的设计变量，采用了不同的邻域产生方法，具有较高的计算精度和适应性。；杨若 黎，顾基发等人提出了一种确定模拟退火算法温度更新函数的启发式准则，构造 了适当的产生随机向量的概率密度函数，应用该启发式准则导出了相应的温度更 新函数，新的温度更新函数与退火时间的幂函数成反比，与优化问题的变量维数 无关，可以显著地提高求解全局优化问题的计算效率“。模拟退火方法在局部搜 索能力方面比较强，纯粹用模拟退火算法求解最短路径问题，目前还存在一些问 题，一般结合全局搜索能力比较强的算法比如遗传算法等来求解最短路径问题， 在求解方法方面还有待进一步研究。张波，叶家玮等人将模拟退火算法应用于路 径优化中，并将该算法与树型算法进行比较，说明该方法在求解最短路径中的优 点“；周长峰，谭跃进用模拟退火算法来求解运输最短路径，并将该方法与贪婪 算法作比较，说明了模拟退火算法的高效性“；田澎，王浣尘等人提出了循环排 序中六种不同的随即抽样方式，并在模拟退火算法求解旅行商问题( 最短路径问 题的一种) 中应用，对六种抽样方式进行理论分析证明，对比分析，给出结论”； 张德富，顾卫刚等人基于模拟退火思想，提出一种解旅行商问题的并行算法，并 在多处理机系统上实现，具有较高的优化程度和较快的运算速度“0 3 。 蚁群算法是一种受自然界生物的行为启发而产生的“自然”算法，它是从对 蚁群行为的研究中产生的，适合于解决组合优化问题。目前蚁群算法的研究和应 用也相当广泛，结合研究的问题，作者只介绍蚁群算法原理、算法改进及其在求 解最短路径相关的一些文献。温文波，杜维等人以求解最短路径问题为例介绍了 蚁群算法原理、发展及实现；丁海军，陈右健等人介绍了蚁群算法的基本原理 及其算法的基本模型，对几种改进的蚁群算法进行了评述，并对算法的研究现状 做了概述，认为蚁群算法是种较好的解决组合优化问题的新型模拟进化算法 ”“；何桂良，潘久辉等人针对蚁群基本算法的缺点，结合遗传算法和自适应思想 对其进行改进，并用实验证明改进效果良好”“；胡小兵，黄席樾等人将蚁群算法 应用于迷宫最优路径问题，针对迷宫最优路径问题的特点，作者进行了相关的定 义，实验结果显示该方法是有效的”；毕军，付梦印等人应用蚁群算法求解最短 路径问题，对算法的选择策略、局部搜索、信息量修改三方面进行改进，使算法 华东师范人学2 0 0 6 届硕士学位论文 w e b g i s 中基于遗传算法的最短路径求斛方法划究 不易陷入局部最优解，并且能较快地收敛到全局最优解“；文献 2 6 2 8 均介绍 了蚁群算法在物流路径搜索方面的应用。由于蚁群算法是一种较新的算法，仍有 很多方面需要研究。 l 。2 2w e b g i s 中最短路径分析 2 0 世纪9 0 年代，地理信息系统在研究、开发和市场化方而取得了很大的进 展。i n t e r n e t 也正是在此时普及和发展，网络地理信息系统( w e b g i s ) 应运而 生，标志着g i s 进入一个崭新的发展阶段。g i s 通过网络功能得以扩展，真正成 为一种大众使用的工具，拓展了g i s 的应用领域，i n t e r n e t 用户可以浏览w e b g i s 站点中的空间数据，放大、缩小、漫游，以及进行各种空间检索和空间分析，从 而使g i s 进入千家万户。 现在，w e b g i s 得到越来越广泛的应用。互联网上已经出现了许多w e b g i s 应 用实例。w e b g i s 技术可应用于农业、林业、水利、地矿、交通、通讯、新闻媒 体、城市建设、教育、资源、环境、人口、海洋以及军事等几十个领域。概括起 来，其应用方向分为两大类：一类为基于i n t e r n e t 的公共信息在线服务，为公 众提供交通、旅游、餐饮、娱乐、房地产等与空间信息有关的信息服务。国内外 站点上已经有了很多成功的应用，如g o o g l em a p s ( h t t p ：m a p s g o o g l e c o m ) 、 m a p q u e s t ( h t t p ：w w w m a p q u e s t c o m ) 、图行天下( h t t p ：w w 9 0 2 m a p c o m c n ) 、 m a d a b c ( h t t p ：w e b m a p a b c c o m ) 和上海徐汇区公共服务g i s 系统 ( h t t p ：p u b l i c g i s x h s h c n ：8 0 8 0 x h p g i s i n d e x j s p ) 。w e b g i s 的另外一类 应用为基于i n t r a n e t 的企业内部业务管理，如帮助企业进行设备管理、以及安 全监控管理等等。 w e b g i s 的目的不仅仅为了显示地图，更主要的是空间分析功能，提供决策 支持服务。空间分析是g i s 的核心，相对于其它空间分析功能，网络最短路径分 析的研究较少，但是近几年来由于普遍使用g i s 管理大型网状设施( 如城市管线、 交通线路、通讯线路等) ，使得对网络最短路径分析功能需求迅速增长，相对于 国际上网络分析的研究不断升温的状况，国内的几个较有影响的g i s 系统已开始 提供或多或少的网络最短路径分析功能，应该看到，国内的应用和需求也是相当 广泛和迫切的，这必将对网络分析的研究产生巨大的推动作用“。网络最短路径 分析地理信息系统空间分析的主要功能之一。最短路径分析的发展程度将大大影 响到w e b g i s 中空间分析的发展步伐。 l2 3 遗传算法 遗传算法是作者研究的重点，本小节将对遗传算法的研究历史和现状做详细 介绍。 华东师范大学2 0 0 6 届硕上学位论文 w e b g i s 中攮十遗传算法的最短路径求斛方浊驯究 i 2 3 1 国外研究概况 遗传算法研究的必起是在1 9 8 0 年代末和1 9 9 0 年代初期，但它的历史起源可 追溯到1 9 6 0 年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。 早期遗传算法的研究特点是侧重于对一些复杂的操作的研究。虽然其中相自动博 弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象，但总的来说，这 是一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具的开拓。这种 现象直到7 0 年代中期由于h o l l a n d 和d e j o n g 的创造性研究成果的发表才得到 改观。“。当然，早期的研究成果对于遗传算法的发展仍有一定的影响，尤其是 其中一些有代表性的技术和方法已为当前的遗传算法所吸收和发展。表卜1 列出 了从1 9 6 0 年代到1 9 8 0 年代这一时期中遗传算法研究的国外发展概况。我们对此 做简要说明。 在遗传算法作为搜索方法用于人工智能系统中之前，已有不少生物学家用计 算机来模拟自然遗传系统。尤其是f r a s e r 的模拟研究，他于1 9 6 2 年提出了和现 在的遗传算法十分相似的概念和思想。但是f r a s e r 和其他一些学者并未认识 到自然遗传算法可以转化为人工遗传算法。而h o l l a n d 教授及其学生不久就认识 到这一转化的重要性。“。h 0 1 l a n d 认为比起寻找这种或那种具体的求解问题的方 法来说，开拓一种能模拟自然选择遗传机制的带有一般性的理论和方法更有意 义。在这一时期，h o l l a n d 不但发现了基于适应度的人工遗传选择的基本作用， 而且还对群体操作等进行了认真的研究。1 9 6 5 年，他首次提出了人工遗传操作 的重要性，并把这些应用于自然系统和人工系统中。 表卜11 9 6 0 年代到1 9 8 0 年代遗传算法( g a ) ) 的研究概况 年代 研究者研究内容 生物学 1 9 6 7 r o s e n b e r g单细胞器官群体的进化模拟 1 9 7 0 w e i n b e r g包括元g a 的细胞群体仿真 1 9 8 4p e r r vg a 中小生境理论和种群的研究 1 9 8 5 g r o s s o带显形子群体和迁移的救倍体g a 研究 计算机科学 1 9 6 7 b a g l e y 采用g a 的穴子棋评估函数中的参数搜索 1 9 7 9 r a g h a v a n 和b i r c h a r d 基丁g a 的聚类算法 1 9 8 4 g o r d o n采用g a 的适应文本说明 1 9 8 5r e n d e l lg a 搜索博弈评估函数 1 9 8 7 r a g h a v a n 署a g a r w a l 利_ l ；| g a 的适应文本聚类 一i ：程和运筹学 1 9 8 2e t t e r 、h i c k s 平c h o 。 _ l = s g a 的递归适应滤波器设计 1 9 8 3 g o l d b e r g用g a 剥瓦斯管道的稳态和暂态优化 华东师范大学2 0 0 6 届坝士学位论文w e b g i s 中基十遗传算浊的避短路径求删方法川究 1 9 8 5 bd a v is 用g a 解决调度问题 1 9 8 6 g o l d b e r g 平口s a m t a n i采用g a 的结构优化 1 9 8 6 g o l d b e r g 平s m i 曲 s g a 求解盲背包问题 1 9 8 7d a v i s 弄口r 1 t t e r 采用规模退火捌元g a 结合的教室调度 遗传算法 1 9 6 2h 0 1 l a n d使j _ ；| 细胞状计算机群序的适削系统 1 9 6 8 h o l l a n d 模式理沦的开发 1 9 7 1h o l ls t i e n采用配对和选择规则的二维函数优化 1 9 7 2 b o s w o r t h ，f 0 0 和z e i g l e r 县张基因中采刚复杂变异的g a 操作 1 9 7 2f r a n t z能置的非线性和逆转的研究 1 9 7 3m a r t i n 类一g a 的概率算法的理论研究 1 9 7 5d ej o n g 在5 个函数试验中的s g a 基本参数研究 1 9 7 5h o l l a n da n a s 的出版 1 9 8 lb r i n d l e g a 中选抒和优势度( d o m i n a n c e ) 的研究 1 9 8 3w e t z e l g a 求解t s p 问题 1 9 8 4 m a u l d l n 几个对维持s g a 中群体多样性有启发的研究 i 9 8 5b a k e r d e j 。n g 试验中的排序选择过程的试验 1 9 8 5b o o k e r 对部分匹配记录、共享和配对限制的提议 1 9 8 5 g o l d b e r g 和l i n g l e对部分匹配交叉( p m x ) 平0 s c h e m a 分析的t s p 1 9 8 5s c h a f f e r 采用子群体的g a 方法来实现多日标优化 1 9 8 6 g o l 曲e r g 用边界模式内容的最大化米估计优化的群体人小 1 9 8 7b a k e r 减少选择过程中的统计误差 1 9 8 7 b r i d g e s 和g 。1 d b e r g 对于卜位g 中的再生和交叉的扩展分析 1 9 8 7 g 0 1 d b e r g 再生和交义操作下的虽小骗问题 1 9 8 7 g 0 1 d b e r g 弄r i c h a r d s o n 采h j 共早幽数的小生境和神群的研冗 1 9 8 7 g 0 1 d b e r g 年口s e g r e s t _ 日：；| 有限马尔可夫链分析再生和变异 1 9 8 7 0 1 i v e r ，s m i t h 着口h 0 1 l a n d 排列重组算子的模拟和分析 1 9 8 7s c h a f f e r 模式采样中选择过程效用的分析 1 9 8 7s c h a f f e r 年口m o r i s h i m a串编码适应交叉试验 1 9 8 7研1 i t l e yg a 选择中子代测试方法的应用 混合技术 1 9 8 5 b r a d y 用遗传算子求t s p 问题 1 9 8 5g r e f e n s t e t t ee ta 1 用考虑知识的遗传算子求t s p 问题 1 9 8 5 d o l a n 和d y e r 采用g a 来学习神经网络拓扑 1 9 8 7 l i e p i n s ，h i l l i a r d ，p a l m e r和组合问题中盲目搜索算于和贪婪搜索算子的比较 m o r r o w 1 9 8 7 s i r a g 和w e is s e r 州模拟退火控制求解t s p 问题的遗传算于频度 并行g a 实现 1 9 7 6b 宅t h k e可能的并行g a 实现的简要理沦研究 1 9 8 1g r e f e n s t e t t e若干并行g a 实现的简单理论研究 1 9 8 7 j o g 和v a ng u c h t 基于知识和并行的g a 的绸台 1 9 8 7 p e t t e y l e u z e 芹口g r e f e n s t e t t e采用d e j o n g 测试在i n t e l 硬什上实现井行g a 1 9 8 7s u h 弄nv a ng u c h t并行g a 搜索用丁t s p 耐的局部选择操作 6 华东师范大学2 0 0 6 届硕士学位论文 w e b g 】s 中拱于遗传算法的罐短路径求斛方法研究 1 9 6 7 年，b a g l e y 在他的论文中首次提出了遗传算法( g e n ( “ca l g o i t h m ) 这一术语，并讨论了遗传算法在自动博弈中的应用+ 3 ”。他所提出的选择、交叉和 变异的操作已与目前遗传算法中的相应操作十分接近。尤其是他对选择操作做了 十分有意义的研究。他认识到，在遗传进化过程中的前期和后期，选择概率应合 适地变动。为此，他引入了适应度定标( s c a l i n g ) 概念，这是目前遗传算法中 常用的技术。同时，他也首次提出了遗传算法自我调整概念，即把交叉和变异的 概率融于染色体本身的编码中，从而可实现算法自我调整优化。尽管b a 9 1 e y 没 有对此进行计算机模拟实验，但这些思想对于后来遗传算法的发展所起的作用是 十分明显的。 在同一时期，r o s e n b e r g 也对遗传算法进行了研究，他的研究依然是以模拟 生物进化为主，但他在遗传操作方面提出了不少独特的设想= “1 。1 9 7 0 年 c a v i c c h i o 把遗传算法应用于模式识别中”，他对于遗传操作以及遗传算法的自 我调整也做了不少有特色的研究。 w e i n b e r g 于1 9 7 1 年发表了题为活细胞的计算机模拟的论文“0 1 。由于他 和r o s e n b e r g 一样注意于生物遗传的模拟，所以他对遗传算法的贡献有时被忽 略。实际上，他提出的多层次或多级遗传算法至今仍给人以深刻的印象。 第一个把遗传算法用于函数优化的是h 0 1 l s t i e n “。1 9 7 1 年他在论文计算 机控制系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方 法。 1 9 7 5 年在遗传算法研究的历史上是十分重要的一年。这一年，h 0 1 l a n d 出版 了他的著名专著自然系统和人工系统的适配。该书系统地阐述了遗传算法 的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论 ( s c h e a t at h e o r y ) 。该理论首次确认了结构重组遗传操作对于获得稳并行性的 重要性。直到这时才知道遗传操作到底在做什么，为什么又做得那么出色，这对 于以后陆续开发出来的遗传操作具有不可估量的指导作用。 同年，d e j o n g 完成了他的重要论文遗传自适应系统的行为分析”。他 在该论文中所做的研究工作可看作是遗传算法发展进程中的一个里程碑，这是因 为他把h o l l a n d 的模式理论与他的计算实验结合起来。尽管d e j o n g 和 o l l s ti e n 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善 和系统化，同时又提出了诸如代沟( g e n e r a t i o ng a p ) 等新的遗传操作技术。可 以认为，d e j o n g 的研究工作作为遗传算法及其应用打下了颦实的基础，他所得 出的许多结论迄今仍具有普遍的指导意义。 进入1 9 8 0 年代，遗传算法迎来了兴盛发展时期，无论是理沦研究还是应用 研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它 华东师范火学2 0 0 6 届砸卜学位论文w c b g i s 中皋于迪传算诎的最短路径求俐方法研， 的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同 时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中办 得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。表卜2 给出了目f 诲 遗传算法所涉及的主要领域。 表卜2 遗传算法的主要应用领域 应用领域 说明 控制瓦斯管道控制，防避导弹控制，机器人控制 规划生产规划，并行机任务分配 设计v l s i 布局，通信网络设计，喷气发动机设计 组合优化t s p 问题，背包问题，图划分问题 图像处理模式识别，特征抽取 信号处理滤波器设计 机器人路径规划 人工生命生命的遗传进化 从表卜2 可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多 更新更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向： 1 ) 基于遗传算法的机器人学习( g e n e t i cb a s em a c h i n el e a r n i n g ) 。“，这 一新的研究课题把遗传算法从历来离散的搜索空间的优化算法扩展到具 有独特的规则生成功能的崭新的机器学习算法。 2 ) 遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方 法相互渗透和结合”2 1 ”1 。 3 ) 并行处理的遗传算法的研究十分活跃“。这一研究不仅对遗传算法本身 的发展，而且对新一代智能计算机体系结构的研究都是十分重要的。 4 ) 遗传算法和另一个称为人工生命的崭新研究领域砸刁i 断渗透。所谓人工 生命，即是用计算机模拟自然界丰富多菜的生命现象，其中生物的自适 应性、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这 方面将会发挥一定作用。 5 ) 遗传算法和进化规则( e v o u t i o np r o g r a m m i n g ，e p ) 以及进化策略 ( e v 0 1 u t i o ns t r a t e g y ，e s ) 等进化计算理论r 益结合”。e p 和e s 几乎 是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自 然界生物进化机制的智能计算方法，既同遗传算法具有相同之处，也有 各自的特点，具体可查相关文献。 随着遗传算法研究的不断深入和发展，一系列以遗传算法为主题的国际会议 十分活跃。从1 9 8 5 年开始，困际遗传算法会议，即】c g a ( n t e r n a t i o n a l c o n f e r e n c eo ng e n e t i ca l g o r i t h m ) 每两年举行一次。在欧洲，从1 9 9 0 年丌始 华东师范大学2 0 0 6 扁硕 一学位论文 w e b g i s 中魑于迷他算法的最娥路径求解方法训究 也每隔一年举办一次类似的会议，即p p s n ( p a r a l l e lp r o b l e ms 0 1 v i n gf r o m n a t u r e ) 会议。除了遗传算法外，大部分有关e s 和e p 的学术会议有 f o g a ( f o u n d a t i o no fg e n e t i ca l g o r n h m ) 。它也是从1 9 9 0 年开始，隔年召丌 一次。这些国际学术会议论文集中反映了遗传算法近些年来的最新发展和动向。 综上所述，作为一种搜索算法，遗传算法的基本框架已经形成，在各种问题 的求解和应用中展现了它的特点和魅力，同时也暴露了在理论和应用技术上的许 多不足和缺陷。客观的说，遗传算法尽管有各种新策略和新提案不断被提出，但 他们几乎都是针对特定问题求解而言的，对他们的评估也都是基于对比。实验，其 中缺乏深刻而且具有普遍意义的理论分析。 1 2 3 2 国内研究概况 遗传算法( g a ) 模拟生物进化过程中物竞天择的自然法则，逐步趋向最优个 体，因此g a 很适合解决组合优化问题。最短路径问题属于求解最优问题，它很 好地符合了遗传算法的思想。据报道，遗传算法对4 3 1 个城市的t s p 问题的求解， 对6 6 6 个城市已可得到准优解。尽管遗传算法比其它传统搜索算法有更强的鲁棒 性，但它更擅长全局搜索而局部搜索能力却不足。研究发现，遗传算法可以用极 快的速度达到最优解的9 0 左右，但要达到真正的最优解则要花费很氏的时问 ”“。探明如何能充分发挥遗传算法优越性的问题性质和类型是十分有意义的工 作。已有一些学者着手研究遗传算法求解最短路径问题