（应用数学专业论文）煤化工多联产系统优化的遗传算法研究.pdf

论文题目：煤化工多联产系统优化的遗传算法研究 专业：应用数学 硕士生：王兮璐( 签名) 指导教师：曹根牛( 签名) 李建伟( 签名) 摘要 王恰倦 遗传算法作为一种新型优化算法，由于具有简单、易操作、使用方便、并行信息处 理等特点，己经成为人们解决一些复杂问题的新思路和新方法，广泛应用于许多领域。 但其在理论和应用方法上仍存在不足和缺陷，例如存在容易产生早熟现象、局部寻优能 力较差、收敛速度较慢、效率相对较低等问题，影响了其进一步的应用。本文介绍了常 规遗传算法的原理和方法，并围绕遗传算法的收敛性与运行效率对遗传算法进行了改 进。主要工作如下： ( 1 ) 对遗传算法的基本原理和实现技术进行了概括和总结。并对遗传算法的各要 素( 编码、适应度函数、遗传算子、和参数选择等) 进行了分析。 ( 2 ) 在对遗传算法的原理、流程、遗传算子及相关理论进行了较深入的研究和分 析的基础上，对算法实行了改进，提出一种新的自适应遗传算法，该算法将欧氏距离引 入初始群体的产生和自适应交叉、变异算子。 ( 3 ) 使用改进的自适应遗传算法对煤化工多联产系统的集成优化问题进行了研究， 完成了对多联产系统的控制策略，从物料消耗、能量衡算及经济效益三个方面进行协同 优化，达到整个系统的资源利用、总体效益的最大化，从而寻求到合理的煤化工多联产 方式。计算结果表明了所设计的算法具有优良的品质。 关键词：自适应遗传算法；煤炭转化；多联产；优化 研究类型：应用研究 s u b j e c t：s t u d yo ng e n e t i ca l g o r i t h m so fc o a lc o p r o d u c t i o nc h e m i c a l i n d u s t r y s p e c i a l t y ：a p p l i e dm a t h e m a t i c s n a m e ：、n gx i i u i n s t r u c t o r ：c a og e n n i u l ij i a n w e i a b s t r a c t ( s i g n a t u r e ) ( s i g n a t ur e ) ( s i g n a t u r e ) a san e w o p t i m i z a t i o nm e m o d ，g e n e t i ca l g o r i t h m sw 鹤w i d e l yu s e di nt h eo p t i m i z a t i o n s o f m a i l y j f i e l d s o 谢n g t ot ：h ef e a n 鹏so f s i m p l i c i t y ，e 嬲i l yh a n d i n g 肌d p a r a l l e l p r o c e s s i n g h o 、v e v e rg e n e t i ca l g o r i t h m st l l e o r yi sn o tp e r f e c t ，s u c h 嬲t ：h e r ee x i s tt h ep r o b l e m s o fe a s i l yc r e a t i n ge a r l i n e s sa i l db a da b i l 毋i i ll o c a lo p t i m a l ，e t c i i lt h i sp 印e r ，t i l ee l e i n e n t a d r t l l e o 巧觚dm e t h o d so fg e n e t i ca j g o r i n u n si si n 仃o d u c e d s o m ei l n p r o v e m e n to fg e n e t i c a l g o d t h m so nt l l ea s 曲g e n c y 龇l ds e a r c l l i n ge 伍c i e n c ya r ep r e s e n t e d t h em a 证c o n t e n to ft h i s t l l e s i si n c l u d e st l l ef o l l o 丽n g ： ( 1 ) t 1 1 en l e o 巧a i l d 删i z a t i o no fg e n e t i c 甜g o r i 她si sa 1 1 a l y z e d 觚ds l l i l l m 撕z e d t h e f a c t o r so fg e n e t i c2 l l g o r i 岫sa r ea n a l y z e ds y n t h e t i c a l l yt l l o s e i n c l u d i n gc o d i n gm e t h o d ， g e n e t i co p e r a t o r ，f i t l l e s se v a l u a t em 州的da i l d l ep a r a m e t e r so fg e n e t i ca l g o r i 让u n s ，s o m e i n d e x e sf o re s t i i i l a t i n gm ec 印a b i l i t ) ro fg e n e t i ca l g o r i m m sa r eg i v e n ( 2 ) g e n e t i ca l g o r i t l l i i l si s 丽d e l yu s e d 嬲al 【i n do fg l o b a lo p t i m i z a t i o nm e t h o d i i lo r d e r t oa c t l i e v et t l eb a l a n c eb e t v v e e ni t s c o n v e p 萨n c es p e e da i l de 伍c i e n c y ，a 1 1i n l l ) r o v e da d a p t i v e g e i l e t i ca l g o r i 恤si sb r o u g h tf o r 眦同i nt m sp a p e r e u c l i d e a i ld i s t a n c eo fe a c hi n d i v i d u a li s c o n s i d e r e di 1 1t l l ea d a p t i v eo p e r a _ t o r so fc r o s s o v e r ，m u t a t i o na n dn l em e l o dt o g e tt ：h ef i r s t g e n e r a t i o n ( 3 ) u s i n gt h eh p r 0 v e da d a p t i v eg e n e t i ca l g o r i t l l i i l si nt h e 证t e 掣铽e dc o p r o d u c t i o n s y s t e mo fc o a l t h en e ws y s t e mc a nr e a l i z et h eg r a d e du t i l i z a t i o no fc o a lr e s o u r c ev a l u eb yt l ：i e o p t i l l l 呦i n t e 鲫i o no f s e v e m lc o a lc o n v e r s i o nt e c l l 王1 0 l o 西e s ，s o 嬲t 0r e a l i z et h em a ) ( i m i z a t i o n o fv a l u ei n l p r o v e m e n t ，u t i l i z a t i o ne m c i e n c ya i l de c o n o “cb e n e f i td u r i n gt h eu t i l i z a t i o no f c o a lr e s o u r c e s t h es i m u l a t i o nt e s t sa r em a d ea n dt h er e s u l t sd e m o n s t r a t et h e e m c i e r l c yo f t h e a b o v em f 吐h o d s k e y w o r d s ：a u t o m a t i c a l l ya d a p t i v eg e n “ca l g o r i m m s c o p r o d u c t i o nm u l t i - g e n e r a t i o n o p t i m i z a t i o n t h e s i s ：a p p l i e dr e s e a r c h 要种技太学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：王恰璐日期：2 口口罗、石、歹 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：王恰诒良 1 绪论 1 绪论 遗传算法( g e i l e t i ca l g o r i t h m s g a ) ，是一种模拟自然界生物进化过程的全局随机搜 索算法，由美国m i c l l i g 锄大学的h o l l a l l d 教授于1 9 7 5 年提出。该算法是一类借鉴生物 晃自然选择和自然遗传机制的随机搜索算法，它将问题的求解表示成“染色体”的适者生 存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛 到“最适应环境”的个体，从而求得问题的最优解或满意解。它是一种通用的优化算法， 其编码技术和遗传操作比较简单，优化不受限制性条件的约束。 作为一种新的全局优化搜索算法，遗传算法几乎不需要所求问题的任何信息而只需 要目标函数的信息，不受搜索空间是否连续或可微的限制就可找到最优解。因其具有简 单、易操作、并行信息处理等特点，遗传算法已被广泛地应用于计算科学、模式识别、 工程设计、自动控制、故障诊断和社会科学等领域，并已取得显著成果。 1 1 遗传算法的基本原理 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生方法，它模拟了基 因重组与进化的自然过程，把待解决问题的参数编成二进制码或十进制码也可编程其它 进制码基因，若干基因组成一个染色体个体，许多染色体进行类似于自然选择、配对交 叉和变异的运算，经过多次重复迭代即世代遗传直至得到最后的优化结果。习惯上，适 应度值越大，表示解的质量越好。对于求解最小值问题，可通过变换转化为求解最大值 问题。遗传算法以群体为基础，能同时从不同点获得多个极值，因此不易陷入局部最优。 遗传算法是对问题变量的编码集进行操作，而不是对变量本身操作，有效地避免了对变 量的微分操作运算。遗传算法只是利用目标函数来区别群体中个体的好坏而不必对其进 行过多的附加操作。 一般认为，遗传算法有五个基本组成部分：问题的解的遗传表示、创建解的初始种 群的方法、根据个体适应度值对其进行优劣判定的评价函数、用来改变复制过程中产生 的子个体遗传组成的遗传算子、遗传算法的参数值。 遗传算法维持由一群个体组成的种群尸( f ) ( ，代表遗传代数) 。每一个体均代表问题 的一个潜在解。每一个体都被评价优劣并得到其适应值。某些个体要经历称作遗传操作 的随机变换，并由此产生新的个体。新产生的个体( 称作后代( o 低p r i n g ) c ( f ) ) 继续被 评价优劣。从父代种群和子代种群中选择比较优秀的个体就形成了新的种群。在若干代 以后，算法收敛到一个最优个体，该个体很有可能代表着问题的最优或次优解。 西安科技大学硕士学位论文 1 2 遗传算法的特点【9 】【l o l 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，它模拟基因 重组与进化的自然过程，利用某种编码技术，把待解决问题的参数集编码成遗传算法的 染色体，通过作用于染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法 通过有组织、随机的信息交换来重新组合那些适应性强的串，产生新的串群体，通过多 次重复迭代( 即世代遗传) 直至得到最优染色体串。 与传统优化算法不同，遗传算法不依赖于问题的梯度信息，而是通过模拟自然进化 过程来搜索最优解。遗传算法以群体为基础( 不是以单点搜索为基础) ，能同时从不同点 获得多个极值，因此该方法不易陷入局部最优；由于遗传算法是对问题变量的编码集进 行操作，而不是问题变量本身，这样可以有效地避免了对变量的微分操作运算。遗传算 法只是利用目标函数来区别群体中个体性能好坏而不必对其进行过多的附加操作。而大 多数古典优化算法是基于一个单一度量函数( 评估函数) 的梯度或较高次统计，以产生 一个确定性的试验解序列。由于遗传算法的本质特点，使得遗传算法能够解决复杂问题 的优化求解，例如具有混合离散变量非线性约束的给水管网优化设计的计算问题。此外， 遗传算法具有并行性特点，能同时在多个处理器上进行并行计算，并且各子种群之间可 以按照一定的规则交换个体，避免早熟现象和增加解的精度。 遗传算法与传统优化算法相比，具有如下优点： ( 1 ) 遗传算法作用在参数集的编码上，而不是参数本身。通过对变量的编码进行 群体的搜索。 ( 2 ) 遗传算法作用在解空间的点群上而不是在一个单点上进行寻优，搜索速度较 快。它从多个点出发，通过这些点内部结构的调整和重组来形成新的点，因而每次都将 提供多个解，这对多目标搜索或需要多个近似解作为参照的情况下是非常有用的。 ( 3 ) 遗传算法在搜索中利用适应度值或目标函数值信息，无需导数或其它确定性 规则，并且它不要求目标函数的连续性、可微性以及凸性。 ( 4 ) 遗传算法利用概率转移规则，而不是确定性规则，在搜索过程中不易陷入局部最优， 即使定义的适应度函数是不连续的、非规则的或有噪声的，也能以很大的概率找到全局最优解。 ( 5 ) 遗传算法具有高度的鲁棒性及并行性。遗传算法的鲁棒性是指在不同的条件 和环境下算法的适应性和有效性。遗传算法的并行性表现在两个方面：一是计算内在的 并行性，即遗传算法本身非常适合大规模问题；二是遗传算法的内含并行性，由于遗传 算法采用种群的方式组织搜索，从而它可以同时搜索解空间内的多个区域，并相互交流 信息。 ( 6 ) 遗传算法具有可扩展性，易于同别的技术结合。 遗传算法在具有这些优点的同时，也存在一定的缺点，主要表现在以下三个方面 2 1 绪论 i l l j 【1 2 】： ( 1 ) 对某些问题，遗传算法求解速度太慢。遗传算法是一种随机搜索算法，当然 它是有导向的随机搜索，但在解决具体问题时，影响算法的几种参数的取值很难确定其 最优值及最优组合，往往要根据经验和试验来自行确定。另外，对不同的问题要选择合 适的编码方案，不同的编码方案也会影响算法的执行效率。所有这些，如果处理不当， 都会造成遗传算法的搜索效率低下。 ( 2 ) 遗传算法容易产生早熟现象。早熟收敛是遗传算法的另一个重要问题。通过 染色体的交叉和变异，种群已经很难产生优于父本的子代个体时就会发生早熟。在均匀 种群中经常发生这种情况，所有标准形式的交叉只是简单地重复产生当前的亲本，进一 步的优化将完全依赖于位的变异，而且可能非常缓慢。在遗传算法中，经常会遇到早熟 收敛，伴随着交叉和选择的作用，观察到的最优个体就会以指数速度繁殖，该个体将很 快占据种群的大部分。 ( 3 ) 随着问题规模的扩大，遗传算法的性能降低。问题规模扩大，需要较大的种 群规模以得到满意解。由于遗传算法主要依赖于交叉操作，若交叉概率太小，可能使染 色体失去重要的信息导致未成熟收敛，使遗传算法找不到最优解。为克服这个缺点，采 用较大的种群以包括更多的信息，但由于计算负担较大，收敛速度较慢。在避免未成熟 收敛的问题上人们提出了多种改进措施，如采用适应度值排序选择、改变遗传操作、约 束复配、根据基因丢失变换适应值、降低相似个体的适应值、调整变异概率或插入新的 基因、当种群规模很大时用并行遗传算法或把遗传算法与其它方法结合等。 1 3 煤化工多联产系统 中国一次能源以煤为主且将长期不变已是不争的事实。煤炭资源的开发与利用带来 了严重的资源与环境问题并已经成为国民经济可持续发展的制约因素。长期以来各工业 部门( 发电、动力、石化、化工，冶金等) 所管辖领域之间分隔，都在本行业内单独寻 求最优解，实际上这些局部最优并不一定是整体最优。而开展煤的多联产技术，可充分 实现煤炭资源的合理、高效、洁净、经济利用，从而达到社会、经济、能源、环境的协 调发展。 在有关专家的大力倡导下，以煤气化技术为“龙头”的“多联产”煤炭转化系统越来越 引起人们的普遍关注。多联产系统正是从整体最优角度、跨越行业界限所提出的一种高 度灵活的资源、能源、环境一体化系统。因此，多联产系统通过对多种煤炭转化技术的 优化集成，可以实现从煤炭到各种产品的煤炭资源利用过程效率的尽可能最大化。初步 估算表明，热、电、甲醇、合成气四联供系统与分供情况相比，煤炭消耗量有可降低 2 2 1 6 。煤的多联产就是指将以煤气化技术为“龙头”的多种煤炭转化技术通过优化组合 集成在一起，以同时获得多种高附加值的化工产品( 包括脂肪烃和芳香烃) 和多种洁净的 3 西安科技大学硕士学位论文 二次能源( 气体燃料、液体燃料、电等) 【1 1 1 ，并在系统内部将污染源转化成可利用的产品。 其基本思路可用图1 表达。 空气 图1 1 煤化工多联产系统 f i g u r el - lf l o ws h e e to f c o p r o d u c t i o ni n t e 舯t i o ns y s t e m 煤化工多联产系统是一个过程系统综合问题，它通常具有多峰、奇异的特性，对于这 样一个复杂过程，采用建立数学模型然后用传统的优化算法进行优化是比较困难的，而 采用遗传算法可以有效的解决这个问题。 近几年，遗传算法在化学领域中也有了广泛的应用【l9 】1 2 l 】：( 1 ) 在分析化学中，遗 传算法对于多变量分析、图谱解析、参数拟合等问题的解决非常有效。l u c a s i u s 等报道 了将遗传算法用于u v 法测定四种i 斟a 核苷酸时的波长选择；w e t h r e n s 等成功地将遗传 算法用于蛋白质二核磁共振谱的解析，而且遗传算法在近红外光谱的分析中也得到了应 用。( 2 ) 在生物化学领域中：用于生物大分子的结构预测。用于结构搜索。用于 药物分子设计。( 3 ) 在组合化学中，它是近些年新兴起来的一门学科，它对于寻找药物 先导化合物和对现有先导化合物进行结构改造有着积极的作用。组合化学能通过一定的 固相有机合成实验或特定的液相合成方法迅速合成数目巨大的化合物库。s i n 曲等研究 了以遗传算法为指导合成高活性六肽的方法。因共有2 0 种氨基酸，故共有62 0 种可能， 要全部合成是不可能的。遗传算法的引入大大减少了合成化合物的数量，对化学合成活 性先导物有着指导意义【1 9 】。( 4 ) 萃取过程优化【2 1 】因为萃取过程中，各组分的物料平衡 4 1 绪论 随着组分的增加而呈现高度的非线性，以致于难以用经典的算法进行优化，所以用遗传 算法处理有着较大的优势。0 m o r i 等用遗传算法对使用后的核燃料的溶剂萃取过程的优 化进行了研究，进行了隔离过程的变量优化和消除核污染协同过程的多目标优化，作者 使用了经典的单点杂交的遗传算法就获得较为理想的结果。 除此之外，遗传算法还广泛地应用于同分异构体的研究、动力学参数辨识、换热器 设计、有机分子二维图形显示及定量构效关系研究以及材料化学等方面。而且遗传算 法作为一种有效的全局搜索策略，已经被广泛应用于分子簇，原子簇结构的优化问题中。 以上研究都表明采用遗传算法是有效的，而且比以往常用的方法有很大的改进之处。 遗传算法目前在化学上应用较多，在化工中的应用这两年才刚刚开始。经典的化工 过程大多由一些设计标准的化工单元的序列组成。从这种意义上说，遗传算法应用在这 一序列上应该是比较方便的。另外，大多的化工过程存在一个成本或物料的优化问题， 因此遗传算法在化工中的应用是很有前景的。 由于煤化工多联产是一个非常复杂的系统工程，其实质是通过以煤气化技术为“龙 头”的多种煤炭转化技术的优化集成，实现煤炭资源价值的梯级利用，从而达到煤炭资 源的价值提升、利用效率和经济效益的最大化，同时做到煤炭利用过程对环境最友好的 利用。对于煤化工多联产系统这样一个复杂的过程，采用经典的优化算法进行优化是相 当困难的，目前虽然大多数采用了循环经济分析方法，但多停留在概念阶段，还无法彻 底量化地评价不同利用途径之间的优劣。因此本文将在利用化工技术经济分析对各个模 块进行量化优化的基础上，利用遗传算法良好的结构优化能力以及全局搜索的特征，通 过对不同模块的优化集成，对多联产系统进行多目标优化，以期达到多联产系统的资源 利用、总体效益的最大化，对煤化工项目的方案决策进行指导。 1 4 本文的主要工作及安排 本文主要是利用实际工厂生产参数及各个工段的工艺参数，运用遗传算法良好的结 构优化能力以及全局搜索的特征，对煤化工多联产系统进行多目标优化，设计出一个适 当的遗传算法求解方案，也就是要具体确定遗传算法中的五个基本要素，即编码方案的 确定、适应度函数的设计、遗传操作设计( 选择、交叉、变异算子的确定) 、算法参数 的选取( 主要包括群体规模以及执行遗传操作的概率等) 及算法终止条件的确定。进而 对煤气化、甲醇、和电的生产等小系统和整系统进行控制策略，通过对不同模块的优化 集成，以期达到整个系统的资源利用、总体生产效益的最大化，同时做到煤炭利用过程 对环境最友好。本文的主要工作分为下三部分： ( 1 ) 对遗传算法的基本原理和实现技术进行了概括和总结。对遗传算法的各要素( 编 码、适应度函数、遗传算子、和参数选择等) 进行了分析。 ( 2 ) 在对遗传算法的原理、流程、遗传算子及相关理论进行了较深入学习的基础上， 5 西安科技大学硕士学位论文 对算法实行了改进，提出一种新的自适应遗传算法，该算法将欧氏距离成功引入初始群 体的产生和自适应交叉、变异算子。 ( 3 ) 对于煤化工多联产系统的多目标优化，设计出一个适当的遗传算法求解方案， 确定遗传算法中的五个基本要素，即确定编码方案、设计相应的适应度函数、设计遗传 操作( 选择、交叉、变异算子的确定) 、选取算法参数( 群体规模及执行遗传操作的概 率等) 以及确定该算法的终止条件。进而对多联产系统进行控制策略，从物料消耗、能 量衡算及经济效益三个方面进行协同优化，以期达到整个系统的资源利用、总体生产效 益的最大化，从而寻求到最合理的煤化工多联产方式。计算结果表明了所设计的算法具 有优良的品质。 全文共6 章： 第一章主要概述了遗传算法与煤化工多联产系统的研究背景、研究意义及主要内 容。 第二章介绍了基本遗传算法的思想、特点、原理、应用及其实现技术等问题。 第三章主要介绍了遗传算法的数学基础，对模式定理、积木块假设、遗传算法的 欺骗问题和遗传算法的收敛性进行了详细的分析。 第四章在对遗传算法的原理、流程、遗传算子及相关理论进行了较深入学习的基 础上，对算法进行了改进，提出一种新的自适应遗传算法，该算法将欧氏距离引入初始 群体的产生和自适应交叉、变异算子，并对这种改进的自适应遗传算法进行了测试。 第五章使用改进的自适应遗传算法对煤化工多联产系统的集成优化问题进行了研 究，完成了对多联产系统的控制策略，从物料消耗、能量衡算及经济效益等方面进行协 同优化，达到整个系统的资源利用、总体生产效益的最大化，从而寻求到最合理的煤化 工多联产方式。计算结果表明了所设计的算法具有优良的品质。 第六章总结论文的主要工作，以及论文进一步工作的展望。 6 2 基本遗传算法及其实现技术 2 基本遗传算法及其实现技术 2 1 基本遗传算法 遗传算法是从代表问题可能潜在解集的一个可行解开始，按照适者生存和优胜劣汰 的原理，逐代演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度 的大小挑选个体，并借助于自然遗传学的遗传算子进行杂交和变异，产生出代表新的解 集的种群，末代种群的最优个体经过解码，可作为问题的近似最优解。 2 1 1 算法描述 对于一个求函数最小值的优化问题( 求函数最大值也是如此) ，一般可描述为下述 数学规划模型： in 血( x ) 卜麓5 在上式中，x 为决策变量，厂( x ) 为目标函数，后两式为约束条件，u 为基本空间，满 足约束条件的解x 称为可行解，集合r 表示由所有满足约束条件的解组成的一个集合， 称为可行解集合。 求函数厂( x ) 极小值的的遗传算法的主要过程如下： ( 1 ) 编码表示给出定义域r 上点x 的编码形式，每个x 表示一个刀维实向量， 其中每个分量都可以用一个后进制串表示，从而一个点x 的编码由刀个霓进制串构成。 ( 2 ) 初始化选择一个整数作为群体的规模参数，然后从尺上随机地选取个 点x ( f ，0 ) ，i 1 ，这些点组成初始群体尸( 0 ) = x ( 1 ，0 ) ，x ( ，0 ) ) 的过程称为初始化 过程。 ( 3 ) 适应度值计算群体尸( 七) 中每个个体x ( f ，后) 的适应度值厂( x ( f ，七) ) ，其中七表 示代数，初始代七= o 。 ( 4 ) 选择策略对每个个体x ( f ，七) ，计算生存概率，然后设计一个随机选择策 略，使得每个个体x ( f ，七) 被选择进行繁殖的概率为。 ( 5 ) 遗传算子遗传算法模拟生物进化过程建立的遗传算子主要包括繁殖、杂交和 变异。算法先利用选择策略从群体p ( 七) 中选择进行繁殖的个体组成父代p ( 七+ 1 ) ，然后 对尸( 七+ 1 ) 进行重组，作用繁殖、杂交和变异等算子来形成下一代新的个体。遗传算法 的杂交是以概率只交换两个父代个体间对应的分量。杂交算子有多种，如单点，双点和 多点杂交算子。变异算子是以概率己改变串上的每一位。变异算子包括基本位变异和均 7 西安科技大学硕士学位论文 匀变异等。 ( 6 ) 停止准则遗传算法循环执行计算适应度值、选择复制和应用杂交和变异算子 这几个步骤，直到满足某个停止准则，例如算法已经找到一个能接受解，或己迭代了预 置的代数。 从上面可以看到，遗传算法是个迭代过程，在迭代中，算法保持一个定常规模的解 群体，每一步迭代( 称为代) 包括，计算当前群体中个体的适应度值和基于适应度值重 组一个新的解群体。 2 1 2 算法的基本结构 不同的编码方案、选择策略和遗传算子相结合构成了不同的遗传算法，但遗传算法 的基本结构可描述为： b e g i n f 卜o 初始化尸( ，) 评价p ( f ) w h i l e ( 不满足终止准则) d o b e g i n 重组p ( f ) 以产生c ( ，) 评价c ( f ) 从p ( f ) 和c ( f ) 中选择p o + 1 ) f 卜，+ 1 e n d e n d 2 1 3 算法的基本操作流程 利用遗传算法解最优化问题，首先应对变量可行域中的点进行编码，然后在可行域 中按编码方式随机产生一定数量的个体，作为进化起点的第一代群体。通过计算每个个 体的适应度函数值，并依此对群体进行选择、交叉、变异等人工遗传操作，产生新一代 群体。以新产生的群体作为父本，重复选择、交叉、变异过程，直到终止条件得到满足 为止。 整个计算过程大体分为以下几步： ( 1 ) 随机产生初始种群，个体的数目一定，每个个体表示为染色体的基因编码： ( 2 ) 计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表 的最优解，并结束计算，否则转向第3 步； 8 2 基本遗传算法及其实现技术 ( 3 ) 根据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可 能被淘汰； ( 4 ) 根据设定的遗传概率，进行下述人工遗传操作，产生新一代群体； a 交叉将选出的个体相互配对，进行部分染色体交换，产生新个体添入新种群中 b 变异随机地改变某一个体的某个基因后，形成新的个体，添入新种群中 ( 5 ) 由交叉和变异产生新一代的种群，返回到第2 步，当满足终止条件时，停止进化， 并选择最佳个体作为问题的优化结果。 算法流程如图2 1 所示。 图2 1 遗传算法的基本流程示意图 f i g u r e2 - lf l o ws h e e to f g e n e t i ca l g o r i t l l l i l s 上述算法中，适应度是对个体进行评价的一种指标，是遗传算法进行优化所用的主 要信息，它与个体的目标值存在一一对应关系。选择操作通常采用比例选择，即选择概 9 西安科技大学硕士学位论文 率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从 而可提高种群的平均适配值。交叉操作通过交换两父代个体的部分信息产生子代个体， 使得子代继承父代的有效模式，从而有助于产生优良个体。变异操作通过随机改变个体 中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。 2 2 遗传算法的实现技术 在设计遗传算法时，通常按以下的基本步骤进行： ( 1 ) 确定编码方案：遗传算法求解问题不是直接作用在问题的解空间上，而是利 用解的某种编码表示。选择何种编码表示有时将对算法的性能、效率等产生很大的影响。 ( 2 ) 确定适应函数：适应度值是对解的质量的一种度量，它通常依赖于解的行为 与环境( 即种群) 的关系。一般以目标函数的形式来表示。解的适应度值是遗传算法过 程中进行选择的唯一依据。 ( 3 ) 选择策略的确定：优胜劣汰的选择机制使得适应度值大的解有较高的存活概 率，这是遗传算法与一般搜索算法的主要区别之一。不同的选择策略对算法的性能也有 较大的影响。 ( 4 ) 控制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、执 行不同遗传操作的概率以及其它一些辅助性的控制参数。 ( 5 ) 遗传算子的设计：遗传算法中的遗传算子，主要包括选择、交叉、变异以及 其它一些高级操作。 ( 6 ) 确定算法的终止准则：由于遗传算法计算没有利用目标函数的梯度等信息， 所以遗传过程中，无法确定个体在解空间的位置，从而无法用传统的方法来判定算法的 收敛与否以终止算法。常用的办法是预先规定一个最大遗传代数或算法在连续多少代以 后解的适应度值没有什么明显的变化时，算法终止。 ( 7 ) 编程上机运行：完成上述工作以后，即可按照遗传算法的算法结构编程去进 行问题的求解。由于遗传算法的随机性及不确定性等特点，通常要运行几次才能得到可 靠的解。 遗传算法计算过程的具体实现与计算效果主要取决于变量编码、初始群体生成、适 应度函数设计、遗传算子设计、算法参数选取及停止准则等环节的设计。下面简述标准 遗传算法各个环节的技术实现。 2 2 1 变量编码 遗传算法求解问题时，不是直接在问题的解空间上操作，而是利用解的某种编码将 解空间的解数据表示成遗传空间的基因型串结构数据进行运算，要在目标问题实际表示 与遗传算法的染色体位串结构之间建立关系，即确定编码和解码的关系。d ej o n g 提出 1 0 2 基本遗传算法及其实现技术 了两条操作性较强的编码原则【3 】： 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问题相关的具有 低阶、短定义长度模式的编码方案。 编码原则二( 最小字符集编码原则) ：应使用能使问题得到自然表示或描述的具有 最小编码字符集的编码方案。 1 二进制编码 二进制编码是将问题空间的参数映射到0 1 位串空间上，然后在位串空间上进行遗 传操作，操作的结果再通过解码还原成变量原型( 表现型) 以进行适应度值评估。当变量 用数值描述时，编码就是按变量要求的精度将解空间的十进制数转换成二进制数。当变 量不止一个分量时，可以对各分量分别进行编码，然后合并成一个长串。解码时分别根 据其对应的子串进行解码即可。 设函数变量薯的取值范围为薯h ，包】_ 【，】，用长度为，的二进制编码符号 串来表示该参数，则编码精度为： 6 ：堑：二氇 2 。一l 假设某一个体的编码是： x ：6 ，岛一，6 f 一：如6 1 则对应的解码公式为： 而：+ ( 圭勿2 ，一t ) 訾 符号串的长度为： ，= 【万+ l g ( i x 蒜一x m j n l ) 1 9 2 】+ 1 ) 多变量问题时，可以对珂个变量分别进行编码，相应的编码长度t ，依次连接为一 个长串三= t 作为问题的编码，解码时分别根据变量对应的子串按上述解码公式计算 百 即可。 采用二进制编码有如下优点： ( 1 ) 二进制编码类似于生物染色体的组成，从而算法易于用生物遗传理论来解释， 并使得遗传操作如杂交、变异等很容易实现； ( 2 ) 可以证明，采用二进制编码时，算法处理的模式数最多。 基于此，最初的遗传算法文献多采用二进制编码方案，而且到目前为止二进制编码 方案在遗传算法中仍占主导作用。 同时，二进制编码也存在一些缺点： 西安科技大学硕士学位论文 ( 1 ) 相邻整数的二进制编码可能具有较大的觑删聊f 馏距离，例如1 5 和1 6 的 二进制表示为0 1 1 1 1 和1 0 0 0 0 ，因此要从1 5 改进到1 6 则必需改变所有的位，这种 缺陷将降低遗传算子的搜索效率。 ( 2 ) 二进制编码时，一般要先给定求解的精度以确定串长，而一当精度确定后， 就很难在算法执行中调整，从而使算法缺乏微调的功能。若在算法一开始就选取较高的 精度，那么串长就很大，这样也将降低了算法的效率。 2 实数编码 为了克服二进制编码的缺点，对于目标问题的变量是实向量的情形，可以直接采用 十进制进行编码。若每个变量用三位十进制数表示，变量个数为所，则染色体的长度为 聊。对于实数编码的情形，从理论上讲，二进制编码下的各种遗传操作同样可以使用， 因为在机器中实数也是采用二进制表示的。但实际应用时却很少使用这些基于内部点操 作的算子，而是针对实进制编码的特性，引入其它一些遗传算子。 3 树编码 树编码是一种非固定常用编码模式，其表示空间是开放的。在搜索过程中树可以自 由生长，但是不便于形成更具有结构化和层次化的问题解，实际应用中往往可以加以限 制。 4 乱序编码 g o l d b e r g 和他的同事提出了一种基于乱序编码的遗传算法，用于提高函数优化和概 念学习问题中的遗传算法的搜索能力。其主要思想是促进短距模式的检测和重组效率， 降低模式被交叉算子破坏的概率。 2 2 2 初始群体生成 初始群体是遗传算法搜索的出发点。对于群体规模，编码长度的问题，随机产 生木三位编码字符，组成个初始个体，构成初始种群。 2 2 3 适应性的度量 遗传算法在优化搜索中不用外部信息，仅以个体适应度函数为依据。适应度函数反 映个体( 问题的一个解) 的优劣性，是选择操作的唯一依据。适应度函数的设计直接影响 遗传算法的性能，不同的问题，适应度函数的定义方式也不同。 遗传算法中度量适应性的方法有很多种，可以用目标函数的形式给出，也可用目标 函数变换的方式来定义。 1 原始适应函数： 原始适应函数是问题求解目标的直接表示，通常采用问题的目标函数作为个体的适 应性度量。对于一个问题定义原始适应函数的方法不止一种，选择时要尽量反映问题本 1 2 2 基本遗传算法及其实现技术 身的整体特性，而不能只追求片面的目标，这一点对用遗传算法求解非数值问题时尤为 重要，而且往往也是较困难的。 2 标准适应函数： 因为原始适应函数反映问题的最初求解目标。因此会出现两种情形，一是极小化情 形即原始适应度值越小个体性能越好；另一种是极大化情形即原始适应度值越大个体性 能越好。但是遗传算法中的某些选择策略( 如基于适应度值比例的选择策略) 则要求适 应函数是非负的，而且适应度值越大表明个体性能越好。这时常常需要将原始适应函数 作一个适当的变换以转化成标准的度量方式，即皆化为极大化情形，并且适应度值非负。 对于极小化情形，标准适应度值可定义为： 麓m 耐( x ) = ，二缸一厂( x ) 其中无戤是原始适应度函数厂( x ) 的一个上界。若丘未知，则它也可以采用迄今为 止进化过程中厂( x ) 的最大值来代替。当然这种定义方式也不是唯一的。 对于极小化情形，则标准适应度函数可定义为： 缸( x ) = 二+ 厂( 石) 其中厶；。为原始适应度函数厂( x ) 的一个下界，若厂( x ) 未知，则可以采用当前一代或 前k 代中的7 r ( x ) 最小值，也可以是群体方差的函数。 常用的适应度函数基本有以下三种： ( 1 ) 直接以待求解的目标函数的转化为适应度函数，即： 若目标函数为最小化问题：鼢( ( x ) ) = 一厂( x ) 若目标函数为最大化问题：厅f ( ( x ) ) = 厂( x ) 这种适应度函数简单直观，但存在两个问题，其一是可能不满足常用的轮盘赌选择 中概率非负的要求：其二是某些代求解的函数在函数值分布上相差很大，由此得到的平 均适应度可能不利于体现种群的平均性能。 ( 2 ) 若目标函数为最小化问题，则 m 砌- 八静 式中艮为厂( z ) 的最大值估计； 若目标函数为最大化问题，则 刚) = p i 八紫 式中为厂( z ) 的最小值估计。 这种方法是对第一种方法的改进，可以称为“界限构造法”，但有时存在界限值预先 估计困难、不可能精确的问题。 ( 3 ) 若目标函数为最小化问题，则 1 3 西安科技大学硕士学位论文 1 砌( 似) ) 2 赢c o ，m ) o 若目标函数为最大化问题，则 1 凡( 似) ) 2 赢c o ，c m ) o 这种方法与第二种方法类似，c 为目标函数界限的保守估计值。 常用的个体适应度变换的方法有三种：线性尺度变换、乘幂尺度变换和指数尺度变 换。 适应度函数的设计要满足以下条件： ( 1 ) 单值、连续、非负及最大化，这个条件是很容易理解和实现的。 ( 2 ) 合理、一致性，要求适应度值反映对应解的优劣程度，这个条件的达成往往比 较难以衡量。 ( 3 ) 计算量小，适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的 复杂性，降低成本。 ( 4 ) 通用性强，适应度对某类具体问题，应尽可能通用，最好无需使用者改变适应 度函数中的参数。从目前而言，这个条件应该是不属于强要求。 3 有约束下的目标函数 遗传算法很适合解无约束优化问题，对于有约束优化问题，通常的作法是，在目标 函数中加上考虑约束的惩罚函数，使问题转化为无约束优化问题。 4 多目标问题 实践中经常会遇到一些多目标优化的工程问题，多个目标通常并不一致，相互之间 发生冲突，为协调这一冲突，并考虑到遗传算法适合求解单目标优化问题，有的学者直 接将多个目标乘上权系数后相加转化为单目标求解，有些学者则采用另外的转换形式 【2 3 1 ，有些学者把数学中的p a r e t o 定律与遗传算法相结合，产生了p a r e t og a 【2 4 1 ，由分级 的手段给出适应度。最后得到的不是一个最优解，而是一个p 删。解集，使用者可根 据实际情况从中选择合适的解。 2 2 4 遗传算子的设计 遗传算子从狭义来讲指杂交算子和变异算子。对于不同的编码表示，遗传算子不同。 二进制编码中的遗传算子 杂交分点式杂交和均匀杂交。点式杂交又可分为单点杂交和多点杂交；均匀杂交则 是依概率交换两个父串的每一位。在实际应用中，并不单纯采用某一种杂交方式，不同 的问题有不同的应用方法。当设计变量的个数超过2 0 时，由于需要处理的设计空间很 大，简单遗传算法的效率会很低。 1 4 2 基本遗传算法及其实现技术 二进制编码时的变异算子非常简单，只是以一定的概率将所选的位取反。即若是1 ， 则取o ；若是0 ，则取1 。 实数编码中的遗传算子 实数编码时的遗传算子与二进制编码时的情形将完全不同。在实数编码中，杂交算 子的作用远没有二进制编码时显得重要，变异算子已成为主要的搜索算子。杂交和变异 的方式与二进制编码相比也有很大的不同。 ( 1 ) 选择算子 选择策略对算法性能的影响会起到举足轻重的作用。一般来说，选择策略会影响到 算法的性能和结果。下面是经常用到的几种选择策略。 比例选择【3 j 比例选择方法( p r o p o n i o i 谢m o d e l ) 是一种回放式随机采样的方法。其基本思想是： 各个个体被选中的概率与其适应度大小成正比。由于是随机操作的原因，这种选择方法 的选择误差比较大，有时甚至连适应度较高的个体也选择不上。 设群体大小为m ，个体f 的适应度为e ，则个体f 被选中的概率玩为： 旦 风= f f ，o = 1 ，2 ，m ) l = l 由上式可见，适应度越高的个体被选中的概率越大；反之，适应度越低的个体被选 中的概率越小。 最优保存策略【1 3 】 在遗传算法的运行过程中，我们总希望适应度最好的个体要尽可能地保留到下一代 群体中，为了达到这个目的，可以使用最优保存策略进化模型( e l i t i s tm o d e l ) 来进行优 胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来 替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。 最优保存策略进化模型的具体操作过程是： a 找到当前群体中适应度最高的个体和适应度最低的个体； b 当前群体中最佳个体的适应度比总的迄今为