一种新算法的提出,必须具有解决现实问题的能力,否则无论理论体系如何完整,也不会被广泛应用和认可,也就缺乏进一步发展的可能性.下文以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应用于三维地震勘探的采集、处理等地震勘探优化问题;此外,罗伟强、焦彦军、杨丽徙、王锴、赵颖等人应用模拟植物生长算法在各自的领域进行了大量的应用研究。
