1、遗传算法简介基本遗传算法的基本操作遗传算法的并行性研究并行遗传算法简介并行遗传算法的应用实例介绍-三峡-葛洲坝梯级水库遗传算法的基本操作选择选择:按照一定的规则从原始群体中随机选择若干个个体作为繁殖后代的群体。例如：可根据适度值进行选择。交叉交叉:利用来自不同染色体的基因通过交换与重组产生新一代染色体，从而产生下一代新的个体。过程是：在当前群体中任选取两个个体，按给定的交叉概率p在染色体的基因链上选择交叉位置，进行部分基因得到新的染色体。变异：变异：变异是按给定的 变异概率pmrandom0,1改变某个体的某一个基因值，以生成一个新的个体，在二进制编码中，就是将变异位置处的变异基因由0变成1，
2、或由1变0。遗传操作遗传操作 选择选择 变异变异 交叉交叉遗传算法的初步定义传统遗传算法,适应度的计算是很费资源的。因此，求解问题的复杂性及难度的增加，提高问题的运行速度成为重点遗传算法的并行性研究遗传算法并行性的提出遗传算法的并行性分析1、内在并行性2、隐含并行性 将并行计算机的高速并行性和遗传算法固有的并行性两者的长处彼此结合起来，解决复杂问题。方案一：全局型一主从式模型(master-slavemodel)：全局型又称主从式模型，顾名思义，并行系统分为一个主处理器和若干个从处理器。主处理器负责整个种群的运行，各个从处理器处理来自主处理器的个体 主要负责个体的适应度计算，并把结果发给主处理
3、器全局处理。主从式模型(图1)分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；各个从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。主从式模型对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。图图1 全局型全局型主从式模型主从式模型是方案二：独立型一粗粒度模型(coarse-grained model)图图2 岛屿模型岛屿模型图图3 脚踏石模型脚踏石模型粗精度模型领域之间迁移的主要方法：岛屿模型与脚踏石模型开始随机产生一个初始种群S将S分成N个子群并定义邻域
4、 选择操作 交叉操作 变异操作 邻域间个体迁移产生新的一代子群体 满足收敛要求结束否并行遗传算法的流程图方案三：分散型一细粒度模型(fine-grained modeD 在细粒度模型中如下图所示，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行(根据一个预先定义的邻域结构来判断个体之间是否相邻)，所以网格上的邻域关系就限定了个体空间上的关系。图图4 细粒度模型细粒度模型 方案四:混合模型的并行遗传算法 混合模型的并行遗传算法就是将上述三种模型进行混合形成的层次结构的并行遗传算法；首先，按上层的并行模型将全局种群划分成若干种群。然后，各种群
5、再按下层的并行模型将其分成若干子种群。在下层模型中每个子种群按下层模型进行进化，而在上层模型中，种群之间按上层模型协调运行。无论是从下层还是从上层角度看，都是子种群内部信息交互量大，种群之间信息交互量小。混合模型的层次结构主要有三种：粗粒度一细粒度、粗粒度一粗粒度、粗粒度一主从式。实际中应用较多的是粗粒度一主从式(见下图)。1、水库优化调度数学模型目标函数：以满足各约束条件下水电站发电量最大作为目标函数式中:Ni,t为水电站i 时段t 出力;t为时段时长;I为水电站数;T为时段数。约束条件：水库优化调度的主要约束条件如下。1）水量平衡方程2）水位约束3）流量约束4）出力约束5）边界条件式中：V
6、表示水库的蓄水量，Q为水库在某时段的入库与出库流量，Z为书库在某时段的水位，N为允许的水电站出力大小tNmaxT1tI1iti,OBJp引言引言：水库优化调度研究的基本内容是，根据水库来流过程，遵照调度准则，运用优化方法，寻求能使水库发电、防洪、灌溉、供水等各部门在整个分析期内的总效益最大的调度方案，其本质上属于对高维、非线性问题的求极值运算。tQQVVtOUTitINititi,1,tUUitUitULiZZZ,背景资料：1）三峡水利枢纽工程，坝址位于湖北省宜昌市三斗坪镇，是一个兼具防洪、发电、航运等多项综合效益的大型水利水电工程。三峡水电站左、右侧电站装有额定出力70 万kW 的ALSTO
7、M、VGS、东电、哈电等四种机型的水轮发电机组。葛洲坝水利枢纽工程，坝址位于三峡水利枢纽工程下游38km 处，是三峡水利枢纽的反调节水库。葛洲坝水电站大江、二江水电站装有小机(12.5 万kW)、大机(17 万kW)、东电(14.6 万kW)、哈电(14.6 万kW)等四种机型的水轮发电机组。2)已知各水库上游水位-库容关系曲线，下泄流量-下游水位关系曲线，入库流量-水头损失关系曲线，各电站机组动力曲线和出力限制线。对1882 2010 年119 年水文年宜昌站径流流量资料应用P-曲线进行水文频率分析，得到来水频率50%的1906 年作为平水代表年，以旬划分时间步长进行求解计算。由于葛洲坝为日
8、调节水库，在以旬为时段步长进行计算时可认为葛洲坝水位为常数，故可将葛洲坝与三峡视作整体考虑。并行遗传在本例中的优化处理：1、适应度函数及约束处理 2、编码方法 3、选择算子 4、最优保存策略 5、交叉算子 6、变异算子 7、迁移拓扑，迁移规模，迁移策略1)具体实例参数设置：标准遗传算法 SGA 采用参数:种群大小取500，迭代次数取5000，选择算子竞争规模取2，交叉概率取0.85，变异概率取0.05，最优个体保存比例取10%。并行遗传算法CGGA 采用参数:子种群数取5，子种群大小取100，因而总群体大小为500，迁移率取1，同步迁移方式，迁移周期为5，选择算子竞争规模、交叉概率、变异概率、
9、最优个体保存比例同SGA。SGA 和CGGA 分别进行5 次计算并与动态规划(DP)结果对比，其中DP 计算时对三峡库水位进行离散，离散点取100 个，几种算法发电量结果的对比如表1 所示表表1 几种算法发电量结果对比几种算法发电量结果对比 2)收敛性能 SGA 和CGGA 的收敛曲线如图5 所示，其中虚线表示5 次SGA 的收敛情况,实线表示5 次CGGA 的收敛情况。图图5 SGA与与CGGA收敛曲线收敛曲线3)3)并行性能并行性能 本例最多采用8 个计算进程数，为便于进行并行性能评价，取1 8 的最小公倍数840 作为总群体规模，其他参数不变，重新进行SGA、CGGA 计算，记录计算时间
10、，并计算加速比Sp和并行效率Ep。CGGA 并行性能评价如表2 所示。从表2 可以看出随着计算进程数的增加，计算时间逐渐减少，加速比Sp逐渐增大，并行效率Ep先增大后稳定在1.56。表表2 CGGA并行性能评价并行性能评价图图6 CGGA加速比曲线加速比曲线 4 结语 本文采用PGA 粗粒度模型(CGGA),引入迁移算子，以三峡-葛洲坝梯级水库为例，将基于双向环迁移拓扑的CGGA 应用于水库调度模型求解。从本文的计算结果与分析中能够得出如下结论:从计算结果看，SGA的大种群规模并非避免早熟发生的有效保证，计算结果时有收敛到局部最优的情况发生(本例最劣解977.1亿度),同时SGA计算耗时较长(
11、本例计算时间15.46min)，而CGGA能够同时提高求解质量(本例最劣解978.8亿度)和求解速度(本例计算时间2.32min)从收敛性能看,SGA的大种群规模虽有丰富的基因库，但经过一定迭代后种群中的较优个体同化了种群中的其他个体，造成优良基因的丢失，而CGGA 由于种群隔离保证了种群间的个性，避免优良基因的丢失，从而避免总群体趋于同化;从并行性能看，保持总群体规模不变，随着计算进程数的增加，CGGA 计算时间逐渐减少，加速比Sp逐渐增大，并行效率Ep先增大后稳定在1.56，做出CGGA的加速比曲线,发现CGGA加速比远远大于线性加速比,说明CGGA能够充分合理地利用各个计算进程，避免资源浪费。虽然就本例来看，CGGA在计算结果、收敛性能、并行性能方面有一些优势，但它引入了更多的参数，增加了算法的不确定性，难以确定合适的迁移方式，包括迁移拓扑、迁移率、迁移间隔、迁移策略等，所以在CGGA的研究中亟待解决的问题是如何确定合适的迁移方式。
