（市政工程专业论文）分类遗传算法在给水管网优化设计中的应用.pdf

_ ! l m 子v w j _ 氕土子诬此又茹i 姒 寸罔等二 螂竹给7 | ( _ 管嘲是城市供水糸绩的币要环=方向城市给水学嘲是联 系水r 希i 蒯户的“桥梁”，另方向城市给水管网鲍投资占移个供水糸镜的 5 0 8 0 。凶此，对城市给水管网作优化设计以爆可能降低造价是大有必耍 的一 l f 是由于给水管网优化设计在给水t 程中占有苇要地位，不少困内外 学者对其进行r 广泛而深入的研究，提出了多种优化方法，诸如线性规划 法、非线性规划法、动态规划法和标准遗传算法。但这螳方法在实际应剧 中均存在定的局限性。 本文首先闸述了给水管网优化设计的内容和意义，简单介绍了已宵的 各种优化方法，分析比较了各种优化方法并指出其存在的不足。接着，介 绍了遗传算法的基本原理，以管网造价为目标函数，建立了给水管网优化 设计的遗传算法模型。在标准遗传算法的基础上，作者提出了种新的改 进遗传算法分类遗传算法，使新型优化算法( 遗传算法) 和经典优化 方法( 稿发式优化算法) 巧妙结合起来。并通过两个实例( 。个为新建管 网，+ 个为扩建管网) 加以验证，应片j 表明分类遗传算法无论是在寻优能 力还是在收敛速度方面，都远远优于传统遗传算法。最后，作者对后续工 作进行了展望。 关键词遗传算法；给水管网；优化 望! 兰堕查兰型王堕苎兰兰! 兰堕兰一里里丛 a b s t r a c t u r b a nw a t e rs u p p l yn e t w o r k sa r ea ni m p o r t a n tp a r to ft h ew a t e rs u p p l y s y s t e m s o no n eh a n d ，i ti sab r i d g el i n k i n gw a t e r - w o r k s w i t hc o n s u m e r s o n t h eo t h e rh a n d i ta c c o u n t sf o r5 0 - 8 0p e r c e n to ft o t a lw a t e rs u p p l ys y s t e m s f h e r e f o r e ，i ti se s s e n t i a lt oo p t i m i z et h ew a t e rs u p p l yn e t w o r k sf o rr e d u c i n g t h ep a v i n gc o s t t h eo p t i m a ld e s i g no fw a t e rs u p p l yn e t w o r k sh a sb e e nb r o a d l ya n d d e e p l ys t u d i e db yal o to fd o m e s t i ca n df o r e i g ns c h o l a r sj u s tb e c a u s eo f i t s i m p o r t a n t s t a t u si nw a t e r s u p p l ye n g i n e e r i n g t h e s es c h o l a r sp u tf o r w a r d af e w k i n d so fo p t i m a lm e t h o d s ，s u c ha sl i n e a rp r o g r a m m i n gm e t h o d ，n o n l i n e a r p r o g r a m m i n gm e t h o d ，d y n a m i cp r o g r a m m i n gm e t h o d a n d 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 ) h o w e v e r ，t h e s em e t h o d sa l l h a v es o m el i m i t a t i o n so n p r a c t i c e 1 1 1 i sp a p e r , f i r s t l y , e x p a t i a t e st h ec o n t e n ta n ds i g n i f i c a n c ea b o u to o t i m a l d e s i g no f w a t e rs u p p l yn e t w o r k s ，b r i e f l yi n t r o d u c e sv a r i o u so p t i m a lm e t h o d s t h a th a v eb e e n a d v a n e e d ，a n a l y z e s t h e s em e t h o d sa n d p o i n t s o u tt h e i r l i m i t a t i o n s s e c o n d l y , i ti n t r o d u c e st h ep r i n c i p l eo fg e n e t i ca l g o r i t h m s ( g a ) i tt a k e sc o s to f w a t e r s u p p l yn e t w o r k sa so l ! i e e t i v ef u n c t i o na n d s e t su pt h eg a m o d e lo no p t i m a ld e s i g no fw a t e rs u p p l yn e t w o r k s b a s e do ns g a ，t h ep a p e r s e t su pan e wi m p r o v e dg e n e t i ca l g o r i t h m s - r a n k i n g g e n e t i ca l g o r i t h m s ( r g a ) t h a t i n t e g r a t e d an e wi n t e l l i g e n t o p t i m i z a t i o nm e t h o d ( g e n e t i c a l g o r i t h m so p t i m i z a t i o n m e t h o d ) a n dac l a s s i c a l o p t i m i z a t i o n m e t h o d ( h e u r i s t i co p t i m i z a t i o nm e t h o d ) p e r f e c t l y a tt h es a m et i m e i tp r o v i d e sw i t h t w oe x a m p l e s ( o n ef o rn e w - b u i l t ，t h eo t h e rf o re x p a n s i o n ) ，a p p l i c a t i o n so ft h e a l g o r i t h m ss h o wr g a i sf a rb e t l e rt h a ns g an om a t t e ra tr e s u l t so ra tr u n f i m e a tt h ee n d t h ea u t h o rr e c o g n i z e st h ef u r t h e rw o r k st h a tf o r1 l st od o k e yw o r d sg e n e t i ca l g o r i t h m s ；w a t e rs u p p l yn e t w o r k s ；o p t i m i z a t i o n 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 给水管网系统优化研究的重要性 城市给水系统由取水、净水和输配水三个子系统组成，输配水管网是 城市供水系统和管道化灌溉系统的重要组成部分，它通过各级输配水管道 把水安全可靠地输送到各个用水点，并满足水量、水压和水质的要求。在 整个供水系统中管网部分的投资一般要占到工程总投资的5 0 8 0 ，而且 涉及到庞大的能耗和运行管理费用。同时，随着水资源日益紧缺和水资源 开发利用率的提高，新系统的新建和老系统的修复、改建和扩建等所需要 的工程投入逐渐增大。因此，水管网系统的规划、设计和运行管理是否科 学、经济、实用，直接影响工程总投资、运行费用及系统可靠性。在工程 资金投入有限的情况下，进行管网系统优化设计，寻求能满足水量和水压 要求，且能使整个系统的造价最低或年费用最小、系统可靠性最高的设计 方案，对节约投资、降低能耗、提高经济效益和社会效益等有着重要的现 实意义。 给水管网系统的优化研究主要是通过构造抽象或简化的管网优化设计 模型，借助于最优化理论和计算机技术，研究如何在管网工程规划设计中 合理地选择有关技术参数，从众多可行的设计方案中寻找既能满足工程设 计要求，又能降低工程投资成本的最优或次优设计方案，作为工程建设施 工和运行管理的依据。长期以来，针对管网优化问题，科研工作者进行了 广泛研究，取得了大量研究成果，产生了巨大的经济效益。特别是最优化 理论与技术、计算机技术、数值计算方法的发展和广泛应用，为管网优化 研究提供了必要的理论基础和实现手段，逐渐使工程设计最优化成为衡量 工程设计水平的一种标准。 通常一个完整的给水管网系统设计过程包括规划、设计、运行管理三 个阶段。规划阶段主要进行管网干支线的布置，力求确定管网总长度最短 或投资最小的最佳管网结构形式。设计阶段以最优管网布置形式为依据， 通过管网水力计算确定有关技术参数，主要解决管径最佳组合问题，寻求 系统造价的最优设计方案。一个按最优设计方案施工建设的管网系统还必 须通过水泵机组优化组合、阀门开启优化组合、水压联合优化调度等优化 运行研究，按最优运行策略运行管理才能发挥系统最佳性能。本论文侧重 于给水管网优化设计。 从管网系统的规划、设计到运行管理，每个设计阶段的设计任务依赖 于其他阶段的设计结果，彼此之间有一定的相互影响和相互制约，必须循 西南交通大学硕士研究生学位论文第2 页 环进行才能使系统性能优化达到整体最优。由于在不同设计阶段，管网优 化研究的对象和侧重点内容不同，采用的优化模型和算法也不相同，一般 仍按相对独立的阶段分别进行研究。因此，水管网系统的优化研究工作按 照主要研究对象的不同，一般可以分为管网优化布置、管网优化设计和管 网优化调度等几个方面“。这里忽略管网优化布置和管网优化调度，而只讨 论管网优化设计。 1 2 管网优化设计研究 在管网优化研究的发展过程中，由于管网优化设计对整个系统的投资 影响较大，所产生的经济效益也比较显著。因此，研究人员们对管网优化 设计研究非常重视，其发展速度和取得的成果均优于管网优化布置研究。 管网优化设计研究始于2 0 世纪6 0 年代末，最先在城市供水系统的规 划设计中引起工程设计人员们的重视”。经过3 0 多年的发展和完善，管 网优化设计模型和算法在工程实践中得到了较为广泛的应用，成为提高系 统设计水平和设计效率的重要工具。 目前管网设计优化模型大致可分为数学规划模型和非数学规划模型两 大类，其中应用最广泛的是基于数学规划技术的优化模型，如线性规划模 型、非线性规划模型、动态规划模型和整数规划模型等。非数学规划模型 大多数是基于工程经验和观察所总结的经验性方法，或者是用于特定网络 结构的启发方法。在实际应用中，由于优化设计的目的、所考虑的约束条 件、管网结构类型、系统规模大小等因素的不同，构造出许多不同的优化 模型，各种优化模型的实用性也有很大的差异。 1 2 1 线陛规划模型 线性规划( l i n e a r p r o g r a m m i n g ) ，是研究在一组线性约束条件下，求某 个线性目标函数的最小值或最大值问题，是数学规划中产生时间较早( 产 生于2 0 世纪3 0 年代) 、理论和算法比较成熟、应用最广泛的一个重要分支 ”。许多实际问题在数学上可直接抽象为线性规划问题，或者通过一定的 技术手段转化为线性规划问题来处理。线性规划问题通常可以写成下列标 准形式： m i n c j ， ( 1 一1 ) 西南交通大学硕士研究生学位论文第3 页 n 口f x ，= b 。i = 1 ，川 x ，0 = 1 ，n 式中 _ ，x 。一决策变量，是线性规划中所要求解的变量 。l ，一，c 。一费用系数： ( 1 ，2 ) ( 1 3 ) a i ( f - l ，；j = 1 ， ) 一约束系数； 岛o = 1 ，卅) 一约束右端项a 求解线性规划模型的算法很多，如单纯形法、两阶段法、大m 法和 k a r n a r k a r 法等等。单纯形法是应用最广泛的一种通用算法，特别是单纯形 法在计算机上的成功实现，使线性规划解决问题的数量迅速增加。 国内外不少学者在这一方面作了不少的研究，并在工程实践中产生了 显著的经济效益”“”。 到目前为止，线性规划模型仍然是管网管网优化设计中经常采用的一种 优化模型。但是，应用线性规划模型进行管网优化设计，还存在一些不足： l 、线性规划模型的决策变量数目多，最优管径集合确定困难。管网中 各管道所能选择的管径觌格数目，决定着模型中决策变量数目的多少和解 的最优性。为获得全局最优解，每个管道必须能自由地从所有可用管径集 合中选择其组成管径。但是，如果所采用管径集合太大，如采用最大的商 用管径集合，则会使模型中的决策变量数目急剧增大，降低模型的求解速 度，甚至会因模型太大而无法求解。在实际应用中，设计者往往是根据自 己的实践经验来选择可用管径集合，当管网规模较大时，人工确定和调整 可用管径集合比较困难，难以构成最优集合，需要反复求解模型，增大了 计算工作量。 2 、线性规划模型的约束条件包括节点水压约束和管长约束，约束数目 多，限制了模型所能求解问题的规模。 3 、线性规划模型只能考虑线性目标函数，一些呈非线性关系的费用项 不能在模型中考虑，直接影响管网投资计算精度。 上述不足，一定程度上限制了线性规划模型的应用范围。因此，如何 采用简捷快速的方法，确定最优管径集合，减少优化模型中决策变量和约 束条件的数目，是线性规划模型在大中型管网设计优化应用中，需要进一 步研究和解决的问题。 西南交通大学硕士研究生学位论文第4 页 1 2 2 非线性规划模型 非线性规划模型( n o n l i n e a r p r o g r a m m i n g ) ，是研究在一组线性与( 或) 非线胜约束条件下，寻求某个非线性或线性目标函数的最大值或最小值问 题“，。非线性规划问题通常可用数学模型表示为： m i nf ( x ) ( 1 - 4 ) s t g f ( z ) 0i = 1 ，m h ，( z ) = 0 _ ，= 1 ， x e 4 ( 1 - 5 ) ( 1 - 6 ) ( 1 - 7 ) 式中 厂( x ) 一目标函数； g 。( 工) 、h ( x ) 一约束函数。 这些函数中至少有一个是非线性函数。 在管网系统中，管道和各种水力元件的水头损失关系、泵的抽水性能 关系、水位变化以及各项投资等，一定程度上都是非线性的，完全靠线性 模型无法准确反映问题的实质。对于一个管网系统来说，所建管网优化模 型必须能够比较真实精确地反映管网系统的实际状态，才能使获得的解越 来越接近最优解。从2 0 世纪7 0 年代初，欧美一些学者开始比较完整地把 管网优化问题描述为非线性规划问题，并建立了大量的管网优化设计非线 性规划模型。 尽管人们对非线性管网优化模型和算法进行了大量研究“8 “1 ，也取得 了一定的研究成果，但是应用非线性规划模型和算法进行管网优化设计， 仍存在一些不足： 1 、非线性规划模型的构造和求解方法的选择，往往以实际问题的结构 和分析者的经验为基础，没有统一的规则和普遍适用的解法，存在一个经 验性研究领域。 2 、尽管已经提出了许多非线性规划求解算法，如拟线性规划法、罚函 数法、拉格朗日乘子法、梯度法、广义简约梯度法等，但是这些算法的适 用范围和能力都很有限，没有种方法比其他方法具有明显的优越性。 3 、非线性规划模型求解困难，各种算法的程序代码不易得到，且通用 性和实用性较差。一般只能得到问题的局部最优解，很难得到全局最优解。 当问题变量较多时，求解速度和解的精度会大大降低。 4 、非线性规划模型的设计变量如管径、泵扬程，一般只能作为连续变 西南交通大学硕士研究生学位论文第5 页 量处理，优化结果需要圆整化，以选择标准规格的商用产品。这种圆整化 处理方法会破坏解的可行性和最优性。 因此，寻找快速、简捷、具有广泛适用性的非线性规划求解方法，丰 富和发展最优化理论与技术，具有重要的理论价值和现实意义，仍然是广 大研究人员努力攻克的主要方向之一。 1 2 3 动态规划模型 动态规划( d y n a m i cp r o g r a m r r h n g ) ，是一种求解多阶段决策过程最优化 的方法，在管网设计优化中也有一定的应用。w o n g ( 1 9 6 8 ) 等人第一次应 用动态规划法进行树状输气管网系统运行优化，以系统内泵站之间的运行 压力差作为决策变量，但没有考虑系统最优布局问题“。 l i a n g ( 1 9 7 1 ) 应用动态规划法进行供水系统最优设计“，将系统内的 每个管段作为动态规划的阶段，以每个管段入口和出口处的总压力为输入 和输出状态变量，以连续变化的管径为决策变量，以所有费用项( 包括管 道费用、动力费用和所有阶段的弃水费用) 和整个系统效率为优化目标函 数。该方法不考虑直径不同的相邻管段突然扩大或收缩所引起的水头损失， 这种处理方法影响了最终求解的精度。由于l i a n g 采用批处理方式在计算机 上实践该动态规划过程，一旦运行开始，设计者和计算机间不允许对话交 互，设计者对优化过程缺少控制能力，使计算方法相当无效率和不灵活， 导致计算时间过长，计算机内存开销过大。 k w a n g ( 1 9 7 5 ) 采用动态规划法对一个单压力水源且有多个分支管道的 发散性树状供水管网进行优化设计m 1 ，以标准管径为决策变量，以系统内 的水力关系为动态规划的状态传递关系，确定系统的最优商用管径组合。 国内的项玉章( 1 9 8 4 ) 、魏永曜( 1 9 8 4 ，1 9 8 7 ) 、刘予沛( 1 9 8 6 ，1 9 8 7 ) 、 陆少鸣( 1 9 9 5 ) 等研究者，对动态规划技术在树枝管网优化设计中的应用， 也进行了大量的探讨和研究“”。 从动态规划模型的性能及应用来看，对于单个的串联管道和小型数状 管网，动态规划能得到全局最优解和一组次优解。对于简单的环状管网， 也可以运用动态规划法求解，但需要预先假定管径，进行初始流量分配， 化环状管网为树状网，进行迭代计算等，降低了动态规划的计算效率和精 度。当应用于复杂管网时，动态规划需要的计算机内存数量和计算机运行 时间都很大，甚至得不到最优解。此外，在实际应用中只能根据问题的不 同类型，进行具体分析，构造具体的模型。对于复杂问题，在选择状态， 决策、确定状态转移规律等方面，需要丰富的想象力和灵活的技巧性，使 动态规划技术的应用范围受到限制”。 西南交通大学硕士研究生学位论文第6 页 1 3 基于遗传算法的管网优化研究 目前，在管网优化研究中一般采用的优化技术有线性规划、非线性规 划、动态规划、多目标决策技术等，用上述方法进行实际问题的优化求解 时，存在不同程度的“维数灾难”，即随着问题规模的扩大和约束条件的增 加，求解时间急剧增加且容易产生“组合爆炸”，而不可解。 遗传算法是一种新型的智能优化算法，已成功应用于众多领域。遗传 算法的全局寻优能力和隐含并行特性，使其特别适合于处理传统算法无法 解决的复杂非线性问题，且可直接用于离散变量的计算。近年来，国内外 不少学者将其应用于给水管网经济管径求解中“。并取得了不菲的成绩! 国外在这一方面走在国内前面，在1 9 9 2 年，m u r p h y 和s i m p s o n 首先把简 单遗传算法( s g a ) 应用于管网优化设计，打开了管网优化设计的新路子； s i m p s o n 和g o l d b e r g ( 1 9 9 4 ) 研究了影响s g a 的因素，对其选择机制和 初始种群的大小提出了若干参考意见；d a n d y ( 1 9 9 6 ) 对遗传算法进行改进， 并成功应用于纽约市管网的优化，节省投资达$ 3 8 8m i l l i o n 。但由于受水力 求解功能的限制，以上一般都只针对具体问题，缺乏通用性，且管网规模 不宜太大，构造不能太复杂! 在国内，遗传算法应用于管网优化设计方面， 虽然起步晚，但发展快。不少学者对遗传算法针对具体问题对遗传算法进 行不少的改进1 1 4 本论文研究内容 根据上述对本课题相关领域研究现状分析，存在的问题主要是； 1 、目前的优化方法一般将管径作为连续变量处理，优化结果需要采用 相邻的标准管径进行圆整化，这种处理方法破坏了解的最优性。 2 、应用遗传算法进行管网优化设计中存在的寻优效率和求解规模的问 题，目前的研究论文还没很好的解决，需要进一步研究和改善。 3 、目前应用遗传算法进行管网优化设计般是对特定的问题编制特定 的程序来求解，这样程序缺乏通用性。 针对上述问题，本课题研究内容主要有以下三个方面： 1 、寻求一种简单有效的编码方法一整数编码，既避免管径圆整化所 带来的误差，同时又无二进制编码冗余的缺点。 2 、对传统的简单遗传算法进行改进，提出新的改进遗传算法分类 遗传算法，使新型优化算法( 遗传算法) 和经典优化方法( 启发式优化算 法) 巧妙结合起来，大大提高其寻优能力和求解规模。 3 、引入e p a n e t 水力求解器，建立通用性很强的管网遗传算法优化设 计程序。 西南交通大学硕士研究生学位论文第7 页 本论文第二章介绍了遗传算法的基本原理、基本实现技术和数学理论 基础。 第三章介绍了e p a n e t 水力求解器的水力求解原理和简单的使用技 术。 第四章介绍了管网优化模型的建立和求解过程，提出了分类遗传算法， 并分别以新建管网和管网扩建为例，进行求解，印证分类遗传算法寻优能 力的高效性。 第五章对本论文的研究成果进行总结，对后续研究进行了讨论和展望。 西南交通大学硕士研究生学位论文 第8 页 2 1 遗传算法简介 第2 章遗传算法 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种 自适应全局优化概率搜索算法”“。它最早由美国密执安大学的h o l l a n d 教 授提出，起源于2 0 世纪6 0 年代对自然和人工自适应系统的研究“。7 0 年代d e3 0 n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数优 化计算实验”。在一系列研究工作中基础上，8 0 年代由g o l d b e r g 进行了 归纳总结，形成了遗传算法的基本框架。3 。 2 1 1 遗传算法概要 f m a x 厂( x ) ( 2 - 1 ) s t x r ( 2 - 2 ) lr u ( 2 - 3 ) 式中x = z l ，x ：， 7 一决策变量； 厂( x ) 目标函数； 式( 2 2 ) 、( 2 - 3 ) 一约束条件； u 一基本空间； r u 的一个子集。 满足约束条件的解z 称为可行解，集合r 表示由所有满足约束条件 的解所组成的一个集合，叫做可行解集合。它们之间的关系如图2 - 1 所示。 遗传算法将n 维决策变量向量j _ 一，工：，x 。】7 用n 个记号x i ( f = 1 , 2 ，h ) 所组成的符号串来表示： 西南交通大学硕士研究生学位论文第9 页 并= 蜀x 2 以j x = 阮，x 2 ，x 。】。 把每一个看作一个遗传基因，它的所有可能取值称为等位基因，这样， x 就可看做是由n 个遗传基因所组成的一个染色体。一般情况下，染色体 的长度月是固定的，但对一些问题，z 也可以是变化的。根据不同的情况， 这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是 纯粹的一个记号。最简单的等位基因是由0 和l 这两个整数组成的，相应 的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式z 是个体的基因型，与它对应的工值是个体的表现型。通常个体的表现型和 其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。 染色体x 也称为个体置对于每一个个体而要按照一定的规则确定其适 应度。个体的适应度与其对应的个体表现型x 的目标函数值相关联，x 越 接近予目标函数的最优点其适应度越大：反之，其适应度越小。 可行解 图2 1 最优解问题的可行解及可行解集合 基本空间 可行解空间 遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索 是通过对染色体z 的搜索过程来进行的，从而由所有的染色体就组成 了问题的搜索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是 由m 个个体所组成的集合，称为群体。与生物一代代的自然进化过程 相类似，遗传算法的运算过程也是一个反复迭代过程，第t 代群体记做p ( f ) ，经过一代遗传和进化后，得到第什1 代群体p ( f + 1 ) 。这个群体不 断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高 的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体 正它所对应的表现型将达到或接近于问题的最优解f 。 西南交通大学硕士研究生学位论文 第1 0 页 生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完 成的。与此对应，遗传算法中最优解的搜索过程也模仿生物的这个过程， 使用所谓的遗传操作数( g e n e t i co p e r a t o r s ) 作用于于群体p ( f ) 中，进行 下述遗传操作，从而得到新一代群体p ( t + 1 ) 。 2 1 2 遗传算法的运算过程 图2 2 所示为遗传算法的运算过程示意图。 ： l 毫传空向1 卜空向】j 匮函l 圉陵 日i i 圜b 量“誓i 焉壁 _i - i 日蹦一 西南交通大学硕士研究生学位论文第1 l 页 步骤四：交叉运算。将交叉操作数作用于群体。 步骤五：变异运算。将变异操作数作用于群体。群体p ( f ) 经过选 择、交叉和变异运算之后得到下一代群体p ( 什1 ) 。 步骤六：终止条件判断。若t l 则：t 叫+ l ，转到步骤二；若f 乃 则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计 算。 2 2 遗传算法的基本实现技术 2 2 1 编码方法 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解 空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。编码是 应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步 骤。编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从 搜索空间的基因型变换到解空间的表现型时的译码方法，编码方法也影响 到交叉操作数、变异操作数等遗传操作数的运算方法。由此可见，编码方 法在很大程度上决定如何进行群体的遗传进化运算以及遗传进化运算的 效率。一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作 可以简单地实现和执行。 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算 法的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没 有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。 作为参考，d ej o n g 曾提出了两条操作性较强的实用编码原则( 又称为编 码规则) 啪1 ： 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问 题相关的且具有低阶、短定义长度模式的编码方案。 编码原n - - ( 最小字符集编码原则) ：应使用能使问题得到自然表示 或描述的具有最小编码字符集的编码方案。 上述d e j o n g 编码原则仅仅是给出了设计编码方案时的一个指导性大 纲，它并适合于所有的问题。所有对于实际应用问题，仍必须对编码方法、 交叉运算方法、变异运算方法、解碣方法等统一考虑，以寻求到一种对问 西南交通大学硕士研究生学位论文第1 2 页 题的插述最为方便、遗传运算效率最高的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的 编码方法。总的来说，这些编码方法可以分成三大类：二进制编码方法、 浮点数编码方法、符号编码方法。整数编码是介于符号编码和浮点数数编 码之间的一种编码，这里我们只讨论符号编码方法和浮点数编码方法。 2 2 1 1 浮点数编码方法 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来 表示个体时将会有一些不利之处。首先是二进制编码存在着连续函数离散 化时的映像误差。个体编码串的长度较短时，可能达不到精度要求：而个 体编码串的长度较长时，虽然能提高求解精度，但却会使遗传算法的搜索 空间急剧扩大。其次是二进制编码不便于反映所求问题的特定知识，这样 也就不便于开发针对问题专门知识的遗传运算操作数，人们在些经典优 化算法的研究中所总结的一些宝贵经验也就无法在这里加以利用，也不便 于处理非平凡约束条件。 为改进二迸制编码方法的这些缺点，人们提出了个体的浮点数编码方 法。所谓浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮 点数来表示，个体的编码长度等于其决策变量的个数。因为这种编码方法 使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。 浮点数编码方法有下面几个优点“。： 1 、适合于在遗传算法中表示范围较大的整数： 2 、适合于精度要求较高的遗传算法； 3 、便于较大空间的遗传搜索； 4 、改善了遗传算法的计算复杂性，提高了运算效率： 5 、便于遗传算法与经典优化方法的混合使用； 6 、便于设计针对问题的专门知识的知识型遗传操作数： 7 、便于处理复杂的决策变量约束条件。 2 2 1 2 符号编码方法 符号编码方法是指个体染色体编码串中的基因取值自一个无数值含 义、而只有代码含义的符号集。这个符号集可以是一个字母表，如 a ，b ， c ，d ，) ：也可以是一个数字的序号表，如 1 ，2 ，3 ，4 ，5 ， ；还 可以是一个代码表，如 a 1 ，a 2 ，a 3 ，a 4 ，a 5 ， 等等。 西南交通大学硕士研究生学位论文第1 3 页 例如，对于旅行商问题，假设有n 个城市分别记为c l 、c 2 、c n ， 将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行 路线的个体。如 妊 c 1 ，c 2 ，c 。 就表示顺序访问城市c 1 、c 2 、c n 。若将各个城市按其代号的下 标进行编号，则这个个体也可表示为： 妊【1 ，2 ，n 符号编码的主要优点是： l 、符号有意义积木块编码原则； 2 、便于在遗传算法中利用所求解问题的专门知识； 3 、便于遗传算法与相关近似算法之间的混合使用。 但对于符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗 传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜 索性能。 2 2 2 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个 术语来度量某个物种对于其生存环境的适应程度。对生存环境适应程度较 高的物种将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁 殖机会就相对较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适 应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于 或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率 就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个 体适应度的函数称为适应度函数( f i t n e s sf u n c t i o n ) 。 遗传算法的一个特点是它仅是用所求问题的目标函数值就可以得到 下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度 来体现的。评价个体适应度的一般过程是： 1 、对个体编码串进行译码处理后，可得到个体的表现型； 2 、由个体的表现型可计算出对应个体的目标函数值； 3 、根据最优化问题的类型，由目标函数按一定的转换规则求出个体 的适应度。 西南交通大学硕士研究生学位论文第1 4 页 最优化问题可以分为两大类，一类是为求目标函数的全局最大值，另 一类为求目标函数的全局最小值。由解空间中某一点的目标函数值厂( x ) 到搜索空间中对应个体的适应度函数值f ( x ) 的转换方法： 对于最大值问题，作下述转换： 唧，= h 善0 翟麓 。， 式中，c 卅m 为一个适当地相对较小的数。 对于最小值问题，作下述转换： 刖，- 气九蕃能 c z s ， 式中，g 。为一个适当地相对较大的数。 遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依 据，通过反复迭代过程，不断地寻求出适应度较大的个体，最终可得到问 题的最优解或近似最优解。 2 2 3 选择操作数 在生物的遗传和自然进化过程中，对生存环境适应度较高的物种将有 更多的机会遗传到下一代；而对生存环境适应度较低的物种遗传到下一代 的机会就相对较少。模仿这个过程，遗传算法使用选择操作数( 或称复制 操作数，r e p r o d u c t i o no p e r a t o r ) 来对群体中的个体进行优胜劣汰操作： 适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体 被遗传到下一代群体中的概率要小。遗传算法中的选择操作就是用来确定 如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种 遗传运算。 选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主 要目的是为了避免基因缺失、提高全局收敛性和计算效率。 最常用的选择操作数是比例选择操作数。但对各种不同的问题，比例 选择操作数并不是最适合的一种选择操作数，所以人们提出了其它一些选 择操作数。并且取得了不错的效果。这里我们只讨论比例选择和最优保存 策略。 西南交通大学硕士研究生学位论文第1 5 页 2 2 3 1 比例选择 比例选择方法( p r o p o r t i o n a lm o d e l ) 是一种回放式随机采样的方法。 其基本思想是：各个个体被选中的概率与其适应度大小成正比。由于是随 机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应度较高 的个体也选择不上。 设群体大小为m ，个体f 的适应度为只，则个体被选中的概率m 为： f p b = 1 ，0( i = 1 , 2 ，m ) ( 2 6 ) f i i = 1 由上式可见，适应度越高的个体被选中的概率也越大；反之，适应度越低 的个体被选中的概率也越小。 2 2 3 2 最优保存策略 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而 不断地产生出新个体。虽然随着群体的进化过程会产生出越来越多的优良 个体，但由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏 掉当前群体中适应度最好的个体。而这却不是我们所希望发生的，因为它 会降低群体的平均适应度，并且对遗传算法的运行效率、收敛性都有不利 影响。所以，我们希望适应度最好的个体要近可能地保留到下一代群体中。 为达到这个目的，可以使用最优保存策略进化模型( e 1 i t i s tm o d e l ) 来 进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变 异运算，而是用来替代本代群体中经过交叉、变异等遗传操作后所产生的 适应度最低的个体。 最优保存策略进化模型的具体操作过程是： 1 、找出当前群体适应度最高的个体和适应度最低的个体。 2 、若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适 应的还要高，则以当前群体的最佳个体作为新的迄今为止的最好个体。 3 、用迄今为止的最好个体替换掉当前群体中的最差个体。 最优保存策略可视为选择操作的部分。该策略的事实可保证迄今为 止所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算法 收敛性的一个重要保证条件。但另一方面，它也容易使得某个局部最优个 体不易被淘汰掉反而快速扩散，从而使得算法的全局搜索能力不强。所以 西南交通大学硕士研究生学位论文第1 6 页 该方法一般要与其它一些选择操作方法配合起来使用，方可有良好的效 果。 另外，最优保存策略还可以加以推广，即在每一代的进化过程中保留 多个最优个体不参加交叉、变异等遗传运算，而直接将它们复制到下一代 群体中。这种选择方法也称为稳态复制。 2 2 4 交叉操作数 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新 的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程 的一个主要环节。模仿这个环节，在遗传算法中使用交叉操作数来产生新 的个体。 遗传算法中所谓的交叉运算，是指对两个相互配对的染色体按某种方 式相互交换器部分基因，从而形成两个新的个体。交叉运算是遗传算法区 别于其它进化算法的重要特征，它在遗传算法中起着关键作用，是产生新 个体的主要方法。 遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目 前常用的配对策略是随机配对，即将群体中的m 个个体以随机的方式组 成l 膨，2 j 对配对个体组，交叉操作是在这些配对个体组中的两个个体之间 进行的。 交叉操作数的设计和实现与所研究的问题密切相关，一般要求它既不 要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产 生出一些较好的新个体模式。另外，交叉操作数的设计要和个体编码设计 统一考虑。 交叉操作数的设计包括以下两方面的内容： 1 、如何确定交叉点的位置。 2 、如何进行部分基因交换。 最常用的交叉操作数是单点交叉操作数。但单点交叉操作有一定的适 用范围，故人们发展了其它一些交叉操作数。本论文的交叉算子采用单点 交叉和均匀交叉相结合的单点均匀交叉。 2 2 4 1 单点交叉 单点交叉( o n e p o i n tc r o s s o v e r ) 又称为简单交叉，它是指在个体编 西南交通大学硕士研究生学位论文第1 7 页 码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分 染色体。单点交叉的重要特点是：若邻接基因之间的关系能提供较好的个 体性状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状 和降低个体适应度的可能性最小。 22 4 2 均匀交叉 均匀交叉( u n i f o r mc r o s s o v e r ) 是指两个配对个体的每一个基因座上 的基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个 体。均匀交叉实际上可归属于多点交叉的范围，其具体运算可通过设置以 屏蔽来确定新个体的各个基因如何由哪一个父代个体来提供。均匀交叉的 主要操作过程如下： 1 、随机产生一个与个体编码串长度等长的屏蔽字w = w w 卜w 。w 。， 其中z 为个体编码串长度。 2 、由下述规则从彳、曰两个父代个体中产生出两个新的子代个体彳、 b ： 若w i = 0 ，则4 在第f 个基因座上的基因值继承a 的对应基因值，口 在第i 个基因座上的基因值继承b 的对应基因值； 若w l = l ，则4 在第i 个基因座上的基因值继承b 的对应基因值，口 在第i 个基因座上的基因值继承a 的对应基因值。 2 2 5 变异操作数 在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为 某些偶然因素的影响而产生一些复制差错，这样就会导致生物的某些基因 发生某些变异，从而产生出新的染色体，表现出新的生物性状。虽然发生 这种变异的可能性比较小，但它也是产生新物种的个不可忽视的原因。 模仿生物遗传和进化过程中的这个变异环节，在遗传算法中也介入了变异 操作数来产生新的个体。 遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因 座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个 体。例如，对于二进制编码的个体，其编码字符集为f o ，1 ，变异操作就 是将个体在变异点上的基因取反，即用0 替换l ，或用1 替换0 ；对于浮 点数编码的个体，若某一变异点处的基因值的取值范围为 巩。砜。 ，变 西南交通大学硕士研究生学位论文第1 8 页 异操作就是用该范围内的一个随机数去替换原基因值：对于符号编码的个 体，若其编码字符集为 a ，b ，c ， ，变异操作就是用这个字符集中一 个随机指定的且与原基因值不同的符号去替换变异点上的原有符号。 从遗传运算过程中产生新的个体的能力方面来说，交叉运算是产生新 个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产 生新个体的辅助方法，但它也是必不可少的一个运算步骤，因为它决定了 遗传算法的局部搜索能力。交叉操作数与变异操作数的相互配合，共同完 成对搜索空间的全局搜索和局部搜索，从而共同使得遗传算法能够以良好 的搜索性能完成最优化问题的寻优过程。 最简单的变异操作数是基本位变异操作数。为适应各种不同应用问题 的求解需要，人们也开发出了其它一些变异操作数。其中比较常用的几种 变异操作方法，它们适合于二迸制编码的个体和浮点数编码的个体。 2 2 5 1 基本位变异 基本位变异( s i m p l e m u t a t i o n ) 操作是指对个体编码串中以变异概率 岛随机指定的某一位或某几位基因座上的基因值作变异运算。基本位变异 操作改变的只是个体编码串中的个别几个基因座上的基因值，并且变异发 生的概率也比较小，所以其发挥的作用比较慢，作用的效果也不明显。 基本位变异操作数的具体执行过程是： 1 、对个体的每一个基因座，依变异概率岛指定其为变异点。 2 、对每一个指定的变异点，对其基因值做取反运算或其它等位基因 值来代替，从而产生一个新的个体。 2 2 5 2 均匀变异 均匀变异( u n i f o r m m u t a t i o n ) 操作是指分别用符号某一范围内均匀 分布的随机数，以某一较小的概率来替换个体编码串中各个基因座