（水利水电工程专业论文）自适应遗传算法在水库防洪优化调度中的应用.pdf

摘要 摘要 水库防洪优化调度 是凭借水库的调蓄能力 在保证大坝安全的前提下 有计 划地对水库的入库水量过程进行调节 改善天然径流的时空分配 达到除水害兴 水利 提高水资源的综合利用率 最大限度地满足人民生活和社会经济发展目的 的一种控制运用水库技术 水库防洪优化调度方案是否得当直接关系到国民经济 各部门的发展 如果方案切实合理可行 那么将带来十分可观的经济效益和社会 效益 反之 将给社会经济发展带来巨大损失 因此 进一步加强水库防洪优化 调度工作的研究就更加具有重要意义 本文首先介绍了水库优化调度的国内外研究进展 初步阐述了水库优化调度的 计算方法 在研究水库优化调度原则的基础上 依据最大削峰准则和最短洪灾历 时准则 建立单一水库防洪优化调度模型 依据通过公共防洪控制断面的最大过 流量最小和超过安全泄流量的超标水量最小的原则 建立了并联水库群防洪优化 调度模型 针对传统的优化算法在收敛速度和收敛精度等方面的不足 本文在研究遗传算 法的基础上 提出应用自适应遗传算法对水库防洪优化调度模型进行求解计算 并应用此方法分别对上述两模型进行优化计算 以淮河流域四水库为实例 应用简单遗传算法和本文提出的自适应遗传算法 对单一水库进行优化计算 最大下泄流量较按照原有调度规则运行的下泄流量均 有减少 削峰率均有提高 结果表明 自适应遗传算法根据个体优劣程度对遗传 控制参数进行自动调整 较好地改善了简单遗传算法的不足 应用自适应遗传算 法对并联水库群进行优化计算 公共防洪控制断面的超标水量和最大过流量都有 所减少 优化效果明显 关键词 并联水库群防洪优化调度自适应遗传算法 a b s t r a c t ab s t r a c t t h a to p t i m a l 叩e r a t i o no ff l o o dc o n t r o lr e s e n o i ri sat e c h l l o l o g yo fc o n 仃o lm e r e s e r v o i rw h i c hr e l y i n go nr e s e n o i rs t o r e su pa na b i l i t y w a t e ry i e l dp r o c e s sc a r r i e so u t a d j u s t m e n to nt h er e s e n o i rb ep u ti ns t o r a g ea c c o r d i n gt op l a n t h es p a c e t i m e i m p r o v i n gn a t u r a lm n o f rd i s t r i b u t e su n d e rs a f eg u a r a n t e ed 锄p r e m i s e o n ek i n d a c h i e v i n ge x c e p tt h a tw a t e rh a r m i n gt h ec o m p r e h e n s i v eu t i l i z a t i o nr a t e se n c o u r a g i n ga w a t e rc o n s e r v a n c y i m p r o v i n gw a t e rr e s o u r c e t h eh i 曲l i m i t6 e l ds a t i s 匆i n gt h ep e o p l e l i f ea n d s o c i e t e c o n o m i c伊o v t h p u 印o s e r e s e r v o i rp r e v e m s n o o d o p t i m i z i n g d e v e l o p m e n to fe v e r yb r a n c hw h om a n a g e sas c h e m eb e i n gp r o p e ro rn o tb e i n gr e l a t e d t on a t i o n a le c o n o m y d i r e c t l y w i l lb r i n ga b o mv e d rc o n s i d e r a b l ee c o n o m i cr e t 啪sa n d s o c i a lb e n e f i t si ft h es c h e m ei sr e a s o n a b l ea n df e a s i b l e o nt h ec o n t r a 诮l lb r i n g e n o n i l o u sl o s st os o c i e t ye c o n o m i cg r o 叭h s o i th a sv e 巧i m p o r t a n tm e a n i n gt o 如n h e r p r e v e n to p t i m a lo p e r a t i o no fn o o dc o n t r o lr e s e o i r t h i sp a p e rf i r s ti n t r o d u c e st h er e s e a r c ha d v a n c eo fo p t i m a lo p e r a t i o no ff l o o dc o n t r o l r e s e n o i rh o m ea n da b r o a d a n dt h e nd e s c r i b ei t so p t i m i z a t i o nm e t h o d s 0 1 1 1t i l eb a s i so f s t u d y i n gr e s e r v o i ro p t i m i z e sp r i n c i p l e a c c o r d i n gt ot h em l e so fm a x i m a lf l o o dp e a l r e d u c t i o na i l dm i n i m a ln o o dd 锄a g ed u r a t i o n t h ep 印e rb u i l d u pam o d e lo fo p t i m a l o p e r a t i o no ff l o o dc o n t r o ls i n g l er e s e r v o i r a c c o r d i n gt ot h em i n i m a lm l e so ft h em a x n o wa i l dt h ew a t e rv o l u m eo v e rt h es a f e t yd i s c h a 唱ew h e nt h en o o dp a s s et h ep u b l i c n o o ds e c t i o n t h ep a p e rb u i l d u pam o d e lo fo p t i m a lo p e r a t i o no ff l o o dc o n 打o l m u l t i r e s e r v o i ri np a r a l l e l a n ds p e c i f i c a l l yf o rm et r a d i t i o no p t i m i z a t i o na l g o r i t h md e f i c i e n c yi nt h ef i e l do f c o n v e 唱e n c er a t ea i l dc o n v e 玛e n c ep r e c i s i o na n ds oo n t h ep a p e rp r o p o s ea d a p t i v e g e n e t i ca l g o r i t h i l lf o rt h em o d e lo fo p t i m a lo p e r a t i o no fn o o dc o n t r o lr e s e r v o i rb a s e d o nt h es t u d y i n go fg a a n d 印p l i e st h em e t h o dt ot w oa b o v e m e n t i o n e dm o d e l s t 酞i n gf o u rr e s e o i r so fh u a i h e 砌v e r b a s i na se x 锄p l e t h ep a p e ra p p l i e ss g aa 1 1 d a d a p t i v eg e n e t i ca l g o r i t l l i l lp r o p o s e di nt h ep a p e rt ot h em o d e lo fo p t i m a lo p e r a t i o no f f l o o dc o n t r o ls i n g l er e s e r v o i r a i l dt h em a x i m u mn o wh a sr e d u c e da i l dt h ep e a kr e d u c e d r a t eh a si m p r o v e rc o m p 跚dw i t ht h er e s e r v o i r sw o r k i n gf a l l i n go f o r i g i n a ls c h e d u l i n g 河海大学硕上学位论文 m l e t h er e s u l ti n d i c a t e st h a tg e n e t i ca l g o r i t h mc o n t r o lp a r a m e t e r su s e dt h em e t h o do f a d a p t i v eg e n e t i ca l g o r i t h mp r o p o s e dc a na u t o m a t i ca d ju s ta c c o r d i n gt od e 伊e eo f i n d i v i d u a ls u p e r i o ro ri n f e r i o r a j l dt h ep r o b l e mo fp o o rc o n v e 唱e n c ep e 墒m a n c ew h i c h s g ah a sh a sb e e nb e t t e rr e s o l v e d t h ep a p e ra p p l i e sa d a p t i v eg e n e t i ca l g o r i t h m p r o p o s e d t ot h em o d e lo fo p t i m a lo p e r a t i o no ff l o o dc o n t r o lm u l t i r e s e n o i ri n p a r a l l e l a n dt h em a xf l o wa n dt h ew a t e rv o l u m eo v e rt h es a f e t yd i s c h a 唱ew h e nt 1 1 e f l o o dp a s s et h ep u b l i cn o o ds e c t i o nh a v ea l lr e d u c e d a n dt h ee 艉c to ft h i s0 p t i m i z a t i o n i se v i d e n t k e yw o r d s m u l t i r e s e r v o i ri np a r a l l e l f 1 0 0 dc o n t r o l o p t i m a lc p e r a t i o n a d a p t i v eg e n e t i ca l g o r i t h m 学位论文独创性声明 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及 取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研究成果 与我一同工作的 同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意 如不实 本人负全部责任 论文作者 签名 二 姐2 8 年 月厂日 学位论文使用授权说明 河海大学 中国科学技术信息研究所 国家图书馆 中国学术期 刊 光盘版 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文 档的内容和纸质论文的内容相一致 除在保密期内的保密论文外 允 许论文被查阅和借阅 论文全部或部分内容的公布 包括刊登 授权河海 大学研究生院办理 论文作者 签名 茳翌猹蓬2 8 年 月 飞 h喂 论文作者 签名 江z 鱼墼2 0 0 8 年6 月 第一章绪论 1 1 论文选题背景 第一章绪论 在国民经济持续高速发展的今天 洪水灾害会对生产 生活 生态造成不可估 量的损失 洪水灾害有些属于暴雨洪灾 有些属于持续多雨高水位涝灾 有些属 于溃决洪灾等 但是不管是哪种洪涝灾害 虽然我们不能控制洪水的发生 可是 我们可以研究利用己建工程最大限度的削减洪峰 减少或者根除洪水灾害 绝大多数水库都兼有防洪和兴利的双重任务 水库防洪调度 2 就是利用水库 的蓄泄能力对入库洪水进行蓄泄控制 拦蓄洪水 削减洪峰 减少或根除洪水灾 害 使洪水造成的损失最小 水库防洪调度方案是否得当直接关系到国民经济各 部门的发展 如果方案切实合理可行 那么将带来十分可观的经济效益和社会效 益 反之 将给社会经济发展带来无法弥补的损失 因此 开展水库防洪优化调 度 已成为水库调度工作中的一项刻不容缓的任务 根据水库调度方案编制的过程中采用的分析计算方法的不同 通常把水库调度 分为常规调度和优化调度两类 常规调度是以调度规则为依据 利用丰富的水文 资料 选择典型的来水过程为代表年 取包络线绘制时历法调度图来指导水库运 行 原则上不考虑面临时段的来水预报 这种方法简单实用 但是缺少灵活性 经济效益比较差 优化调度是运用系统工程优化方法 将水库的调度问题处理成 系统工程的优化问题 用优化技术确定水库调度的最优决策 使水库获得最大的 调度效益 水库防洪优化调度一般分为单一水库防洪优化调度和水库群防洪优化调度两 类 3 水库群防洪优化调度又根据水库地理位置和水力联系的不同分为串联水库 群 并联水库群和混联水库群防洪优化调度 到目前为止有关水库群防洪优化调 度问题的研究基本上是围绕这三种水库群类型展开的 水库群防洪优化调度主要 利用的是各水库间的时空补偿 具体表现在两个方面 一是各水库来水不同步 根据各水库洪水发生的时差 以防洪控制点的防洪效益最大为目标 确定各水库 的蓄泄方案 另一方面表现为各水库空间分布不同 到防洪控制点的距离不等 以减轻或避免不同支流的洪峰叠加 提高防洪控制点的安全度为目标 确定调度 河海人学硕 j 学位论文 方案 水库防洪优化调度 满足下面两个条件就能达到最优1 4 j 第一是充分利用河道 下泄 即当洪水大于下游安全泄量时按下游安全泄量下泄 使水库拦蓄的成灾洪 水最小 当水库不能全部拦蓄成灾洪水时 使分洪量最小 对中小洪水 为了减 轻下游防洪负担 可采取分级放流 对单一防洪水库 上述的调度结果足最优的 第二是必须拦蓄成灾洪水 各库在蓄泄过程中 应充分利用河道调蓄作用 使动 用的防洪库容最小 换言之 使其能多腾出一部分库容多削减一些洪峰 减少一 些分洪量 提高防洪标准 对防洪水库群 除要满足第一个条件 还应满足第二 个条件 国内外学者对水库防洪优化调度的研究已经取得了一定的成就 5 j 对于单一水 库的防洪优化调度问题 以前一般应用动态规划法 借助电子计算机就可以解决 这一问题 但是这种方法的精度和计算速度相比于目前应用比较广的遗传算法 蚁群算法等智能优化算法要差得多 对于复杂和庞大的水库群系统优化调度问题 需要引入若干个状态变量 状态变量数目的增加 使每阶段状念的组合数目随状 态变量的数目呈指数关系增加 应用动态规划法 逐次优化法和线性优化法等方 法 已经不能适应库群防洪调度多目标之间 各水库之间侧重点实时动态变化的 要求 不能灵活地反映实时水情变化状况对防洪决策的影响 其求得的结果往往 并不是 最优 而遗传算法则可以相对比较好的解决这个问题 但是简单遗传算法又存在收敛速度慢 容易出现局部最优解 遗传控制参数难 以确定等问题 因此本文提出应用自适应遗传算法对水库防洪优化调度进行计算 1 2 水库防洪优化调度的研究进展 从系统工程理论出发 水库防洪优化调度的主要内容可概括为两个方面 建 立水库调度数学模型 包括系统输入模型 目标函数 约束方程 选择最优化 技术 4 1 确定合适的目标函数是水库防洪优化调度数学模型建立的重中之重 由于洪 灾损失的定量化存在较大困难 目前在进行水库防洪优化调度时 最大削峰准则 和最小成灾历时准则应用较为广泛 6 水库调度的优化算法目前主要有常规优化算法和智能优化算法 如图1 1 所 第一章绪论 不 线 性 优 化 算 法 优化算法 常规优化算法il 智能优化算法 动 态 优 化 算 法 非 线 性 优 化 算 法 大 系 统 分 解 协 调 逐 次 优 化 算 法 等 遗 传 算 法 入 工 神 经 网 络 法 蚁 群 算 法 模 糊 算 法 等 图l l 优化算法示意图 国外对水库优化调度的研究最早始于1 9 4 6 年 美国学者m a s e s 将优化概念引 入单一水库优化调度 而真正开始水库优化调度研究是1 9 5 5 年l i t t l 采用马氏过程 原理建立的水库调度随机动态规划模型 我国对于水库优化调度的研究与应用起 步相对较晚 2 0 世纪6 0 年代开始对单一水库优化调度进行研究 8 0 年代中期才 开始研究水库群的优化调度问题 近2 0 几年发展较快 很多学者在理论和实践上 进行了比较深入的研究 成绩显著 1 动态优化算法 动态优化法f 7 9 1 是在时间过程中 依次采取一系列最适当的决策 来求得整个 动态过程的最优化问题的解的动态过程寻优的一种基本的数学方法 适用动态优 化模型需要满足两个条件 最优化原理与无后效性 最优化原理是指无论过去的 状态和决策如何 对当前状态而言 余下的诸决策必须构成最优策略 无后效性 是指一旦某一阶段的状态已经确定 则此后过程的决策不再受此前各状态及决策 的影响 1 9 7 6 年 s c h u l t z 对某并联水库群建立了动态规划模型 以下游削峰量最大为 目标 但此模型只适用于各支流洪水同时发生的情况f l o 1 9 6 3 年 谭维炎 黄守信等根据动态规划与m a r k o v 过程理论 建立了一个长 期调节水电站水库的优化调度模型 并在狮子滩水电站的优化调度中得到应用 1 1 1 河海大学硕十学位论文 1 9 9 0 年 许自达编著的 优化技术在防洪中的应用 一书重点介绍了动态规划方 法在水库防洪调度中的应用 并建立了水库防洪优化调度模型及求解的方法 1 2 l 刘鑫卿 钟琦在进行发电水库群优化调度中 采用随机统计迭代算法 通过计算 最优余留效益函数 从而得出最优调度规则函数 其最优性与随机动态规划方法 相同1 1 3 j 动态规划法虽然广泛用于水库或水库群的优化调度问题 但随着状态数目的 增加 它往往伴随着所谓 维数灾 问题 尤其是当它用于库群联合调度时 维 数灾 问题尤为突出 2 线性优化算法 1 9 7 4 年y e h 等人用线性规划方法研究了水库最优化问题 以直接寻求最优运 行策略 1 4 1 9 7 9 年 h o u c k 提出了一个包含与未来径流预报有关的风险模型 该 模型以预报可靠性作为输入 是一个有机遇约束的线性规划模型 1 5 1 9 8 3 年 w a s i m i 以二次线性离散最优控制方法进行水库群系统实时预报与调度 该模型与 方法适合于中等洪水调度 16 1 1 9 9 8 年 马勇 高似春 陈惠源针对由混联水库群和多分蓄洪区组成的复杂 防洪系统 研究和建立了一个防洪系统联合运行的大规模线性规划模型 提出了 判断扒口分洪界点及其相应的分阶段解算的处理方法 17 1 线性优化模型主要有三个特剧1 8 l 每个模型都有n 个决策变量 决策变量的 一组值就表示一种方案 目标函数是决策变量的线性函数 求最大值或最小值 约束条件是决策变量的线性函数 线性优化发展的较为成熟 但是其要求目标函 数和约束条件都可以或近似可以表示为线性关系 正因为其理论特征的要求 针 对单库和库群调度中的非线性特征 线性优化已经很少运用 3 非线性算法与逐次优化算法 1 9 9 0 年 u n v e r 和m a y s 提出了一种实时防洪优化调度模型 该模型由防洪调 度的非线性规划方法和洪水演算的模拟方法组成1 1 9 1 9 9 6 年 樊尔兰 李怀恩等 建立了综合利用水库优化调度的动态确定性多目标非线性数学模型 并利用逐次 逼近 t h ep r o g r e s s i v ea p p r o a c ha l g o r i t h m p a a 的逐步优化法 t h ep r 0 舒e s s i v e o p t i m a l 时a l g o r i t h m p o a 即p a p o a 法求解模型的最优解集 2 0 1 1 9 8 8 年吴保生 陈惠源研究了多水库防洪系统优化问题 提出了并联防洪系 4 第一章绪论 统优化调度的多阶段逐次优化算法模型 该模型由三阶段子模型和跨阶段子模型 组成 2 1 1 9 9 3 年 都会康 周广安提出了水库群防洪调度的逐次优化方法 针对 防洪系统的具体问题 分析了并联水库群下泄流量与河道防洪控制点洪峰流量之 间的内在联系 根据 先泄 后蓄 再分洪 的一般洪水调度原则 提出了水库 群洪水调度模型及其逐次优化解法 该方法成功地实现了水库群之问以及水库群 与区间汇流的错峰 为洪水实时调度及防洪系统规划提供了一套简捷 高效而又 符合实际的模型和方法1 2 2 1 非线性优化方法是最普通 应用最广泛的数学优化方法之一 用于研究线性 或非线性函数在非线性或线性约束条件下的最优化问题 只是它优化的过程比较 慢而且需要大量的计算机内存 况且没有通用的求解方法和程序 因此它在水库 群防洪优化调度中的应用并不非常广泛 2 3 4 大系统分解协调法 大系统分解概念最早是由d a n t z i g 和w o l f e 19 6 0 年 在处理大型线性规划问 题时提出的 上世纪七十年代初 m e s a r o v i c 提出了大系统递阶控制理论 其基本 思想是将复杂的大系统分解为若干个简单的子系统 以实现系统局部最优化 2 4 大系统理论研究的就是按照整个系统的最优指标与各子系统之间的关系 优化各 子系统的指标 并以此控制子系统 使整个系统实现最优化 分解一协调 算法 是大系统设计和优化中一种很有效的方法 黄益芬提出在求解并联水库群优化调度问题时 采用系统分析方法 提出了 偏优损失系数法 将水库群视为一个大系统 其中各水库视为既相互独立又相互 制约的子系统 这个系统的优化分为两步来完成 首先将系统进行分解 对各子 系统进行优化 然后在子系统优化的基础上 在子系统间建立某种联系 按照总 的要求进行协调 最后得出系统最优解 2 5 1 9 8 8 年 胡振鹏 冯尚友提出了动态 大系统多目标递阶分析的分解一聚合方法 将水库群多年运行的整体优化问题分解 为按时间划分的一系列运行子系统 在各个子系统优化的基础上 将各水库提供 的年运行策略集合到上一系统 并由聚合模型描述和确定水库群的多年运行过程 和策略1 2 6 1 9 9 8 年 解建仓 田峰巍等结合黄河干流水库群 包括水电站 实例 建立了优化调度模型 采用大系统分解协调原理推导了模型的求解算法 2 7 j 大系统分解协调法 2 8 有两个特点 一是一种降维技术 将一个复杂 多维的大 河海大学硕i 学位论文 系统分解为变量少 维数少的予系统 二是一种迭代技术 各子系统通过各自优 化得到的结果 还要反复迭代计算互相协调 直到得到整个大系统的全局最优为 止 此方法可以避免 维数灾 的问题 简化系统 减少工作量 但是其缺点是 收敛性差 即使收敛也需要较长的计算时间 5 人工神经网络优化算法 随着电子计算机技术不断提高 智能优化算法的快速发展拓宽了水库优化调度 研究的视野 人工神经网络 或称为类神经网络 指的是模仿生物神经网络的资讯处理系 统 2 9 1 人工神经网络是生物神经元的简单模拟 它从外界环境或者其他神经元取 得资讯 同时加以非常简单的运算 输出其结果到外界环境或者其他人工神经元 1 9 4 3 年 美国心理学家麦卡洛克 w m c c u l l o c h 和数学家皮茨 w p i t t s 首先用 数学模型对神经系统中的神经元进行了理论建模 从此揭开了人工神经网络研究 的序幕 特别是1 9 8 2 年h o 曲e d 模型和1 9 8 5 年反向传播算法b p 的提出 更是大 大拓宽了人工神经网络的应用领域 人工神经网络在水资源领域的应用刚刚起步 它是模拟人脑思维与记忆的智 能化数学模型及算法系统 主要功能是自学习 通过对信息的学习反映信息之间 复杂的相关关系 水利系统完善的水情信息资料 使得利用神经网络技术预测未 知数据资料成为可能 也为优化调度提供了最直接 有效的基本信息 所以国内 外在神经网络的水资源领域应用方面做了大量的研究工作 已经在分类和识别问 题 预测预报问题 优化计算问题 专家系统研制与开发问题和其它一些问题上 取得了不错的成果 如胡铁松教授将人工神经网络应用到径流中长期预报 水库 较长期优化调度识别等方面 2 9 3 0 1 6 模糊算法 1 9 8 8 年陈守煜提出多目标 多阶段模糊优化模型的基本理论和解法 并建立 了新的水库防洪调度的优化方法 3 l 1 9 9 0 年 王本德编写的 水库模糊优化调度 重点介绍了水库模糊防洪优化调度的基本原理 基本概念和一些模型求解的要点 3 2 o 水库防洪优化调度的模糊算法起步相对较晚 其理论与实践的结合还需要进 一步的研究 6 第一章绪论 7 遗传算法 遗传算法 g e n e t i ca l g o r i t h m s 是美国密执安大学的著名科学家j h h o l l a n d 教授于2 0 世纪7 0 年代中期提出来的一种基于生物遗传和进化机制的适合于复杂 系统优化计算的自适应概率优化技术 3 3 1 遗传算法具有鲁棒性和全局搜索能力 尤其适于处理比较复杂的系统 鉴于水科学中存在大量复杂的非线性优化问题 国内外水科学界已经对g a 及其应用进行了探讨并同益显示出g a 的价值及对g a 进行深入研究的必要性 魏加华 张建立 3 4 3 5 1 研究利用遗传算法对非线性水污染控制系统规划进行优 化 他们首先分析了水污染控制系统规划常采用的最优化方法和模拟法相结合的 方法的优缺点 证明了传统算法不仅计算繁琐 而且很难保证得到的解全局最优 于是给出了一种求解非线性水污染控制系统规划的遗传算法 g a 应用g a 一次 性求出了污水系统规划的最佳方案 比常规的方法更为简洁 而且能保证得到的 解全局最优 1 9 9 7 年 王黎等人利用二进制遗传算法对水电站水库优化调度进行了研究 同时他把这一论理应用于四川省某大型水利枢纽的优化调度中 得到了较好的计 算效果 3 6 1 马光文 王黎 g a w a l t e r s 利用遗传算法对水库优化调度进行了研究 提出 了一种用浮点表示的遗传算法 该方法从众多个初始点开始迭代计算 应用交叉 和变异算子 可获得全局最优解 3 7 畅建霞等人采用十进制整数编码的遗传算法 对水电站水库优化调度进行了研究 得到了较好的计算结梨3 8 1 遗传算法在水问题中有着巨大的应用前景 但是 目前应用此方法对水库防 洪优化调度方面的研究相对较少 因此对遗传算法以及其在水库防洪优化调度方 面的应用还需要更深一步的研究 1 3 论文的研究内容 本文在广泛收集 整理国内外相关文献资料的基础上 建立水库防洪优化调 度模型 并且针对简单遗传算法存在的收敛性差的问题 提出应用自适应遗传算 法对水库防洪优化调度进行求解计算 并以淮河流域水库群防洪系统为实例 应 用自适应遗传算法对水库防洪优化调度模型计算 研究的主要内容包括 7 河海人学硕f 学位论文 第一章给出问题的研究背景 以及国内外研究进展 第二章阐述遗传算法的概念 原理 特点等 指出简堆遗传算法具有收敛速 度慢 容易出现 早熟 现象 控制参数难以确定等缺点 因此本文提出应用自 适应遗传算法进行水库防洪优化调度计算 第三章依照最大削峰和最短洪灾历时准则 建立单一水库防洪优化调度模型 以通过水库群削峰 错峰作用 减轻公共防洪控制断面洪水压力为目的 建立并 联水库群系统防洪优化调度模型 并应用自适应遗传算法对两模型进行优化计算 第四章以淮河流域梅山 鲇鱼山 宿鸭湖 响洪甸四水库为例 应用简单遗 传算法和自适应遗传算法对单一水库防洪优化调度模型计算求解 应用自适应遗 传算法对水库群防洪优化调度进行计算求解 得出并分析优化调度结果 第五章总结了全文的研究成果 并展望了今后继续研究的方向 8 第二幸自适应遗传算法研究 第二章自适应遗传算法研究 2 1 遗传算法概述 遗传算法 g e n e t i c a l g o r i t h m s f 3 9 4 2 1 是模拟生物在自然环境中的遗传和进化过 程而形成的一种自适应全局优化概率搜索算法 它最早由美国密执安大学的 h o l l a l l d 教授提出 起源于6 0 年代对自然和人工自适应系统的研究 基于对生物界中生物遗传与进化机理的模仿 很多学者设计了许多不同的编 码方法来表示问题的可行解 开发了许多种不同的遗传算子来模仿不同环境下的 生物遗传特性 这样 不同的编码方法和不同的遗传算子就构成了各种不同的遗 传算法 但这些遗传算法都有共同的特点 即通过对生物遗传和进化过程中的选 择 交叉 变异机理的模仿 来完成对问题最优解的自适应搜索过程 9 基于这个 共同特点 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 又称简单遗传算法 4 3 基本遗传算法只 使用选择算子 交叉算子和变异算子这三种基本遗传算子 其遗传进化操作过程 简单 容易理解 2 1 1 遗传算法的概念 遗传算法是模拟生物在自然环境中的遗传和进化过程 因此算法中要用到进 化论和遗传学的一些基本概念 4 4 4 5 1 染色体 又称个体 是遗传物质的主要载体 通常用一个串来表示 例如 染色体x l x 2 x n 其中x i 是串x 的基本单元 称为基因 2 种群 个体的集合 该集合内个体数称为群体的大小 3 选择算子 以一定的概率从种群中选择较适合环境的个体的操作 选择的 过程是一种基于适应度的优胜劣汰的过程 被选中的个体用于繁殖下一代 4 交叉算子 将两个染色体相同位置的基因以某一概率相互交换 形成两个 新的个体 5 变异算子 用来模拟生物在自然界的遗传环境中由于各种偶然因素引起基 9 河海人学硕t 学位论文 因突变 产生新的染色体而引入的算子 变异算子可以保证解空间的全局性 6 适应度 每个个体对环境的适应程度 2 1 2 遗传算法的原理 遗传算法是从代表问题可能潜在解集的一个种群丌始的 而种群则由经过基 因编码的一定数目的个体组成 编码采用二进制编码或浮点编码 初始群体产生 后 按照适者生存和优胜劣汰的原理 逐代演化产生出越来越好的近似解 在每 一代 根据问题域中个体的适应度大小进行组合交叉和变异 产生出代表新的解 集的种群 这个过程将导致种群像自然进化一样 后代种群比f 代更适应于环境 末代种群中的最优个体经过解码 可以作为问题近似最优解 3 3 l 4 6 4 7 1 遗传算法包括5 个基本要素 变量编码 设定初始种群 适应度函数与目标 函数的转换 遗传操作 设定控制参数 主要包括种群的大小 遗传算子的概率 等 这5 个要素构成了遗传算法的核心内容 2 1 3 遗传算法的步骤 应用选择算子 交叉算子 变异算子这三种算子的遗传算法的运算步骤如下 1 染色体编码 生成遗传算法的初始种群 d ej o n g 曾提出了两条操作性较强的实用编码原则 又称为编码规则 4 3 l 编码原则一 有意义积木块编码原则 应使用易于产生与所求题相关的 且具有低阶 短定义长度模式的编码方案 编码原则二 最小字符集编码原则 应使用能使问题得到自然表示或描 述的具有最小编码字符集的编码方案 目前遗传算法的编码方法可以分为三大类 二进制编码方法 浮点数编码方 法 符号编码方法 二进制编码方法是遗传算法中最常用的一种编码方法 由o 和1 组成的二进 制编码符号串 如 0 1 0 1 0 0 1 0 l o 二进制编码操作简单 交叉 变异等遗传操作 便于实现 所谓浮点数编码方法 3 3 1 是指个体的每个基因值用某一范围内的一个浮点数 来表示 个体的编码长度等于其决策变量的个数 因为这种编码方法使用的是决 l o 第二章自适应遗传算法研究 策变量的真实值 所以浮点数编码方法也叫做真值编码方法 浮点数编码比较适 合决策变量的范围较大 精度要求较高的遗传算法 符号编码方法 3 4 1 是指个体染色体编码串中的基因值取自一个无数值含义 而 只有代码含义的符号集 这个符号集可以是一个字母表 如 a b c d 也可以是一个数字序号表 如 1 2 3 4 还可以是一个代码表 如 a 1 a 2 a 3 a 4 j 等等 考虑到具体情况 本文采用最常用的二进制编码方法 2 解码 选择相应的解码方法 将编码串转换成数值 进行下一步操作 3 将目标函数转换成适应度函数 确定个体适应度的评价方法 在遗传算法中 以个体适应度的大小来确定该个体被遗传到下一代群体中的 概率 4 选择运算 按照优胜劣汰的原则 以一定的概率选择适应度较大的个体进入到下一代 5 交叉运算 将两个个体以一定的交叉概率按照某种方式相互交换部分基因 来形成两个 新的个体 6 变异运算 如果只考虑交叉运算来实现进化 有些近似于近亲繁殖 因为种群中染色体 的数量是有限的 经过若干代的选择和交叉运算以后 源于一个祖先的较好的个 体逐渐充斥整个种群 结果过早收敛 得到局部最优解 因此效仿生物界的生物 变异现象 对遗传算法进行变异操作 对于二进制编码的个体组成的种群 以一 定的小概率 实现基因编码的翻转 形成具有新特征的个体 7 收敛性判断 当最优个体的适应度值与上一代最优个体的适应度值相比不再上升时 算法 的迭代过程收敛 运算结束 否则 经过选择 交叉 变异运算形成新一代种群 来取代上一代 返回步骤2 河海人学硕 学位论文 2 1 4 遗传算法的特点 遗传算法与其他一些优化算法相比 它主要有下述几个特点 4 8 j 1 遗传算法以决策变量的编码作为运算对象 传统的优化算法往往直接利用 决策变量的实际值本身来进行优化计算 但遗传算法不是直接以决策变量的值 而是以决策变量的某种形式的编码为运算对象 这种对决策变量的编码处理方式 使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念 可以模仿生 物界中生物的遗传和进化等机理 也使得我们可以方便地应用遗传操作算子 特 别是对一些无数值概念或很难有数值概念 而只有代码概念的优化问题 编码处 理方式更显示出了其独特的优越性 2 遗传算法直接以目标函数值作为搜索信息 传统的优化算法不仅需要利用 目标函数值 而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索 方向 而遗传算法仅使用由目标函数值变换来的适应度函数值 就可确定进一步 的搜索方向和搜索范围 无需目标函数的导数值等其他一些辅助信息 这个特性 对很多目标函数是无法或很难求导数的函数 或导数不存在的函数的优化问题 以及组合优化问题等 应用遗传算法时就显得比较方便 因为它避开了函数求导 这个障碍 再者 直接利用目标函数值或个体适应度 也可使得我们可以把搜索 范围集中到适应度较高的部分搜索空间中 从而提高了搜索效率 3 遗传算法同时使用多个搜索点的搜索信息 传统的优化算法往往是从解空 间中的一个初始点开始最优解的迭代搜索过程 单个搜索点所提供的搜索信息毕 竟不多 所以搜索效率不高 有时甚至使搜索过程陷于局部最优解而停滞不前 遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程 而不是从 一个单一的个体开始搜索 对这个群体所进行的选择 交叉 变异等运算 产生 出的乃是新一代的群体 在这之中包括了很多群体信息 这些信息可以避免搜索 一些不必搜索的点 所以实际上相当于搜索了更多的点 这是遗传算法所特有的 一种隐含并行性 4 遗传算法使用概率搜索技术 很多传统的优化算法往往使用的是确定性的 搜索方法 一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系 这 种确定性往往也有可能使得搜索永远达不到最优点 因而也限制了算法的应用范 围 而遗传算法属于一种自适应概率搜索技术 其选择 交叉 变异等运算都是 1 2 第二章自适应遗传算法研究 以一种概率的方式来进行的 从而增加了其搜索过程的灵活性 虽然这种概率特 性也会使群体中产生一些适应度不高的个体 但随着进化过程的进行 新的群体 中总会更多地产生出许多优良的个体 实践和理论都己证明了在一定条件下遗传 算法总是以概率l 收敛于问题的最优解 当然 交叉概率和变异概率等参数也会 影响算法的搜索效果和搜索效率 所以如何选择遗传算法的参数在其应用中是一 个比较重要的问题 而另一方面 与其他一些算法相比 遗传算法的鲁棒性又会 使得参数对其搜索效果的影响会尽可能地低 2 1 5 简单遗传算法存在的问题 简单遗传算法主要存在两个问题 一是算法的收敛速度太慢 二是算法容易 产生早熟现象 简单遗传算法的局部搜索能力不强 影响算法搜索性能的因素主 要包括初始种群 编码方式 遗传算子和控制参数等多方面因素 简单遗传算法 由于自身固有的缺陷 通常在优化过程中收敛速度较慢 而且算法的稳定性不高 不能保证收敛于全局最优解 4 9 而产生早熟现象一方面是由于目标函数的特性造 成的 对于单峰函数的优化问题可以比较有效地解决 而对于多峰复杂函数的优 化问题容易发生早熟现象 另一方面是由于算法的设计不当造成的 为此 许多学者对简单遗传算法提出了各种各样的改进 比如针对最基本的 二进制编码提出浮点数编码 格雷码编码等 针对控制参数在进化过程中不变的 情况提出自适应遗传算法等 2 2自适应遗传算法 2 2 1自适应遗传算法的产生 简单遗传算法采用事先确定参数固定不变的方法 在优化过程中的效果较差 尤其是多峰值复杂优化问题的求解过程 很容易陷入局部最优解 并且无法满足 在遗传过程中交叉概率和变异概率等参数动态的 变化的要求 因而无法比较客 观地反映种群中个体的个性化要求 从生物进化的角度看 这种做法虽然考虑到 了种群对环境的适应能力的模拟 但是却忽略了种群跟随环境进化时 个体发育 和遗传行为 如交配频率 交配范围 变异程度和繁殖数量等随之变化的自适应 f l 海入学硕i 学位论文 特性 这是影响简单遗传算法等控制参数不变的算法的性能和效率的根本原因 1 5 0 5 1 1 o 在加快遗传算法收敛速度的同时 防止早熟现象是遗传算法中一个较难解决 的问题 参数 种群大小 交叉概率和变异概率等 的选择关系到遗传算法的收 敛性 稳定性和计算速度等诸多因素 而目前对于控制参数的设置还缺少合理的 理论指导 通常 一种遗传算法设计完成后 应用时需设定的控制参数主要有 种群大 小 交叉概率 变异概率等 控制参数的不同选取会对遗传算法的性能产生很大 的影响 这些参数设定的合理与否关系到算法寻优计算的成败1 5 2 1 对于遗传算法控制参数中的交叉概率和变异概率的选择是影响算法性能的关 键 它们的好坏直接影响遗传算法的收敛性 由于简单遗传算法中交叉概率和变 异概率取固定值 交叉概率与变异概率不能反映进化的过程 从而容易出现早熟 或随机漫游的现象 对于交叉概率 若交叉概率太大 新个体产生速度就越快 适应度高的个体被破坏的可能性也就越高 若交叉概率太小 就不易产生新个体 算法容易陷入停滞状态 对于变异概率 若变异概率取值太大 遗传算法就变成 了纯粹的随机搜索算法 若变异概率太小 也不易产生新个体 5 3 5 4 1 种群大小在遗传算法整个寻优过程中扮演着重要的角色 因为它规定了搜索 样本个体的数目 虽然种群数量较小可以提高遗传算法的收敛速度 减少了有效 基因缺失的概率 但是却降低了种群的多样性 影响了对最优解的搜索 而且有 可能导致算法出现早熟现象 种群数量太大会影响整体的编码时间 降低算法效 率f 5 5 5 6 1 遗传算法运行初期 适应度相对较低的个体比较集中 若采用较小的交叉概 率和变异概率 种群很难产生出优秀新个体 遗传算法运行后期 适应度相对较 高的个体比较集中 倘若采用较大的交叉概率和变异概率 容易破坏优良个体 使算法陷入局部收敛 要为某个特定的优化问题设置好交叉概率和变异概率 算 法需要经过反复地试验且难以丰富种群中优良解的多样性 因此 产生了使交叉 概率和变异概率能够随着适应度自动改变的自适应遗传算法 5 7 1 1 4 河海人学硕士学位论文 交叉概率只和变异概率匕增大 而当种群适应度比较分散时 交叉概率只和变异 概率r 减小 同时 对于适应度值高于种群平均适应度值的个体 取较低的交叉 概率只和变异概率巴 使该解得以保护进入下一代 而低于平均适应度值的个体 取较高的交叉概率只和变异概率匕 使该解被淘汰掉 5 9 1 根据s r i n i v a s 等提出的自适应遗传算法 交叉概率只和变异概率匕随着个体 的适应度在种群平均适应度和最大适应度之间进行线性调整 当适应度越接近最 大适应度时 交叉概率只和变异概率匕越小 当适应度值接近或等于最大适应度 值时的个体 交叉概率只和变异概率己接近或等于零 这种自适应遗传算法的缺点是 自适应遗传算法在进化初期并不理想 因为 种群在进化初期时 较优个体几乎处于一种不发生变化的状态 而此时的优良个 体不一定是全局最优解 这容易出现局部收敛 5 们 任子武等人在s r i n i v a s 等提出的自适应遗传算法的基础上 提出一种改进的自 适应遗传算法 i m p r o v e da d a p t i v eg e n e t i ca 1 9 0 r i t h