优化随机策略的蛙跳算法

"A Least Random Shuffled Frog-Leaping Algorithm 是一种优化算法，旨在解决经典Shuffled Frog-Leaping算法中的时间消耗问题。该经典算法在进化青蛙群体（每个群体大小为n）时，通常通过不等概率选取每个群体中的q个（q≤n）青蛙，然后选择其中适应度最小的青蛙进行进化。然而，这个过程需要多次生成随机数，导致显著的时间消耗。本文提出的新方法首先计算每个青蛙被选为适应度最低青蛙的概率，然后利用轮盘赌算法选择最终的青蛙。这种方法在第一步不生成随机数，第二步只生成一个随机数，从而提高了效率。实验结果显示，该方法在大多数情况下比经典方法在时间消耗上表现更好，速度提升约为3.2倍（当q=0.5n时，使用线性同余发生器）。关键词包括：Shuffled Frog-Leaping，最少随机数生成，不等概率采样，多项式分布。" 本文介绍了一种改进的Shuffled Frog-Leaping算法，即Least Random Shuffled Frog-Leaping Algorithm，其主要目标是提高算法的运行效率。Shuffled Frog-Leaping算法是一种全局优化方法，灵感来源于自然界中青蛙跳跃寻找食物的过程。在经典版本中，算法基于个体适应度不等概率地从每个群体中选择一定数量的青蛙，并选择适应度最低的青蛙进行进化操作，这一过程需要大量生成随机数，从而增加了计算时间。 为了解决这个问题，作者提出了一种新的策略，他们先计算每个青蛙被选为适应度最低者的机会，然后利用轮盘赌算法来确定哪个青蛙将被选中进行进化。这种方法减少了对随机数生成的依赖，第一步完全避免了生成随机数，仅在第二步需要生成一个随机数，从而大大降低了时间消耗。实验数据显示，新算法在大多数情况下能够显著减少计算时间，尤其是在q等于群体规模的一半时，性能提升达到3.2倍。 关键词中的“Multinomial distribution”（多项式分布）可能是指在计算每个青蛙被选中的概率时用到的概率分布模型。这种分布可以用来模拟多个类别中每个类别被抽样的次数，与不等概率采样相符合，因为不同适应度的青蛙在被选中的概率上可能存在差异。 Least Random Shuffled Frog-Leaping Algorithm是对经典Shuffled Frog-Leaping算法的优化，通过改进选择和进化策略，降低了算法的时间复杂度，提升了搜索效率，尤其适用于需要高效优化的问题场景。这一研究对于理解和改进其他基于随机性的全局优化算法也具有参考价值。