（电力系统及其自动化专业论文）电力系统安全经济运行的计算智能模型及方法研究.pdf

上海交通大学博士后研究工作报告 摘要 建立了一个同时考虑经济、环境和安全指标的电网多目标优化运行模型。为了充 分地体现电力决策者对某目标的偏好程度，本文将数学优化技术与进化计算方法相结 合，并针对该多目标优化问题进行了相应的决策分析。 关键词：蚁群算法，收敛性分析，转移概率，机组启停，可靠性，潮流计算，模糊集 理论，多目标规划，优化模型，决策分析 1 1 上海交通大学博士后研究工作报告a b st f a c t a b s t r a c t i ti sa l li n e v i t a b l et e n d e n c yf o rt h ed e v e l o p m e n to fm o d e m p o w e rs y s t e m st oi n c r e a s e s y s t e mc a p a c i t y , c o n s t r u c te x t r a - v o l t a g eg r i da n df o m - ii n t e r c o n n e c t i o ns y s t e m w i 也t h e i n c r e a s i n g o f s y s t e ms i z e ，h o w e v e r ，t h e s t r u c t u r eo fg r i db e c o m e sm o r ea n dm o r e c o m p l i c a t e ds ot h a tt h el i k e l i h o o do fs y s t e mf a i l u r eb e c o m e s m o r ea n dm o r eh i g h e ra sw e l l ， f u r t h e r m o r e ，h o wt or e a s o n a b l ys c h e d u l et h eo p e r a t i n gm o d eo fs y s t e mf o rt h eb u l k y i n t e r c o r m e c t i o ns y s t e m w h i c hi st o s a r i s f y t l l el o a dd e m a n dw i t hm i n i m u m s y s t e m p r o d u c t i o nc o s t , i st h ee c o n o m i c a le f f i c i e n c yp r o b l e mo f e l e c t r i cp o w e r s y s t e mo p e r a t i o n i t w i l i b r i n gs o c i e t y t h e h u g e e c o n o m i cb e n e f i t s s o s r u d y i n go nt h es e c u r i t y e c o n o m i c o p e r a t i o no fp o w e rs y s t e m s i sac o m p r e h e n s i v ep r o b l e mv e r yc a r e db yp o w e ri n d u s t r y 1 1 1 i s t h e s i sh a s c o m p r e h e n s i v e l ye m p l o y e de v o l u t i o n a r yc o m p u t a t i o nt h e o r y , o p t i m i z a t i o n t e c h n i q u e ，f u z z ys e t st h e o r ya n dp r o b a b i l i t yt h e o r y t om a k e s y s t e m a t i ca n dt h o r o u g hs t u d i e s o nt h ec o m p u t a t i o n a l i n t e l l i g e n c et h e o r ya n ds e c u r i t ye c o n o m i co p e r a t i o no f p o w e rs y s t e m s s o m en e wi d e a sa n dm e t h o d sh a v eb e e np u tf o r w a r d t h em a i na c h i e v e m e n t sa r ea sf o l l o w s an o v e la n tc o l o n yo p t i m i z a t i o na l g o r i t h mw i t hr a n d o mp e r t u r b a t i o nb e h a v i o r ( r p a c o ) b a s e do nc o m b i n a t i o no fg e n e r a la n tc o l o n yo p t i m i z a t i o na n ds t o c h a s t i cm e c h a n i s mi s d e v e l o p e d i nt h i s p a p e r s o m ec o n v e r g e n c ep r o p e r t i e s f o rt h e p r o p o s e d m e t h o da r e e x p l o r i n g l ys t u d i e d i np a r t i c u l a r , w ep r o v et h a tf o ra n y s m a l lc o n s t a n t e 0 ，t h ea p p r o a c h w i l lc o n v e r g et oa no p t i m a ls o l u t i o na tl e a s to n c ew i t hp r o b a b i l i t y1 一占d u r i n gt h ef i n i t e i t e r a t i o n sa n dt h e p r o b a b i l i t y t e n d st o 1f o rt h e e n o u 【g hl a r g e n u m b e ro fi t e r a t i o n s f u r t h e r m o r e ，t h ee m p i r i c a lm e t h o do ff i n d i n go p t i m a lp a r a m e t e rs e t t i n g sb a s e d o nt h et s p p r o b l e mv i as i m u l a t i n gal a r g en u m b e r o ft r i a l si su s e di nt h i sp a p e r , a n df i n a l l yt h eo p t i m a l n u m e r i ca r e ao fp a r a m e t e r sc a nb eo b t a i n e d c o n s i d e rt h el i k e l i h o o do fg e n e r a t i n gu n i tf a i l u r e ，ac e r t a i ng e n e r a t i o nr e s e r v es h o u l d b ee s t a b l i s h o d i nt h i st h e s i s t h ep r o b a b i l i s t i ct e c h n i q u e ，s e c u r i t yf u n c t i o nm e t h o d ，i su s e dt o e v a l u a t et h es p i n n i n gr e s e r v er e q u i r e m e n t so fs y s t e mb a s e do nt h es o l u t i o no fo p t i m a lu n i t c o m m i t m e n tp r o b l e m ，a n da n tc o l o n yo p t i m i z a t i o na l g o r i t h mw i t hr a n d o mp e r t u r b a t i o n b e h a v i o rd e v e l o p e di nt h i sp a p e ri sa p p l i e dt ot h es o l u t i o no ft h eo p t i m i z a t i o nm o d e l s o m e c o r r e s p o n d h a gt e c h n i c a lp r o b l e m s ，s u c ha st r a n s f o r m a t i o no fm o d e l ，h a n d l i n go f c o n s t r a i n t s e ta l ，a r ee x p l o r i n g l ys t u d i e dd u r i n go p t i m i z a t i o n i nv i e wo ft h ei n t r i n s i cu n c e r t a i n t yp h e n o m e n o ni ne l e c t r i cp o w e rs y s t e mo p e r a t i o n ， t h em e t h o do ff u z z yp o w e rf l o wa n a l y s i si se x t e n d e df r o md cm o d e lt oa co n e ，a n da n o n l i n e a rm o d e li sc o n s t r u c t e dt o o b t a i nt h e p o s s i b i l i t y d i s t r i b u t i o no fp o w e rf l o w e f f i c i e n t l yi na c c o r d a n c ew i t h t h ec o r r e s p o n d i n gf u z z ys e t st h e o r y s o m et e c h n i c a lp r o b l e m s ， s u c ha st h es o l u t i o nf o rt h en o n l i n e a rf u z z yp o w e rf l o we ta 1 ，i s s t u d i e df u r t h e r f o r u t i l i z a t i o n t h ef i c t i t i o u sf l o wp h e n o m e n o ni sc o n s i d e r e di nt h ef u z z yp o w e r f l o wa n a l y s i s a n da ne 伍c i e n ta l g o r i t h mo ff u z z ye c o n o m i cp o w e rd i s p a t c hi sp r e s e n t e dt oc a l c u l a t et h e p o s s i b i l i t yd i s t r i b u t i o no f t h eo u t p u to f d i s p a t c h i n g u n i t s i nt h i st h e s i s ，am o r ep r a c t i c a la n dt h o r o r 【g hm o d e li sp r o p o s e da n dt h em u l t i p l e 1 1 1 一 上海交通大学博士后研究工作报告 o b j e c t i v e sf o rt h eo p t i m a lo p e r a t i o ns o l u t i o na r ec o n s i d e r e da se c o n o m i c ，e n v i r o n m e n t a l p o l l u t i o na n ds e c u r i t yi n d e x i no r d e rt os h o w t h ep r e f e r r e dd e g r e eo fd e c i s i o nm a k e rt oa c e r t a i n o b j e c t i v e ，t h ec o r r e s p o n d i n gd e c i s i o n m a k i n ga n a l y s i sp r o c e s s b a s e do nt h e m u l t i o b j e c t i v eo p t i m a lp r o b l e m i so p e r a t e di nt h i st h e s i sv i a t h es o l u t i o no fc o m b i n a t i o no f t h em a t h e m a t i c a lo p t i m i z a t i o n t e c h n i q u ea n d t h ee v o l u t i o n a r yc o m p u t a t i o nm e t h o d k e y w o r d s ：a n t c o l o n ya l g o r i t h m ，c o n v e r g e n c ep r o o f , t r a n s i t i o np r o b a b i l i t y , u n i t c o m m i t m e n t ，r e l i a b i l i t y , p o w e rf l o w , f u z z y s e t s t h e o r y ，m u l t i o b j e c t i v e p r o g r a m m i n g ，o p t i m i z a t i o nm o d e l ，d e c i s i o n m a k i n ga n a l y s i s 4 v 上海交通大学博士后研究工作报告第1 章绪论 第1 章绪论 1 1 电力系统安全经济运行的计算智能模型及方法研究的目的和意义 电力系统安全经济运行是电力系统分析的一个重要课题，它的主要任务是在保证 满足用户用电需求( 即负荷) 及系统安全性的前提下，合理安排电源运行方式，从而 使系统发电的总费用或所消耗的总燃料耗量达到最小以取得最好的社会经济效益。其 中，“合理安排电源运行方式”包含以下内容：电源功率经济分配、机组最优启停、 水火电经济协调以及无功优化等。 电力系统安全经济运行从数学模型上一般可描述为非线性规划问题。长期以来， 人们对这一领域问题进行了广泛而深入的研究，并取得了丰硕的成果【l 5 】。其中发展最 为成熟、应用最为广泛的方法是线性规划方法。以梯度寻优为主流的非线性规划方法， 理应是求解非线性规划问题的最佳途径。但该方法对目标函数及约束条件有一定趵限 制，解算复杂，且在很多情况下会陷入局部极小或接近全局最优解时难以收敛。此外， 电力系统优化运行的实际物理模型是非常复杂的，将其抽象成数学模型时，往往是忽 略了实际运行状况的非线性、离散性、随机性及不确定性等因素进行简化，即便如此， 常规的计算方法在进行求解时仍表现出极大的局限性。如果将上述因素加以考虑并建 立一个更接近实际的数学模型时，常规的优化方法已显得力不从心了。如机组优化启 停1 】p 。6 】这样一个非常复杂的电力系统优化运行问题，因其可观的经济效益和高难度的 技术而成为多年来广大学者关注的研究课题之一，但由于其内在的复杂性，基于常规 的数学优化方法在进行求解时遇到了一定的困难，目前仍在不断的研究之中。 此外，这一领域问题发展最为成熟、广泛的方法是确定性方法，这类方法具有模 型意义明确、解法成熟等优点。但是，这些方法只有在系统的运行信息数据确切知道 的前提下，才具有实际意义。然而，随着电力系统规模的日益扩大及广泛互联，需要 收集的运行信息将越来越多，所涉及的地域也将越来越广。这使得系统负荷、电源、 网络拓扑等数据不可能都确切知悉。可见，在电力系统的安全经济运行问题中，不确 定性因素是固有的。为了更加实际地反映系统的运行情况，应计及这些不确定性因素 上海交通大学博士后研究工作报告第1 章绪论 并直接根据不确定信息进行分析和决策。 由此可见，开发高效、快速、可靠的电力系统优化运行计算方法是一项相当艰巨 的工作。以进化计算。糟1 、模糊集理论f 舢2 1 、神经网络1 等技术构成的计算智能方法 的诞生和发展，为电力决策者解决极其复杂的电力系统优化运行问题提供了一条有效 的途径。进化计算是一种框架性的优化算法，只需一个适应性函数或性能指标，对目 标函数及其约束条件既不要求连续，又不要求可微，只要问题是可计算的，从计算机 理来看，最适合解决缺乏解析知识的、复杂的、有噪声和随时间变化的动态系统；另 外，在电力系统优化运行问题中，不确定性因素是固有的 2 4 - 2 ”，为了更实际地反映系 统的运行情况，应计及这些不确定性因素并且直接根据不确定性信息进行分析和决策。 模糊集理论在这方面则显示了强大的优越性。 综上所述，对电力系统安全经济运行的计算智能模型及方法的研究不仅具有十分 重要的理论价值，而且具有重要的实用价值。 1 2 计算智能方法及其在电力系统安全经济运行中的应用概况 智能可以分为高、中、低三个层次：高层次是生物智能( b i o l o g i c a li n t e l l i g e n c e ， 简称为b i ) 它描述了自然界中的生物体在其所生存的环境中所表现出的各种行为状 态，如环境适应性、种群进化性等；中间层次是人工智能【2 8 ( a r t i f i c i a li n t e l l i g e n c e ，简 称为a i ) ，它借助于工程技术手段对生物智能进行模拟，旨在揭示生物智能这一复杂 系统工作的奥秘及解决当前传统方法难以处理的问题；处于低层次的是计算智能口9 3 3 1 ( c a l c u l a t e di n t e l l i g e n c e ，简称为c i ) 。计算智能是国际上新近提出的学科概念，在计 算智能中，计算的概念是传统计算概念的拓展，计算对象不再局限于数和字符，运算 符号也不再局限于加减乘除等运算，在这范畴内的加减乘除也需赋予新的含义。从某 种意义上讲，c i 应包含在a i 之中，但一般来说，a i 偏重于逻辑推理，而c i 偏重于 数值计算。 目前，计算智能正处于迅猛发展的阶段，其主要技术包括进化计算、模糊集理论、 神经网络等。这几项技术各自均有了数十年的历史，但这些方法一般需要较大的计算 量，当时并未受到足够的重视。一是这些方法自身还不很成熟；二是受计算机软硬件 的限制，难以取得实际应用。随着计算机技术的发展和普及，它们在最近十年得到了 2 一 上海交通大学博士后研究工作报告第l 章绪论 突飞猛进的发展，引起了诸多领域专家学者的关注，成为一个跨学科的研究热点。 在电力系统的很多领域中存在着大量的、传统优化方法难以求解的问题，如非线 性、组合优化问题及系统模糊性问题等。而计算智能方法以其特有的处理复杂优化问 题的能力，为求解这类问题提供了一条可能的途径。 文献 3 4 1 综合叙述了遗传算法、进化策略及进化规划算法的基本原理、解算步骤 及它们之间的差别，指出遗传算法强调染色体算子，进化策略强调模拟个体，进化规 划强调模拟种族。文献 3 5 通过引入种群早熟集和种群多样度的概念，分析了遗传算 法中过早收敛现象的起因与特征。依据所作的理论分析，提出了一种可以预防和克服 过早收敛的新型遗传算法，并从理论上证明该算法依概率收敛到全局最优状态。文献 【1 3 】提出的蚁群算法中，给出了三种不同的模型，分别称为a n t - c y c l es y s t e m ， a n t q u a n t i t ys y s t e m a n t d e n s i t ys y s t e m ，它们之间的区别在于：后两种模型利用的是 局部信息，而前者为整体信息，求解优化问题时性能较好，通常将其作为蚁群算法基 本模型。文献 3 6 3 7 1 提出了一种更一般的算法，称之为a n t qs y s t e m ，采用了新的个 体移动规则及全局信息更新规则，实验结果表明该方法更具有一般性，且更利于全局 搜索。文献 3 8 将蚁群算法与两交换方法结合；文献 3 9 提出一种嵌套混合蚁群算法， 用于解决具有混杂变量类型的复杂生产调度问题。文献 4 0 l 提出了一种特别的蚁群算 法一基于图的蚁群算法( g b a s ) ，并进行了收敛性分析。文献 4 1 1 从极限理论对另一 种蚁群算法a c o b ，进行了一般性收敛性分析。尽管进化计算方法在理论方面取得了 一定的成果 3 4 - 4 6 1 ，但由于从生物进化抽象出来的数学模型的复杂性，使得进化计算方 法的理论研究仍处于探索和尝试阶段，特别在算法寻优机理、避免局部极值、算法的 自适应及通用性、收敛性分析等方面均有待进一步研究。 计算智能方法自2 0 世纪9 0 年代初期被引入电力系统领域以来，这方面的研究工 作越来越受到重视，在国内外有关的杂志和学术会议上发表了大量学术论文，内容涉 及到：电力系统优化运行、警报处理与故障诊断、网络分解、谐波分析与滤波、状态 估计、分散电源的最优配置、水轮机参数协调、灵活交流输电系统( f a c t s ) 、配电 系统中分段开关的最优分布等。文献 4 7 1 提出了针对计及环境约束的多时段经济调度 的一种有效、可靠的进化规划算法，求解过程中，考虑了解的加速技术。文献 4 8 1 提 出用进化规划算法求解电力系统短期水火电经济调度问题，并同模拟退化、遗传算法 上海交通大学博士后研究工作报告第1 章绪论 进行了比较。文献 4 9 】利用进化规划求解带有不连续费用函数曲线的经济调度问题。 文献 5 0 提出了基于g a 的火电机组短期最优组合方法。g a 中的数字串用二进制表示， 其中每位数字表示某一台机组在某个时段的状态。在g a 求解过程中，测试每个串所代 表解的可行性，如不可行则将其抛弃。而文献 5 1 提出的方法则将某些基本的约束体 现在数字串的编码中，这样就降低了产生不可行解的概率，从而明显改善了计算效率。 文献 5 2 1 中提出了在g a 的求解过程中引入启发式方法，改善了g a 的求解效率。文献 5 3 提出了一种联合采用g a 和专家系统求解机组最优组合的方法，利用专家系统对 用g a 求得的结果作进一步处理，以求得更好的解。文献 5 4 】 5 5 】将基本蚁群算法应用 于水火电经济调度中。目前，国内外有很多文献 5 6 _ 6 7 】是关于概率理论在电力系统可靠 性评估中的应用。其中大部分是长期的可靠性评估。因此，这些方法一般用于规划类 型的研究而不是当前的运行决策。为了运行人员在进行决策时保证系统有足够的安全 度，还应考虑运行可靠性问题，即短期可靠性评估。评估短期可靠性的方法通常分为 两大类，即确定性方法和概率性方法。确定性方法主要对未来可能发生事故的计算分 析，如潮流、稳定性分析等。考察这些结果并加以分析，判断是否需要采取纠正措施 以维持系统一定的可靠度。对于概率性方法，它并不独立于确定性方法。以概率法则 为基础的方法会是更合理而现实的方法，用该方法得到的风险度指标能够使各种运行 对策与这些对策的经济性之间有一个统一的判断基础。到目前为止，国内外很多学者 提出了各种不同的概率方法来进行短期可靠性评估。主要有p j m t 5 6 】 6 q 法、安全函数法 1 5 6 6 2 1 、频率和持续时间( f & d ) 法【5 6 】等。可接受的风险水平是一个管理决策的问题，它 必须根据社会和经济的需求来决定。可以使用现有的概率评估方法计算相关的概率风 险指标来估计一个合理的风险水平。一旦这个风险水平被决定以后，就可安排足够的 发电容量来满足它。总的来看，目前的研究工作是初步的，有很多问题值得研究或进 一步研究。 以牛顿法为代表的传统潮流计算，通常是根据给定的节点数据来求解系统中各节 点的电压和支路上的潮流。其中节点的数据是以确定值的形式给出的，求得的节点电 压和支路潮流也是确定的。但在实际中，节点数据的不确定性，必然会引起节点电压 和支路潮流的不确定性。这时若采用确定性潮流计算法，就要对众多可能发生的运行 情况做大量的重复计算，而且对于如此多的潮流结果也很难进行分析和综合。因此有 必要研究给定量具有不确定性的潮流计算方法。文献 6 8 】提出了模糊潮流这一概念， 并采用直流潮流，假设发电机组出力及负荷为已知可能性分布的模糊变量，然后通过 4 上海交通大学博士后研究工作报告 第1 章绪论 模糊数的加减运行求取支路有功功率的可能性分布。文献 6 9 1 提出将模糊数学规划用 于求解有功优化问题，首先建立起系统运行模型，负荷和发电量的不确定性由模糊量 表示，在注入功率给定的前提下，系统轨迹由直流模糊潮流模型来处理，最后通过线 性规划来求解。文献( 7 0 利用模糊规划求解有功优化时，把约束条件分为硬约束和软 约束，同时还计及对控制变量变动总数量的限制，并用模糊集把软约束和目标函数模 糊化，最后用逐次线性规划法求解。文献 7 h 采用潮流雅可比矩阵直接变换求取灵敏 度系数矩阵，从而建立无功电压控制的优化模型，其目标是系统网损最小，并利用模 糊集理论对已线性化的目标函数和部分约束条件建模，把单目标线性规划问题转化为 多目标模糊线性规划问题进行求解。目前，在对模糊潮流的研究中已取得了一定的成 果【6 8 _ 7 ”，但仍有许多问题尚待解决，如将基于直流潮流的模糊潮流模型拓展到交流， 解决模糊潮流问题中的虚拟潮流现象等。 综上所述，计算智能方法，无论就其本身还是在电力系统安全经济运行领域中的 应用，均已取得了一定的成果，但还谈不上成熟与系统的应用，在很多方面尚需做进 一步的探索和研究。 1 3 本文的主要研究工作 现有优化运行分析方法无论是在理论分析方面，还是在实际应用方面，其应用范 围、涉及领域、研究的宽度与深度等均存在一定的不足，有待进一步深入、系统化的 研究与探讨。在广泛阅读了有关计算智能方法以及计算智能方法在电力系统优化运行 中的应用文献的基础上，并在所作的前期工作的前提下，论文提出了相应地研究思路 与解算方法，即：综合运用进化计算理论、数学优化理论、模糊集理论以及概率统计 理论等技术，以电力系统安全经济运行问题为主要研究对象，对计算智能方法、计算 智能方法在电力系统安全经济运行中的应用等方面进行了深入而系统地研究，表明了 计算智能方法在电力系统安全经济运行中必将有着广阔的应用前景。概括起来，本文 的主要研究工作如下： ( 1 ) 简单论述了蚁群算法的基本原理，并在此基础上，从随机优化技术出发，构造 出一种更合理、通用性更强的转移策略，提出了一种新颖的随机摄动蚁群优化算法。 蚁群算法相对于其鲜明的生物基础( 自然界生物进化的客观实际) 而言，其数学基础 要薄弱一些。本文针对所提出的随机摄动蚁群优化算法，从理论上对其收敛性分析进 5 上海交通大学博士后研究t 作报告第l 章绪论 行了探索性的研究。指出该算法在有限迭代次数下以概率l 一占( 是一个很小的正数) 找到全局或局部最优解( 至少一次) ；而且如果迭代时间足够长，将以概率1 收敛于 全局或局部最优解。最后，以旅行推销商( t s p ) 问题为例，对该算法中若干参数的 选取进行了仿真分析，提出了具有普遍意义的参数选取方法，并制定出各参数的最佳 取值范围。 ( 2 ) 机组最优投入问题是寻求一个周期内各个负荷水平下机组的最优组合方式及开 停机计划，使运行费用最小。考虑到负荷预测的不确定性和发电设备的可能停运，还 必须安排一定的发电备用。本文针对采用确定性方法评估系统旋转备用的不足，提出 用概率性方法来评估系统的旋转备用，即在机组启停模型中引入相应的可靠性约束。 解算时，对模型的转化、约束项的处理等方面进行了较为深入的研究。此外，通过计 算安全函数排除不满足可靠性要求的组合，并进行了期望安全水平对优化解影响的敏 感度分析。 ( 3 ) 电力系统潮流计算是电力系统运行分析中的一项重要计算，如何处理给定量模 糊情况下的潮流计算仍是一个值得进一步研究和探讨的问题。考虑到现有的模糊潮流 计算中多采用直流潮流模型，本文则基于非线性潮流方程，提出了计算系统模糊潮流 精确可能性分布的非线性模糊潮流模型。此外，对模糊潮流中的虚拟潮流现象进行了 探讨，指出了有效的解决途径，建立了模糊有功经济调度的方法，巧妙地解决了参调 机组有功出力可能性分布的求取问题。 ( 4 )电力系统多目标优化运行是一个极其复杂的优化问题。本文建立了一个更为全 面、实用的电网多目标安全经济运行模型，模型中同时考虑经济、环境和安全指标因 素。对此多目标优化问题，为了更好地体现电力决策者对经济、环境及安全目标的权 重考虑，运用进化计算技术及常规的基于理想点的解算思想，进行了相应的决策分析。 ，6 一 上海交通大学博士后研究工作报告第2 章随机摄动蚁群算法的基本理论及特- 陛 第2 章随机摄动蚁群算法的基本理论及特性 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m a c o ) 1 3 - 1 8 1 是模拟自然界中真 实蚁群的觅食行为而形成的一种模拟进化算法。它采用有记忆的人工蚂蚁，通过个体 之间的信息交流与相互协作来找到从蚁穴到食物源的最短路径。目前蚁群算法在旅行 推销商( t s p ) 1 6 、指派( a s s i g n m e n tp r o b l e m ) 7 2 【7 3 1 及i o b s h o p 调度【7 4 】等优化问题的 应用中，取得了一定的成功。众多研究己经证明蚁群算法具有很强的发现较好解的能 力，这是因为该算法不仅利用正反馈原理在一定程度上加快进化进程，而且是一种本 质并行算法【l3 1 。但算法本身也存在一些缺陷，如搜索时间较长，而且容易出现停滞现 象【1 3 】等。 本文以基本蚁群算法为基础，并从随机优化技术及生物进化角度出发，提出了一 种随机摄动蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m v v i t hr a n d o mp e r t u r b a t i o n b e h a v i o r ，简称脚) a c o ) ，并从理论上对该算法的收敛性及一些相关特性进行了分析， 同时针对t s p 闻题，对改进算法的参数选取进行了分析，在大量数值仿真的基础上提 出了具有普遍意义的参数选取方法，并基本确定了各参数的最佳取值范围。数值模拟 结果验证了该算法可以有效地提高算法的运算效率和计算精度。 2 1 基本蚁群算法 为了更好地理解所提出的改进算法的实质，这里简要叙述一下基本蚁群算法的基 本原理。同时，以下对算法的描述都是以求解平面上疗个城市的t s p 闯题为例来进行 的。 众所周知，真实的蚂蚁能够在没有任何视觉线索的情况下找到从食物源到蚁穴的 最短路径，并且能够适应环境的改变。比如在旧的路径上放置一障碍物，此时姆蚁能 够很快找到一条新的最短路径。生物学家的研究发现蚂蚁建立和维持这一运动主要是 依靠这条路径上的“信息素”，蚂蚁在运动过程中，能够在它经过的路径上沉积一定的 “信息素”，并在运动过程中能够感知这种物质的存在及其强度，以此指导自己的运动 方向。一般，蚂蚁倾向于朝着该物质强度高的方向移动，正是利用这一基本性质，当 前面这一路径上突然出现一障碍物时，蚂蚁仍能找到一条新的最短路径。以上整个过 程如图2 - i 所示。 上海交通大学博士后研究工作报告第2 章 随机摄动蚁群算法的基本理论及特性 警妻毒 g ；g 置三童 8 8 奏 窀；8g ；8 cr 8 美8 置譬皇u 8 吣。”8 i 8 扩 需注意的是：那些选择较短路径的蚂蚁将比那些选择较长路径的蚂蚁更快重建被 阻隔的信息素路径。因此，短路径上沉积的信息量更多，这就导致更多的蚂蚁选择这 条较短的路径，最终所有的蚂蚁将全部选择这条较短的路径。通常这过程称为“正 反馈”。蚂蚁个体就是通过这种信息的交流达到搜索食物的目的。 基本蚁群算法的模型及其实现可以表述如下： 1 初始化蚁群算法。设定相应的参数，如蚂蚁数m 、最大迭代次数，。等。令r 。) 表 示f 时刻在路径 ，上的信息量。初始时刻，各条路径上的信息量相等，设r 。( 0 ) = c ( c 为常数) 。 2 选择城市。蚂蚁从某城市出发，按照如下的转移概率选择下一个城市： 乃( t ) 2 豢j , s 隹t a b u ( k )。， o 式中，玎。= 1 d d 。( f ，j = 1 , 2 ，n ) 表示城市i 和城市，之间的距离，为启发式因子， 表示由城市i 转移到城市，的期望程度；t a b u 。( k = 1 , 2 ，m ) 为t a b u 表，用以记录蚂蚁k 已经走过的城市，它随着进化过程做动态调整，蚂蚁在后来的运动中不能选择那些已 记录在t a b u 表中的城市；s 表示蚂蚁k 下一时刻所允许转移的城市，即不在t a b u 表中 的城市；口，口分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径 的过程中所起的不同作用。蚂蚁按照上述状态转移规则选择城市并最终形成一条封闭 路径，当所有的蚂蚁完成了它们的闭合路径后，即一次迭代结束，利用全局信息更新 上海交通大学博士后研究工作报告第2 章随机摄动蚁群算法的基本理论及特性 规则来更新路径的信息量，再开始下一次迭代直到达到最大迭代次数或最大停滞次数。 3 全局信息更新原则。算法完成一次迭代后，各路径信息量的更新应遵循如下的全 局信息更新原则： r 0 + n ) = p 7 ( t ) + f ( 2 - 2 ) a r - - z a r p ( 七) ( 2 - 3 ) 螺( 驴詈，若蚂蚁腱过路绚 ( 2 - 4 ) 0 否则 其中，p 表示信息残留的程度，即信息素挥发系数，一般p ( 0 , 1 ) ：q 为常数：l 。 为第k 只蚂蚁在本次循环中所走过的路径的长度。在每次迭代的初始时刻，设f 。= 0 。 蚁群优化算法是模拟蚂蚁真实行为的一种算法。其本身也是一种迭代算法，但它 并不是简单的迭代，当前的迭代总是利用以前迭代的信息，即模拟了信息正反馈原理。 正是正反馈原理和启发式算法相互作用，使得蚁群优化算法有较强的全局收敛性。 2 2 随机摄动蚁群算法基本原理 众多研究已经证明蚁群优化算法具有很强的发现较好解的能力，这是因为该算法 不仅利用了信息正反馈原理，在一定程度上加快了进化进程，而且有较强的鲁棒性， 是一种本质并行算法。不同个体之间不断进行信息交流和传递，从而相互协作，有利 于发现较好解。但是，该算法也存在一定的缺陷，如搜索时间较长、易出现停滞现象， 即搜索到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索， 容易限于局部最优解。为此，本文对蚁群优化算法的寻优机理进行了研究和探讨，从 随机优化技术及生物进化角度出发，提出了一种新的转移策略，设计出一种随机摄动 蚁群算法。其基本原理表述如下。 前已述及，基本蚁群优化算法的主要依据是信息正反馈原理和某种启发式算法的有 机结合。基本蚁群算法中的转移概率公式( 式2 1 ) 则揭示了这一原理。它表明如果放到 某条路径上的信息素越多且路径越短，则该路径的转移概率越大，那么该路径被蚂蚁 选中的概率就越大，类似于遗传算法中的“轮盘赌”法。鉴于这样一层物理含义，本 文设计如下更为简洁的转移策略： 上海交通大学博士后研究工作报告第2 章随机摄动蚁群算法的基本理论及特性 c 。，c ，= f ”g 叩，名” 陋s ， 令s = 按峄( c 啡) ) 转移到的城市。勺的物理含义为单位路径上的信息量。需要指 出的是：公式( 2 5 ) 中的c ) 不再是“转移概率”，而是路径驴的“转移系数”，蚂蚁总 是选择转移系数最大的路径，具有定的确定性。此外，c 涨) 是有量纲的，但由于在 计算过程中只取其相对值，因此其对计算结果无影响。 由于迭代过程中，路径 ，上的信息量r 。在迭代过程不断更新，因此在最初的几次 迭代中，为使较好路径上信息量的作用更明显，本文提出一个“放大因子”y 。初始 几次迭代中，取较大的值，以提高算法的收敛性：此外，为防止算法早熟，使，的 值在迭代过程中逐渐衰减。这里，本文设计了例指数关系曲线来描述，： y 2 妙( r = 1 , 2 ，m “b o ) ( 2 - 6 ) 式中，r 表示当前迭代次数；i 。为最大迭代次数：b 为尺度因子。由式( 2 6 ) 可知，随 着迭代次数的增大，y 的值最终趋近于1 ，而系数b 的大小决定了曲线趋近于1 的快慢 程度。 这样，转移系数可表达为： f 吃( f ) 】7 r ”，j 盛t a b u c ) ( f ) = ( 2 7 ) 【0 ， 此外，考虑到基本蚁群算法中易出现的停滞现象，本文设计了一种摄动策略，即 进化到一定程度后增加一定的扰动，以避免算法过早陷入停滞。最后，本文设计了如 下具有随机摄动特性的转移系数： c ”( 女) ( f ) = ( 瑚。u p 。，岳t a b u ( f ) 】7 u p 。，g t a b u ( 2 - 8 ) 0否则 式中，p 。( o ，1 ) 称为随机变异率；u 是( 0 ，1 ) 中均匀分布的随机数。式( 2 培) 中， 当p 。取很小的值时，即退化为式( 2 7 ) 。但当p 。，取适当值时，由于随机变异的作用， 可以避免蚂蚁的搜索陷入同一种模式，提高解的多样性，有利于进一步搜索全局最优 解。 该模型将确定性选择与随机选择相结合，确定性选择引导蚂蚁朝着最优方向搜索， 上海交通大学博士后研究工作报告第2 章随机摄动蚁群算法的基本理论及特性 随机性选择导致计算转移系数时具有一定的随机性，从而有效地避免了搜索陷入局部 最优解。正是两者的共同作用才使r p a c 0 具有更强的全局搜索能力。 2 3 收敛性分析 目前，蚁群算法在很多n p 难问题的应用中取得了一定的成功，但在理论分析方 面仍有一定的欠缺。可以说，蚁群算法相对于其鲜明的生物基础而言，其数学基础要 薄弱一些。文 4 0 】对一种特别的蚁群算法基于图的蚁群算法( g b a s ) 进行了收敛性 分析，但缺乏一定的数值仿真分析及比较；文【4 l 】从极限理论对另一种蚁群算法 彳c o 。进行了收敛性分析，但证明过程比较笼统，并末计及算法中某些参数的影响。 本文从上述文献的分析中得到一定的启发，并针对所提出的算法r p a c o ，从理论上对 其收敛性分析进行探索性的研究。 这里，为不失一般性，对该算法作如下处理：对于约束优化问题，采用适当的 方式将其化为无约束优化问题；采用优先策略，即：上一次迭代中获得的最优解将 被保留下来；认为最终所找到的最优解不一定是全局最优解。 准则1 ：令m 为所要求解问题的最优值( 最短路径长度) ，如果在f 次迭代时，找到 最优解石+ ，则对于v ( i ，) x 路z 一- 2 。* 在足够长的迭代次数下，必有 l i r a 未蔬 池。) 特别，对于任何路径 ，上的信息量“在足够长的迭代次数下，存在 i i m r 。( ，) f ( 2 l o ) 证明：如在第九次迭代时，第一次找到最优解，则在f + 1 次迭代时，根据前述的全局 信息更新原则，对于属于该最优解中的任一条路径上的信息量f ：被更新为p - f ：( l ) + q - r o l l ，在i + 2 次迭代时为p 2 一f ：( ) + p q 掰三。+ q t r e l _ ，依次类推，经 过f 次迭代后，信尽量r ；被更新为 ，：pr r + 兰p ，譬 考虑到0 p ( 0 考恶o m b、，“m 即 f 生= f ， 证毕 i p 3 定理：令p + ( r ) 为r p a c o 算法在f 次迭代时至少一次找到最优解( 全局或局部) 时的 概率，则在有限迭代次数下，存在 p ( f ) 1 一( 5 是一个很小的正数) ( 2 1 4 ) 特别，如果迭代时间足够长，将有 l i m p + 0 ) = 1 ( 2 - 1 5 ) 证明：根据准则1 和准则2 ，可以确保进行由式( 2 8 )