（计算机科学与技术专业论文）基于遗传算法的多目标空间优化选址.pdf

t h em u l t i - o b j e c t i v es p a t i a lo p t i m a ll o c a t i o nb a s e do ng e n e t i c a l g o r i t hm at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：h o uj i n l i a n g s u p e r v i s o r ：a s s o c i a t e p r o f l i uy u j i e a s s o c i a t ep r o f w a n gh a i q i c o l l e g eo fc o m p u t e r & c o m m u n i c a t i o ne n g i n e e r i n g c h i n au n i v e r s i t yo fp e t r o l e u m ( e a s tc h i n a ) 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 日期：山，f 年j - 月夕妒e t 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：勉苗 指导教师签名：查p l 日期：如，年_ 1 - 月j 踊 日期：d k 年j 一月孑日 摘要 空间优化选址是g i s 空间决策分析的重要问题之一，指的是在一定地理区域内为一 个或多个空间对象选定合适的位置，使某一指标或综合指标达到最优的过程。此问题常 常涉及高维地理空间、海量数据、多个互相冲突的目标和限制条件，是n p h a r d 组合优 化问题。传统的优化方法，如穷举法、盲目搜索法等难以取得很好的效果。本文提出了 将空间结构知识和关联模式融合到多目标遗传算法，结合g i s 强大的空间数据处理、空 间查询、空间分析和可视化等技术进行空间优化决策。 首先，从影响空间优化选址的定性因素和定量因素两方面着手，分别进行不确定的 定性因素分析、量化及建模和确定性的定量因素分析及建模，利用粗集的知识将定性因 素定量化的表达为一个综合效用因子并引入到定量因素的数学模型中，进行空间优化选 址的影响因素建模。 其次，在对多目标遗传算法的原理、内部机制的分析基础上，建立融合空间结构知 识和关联模式的n s g a i i 、s p g a 2 和p e s a i i 三种多目标空间优化选址模型。同时，将 g i s 与应用模型紧密无缝集成，并构建不同的评价体系评价不同模型的性能。 最后，设计和开发基于a r c g i se n g in e 9 3 + c 撑n e t 的g i s 桌面应用系统，并进行大 型不规则区域的北京市医院空间优化选址应用实践。实验结果证明，空间结构知识和关 联模式对空间优化选址有较大的影响，本文所建模型在保持稳定性、鲁棒性的基础上， 生成的p a r e t o 最优集的收敛性更好、搜索到的最优位置的分布范围更广，三种模型的性 能较单纯多目标算法模型均有不同程度的提高。 关键词：g i s ；空间优化选址；遗传算法；多目标优化；空间结构知识和关联模式 t h em u l t i - o b j e c t i v es p a t i a lo p t i m a ll o c a t i o nb a s e do ng e n e t i c a l g o r i t h m h o uj i n l i a n g ( c o m p u t e rs c i e n c e & t e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o f l i uy u j i e & a s s o c i a t ep r o f w a n gh a i q i a b s t r a c t s p a t i a lo p t i m a ll o c a t i o ni so n eo f t h ec l a s s i cp r o b l e m si nt h er e a l mo fg i s i ts e l e c t e dt h e m o s ta p p r o p r i a t el o c a t i o nf o rs i t eo rs i t e si nac e r t a i ng e o g r a p h i ca r e aa n dm a d ep e r f o r m a n c e o rac o m b i n a t i o no fp e r f o r m a n c e st or e a c ho p t i m u m t h i sp r o b l e mu s u a l l yi n v o l v e s h i g h d i m e n s i o n a lg e o g r a p h i c a ls p a c e ，m a s s i v ed a t a , m u l t i p l ec o n f l i c t i n g o b j e c t i v e sa n d c o n s t r a i n t sa n dt h ei s s u ei san p h a r dc 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 t h u s ，t r a d i t i o n a l m e t h o d ss u c ha sb r u t e f o r c e ，b l i n d n e s ss e a r c ha n de t c a r ei n f e a s i b l et of i n dt h eo p t i m a l s o l u t i o n t h i sp a p e rd e m o n s t r a t e st h em e t h o di n t e g r a t i o no ft h ek n o w l e d g eo fs p a t i a ls t r u c t u r e a n da s s o c i a t i o np a t t e r n si n t om u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mt oe x e c u t i v es p a t i a lo p t i m a l d e c i s i o nb a s e do ng i s sp o w e r f u ls p a t i a ld a t ap r o c e s s i n g ，s p a t i a lq u e r y , s p a t i a la n a l y s i sa n d v i s u a l i z a t i o na n ds oo nt e c h n o l o g y f i r s t l y ，t h ep a p e rt a k i n gt w ob a s i ca s p e c t s - - q u a l i t a t i v ea n dq u a n t i t a t i v e f a c t o r st h a t a f f e c tt h ep r o c e s so fs i t el o c a t i o ni n t oa c c o u n t a n a l y s i s ，q u a n t i f i c a t i o na n dm o d e l i n go f u n c e r t a i n t yq u a l i t a t i v ef a c t o r s ，a n dd e t e r m i n i s t i cq u a n t i t a t i v ef a c t o r sa n a l y s i sa n dm o d e l i n g r e s p e c t i v e l y , t h e nq u a n t i f i e dq u a l i t a t i v ef a c t o r sw i t hac o m p r e h e n s i v eu t i l i t yf a c t o ru s i n g r o u g h s e t s p r o c e s s i n gm e t h o da n d i n t r o d u c e dt h e c o m p r e h e n s i v eu t i l i t y f a c t o ri n t o m a t h e m a t i c a lm o d e lo fq u a n t i t a t i v ef a c t o r ss oa st or e a l i z et h em o d e l i n gp r o c e s s s e c o n d l y , b a s e do nt h ea n a l y s i so fp r i n c i p l ea n di n t e m a lp r o c e s s e so fm u l t i o b j e c t i v e g e n e t i ca l g o r i t h m ，w ee s t a b l i s h e d t h et h r e em o d e l sa b o u tm u l t i o b j e c t i v es p a t i a lo p t i m a l l o c a t i o n ，t h a ti st os a yn s g a - i i ，s p g a 2a n dp e s a - i it h a ti n t e g r a t i o no ft h ek n o w l e d g eo f s p a t i a ls t r u c t u r ea n da s s o c i a t i o np a t t e m s m e a n w h i l e ，w er e a c h e dt h ec o m p a c t e ds e a m l e s s i n t e g r a t i o no fg i sa n da p p l i c a t i o nm o d e l f i n a l l y , d e s i g na n dd e v e l o p m e n tg i sd e s k t o pa p p l i c a t i o ns y s t e mb a s e d o na r c g i s e n g i n e 9 3 + c # n e ta n dc o n d u c tt h ee x p e r i m e n t sa b o u ts p a t i a lo p t i m a ll o c a t i o no fb e i ji n g h o s p i t a l si nl a r g ei r r e g u l a ra r e a e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ek n o w l e d g eo fs p a t i a l s t r u c t u r ea n da s s o c i a t i o np a t t e r n sh a sg r e a ti n f l u e n c eo ns p a t i a lo p t i m a ll o c a t i o n ，m o d e l s 目录 第一章绪论1 1 1 选题背景、依据和意义1 1 2 国内外研究现状2 1 2 1 空间优化选址的研究进展2 1 2 2 遗传算法在空间优化选址中的应用3 1 3 研究的内容、方法和关键问题4 1 3 1 研究内容4 1 3 2 研究方法5 1 4 论文组织结构5 第二章遗传算法与多目标优化7 2 1 多目标优化7 2 1 1 多目标优化问题的基本概念7 2 1 2 传统的多目标优化方法8 2 1 3 传统多目标优化方法的局限性9 2 2 遗传算法概述9 2 2 1 遗传算法发展9 2 2 2 遗传算法基本原理与一般流程9 2 2 3 遗传算法存在的问题1 0 2 3 遗传算法进行多目标决策制定的框架1 l 2 4 遗传算法用于多目标优化的分类1 3 2 4 1 基于非p a r e t o 最优概念的多目标优化1 4 2 4 2 基于p a r e t o 最优概念的多目标优化1 5 2 5 本章小结1 8 第三章空间优化选址理论与方法1 9 3 1 空间优化选址的相关理论1 9 3 1 1 空间优化选址的原则1 9 3 1 2 空间优化选址的一般规律和步骤1 9 3 2 空间优化选址的三类经典模型2 0 3 3 空间优化选址的常见算法2 2 3 3 1 数学优化方法2 2 3 3 2 智能启发式优化方法2 3 3 4 本章小结2 5 第四章基于遗传算法的多目标空间优化选址模型2 6 4 1 研究区分析和g i s 空间数据处理2 6 4 1 1g i s 数据采集2 6 4 1 2g i s 数据空间处理2 7 4 2 空间优化选址影响因素的表达2 7 4 2 1 确定空间优化选址影响因素2 7 4 2 2 空间优化选址影响因素建模2 8 4 3g i s 空间分析与空间知识表达3 1 4 3 1 空间对象的结构知识表达3 1 4 3 26 i s 空间分析3 2 4 3 3 空间相关性的度量3 2 4 4 多目标遗传算法进行空间决策3 4 4 4 1 融合空间结构知识和关联模式的n s g a i i 模型3 4 4 4 2 融合空间结构知识和关联模式的s p g a 2 模型3 6 4 4 3 融合空间结构知识和关联模式的p e s a i i 模型3 7 4 5 模型评价标准3 9 4 6 本章小结4 0 第五章基于遗传算法的多目标空间优化选址系统的设计与实现4 2 5 1 系统的总体构架4 2 5 2 系统设计的目标与原则4 2 5 3 系统总体设计4 3 5 4 系统详细设计和实现4 3 5 4 1 框架的建立4 3 5 4 2 地图基本管理模块4 4 5 4 3 空间数据库管理系统模块4 6 5 4 4g i s 空间查询与空间分析模块4 7 5 4 5 空间优化选址决策模块5 l 5 4 6 地图输出和可视化6 0 5 5 数据库设计6 2 5 6 系统的运行环境6 3 5 7 本章小结6 3 第六章应用实例北京市医院空间优化选址6 4 6 1 研究区分析和g i s 数据预处理6 4 6 1 1 研究区分析和g i s 数据收集6 4 6 1 2g i s 空间数据处理6 4 6 2 染色体的编码方案6 7 6 3 选址过程参数设置6 7 6 4 结果评价与性能分析6 8 6 4 1 实验结果6 8 6 4 2 结果分析7 6 6 5 本章小结7 7 结论与展望7 9 参考文献8 1 攻读硕士学位期间取得的学术成果8 6 致谢8 7 中国石油大学( 华东) 硕士学位论文 1 1 选题背景、依据和意义 第一章绪论 空间优化决策作为g i s 领域的关键问题，随着社会、经济、科学技术的飞速发展变 得日益重要。各种空间优化决策问题，如资源分配、优化选址、土地利用优化布局等， 逐渐成为了国家战略规划、国防建设和国民经济等各个领域随处可见的问题。 空间优化选址作为空间优化决策的重要问题之一，大到国家战略合作伙伴、军事基 地，d , n 学校、医院、消防站、商场等基础设施位置的选择等都属于空间优化选址的范 畴。优化选址决策结果的好坏也直接影响到选址对象的服务质量、服务效率和服务成本 等各方面，好的选址结果会给生产、生活带来便利，而不好的选址结果往往会带来不便、 损失甚至灾难。因此，优化选址问题的研究有着重大的经济、社会和军事意义。 由于选址对象的范围非常广泛，影响空间选址的各种因素也错综复杂，涉及到自然、 人文、社会、经济等不同类型的因素。对于不同的选址对象来说，选址因素的作用也是 有差异的和不固定的，如：对于地区选择和地点选择两个不同尺度的选址问题来说，前 者更注重宏观因素，后者还需考虑微观因素。就现实的具体优化选址问题而言，一般并 未明确设施的位置，也未定义候选点的数量，是不确定性的问题。要确定选址对象的空 间最优位置，常常涉及高维地理空间、海量数据、多个互相冲突的目标和多个限制条件， 使空间优化选址问题成为典型的n p h a r d 组合优化难题，已有的传统优化选址方法均暴 露出了一定的局限性。 随着空间技术和信息处理技术的发展，g i s 作为数字化获取、收集、存储、处理、 管理和应用空间信息的技术体系，为空间优化选址决策提供了崭新的方式。在g i s 数据 使用以前，传统的空间优化选址手段就是根据相关规划、标准、规范进行设计，它只能 提供所需设施的数量和规模，不能确定各个设施的具体位置，并没有将对象的空间位置 和属性数据紧密结合，决策过程中掺杂的主观因素较多，决策质量难以保证，一般只能 解决小数据量的优化选址问题。当g i s 空间数据引入到优化决策模型之后，利用g i s 采集、处理、存储和组织数据，辅以g i s 的空间分析、地图显示等功能，可以灵活、有 效、直观的处理选址过程中涉及的各种空间数据和非空间数据。针对实际空间优化选址 问题往往并不存在使多个目标同时达到最优解的特点，从选址问题本身着手，将多目标 空间优化选址模型与g i s 合理有效地融合显得尤为重要。 第一章绪论 过去的4 0 年，g i s 的发展虽然很快，但其主要应用还集中在空间数据库的建立、 空间查询、空间分析和成果的输出方面，g i s 在启发式自动搜索和知识处理推理方面的 能力还不足，无法提供足够的决策来解决复杂的空间n p 组合优化问题。近年来人工智 能领域的各种智能启发式算法因自适应搜索能力而越来越引起重视，使g i s 与各种智能 算法结合建立智能g i s 成为解决一些空间复杂问题的重要途径。 以遗传算法( g e n e t i ca l g o r i t h m ，g a ) 为典型代表的智能启发式优化方法因其内在 的并行机制及全局优化的特性而更适合于空间优化领域。g a 在解决复杂的非线性组合 优化问题时，不需要建立复杂的数学表达式，便可在高维的搜索空间中找到全局最优或 接近全局最优的解，具有高度的灵活性，一般的方法很难做到这一点。 将g i s 强大的空间分析、图形显示功能与进化算法结合后解决空间优化选址问题， 可使优化选址的要素和现实中的实际问题有了联系，以量化的方式处理选址问题，减少 了人为因素的干扰，大大提高了选址的科学性、准确性与直观性，达到更好的效果。 1 2 国内外研究现状 1 2 1 空间优化选址的研究进展 对于空间优化选址问题，目前大致有两类优化方法：一是数值优化方法，二是智能 优化方法。常见的数值优化方法包括：s i m p l e x 、g a u s s - n e w t o n 和l e v e n b e r g - m a r q u a r d t 等，这些传统的搜索方法由于经常会陷于局部最小或最大且初始值的选择对最终结果影 响很大，因此在实际应用中存在一定的局限性。常见的智能优化方法主要有：模拟退火 算法( s i m u l a t e da n n e a l i n g ，s a ) 、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、微粒群优化算 法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 、蚁群智能算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 、 禁忌算法( t a b us e a r c h ，t s ) 等【l 】 【l o l ，这些方法具有适于高度并行、自组织、自学习 与自适应的特征，与传统的数值优化方法比较，智能优化算法更适合求解多目标优化问 题。 其实寻找最优位置的最直接方法是穷举法( b r u t e f o r c e ) ，但是其需要对所有可能 的组合方案进行评价，黎夏等【5 1 1 6 1 指出在i o o x1 0 0 单元空间中选取2 0 个最佳位置就会 涉及到4 0 3 1 0 6 1 种组合，其计算量之大可想而知，因此穷举法在实际中并不可行。 当需要配置的资源位置预先就是确定的且数目较小，多准则分析( m u l t i c r i t e r i a a n a l y s i s ，m c a ) 不失为一种有效的空间优化搜索方法，但m c a 不适合大数据量的搜 索，并且具有较强的主观性。 2 中国石油大学( 华东) 硕士学位论文 线性整数规划( l i n e a ri n t e g e rp r o g r a m m i n g ，l i p ) 也可用于空间优化寻址，但此方 法属于穷尽搜索，速度较慢，处理的数据量也有限，并且是线性方法，不能很好地处理 复杂的非线性的地理问题。 目前，关于空间选址问题的研究日渐增多，现有研究方法和理论相对成熟，但技术 手段较为落后，还没有统一的框架或方法完美地解决某一类型空间优化选址问题，一些 新技术、新手段在空间优化选址问题中的应用还比较缺乏。 1 2 2 遗传算法在空间优化选址中的应用 g a 来源于对生物进化过程的模拟，它将问题的求解表示成染色体的适者生存过程， 通过染色体的一代代进化，最终收敛到最适合环境的个体( 问题的最优解) 。现阶段， g a 用于解决空间优化选址问题时，大多采取的是将多目标问题组合为单一目标函数的 方式。典型的应用有： b r o o k e s 【1 1 1 利用g a 来解决空间几何形态的优化问题。j a r a m i l l 等利用g a 解决简 单网络上若干节点的优化选址问题。s t e w a r t 等【13 】用遗传算法来解决经典的空间规划问 题。黎夏等1 5 1 1 6 1 结合g i s 和遗传算法进行了医院优化选址问题的研究。d u c h e y n e 等【1 4 】 以森林管理为例结合g i s 和多目标遗传算法进行了空间决策支持方面的研究。p a r k 等【l 习 结合遗传算法和g i s 设计了大规模水系的水质监测网络。b a b a i e k a f a k i l l 6 j 等用遗传算法 解决公共汽车终点选址问题。z h a n gl i x u n 等【 1 提出了在竞争环境下用遗传算法解决服 务点选址的多点定位分配模型。a n ap a u l ai a n n o n i 等【l8 】研究了高速公路上急救站的选址 优化问题，此问题需要同时考虑救护车的最优位置和响应区域，从而最小化平均响应时 间。类似的研究非常多，这种将多目标转化为单目标的方式虽然较简单，但由于对选址 过程中遇到的多个影响因素考虑不足，从而容易漏掉那些实现了多目标最优而单目标不 是最优的方案，因此，转化为单目标的方式并不能体现出优化选址的多目标性。 基于p a r e t o 最优概念的遗传算法克服了将多目标问题转化为单目标问题的不足，成 为解决多目标问题的有效途径。例如，x i a o 等1 9 】【2 0 1 利用遗传算法来解决多目标站点选 择问题，提出了解决多目标空间决策问题的迭代方法。陈南祥等【2 l 】将适应度赋值多目标 遗传算法( m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ，m o g a ) 用于解决水资源优化配置问题。包 伟1 2 2 等将改进的非劣排序遗传算法( a d v a n c e dn o n - d o m i n a t e ds o r t i n gg e n e t i c a l g o r i t h m ，n s g a i i ) 应用到了火电厂优化选址模型。阎志伟【2 3 j 等将n s g a i i 与多目标 的区域覆盖星座优化问题结合起来。丁胜祥【2 4 j 等将强度p a r e t e 遗传算法( s t r e n g t h 第一章绪论 p a r e t og e n e t i ca l g o r i t h m ，s p g a ) 用于解决供水库群的多目标优化调度问题。涂启玉【2 5 1 将小生境遗传算法( n i c h e dp a r e t og e n e t i ca l g o r i t h m ，n p g a ) 用于区域水资源优化 配置等等。 目前关于p a r e t o 最优的多目标遗传算法取得了不小的研究进展，并成功地解决了大 量的函数优化、调度优化和控制系统优化等问题，但由于多目标遗传算法的内部运行机 制比较复杂，具有“黑箱或“灰箱特性，国内外对多目标遗传算法的研究仍然还没 有形成一套完善的理论体系，不能够用理论来证明算法的有效性，仅仅是停留在比较试 验结果上，在实践领域中多目标遗传算法还没有得到非常广泛的应用。在g i s 空间优化 选址方面，研究范围还比较小、发展不平衡、体系不完善，理论创新不足，尤其是基于 p a r e t o 遗传算法的g i s 空间多目标优化选址更是很少涉及到。 1 3 研究的内容、方法和关键问题 1 3 1 研究内容 本论文是以北京市医院的空间优化选址为研究对象、g i s 为可视化分析平台、多目 标遗传算法为应用分析模型的综合空间优化选址方法。在考虑空间结构知识和关联模式 的情况下，确定影响空间对象最优位置的因素并建立合适的数学表达式作为多个目标函 数，再利用基于p a r e t o 最优的多目标遗传算法搜索全局“最优”的解，也就是空间对象 的最优选址位置。 本文的主要研究内容包括： 1g i s 与智能优化算法模型的无缝紧密集成 通过公共对象模型( c o m ) 建立g i s 与智能算法应用模型之间的快速通信。c o m 技 术能避免频繁的文件数据转换，也避免外部直接访问g i s 数据结构的安全代价，可以通 过任何符合工业标准的开发语言进行集成。 2 融合空间结构和关联知识的多目标遗传优化模型 遗传算法用于常规的数据优化时，通常假设数据具有独立同分布性，在对g i s 空间 数据优化时，这个特点不再适用。本部分对n s g a i i 、s p g a 2 和改进的包络盒选择算法 ( r e g i o n - b a s e ds e l e c t i o ni ne v o l u t i o n a r ym u l t i - o b j e c t i v eo p t i m i z a t i o n ，p e s a - i i ) 三种最 近流行的p a r e t o 遗传优化模型内部结构和算法进行研究，通过在模型的内部融合位置、 形状等空间结构知识和距离、方位、拓扑等空间关联模式，从而提高全局优化的精度和 准确性。 4 中国石油大学( 华东) 硕士学位论文 3 确定影响优化选址的因素并建立数学表达式 空间优化选址影响因素可分为两类：定性因素和定量因素，需分别建模。采用粗集 的方法为不确定的定性因素建模，并将定向因素表达为综合效用评价值，再引入到定量 因素模型中。 4 空间信息表达方法和模型评价指标体系的研究 空间结构知识和关联模式的表达包括：一是空间对象本身结构知识的表达，如位置、 形状、大小等的定量表示，二是其它对象对该空间对象影响的表达，即空间对象之间的 相对位置、距离关系、方位关系和拓扑关系等的表达。另外，针对提出的融合空间结构 知识和关联模式的不同遗传优化新模型，评价性能优劣。 1 3 2 研究方法 1g i s 用来对相关的各种地理空间和非空间数据和其它相关选址材料准备、收集、 整理、存储、分析，为多目标智能优化决策模型的提供输入输出支持； 2 根据实际问题的具体要求，建立符合条件的多目标智能优化算法模型； 3 实现g i s 与多目标智能优化算法模型的紧密式集成； 4 评估相关结果，根据结果调整模型的参数，再进行决策。 1 4 论文组织结构 本文首先归纳和总结了多目标优化问题的数学定义、常规的解决方法及其存在的缺 陷，简单介绍了遗传算法的基本原理和应用遗传算法解决多目标问题的原因。其次，阐 述了空间优化选址的原则、选址规律以及经典选址模型和常见算法，在此基础上提出了 本文的基本思想和技术路线。最后，将研究成果应用于北京市医院的空间优化选址，验 证了基于遗传算法的多目标表空间优化选址方法的可行性。本文共分为六章，其中： 第一章绪论部分，主要介绍了本论文的提出背景和研究意义、国内外关于空间优 化选址和遗传算法用于空间优化选址的研究进展情况以及存在的不足之处、论文的研究 内容和要解决的关键问题。 第二章论文的理论基础部分，包括多目标优化问题的数学定义、遗传算法概述、 遗传算法进行多目标决策时的框架和遗传算法用于解决多目标问题时的主要方法。 第三章总结选址问题的理论基础，归纳空间优化选址的原则和规律以及经典的优 化选址模型，讨论了不同类型的优化选址适用的模型和常见的空间优化选址算法。 第一章绪论 第四章是论文的核心部分。根据前两章的相关理论基础，提出了基于遗传算法的 多目标空间优化选址模型。首先是方法的技术路线，涉及g i s 数据的选择、g i s 和智能 算法模型的集成方式、结果的可视化表达方式等。其次是空间选址影响因素的确定和定 量化表达方式。再次是三种不同的融合空间结构知识和关联模式的多目标遗传算法模型 的建立过程。最后介绍了模型的评价方式。 第五章主要介绍了基于遗传算法的多目标空间优化选址系统的设计与开发过程。 首先，确定系统的整体构架和系统设计的目标与原则。其次，在系统的总体设计的基础 上，建立适合本文研究对象的数据库。最后，详细设计各主要模块与g i s 主界面，并利 中国石油大学( 华东) 硕士学位论文 2 1 多目标优化 第二章遗传算法与多目标优化 多目标优化问题( m u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 起源于实际复杂系 统的设计、规划和建模过程中。无论是科学研究还是工程实践，碰到的许多优化问题都 是多目标优化问题。多目标优化问题的特点是各目标通过决策变量和约束条件互相制 约，对其中一个目标的改善必须以牺牲其它目标为代价，且由于各目标的评价单位又往 往不一致，因此很难找到唯一的一个解，使多个目标同时达到最优。多目标优化就是在 各目标之间进行协调权衡和折中处理，使所有目标尽可能达到最优或接近“最优 的解， 即p a r e t o 最优解。 2 1 1 多目标优化问题的基本概念 数学上，通常将m o p1 2 6 】【2 7 】定义如下： m i n m i z ey = ( 曲= ( ；( x ) ，厶( x ) ，以( x ) ) ( 2 - 1 ) s t g ( x ) = ( g l ( x ) ，9 2 ( x ) ，g 。( x ) ) 0 式中x = ( x l ，x 2 ，x n ) x ，少= ( y l ，y 2 ，少疗) y ，x 是决策向量，y 是目标向 量，x 是决策向量空间，】，是目标向量空间。约束条件g ( x ) 确定决策向量的可行取值范 围，f i ( x ) ( i = 1 , 2 ，疗) 为决策空间上的连续函数。 定义l 假设x 。，x ，为多目标优化问题的两个可行解，甜= ( 屯) = ( z ，。，“：，u 。) ， 1 ，= f ( x ，) = ( 1 ，。，2 ，1 ，。) ，如果u 部分小于，即对任意的f ( 1 , 2 ，门) ：k 并且存在 f ( 1 , 2 ，行) ：“， 一只 叩 一 = m 第三章空间优化选址理论与方法 鼽矿墨微构鬻服艄= 墨糯求篙p 盖 其它变量和前面的含义相同。 3 中心模型 中心模型就是指选定p 个设施的位置，使最坏的情况最优，如使最大反应时间最小、 使需求点与最近设施的最大距离最小或使最大损失最小等等，也叫极小化极大问题，最 早仍是由h a k i m i 提出。模型可描述为： m i n m a x ( d f ) ( 3 4 ) “嘞= 1 v i ， y = 尸 x i j y j 0 v i i 如j j 鼽乃= 忙粉施鬻服触_ ，= 仁糯枇警撒服务 3 3 空间优化选址的常见算法 3 3 1 数学优化方法 1 线性规划方法( 1 i n e a rp r o g r a m m i n g ，l p ) 将实际问题首先进行建模，从而将问题转化成一个线性目标函数和一系列的线性约 束方程，然后求线性目标函数在这些约束条件下的最值，适用于从网络中的多个备选点 中选出若干个选址点，使总成本最小。但由于实际问题的复杂多变性和不确定性等，不 易建立适当的线性模型，使得此方法并不能很好的解决现实问题。 2 盲目穷举方法( b r u t e f o r c e l 此方法通过把问题所有可能的解决方案逐- - n 举出来进行试验，找出符合条件的解 决方案的方法，其实质是用时间上的牺牲换来了解决方案的全面性保证。但实际问题往 往不可能列举出所有的可行方案，故此方法也有很大的局限性。 3 层次分析法( a n a l y t i ch i e r a r c h yp r o c e s s ，a h p ) 中国石油大学( 华东) 硕士学位论文 a h p 删洲是s a a t y 教授在2 0 世纪7 0 年代提出的一种多目标层次权重决策评价方法。 该方法综合考虑定量决策和定性决策，将决策过程层次化、数量化，常用来解决不能完 全依靠定量分析的问题。 a h p 首先将问题层次化，根据问题的性质、目标，将问题分解成不同的组成因素， 然后将组成因素根据相互关系进行不同层次的聚集组合，形成一个多层分析结构模型。 a h p 把要解决的问题归结为最低层的方案、措施、准则相对于最高层目标的相对重 要程度的权值问题，该方法的过程如图3 1 所示。 图3 - 1 层次分析法 f i g3 - 1a n a l y t i ch i e r a r c h yp r o c e s s 4 重心法 单个设施的最优位置选择时，常用重心法。其将某一范围内分布的用户点看作物体 系统，用户量和设施量看作物体的重量，则成本是用户量和设施量的函数，设施的最优 位置就是成本最低的重心点。 5 加权评分法因素分析法 当空间优化选址的因素难以精确的量化时，常选择加权评分法因素分析法。该方法 就是选定几个因素并根据专家评估或经验给出权重，对备选点求总分，得到某一方案的 评分，以得分最多的方案作为最佳选择，离散型设施选址时采用这种方法比较多。 3 3 2 智能启发式优化方法 l “炸弹法”优化模型 o p e n s h o w 和s t e a d m a n 在1 9 8 2 年提出的基于人口数据原子弹爆炸的落点优化问题。 最优选点问题就是要通过寻找最佳的炸弹落点位置，以同样数目的炸弹，产生最大的杀 2 3 第三章空间优化选址理论与方法 伤力。这可以看成是空间建模问题或是特殊的位置分配( 1 0 c a t i o n a l l o c a t i o n ) i h - j 题。其算法 为： 步骤1 ：定义炸弹杀伤力随距离衰减的规则( 函数) ； 步骤2 ：以公里网格为单元，寻找能产生最大死亡人口的每一个落点，确定第一个 炸弹的位置； 步骤3 ：移除死亡人口，获得新的人口分布； 步骤4 ：重复步骤2 和3 ，直至找到n 个炸弹的最佳落点。 这种炸弹杀伤力随距离衰减的规则是以每个落点位置分别以不同的半径和相应的死 亡率计算同心圆内的人口数。“炸弹法 简单易行，但其缺点是解决较为复杂条件下的 优化选址问题时易陷于局部最优值。在这种情况下，可以对所有的组合方案进行评价比 较，即采用b r u t e f o r c e 方法是最直接的方法，但是很多情况下其计算量巨大，实际操作 中并不可行。 2 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) s a 是一种通用概率算法，其基本思想源于金属退火过程。它将目标函数看作能量函 数，在求解过程中，以某种概率接受状态的转移。该算法在求解过程中，不但接受对目 标函数( 能量函数) 有改进的状态，还按某种概率接受变坏的状态，尽量避免过早收敛到 某个局部极值点，进行比较有效的全局搜索。该算法的缺点是要求温度下降的足够慢， 采用何种使温度下降的迭代公式还不太成熟，计算的结果还不稳定。 3 遗传算法 g a 在任何最优求解过程中，需优化的参数都将表示成由0 和1 组成的有限序列表 示的基因。若问题有多个参数，可以由多个相应的基因组成染色体，即一个解决方案。 然后开始进化过程，对群体迭代地进行遗传操作。最后，需要根据目标的适应度函数进 行性能评价。 4 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) p s o 是k e n n e d y 和e b e r h a r t 受人工生命研究结果的启发、通过模拟鸟群觅食过程中 的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。其与遗传算法一样， 也基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。 p s o 和g a 不同之处是其无需对个体进行交叉、变异、选择等遗传算子操作，而是将群 体中的个体看作是在搜索空间中没有质量和体积的微粒，每个微粒以一定的速度在解空 中国石油大学( 华东) 硕士学位论文 间运动，并向自身历史最佳位置和邻域历史最佳位置聚集，实现对候选解的进化。p s o 简单、易理解、参数少且易实现，对非线性、多峰问题均具有较强的全局搜索能力。 5 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 蚂蚁算法是由意大利学者m d o r i g o 等人受蚁群觅食过程的启发而提出的一种新型 的智能优化算法。a c o 算法是一种模拟进化算法，是一种用来在图中寻找优化路径的机 率型算法，根据蚁