双层多种群PSO在水库群供水优化调度中应用
卿逸男1，丁永生1，2，曾献辉1，2，郝矿荣1，2
【摘 要】针对水库群供水优化调度问题，提出了一种带差分进化的双层多种群粒子群算法（DE-TMPSO）。该算法实现粒子群优化算法的群体拓展和双并行运行机制，针对性地提高粒子群算法的全局搜索能力，同时采用不同粒度的多子群并行机制、种群间的双向最优信息流动以及引入差分进化策略也提高了该算法的局部搜索能力，在一定程度上避免了“早熟”现象的发生，具有较好的稳定性，收敛速度也得到了提高。该算法应用于我国南方某流域的水库群供水优化调度问题中，调度结果合理，为求解高维、复杂的水库群供水优化调度提供了新的思路和方法。
【期刊名称】计算机工程与应用 【年(卷),期】2013(049)005 【总页数】5
【关键词】供水优化调度；水库群；多种群粒子群；差分进化
1 引言
我国水资源时空分布不均，缺水问题严重影响着人民的生活生产以及生态环境，合理高效地利用水资源是目前亟待解决的问题。如何通过水库群联合水量优化调度，更好地调配有限水资源一直是研究的热点问题。水库群供水优化调度问题是一个具有各类约束条件的大型、动态的负载非线性系统的优化问题，国内外学者进行了广泛研究，其中包括：动态规划法、网络流法、大系统分解协调、人工神经网络法、遗传算法、模拟退火算法等[1]。
粒子群优化（PSO）算法是由Kennedy和Eberhart于1995年提出的一类基
于群智能的随机优化算法[2]，其思想来源于对鸟群捕食行为的研究，PSO算法有着算法简单、容易实现，并且可调参数少等特点，适用于求解大量非线性、不可微和多峰值的复杂优化问题，已应用于多个学科和工程领域[3-5]。但通过研究发现基本PSO算法本身存在较强的“趋同性”，在进化过程中会导致多样性的大量丧失，常常会陷入到局部最优解中，全局搜索能力较差，求解精度不高；同时，在算法后期收敛速度较慢。如何保持群体的多样性，避免算法过早地陷入局部极值是改进粒子群算法的一个直接出发点。
本文在前人研究[6-11]的基础上提出一种带差分进化的双层多种群粒子群优化算法（DE-TMPSO），利用多个普通子群覆盖不同的解空间，加大粒子的多样性；同时利用精英种群重点进行局部搜索，添加差分进化操作有效地减少陷入局部极值的概率，具有更好的全局搜索能力和局部搜索能力，提高了算法的效能。
2 基本粒子群优化算法
PSO算法先在可行解空间随机初始化M个粒子构成初始种群，其中每个粒子表示问题的一个潜在解，粒子在解空间中朝着最优的粒子飞行，逐代进化，最终得到问题的最优解。它的进化更新规则如下[2]：设第i个粒子的位置为，其速度为，每个粒子迄今找到的最优解为个体极值pbesti=( ) pbesti1，pbesti2，…，pbestin，全种群迄今所找到的最优解即为全局极值gbest=( ) gbest1，gbest2，…，gbestn。下一代粒子的速度和位置的第d( ) 1≤d≤n维根据如下方程变化：
其中，i=1，2，…，m，m为种群规模；d=1，2，…，n，n为粒子维数；c1和c2分别为认知部分和社会部分的加速常数，一般设定速度上限vmax；r1和
r2为均匀分布于[0，1]之间的随机数；ω为惯性权重值，是一种控制群的搜索和挖掘能力的机制，大的ω值有利于全局探索，多样性增加，小的ω值促进局部的挖掘[12]，建议采用线性递减权策略：
其中，k为当前进化代数，kmax为最大进化代数，ωstart为初始惯性权值，ωend为进化至最大代数时的惯性权值（终止惯性权值）。
3 DE-TMPSO算法
3.1 思想与结构
DE-TMPSO算法分成上下两个层次：上层由具有问题较好解的粒子组成的精英种群，下层由N个普通子群构成，上下两层组成一个相互影响的闭环循环，如图1所示。
下层的各个普通子群之间相互独立地进化，并从精英种群中得到优良信息指导自己的进化进程；各个基础种群将进化得到的优良粒子贡献出来，输送给精英种群。每个普通子群分别进行初始化和独立搜索。为了确保候选解的多样性以防止算法陷入局部最优解，每个子群分别设置不同的参数。具有粗粒度参数的子群负责搜索全局最优解，而其他种群用于细化局部搜索和增强求解精度。 上层的精英种群从每个子群选择较好的粒子来进行初始化，并在迭代过程中不断地选取每个子群中最好的粒子来替换自身较差的个体。为减少算法陷入局部最小值的可能，在精英种群中添加差分进化操作，有助于粒子跳出局部极值，同时差分进化操作不会出现因变异而产生的倒退，能够保证算法的整体最优值不受到影响。反过来，选取精英种群中前N（N为下层普通种群个数）个粒子随机分配到各个普通子群中指导它们进化更新。 3.2 进化规则
双层多种群PSO在水库群供水优化调度中应用
