基于PGSA 的模拟竹林生长算法

孙威威，张 峥

（上海理工大学管理学院，上海 200093）

0 引言

通过模拟植物生长原理计算植物生长素，基于植物向光性的生长规律，李彤等［1］提出模拟植物生长算法（Plant Growth Simulation Algorithm，PGSA）。借鉴匈牙利生物学家Rozenberg［2］的L-系统分支规则迭代重写，构建模拟植物在搜索空间中找到最优解的理论体系。郭改文等［3］提出的森林竞争算法是基于自然树枝条的生长、凋落矛盾统一原理和森林生态系统中竞争排斥原理提出的算法，竹林算法则是基于模拟植物生长算法的新算法，主要区别在于允许多棵树木生长，不删除单棵树木个体，不需要计算营养因子、遮挡因子等，计算步骤较为简化。与吴俊秋等［4］提出的模拟植物生长算法改进方案不同，模拟竹林生长算法不在单棵树计算过程中进行初始化及改变步长，而是尽可能快地生长单棵树，并从多棵树木中找到全局最优解。

PGSA 算法在不同领域如电力系统、企业管理、生产调度、物流优化等多种场景中得到应用，但存在一定的改进空间，如较大的生长空间导致优化效率降低，算法缺乏有效的终止判断设计，初始值和步长设置不当容易陷入局部最优解等。因此很多学者从不同角度对算法进行改进，但改进基本上都侧重于对于特定问题的数学模型进行改造，或者对单棵树木的生长规则进行调整，没有从多棵树木角度以及简化计算步骤角度进行改进［5-23］。

本文受模拟植物生长算法和随机森林思想启发，提出模拟竹林生长算法（Bamboo Grove Simulation Algorithm，BGSA），取消了适应度（生长素）计算和生长节点的随机选择，而是基于根节点与生长步长（每次生长的树干长度）的随机化通过快速迭代寻找全局最优解。

1 模拟竹林生长算法

竹子生长特征是由一根主干组成，虽然会生长小的茎叶，但是整体向上生长依然是从主干的竹节上依次生长，具有快速生长、枝干挺拔的特征，见图1。借鉴竹子生长特征，且考虑到模拟植物生长算法寻找全局最优解受到生长步长和初始树根的影响，参考随机森林算法［24］，通过选择不同的生长位置，按照不同的步长快速生长出不同的竹子，进而在竹林中找到最高点作为全局最优点。

Fig.1 Bamboo nodes图1 竹子节点

首先取消生长素计算，将每次最高节点作为新的生长基点，减少计算过程和时间消耗；其次减少茎叶生长，集中在主干上快速生长。将竹林多重迭代优化并选取最大值，每棵竹子的初始生长点、步长均不同，从而更大程度上避免陷入局部最优解，更快寻找到全局最优解。

模拟竹林生长算法流程见图2，步骤如下：①初始化，确定初始解，随机选择根节点和迭代步长；②生长新的节点，计算并保存局部最优解；③选择局部最优解作为新的生长基点；④重新在不同位置生长新的竹子，迭代以上步骤；⑤迭代终止。

根据问题性质和规模，设置终止条件如下：在步骤④处，如果满足单棵竹子的迭代终止条件，如达到单棵竹子生长次数，或最优节点重复次数达到局部最优节点最大允许出现的次数，则单棵竹子停止生长；在步骤⑤处，如果竹林中的竹子总数达到设定上线则整片竹林停止生长，并将竹林中所有竹子的最高点作为全局最优解。

Fig.2 Flow of simulating bamboo growth algorithm图2 模拟竹林生长算法流程

2 实验

首先，模拟植物生长算法要计算树干和树枝上所有节点的适应度（生长素），在生长出新的树枝后计算公式会变得更加复杂，增加了计算工作量；其次，基于适应度随机选择节点虽然降低了陷入局部最优解概率，但也会造成计算工作的重复。而模拟竹林生长算法首先取消了适应度计算，其借鉴竹子每次从最高节点生长新的节点，减少了计算步骤。由于随机化步长和根节点的选择，以较小的成本生长单棵竹子，并从多棵竹子的最优解集合中找到全局最优解，减少了计算步骤。

以整数域问题求解为例，选取常见的Ackley、Beale、Hölder Table、Sphere、Rastrigin 和Bukin 测试函数，分别使用模拟植物生长算法和模拟竹林生长算法计算，使用Python 3.7 编程，在Windows 10 家庭版操作系统、Intel i5-8300H 2.30 GHz、内存8GB 环境下测试。

初始化根节点设置为（-10，10）之间的随机整数值，步长为（5，12）之间的随机整数值，每棵树最大迭代次数200次，允许重复出现局部最优解次数10 次，竹林最多生长5棵竹子。其中PGSA 迭代5 次，全局最优解选取5 次迭代中的最小值，计算时间和收敛次数取平均值进行对比。与模拟植物生长算法相比，平均计算时间减少了79%，平均收敛次数降低了48%，全局最优解准确率提升了50%，如表1 所示。

Table 1 Comparison of the performance of PGSA and BGSA表1 PGSA 和BGSA 性能对比

3 分析

根据以上数据分析可知，BGSA 在平均收敛次数和计算时间上的性能优于PGSA 算法。由于PGSA 每次生长节点选择存在随机性，并不是在局部最优点选择，所以存在一定的计算资源浪费，同时也因为步长选择和初始节点选择原因，并不一定能够每次找到全部最优解，如果不通过多次迭代比较则容易陷入局部最优。

选取几个具有代表性的测试函数作为对比，可以看出PGSA 与BGSA 算法在收敛迭代速度上存在差异，图3-图6（彩图扫OSID 码可见）由左边收敛下降曲线和测试函数三维曲线组成，其中x 轴为迭代次数，y 轴为局部最优函数值。由于BGSA 最大迭代次数设置较小，BGSA 最大迭代测试的x 轴比PGSA 短。

Fig.3 PGSA Ackley test function图3 PGSA Ackley 测试函数

Fig.4 Bgsa Ackley test function图4 BGSA Ackley 测试函数

Fig.5 PGSA Rastrigin test function图5 PGSA Rastrigin 测试函数

Fig.6 Bgsa Rastrigin test function图6 BGSA Rastrigin 测试函数

以图7 迭代收敛曲线为例，可以看出BGSA 和PGSA在收敛速度上存在差异，BGSA 收敛速度优于PGSA 算法。为便于对比展示两个算法，将BGSA 迭代次数作延长处理。

Fig.7 Convergence curves of Ackley iteration for BGSA and PGSA图7 BGSA 与PGSA Ackley 迭代收敛曲线

4 结论

针对优化问题中PGSA 算法可能存在多个局部最优解，导致算法无法自动终止、计算时间长等问题，PGSA 通过随机选择生长点在更小范围内避免陷入局部最优，但存在收敛迭代次数较多、计算时间较长的缺陷。本文受竹子生长特性启发，基于竹子生长特征，提出BGSA 模拟竹林生长算法，通过常见的测试函数对比验证得出如下结论：

（1）去除掉生长素计算和随机选择生长点之后，减少了计算时间消耗，加快了搜索能力，减少陷入局部最优解的风险。

（2）通过随机化根节点和多棵竹子计算比较发现，BGSA 在计算速度、收敛速度和全局最优解寻找上存在一定的比较优势，可以更快收敛到全局最优解，基于多棵竹子的最优解综合计算避免了固定步长和固定初始根节点对寻找全局最优点的不利影响。

5 结语

本文通过理论分析和测试验证，基于不同植物的生长特性比较，发现竹子的生长寻优特征更加明显。节点快速生长特性去除了随机选择节点，每次基于最高节点继续生长，提高了优化算法效率。通过简化计算步骤、更改迭代步骤，以及根据随机根节点在不同地点生长出不同竹子，采取每根竹子的步长为随机长度的优化方法，寻找到全局最优解。通过测试函数发现，BGSA 相对于PGSA 存在一定的改进优势。后续将在此基础上，通过研究更多维的空间测试函数解决计算优化问题，以及不同场景下的具体算法应用，不断完善该算法。