（工程热物理专业论文）基于遗传算法的动力配煤优化模型的研究及其软件实现.pdf

浙江大学硕上学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 摘要 动力配煤优化模型的研究及实现是本文的主要研究内容。用穷举法作为优化 模型虽然能够取得最优解，但是由于穷举法的求解过程需要遍历解空间中的每一 个解，随着解空间的膨胀，其低下的搜索效率便成为一个无法克服的缺陷，因此 这种方法不适合解决大规模动力配煤优化问题。 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种基于遗传机理的全局优化算 法，它是由美国密歇根大学的j o h n h h o l l a n d 教授于1 9 7 5 年受生物进化论的启 发而提出的。g a 是基于“适者生存”进化规律的一种高度并行、随机和自适应 的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体” 群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境” 的个体，从而求得问题的最优解或满意解。近年来，g a 凭借其独特的群体搜索 机理和高效的优化效率，在各个领域得到了广泛应用，取得了显著的成绩。 本文在前人研究的基础上，对简单遗传算法作了改进。首先利用g a 不需要 目标函数的可微性这个特点，直接采用，( x ) 作为罚函数，替代优化界传统上为 保证目标函数f ( x ) 的梯度处处存在而采用( x ) 的罚函数形式，降低了优化结果 中不可行解的比例，提高了解的可靠性；其次通过理论的分析，找出了简单遗传 算法使用适应度比例选择法的缺陷，并运用b o l t z m a n n 选择法替代适应度比例 法，进一步提高了动力配煤优化结果的准确性和稳定性：再次，针对罚函数法处 理约束优化问题时，罚因子难以确定的情况，以及运算结果偶尔会出现不可行解 的缺陷，本文使用了g a 独有的直接比较一比例法，d c p m g a 进行动力配煤优 化，保证了结果的可靠性；最后，本文采用面向对象软件设计法，在前面的研究 成果的基础上，设计了配煤优化模块动力配煤优化引擎。 全文共分四章。第一章为综述，大致介绍了动力配煤的研究现状，并对几种 优化算法进行了比较，提出了本文需要研究的内容；第二章为本文的主要部分， 这个部分从简单遗传算法入手，详细介绍了遗传算法在动力配煤优化问题中的应 用过程，接着通过对算法结构的改造，提出了b o l t z m a n n 选择g a 和d c p m g a 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 两种算法结构；第三章是在第二章的基础上，对配煤优化模块进行了软件设计； 第四章总结了本文的研究成果，并对今后的研究方向进行了展望。 关硭女孔配煤动力配煤优化遗传算法g a 面向对象设计o o d 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 a b s t r a c t t h em a i n p u r p o s e o ft h i s p a p e r i st or e s e a r c ht h em o d a lo fc o a lb l e n d o p t i m i z a t i o n i n t h e p r o g r e s so fo p t i m i z a t i o n ，t h ee n u m e r a t i o n m e t h o dn e e d st os e a r c h e v e r yr e s u l t a l t h o u g ht h eb e s tr e s u l tw i l lb ef o u n da tl a s t ，t h ee f f i c i e n c yi sv e r yl o w , a n di tc a n tb eo v e r c o m e w h e nt h er e s u l t s p a c e i s v e r yl a r g e ，t h ep r o g r e s so f o p t i m i z a t i o nw i l lb ev e r ys l o w s ot h i sm e t h o d i sn o tf i tf o rc o a lb l e n do p t i m i z a t i o ni n l a r g es c a l e g e n e t i ca l g o r i t h m ( g a ) i sag l o b a lo p t i m i z a t i o na l g o d t h r n ，w h i c hi sb a s e do n i n h e r i tm e c h a n i s m e n l i g h t e n e db ye v o l u t i o n i s m p r o f e s s o rj o h nh h o l l a n df r o m m i c h i g a nu n i v e r s i t yc r e a t e dg a i n1 9 7 5 g ai sah i g h l yp a r a l l e l ，s t o c h a s t i ca n d a d a p t i v eo p t i m i z a t i o nm e t h o d ，w h i c hi sb a s e do nt h ee v o l u t i o n a lr e g u l a r i t yo f “t h e s u r v i v a lo f t h e f i t t e s t w h e ns e e k i n gs o l u t i o n o f a q u e s t i o n ，i t t r a n s f o r m s t h e p r o g r e s s i n t ot h ef o r mo f t h es u r v i v a lo f t h ef i t t e s t ”o f c h r o m o s o m e sa tf i r s t ，t h e na f t e rm a n y g e n e r a t i o n so fe v o l u t i o n ，i n c l u d i n gt h eo p e r a t i o n so fc o p y , c r o s s o v e ra n dm u t a t i o n ， t h ec o l o n yo fc h r o m o s o m e sw i l lb ec o n v e r g e d ，w h i c hf o r m st h em o s tf i t t e s to n ei nt h e e n v i r o n m e n ta tl a s t ，a n dt h i si st h em o s to p t i m i z e ds o l u t i o no ra p p r o x i m a t e l ym o s t o p t i m i z e ds o l u t i o n t h e s ey e a r s ，w i t hr e s o r tt o i t s p a r t i c u l a rm e c h a n i s mo fc o l o n y s e a r c ha n d h i g he f f i c i e n c yi no p t i m i z a t i o n ，g a h a sb e e nu s e di nm a n yf i e l d sa n dh a s m a d e g o o d a c h i e v e m e n t s t h i sp a p e ri sb a s e do nt h ef o r m e rr e s e a r c ha c h i e v e m e n t , a n d i m p r o v e st h es i m p l e g e n e t i ca l g o r i t h m i nc o a lb l e n d o p t i m i z a t i o n f i r s t ，g a d o e sn o tn e e dt h e d i f f e r e n t i a b i l i t yo f t h eg o a lf u n c t i o n ，a n dw i t ht h ec h a r a c t e ro ft h a t , i tu s e s f a x ) a s t h e p e n a l t y f u n c t i o n s d i r e c t l y i n s t e a do fr ( x ) i nt r a d i t i o n ，w h i c hr e d u c e st h e p r o p o r t i o no f e r r o r si nt h es o l u t i o n s ，a n de n h a n c e st h e r e l i a b i l i t y ；s e c o n d ，t h r o u g ht h e a n a l y s i si nt h e o r y , t h i sp a p e rf i n d st h el i m i t a t i o no f t h ef i u t e s s - p r o p o r t i o n a t es e l e c t i o n i n s i m p l eg a ，a n du s e sb o l t z m a n ns e l e c t i o n ，w h i c hi m p r o v e st h ea c c u r a c ya n d s t a b i l i t y o ft h e r e s u l t ；t h i r d ，w h e nu s i n gp e n a i t yf u n c t i o n si nd e a l i n gw i t ht h e q u e s t i o n so fo p t i m i z a t i o nw i t hr e s t r i c t i o n s ，t h ep e n a l t yf a c t o r sa r eh a r dt ob ec h o s e n 新江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 a n dt h e r ea r eaf e we r r o r si nr e s u l t s ，s ot h i sp a p e ru s e sap a r t i c u l a rm e t h o d ，d i r e c t c o m p a r i s o n - p r o p o r t i o n a lm e t h o dw h i c h e n s u r e st h er e l i a b i l i t yo ft h er e s u l t ；a tl a s t ， t h i sp a p e ru s e so b j e c t o r i e n t e dm e t h o d ( 0 0 d ) t o d e s i g nt h es o f t w a r em o d u l eo f c o a l b l e n d o p t i m i z a t i o nn a m e d c o a lb l e n do p t i m i z a t i o n e n g i n e t h i sp a p e rc a l lb ed i v i d e di n t o4c h a p t e r s t h e15 c h a p t e ri n t r o d u c e st h es i t u a t i o n o f t h ec o a lb l e n d sr e s e a r c h , c o m p a r e ss e v e r a lo p t i m i z a t i o nm e t h o d s ，a n dt h e nl i s t st h e c o n t e n t so ft h i sp a p e r c h a p t e r2i st h em a i n p a r t t h i sp a r tb e g i n s 、 ，i t l ls i m p l eg a a n di n t r o d u c e st h ea p p l i c a t i o no fg ai nc o a lb l e n d o p t i m i z a t i o ni nd e t a i l t h e na l t e r s t h es t r u c t u r eo fs g a ，w i t ht h eu s eo fb o l t z m a n ng aa n dd c p m g a c h a p t e r3 d i s c u s s e st h ed e s i g no ft h es o f t w a r em o d u l e ，c o a lb l e n do p t i m i z a t i o ne n g i n e t h e l a s tc h a m c t e rm a k e sas u m m a r y ， k e y w o r d s ：c o a lb l e n do p t i m i z a t i o n ，g e n e t i ca l g o r i t h m ，g a ，o b j e c t - o r i e n t e dd e s i g n ， o o d 浙江大学硕士学位论文 基于遗传算法的动力配煤优化模型的研究及其软件实现 第一章综述 1 1 引言 我国是以煤炭为主要能源的国家，煤炭的生产量与消费量均占世界首位。在 我国各种能源资源中，煤炭资源也最为丰富，2 0 0 2 年探明的储量为1 1 4 5 亿吨。 2 0 0 2 年，我国的煤炭产量为1 3 8 亿吨，占世界总产量的2 9 5 ，消费量为1 3 7 亿吨，占世界总消费量的2 7 7 。全国每年用于直接燃烧的动力煤约占煤炭总消 费量的8 0 ，其中发电约占3 2 ，工业锅炉、窑炉约3 5 ，民用及其他1 0 以 上。我国以煤炭为主要能源的结构在今后几十年时间内不会被改变。 当前，我国煤炭燃用过程中主要存在两个方面的问题： 1 煤炭热能利用率低。煤的热能利用率在电厂仅为3 3 3 4 ( 国际先进为4 0 以上) ，工业锅炉仅为6 0 - - 6 5 ( 国际先进为8 0 8 5 ) 。造成煤炭热能 利用率低的原因，主要由于燃煤来源渠道多、煤种杂、质量不稳定，偏离锅 炉等燃烧设备的设计煤种造成。 2 燃煤污染物排放严重。煤炭燃烧时产生s 0 2 、n o 。、烟尘及其它有害物质。 以我国为例，2 0 0 2 年，工业烟尘和8 0 2 的排放量分别为8 0 4 万吨和1 5 6 2 万 吨，占当年全国总排放量的7 9 和8 1 。燃煤污染物排放是我国大气污染的 主要来源。 要改变这一现状，发展以提高煤炭利用率和减少污染为宗旨的洁净煤技术 ( c l e a nc o a lt e c h n o l o g y ) 是切实而有效的现实选择【1 】。 洁净煤技术的含义f 2 j 是指在煤炭加工和利用过程中旨在减少环境污染和提高 利用效率的由加工、燃烧、转化和污染控制等新技术组成的技术体系。我国煤炭 消耗量大，洗选率低，能源利用率低，单位能耗产生的污染大，这些都决定了开 发和应用洁净煤技术的必要性和紧迫性。中国政府已经把发展洁净煤技术作为一 项重大的战略性措旖列入中国2 1 世纪议程，并于1 9 9 5 年成立了洁净煤技术 开发和推广领导小组。中国洁净煤技术“九五”计划和2 0 1 0 年发展纲要已得 到国务院批准，洁净煤技术作为能源发展的主导技术将得到重视和发展。 洁净煤技术是我国能源的未来”，研究、开发和利用适合我国国情的中国洁 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 净煤技术是一项具有重大意义的战略性课题。中国洁净煤技术的核心【4 j 1 5 j 是提高 效率和减少污染，从而使煤炭成为洁净、高效、可靠的能源。根据我国煤炭开采 利用的特点及对环境的影响，洁净煤技术应包括煤炭的洁净开采和污染控制，主 要包括下面四个领域、十五个方面的技术：( 1 ) 煤炭加工：选煤、动力配煤、型 煤、水煤浆；( 2 ) 煤炭转化：气化、液化、燃料电池；( 3 ) 煤炭高效洁净燃烧： 流化床、增压流化床、整体煤气化联台循环发电技术；( 4 ) 污染排放控制与废弃 物处理：烟气净化、电厂粉煤灰综合利用、煤层气开发利用、矸石和煤泥水的综 合利用。在这个技术体系的框架中动力配煤技术和循环流化床燃烧技术是目前我 国研究应用得比较多的两种技术1 6 j 。 1 2 动力配煤概述 动力配煤技术是以煤化学、煤的燃烧动力学和煤质测试等学科和技术为基 础，将不同类别、不同质量的单种煤通过筛选、破碎、按不同比例混合和配入添 加剂等过程，改变单种动力用煤的化学组成、物理性质和燃烧特性充分发挥单 种煤的煤质优点，克服单种煤的煤质缺点，提供可满足不同燃煤设备要求的煤炭 产品的一种简易的成本较低的技术。从而达到提高效率、节约煤炭和减少污染物 排放的目的。 任何类型的锅炉和窑炉对煤质均有一定的要求，在现有条件下，要提高锅炉 热效率，就要保证锅炉达到正常高效运行，使燃煤特性与锅炉设计参数相匹配。 煤质过高或过低都难以达到最佳效果。在满足燃煤设备对煤质要求的前提下，采 用动力配煤技术可最大限度地利用低质煤、或更充分地利用当地现有的煤炭资 源。不同品质煤的相互配合，还可以按不同地区对大气环境、水质的要求，调节 燃煤的硫分及氮、氯、砷、氟等有害元素含量，减少s 0 2 、n o x 及有害元素的排 放，最大限度地满足环境保护要求。 概括而言，动力配煤具备以下几点意义： l 、保证燃煤特性与用煤设备设计参数相匹配、提高设备热效率、节约煤炭； 2 、通过“均质化”来保证燃煤质量的稳定，使用煤设备正常、高效运行； 3 、充分利用低质煤或当地现有煤炭资源，做到物尽其用，提高社会效益： 4 、调节燃煤中硫及其它有害物质的含量、满足环保要求。 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 动力配煤技术在我国的研究与应用起步于八十年代，上海、北京、天津、沈 阳和南京等十几个大中城市的燃料公司率先建成了动力配煤场( 车间) 。到九十 年代初，全国已建成了近2 0 0 条动力配煤生产线，取得了较好的经济效益、社会 效益和环境效益。近年来，动力配煤技术在我国发展较快，一些用煤量较大的城 市、大的煤炭集散地以及一些煤种较多且煤质复杂的矿区正计划建动力配煤场。 煤炭工业“十五”规划把发展配煤作为煤炭产品结构调整的方向之一，确定了 动力配煤量在“十五”期间达到7 0 0 0 万t 的目标。动力配煤技术己作为一种比 较适合中国国情的洁净煤技术列入了煤炭工业洁净技术发展规划，这项技术在中 国将会有广阔的发展前景。 1 3 动力配煤技术的研究状况 国外一些电厂进行动力配煤的主要原因和目的是采用低硫煤与高硫煤混合 燃烧以降低s 0 2 的排放，降低锅炉的结渣、沾污和积灰，充分利用高热值煤，保 证灰含量和发热量等等【1 q ，而美国、德国、日本、英国、西班牙、荷兰和加拿大 等是从事动力配煤研究较早的国家。其研究内容涉及到混合系统和混合方法的研 究、配煤着火性能的研究、配煤对结渣性能影响的研究、采用混烧方法以降低 n o x 及s o x 排放的研究等等1 1 1 4 3 1 。 在国外，特别是在美国，动力用煤大部分为优质煤，燃烧界认为在煤粉炉中 燃烧方面不成问题，故将研究的重点放在其他方面，特别是污染物的排放控制， 对混煤的研究也是如此。因此，美国在采用混煤方法降低s o x 的排放方面进行 了较为深入的研究。与此同时，也考虑通过电厂配煤运行方式来稳定入炉煤的煤 质，以此避免锅炉的结渣，而且灰含量稳定还能使灰处理系统高效运行。 英国利用混煤燃烧可以将燃煤的灰分含量限制在1 7 以下，收到了减轻或消 除结渣的良好效果。西班牙的劣质煤储量较多，为了充分利用这些煤，其研究人 员研究了低挥发分煤燃烧和混煤的燃烧特性，研究结果表明当采用混煤燃烧时， 可以提高锅炉的燃烧效率以及保证锅炉燃烧的经济性。 在配煤技术方面，国外配煤一般采用仓混式、库混式，带混式或采用炉内直 接混合等形式，并且已经发展到依靠配煤理论、运用计算机指导煤场和电厂的动 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 力配煤。 我国国内对配煤进行深入研究的机构主要有浙江大学热能工程研究所、华中 理工大学煤燃烧国家重点实验室，华北电力大学，哈尔滨工业大学，中国矿业大 学等，对于混煤煤质特性，燃烧特性，结渣特性，s 0 2 排放的预测方面的研究工 作做得比较多。浙江大学热能工程研究所是我国较早进行动力配煤研究的单位， 早在上个世纪9 0 年代末就提出了完整的动力配煤优化模型，如公式( 1 11 ) 所 示 2 l 】： 目标函数 r a i n p = g 并，( f = 1 , 2 ，3 ，”) ( 1 ) i - i 约束条件 发热量 q 。( x ，q f ，m ，4 ，_ ，f c 。) s g 。 ( 2 ) 挥发分 n 工( j 0m ，4 ，k ，f c i ) ( 3 ) 硫分 配，( 鼻，s ) s b ( 4 ) 灰分 a s 正( x ，a i ，k ，f c i ) a 口 ( 5 ) 水分 既s l ( x 。，彬) ( 6 ) 灰熔点 s l 丘( 五，各单煤的灰成分分析) ( 7 ) 着火温度 以s ，( 墨，q ， i ，4 ，巧，冗：) s 毛 ( 8 ) 结渣特性 r 。l ( x ，各单煤的灰成分分析) sr 。 ( 9 ) 燃烬特性d as 厶( 鼻，q ，m ，4 ，砟，心) s j d 。( 】o ) 硫排放特性 s 0 2 2 ( x 。，墨，q i ，各单煤的灰成分分析) ( 1 1 ) 其中，为混煤价格， 为掺配煤种的数日，c i 为单煤价格z i 为单煤配比，通常0 i x 0 9 。 对于这个模型中的混煤煤质预测函数，业界还存在一定的争论。一种观点认 为，混煤煤质指标是线性可加的【1 4 - 1 5 ，即混煤煤质指标是各单煤指标的加权平均 或线性回归( 线性论) ；另一种观点则认为，混煤特性与各种单煤的特性之间是 一种复杂的非线性关系1 8 。1 。4 2 射，这种关系很难通过给出一个确定的非线性函数 来表现，但是可以用神经网络模型来模拟。在综合了这两种意见后，文献【l6 】认 为，不能简单的认为混煤煤质是线性或非线性的，首先需要有一个统一的评价标 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 准，如果某个指标的加权平均值在这一标准内，则认为其是线性的，否则就认为 是非线性的，作者建议采用实验室国家标准；其次评价煤质可加性时需要采用统 一的基。基于这两个前提，作者通过理论分析和试验论证后认为，混煤的分析基 水分m 。d ，灰分a a d ，挥发分v 叫，发热量q d 等指标具有线性可加性。文献 1 7 】 在对混煤挥发分的可加性进行研究后，分析基挥发分v 。d 是线性可加的，而干燥 无灰基挥发分v d 酊是非线性可加的。目前，混煤煤质预测方法主要有简单线性相 加，线性经验公式，神经网络模拟等，用这些方法计算的结果都存在一定程度的 误差。 对动力配煤优化模型的研究，总的说来还没有实质性的突破。早期的配煤理 论建立在线性论的基础上，而单纯形法是一种线性优化方法，所以有人曾使用这 种方法来进行动力配煤优化，但是这种方法随着对配煤的研究的深入，特别是非 线性论的提出后，已经不再适合了：穷举法因为其算法简单，绝对收敛于最优解 的特点，目前仍被广泛应用，但是这种方法只适合于小规模的优化搜索，在配煤 精度高，煤种多的情况下，穷举法的运算效率极其低下【9 】：文献【8 】采用m d o d 法( 混合离散变量优化设计) 进行优化配煤，该方法结合了“爬山”和“查点” 的策略，在计算效率上较穷举法有较大改善，但是它只能对掺配比例而不能对掺 配煤种进行优化设计，并且其自身算法的缺陷导致其容易陷入局部优解【叭。文献 9 】抛开了传统优化算法，采用模拟退火和遗传算法等智能优化算法，在配煤优 化领域取得了一定的突破。 计算机优化配煤运行是一种应付当今火电厂燃煤频繁变更，控制入炉煤煤质 的重要手段，可以有效地控制入炉煤质，保证锅炉的稳定运行，减轻结渣，沾污， 积灰，腐蚀和磨损。 例如美国p r a x i c 公司于九十年代中期开发的电厂优化配煤专家系统( c b a s ) 已经用于美国和加拿大的部分电厂，根据p r a x i c 公司的最新统计分析显示： 美国p e n n s y l v a n i a 电厂在使用了c b a s 系统后，一改往日只使用固定煤种的 情况，采用多煤种的配煤燃烧，仅此一项每年可节约达$ 2 ，0 0 0 ，0 0 0 。 肯塔基州电厂在使用了c b a s 系统后，通过配煤燃烧，增加了廉价煤使用量， 降低了发电成本，同时降低了s 0 2 和n o x 的排放，全年总计节约$ 1 ，0 0 0 ，0 0 0 。 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 美国的另一座电厂使用c b a s 系统控制混煤的质量，达到了减轻结渣的目 的，全年总计节约$ 2 ，5 0 0 0 0 0 。 瑞士a b b 公司开发了应用于电厂的配煤专家系统f c o a lq u ar i t y e x p e r t ) ，此套系统为电厂带来了良好的经济效益，并在控制污染物排 放中起到了一定的作用。 由于我国的计算机应用总体水平仍然比较低下，因此要实现动力配煤过程的 自动化、智能化控制还有一定的难度。南京大陆产业集团曾经提出了“绿色数字 化煤场”的概念，并专门为此邀请了浙江大学热能所，东南大学，西安国电热工 研究院等多家研究机构的专家学者，和华东地区几十家火电厂的相关负责人及工 程师，举办了一个研讨会，笔者有幸参加了这次会议。“绿色数字化煤场”是集 动力配煤优化，配煤控制，自动输煤，煤质自动检测，检测数据反馈，混煤配比 智能调整等多项功能于体的应用方案。与会人员致认为这套方案十分完整， 基本上可以实现火屯厂配煤全过程的自动化和智能化。然雨，要实现这个方案， 需要配置很多硬件设备以及相关的软件，因此成本太高，难度和风险都很大，现 阶段实施的可能性不大。大多数火电厂的工程师们提出，他们目前最关心的是希 望有一个软件，能够帮助他们分析混煤煤质特性，提供优化的配煤方案。浙江大 学热能所研发的“优化配煤专家系统”【2 2 】正好满足了火电厂的这两个需求，具 有良好的应用前景。但是，目前的“优化配煤专家系统”在进行配煤优化的时候， 使用的优化方法为穷举法，而穷举法的效率极其低下，这已经成了该系统的一个 软肋，因此加强对优化方法的研究是项十分必要的工作。 l i4 优化搜索技术综述 1 4 1 优化搜索算法概述 在工程技术、经济、科学和社会等许多领域，存在着大量的以各种形式出现 的整体优化问题，物理上表示为费用、时间、风险的整体极小化，以及质量、利 润和效率的整体极大化等口6 1 。因此，针对这些具体问题研究的需要，发展了一 般性的优化求解策略。 浙江大学硕士学位论文 基于遗传算法的动力配煤优化模型的研究及其软件实现 整体优化问题的搜索求解技术主要包括基于微分的搜索技术、随机搜索技 搜索技术 太= _ 基于微分的搜索技术启发式随机搜索技术枚举技术 随机搜索技术 弋、 直接法间接法模拟退火算法进化算法 隐枚举法完全枚举法 动态规划 7 f i b o n a c c i ji n e w t 。n ii 进化策略il 遗传算法ii 进化规划i 7 串行遗传算法并行遗传算法分类器遗传规划 幽i - 4 l 搜索算法分类 术、启发式随机搜索技术和枚举技术。图i - 4 1 对有关具体优化搜索算法进行了 大致分类【2 7 1 。 目前，对于求解整体优化问题已经进行了大量理论研究，并提出了许多基于 导数( g r a d i e n t ) 的解析方法( c a c u l u s b a s e d ) 币l l 其他非解析的数值优化技术。但是， 在实际领域中存在着各种高度复杂的优化问题，其目标函数可能表现为非连续或 非处处可微、非凸、多峰和带噪声等各种形式，这类复杂优化问题不适合用解析 方法，同时用传统上的搜索技术求解也会遇到许多困难。因此，多年来人们一直 在努力寻找能够处理这类问题的新的、更稳健的优化技术。 传统的基于微分的方法，包括直接法( 如爬山法) 和间接法( 如求导数方法) ， 对问题性质有较高的要求，或者是针对特定问题形式而设计的，一般统称为强方 法( s t r o n gm e t h o d s ) 。枚举方法是一种解空间的遍历搜索方法，包括动态规划法， 隐枚举法，完成枚举法等，其特点是可以发现问题的全局最优解，但是计算效率 太低( 存在维数灾难) ，不适用于大型优化问题求解。随机搜索方法在问题空间 中随机选择一定数量的点，然后从中选优，带有一定盲目性，对于复杂问题不能 保证解的质量，而且其计算效率与枚举方法基本等价。 启发式随机搜索方法( r a n d o mh e u r i s t i cs e a r c h ，r i - i s ) 是目前关于复杂优化问 题求解的一类有效方法，不需要或者只需要很少的关于问题的先验信息。其次， 7 浙江大学硕士学位论文 基于遗传算法的动力配煤优化模型的研究及其软件实现 该类算法具有很强的鲁棒性，即能适应不同领域的优化问题求解，并在大多数情 况下都能得到比较满意的解。r h s 一般统称为弱方法( w e a km e t h o d s ) 。遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 就是一种典型的弱方法，与模拟退火、爬山算法等相 比，具有独特的算法形式和运行机理，在复杂优化问题求解中有着比较显著的优 势。 1 4 2 启发式随机搜索技术的基本功能 遗传算法发明人美国密歇根大学j o h nh h o l l a n d 教授，在复杂适应系统 研究中指出，适应过程必须通过设计合理的适应计划，在关于新的系统结构的探 索和已获得遗传信息的继承与完善之间取得平衡，我们分别称之为适应计划或算 法的求泛和求精的能力( r e f o r m i n g a n d r e f i n i n g ) 。这种情形不仅存在于生物体的进 化过程，也是复杂优化问题求解的搜索技术的基本功能。对于任何一种算法来讲 它们均构成了一对矛盾，求精能力好的算法往往不具备良好的解空间上的探索功 能，反之，求泛能力好的算法却往往不能找到精确的全局最优解。 对于优化问题的求解，搜索技术一般从一个或一组初始可行解开始，通过某 种机制转移到解空间上的另一个解或一组解并获得一定的目标函数值的改善。 其中，转移机制的设计是决定性的因素，也是区分局域搜索技术( 1 0 c a ls e a r c h ) 和 全局搜索技术( g l o b a ls e a r c h ) 的基本标准。根据搜索工程是基于单一可行解还是多 个可行解的不同，一般称为单点搜索策略和群体搜索策略。 1 。4 。3 局域搜索技术 采用单点搜索策略，传统上的局域搜索技术从初始可行解开始，运行新的可 行解产生器，持续在当前解的领域中搜索比当前解更好的可行解。若找到这样的 解，用其代替当前解，作为新的当前解，继续同样的搜索行为。爬山法就是一种 典型的局域搜索技术。 局域搜索技术的一般算法形式( l s a ) 表示如下： p r o c e d u r el o c a l _ s e a r c h b e g i n t = 0 8 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 x c 一x 0 c a l c u l a t ef ( x c ) r e p e a t g e n e r a t ex n = g e n ( x 0 ( es o 。) ) c a l c u l a t ef i x ) i f f ( x n ) f 【x 。) t h e nx c ： t ：= t + l u n t i l ( s t o p _ c r i t e r i a ) o r t2m a x e n d 其中，s ( x 。) 是k 的一个领域，s ( x 。) s 。g e n ( x , ) 是新的可行解生成规则或者函数， 称为生成器。生成器既可以是确定性的规则也可以是随机型函数。 l s a 的搜索效果和效率由初始解x o 选择、领域结构s ( x 。) 和生成器邸n ( x 。) 等 因素综合决定，统称需要一定的启发式信息。厂( ) ，( t ) 称为接受准则，使得 l s a 仅仅在当前可行解的附近进行搜索，这是l s a 的主要特征，使得l s a 具备 很好的局部搜索和解的求精能力。 l s a 具有较好的通用型，适用于各种优化问题的求解。算法本身简单灵活， 可以针对特定优化问题设定不同的领域结构和生成器。对于目标函数为单调或单 峰函数来讲，l s a 可以搜索到全局最优解。然而。应用l s a 求解多峰函数优化 问题，能否搜索到全局最优解，以及算法的计算效率等问题，与初始解的选择和 领域结构的设计存在着直接关系。为了提高l s a 的全局搜索能力，引入了多次 重新搜索( m u l t i s t a r t s ) 策略和更为复杂的领域结构，采用更多的启发式信息，以 及改变接受规则等。关于接受规则的改变实际上就为转化另一种搜索方法一模 拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 。 1 4 4 模拟退火算法 1 9 8 2 年，k i r k p a t r i c k 等将金属热加工中的退火工艺的思想应用组合优化问题 领域，提出了一种新的搜索技术模拟退火算法f 3 l 】。它采用m e t r o p o l i s 接受准 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 则，以一组冷却进度表参数控制算法进程，可以在多项式时间内找到近似最优解。 算法的一般形式如下： p r o c e d u rs i m u l a t e d _ a n n e a l i n g b e g i n t = 0 i n i t i a l i z ex o ( x o s ) ，l o ( l o o ) ，t o ( t o 0 ) ) 【c ：= x o l ：= l o t t ：= t o c a l c u l a t e f ( x 。) r e p e a t e f o r l = 1t o l t d o b e g i n g e n e r a t ex n = g e n ( x c ) ( z 。s ( x 。) ) c a l c u l a t e 厂( k ) i f f ( x 。) f ( x 。) t h e nx 。= ：x 。 e l s ei f e x p 芦专盥) r a n d o 删) t h e n t ：= x 。 e n d f = - ，+ 1 z ：= g e n ( t , - l t ) 厶：= g e n ( l f - l ，r ) u n t i l ( s t o p _ c r i t e r i a ) o rt = m a x e n d 其中，s ( t ) 是x 。的一个领域，s ( x d s s 。g e n ( x ) 是新的可行解生成器。 i o 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 f ( x 。) f ( x 。) 是正常的接受准则，对于新生成的较差的可行解按m e t r o p o l i s 接受 准则e x p ( 丛益! ；? ! 型) 。d o 州o ，1 ) 执行。妒。( z + f ) 是t 阶段温度的控制参数 j f 生成函数，一般采用较大的初始值t o ，随着t 增加缓慢降低，使得m e t r o p o l i s 接 受概率也随之逐渐减小。g e n ( l 。，r ) 是t 阶段迭代变换次数的生成函数，h 可以 是全程固定值，也可以随着退后温度而变化。 由于采用了m e t r o p o l i s 接受准则，s a 可以暂时接受较差解，从而扩大了搜 索领域，使得s a 具备一定的跳出局部极值解而发现全局最优解的能力。 1 4 5 g a 搜索 遗传算法应用于优化问题求解，也是一个启发式随机搜索过程。在该搜索过 程中，g a 不仅需要探索解空间上的全局最优解，而且应当充分利用已经获得的 解空间信息，逼近当前局部最优解。g a 通过群体和遗传算子( 选择、交叉、变 异) 可以实现扬弃性的探索，克服局部极值陷阱和模式欺骗，实现整个解空间范 围内的搜索，提高全局寻优能力。通过继承性的开发，维持群体的可进化性，同 时克服早熟问题，实现领域搜索，提高逼近最优解的搜索能力。 对于多模态函数优化问题( m u l t i m o d a lo p t i m i z a t i o n ) ，解空间存在多个局部极 值点，g a 搜索过程应当在求泛和求精的能力方面进行恰当的平衡。一般来讲， 探索解空间上的全局最优解需要较长的时间，具有较大的随机性；完善当前局部 最优解，应当快速逼近局部极值点，尽量减少计算资源消耗，或者尽快改善解的 质量。 1 4 6 启发式搜索技术比较 以上我们简单介绍了三种启发式搜索技术。在局域搜索方面，l s a 和s a 好 于g a ，但是这并不意味着g a 不具备局域搜索能力。当变异概率比较小时，整 个群体中变异基因位基本上均匀分布在染色体位串上，在交叉算子的作用下，可 以进行以当前最佳位串为中心的领域交换，g a 也会表现出很好的局域搜索能力。 当群体规模比较大时，计算效率比较低。因此，在g a 进化的后期，往往采用较 浙江大学硕士学位论文基于遗传算法的动力配煤优化模型的研究及其软件实现 小的群体规模和较大的选择压力。 在g a 进化的早期，群体的多样性较好，以较小的选择压力、较大的交叉概 率和变异概率，g a 可以实现整个编码空间上的探索( 不考虑采用误差) 。在选 择算子的作用下，群体的多样性不断减低，群体中的个体趋于相似，g a 搜索区 域仅为编码空间中的某个子空间，g a 搜索行为也就从探索进入开发阶段。若选 择算子和参数设计不合理，g a 过早结束探索阶段，则难以实现全局寻优。同样， 过迟进入开发阶段，也难以完成领域搜索和提高当前最优解的精度。 严格来讲，在有限群体和有限迭代次数下，o a 搜索行为不是全域上的完全 随机化搜索，解空间中的各个解被探索到的概率不一样。s a 和其他算法的搜索 行为也是样。因此，我们称之为广域