（控制理论与控制工程专业论文）基于改进遗传算法的配电网络重构.pdf

硕 士 论 文 基于改进遗传算法的配电网络重构 ab s t r a c t 压s tri b u ti onn e t w o rkr e c o 呱g u ra t l oni s n o t oniy ani m po比 犯 t m e th od for c ir c u l ati n g 阳 dcon 加ll i n go fdi strib ution s y s t e m ， b u t al s oan 面portan t p art o fd i s tri b u ti on man a g e m e n t s y s t e m . inth co ry， th ere 骊s tsa b es t n e two 比s tl ” 曰 比 代for any 山 s tri b u ti o n n e two rk . u n d erth e b es t n e 幻 囚 o rks tructure ， th e v of tage ateac h to ad州成 n e 幻 囚 。 比l osses a n d to adb al an c e are all b e tt erth an 0 t h erfe as i h lemeth eds . the pul poseofdi strib ution n e two rkr ec o n fi gura ti on istoadju stthe ne 栩0 比s truc to r esb y c h an乡 ng the o 脚叭l ose s ta t 璐 。 fthe ti eandsub s ect i on swi teh es imd er b o th n o ny阁 andai 川 o m因 。 沐mting conditi ons . n is h el p fu l toel th anceth e 涨 父 u n ty，e c 0 n 0 m y and re li ab ili tyofthe sy s t 曰 旧 . inu 劝 s p a per 五 招 ti y th e n etw o rkto pel o gy i s an a 1 y z ed withthe i n v o rt ed s e q u en ce n u m b erin g meth odado p ti n g b re ad th俪 t 涨 a rc h pl anfor n u mb 饥. origi nal b ac 灯化 ，ard s w ee p 砒 th od b as ed o nb 团ch c u n n t i s l m p ro v ed， add in g th e meth 冈 for p vn odes w hi ch n 加 改 e th e m ode ! ofpew ern o wsolutionm o rep ra c ti cal. s ec ond ly，b y an al y 幻 ng th e si mpleg e n e t i c al g o n t 加 mind e 面1 ， 如 乡 obalcon v ergen ce isn 尤 ti fi e dwi theli teg e n etic al g o n t l l l nand a 山 甲 tive g e n etic al gori d l n l . the a 山 甲 ti ve fo n 刀 u las ofcro s sov erp r o b ability and mutationp r o b ab ili tyare fu rtheradjus ted toeli 而n a teth e 。 址 ly lnatu ri ngp h e n o m e n on. 仆让 d 】 y ， 1 沈u si n gon l 元 hi而zin gn e 幻 刃 o rk tos ses， th eit 叼 th e it 份 ti c s m ode l of d i s 币b ution n e t w o rk reconfi gur a t l on i s con s tl 刀 c 囚 . the p rob 1 em ofin fe asi b l esol u ti ons in山 s tri加ti o n netw o 比n 兄 。 n fi g u ra ti onis di sc u s “ 刘明 d i m p r o v 比byen c ode m e th od. 玩 允 韶 ib les o l u ti ons 汪 a 压 cro s s in gandmu ta o n gare c o 打 ect ed to fe a s i b l esol u ti o n sb yamend ed cro ss over 。 伴 花血g an d mu画on o pe ” ti n g r n al l y，th e ap p l l c 如on p ro g ra n l iscom p l i edb 助 edon th e p ro pos ed al g o n t 知 叮in面s p a 户 甄孙 。 5 加 叮 ds 川 姗t colr 甲 u tations ofsingl e power sourcean dmuni p le pew er sou rc c sare v erifi 司. thev 碰di ty of th eai g orit h m is d o m o ns。 刁 t ed byth e 心 ul ts. keyv 叭 ， r ds: di 面buti on ne two 改 以叨6 g u ra ti on; fi ow calcul ation; g enetic al g o n d ll 斌 self- a dap ti v e ; 访 介 韶 l b l e solu ti o n 声明 本学位论文是我在导师的指导下取得的 研究 成果， 尽我所知， 在本 学位论文中， 除了 加以 标注和致谢的部分外， 不包含其他人已经发表或 公布过的研究成果， 也不包含我为获得任何教育机构的学位或学历而使 用过的材料。 与我一同 工作的同事对本学位论文做出的贡献均己 在论文 中作了明确的说明。 研 “ 生 签 “ : 客应一 年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档， 可以 借阅或 上网公布本学位论文的部分或全部内 容， 可以向有关部门或机构送交并 授权其保存、 借阅或上网公布本学位论文的部分或全部内容。 对于保密 论文， 按保密的有关规定和程序处理。 研 究 生 签 名 二 黝 足- 年月日 硕 士 论 文基于改进遗传算法的配电网络重构 绪论 1 . 1引 言 配电系统是处在电 力系 统末端， 把电 源系统或者 输变电 系统与用户设备连接起 来， 向用户分配电能或 供给电 能的重要 环节， 是整 个电 力系统自 动化的一个重要组成 部分，其主要任务是保证配电网络的安全经济运行。 由 于配电网的 发展有个过 程， 除了 受到电 源位置、 负荷分布的限制和约束， 还受 到经济和地理条件等因素的影响， 因此配电网的供电方式和网络结构各式各样， 大体 上可以 分为三类: 辐射式， 环网 式， 网 格式。 其中 尤以 网格 式供电的 可靠性最高， 而 我国 大部分配电网 络结构都是 辐射式，辐射式的配电网 络结构具有如下 特点: 1) 总线路里程较长，运行电压低，线损较大; 2) 网络结构复杂，装有大 量的 分段开关和联络开关; 3)由于网架结构不合理，容易出现负荷不均匀，电能质量较差等现象。而配电 网系统内 经常有设备的 扩容、 更新， 这往往进一步 加剧了网 架结构的 不合理 性。 国 家电 力公司成立后，实施了“ 公司化改组、商业化 运营、 法制化管理” ， 为 电力经营从垄断走向开放奠定了基础。 开放的电力市场势必将促进城市电网的建设和 改造，但是由于我国长期习惯于缺电局面和垄断经营，以 及 “ 重发、轻输、不管用” 的建设理念，导致了城市电网的建设速度明显滞后于发电和用电的增长速度， 特别是 城市电 网中的配电网建设更为 缓慢。 随 着国民 经济的持续发 展以 及人民 生活水平的 不 断提高，为了满足不断增长的电力需求就必须加快电网建设以及对原有电网进行改 造。而在这一过程中，我国配电网络建设滞后，电网容量不足，网损过大，电压质量 差的问题就进一步的暴露出来。 对配电 网的要求 有很多， 主要有 三点:供电 可靠，电能 质量合格， 供电 损耗少。 原国家电力公司要求全国 城市电 网用 户供电可靠性2010年达到99一 92% ， 而一些大城 市的要求更高， 要达到99. 99% ; 电 压不合格率到2 010 年控制在0. 5 % 和1 % 之间: 线 损 率 到2010年 要 降 到4 % 以 下 川 。 而目 前这 些 指 标 离 要 求 还 有 相当 一 段 距 离。 因 此， 对配电 网络进行 优化势 在必行。 配电网络重 构， 作为 配电 网络 优化的 重要组成部分， 最早是在 1 9 75 年由英国人 m erlin a 和b ack h 首 次 提 出 12 ， 最 初 主要 针 对城 市电 网 . 城市 电 网的 特点 是 大量 使 用地下电缆，具有环形结构而且通常以辐射状运行。系统中配电变压器存在哪条 电缆供电最优的问 题。在 农村电网中 主要使用架空线， 最 初系统是按照辐射形设计， 后来为了 提高供电可靠性， 分段开关和联络开关的数目 不断增加， 并且随 着配电自 动 化技术的发展，配电网重构也就成为可能。近年来， 随着电网改造和配电管理系统 硕 士 论 文基于改进遗传算法的配电网络重构 归m s)的 研发工作在中国 蓬勃展开， 作为 d m s重要功能的 配电网 重构也 开始得到研 究。 1 . 2配电网 络重构的目 的 和意义 早期的配电网 络重构主要是研究通过何种供电路径给新用户供电可以使总的费 用最小， 即研究配电网 络规划阶段的重构问 题。 随着对配电网 络重构认识的 逐步加深， 学者们开始研究配电自 动化系统加入网络重构的可行性， 研究结果表明配电网络重构 不仅 在经济 和技 术上可行，而且可以极大 地优化配电系统的 运行。 在电力 系统的 各个环节中， 配电作为 末端直接与用 户相联 系， 配电网的 可靠性、 电能 质量是电力 系统的“ 窗口 ” ; 另一方面，配电网的网 损常 常要占 到整个传输网 网 损的50% 一 0 % ， 是电 力 系统降 低损耗、 经济 运行的“ 挖潜大户” 。 所以， 对于配 电网 来说: 快速反应切除故 障， 通过网 络变化尽可能 地恢 复用户的电 力供给; 实时规 划、 调整系统结构， 使其更经济， 电能品质 更优， 这两者都具有极其重要的意义。 配 电网 络重构就是保证在配电网 呈辐射状、 满 足馈线热容、 电 压降 落要求和变压器容量 等前提下， 通过改 变分段开 关、 联络开关的 组合状态， 即选择用户的 供电路径， 使配 电网 的某一个指标或者某几 个指标( 如配电网 可靠性，供电 电压质量，配电网网络损 耗等) 处于最佳的 运行状态，以 达到降低网损、 消除 过载、 平衡负荷、提高电压质量 的目的. 任何一个配电网， 理论上都存在一个最优的网 络结构， 在这个最优结构下， 各负 荷点的运行电压、网 络损耗和负荷平衡的 协调都 优于其它可行方案。当负荷变化时， 该最优结构也随之变化， 计算出最优结构， 使网络运行于最优状态，这就是配电网络 重构研究的主要内容 131 。 目 前， 配电 网多 采用环状结构、 开环运行， 在配电线路 上， 通常沿馈 线设 有一定 数量的常闭的分段开 关， 馈线之间则装有常开的 联络开关。 在正常运行状态下， 为了 增加网络的可靠性，减少网损，需要定期通过开/ 合这些开关来重新构造配电网络的 运行结构， 使负 荷在各馈线之间相互转移而 得到 合理分配; 在产生故障时， 为了 尽可 能的恢复用户的电力供给，同时减少配电网络损耗，也需要进行相应的网络变化。 近二十年来， 电 力工作 者己 经在配电网 络重构方面 做了 大量的工作， 提出了 很多 实用有效的算法， 尽 管他们采用了 不同 的方法， 借 鉴了 不同 的理论， 但在收敛性， 寻 优效果以 及运算 速度 这三者的协调上， 配电 网 络重构仍存在一 个寻找更为实 用更 为优 化的综合解决方法的问 题。 因此， 无论是现在 还是将来， 作为配电管理系统的 重要组 成部分，配电网络重构都是值得深入研究的领域。 1 . 3配电网 络重构算法的 研究现状 硕 士 论 文 基于改进遗传算法的配电网络重构 配电网络重构是高维数非线性组合优化问题。 自 一me rl l na 和b a c kh 首次提出以 来，受到 广大学者和电 力工作者的广泛重视， 正逐步成为 一个国 际热门课题。 1 . 3 . 1现有算 法介绍 为了 提高 计算速度，保证得出 最优或次 最优的 配电网络运行结构， 人们尝试了 用 不同的方法来解决配电网络重构的问题。 解决配电网重构的算法主要有 : 数学优化理 论、 最 优 流 模式 (o pti n 叼 l fl o w p a tt e m ， 简 称 为 o fp) 、 支 路 交 换 法 化 脚chex ch an gemet h ed ， 简称为 b e m ) 、 模拟退火算法(si m u l a 让 幻 a n n ea li n g ， 简称s a ) 、 遗传算法 ( 9 o l e t i c al g o ri t 加 皿 1 简称g a ) 、 人工神经网 络( a rt i fi d aineu ral n e t w o rk ， 简称为a n n ) 和专家系统 等。 其中， s a、g a 、a n n和专家系统并称为人工智能算法。 1 . 3 . 1 . 1 数学优化理论 m e rl i n 和 b 毗 等人利用数学规划方 法来处理配电 网重构的问 题闭 ，他们首先做了 一些假设: 负荷以恒定的纯有功分量电流源表示;电压角度被忽略; 不考虑网格的约 束条件;以 d c 潮流计算网 络流，利用分支定界 法得出 最佳的配电网结 构。 此后许多 学者尝试将优化理论 应用于配电网 重构中 : ji 一anf an等人提出 一次只开合一 对开 关 的单环网优化问 题ll ， 其数 学模型 为具有二次目 标函 数的、 0 一 1 状态变量的非 线性整数 规划问题，用单纯形法求解.n.d.r.s a l l l l a 等人提出一种基于0 一 1 整数规划的配电网重 构 算 法 5 ， 这 种 方 法 一次 可以 考 虑 多 个 开 关 操 作 ， 并 可以 得 到 全 局 最 优 解 。 t. p. w an ger 等人把网 损最小的网 络重构问 题转化成 考虑 二次费用的网 络传输问题 161 ， 二次功率损 耗 用分段 线性函 数表示，将馈线电压降落和 热容约束包含在其中 ， 该 方法不需要起始 方案， 在优化过程中形成辐射状的网络结构. ka o k i 等人忽略电压降落将负荷当成恒 定电流， 用非线性规划技术来求解配电网 重构问题门 . 一般认为，利用数学优化理论可以得到 不依赖于配电网 初始 结构的 全局最优解， 但已 经证明 ，数学优化技术属 于 “ 贪婪” 搜索算法，计算时间非常长。 1 . 3.l 2最优流模式算法 最优流模式算法是由 d.s hi n n o h aj . n la d i 等人于1 9 89年提出的一 种启发式方法8 它 以 功率损耗最小为目 标函数， 算法步骤的 基本思想为: 1) 将所有联络开关合上形成多环网; 2) 只保留支路的电 阻， 在满足k v l 和 k c l 条件下求得的电 流分布就是系 统的最 优流模式; 3) 打开 在最优流模式下电 流最小的开 关，打开一个开关解开一个 环路: 4) 重复 步骤2 和步骤3 ， 直到网络恢复为 辐射状为止。 该方法把开关组合问题转 化为 优化潮流的计算问题， 使复杂问 题得到了简 化。 其 硕 士 论 文基于改进遗传算法的配电网络重构 缺点是初始时闭 合所有联 络开关使网 络中同 时存在多 个环网，求解o fp时各环网电 流相互影响 ，打开开关的 顺序对结 果也有较大影响; 确定一个待开开 关有可能 需要进 行多次配电网 潮流计算。为此， 5 . k gos w anu 等人 提出 每次只合一 个联 络开关，确定 一 个 待 开 开 关的 方 法 19 消除 了 环网 电 流 的 相 互 影 响 ， 但计 算 量 仍 较 大。 文 献 l 0 在 文 献9 1 的基础上提出一种改进的 最优流模式算法，在求最优流时，只将环网支路中的 阻抗 简化为电 阻，而辐射状分支仍保持 用阻 抗描述， 从而更加符合实际 情况，并且通 过网 损变化的估算公式来确定要打 开的 开关。 而文献11 1 推导出 一次开关 操作中 功率 损耗增量的 表达式，然 后选择功率 损耗增量最小的 开关操作。 1 . 3.1 . 3支路交换算法 该 算 法由 s. ci v 剑ar 等 人 首 先 提 出 【切 ， 首 先 计 算 初 始 潮 流 和网 损 ， 利 用 潮 流 计 算 的 结果将负荷用 恒定电 流表示，每次只合上 一个联络开关形成一 个环网: 选择环网中 一个分段开 关并打开，使配电网 恢复为辐射网 ，从而实现负 荷转移 ，达到负 荷均衡 和降 低线损的目 的。 为了 保证支路交换操作能 够降 低网损，作者推导了 一个支路交换 前后网损变 化的估算公式，为了 保证网 损下降 ，必须闭 合两端电压 差最大的联络开 关，并将负 荷从电 压降落大的一侧转移到电 压降落小的一侧，据此可以 建立一组启 发式的规则。 me b 等 人 11 习 在 文 献 1 2 的 基 础 上 进 行了 改 进 ， 利 用网 损 变 化的 估 算公 式 为 二次函 数的 特点 ，将二次函数求极值的方法用于寻找最佳开关操作，降低了总的搜 索 次 数。 m :ak as h eln等 人 【 14 将文 献 11 3 的 思 想用 于 配电 网 负 荷 均 衡。 在 文 献 11 5 中 m .a名 泊 s h eln等人从潮流方程出发得出支路交换引起网损变化的另外一个公式。 认 币 一inu n 等 人 汇16 采 取 每次 只 考 虑 具 有 最 大 降 损 效 果的 开 关 操作 策略 ，降 低了 搜 索 空 间。 g. pe pe m s 等 人 1门 对雅 典 的 一 个配 电 网 进 行了 简 化， 然后 用 支 路 交 换算 法 和 最优流模式算法进行配电网重构，结果 表明支路交换算法结合启发式规则具有更快 的处理速度。 该算法 有如下特点: 1) 可以 快速确定 降低配电 网线损的 配电网 结构: 2) 通过启发式规则减少需要考虑的开关组合; 3) 可以 利用公式估算开关操作 带来的 线损变化. 该算法的不足之处在于: 1) 每次只能 考虑一对开关的操作; 2) 不能保证全局最优: 3) 给出的 配电网 重构结果与配电网的 初始结构 有关。 1 . 轰1 . 4模拟 退火算 法 硕 士 论 文 基于改进遗传算法的配电网络重构 s a 是解决混合优化问题的有效方法，该算法的要点是:设计合适的全局冷却过 程，即确 定起始冷却温度、 冷却率、 每次交换开 关的 数目 及每个温度下 交换开 关的总 数等。 通过交换开关形成的网络结构， 计 算其潮流及网 损，若具有较小的网 损， 则保 留，否则按一定的概率接受。 继续交换开关，直到达到最大开关交换数目。 继续冷却， 直到 符合结束判据。 结束判 据为: 在连续多 个温度下，网 损变化极小， 认为系统已 经 达到冻结状态，得到优化结构。 c hi an g h d 等 人 11 8 将 配电 网 重 构 描 述 为 不 可 微 的 、 具 有 等 式 和 不 等 式 约 束 的多目 标函数优化问题，采用在不同的温度用不同的收敛指标来提高s a 算法的速度。 c hi anghd 等 人在文 献l 9 中给出了 s a 算法在配电网重构中的具体应用，当温度较 高时用简化的潮流计算方法，在温度较低时用严格的潮流计算公式的策略来提高计 算速度。 文献 20 提出 了一种改 进的 s a 算法，即以 当前最 优解作为当 前控制温度下的 初始当 前解，从而构造了一个单调递减的初始当前解序列，这一改 进使算法对参数 的依赖减小，而且 进一步降 低了 计算量。 hon g 毛h an c h an g 等 人在文 献 21 中介绍了 一种改进的 s a 算法，首先通过多次配电 网重 构确定出与系统结构 和系统负荷模式 相 关的 初始 温度，然后通过改变邻近开关 状态的方法来构造新的 配电网 结构。 d . j 咖9 等人 122提 出 利 用 模拟 退 火 算 法 进 行 配电 网 重 构 和电 容 器 投 切的 综 合 优 化 算 法 ， 不仅 降低了线损也解决了配电网重构过程中的电压越限问题。 s a 算法一般可以 得到 全局最 优或 全局次最优解，但该方法对参数和退火方案的 依赖性大，计算量大，将其用于配电网 重构时需要进行多 层次大量的开关交换，需 要进行多次潮流计算 及网 损估计，因 此计算量 更大。 1 . 几1 . 5遗传算法 g a 是以自 然基因 选择机理为基础的搜索 方法，通过 模拟基因串的 优者生存及随 机交换信息的方 法搜索优化方案。 在每 个新代里，它利用上 代最适 合的 信息去创造新 的合成基因串，它有效利用过去的信息去搜寻新的搜索点，从而改进搜索操作。 g a 结合了目 标函数和遗传过程，在配电网 重构中 ，编码的 位用来表示开关的状 态，而适应度函数由系统的总线损构成。 适应度函数值是遗传算法指导搜索方向的依 据，首先要保证其值不为负，其次目 标函数的 优化方向 应当对应于适应度值增加的 方向 。 k- n 姗等 人 【23 首 先 将 配 电 网 重 构 描 述 为 混 合 整 数 规 划问 题 ， 然 后 用 一 种 简 单 遗 传算法进行配电网重构. 该方法首先随机产生一组初始种群，将其中不符合实际运行 约束要求的 个体去掉。 采用轮盘赌方法进行 选择复制，并用由 经验 值确定的 交叉率pc 和变 异率 尸 几 以 寸 个体进行交叉和变异操 作。 由 于采用固定的 pc和尸 ” 1 影响了 遗传算法的 性 能 m .s ri ni v as 等 人 124提 出 一 种 随 进 化 过 程自 适 应 地 改 变 凡和 pm 的 算 法 。 文 献 1 2 5 提出 一种模 糊遗传算法，即 通过模糊规则 在线地改 变尸 c 和 尸 ” 1 的值， 提供的 算例表明， 硕士论文 基于改进遗传算法的配电网络重构 模糊遗传 算法改进了 简单遗 传算法的 性能，提高了收 敛速度，避免了 未成熟收敛。 文 献 26 提出部分匹配逆转交叉法，该方法使得完全相同的两个父串进行交叉操作也 能产生新的基因组合，在后期种群中的 个体单调时 ，算法仍能跳出 局部最优解，开 辟新的搜索空间。 g a 有以 下 特点: l) g a 操作的是参数的 编码而不是参数 本身; 2) g a 从一群点 搜索，而不是从一个点开始搜索，在早期发 现优 化值的 可能性 很高，能 够快速全局收 敛; 3) g a 使用概率变迁规则而不 是确定 性规则指导搜索，能处理病态、离散型的 优化问题; 4) g a 具有内 在并行计 算的 特性. 当 然，g a 也面临许多问题，如计算 速度慢，选取不同的 初始基因串 会有不同的 优化结果等。 1 . 乳1 . 6人工神经网 络 a n n 的 最大特点是可以通过样 本的训 练将输入与输出之间的非线性关系存储在 神经元的 权值中 溯。 因 此，可以 用 a n n 反 映配电 网负荷模式( 各 节点负 荷的 组合就称 为负 荷模式) 与配电网 最优结构之间的非线性 关系。 h.幻 m 等人128 为了 克服获取大量 训练样本的困难，将负荷分为不同 的区 域，针对每一负荷区域得出训 练样本，样本 的 输出 则通过求解包含电 压降 落和馈线热容 约束的 二次规划问 题得到。 文献【 29】 将负 荷分为 工业、 商 业和民 用3 类， 同时 将负 荷水平分为 7 类， 大大减少了负 荷模式的 数量。 由于同类负荷的变化规律是相同的 ，由 3 类负荷的 7 种负 荷水平构成了训练样本的 输 入，样本的输出由开关交换方法确定. 上述措施不仅降低了配电网重构的维数，也提 高了运算速度。 由于不需 要进行潮流计 算，也不用对开关 操作的降损效果进行估算，利用a n n 可以大大降 低配电网 重构的时间， 从速度上 看这是目 前最 快的 配电网 重构算法。 然而 a n n 算法得出的 结果的 精度依赖于提供的训练样本，对于一个有一定规模的 配电网， 要得到所有可能的负 荷模式 及其 对应的最 优配电网结构是困 难的 ，训练样本也需要 大量的时间。 1 . 志1 . 7专家系统 有 不 少 人 尝 试 利 用 专 家 系 统 来 进 行 配电 网 络 重 构 。 c h ell 毛 hing u u 等 人 【30 提出 了 一种基于 专家系统的故障恢复与配电 网重构算法，规则是对配电网 进行研究和了 解 调度人员的经验后所得到的，这种方法可以 降低网损但不能 保证得到 全局最优解。 t. t a y lor 等 人 3l和 g. c hang 等 人 【32 提出 的 算 法 基 本 相同 ， 其目 标函 数 为 避 免 变 压 器、 硕士论文 基于改进遗传算法的配电网络重构 馈线过负荷以 及电 压越限的发生，他们认为满足这些 条件时 可以降低配电网 线损。 achang 等人的研究表明应 该在进行配电网 重构时采取继电 保护和电 压控制策略。由 于 在实际运行中调 度员不愿意 对系统做较大的调整，因 此专家系统方法可以 给调 度 员提供确实有效的建议。当然专家系统也有其 自 身的缺点:知识获取难，容错能力差 以及基础理论还不完善。 1 . 3 . 2现 有算法总结 配电网重构问 题属于大规模、混合整数、非线性的组 合优化问题。表1 . 1 列出了 现有主要配电网重构算法的性能比较结果。 表1 . 1配电网重构算法的主要性能表 算法是 否 全 局 最优解 是否需要 潮流计算 是否取决于 初始结构 计算 速度 是否采用 启发式规则 数学优化技术是是否 慢否 最优流算法否 是否快是 支路交换算法否是是 快是 模拟退火算法是是否慢否 遗传算法是是否慢否 人工神经网络是否否 较快否 专家系统否否是快是 利用 数学优化的 方法，可以 从理论 上保证得到全局最优解，但是应用于实际配 电网络时，随着维数的增多将导致严重的 “ 组合爆炸”问题:基于s a 的算法可以获 得全局最优解，但存在算法依 赖参数和计算量大的 缺点: 基于a n n 的算法不需要进 行潮流计算，可以 在很短的时间内 得出结果，但其精度取决于样本， 而要获得完整 的样本较困 难， 训练样本需要较长的时间; 专家系 统擅长 解决电 力系统中 难以 建立数 学模型而又依赖专家经验知识的问题， 但是其基础理论还不完善并且知识获取较为困 难;反观g a 具 有很多 适于求解配电网 重构的 特点，如果能结合配电 网重构本身的 特 点对算法收敛性做进一步研究，从而提高其 速度，必将在配电 网重构中 得到更好的 应用。 1 . 4本文的主要工作 通过上述介绍可知， 配电 网络重构无论是 在理论上 还是在实际应用上都有着重大 的意义和广阔的前景。 尽管配电系 统的重 构问 题是在近十 几年才引 起人们的注意， 但 在此期间 经过许多学者和电力工作者的 认真研究 和不懈努力，已 经取得了 很大的进 展， 提出了 各种数学 模型和求解算法。 本 文是 在总结 前人经验的基础上， 做了以 下一 硕士论文基于改进遗传算法的配电网络重构 些工作: l )利用遗传算法进行配电网络 重构的 过程中， 每次 迭代都需要对当 前进化代数 的网络结构进行潮流计算，通过潮流计算确定当前种群中所有个体的适应 度。 本文 针对目 前配电 网络的 现状， 在对配电网 络进行 拓扑分 析的基 础上， 改进了 原有 的基于支路电流的 前推后代潮流算法， 加入了在计算过 程中 对p v 节点的 修正方案，使得配电网 络潮流计算的 模型更加贴 近现实; 针对基本遗传算法不够完善的 地方， 采用精英选 择策略和自 适应的方法进行 解决。 原有交 叉概率和变异概率的自 适应公式 对于 适应度接近或者等于最大 适应度的 个体， 其交叉概率 和变异概率接近或等于零， 使得 优良 个体几乎 处 在一种不发生变化的 状态， 而进化初期的 优良 个体不一定 是全局 最优解， 导 致了 种群有可能收敛不到 全局最优， 本文针对这一现象 对原有的交叉概率和 变异概率自适应公式作了进一步改进，确保遗传算法最终能收敛于最优解; 构建了以 最小 化网 损为目 标的配电 网络重构的数 学模型， 论述了 在利用遗传 算法进行配电网 络重构的过 程中不 可行解的产生 原因 和危害， 通过改 进遗传 算法的编码方 式减少了 不可行解的 产生， 并利用改进 后的 交叉算 子和变 异算 子纠正在遗传 算法过程中 产生的不 可行解。 根据文中提出的改 进遗传算法编写了应用程序， 综合考虑灵活性和可扩展 性， 将程序分为 7 个模块。利用编写的程序分别对单电源和多电 源的配电网 络进行了仿真 计算， 仿真结果表明， 利用本文的 方法进行配电网 络重构是正 确可行的。 硕士论文基于改进遗传算法的配电网络重构 2基本遗传算法的 理论分析 遗传算法是一种建 立在自 然选择原理和自 然遗传机制上的迭代式自 适应概率性 搜索方法。 它通过模拟自 然界生 物进化的 发展规律， 在人工 系统中实现特定目 标的 优 化。 早在 20 世纪50 年代， 就有少数几个计算机科学家独立的进行了所谓的 “ 人工进 化系统” 研究， 其出 发点 是进化的思想可以发展成为许多 工程问题的优化工具， 形成 了遗 传算法的雏形。 但是， 由 于缺乏一种通用的编 码， 人 们只能依 赖变异而非交叉来 产生新的基因结构，因 此早期的算法收效甚微. 20 世纪60 年代中期， john holl an d 在前人工作的基础上提出了位串编码技术， 这种编码既适用于变异操作， 又适用于交 叉操作，并且强调将交叉作为主要的遗传操作。随后，h olland将该算法用于自然和 人工系统的自 适应行为的研究中，并于 1 975年出 版了 其开创性著作 a d a p tation in n atu血 an d a rt i fi d als y s t e lns 一 。为 遗传算 法的发 展奠定了 基础。 经过长期的努力， 如今， 遗传算 法己 经成为一种成熟的具有 广泛适 用性的 全局优化算法， 应用于 系统优 化、 机器学习、 工 程控制、 人工智能、 故障诊断以 及计算机 等许多领域并取得了良 好 的效果。 遗传算法的建立源于 达尔文的生物进化论和孟德尔的 遗传学说基础。 即生物体可 以通过遗传和变异来适应于外界环境。 在进化论中， 每一物种在不断的发展过程中都 是越来越适应环境， 物种的每 个个体的 基本特征被后代所继承， 但后代又不完全相同 于父 代， 子代的这些新变化， 若 适应环境则 被保留 下来， 否则就 被淘汰， 即适者生存。 遗传学认为， 遗传是作为一种指令遗传码封装在每个细胞中， 并以基因的形式包含在 染色体中， 每个基因有特殊的位置并控制每个特殊的性质。 每个基因产生的个体对环 境都 有一定的 适应性。 基因 杂交和基因突变可能产生对环境 适应性强的 后代， 通过优 胜劣汰的自 然选择， 适应性高的基因结构 就保存下来。 遗传算法通过模仿生物的遗传 进化原 理， 并利 用随机 统计理论， 在求 解过程中从 一 个初始种群开始， 逐代的 寻找问 题的最优解， 直至满足收 敛条 件或者预 先设定的迭 代次数为止。 随着问 题种类的不同以 及问题 规模的 扩大， 需要寻找一 种能以 有限的 代价来解决 搜索和优化的 通用方法， 而 遗传算法就提供了 这样 一个有效的途 径， 它不同 于传统的 搜 索 和 优 化 方 法， 主 要 区 别 在 于 133: 1) 自 组织、自 适 应和自 学习。 应用遗 传算法求解问 题时， 在编码方案、 适应度 函数及遗传算子确定后，算 法将利用进化过程中 获 得的 信息自 行组织搜索。 由于基于 自 然的选择策略为 “ 适者生存” ，因而适应度大的个体具有较高 的生存概率。自然选择消除了算法设计过程中的一个最大障碍，即需要事先 描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因 硕 士 论 文 基于改进遗传算法的配电网络重构 此， 利用遗传 算法的 方法可以 解决那些复 杂的 非结构化问 题; 2) 遗传算法的本 质并行性。 遗传算 法按照并行方式搜 索一 个种群数目 的点， 而 不是单点。 它的并行性表现在两个 方面， 一 是遗传 算法的内 在并 行性， 即遗 传算法本身非常 适合 大规模并行计算。 二是遗传算法的内含并行性， 它采用 种群的 方式组 织搜索，同时 搜索解空间内 的多 个区 域， 并相互交流信息; 3) 遗传算法不需要求导或者其它辅助知识，而只需要影响搜索方向的目标函数 和相应的适应度函数; 4) 遗传算法强调 概率 转换规则， 而不是确定的 转换规则; 5) 遗传算法以决策变量的某种形式的编码而不是直接以决策变量的值作为运 算对象。这种对决策变量的编码处理方式，使得在优化计算中能充分借鉴生 物学中 染色体 和基因 概念， 模仿自 然界中 的生物遗传和进化机制， 方便的运 用各种遗传算子。 2 . 1 基本遗 传算 法的 基本概念 遗传算法基于自然选择的生物进化， 是一种模仿生物进化过程的随机方法， 下面 给出 一些生 物学中 关于 遗传的 基本概念和常用术语， 这对于理解遗传算法是非常重要 的。 染色体:遗传物质的主要载体，指多个基因的集合. 基因: 控制生 物性 状的 遗传物质的 功能和结构的 基本单元， 又称遗传因 子。 表现型:由 染色体决定 性状的 外部表现， 或者说根 据基因 形成的 个体. 基因型:遗传基因在染色体中所占据的位置。 个体:指染色体带有特征的实体。 种群:染色体带有特征的个体的集合。 该集合内个体数称为种群的大小。 有时个 体的集合也称为个体群。 进化: 生物 在延续生存的 过程中， 逐渐适应周围生 存环境， 使得其品 质不断 的得 到改良，这种生命的现象称为进化。 适应度: 指某个 物体对于生存环境的适应 程度， 适应程度越高的 个体 将获 得更多 的繁殖机会。 选择: 指以一定 的概率从种群中 选择若干个体的操作。 一般而言， 选 择的过 程是 一种基于适应度的 优胜劣汰的过程。 交叉: 在两 个染色体的某一相同 位置处d n a被切断，其前后两串分别交叉 组合 形成两个新的个体。 变异: 在 细胞进行复 制时 可能以 很小的概率产生 某些复制差错， 从而使d n a 发生 某种变异， 产生出新的 染色体， 这些新的染 色体 表现出 新的性状。 l 0 硕 士 论 文 基于改进遗传算法的配电网络重构 编码:从表现型到基因型的映射. 解码:从基因型到表现型的映射。 2.2羞本遗传算法求解过程 遗传算法 模拟了自 然选择和遗传中发生的 选择、 交叉和 变异等现象。 从任意初始 种群出 发， 通过随 机选择、 交叉和 变异操作， 产生一群更适应环境的 个体， 使群体进 化到搜索空间中 越来越好的区 域， 这样逐代的不断繁衍进化， 最后收 敛到一群最适应 环境的个 体， 求 得问题的最 优解。图2. 1 是基本 遗传算 法的总 流程， 下文将结合该图 来具体分析整个的遗传操作过程中一些重要的步骤。 染色 体进行 编码， 产生初始种群 计算种 群中 每个个体的 适应度呸 傲值 各种溃传操作 产生新一代种群 停止准则的判断 图2.1基本遗传算法流程图 2 . 2.1 编码 结合图2 . 1 可知， 利用遗传算法进行问 题求解时， 首 先要确定的是问 题的目 标函 数和变量 ， 这就必须在目 标问 题实际表示 与染色体位串 之间建立一 个联系， 将目 标问 题转化为 染色体位串的操 作叫 做编码， 反 之叫做解码。 这 样做的 原因主 要是因 为在遗 传算法中 ， 问 题的解是用数字串 来表示的， 而 且遗传算子也是直接对 数字串 进行操作。 选择一个什么样的 编码方式， 对遗传算子尤 其是交 叉和变异算子的功能 和设计有着很 1 l 硕 士 论 文 基于改进遗传算法的配电网络重构 大的影响。 理论 上而言， 编码应当 适应要解 决的问 题， 而不仅仅是描述问题。 通常情 况下，编码应当满足以下四点原则: 1) 完全 性。 原则 上， 分布在问 题空间范围内的 所有点( 可 行解) 都应当可以 被构 造出来; 2) 封闭 性。 每个基因编码都对应一 个可接受的 个体， 封闭性保 证了 系统从不产 生无效的个体; 3) 紧 凑 性。 若 两 种基 因 编码 9 ， 和9 2 都 被 解 码 成 相同 的 个 体， 且9 1 比 9 2 占 的 空 间 少 ， 就 认 为9 ， 比 9 2 紧 凑 ; 4) 可扩展性。 对于具体的问 题， 编码后若想增 加一 种表现型， 作为基因型的编 码大小也做出相 应的 增加。 遗传算 法的 编码方式 有很多， 常 用的 有二进制编码和实数编码， 除此之外还 有学 者针 对特殊问 题提出的 一些编码方式， 例如十 进制 编码、 格雷码编 码、 d n a编码等。 不同的 编码方式有着不同的 优点和缺点， 以下 里主要讨论二进制编码和实 数编码这两 种编码方式。 1) 二进制编码 二进制编 码与 计算机编码的方式相一 致， 适用 于计算机计算。 由 于码串的 每一位 只有1 或者0 两 种码制， 在交 叉和 变异等遗传操作中原理清晰， 操作简单， 便于实现， 其表达的变量范围大， 非常适合于表示离散变量。 但对于一些多维、高精度要求的连 续函 数优化， 二进制编 码同 样也存在着连续函数离 散化时 的映射误差， 个体编码串 较 短时 可能达不到 精度要求，较长时 搜索空间 又会急剧扩大等缺点。 2) 实数编码 实数编码方法 是指个体的每个基因 值用某一范围内 的一个实数来表 示， 个体编码 的长度等于其决 策变量的个数， 即 使用决策 变量的 真实 值进行编码。 它必须保证基因 值在给定的区间 范围内 ， 而通过交叉、 变异等遗传操作后产生的新 个体的 基因值也必 须限 制在该区间范围 之内。 实数编码 运算效率高， 所需计算时间较短， 便于处理复杂 的决策变量约 束问 题， 但是其收敛 性无法保障。 就二进制编码和实数编码而言， 一般情况下二进制编码比浮点 数编码搜索能力 强， 但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。 具体选择 什么样的编码方式应当根据具体问题来确定。 2 . 2.2初始种群的 选取 随机产生n个初始串结构数据， 每个串 结构数据成为一个个体， n个个体构成 了 一个群体。 基本遗传算法以这 n个个体作为初始点 开始迭代。设 置进化代数计数 器 t 声 0 : 设置最大进化代数t ; 随机生成m 个个体作为初始群体 p(0)。 有些学者认为: 硕 士 论 文 基于改进遗传算法的配电网络重构 初始群体应该随 机选取， 只 有随机 选取才能达到所 有状 态遍历， 因而 最优解在 遗传算 法的进化中最终 得以 生存。 但是， 种子的 随机选取加大的进化的 代数， 延长了 进化时 间。因此， 另外有些学者提出应该采用一些启发式算法或者经验选择一些比较好的染 色体作为初始种群。 种群的大小 代表种群中个体的数量， 当该取 值较大 时， 能 够更为准 确的 反映问 题 本身，也更 容易 收敛于全局最优，但是却是以 牺牲了 算法的运行效率为 代价; 反之， 如果取值较小， 算法的运行效率会提高， 但是却降 低了 种群的多样性， 导致出 现“ 早 熟”现象，也就是局部收敛。究竟如何选择种群的大小应当根据实际问题来确定，当 问题重点在最优解时，不妨选择较多的初始种群， 反之，当问题的重点是计算速度的 时候就不能够再选取很多的初始种群了。 2 . 2.3 适应 度函 数的 设计 遗传算法在进化 搜索中 基本不利用外部信息， 仅以 适应度函数为依 据， 利用 种群 中 每个个体的适应 度值来进行搜索。 因 此， 适应度函数的 选取至关重要， 直接影响到 遗传算法的 收敛速 度以 及能否找 到最优解。 一般而言， 适 应度函 数是由目 标函数 变换 而成的。 如果说编码是遗传算法的基础， 那么适应度函数的设计就是遗传算法的关键， 因 为个体的好坏 是利用适应度函 数值来进行评价的， 值越大说明该 个体越好， 进而 就 会有更多的繁殖 机会， 反之值越小， 说明 该个体越差， 相应的繁 殖机会也会越少， 这 样便保证了遗传算法的寻优效果. 设计适应度函数应当遵循以下三点原则: 1) 单值、连续、非负、最大化。这些是数学方面的基本要求: 2) 合理。 要求适应度函数能够恰如其分的反 映对应解的优劣 程度: 3) 计算量小。 适应度函 数的 设计应当 尽量简化， 避免一些过于复 杂的计 算过程， 这样可以减少计算时间，提高计算效率。 如果 适应度函 数设计不当就会 产