Solving the Economic Dispatch Problem of Power Systems Based on Multi-Population Genetic Algorithm ()
1. 引言
遗传算法,这一灵感源自生物进化理论的优化技术,已经成为全球范围内寻找最优解的有力工具[1]。它以其独特的优势在智能算法领域占据了不可替代的地位,被视为一种高效的优化手段,具有广泛的应用前景和深远的研究意义。在实际应用中,遗传算法被广泛用于多个领域,包括但不限于路径优化[2] [3]、电力调度[4]和多目标优化[5]等。
电力系统经济调度问题是电力系统领域中的经典问题[6],其目的是在满足发电机出力约束和系统有功功率平衡的前提下实现最小的发电成本[7]。因此对于电力系统经济调度问题的求解具有现实的经济和政治意义。针对电力系统经济调度问题本文首先采取经典遗传算法对其进行求解,然而,在实际操作中,传统的遗传算法可能会遇到一个主要问题:它们倾向于过早地收敛到局部最优解,而非全局最优解。为了克服这一挑战,对遗传算法的算子、变异策略和编码方法进行改进成为了研究的重点。这些改进措施能够有效提高遗传算法的性能。
在经典遗传算法的执行过程中,种群中表现优异的个体被选中的概率较高,这可能导致算法过早地收敛,进而容易陷入局部最优解。为了规避或延缓这一现象,本文提出了基于多群体遗传算法的改进策略,对个体进行更新。具体来说,每个种群都被赋予了独立的交叉概率和变异概率,这样的设置使得每个种群中的个体更新环境都有所不同。这种差异化的更新机制有效地增强了算法对全局解的搜索能力,并在一定程度上限制了算法过早地陷入局部最优解的风险。通过这种方式,算法能够更全面地探索解空间,从而提高了找到全局最优解的可能性。
2. 经典遗传算法
经典遗传算法(Genetic Algorithm, GA) [8]模拟了自然界生物进化的过程,它融合了达尔文的自然选择理论和孟德尔的遗传学说。这种算法作为一种独特的搜索策略,模仿了生物在自然选择和遗传过程中的演化模式,旨在寻找问题的最优解[9] [10]。由于其高效性,遗传算法已经在科学与工程的多个领域得到了广泛应用,证明了其广泛的实用价值。
经典遗传算法的核心过程可以简述为:算法在优化搜索过程中,对拥有特定属性的群体中的个体执行遗传操作——选择、交叉与变异等操作,通过迭代产生新世代群体,逐步逼近最优解决方案。这一过程是迭代进行的,每一代群体都通过适应度函数进行评价,并根据适应度的高低进行选择、交叉和变异操作,以产生新的群体。更新的族群既保留了前代的特性,又实现了超越,经由反复迭代,族群的整体适应力持续增强,直至达到预设的条件或完成既定的迭代数[11] [12]。
遗传算法,作为一种广受青睐的优化技术,其核心步骤涵盖了个体编码、选择、交叉和变异等关键环节。以下是对遗传算法中这些关键要素及其操作流程的详细阐述。
2.1. 遗传编码
遗传算法的直接操作对象为编码后得到的字符串,而非直接针对问题的原始解。所以在正式求解问题前,要先设计一种解决方案向遗传编码转化的机制,此过程被称作编码。面对不同的问题背景,人们开发了多样化的编码方案,例如常用的遗传编码方法就包括二进制编码、格雷码、实数编码和符号编码等[13]。本文求解电力系统经济调度问题采取二进制编码。二进制编码的解码过程具有简单易操作、操作易实现等优点。如果我们取某一解集A,设A的取值范围为[Umin, Umax],参数的长度设为b,b表示的二进制编码符号串,解集A可产生的编码有2b种,则A编码精度为:
(1)
二进制编码符号串的长度对问题求解的精度是有影响的,不同的符号长度求解出来的精度是不一样的,二进制编码长度越长,其所对应的编码精度就越高,阶跃值也就越小;反之,二进制编码长度越短,其所对应的编码精度就越低,阶跃值也就越大。
2.2. 选择操作
遗传算法中的选择机制旨在从群体中甄别并保留优质个体,同时减少劣势个体的遗传机会,此过程也常被称作再生操作。选择算子基于个体适应度评估[14]。本文选取“轮盘赌选择”实现选择操作。“轮盘赌选择”根据每个个体的适应度值分别占总适应度值的比例,为每个成员分配一个累积概率值。在选拔阶段,则是随机生成一个位于0与1区间的数值,借此数值匹配至某个个体的累加概率区间内,以此决定选取的个体。这种方法简单明了且高效,确保了适应度较高的个体有更大的可能性被选中。
对于一定规模为n的群体
,其中个体
的适应度值为
,那么它的选择概率为:
(2)
2.3. 交叉操作
遗传算法中的交叉操作,灵感源于自然界中的有性生殖,是其标志性的行为特点。此步骤通过模仿基因的重新组合,旨在将优质基因遗传给后代,并催生具备混合基因特征的新个体。具体过程如下:
1) 首先,从交配池中随机抽取一对参与交配的个体;
2) 依据染色体的长度L,再随机选定这对个体
中一个或更多整数k作为交叉位置;
3) 按照预定的交叉概率进行操作,两个个体在特定的交叉点交换它们的遗传片段,从而产生一对新的后代。
2.4. 变异
变异算子是根据基因突变得到新个体模拟而来的。它在遗传算法中起辅助作用,主要是维持种群的多样性,防止种群早熟进化。变异算子可以在搜索解的过程中加强局部随机搜索能力。同时,变异算子和交叉算子的结合可以快速完成遗传算法中的优化过程,最终收敛到最优解。
变异换另一种说法就是突变,基因发生突变然后出现了新的生物或者种群,这也是生物多样性的主要途径之一。变异是随机的,只是具有一定概率性。在遗传算法中,变异就是将所表示的二进制编码中的某一段或者几段的数值取反,即1变成0或者0变成1。
3. 多种群遗传算法
多种群遗传算法[15]首先引入M个多种群来执行遗传算法的基本操作;每个种群进化过程中每代的最佳个体将被人工选择算子保存,最终放入精英种群;而移民算子作为这M个种群的交流基站,会每隔几段进化周期就会把源种群内适应度最高个体替换掉目标种群中的适应度最差的个体,由此来进行各种群之间的信息的沟通与交换。不断地执行以上操作,直到最优个体(适应度最高的个体)达到设定的进化代数,跳出循环,终止算法。
各种群之间是通过移民算子进行信息传递来联系的,这个联系是定期的,每隔一段时间(一般为几个进化周期)会将进化过程中各种群搜索到的最优个体引入到其他种群中,这样各种群之间就可以实现信息的沟通与交换。具体操作是将各种群搜索得到最优个体替换掉对应种群的最差个体。从上述可知,移民算子在多种群遗传算法中是不可或缺的部分,如果缺失了这部分,那么各种群间的联系也会被中断,多种群之间就会各自成为一个参数设定不同的经典遗传算法,这样多种群遗传算法就无法进行完整的构建,失去了它的特性。
多种群遗传算法会引入多种群,多种群里不同的种群会设计不同的参数进行控制。经典遗传算法变异和交叉概率的设定会影响到最终的搜索择优的结果,也就是变异和交叉概率的值会影响到在运行过程中算法的全局搜索能力与局部搜索能力。但是多种群遗传算法,控制多个种群的参数,使得不同种群相互进化,弥补了传统遗传算法的这一不足。
各种群进化过程中每一代的最优个体保存下来,保存下来的最优个体会放入到精华种群中,也就是说,精英群体是这些群体在循环迭代进化过程中搜索到的最优个体的集合。同时,这个群体不同于提供最优个体的群体,它不需要选择、交叉、变异等遗传操作来保证最优个体不会丢失或受损。同时,精英种群也是有着决定算法是否结束跳出循坏迭代的功能。在这里,最优个体的最小维持代数被用作结束循环的判定依据。该判定依据主要是使用了遗传算法在进化的过程中的经验积累。
4. 遗传算法在电力系统优化中的应用
4.1. 电力系统经济调度问题数学模型的建立
电力系统经济性调度问题的数学模型表述如下:
(3)
其中,
为系统总发电费用;
为系统内发电机总数;
为第
台发电机的有功功率。
用二次函数近似表示为:
(4)
其中,
为系统参数。
约束条件:
经济调度问题面临双重限制:容量界限与平衡要求。其中,容量界限指的是:
(5)
其中,
,
分别为第
台发电机有功功率输出的上下限。
平衡条件为:
(6)
其中,
为系统负荷需求。
4.2. 仿真
在本文中,选择了一个包含13台发电机组的系统作为模拟演示的案例。这13机组系统的负荷为1800 MW。13机组系统的数据如表1所示。
表1. 13机组系统数据
机组 |
|
|
|
|
|
1 |
0.00028 |
8.1 |
550 |
0 |
680 |
2 |
0.00056 |
8.1 |
309 |
0 |
360 |
3 |
0.00056 |
8.1 |
307 |
0 |
360 |
4 |
0.00324 |
7.74 |
240 |
60 |
180 |
5 |
0.00324 |
7.74 |
240 |
60 |
180 |
6 |
0.00324 |
7.74 |
240 |
60 |
180 |
7 |
0.00324 |
7.74 |
240 |
60 |
180 |
8 |
0.00324 |
7.74 |
240 |
60 |
180 |
9 |
0.00324 |
7.74 |
240 |
60 |
180 |
10 |
0.00284 |
8.6 |
126 |
40 |
120 |
11 |
0.00284 |
8.6 |
126 |
40 |
120 |
12 |
0.00284 |
8.6 |
126 |
55 |
120 |
13 |
0.00284 |
8.6 |
126 |
55 |
120 |
在本节,探讨了应用经典遗传算法来解决电力系统经济调度问题。种群数量设置400,交叉概率设置为0.7,变异概率设置为0.05。程序共运行了5次,每次运行后目标函数的变化趋势如图1所示,所有的最终结果保留在表2。
通过观察图1所展示的信息,可以发现最优目标函数变化曲线在迭代初期迅速变化,但是在迭代后期基本保持不变。这表明在迭代的后期,经典遗传算法会陷入了局部最小值的困境,并且无法从这一局部最小值困境中跳出来。
图1. 经典遗传算法运行5次最优解变化曲线
表2. 经典遗传算法多次运行程序目标函数数最优值
程序运行次数 |
目标函数最优值 |
1 |
17993.3 |
2 |
17997.7 |
3 |
17985.2 |
4 |
17995.7 |
5 |
17981.7 |
同样的,还是以13台发电机组的系统作为模拟演示的案例。但是在下文中采用多种群遗传算法解决电力系统经济调度问题。为了便于比较,多种群遗传算法设置20个种群,每个种群包含20个个体,个体共计20 × 20 = 400,多种群遗传算总个体数量设置和经典遗传算法个体数量相同,同时对于多种群遗传算法交叉概率0.7~0.9之间随机数,变异概率设置为0.001~0.5之间的随机数。程序运行5次,每次运行后目标函数变化趋势如图2所示。所有的最终结果保留在表3。
按照同样的思路观察图2,可以发现在迭代的前期,图2曲线迅速变化(也就是说迅速逼近问题的最优解),同样的趋势可以发现在图1中。但是图2曲线在整个迭代过程后期中依然保持变化,虽然这种变化与前期的过程相比较变化较小。从中可以得知,对遗传算法采取多种群遗传算法可以有效规避早熟收敛困境。
图2. 多种群遗传算法运行5次最优解变化曲线
表3. 多种群遗传算法多次运行程序目标函数最优值
程序运行次数 |
目标函数最优值 |
1 |
17949.1 |
2 |
17948.0 |
3 |
17946.2 |
4 |
17967.4 |
5 |
17953.7 |
对比两次运行结果,即经典遗传算法的结果(表2)和改进遗传算法的结果(表3),可以明显看出改进后的遗传算法得到的解决方案更为优异(考虑到我们的目标是解决最小化问题,因此数值越小意味着算法的性能更好)。仿真结果验证了多种群遗传算法在解决该电力系统优化问题时比经典的遗传算法效果更好。
基于表2和表3中展现了经典遗传算法与多群体遗传算法的重复执行五次的仿真结果。在此基础上,本文通过计算它们的统计学特性来实现进一步分析了这两种算法的性能差异。我们关注的统计特性包括每次运行得到的最优解的期望值。较小的期望值表明算法更接近全局最优解。表4详细列出了这些统计数据。从表4中可以看出,多群体遗传算法的期望值为17952.8,而经典遗传算法的期望值为17990.7。这意味着多群体遗传算法得到的解更接近全局最优解,因为期望值越小,表明算法找到的解越接近最优值。具体来说,多群体遗传算法的期望值比经典遗传算法低了37.9 (17990.7 − 17952.8 = 37.9)。这一差异表明多群体遗传算法在精度上提高了约37.9个单位显示出更好的性能。
表4. 多种群遗传算法与经典遗传算法期望值比较
方法 |
期望 |
多种群遗传算法 |
17952.8 |
经典遗传算法 |
17990.7 |
5. 总结
本文首先介绍了经典遗传算法概念和具体的实现步骤,随后指出经典遗传算法容易陷入局部最优。因此在经典遗传算法的基础上引入了多种群遗传算法的概念,在多种群遗传算法中每个种群可以独立设置交叉概率和变量概率,同时邻近种群交换信息,利用本种群最优个体替换邻近个体最差个体。仿真结果表明多种群遗传算法与传统的经典遗传算法相比较可以在一定程度中避免算法过早陷入局部最优同时可以获得更佳的调度结果。
基金项目
桂林理工大学科研启动基金(GLUTQD2018001)。
Conflicts of Interest
The authors declare no conflicts of interest.
Appendix. Abstract and Keywords in Chinese
基于多种群遗传算法求解电力系统经济调度问题
摘要:电力系统经济调度问题是电力系统领域经典问题。本文首先利用传统的遗传算法实现电力系统经济调度问题的求解,仿真结果表明经典遗传算法会陷入了局部最小值的困境。因此我们引入多种群遗传算法,在不同的种群设置不同的交叉和变异概率,同时引入移民算子,将各种群搜索得到最优个体替换掉相应种群的最差个体。仿真结果表明引入多种群遗传算法在整个迭代过程在一定程度上避免算法陷入早熟的情况。与经典遗传算法相比较,多种群遗传算法获得的最优解明显由于经典遗传算法获得的最优解。
关键词:经济调度问题,多种群遗传算法,优化