植物可看作由大量枝、节组成的系统,模拟植物的生长演绎方式是A.Lindenmayer在20世纪 60年代末把乔姆斯基的生成转换语法引入生物学,以简单的重写规则和分枝规则为基础,建立了关于植物的描述、分析和发育模拟的形式语法,称为L-系统.对植物生长作形式化描述,可以根据以下几点进行:1)破土而出的茎杆在一些叫做节 的部位长出新枝;2)大多数新枝上又长出更新的枝,这种分枝行为反复进行;3)不同的枝彼此有相似性,整个植物有自相似结构.用L-系统描述生长的基本概念如图1所示.

20世纪80年代,P.Prusinkiewicz等人把L-系统与计算机图形学、分形学结合起来,完善了植物生长的分枝模型.在所规定的生长规则的反复重写下,可作出如图2所示的分形生长树图(取自普鲁森科维奇专著).

PGSA以L-系统作为人工植物的生长演绎方式的源模式,生长点即植物生长细胞,是模拟植物系统每一次生长的位置点.植物生长过程是在生长点按2n(厅为变量的维数)个方向生长并产生新枝,分枝长度在整数规划情况下设定为1(非整数规划情况下可根据精度要求选取).

按照L-系统完成的人工植物结构,仅解决了模拟植物生长的演绎问题,其关键问题还没有解决,即在众多生长点中,每一次到底确定其中哪一个进行新的生长,怎么保证树枝向最优解方向生长,其核心问题就是植物向光性特点的算法实现问题.

一种新算法的提出,必须具有解决现实问题的能力,否则无论理论体系如何完整,也不会被广泛应用和认可,也就缺乏进一步发展的可能性.下文以PGSA解决斯坦纳最小树问题切入点,同时 对目前PGSA在不同领域的应用情况做一个简要 的总结.

模拟植物生长算法PGSA在斯坦纳最小树问题中的应用

斯坦纳最小树(SMT)问题最早可追溯到法国数学家费马(P.de Fermat)1634年所提出的费马问题“.目前该问题是组合优化中著名的NP难题,是指连接给定点(Girven point,或称所与点)的最小树长问题.若x为平面上给定n个点的点集,设G是由某些边构成的图形,边的端点叫做G的顶点.若G的顶点集包含x中所有点,则称G为x的生成树,当树的总长度最短时,则称之为最小生成树(MST),其长度记作(X).如果除了n中的点外,还可以用n点以外的点(斯坦纳点)作为树的结点,则这样的树即称为斯坦纳最小树(SMT),其长度记作(X).

模拟植物生长算法(PGSA)在解决SMT问题上以斯坦纳比(X)/(X)为标准与文献[8]中蚂蚁算法(AA)、模拟退火算法(SA)进行了精度比较,实验采用国际上公布的测试数据库STEINLIB中的问题实例,算法用Matlab编程实现,在Windows XP平台上运行通过,试验中计算机为Celeron(R) CPU 3.06GHz,1.00GB内存. PGSA在STEINLIB中的每个测试实例分别进行15次计算,其中最好结果与最差结果之间误差值不超过0.017%,表现出了算法突出的计算稳定性。

模拟植物生长算法算法在各学科领域中的应用

除了解决组合优化问题,PGSA目前在整数规划和工程技术领域已逐步被许多国内外学者应用.

K.Guney、A.Durmus和S.Basbug在文献[9]中将模拟植物生长算法(PGSA)用于电磁学中的干扰幅度控制领域,分别于MTACO、BA、BFA三种智能算法比较,PGSA均得到了更优的结果,且收敛性和计算速度明显优于其他算法.他们的应用结论为:“As an optimization algorithm, the PGSA will most likely be an increasingly attractive alternative, in the electromagnetics and antennas community ,to other optimization algorithms.’’

R.Srinivasa Rao、S.V.L.Narasimham在文献[10]中应用PGSA来解决雷达分配系统中电容优化配置的问题.他们的应用结论为:“The advantages with the Plant Growth Simulation algorithm(PGSA)is that it treats the objective function and constraints separately ,which averts the trouble to determine the barrier factors and makes the increase/decrease of constraints convenient ,and that it does not need any external parameters such as crossover rate,mutation rate, etc.It adopts a guiding search direction that changes dynamically as the change of the objective function.’’

在国内,上海交通大学、大连理工大学、哈尔滨工业大学、郑州大学、华北电力大学等高校的学者也分别在不同领域对PGSA进行了应用研究.

文献 对模拟植物生长算法进行了一些改进,采用植物顶点变速度生长特点来减少搜索时间,利用植物生长期前期纵向型生长特性来减少搜索空间,因此能够在更少的时间内得到更优解.通过对不同类型的非线性整数规划算例求解, 表明该算法是很有效的.

文献 中运用PGSA与其他优化算法进行了比较研究,结果表明PGSA给出的最优网络是现有文献当中最好的方案,明显优于遗传算法和粒子群算法.

文献 的计算结果表明PGSA优于遗传算法和协同进化算法.

文献 中的分析计算表明PGSA与遗传算法、Tabu搜索算法相比，具有更高的精度和更加快速的全局寻优能力。

文献 中建立了动态无功优化的模拟植物生长算法,算法对负荷按实际形状而不是按设备动作次数限制进行分段,更加准确地描述了负荷的实际状况,所得到的无功补偿优化投切方案能更好的满足电网实际运行的需要。

文献 中对PGSA做过一个总结:“理论分析及算例结果表明,与遗传算法为代表的现代启发式算法相比,模拟植物生长算法具有以下优点:1模拟植物生长算法将目标函数和约束条件分开处理,且无需编码和解码,避免了构造新的计算用目标函数,也不存在惩罚系数、交叉率、变异率选取等问题，解的稳定性好；2.模拟植物算法具有一个由形态素浓度决定的方向性和随机性平衡比较理想的搜索机制,能以较快的速度寻找到全局最优解.”

文献 中,通过对IEEE 30节点系统采用 模拟植物生长算法、标准遗传算法和粒子群优化 算法比较,模拟植物生长算法得到的优化方案网损最小,同时有更强的收敛稳定性.

文献 将PGSA用于设施选址问题,比较研究结果表明PGSA优于遗传算法.

PGSA的研究领域还包括:我国著名水处理专家,哈尔滨工业大学李圭白院士等将PGSA推广应用于双级决策的排污收费模型,改进了传统 的最优Pigovian定价法的诸多问题;西南石油大学的张伟等人将PGSA应用于三维地震勘探的采集、处理等地震勘探优化问题;此外,罗伟强、焦彦军、杨丽徙、王锴、赵颖等人应用模拟植物生长算法在各自的领域进行了大量的应用研究。

模拟植物生长算法(PGSA)是在2005年提出的一种以植物向光性机理为启发式准则的智能优化算法.该算法是将植物系统演绎模式(L一系统)和植物系统概率生长模式(向光性)向优化领域进行映射和变异的典型应用.PGSA提出3年来,在整数规划、组合优化以及工程技术领域逐渐显示出其突出的稳定性、精确性和全局搜索能力,因而具有良好的应用和推广前景.

所谓PGSA,就是将优化问题的解空间当作植物的生长环境,将最优解当作光源,模拟真实植 物的向光性机理(形态素浓度理论),建立枝叶在不同光线强度环境下的快速生长的生长演绎方式 (L-系统).PGSA的研究重点是建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,就是实现人工植物在优化问题解空间中从初始状态到完整形式的终态(没有新的树枝生长)的过程.

植物向光性涉及生物学理论中的形态发生模型,该模型是用复杂动力系统为生物生长建模的著名例子,模式的形成被理解为复杂过程,其中一个细胞发生分化,产生出新的明确定义的空间结构.形态发生的最初的动力学模型是拉什夫斯基、 图林等人提出来的.他们关于植物生长形态发生 (“叶序”)模型如图3所示,葡萄茎梗发出一个枝芽的某一时刻,它出现在对于3个枝芽对称旋转 的方向(PGSA将旋转方向确定为90度).在生长中的茎梗的顶部,生长出来一个芽,包含着未分化的细胞.叶序问题涉及作为叶芽细胞、分枝细胞和其他导致叶芽和分枝的分化细胞的生长模式的形成.一个细胞被看作是一个流体袋,其中有均匀的化学组分,其中的一种化学组分是生长激素,叫做形态素.这种形态素的浓度名是此模型的观察参量,随着参量在0和1之间变动,模型的状态空间是一条线段(图4).这种形态素的浓度决定细的生长函数是否开始起作用,即细胞分裂,枝芽开始出现.

新的生长点(细胞)产生后,形态素浓度将根据新系统所在环境的改变,重新进行分配.在多细胞系统中,如果把任意一个细胞形态素浓度记为 Pi(i=1,2,⋯,n),则多细胞封闭系统形态素状态空间用见图5,且浓度和是恒定的(设定为1). 生物学实验已经证明,决定植物细胞分裂和枝芽生长的生长素信息(形态素浓度)并非是预先一个个赋予给细胞的,而是细胞系统从其环境中接 受到了它的位置信息,依据这种信息,植物表现出明显的向光性特点.模拟这一过程,设有n个初始生长点Si=(S1,S2,⋯,Sn),每一个生长点的形态素浓度为Pi=(P1,P2,⋯,Pn),当目标函数实现最小化时,计算各生长点形态素浓度值为式(1)

其中以f(·)为目标函数值.式(1)中,各生长点形态素浓度是由各点的相对位置以及该位置的环境信息(目标函数值)所确定,这与真实植物细胞的形态素浓度生成机理相一致.因此,n个生长点均对应n个形态素浓度值,每次产生新枝,该浓度值都将发生变化.

由式(1)可知式2

在确定了形态素浓度之后,就可以建立植物的向光性机制,即形态素浓度较高的生长点(细胞),将具有较大的优先生长机会,其算法可描述为:设共有n个生长点(S1,S2,⋯,Sn),按照公式 (1)分别计算其形态素浓度值为(P1,P2,⋯,Pn),式(2)已经得到Pl P2 ⋯ Pn=1,因此其概率空间如图5所示.

计算机系统不断产生随机数,这些随机数就象不断向区间[0,1]上投掷的小球,小球落在P1, P2,⋯,Pn的某一个概率空间内,所对应的生长点就得到优先生长的权利.这个过程反复进行,模拟植物的树枝按照L-系统生长模型在解空间内快速蔓延,直至没有新枝的产生为止,这就是 PGSA,其迭代过程详见文献 .

《模拟植物生长算法与应用》是以丁雪枫的博士论文为基础，由丁雪枫和尤建新合作为模拟植物生长算法撰写的专著。在《模拟植物生长算法与应用》中，作者从模拟植物生长算法的思想来源、基本原理出发，介绍了模拟植物生长算法及其在一些典型问题当中的应用，涉及的应用重点还包括了模拟植物生长算法应用于整数规划问题、无线传感器网络最小连通集合划分问题、虚拟企业盟友选择题、物流中心选址问题、作业车间调度问题的实现技术及应用等内容。

《模拟植物生长算法与应用》以丁雪枫为主笔，尤建新辅助。

前言

第一章 绪论

1.1优化问题介绍

1.2植物生长的生物学特征

1.3模拟植物生长算法的思想起源

1.4研究模拟植物生长算法的意义

1.5模拟植物生长算法的研究现状

1.6本章小结

第二章 模拟植物生长算法模型

2.1模拟植物生长算法基本原理

2.2模拟植物生长算法动力学特征

2.3模拟植物生长算法的流程及实现

2.4模拟植物生长算法的收敛性分析

2.5本章小结

第三章 模拟植物生长算法与其他优化算法的比较

3.1遗传算法

3.2蚁群算法

3.3模拟退火算法

3.4微粒子群算法

3.5各算法的对比分析

3.6本章小结

第四章 模拟植物生长算法的典型应用

4.1整数规划问题

4.2WSN最小连通集划分问题

4.3虚拟企业盟友选择问题

4.4中心选址问题

4.5作业车间调度问题

4.6本章小结

第五章 模拟植物生长算法改进策略及其应用

5.1基本模拟植物生长算法的缺陷

5.2模拟植物生长算法的几种先进策略

5.3模拟植物生长算法的改进应用

5.4本章小结

第六章 展望

6.1算法总结

6.2未来研究工作

参考文献2100433B

模拟法的基础是蒙特卡洛模拟，因此该方法是目前电力系统中处理含不确定因素概率潮流问题中计算结果最为精确的一类方法，但与其高精度计算能力相对应的是低时效性。在蒙特卡洛模拟基础上改进的各种算法都是以减少抽样计算量为目的：重要抽样法计算速度快，期望值结果准确，但其计算结果单一，无法全而描述系统运行特征；拉丁超立方采样法的采样规模相对于蒙特卡洛模拟法大幅降低，是目前精度和时效较高的概率潮流算法，但该方法在处理变量之间的相关性时具备较高的复杂度，且相关性结果往往与实际情况存在一定的偏差；QMCS理论上计算速度最快，但低差异序列的维数问题是该方法应用瓶颈。

随着电子计算机技术的发展与电力系统计算平台的壮大，模拟法必然在概率潮流计算中扮演越来越重要的角色，本文认为其发展趋势可以包含以下几个方向。

1）采用多种采样方式相结合的混合采样法，例如QMCS对维度较低的问题具备优越性，当问题维度较高时，采用QMC'S与拉丁超立方采样法的混合采样法计算，从而发挥不同采样方法的优势。

2）采样过程中针对不同的研究重点分段处理，期望值附近的概率曲线在处理过程中保持良好的计算准确度，但分布曲线的尾部计算精度往往很差，在对精度要求很高时，可以对分布曲线分段，对尾部采样进行特殊处理。

3）并行计算的应用。目前计算机的多核并行处理计算能力得到了大幅提升，同时基于图像处理单元的并行计算得到了发展，该硬件平台对重复性抽样计算的提速效果显著。