（电力系统及其自动化专业论文）基于免疫遗传算法的电力市场竞价方法.pdf

a b s t r a c t w i t ht h em e r g i n g0 fl h ep o w c rm a r k c ti nc h i n a ，p o w e fp l a n t sw e r c f h c e dw i t has c r i o u sc h a l l c n g e t h cp o w c rm a r k c t0 ng e n e r a t i o n - s i d eo f s e p a r a t i n gp o w c rp l a n t s f r o m p o w c fg r i d a n dg c n e r a t i o n b i d d i n gw i l l b e c o m et h em a i no p c r a t i n gm o d e li no u rh o m e t o w n i ti s n c c e s s a r yt o i m p r o v cs o c i a lb c n c f i t sa n dr c d u c et h ep u r c h a s i n gp r i c ew i t ht h em a t u r c p o w e ft e c h n o l o g y t h i st h e s i sr c s e a r c h e s0 nb i d d i n gm e t h o do fp o w c r m a r k e t ，a c c o r d i n gt 0 t h cd c v e l o p m c n td i r e c t i o no fp o w e rm a r k c ti no u r c o u n t f y a tf i r s t ，t h i st h c s i sa n a l y z c st h ee m e r g e n tp r o b l c mn e e d e dt ob es o l v c d i np o w e rm a r k c ta n dg i v c ss o m eb a c l 【g r o u n da b o u tp o w c rm a r k e t ；s e c o n d l y ， g c n c f a t i o nc o s tc u r v eh a sb c c na n a l y z e di nt h i st h e s i s ，w h i c hg e n e r a t i o n c o s ti sp r i m a r yp a f to fe l e c t r i c a lp r i c c ；a n dt h c n ，t h eb i d d i n gm o d e l sa n d p r i n c i p l co fp o w c rm a r k e th a sb e e nd c s c r i b e dd e t a i l c d ；a tl a s t ，t h et h c s i s p r e s c n t sab i d d i n gm e t h o db a s e di m m u n cg c n e t i ca l g o r i t h m a tp r e s e n t ，t h e f ca r cs om a n yt y p e so fg e n c r a t i o nb i d d i n ga l g o r i t h m s c o m 血o n l yu s c di nd c r e g u l a t i o ne n v i f o n m e n t ，l i k et h ec q u a lb i d d i n gp r i c c m c t h o d ，m e r i t - o r d e rm e t h o d ，t h ed y n a m i cp f o g r a m m i n gm e t h o da n ds oo n b u tt h c yh a v eb i gi i m i t a t i o n ，b e c a u s ct h c yc a nb eu s c dt 0s o l v cd i f f c f e n t b i d d i n gc u r v e sr e s p c c t i v e l ya n dd c a lw i t hv a f i o u ss e t s o fc o n s t r a i n t s i m m u n ca 1 9 0 r i t h mi sai m m u n es y s t e m s i m u l a t i n gb i o l o g i c a li m m u n c s y s t e m ， i nw h i c ht h ea n t i g c na n da n t i b o d i c sa r e c a t e g o r i z c d a st h e o b j e c t i v c f u n c t i o na n dt h es o l u t i o n f e s p c c t i v e l y t h ea n t i b o d yt h a t c o m b i n c dp e r f c c l c dw “ht h ea n t i g e ni sd e e m e dt h e0 p t i m u ms o i u t i o nt ot h e p r o b l e m 0 n ei m m u n eg e n e t i ca l g o r i t h mh a sb c e ne x p l o r e df o rb i d d i n go f p o w c rm a r k e ti nt h i st h e s i s ，w h i c h0 p e n su po n cn c wk i n do fa p p r o a c ht 0 s o l v ct h ep r o b l e mo fb i d d i n ga f t c rt h ee n c o d i n gs t y l e ，i m m u n e0 p e r a t o f ，t h e m c t h o dt o g e tt h ci m m u n i t ya n dr e p u l s i o n ， t h c c h o o s i n g m e t h o d0 f a n t i b o d ya n dt h er c n e w i n gm c t h o do ft h ea n t i b o d ym e m o r yb a n kh a v eb e e n c o n f i r m c di nt h i st h e s i s t h et y p i c a lc o m p u t a t i o n a le x a m p l es h o w st h a tp f e s e n t c da l g o r i t h mi s an e we f f c c t i v eo p t i m a lm e t h o d ，a si tc a no b t a i nb e t t c rr c s u l ta n dh a sf a s t e r n c o n v e r g e n c cs p e e d ，a n da l s o i th a sa p p r o x i m a t e l yl i n e a rc o m p u t a t i o n a l c o m p l e x i t y k e yw o r d s ：p o w e rm a r k e t ；b i d d i n g ；b i d d i n gm o d e i ；i m m h n eg e n e t i c a i g o r i t h m i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 多l 描趱 日期：，唧年5 月二弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复目l 件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名：剖落通 导师躲辅 日期：砰多月3 5 日 日期：9 叼年多月z 岁日 第一章绪论 1 1 电力市场背景 1 1 1 电力市场的形成 在2 0 世纪早期，电力系统充分显示了规模经济的优越性，它可以随 着系统规模的扩展而提供较低的电价和较高的系统可靠性。然而，自2 0 世纪6 0 年代以来，情况发生了变化。电力工业高度垄断的某些负面影响 显现了出来，主要表现为非生产性成本加大。在西方发达国家，电力工 业的规模经济性已逐渐饱和，发电机组的效率已接近或达到了极限，建 造更大的发电机组已不能再大幅度降低成本，输电网络规模的简单扩展 ( 互联除外) 也不能继续保持需求的增加。成本的增加以及在电价受到 管制的情况下，政府要为此承受巨大的财政负担。为了消除这些负面影 响，2 0 世纪8 0 年代末期，一些国家开始放松对电力工业的管制，实施 电力工业重组，建立竞争性的电力市场( c o m p e t i t i v cm a r k c t ) 。这里，“电 力市场”是相对传统的垄断电力工业而言的，它是实现电力工业结构重 组而引入商业竞争机制后的一大类新型电力工业资产结构、经营管理和 运行管理模式的总称。从技术上讲，电力市场是应用计算机、现代化的 测量和通信等设备，以电价作为控制电力交易的杠杆，进行负荷管理、 控制电力系统的运行，在电力生产者、电力消费者和输配电网络管理者 之问实行平等、公正的等价交换的系统之总称m 。 到目前为止，全球有不少国家都进行了电力工业的市场化改革。1 9 9 0 年英国电力工业全面走向市场化并取得初步成功，引起世界许多国家的 仿效，美国、日本、澳大利亚、挪威、瑞典、新西兰、印度、阿根廷、 巴西、智利及东欧国家都先后卷入了这股电力工业改革的洪流。上述这 些国家的成功经验表明，实行电力市场，可促使电力企业从市场竞争中 寻找契机，吸引投资，推进技术改造，提高资源配置，降低能耗，提高 效率，减少成本，节约资源；可促使电力企业深化改革，为广大客户提 供低价、优质、高效的用电服务。 1 1 2 电力市场的交易和运营模式 目前，各个国家的电力市场主要分为三部分：发电市场、输电市场 和供电市场。目前多数国家都是在仅开放发电市场的情况下，进行电力 市场竞价。在发电市场，大多数国家采用“厂网分开，竞价上网”的方 式进行电力商业化运营。它们大致可分为两类：第一类是原来由政府垂 直管理并经营电力系统的国家，其改革模式一般采取发电与电网分开， 并逐步开放电力销售市场，而调度和市场运营机构仍与电网紧密结合， 如英国、西班牙、阿根廷等国家；第二类是原来政府不直接管理、经营 电力系统的国家，其改革模式一般是新成立独立的系统运行及电力交易 机构，各电力公司仍可拥有电厂和电网，配电市场逐步开放，这一类国 家如美国、德国、日本等。 我国自实行集资办电、多渠道筹资办电、多种形式利用外资办电的 方针以来，极大地调动了国内外投资者和经营者的积极性，出现了一大 批独立发电企业，缓解了严重缺电的局面；近年来，随着举世瞩目的三 峡水利枢纽工程和输变电工程的顺利进展，以及西部开发、西电东送战 略的实施，我国将逐步在跨省的基础上实现全国联网。以上这些都为电 力市场的发展创造了条件。由于多年来已形成一套由国家统一管理电力 系统的纵向体制，所以从整体看，我国更接近上述第一类模式。这种模 式的显著特点是调度机构、交易机构与电网公司紧密结合，而不另设独 立的调度机构。在我国实行这种模式同时是考虑到以下因素： ( 1 ) 实行调度机梅、交易机构和电网公司合为一体后，交易环节和 协调环节减少，交易技术系统简化，交易成本降低，因为这时相互之间 传送数据的工作将大大减少。 ( 2 )目前，我国电网比较薄弱，在负荷发展以后，输电、配电网络 往往是发、用电的“瓶颈”。调度机构、交易机构和电网公司合为一体后， 网络的容量极限可以由调度随着机组排序的变化及电网运行情况及时计 算修正，这样可以尽最大可能地满足交易的需要。 ( 3 ) 无功、备用等辅助服务可以由调度统一安捧，这样有助于提高 电网运行的可靠性和电能质量，同时降低交易执行的难度。 ( 4 ) 鉴于我国在长期传统的统一调度模式下所形成的各方利益关 系以及所积累的运行经验，采用调度机构、交易机构和电网公司合为一 体的市场机制有助于调动各方的积极性，从而更快地推进电力市场的完 善和健全。 电力交易主要有竞价上网方式、双边交易及期货交易等多种交易形 式。其中开展期货交易的一个主要特征就是允许电力合同的买卖，也可 以委托某个电力交易所交易。期货合同在带来交易灵活性的同时，也给 电力系统带来了很大的风险。现货交易是针对第二天2 4 小时确定的电力 交易，以小时为段，共2 4 个时段。以北欧电力市场m 为例，在上午1 1 2 点以前，北欧电力交易所从各国电网公司获取网络运行信息：上午1 2 点以前，各电力公司通过电子邮件的方式，向北欧电力交易所申报第二 天每时段的交易数据，包括交易电量( 以兆瓦时为单位) 和最高、最低 价格。该现货价格一般均高于月度合同电价。所以，为了降低购电成本， 电力公司均签定大量的期货合同。 每个国家应根据本国国情做具体分析，决定采用何种交易。例如， 英国新的电力市场以双边合同为主的n e t a 模式已完全取代了集中交易 的p o o l 模式n ，而美国电力市场中竞价上网是主要的交易方式m 在我 国电力工业存在国家投资、外资、合资、股份、地方等多种形式，产权 呈现多元化，形成了利益主体多元化“，选择何种交易方式与运营模式 涉及多方利益，是电力规划中应认真研究的问题。建立合理的电力市场 结构的重要内容之一就是建立市场的合理的交易方式，合理的交易方式 可以导致电力市场朝提高效率，降低成本的方向发展。 1 2 电力竞价综述 1 2 1 发电厂成本曲线的分析 发电厂竞价时，竞标成功后的利润大小是与自己电厂的设备性能及 成本曲线密切相关的。大机组、高参数的电厂竞争力就比小机组的电厂 竞争力强。所以，在电力市场中，研究发电报价首先要研究市场采取何 种形式的报价曲线，以及报价曲线与生产成本的关系。即发电厂一定要 根据自己的成本曲线来构建自己的竞价曲线。另外，如果发电厂的成本 单价曲线和市场要求的竞价曲线不一致，还要对发电报价曲线做相应的 处理，要根据成本单价曲线来制定市场要求的竞价曲线。 发电成本包括燃料费、管理费、检修费和发展费。参与竞价的单位 可以是机组、发电厂或发电公司，竞价的周期可以是年、月、日或小时。 下面先研究单段发电成本曲线，包括二次成本曲线和线性成本两种情况。 通常认为发电成本是发电功率的二次函数，即对发电公司( 或发电 厂或发电机组) f ，设发电功率只在短时间( 如一小时) 内恒定不变，则 一小时内发电公司的发电成本c ；与发电功率问有如下的二次函数关 系： c fi 口j 弓2 + 岛只+ d j ( 1 1 ) 式中口；、i 和d ；为发电公司( 或发电厂或发电机组) f 的成本曲线系数， 可以通过对发电成本的统计分析获得；f 一1 ，2 ，m 为发电公司( 或发电厂 或发电机组) 的编号，m 为系统中参与竞标的发电公司总个数。发电成 3 本二次曲线如图l 1 所示。 c f c m q 只柚 只一 图1 1 c 为发电功率只的= 次曲线 如果发电公司的发电功率维持恒定的时间f ( 分钟) 不足一小时或 大于一小时( 发电功率就增大或减小到另一定值) ，则其实际消耗的成本 应在上式的右边乘以系数( f 6 0 ) ，即乘以实际恒定出力的小时数。 上式两边同时除以发电功率只( 严格的说应该是发电量 只似彤) 1 伪) ) ，即得该发电公司的发电成本单价曲线为( 见图1 1 ) ： o g 一口j + 岛+ 詈 ( 1 2 ) c 。即为发电公司f 的发电成本单价( 元( 肭) ，显然，q 不是常数。 它随着发电出力的变化而变化。 对发电成本c 与发电功率只的二次函数关系式两边对发电功率e 求 导，即得发电公司f 的微增成本曲线( 见图1 1 ) ： j f 、 c ；一等一只+ 包 ( 1 3 ) p f 即当发电公司的发电出力为只时，若发电功率增大1 个单位( 邢) ，则 一小时内发电公司的发电成本将增大c ：( 元) 。 综上，发电成本曲线c 为二次函数时，发电成本单价曲线c 。为双曲 线，发电成本微增曲线c 坝u 为一次函数。 1 2 2 竞价模式 随着资产重组、厂网分开等电力体制改革措施的逐步到位，建立电 力市场，实行竞价上网“”将是目前及下一步电力体制改革的重要内容。 由于发电公司与电网公司之间原有的行政隶属关系不复存在，形成了平 4 等的经济关系，电网公司不能直接向独立发电公司下达行政命令，涉及 生产和经营上的各种问题，只能通过合同、协议来解决，“竞价上网”必 须以实现最大范围内的资源优化配置为目标，在保证电网安全稳定运行 的基础上，以最小的购电成本满足负荷要求。 竞价上网模式与算法的研究是电力市场理论的难点，竞价模式具有 很强的随机性和实时性要求，对电力市场的竞争力度运行方式有很大的 影响，关系到电力市场的经济效益和电力系统的安全及可靠性。研究发 现电厂的实时发电成本核算是竞价上网电价制定的基础工作，目前实时 电价已成为许多国家的一项主要研究课题，美、英等国已开始实行有限 的实时电价运行模式，使发、供、用各方都能更有效合理地利用电力资 源。目前国内一些试点的电力市场已经采用国家发改委拟荐的电力市场 竞价模式，归纳起来主要有3 种：“有限电量”竞争模式、“差价合约” 竞价模式及“两部制电价”竞争模式”“。 ( 1 ) 有限电量竞价模式是指上网电价实行单一制形式，一部分电量 按照合同规定上网并按政府核准的上网电价结算；另一部分电量参与现 货市场竟价，并按市场价格结算。国内电力市场试点单位中，上海、山 东、东北电力市场基本上都采用的是这种模式。 一 ( 2 ) 差价合约竞价模式是指上网电价实行单一制形式，全部电量参 与现货市场竟价，但结算分为合约电量收入和差价合约收入两部分，即 r q ：只+ b 良一q 归乙 ( 1 4 ) 或 r 。皱只+ 僻一只胁 ( 1 5 ) 式中r 为发电企业收入，q c 为合约电量，只为合约电价，皱为市场交易 电量，己为市场交易价格。其中式( 1 4 ) 的经济意义为：发电企业的 收入由合约电量收入和差价合约收入两部分组成，合约电量收入由有关 部门规定的合约( 计翅 ) 电量乘以政府价格部门规定的电价形成；差价 合约收入则可以理解为合约以外电量的收入，它是由发电企业参与现货 市场竞价的交易电量与合约电量之差乘以现货市场交易价格形成，这部 分收入是不明确的，可正可负。式( 1 5 ) 的经济意义为：发电企业的收 入由市场交易电量收入和差价合约收入两部分组成，市场交易电量收入 由市场交易电量乘以市场价格形成，差价合约收入是由合约电价与市场 交易价格之差乘以合约电量形成，这部分收入是不确定的，可正可负。 这样的机制比较好地保证和平衡了购售电双方的利益，避免了市场价格 的风险。目前国内市场试点单位中，浙江电力市场即采用的是这种模式。 5 ( 3 ) 两部制电价模式( 又称霍普森电价) ，即上网电价由容量电价 和电量电价两部分组成，电价分别根据电厂的固定成本与变动成本来作 价，以容量电价来反映固定成本的补偿，以电量电价反映变动成本的补 偿，前者由政府根据平均成本来定制，后者由市场竞争形成，东北区域 电力市场采用此模式。 1 2 3 竞价方法 文献 9 2 0 针对发电竞价模式提出了许多模型和算法。 文献 9 完整地描述了电力市场的竞价模型。首先确定竞价数学模型 的目标函数，在发电、输电、配电市场全面开放的条件下，目标函数是 社会效益最高；而在仅开放发电市场的条件下，目标函数是购电费用最 低。目标函数按市场结算规则分为两种：电网统一边际成本结算的购电 费用最低和按各发电机组实际报价结算的购电费用兄最低的。然后按 不同的被控变量，列出了3 类约束条件：功率与容量、时间、电网安全。 以上2 类目标函数和3 类约束条件只是经典竞价问题的描述，实际还可 能出现网损、交换功率、辅助服务、竞价比例等问题。最后详述了竞价 原理。 发电竞价可能用到的主要算法：排队法、等报价法( 或等微增率法) 、 动态规划法、网络流规法和线性规划法等，它们分别适应于不同类型的 报价曲线，解决不同类型的约束条件。文献 1 0 卜 1 4 分别介绍了上述的 5 种方法。 ( 1 ) 排队法，也称优先级法既可以用于解决机组经济组合或机组开 停问题，又可以用于解决机组经济功率分配问题，同时还可以用做动态 规划机组经济组合的初始状态。捧队法可以用于各种周期包括年、月、 日的计划、校正和控制以及实时调度之中一。其使用条件是报价必须是 分段水平线( 阶梯形) 。该方法可用来解决机组组合问题和功率分配问题。 其优点是简单快速，但仅适用于常数( 或多段常数) ，处理第2 类约束( 时 间) 和第3 类约束( 电网安全) 问题较困难。 ( 2 ) 等报价法( 或称等微增率法) 它是发电竞价的基本算法，其数学 实质是利用线性方程法、牛顿内插法、合成曲线( 等值) 法和夹板二分 法等方法解一维非线性方程- ，。此方法只要报价曲线是不下降的，无论 在斜线段、水平段或垂直段均能可靠收敛；计算速度足够快，在自动发 电控制( a g c ) 的实时经济控制中也用此方法。但是它只能在已运行的 机组问竞价分配发电功率，机组的起停状态需用其他算法确定；在下降 报价特性时，等报价准则不能导致购电费用最低。 6 ( 3 ) 动态规划法它可以用来解决发电竞价中的机组组合与功率分配 问题。其优点有：能够针对任何形状的报价曲线，可以包含下降段，甚 至是波动起伏的特性；在机组组合模型中可以考虑时间启动费用和启停 约束“”。其缺点是：目前功率分配采用的是离散型动态规划，如果分割 状态的步长小，则计算量大；如果步长大，则计算精度低。机组组合的 动态规划解法的困难在于状态量过多，一般采用带状域法，但在不同时 段发电报价变化过大时，难以找到带状区，而松弛法又容易出现不收敛 问题。 ( 4 ) 网络流规划法它是电力市场分析中最有前途的算法，其特点是： 竞价过程非常简单、直观：可以用于一日前计划和一小时前计划，更适 合做实时调整和电力拍卖；可以解决各种约束问题，特别是与时间相关 的约束和与网络相关的约束m ，。 网络流规划法非常适合竞价，计算原理符合市场操作过程，它能解 决其他一些竞价算法难以解决的时间约束和网络安全类约束问题。 ( 5 ) 线性规划法在文献【9 l 中竞价模型的目标函数及约束条件( 不 考虑网损时) 基本是线性模型，由此引入线性规划作为竞价算法n ”。其 优点是：快速、可靠，能有效地处理网络安全约束；可以直接解决与时 间有关的约束；能无障碍地使用报价的下降特性。其缺点是：处理网损 比较麻烦；逐次线性化会造成计算精度的损失。线性规划适合用于发电 竞价问题，可以比较方便、快捷地处理各种约束，取得理想的优化结果。 文献【1 5 】提出了在电力市场环境下，发电商可以通过策略性报价来 最大化自己的收益，其竟价过程可以被描述成一个不完全信息的非合作 博奕过程。文中在分析策略性报价方法研究现状的基础上，提出了电厂 优化报价问题的数学模型，并给出了基于博奕论和概率论的求解方法。 文献【1 6 】提出一种可通用的有功功率和无功功率的电价计算方法。 该方法是通过一降幂方程来识别有功和无功的子问题。分析一个用来刺 激代理商参与电力市场反功率价格计算的模型。一个最优化功率流程解 决了反功率的子问题，就是在目标函数中考虑反功率的生产成本及有用 功率损失最小得以实现。采用非线性设计方法解决最优功率流程从而得 到有用功率及反功率的边际成本。最后用9 台机组及一些负载的系统来 检测该方法的有效性。 文献【1 7 】提出了一个旨在帮助电力市场中的发电商在能量交易市场 中进行合理报价的综合竞价模式。激励发电商或用户进行报价的主要因 素之一就是希望他们能够从交易市场上获得最大收益回报，有些市场参 与者所关心的可能是发电厂或发电机平均运行成本的最小化，而不是收 7 益或利润的绝对最大化；有些市场参与者，希望按照预先确定的日总发 电量或投资成本来竞争。文中针对这些能量交易市场中不同发电商的目 标进行了探讨，并提出了一个综合竞价模型，同时详细列出了用该模型 计算出的一个拥有5 台发电机组的火力发电厂的报价结算结果。 文献【1 8 】提出了一种具体的分段竞价电力市场的出清算法，考虑将 日负荷预测曲线自下而上水平分成基荷段、腰荷段和峰荷段；基荷段和 腰荷段的分界点由日负荷曲线的最小值确定，再按照报价由低到高的顺 序分配腰、峰荷负荷，根据机组爬坡约束进行调整；最后以总购电费用 最小为目标，优化调整腰荷段和峰荷段的分界点以及基荷机组的组合， 达到总体购电费甩最小。 文献【1 9 】指出在电力市场条件下，为保证参与的各电厂公平竞争， 必须按照各电厂的竞价胁线，合理分配各电厂的发电功率。目前，世界 各国的电力市场都是建立在实时电价理论基础上的，实时电价形成、竟 价与结算，采用分时竞价方式。但是，分时竞价电力市场存在弊端：对 于某一具体时段，目前按照该时段的统一出清价来结算，但该时段各电 厂所发电能质量、发电成本并不相同，这种趋势在日负荷陆线最大值附 近体现得越发明显，所以难以公平地区分电能的质量；其次，各时段竞 价的相对独立性不能很好地保证火电机组、核电机组或带有强迫出力的 水电机组生产的连续性。 文献f 2 0 1 就日前电力市场的竞价机制进行讨论，指出了当前普遍采 用的分时竞价机制存在的问题。在此基础上介绍了分段竞价机制，并重 点以包含3 4 台火电机组和1 7 台水电机组的实际电力系统为例，对分段 竞价与分时竞价这两种竞价机制进行了详细比较，分段竞价为电力市场 交易机制提出了一种新思路，可以将其用于p 0 0 l 模式竞价，提高市场 效率，也可以构成更有效、更规范的远期和期货市场。 1 3 仿生智能计算方法 1 3 1 遗传算法 1 3 1 1 遗传算法概述 遗传算法( g c n e t i ca l g o r i t h m s ，g a ) 是一种基于自然选择和群体遗 传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的繁殖、杂 交和突变现象。在利用g a 求解问题时，问题的每个可能的解都被编码成 一个“染色体”，即个体，若干个个体构成群体。遗传算法开始时，首先 随机地产生一些个体( 即初始解) 构成初始群体，根据预定的目标函数对 8 每个个体进行评价，得出一个适应度值，然后以此适应度值为依据，根 据“优胜劣汰”的原则来繁殖下一代的个体。“好”的个体被选择用来繁 殖，“坏”的个体则被淘汰。选择出来的个体经过交叉和变异算子进行 再组合生成新的一代群体，这一新群体中的个体继承了上一代的一些优 良性状，逐步朝着更优解的方向进化。因此，g a 可以看作是一个由可行 解组成的群体逐代进化的过程。所有的自然种类都是适应环境而得以生 存，这一自然适应性是遗传算法的主旋律。g a 搜索结合了达尔文适者 生存和随机信息交换，前者消除了解中不适应因素，后者利用了原有中 已有知识，从而有利的加快了搜索过程n ”。 1 3 1 2 遗传算法的步骤 g a 是建立在自然选择和群体遗传学机理基础上的随机、迭代、进 化，具有广泛适应性的搜索方法。下面举例说明基本方法： f ，杠，) ，z j ，协，) ，：) q ，f r ( 1 6 ) 要求k ，y 。，z 。) 使得( 不失一般性，假设求最大值) ，- ，) ，o ，z o ) - ，粤? ，协，y ，z ) ( 1 7 ) p p p 式中b ，y ，z ) 为自变量；q 是b ，y ，z ) 的定义域；x ，y ，z 可以是数值，也可以是 符号；f 为实数，是解的优劣程度或适应度的一种度量；，为解空间 b ，y ，z ) q 到实数域f r 的一种映射。g a 的求解步骤：器 ( 1 ) 编码用一定比特数的o ，1 二进制码对自变量x ，y ，z 进行 编码形成基因码链，每一码链代表一个个体，表示优化问题的一个解。 ( 2 ) 产生初始群体置遗传迭代次数f o ，随机产生捍个个体组成一 个初始群体p ( r ) 一p ( o ) ，该群体代表优化问题的一些可能解的集合。当然， 一般来说，p ( o ) 中个体的素质都很差，g a 的任务是要从初始群体p ( o ) 出 发，模拟进化过程，择优劣汰，最后得出非常优秀的个体。 ( 3 ) 评价按编码规则，将群体p ( f ) 中的每一个体的基因码所对应 的自变量取值( 而，只，盈) 代入f 算式，算出其函数值e 【f - 1 2 ，) 。e 较 大时，表示该个体有较高的适应度，更适应于，所定义的生存环境。适 应度e 为为群体进化时的选择提供了依据。 ( 4 ) 选择( 复制)按编码规则，在群体p ( f ) 中按概率曰选取m 对 个体，作为父辈用于繁殖后代，产生新的个体加入下一代群体p ( f + 1 ) 中。 一般概率既与e 成正比，就是说，适合于生存环境的优良个体将有更多 的繁殖后代的机会，从而使优良特性得以遗传。选择是g a 的关键，它 体现了自然界中适者生存的思想。 9 ( 5 ) 交叉对于选中的用于繁殖的每一对个体，随机地选择同一整 数摊，将双亲的基因码链在此位置相互交换。如个体z 、y 在位置3 经交 叉产生新个体z 、l ，他们组合了父辈个体z 、y 的特征，即 石x l x 2 工3 x 4 x 5l 1 0 0 ；1 0 j y k 匕匕l kl 0 1 0 i l l j l z - z l x 2 j 3 k ku 0 0 1 1 1 j y - k k 匕z 。邑【0 1 0 i l o j 交叉体现了自然界中信息交换的思想。 ( 6 ) 变异以一定概率己从群体耶+ 1 ) 中随机选取若干个体。对于 被选中的个体，随机选取某一位进行反运算，即由1 一o 或o 一1 。同自然 界一样，每一位发生变异的概率是很小的，变异模拟了生物进化过程中 的偶然基因突变现象。g a 的搜索能力主要是由选择和交叉赋予的。变 异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全 局收敛，它进一步增强了g a 的搜索能力。 对产生的新一代群体进行了重新评价、选择、交叉、变异，如此循 环往复，使群体中最优个体的适应度和平均适应度不断提高，直到最优 个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度值 不再提高，则迭代过程收敛，算法结束。 1 3 1 3 遗传算法的特点 ， ( 1 ) g a 处理参数集合的编码，即操作是在给定字符串上进行的； ( 2 ) g a 同时搜索解空间的许多点，而不是一个点，因而收敛速度 较快； ( 3 ) g a 只需要一个适应性函数( 性能指标) ，而不需要其导数或其 他辅助信息，因而具有广泛的适应性； ( 4 ) g a 使用概率规则指导搜索而不是确定性规则，因此能搜索离 散的有噪声的多峰值的复杂空间； ( 5 ) g a 在解空间内进行充分的搜索，但并不是盲目的穷举或瞎碰 ( 评价为选择提供依据) ，因此其搜索时耗和效率往往优于其他优化算 法。 1 3 1 4 遗传算法的改进 g a 作为一种基于自然选择和群体遗传机理的全局优化搜索算法，深 受实际工作者的喜爱，国内外学者对g a 进行了大量研究，取得了不少 令人鼓舞的成果，但目前仍存在一些问题，如： 1 0 ( 1 ) 适应度值标定方法多种多样，没有一个简洁、通用的方法，不 利于对遗传算法的使用。 ( 2 ) g a 的早熟现象( 即很快收敛到局部最优解而不是全局最优解) 是迄今为止最难处理的关键问题。 ( 3 ) 快要接近最优解时在最优解附近左右摆动，收敛较慢。 为此，很多学者分别从参数编码、初始群体设定、适应度函数标定、 遗传操作算子、控制参数的选择以及遗传算法的结构等方面来对改进g a 实际计算性能”。 文献 2 3 提出了一种具有自适应搜索能力的快速收敛遗传算法。在 计算过程中，设计变量的搜索范围依据每代自变量的数学期望和方差自 动进行调整，并且通过引入进化策略中的自适应高斯变异算子，对变异 算子进行改进，加速了算法的收敛性。该算法克服了传统遗传算法中设 计区间的给定具有一定盲目性的缺陷，在收敛性和鲁棒性方面均优于传 统的实数编码遗传算法。 1 3 1 5 遗传算法的应用 g a 提供了一种求解非线性、多模型、多目标等复杂系统优化问题 的通用框架，它不依赖于问题所属的具体领域。随着对g a 技术的不断 研究，人们对遗传算法的实际应用也越来越重视，它已经广泛地应用于 函数优化、组合优化、自动控制、机器入学、图象处理、人工生命、遗 传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包 问题、装箱问题、图形划分问题等方面取得了成功m ，。 文献 2 8 将投标竞价原则引入电力市场，建立了一种改进的投标 竞价数学模型，用遗传算法和网络流法进行优化。对1 2 节点系统作仿真， 结果合理且收敛性好。 1 3 2 免疫算法 人类和其他生物的免疫系统是一个由许多执行免疫功能的器官、组 织、细胞和分子等组成的复杂系统，其主要功能是识别并清除从体外入 侵的病原体及其产生的毒素和体内因基因突变产生的肿瘤细胞，实现免 疫防卫功能。免疫系统的结构如图1 2 所示。 执行免疫功能的细胞为淋巴细胞( 包括t 细胞和b 细胞) 。b 细胞 的主要作用是识别抗原和分泌抗体，t 细胞能够促进和抑制b 细胞的产 生与分化。当抗原入侵体内后，b 细胞分泌的抗体与抗原发生结合作用， 当它们之间的结合力超过一定限度时，分泌这种抗体的b 细胞将会克隆 扩增，产生大量相同和相似( 由于变异的作用) 的克隆。克隆扩增后， b 细胞的一部分克隆分化为记忆细胞，再次遇到相同抗原后能够迅速被 激活，实现对抗原的免疫记忆。b 细胞的克隆扩增受t 细胞的调节，当 b 细胞的浓度增加到一定程度时，t 细胞对b 细胞产生抑制作甩，从而 防止b 细胞的无限复制。 田1 ：2 免疫系统基本结构 免疫系统是由许多分布式的具有一定功能的个体( t 细胞、b 细胞、 抗体和细胞因子等) 通过相互作用形成一个复杂的动态大系统的典型俩 子，具有个体特异性( 一种免疫细胞仅对特定的抗原起作用) 和整体多 样性( 免疫系统几乎对所有抗原都能进行处理) 的双重特点，具备学习、 记忆、自我调整、“模式识别和特征提取能力。免疫系统的特性引起了众 多领域学者的注意，人们开始运用免疫系统的机理构造人工智能系统来 解决工程领域的阿题，如计算机安全、模式识掰，燥声处理，反馈控制 器设计n ”等。 免疫系统对外来抗原的识别过程是一个寻找能够与抗原结合力最大 的抗体的过程，而又有其不同于生物进化过程的特点。大量的b 淋巴细 胞在骨髓中产生后进入淋巴循环，通过分泌的抗体与抗原结合而受到抗 原的激励作用，结合越紧密，激励作用越强，反之越弱。同时，b 细胞 之间也会产生相互激励和抑制的作用。细胞受激励作用强到一定程度， 细胞就会成熟，产生很强的复制和分化，大部分分化为浆细胞以消灭抗 原，一部分分化为记忆细胞。抗原被消灭后，产生抑制成熟b 细胞的抑 制细胞，受到抑制的b 细胞会逐渐被淘汰。 根据免疫系统响应的作用原理，许多学者提出了不同的人工免疫算 法或免疫进化算法，来解决优化问题”。m o r i 等人提出一种二进制编 码的人工免疫优化算法“，其主要思路是将抗原对应于目标函数和约束 条件，抗原对应于搜索空间的解，依据抗原和抗体的信息熵定义抗原与 1 2 抗体的结合力以及抗体之问的结合力对解进行评价和选择，通过记忆细 胞保留局部最优解以保证解的多样性。本论文将在第三章介绍免疫算法 的种类、计算步骤、特点及全局收敛性分析。 1 3 3d n a 计算 d n a 计算是伴随着分子生物学的兴起和发展而出现的，其核心问题 是将经过编码后的d n a 链作为输入，在试管内经过一定时间完成控制的 生物化学反应，以此来完成运算，使得从反应后的产物及溶液中能得到 全部的解空间n ”。理论上，d n a 计算基于大量d n a 分子自然的并行操 作及生化处理技术，通过产生类似某种数学过程的一种组合结果并对其 进行抽取和检测来完成。d n a 分子模型大体划分为非限制性模型和限制 性模型两类，这两个阶段均由多个d n a 操作组成。每一种操作都能并 行执行，这些操作构成分子计算机的基本指令。一些有序、特定的分子 操作指令的集合可构成分子计算机上的程序或算法。 ld n a 的结构 ， d n a 是重要的基因物质，携带着生物的遗传信息，d n a 的基本元 素是核苷酸。由于化学结构的不同，苷酸划分为4 类碱基( b a s e s ) ：嘌呤 ( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 。d n a 由两条核苷酸键组成， 两条极长的核苷酸键利用碱基之间的氢键而结合在一起，成一条双股的 螺旋结构，一股中的碱基序列与另：股中的碱基序列互补。a 和t 配对， c 和g 配对。传信息以a 、t 、c 、g 在核苷酸中的排列顺序而体现，排 列序列的多样性构成了丰富的遗传信息。 2 d n a 的计算机理 d n a 算法解决计算问题的基本思想是：用d n a 特殊的双螺旋结构 和碱基互补配对原则，计算问题进行编码，要运算的对象映射成d n a 分子链，在d n a 溶液的试管里，生物酶的作用下，生成各种数据池( d a t a l p 0 0 1 ) ，后按照一定的规则将原始问题的数据运算、高度并行地映射成 d n a 分子链的可控的生化过程。用分子生物技术如聚合酶链反应( p c r ) 、 聚合重叠放大技术( p o a ) 、超声波降解、亲和层析、克隆、诱变、分子 纯化、电泳、磁珠分离等分子生物学技术。获得最终运算结果。 3 d n a 的数学机理 从d n a 的原理来看，它与数学操作非常类似。单股d n a 可看作由4 个不同符号a 、g 、c 、t 组成的串，它在数学上就像电子计算机中编码“o ” 和“1 ” 一样，可表示成4 字母的集合= a ，g c ，t 来译码信息。酶可 看作模拟在d n a 序列上简单的计算，不同的酶用于不同的算子，如限 制内核酸酶可作为分离算子，d n a 结合酶可作为绑结算子，d n a 聚合 酶可作为复制算子，外核酸酶可作为删除算子等n “。 4 d n a 算法的步骤 ( 1 ) 编码即将所要解决的闯题映射为一个d n a 分子的集合； 编码是d n a 计算的第一步，也是最重要的一步，编码质量的好坏 直接影响反应过程的速度和效率”。影响编码的因素有：化学自由能 g ；解链温度l ；d n a 分子的组成；编码的距离。 ( 2 ) 计算即进行各种生化反应如杂交、连接及延伸等生成可能解空 间； ( 3 ) 解的分离和读取( 如4 5 6 反应和凝胶电泳) 。 5 d n a 算法的特点 ( 1 ) d n a 算法具有高度的并行性，运算速度快； ( 2 ) d n a 作为信息的载体其贮存的容量非常之大，每立方米的d n a 溶液可存储1 万亿的二进制数据，远远超过目前所有电子计算机的总储 存量； ( 3 ) d n a 计算所消耗的能量只有一台电子计算机完成同样计算所消 耗的能量的十亿分之一。 d n a 计算的上述特性，即运算的高度并行性、大容量、低消耗是目 前计算机和并行计算机所无法比拟的，。从这个意义上说，1 9 9 4 年由 a d i e m a n 所开创的生物计算技术具有划时代的意义。 1 3 4 蚁群算法 蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 是一种新型的模拟进化算 法1 。该算法是由意大科学者m d o r i g o 、v m a n i e z z o 、a c o l o r n i 等人在 2 0 世纪9 0 年代初首先提出来的，称之为蚁群系统( a n ta l g o r i t h m ， a a ) 。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络 算法等启发搜索式算法以后的又种应用于组合优化问题的启发式搜索 算法。 1 3 4 1 基本原理 蚁群算法是受到对真实的蚁群行为研究的启发而得出的。像蚂蚁、 蜜蜂、飞蛾等群居昆虫，虽然单个昆虫的行为极其简单，但由单个简单 的个体所组成的群体却表现出极其复杂的行为，原因是什么呢? 仿生学 家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素 ( p h e r o m o n e ) 的物质进行信息传递的，蚂蚁在运动过程中，能够在它 所经过的路径上留下该种物质，而且蚂蚁组成的蚁群的集体行为便表现 1 4 出一种信息正反馈现象：某路径上走过的蚂蚁越多，则后来者选择该路 径的概率就越大，蚂蚁个体之间就是通过这种信息的交流达到搜索事物 的目的。 人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含 “外激素”浓度较大的路径；区别在于，人工蚁群具有一定的记忆能力， 它能够记忆已经访问过的节点；另外，人工蚁群在选择下一条路径的时 候并不是完全盲目的，而是按一定的算法规律有意识地寻找最短路径( 如 在t s p 问题中，可以预先知道下一个目标的距离) 。 该