系统优化的新算法

动态规划的维数灾1231211ZmaxZmin10……单一水库:解的个数:6×6×6×…=611水库群维数灾3.5系统优化理论的新进展遗传算法1、遗传算法概述遗传算法（geneticalgorithm，简称GA）是由美国J.H.Holland于1975年提出的一种全新的优化搜索算法。GA发展初期，并没有引起学术界的关注，因而发展比较缓慢，直到八十年代，GA的研究才引起重视并逐步成熟起来，目前，已在组合优化、机器学习、自适应控制、模式识别、神经网络、经济预测等领域取得了令人瞩目的应用成果。基本思想来源于遗传进化，根据自然选择和适者生存原理，利用简单的编码技术和繁殖机制，模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解。把搜索空间（欲求解问题的解空间）映射为遗传空间，把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（或个体），向量中每一个元素称为基因。所有染色体组成群体（群体中染色体个数用POP表示），并按预定的目标函数（或某种评价指标）对每个染色体进行评价，根据其结果给出一个适应度值。1．1遗传算法的实现算法开始时，先随机地产生一些染色体（欲求解问题的候选解），计算其适应度，根据适应度对诸染色体进行选择、交叉、变异操作，剔除适应度差的染色体，留下适应度较好（性能优良）的染色体，从而得到新的群体。新群体的染色体是上一代群体的优秀者，继承了上一代的优良性态，因而明显优于上一代，这样就能向着更优解的方向进化，直至满足某种预定的优化收敛指标。参数编码和生成初始群体p（n）计算各染色体适应度通过遗传运算去劣存优生成种群P（n+1）是否满足终止条件解码，输出最优结果选择交叉变异ＮＯ1．2基本遗传算子（1）选择算子用于模拟生物界去劣存优的自然选择现象，其作用是将优良个体（较优解）直接遗传到下一代。目前常用的选择算子是适应度比例法。个体被选择的概率与其适应度值成比例，适应度值高的染色体被选择的可能性较大，其遗传基因在下一代群体中的分布更广。从父代种群中根据选择率Ps选择出Ps×POP个适应性较强的染色体，（1-Ps）×POP个染色体将被剔除，为染色体交叉、变异产生新种群做准备。（2）交叉算子按一定概率随机从亲代群体中选择两个个体，随机地将两个亲代个体的部分结构相互交换，生成两个新的子代个体。即：在种群中任选Pc×POP个染色体（称为双亲染色体），进行交叉运算。交叉算子可以采用单点交叉、两点交叉、多点交叉、均匀交叉等多种方式。例如，从种群中取出的一对染色体为：染色体A1011100‖101B1001001‖110采用单点交叉，随机产生的一点交叉位置是7，交换染色体A,B中第7位右边的部分：染色体A1011100110B1001001101交叉运算后，Pc×POP个母体被其后代所替代，其余母体保持不变。（3）变异算子

以一个很小的随机概率Pm（变异率）改变个体字符串上的某些位，对二进制编码，就是将相应的位从0变1或1变0。变异算子可确保群体中个体的多样性，以使搜索能在尽可能大的空间中进行，避免陷入局部解。2遗传算法应用的特点及改进２．１特点（１）以决策变量的编码作为运算对象传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算。对决策变量的编码处理方式，可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理，特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。（２）遗传算法直接以目标函数值作为搜索信息传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。

无法或很难求导数的目标函数，或导数不存在，以及组合优化问题等，应用遗传算法时就显得比较方便。直接利目标函数值或个体适应度，也可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。（3）遗传算法同时使用多个搜索点的搜索信息

传统的优化算法往往是从解空间中的一个初始点开始最优解的这代搜索过程，搜索效率不高，有时其至使搜索过程陷于局部最优解而停滞不前。遗传算法从由多个个体所组成的一个初始群体开始最优解的搜索过程，而不是从—个单一的个体开始搜索，实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。（4）遗传算法使用概率搜索技术

很多传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点。遗传算法属于一种自适应概率搜索技术，选择、交叉、变异以一种概率的方式来进行的．虽然这种概率特性也会使群体中产生—些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体。（交叉和变异概率等参数会影响算法的搜索效率，如何选择是一个比较重要的问题。）标准遗传算法（SGA）至今仍是国内外GA应用中常用的实施方案，它提供了一个遗传算法的基本框架，同时也解决了一些简单的函数优化问题。但对于复杂的系统优化问题，SGA在使用时出现了一些困难和问题，（１）SGA收敛于最优解的概率小于1。（２）SGA在使用选择算子进行优胜劣汰时，要求个体的适应度均大于零，因此需考虑个体的目标函数向适应度评价函数的转化，当无法确定个体目标函数的正负上限时，这种转换通常很不方便。（３）在应用中表现出的主要问题还有：存在早熟收敛，计算量大，收敛速度慢，解的精度受二进制编码长度控制，尤其是当优化变量的搜索空间较大时这些缺点更为明显。2.2遗传算法的改进(1)混合遗传算法

对于每个新产生的后代在其进入下一代群体之前应用局部优化技术(如爬山法、模拟退火算法等)，使之移动到最近的局部最优点。在混合遗传算法中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。由于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。(2)并行遗传算法P85

遗传算法在解决一些实际问题时，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传算法的并行计算问题受到重视。提出了多种基于各种并行计算机或局域网的并行遗传算法。

(3)改进遗传算法P853遗传算法的应用（１）遗传算法在电网规划中的应用

电网规划的任务是在已知规划水平年负荷要求和电源规划的基础上，根据现有网络结构和待选线路，确定出满足运行要求且最经济的网络规划方案。用遗传算法求解时，首先对问题的解即待选线路进行编码，每个染色体表示一个规划方案，其中每个基因表示一条待选线路，当某基因为1时，表示其对应的线路被选中加入了网络，基因为0时，表示其对应的线路未被选中。适应度函数为电网投资最小。然后对随机选取的初始母体群进行选择、交叉、变异运算。如某电网规划由7条待选路线，根据一些规则，要求选择4条最经济合理的线路。其求解步骤为：（1）确定种群长度即染色体个数POP，选择概率Ps（0<Ps<1），交叉率为Pc（0<Pc<1），变异率Pm（0<Pm<1），遗传代数等参数。（2）对染色体进行编码，其长度为7，必须有4个基因为1，如染色体1010110表示第1，3，5，6条待选线路加入系统。按上述方法，随机生成POP个初始母体群。（3）构造适应度函数f(z)：式中，u0为常数，c(z)为设计方案的费用，ci为第i条线路的建设费用，zi为染色体中第i个基因的值。对初始种群分别计算适应度函数值。（4）进行选择操作。选择POP×Ps个适应度函数值较大的染色体到下一代群体，删除费用较高的染色体。（5）交叉操作。当利用双亲交叉时，很可能使选择的线路大于或小于4，改变了电网的品质，因此采用单亲交叉算子，随机选取POP×Pc个染色体进行交叉运算，对每个染色体随机生成交叉基因位。（6）变异操作。选取POP×Pm个染色体进行变异，电网规划中的变异应是成对变异而不是单位变异，单位变异是将某个基因由0变1或1变0，这意味着增加或减少一条待选线路，不符和电网的基本要求；成对变异是当某个基因由1变0，即去掉一条线路时，寻找一条更经济的线路加入系统，即把费用更低的线路对应的基因位由0变1。（7）对新个体进行适应度评价，判断是否达到预定的遗传代数。若已达到，算法停止，适应度最大的个体为推荐方案；否则，转入第4步继续算法计算。研究结果表明，应用GA解决电网优化规划问题，可克服一般优化算法的局部最优限制及维数灾，能在较短的时间内提供优化方案。（２）遗传算法在水库调度中的应用

对于具有供水、发电、防洪、灌溉等综合利用目标的水库群、水电站群与火电站群之间的联合优化调度问题日益迫切，常规优化调度方法如动态规划法（DP）、逐步优化算法（POA）都有其局限性。如：DP法易于编制程序，但要提高精度，必须加密网格，则计算工作量、占用计算机内存随之加大，若用于求解联合运行问题，常会导致“维数灾”。把遗传算法用于水库（电站）群联合优化调度，可避免这类问题。首先对问题的候选解即染色体编码。编码过去常用二进制数，对水库群联合调度来讲，由于水库数目比较多，用二进制编码时，会导致数字串过长，操作复杂，而且编码时需进行十进制数到二进制数的变换，输出结果时要解码。为了改进和简化计算，对水库群联合调度引入十进制编码。由于水库调度决策变量是水库水位（或库容）的隐性函数，所以把水库水位（或库容）作为优化变量。把各时段每个水库优化变量的可行区间分为m个等份，并按从小到大的次序用整数1，2，…,m，m+1表示。染色体的每一向量(基因)即用该整数n(n=1,2,…,m,m+1)表示，它代表的水库水位在某一时段的值Zt：式中Zt,min,Zt,max分别为时段t允许水库水位的最小值和最大值。如果优化调度计算时段为月，那么每个水库的编码包含12个向量，若m取为20，染色体就可用十进制码表示，如：一个水库的十进制编码染色体（1，3，4，7，12，15，18，21，16，11，6，4）的意义为：水库群联合调度的每个染色体由所有水库的编码组成，如水库个数是三个，调度时段取为月，那么染色体长度为36（即基因个数为36），每个基因表示其对应水库在某个时段的优化变量取值。适应度函数为目标函数的某种数学变换。随机选取初始母体群，运用遗传算子往复循环寻优，直至最优个体的适应度函数值小于某一设定值。实例证明，由于遗传算法采用群体方式组织优化搜索，并行地处理目标函数的多个局部峰值，而不必存储大量状态变量信息，搜索速度快，占用内存少，效率高，并且容易考虑梯级水库间的水利联系，可克服水库群联合优化运行的“维数灾”。（３）遗传算法在确定水电站厂内经济运行准则中的应用水电站厂内经济运行准则是在满足电力系统负荷（日负荷图）要求的前提下，使各机组耗用的总流量最小，它是电力系统经济运行的重要组成部分。目前主要的研究方法有动态规划法、整数和非线性混合整数规划法、优先级表法等，但开停机计划问题在数学上表现为一个大规模的非线性整数规划问题，上述方法或采取了简化措施，或由于方法本身的限制不能得到全局最优解。用遗传算法寻求水电站厂内经济运行准则时，每个染色体表示某一时段各机组的状态，染色体中基因表示其对应机组的运行方式，1表示开机，0表示停机，如系统共有5台机组，染色体10011，表示在该时段第1，4，5台机组开机。适应度函数为：式中，Q0为一常数，Hit为第i台机组在t时段的平均水头，Nit为第i台机组在t时段的平均出力，Qi为第i台机组在水头Hit、出力Nit下的发电流量，uit为t时段第i个基因的值，Pikt为第i台机组的开停机罚因子，Qikt为第i台机组的开停机损耗流量。初始种群由满足约束条件的个体组成，然后对染色体利用适应度函数评价，根据给定的选择概率、交叉概率、变异概率进行选择、交叉、变异（1变0，0变1）操作，直到满足某种收敛准则。(4)遗传算法在水轮机调速器参数选择中的应用水轮机调节是水电站主要的调节内容，目前水轮机调速器主要采用PID控制规律。PID调速器设计的关键是其参数的优化设计，即寻求最佳的比例增益Kp，积分增益Ki，微分增益Kd，使水轮机控制系统的某一性能指标达到最优。用GA优化PID参数，首先对每个参数进行二进制或十进制编码，再把这些编码联接起来构成一个完整的染色体，即个体。参数优化的目标是使调节时间T最小，适应度函数f将极小值问题转化为极大值问题：

式中：Tmax可在统计过程中求得。对初始个体通过适应度函数进行评价，运用遗传算子循环选优，直到找到最优参数或达到预定的进化代数。蚂蚁算法蚂蚁在没有任何可见提示下找出从其窝巢至食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。蚂蚁在寻找食物源时，能在其走过的路径上释放一种分泌物──信息激素，使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息素轨迹（trail）也越来越多，以致信息素强度增大（当然，随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为。增强型学习系统（reinforcementLearningsystem）。1蚂蚁算法原理

用于优化领域的蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征：（1）能察觉小范围区域内状况,并判断出是否有食物或其他同类的信息素轨迹；（2）能释放自己的信息素；（3）所遗留的信息素数量会随时间而逐步减少。假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源．穴-ABD-食和穴-ACD-食，分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。食物ＤＡＣＢ障碍穴１２２１１１在t=0时刻，20只蚂蚁从巢穴出发移动到A。它们以相同概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，10只走右侧。

在t=4时刻，第一组到达食物源的蚂蚁将折回.

在t=5时刻，两组蚂蚁将在D点相遇。此时BD上的信息素数量与CD上的相同，因为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择BD而另5只将选择CD。在t=8时刻，前5个蚂蚁将返回巢穴，而AC、CD和BD上各有5个蚂蚁。在t=9时刻，前5个蚂蚁又回到A并且再次面对往左还是往右的选择。

这时，AB上的轨迹数是20而AC上是15，因此将有较为多数的蚂蚁选择往左，从而增强了该路线的信息素。随着该过程的继续，两条道路上信息素数量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线会有更多的机会被选择。模型变量和常数：m—蚂蚁个数ηij—边弧(i，j)的能见度,1/dijτij—边弧(i，j)的轨迹强度△τij—蚂蚁k于边弧(i，j)上留下的单位长度轨迹信息素数量Pijk—蚂蚁k的转移概率，与τijαηijβ成正比，j是尚未访问结点轨迹强度的更新方程为：

其中各参数的含义为：α—轨迹的相对重要性；β—能见度的相对重要性；ρ—轨迹的持久性，１－ρ理解为迹衰减度(evaporation)；Ｑ——体现蚂蚁所留轨迹数量的一个常数。2基本模型蚂蚁方法的主要步骤如下：步骤1：令nc=0(nc为迭代步数或搜