（应用数学专业论文）搬家公司的选址问题.pdf

北京邮电大学硕士研究生毕业论文 搬家公司的选址问题 摘要 选址问题研究的是如何选定一个或多个设施的地理位置使得所 考虑的目标达到最优的问题。搬家公司试图选择若干个居住区开设 公司的店面，店面的选择需要考虑的因素很多，除了该市的不同区 划间的相对地理位置以及与之相关的交通条件外，还有各居住区的 人口数以及不同居住区间的人口流动情况。 本文主要研究了搬家公司选址问题的模型建立和求解，结合搬 家公司具体问题，逐一分析搬家公司行车时所产生的运输成本和开 设店面的成本费用等。以开设店面的费用和行车费用总和最小为目 标，根据搬家公司各个店面之间的联系情况和车辆调度方法的不同， 提出了三种不同的数学模型。并利用遗传算法对三个模型进行求解； 其次把简化的抛物线法作为局部搜索算子，融入实数编码遗传算法， 构成适用于求解全局优化问题的混合遗传算法，对模型进行求解。 最后通过算例应用和敏感度分析，以验证本文所构建的模型的合理 性及可行性。 关键词：选址问题遗传算法混合遗传算法抛物线法 北京邮电大学硕上研究生毕业论文 t h el o c a t i o np r o b l e mo f m o n gco m p a n y a b s t r a c t t h es t u d yo fl o c a t i o np r o b l e mi sh o wt os e l e c to n eo rm o r ef a c i l i t i e sb y c o n s i d e r i n gt h eg e o g r a p h i cl o c a t i o nm a k e st h eg o a lo fr e a c h i n go p t i m a l m o v i n g c o m p a n i e s a lea t t e m p t i n gt os e l e c tan u m b e ro fr e s i d e n t i a la l e a st oo p e nt h e c o m p a n y ss t o r e s ，t h ec h o i c eo fs t o r e sn e e d st oc o n s i d e ran u m b e ro ff a c t o r s ，a p a r t f r o mt h ec i t y sd i f f e r e n td i v i s i o n sa sw e l la st h er e l a t i v eg e o g r a p h i c a ll o c a t i o n a s s o c i a t e d 、) i ，i t ht h et r a f f i cc o n d i t i o n s ，t h e r ea r ev a r i o u sr e s i d e n t i a la r e a so f p o p u l a t i o na sw e l la st h er a n g eo ft h ep o p u l a t i o nl i v i n gi nd i f f e r e n tf l o w s t h i sp a p e rs t u d i e st h el o c a t i o np r o b l e mo ft h em o v i n g c o m p a n y , a b o u tg i v i n g i t sm a t h e m a t i cm o d e l sa n dh o wt os o l v et h em o d e l s i nt h i sp a p e r , w ec o n s i d e rt h e s p e c i f i ci s s u e so ft h em o v i n gc o m p a n i e sa n dd i s c u s st h ei n f l u e n c ef a c t o r s ，s u c ha s t h ec o s to ft r a n s p o r t a t i o na n dt h ec o s to fo p e n i n gs t o r e s t h e nw ee s t a b l i s ht h r e e c o s t so p t i m i z a t i o nm o d e l sf o rt h el o c a t i o np r o b l e mo ft h em o v i n gc o m p a n y , a c c o r d i n gt ot h ed i f f e r e n tv e h i c l es c h e a u l i n gw a y s ，c o m b i n a t i o nt h el i n k a g e s b e t w e e nt h ev a r i o u ss t o r e s t h e nu s i n gt h ei m p r o v e dg e n e t i ca l g o r i t h mt os o l v et h e t h r e em o d e l s ，w eo b t a i na no p t i m a la n dp r a c t i c a ll o c a t i o n s e c o n d l y , t h es i m p l i f i e d p a r a b o l am e t h o di si n t e g r a t e di n t ot h eg e n e t i ca l g o r i t h r na sa l o c a ls e a r c ho p e r a t o r t h e nan o v e lh y b r i dg e n e t i ca l g o r i t h mf o rg l o b a lo p t i m i z a t i o np r o b l e m si sp r o p o s e d t os o l v et h em o d e lt w o 。f i n a l l y , t h r o u g ht h es e n s i t i v i t ya n a l y s i sa n dt h ef e a s i b i l i t yo f t h ec o n c r e t em o d e lh a sp r o v e nt h er a t i o n a l i t ya n dt h ef e a s i b i l i t yo ft h em o d e l k e yw o r d s ：l o c a t i o np r o b l e m ；g e n e t i ca l g o r i t h m ；h y b r i dg e n e t i ca l g o r i t h m ； p a r a b o l am e t h o d i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗 列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任口 本人签名：蕊莛遮 日期： 丝刍! 堡圣丑垡璺 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位 属北京邮电大学。学校有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布 学位论文的全部或部分内容，可以允许采用影印、缩印或其它复 制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此 规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权 书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：氆叠查日期：2 塑生墨旦竺旦 导师签名：礅盆塑。f 毛1日期：1 壁2 聋三团! 兰盈! 北京邮电人学硕士研究生毕业论文 1 1 研究的背景和意义 第一章绪论弟一早珀下匕 选址问题是一个复杂的综合性决策过程，既需要定性考虑，又需要定量分 析。目前已有很多学者对物流配送中心选址问题进行研究，总结他们的研究方 法大致可以分为定性法和定量法两大类。其中，定性的方法主要是层次分析法 和模糊综合评价相结合的方法，对各方案进行指标评价，来确定最终地址；定 量的方法主要包括重心法，运输规划法，c l u s t e r 法，c f l p 法，0 1 整数规划 法，遗传算法等，松弛算法和启发式算法以及两者的结合应用。 总体来说，这些物流配送中心选址方法大致可分为以下三类： ( 1 ) 应用连续型模型选址： 连续模型选址方法认为物流配送中心的地点可以在平面上取任意点，代表 性的方法是重心法和交叉中值法。该方法不限于对特定的备选点的选择，灵活 性较大，特别是在单个物流配送中心选址的应用中，已经得到多数人的接受和 认可。但是，由于这个地址可能位于河流、建筑物或其他无法实现的地点，实 际上找到的最优地点可能很难实现。 ( 2 ) 应用离散型模型选址 离散模型选址方法认为物流配送中心的备选地点是有限的几个场所，最合 适的地址只能按照预定的目标从有限个可行点中选取。代表性的方法有：整数 或混合整数规划问题的分制定界法、鲍姆尔一沃尔夫( b o u m o l w o l f e ) 法、 库恩一汉姆布利尔( h u e h n - h a m b u r e e r ) 、反盯氏法、逐次逼近模型法等等。如 果基础数据完备，该类方法得出的解是较符合实际情况的。但是这种方法所需 要的基础资料相当多，而且这类方法所建立的模型多数已经被证明为n p 问题， 无法用线性模型的方法来处理，算法相当复杂计算量较大。 ( 3 ) 应用德尔菲( d e l p h i ) 专家咨询法选址 d e l p h i 方法选址的中心思想是将专家凭经验专业知识做出的判断以数值的 形式表示出来，从而经过综合分析后对选址进行决策。由于前两类的选址研究 很难将选址中的所有影响因素考虑周全，如：地理，地形，环境，交通，城市 用地等等，或者即使想把这些因素考虑全面，也很难量化形成模型中的约束条 件。因此，建立起一套物流配送中心的选址评价指标体系，应用层次分析法、 灰色关联理论、变权综合及模糊评价等数学方法进行综合评价，进而确定物流 配送中心的最优位置就显得十分有效。但是，这类方法专家的主观判断占有主 北京邮电大学硕士研究生毕业论文 导地位，决策结果往往受到专家的知识结构，经验以及他们所处的地位、时代 和社会环境等诸多因素的限制和影响。所以，对于有限的备选地点，该类方法 尽管比较有效，则必须具备足够的基础资料，辅助以定量分析，否则会缺乏足 够的说服力。 国内外物流配送中心选址问题的研究已有几十年的历史，对各种类型物流 配送中心的选址问题在理论和实践方面都取得了令人瞩目的成就，形成了许多 可行的模型和方法。 但是对于具体的搬家公司选址问题却没有相应的资料和文献，为了更好地 为居民服务，也为了实现搬家公司节省费用，实现利益最大化，店面的选址就 成为一个值得深入研究的问题。对于搬家公司来说，利润的最大化是其追求的 目标，为实现这一目标，搬家公司最关心的问题是在何处建店面，建多大的店 面才能实现利润的最大化，也即是实现搬家公司成本最小化，因此需要结合搬 家公司的具体问题。 搬家公司的选址模型所考虑的因素与一般的选址问题不同，配送中心或者 工厂仓库的选址模型，只需要考虑建店的费用和配送中心到达顾客地址的单程 距离，实现其运输费用和店面费用的最小化；但是，搬家公司的选址问题，根 据其实际运营过程及其所提供的服务类型，需要考虑搬家公司从搬迁任务开始， 到任务的完成，回到店面的整个路程实现，这也是其它选址模型里面所没有探 讨的问题，结合搬家公司具体问题和实现过程，综合考虑不同区划间的相对地 理位置以及与之相关的交通条件外，还有各居住区的人口数以及不同居住区间 的人口流动情况，根据搬家公司车辆不同的调度方法建立相应的选址模型，应 用最优化方法对模型求解，给出搬家公司最佳的店面选择方案，这也是本文的 意义所在。 随着人们生活水平的提高，搬迁日趋频繁，搬家公司的业务也有相应的增 加，搬家公司往往在一定地区范围内开设多个分店。为了更好地为居民服务， 也为了节省费用，店面的选址就成为一个值得研究的问题。 1 2 本文主要工作 本文主要研究搬家公司的选址问题及其算法实现，在第一章探讨了选址问 题的研究情况和背景，阐述了研究搬家公司选址问题的实际意义。 在第二章对几种经典的选址模型及算法进行了概述，在对这些比较经典的 选址模型的分析研究基础上，结合搬家公司具体问题和实现过程，综合考虑不 同区划间的相对地理位置以及与之相关的交通条件，还有各居住区的人口数以 及不同居住区间的人口流动情况，根据搬家公司车辆不同的调度方法，店面数 2 北京邮电人学硕士研究生毕业论文 目的不同以及各个店面之间的联系情况，提出了三种不同的数学模型。 在第三章中完成了模型的算法实现，首先介绍了遗传算法，并结合实例用 遗传算法对模型进行求解；其次，把简化的抛物线法作为局部搜索算子，融入 实数编码遗传算法，构成适用于求解全局优化问题的混合遗传算法，结合实例 对第二章所建立的模型二进行求解；最后通过算例应用和敏感度分析，以验证 本文所构建的模型的合理性及可行性。 3 北京邮电大学硕士研究生毕业论文 第二章搬家公司选址问题和模型 2 1 几种经典的选址模型 选址问题多种多样，按决策变量的特征，将其分为两类：一类是连续选址 问题，决策变量可以在某一平面连续取值；一类是离散选址问题，决策变量是 在有限的点中组取值。 1 连续选址问题 平面上的连续选址模型主要有两点特征：一是决策变量是连续的，即可以将 工厂建在平面上的任何一点；二是采用适合的度量方法度量距离。比较常用的 有厶距离( 也称直角距离) ，三：距离( 也称欧氏距离) 和厶距离。 最早的连续选址问题是单工厂静态选址的韦伯( w e b e r ) 问题，将加权距离作 为唯一的选址决策因素。问题可以这样描述：选择一个工厂的坐标 ( x , y ) r r ，使得给定的需求点0 i ，钆) 到该设施的加权距离以k y ) 的和最 小。可以用下面的数学模型表示： ( 嘲卿心以o ，y ) ( 1 ) ”i e j l ： 这里畋o ，y ) = ( x - - a i ) 2 + ( y - b k ) 2 ， 将韦伯问题推广：选择p 个工厂，1 ， o ，1 ) ( 3 - 1 ) ( 3 2 ) c 扩= m i n d 硅 + m i n d 玎) ix i = 1 ，z ，= 1 ；k ，= 1 ，m ( 3 3 ) 其中：旯为常数 以表示是否在居住区k 开设店面 c 。表示在k 点开设店面的费用 目标函数( 3 ) 是要求开设店面的费用，从搬迁起点到搬迁终点的行车费用 和空载车费在内的总费用最小；( 3 1 ) 表示开设的店面数目的约束条件限制； 北京邮电大学硕十研究生毕业论文 ( 3 2 ) 以为o ，1 变量；只考虑开设了店面的居民区，即黾= 1 的点k ；( 3 3 ) 店面选择的使得店面k 到搬家起点f 的距离最小，搬家终点j f 到搬家店面r2 _ 间 的距离最小。 1 2 北京邮电大学硕上研究生毕业论文 第三章模型的算法实现 工厂选址问题已经形成了多种求解方法，大致可分为定性和定量两类：定性 的方法主要是结合层次分析法和模糊综合法对各方案进行指标评价，找出最优 选址；定量的常用方法包括松弛算法和启发式算法以及两者的结合。 线性松弛算法和拉格朗日松弛算法的基本原理是：将造成问题难的约束吸 收到目标函数中，并使得目标函数依旧保持线性，由此使得问题易于求解。一 些组合优化问题在现有的约束条件下很难求得最优解，但在原问题减少某些约 束后，求解问题的难度就大大减少，达到在多项式时间内求得减少约束后问题 的最优解。由于拉各朗日松弛算法的实现比较简单且有较好的性质，因此它不 仅可以用来评价算法的效果，同时也可以用在其它算法中，提高算法的效率。 拉各朗日算法主要包括次梯度算法和拉各朗日松弛启发式算法。它们两个的主 要应用是给出混合整数规划问题的下界和构造基于拉各朗日松弛的启发式算 法。 在介绍启发式算法之前我们先介绍状态空间搜索。状态空间搜索就是将问 题求解过程表现为从初始状态到目标状态寻找路径的过程。由于求解问题的过 程中分枝有很多，主要是求解过程中求解条件的不确定性、不完备性造成的， 这使得求解的路径很多，这些路径构成了一个图，这个图就是状态空间。问题 的求解就是在图中找到一条从开始到目标的路，寻找的过程叫做搜索。常用的 状态空间搜索有深探法和广探法口射，深探法是按照一定的顺序查找完一个分枝， 再查找另一分枝，直到找到目标为止。广探法是从初始状态按某种顺序一层一 层往下找，找到目标为止。这两种搜索方式的缺陷在于都是在一个给定的状态 空间穷举。这在状态空间不大的情况下是很合适的算法，但是在空间很大又不 可预测的情况下就不可取了。这就要用到启发式搜索。 启发式搜索就是指在状态空间中对每一个要搜索的位置按照某种方式进行 评估，得到最优的位置，再从这个位置进行搜索直到达到目标。这样可以省略 大量的无谓的搜索路径，提高了效率。不同的位置评估方式，得到不同的算法。 常用的启发式算法包括禁忌搜索、遗传算法、进化算法、模拟退火算法、蚁群 算法、人工神经网络等等。 3 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是模拟生物在自然界中的遗传和进化过程 1 3 北京邮电大学硕上研究生毕业论文 而形成的一种自适应全局优化搜索算法汹1 。它最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年代对自然和人工自适应系统的研究。遗传算法产生的开 始阶段并没有引起人们的关注，一方面是因为它本身还不成熟；另一方面，当 时的计算机容量小，计算速度慢，也使得需要较大计算量的遗传算法难以实际 应用。7 0 年代d ej o n g 基于遗传的思想在计算机上进行了大量的纯数值函数优 化计算试验。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行归纳总结， 形成了遗传算法的基本框架，遗传算法也迎来了兴盛发展时期。这包括“早熟” 现象的研究和对“收敛 的证明啪1 ，同时针对遗传算法的不足提出了改进方 法，取得了一定的成绩。 3 1 1 基本遗传算法概述 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。 受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自 适应系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算 机模拟钟令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗 传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴 的生物学基础就是生物的遗传和进化。 生物的遗传物质的主要载体是染色体( c h r o m o s o m e ) ，脱氧核糖核酸( d n a ) 是 其中最主要的遗传物质，而基因( g e n e ) 又是控制生物性状的遗传物质的功能单 位和结构单位。复数个基因组成染色体，染色体中基因的位置称为基因座 ( l o c u s ) ，同一个基因座可能有的全部基因称为等位基因( a l l e l e ) 。基因和基因 座决定了染色体的特征，也就决定了生物个体的性状。此外，染色体有两种相 应的表示模式，即基因型( g e n o t y p e ) 和表现型( p h e n o t y p e ) 。所谓表现型是指生 物个体表现出来的性状，而基因型指与表现型密切相关的基因组成。同一种基 因型的生物个体在不同的环境下可以有不同的表现型，因此表现型是基因型与 环境条件相互作用的结果。在遗传算法中，染色体对应的是数据或数组，在标 准的遗传算法中，这通常是由一维的串结构数据来表现的。串上各个位置对应 上述的基因座，而各位置上所取的值对应上述的等位基因。遗传算法处理的是 染色体，或者叫基因型个体( i n d i v i d u a l ) 。一定数量的个体组成了群体 ( p o p u l a t i o n ) 。群体中个体的数目成为群体的大小( p o p u l a t i o ns i z e ) ，也叫群 体规模。而各个体对环境的适应程度叫做适应度( f i t n e s s ) 啪1 。 此外，执行遗传算法时包含两个必需的数据转换操作，一个是表现型到基 因型的转换，另一个是基因型到表现型的转换。前者是把搜索空间中的参数或 解转换成遗传空间中的染色体或个体，此过程又叫做编码( c o d i n g ) 操作；后者 1 4 北京邮电大学硕l ：研究生毕业论文 是前者的一个相反操作，叫做解码( d e c o d i n g ) 操作。 基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者 设计了许多不同的编码方法来表示问题的可行解，并开发出了许多不同的遗传 算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗 传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通 过对生物遗传和进化过程中选择、交叉和变异机理的模仿，来完成对问题最优 解的自适应搜索过程。基于这个共同特点，g o l d b e r g 总结出了一种统一的最基 本的遗传算法一一基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，简称s g a ) 1 。 基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其 遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础，它不 仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 尽管遗传算法本身在理论和应用方法上仍有许多待进一步研究的问题，由 于它具有简单、通用、鲁棒性强，适用于并行分布处理等特点，遗传算法在下 面领域中已展现了其特色和魅力：函数优化、组合优化问题、生产调度问题、 自适应控制、结构性优化、图像处理、军事应用、规划设计、遗传编程、机器 学习和人工生命等。 3 1 1 1 基本遗传算法实现 基本遗传算法( 也称为标准遗传算法或简单遗传算法，s i m p l eg e n e t i c a l g o r i t h m s ，简称s g a ) 是一种群体型操作，该操作以群体中的所有个体为对 象，只使用基本遗传算子( g e n e t i co p e r a t o r ) ：选择算子( s e l e c t i o no p e r a t o r ) 、 交叉算子( c r o s s o v e ro p e r a t o r ) 和变异算子( m u t a t i o no p e r a t o r ) ，其遗传进 化操作过程简单，容易理解。选择、交叉和变异是遗传算法的3 个主要操作算 子，它们构成了所谓的遗传操作，使遗传算法具有了其他传统算法没有的特点。 基本遗传算法可表示为： s g a = ( c ，e ，r ，m ，f ，甲，d ( 3 一卜1 ) 式中：c 个体的编码方法； e 个体适应度评价函数； 只初始种群； m 种群大小； 选择算子； r 交叉算子； 甲变异算子； r 遗传运行终止条件。 图3 1 所示为基本遗传算法的流程图： 1 5 北京邮电大学硕上研究生毕业论文 图3 - 1 遗传算法的基本流程图 3 1 1 2 基本遗传算法的步骤 1 染色体的编码( c h r o m o s o m ec o d i n g ) 与解码( d e c o d e ) 遗传算法进化过程是建立在编码机制基础上的，编码对于算法的性能如搜 索能力和种群多样性等影响很大。它的工作对象是可行解的个体编码，通过对 编码的选择，交叉，变异操作来达到优化目的，这也是遗传算法的特点之一。 遗传算法通过这种对个体编码的操作，不断搜索出适应度较高的个体，并在群 体中逐步增加其数量，最终寻求出问题的最优解或近似最优解。在遗传算法中 如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所 能处理的搜索空间的转换方法就称为编码。而由遗传算法的解空间向问题空间 的转换称为解码。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键 步骤。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编 码方法。总的来说，这些编码方法可以分为三大类：二进制编码、浮点数编码、 符号编码方法。 浮点数编码方法嘲：对于一些多维，高精度要求的连续优化算法，使用二 进制编码来表示个体时将会有一些不利之处。人们在一些经典优化算法的研究 中的一些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。 为了克服二进制编码方法的缺点，人们提出了个体的浮点编码方法。所谓浮点 1 6 北京邮电大学硕士研究生毕业论文 数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体 的编码长度等于其决策变量的位数，因为这种编码方法使用的是决策变量的真 实值，所以浮点数编码方法也叫做真值编码方法。 浮点数编码方法有以下几个优点： ( 1 ) 适合于在遗传算法中表示范围较大的数； ( 2 ) 适合于精度要求较高的遗传算法； ( 3 ) 便于较大空间的遗传搜索； ( 4 ) 改善了遗传算法的计算复杂度，提高了运算效率； ( 5 ) 便于遗传算法与经典优化算法的混合使用； ( 6 ) 便于设计针对问题的专门知识的知识型遗传算子； ( 7 ) 便于处理复杂的决策变量约束条件。 2 个体适应度函数 在遗传算法中，使用适应度( f i t n e s s ) 这个概念来度量群体中各个个体在优 化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体 遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对 小一些。度量个体适应度的函数就称为适应度函数( f i t n e s sf u n c t i o n ) 。 适应度函数也称为评价函数，是根据目标函数确定的用于区分群体中个体 好坏的标准，是算法演化过程中的驱动力，也是进行自然选择的唯一依据。适 应度函数总是非负的，任何情况下都希望其值越大越好。而目标函数可能有正 有负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之 间进行变换。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步 的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。 评价适应度函数的一般过程为： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型； ( 2 ) 由个体的表现型可计算出对应个体的目标函数值； ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适 应度。 3 选择算子 选择算子或是复制算子是遗传算法的基本算子，它的作用是从当前代群体 中选择出一些比较优良的个体，并将其复制到下一代群体中。体现了“适者生 存 的自然选择原则。它的主要目的是为了避免基因缺失、提高全局收敛性和 计算效率。 目前所适应的选择算子有以下几种： 1 7 北京邮电人学硕士研究生毕业论文 最常用和最基本的选择算子是比例选择算子( p r o p o r t i o n a lm o d e l ) 。所谓 比例选择算子，是指被选中并遗传到下一代群体中的概率与该个体的适应度大 小成正比。比例选择实际上是一种有退还随机选择，也叫做赌盘( r o u l e t t e w h e e l ) 选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。但是这种 操作容易产生较大的抽样误差。 最优保留策略( e l i t i s tm o d e l ) ，即当前群体中适应度最高的个体不参与交 叉运算和变异运算，而是用它来替换掉本代群体中经过交叉变异等遗传操作后 所产生的适应度最低的个体。 确定式采样选择( d e t e r m i n i s t i cs a m p l i n g ) ，它的基本思想是按照一种确 定的方式来进行选择操作。它能保证适应度较大的一些个体一定能被保留在下 一代群体中，并且操作简单。 无回放随机选择( e x p e c t e dv a l u em o d e l ) ，它的基本思想是根据每个个体 在下一代群体中的生存期望值来进行选择运算。这种操作可以降低选择误差， 但操作不便。 无回放余数随机选择( r e m a i n d e rs t o c h a s t i cs a m p l i n gw i t hr e p l a c e m e n t ) 它的主要思想是取每个个体在下一代群体中的生存期望的整数部分做比例选 择。它能确保适应度比平均适应度大的一些个体一定能够被遗传到下一代群体 中，因此选择误差比较小。 排序选择( r a n k - b a s e dm o d e l ) ，其主要思想是对群体中所有个体按照其适 应度大小进行排序，基于这个排序来分配各个个体被选中的概率。它着眼于各 个适应度之间的大小关系，随机性很强，有较大的误差，当选择群体很大时， 计算量也很大的。 随机联赛选择( s t o c h a s t i ct o u r n a m e n tm o d e l ) 是一种基于个体适应度之间 大小关系的选择方法。它的基本思想是每次选取几个个体之中适应度最高的一 个个体遗传到下一代群体中。 4 交叉算子 在生物的自然进化过程中，两个同源染色体通过交叉而形成新的染色体， 从而产生出新的个体和物种。交叉重组是生物遗传和进化过程中的一个主要环 节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。 遗传算法中所谓交叉运算，是指对两个相互配对的染色体按某种方式相互 交换其部分基因，从而形成两个新的个体。它在遗传算法中起着关键作用，是 产生新个体的主要方法，决定了遗传算法的全局搜索能力。 交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多 地破坏个体编码串中表示优良性状的优良模式，又要能够有效地生产出一些比 较好的新个体模式。另外，交叉算子的设计要和个体编码实际统一考虑。 1 8 北京邮电人学硕士研究生毕业论文 最常用的交叉算子有如下几种： ( 1 ) 单点交叉( o n e - p o i n tc r o s s o v e r ) ，又成为简单交叉，它是在个体编码 串随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单 点交叉的重要特点是：若邻接基因座之间的关系能提供较好的个体性状和较高 的个体适应度的话，则这种单点交叉操作破坏这