模拟植物生长算法与应用

前言

第一章 绪论

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

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

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

一种新算法的提出,必须具有解决现实问题的能力,否则无论理论体系如何完整,也不会被广泛应用和认可,也就缺乏进一步发展的可能性.下文以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的研究重点是建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,就是实现人工植物在优化问题解空间中从初始状态到完整形式的终态(没有新的树枝生长)的过程.

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

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

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

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