Leapfrogging: A Multiplayer Optimization Direct Search Algorithm

Introduction

Leapfrogging as an optimization algorithm was first published in 2012, and has had many supporting publications since.  Key references to the technique are:

  • Rhinehart, R. R., M. Su, and U. Manimegalai-Sridhar, “Leapfrogging and Synoptic Leapfrogging: a new optimization approach”, Computers & Chemical Engineering, Vol. 40, 11 May 2012, pp. 67-81.
  • Manimegalai-Sridhar, U., A. Govindarajan, and R. R. Rhinehart, “Improved Initialization of Players in Leapfrogging Optimization”, Computers & Chemical Engineering, Vol. 60, 2014, 426-429.
  • Rhinehart, R. R., “Convergence Criterion in Optimization of Stochastic Processes”, Computers & Chemical Engineering, Vol. 68, 4 Sept 2014, pp 1-6.

It is a direct search algorithm meaning that it uses function values only, not derivative (gradient or Hessian) information. This makes it robust to many surface features that confound or misdirect derivative-based searches (saddle, inflection, ridges, discontinuities, stochastic, etc.).

Real-data applications have included steady-state applications (neural network modeling to predict student performance, device calibration), dynamic process modeling (viscoelastic responses, and pilot-scale heat exchange, distillation, and absorber), and nonlinear model-predictive control (distillation and heat exchange).  There are hundreds of additional simulation exploration applications.

The file r3eda 2-D Optimization Examples 2017-04-23 provides demonstration examples and a chance for the visitor to assess several measures of optimization aspects for several optimizers.  The file r3eda site 2-D Examples User Guide 2016-06-11 provides directions.  And the file r3eda site 2-D Challenge Problems describes the VBA functions coded in the .xlsm file.

Mark Redd offers a Python version of the LF algorithm for public use.  Visit: https://sourceforge.net/projects/leapfrog-optimizer/

For a YouTube Webinar about LF visit: https://www.youtube.com/watch?v=86W71ocI8Ww

 

Method Overview

Start with a randomly placed team of players (swarm of particles, individuals, trial solutions) in feasible spots in the DV space range thought to be of interest.

Evaluate the objective function (OF) value for each, and determine the one with best and the worst OF values.

Move the worst player to the other side of the best player in DV space.  The worst player jumps over the best player, and lands in a random spot in the projected “area” on the other side.

The file Leapfrogging Optimization Explanation illustrates the method.

If there are two DVs, x and y, the leap-to location is calculated as:

xw,new = xb - rx (xw,old - xb)

yw,new = yb - ry (yw,old - yb)

Here,  the rx and ry are independent random numbers, with a uniform distribution and range of (0,1].  These random perturbations are independent for x and y, and for each leap-over.

This player jump-over is similar to children playing leapfrog, hence the algorithm name.

The leap-over may place the player at an OF value that is still the worst, or into an infeasible region (violates constraints, leads to an execution error in the OF calculation, etc.).  If so it remains the worst, and is the one selected for the next leap-over.

 

Analysis

On average each leap-over moves the player with the worst OF ½ of the distance closer to the player with the best OF. If the best player remains the best, all players converge to it. However, if the leaping player becomes the best, the solution moves toward the optimum.  On the side of a hill, the worst player, from the back of the team, leaps a long distance over the lead player, and this expands the team, accelerating motion and widening exploration as it leapfrogs downhill.

Equation set (1) can be modified in any of a number of ways: to move the player (particle, individual) to the other side of the centroid of all players, to blend moving to the other side of the centroid and the best, or to move randomly either between or beyond the best or the centroid, or to jump into a window that is either larger or smaller than the reflected window.  If the leap-to window is smaller than the leap-from window, the team converges faster, but does not explore as much.  Alternately, if the leap-to window is larger than the leap-from window it explores the entire space more, has a higher probability of finding the global, but converges slower.  The team will converge if the leap-to window size is less than e=2.718… The leap-to window size can be adjusted as belief increases that the proximity of the global has been found.  Although there are some benefits to such enhancements, I find the basic version initially presented to be best – simple and equivalently effective on a variety of test applications.

The equation set can be generalized to any number of dimensions.

If there are M players (trial solutions), there are M initial OF evaluations.  But subsequently, each leap-over only costs 1 additional OF evaluation.  Nominally, I recommend that the number of players is 10 times the number of DVs, M=10N.  This is from experience, and it seems to be partly dependent on the leap-over amplification factor.  I will be presenting analysis of rates of convergence and probability of finding the global in my in-process optimization book.  Meanwhile, use 1 for the leap-over window size and M=10N for the number of players.

If there are N dimensions, each leap-over changes all N DV values for the jumping player.

I term an iteration as N leap-overs, one leap-over per dimension, representing N OF evaluations, which is roughly equivalent to the work per iteration of an incremental steepest descent method, and a cyclic heuristic search, slightly fewer than Hook-Jeeves, and much fewer than a Newton-type search.  Not all players will necessarily move in an iteration – the worst could jump to a new spot and remain the worst.

Eliminating the worst is the driving philosophy of the Leapfrogging, and Nelder-Mead Simplex searches.  It is also the logic in searches called “Tabu”.  It is also the philosophy in Pareto optimal selection, and Genetic Algorithms and evolutionary algorithms remove the worst.  Like them, LF moves the worst.  By contrast, most optimizers seek to improve the best.

 

Convergence Criteria

Any of many criteria could be used to determine convergence of the LF algorithm.  Perhaps the simplest is the range on the DVs.  For each DV calculate the range as the difference between highest and lowest.  Test for each DV.  Test after an iteration, after N leap-overs.   When the range on each is small enough, then the team has converged.  Report the best of the M players as the optimum.  While simple to understand, this requires the user to identify a range for each DV (the implication of the DV on the OF might not be obvious), and the computer to search over all DVs for their ranges (computational time).

Another simple option is to claim convergence when the range of the OF values is small.  It may be easier for a user to relate to the OF value, and to determine what incremental change would be inconsequential, than for a user to do this for the DV values.  Further, since the LF algorithm requires identification of the best and worst, there is no additional computer burden.   I recommend setting the OF threshold range for convergence to be an order of magnitude smaller than what the user decides is an inconsequential deviation from OF perfection, from a not quite optimal OF that is still fully acceptable in use.  Test after an iteration, after N leap-overs.  Once converged, report the DV and OF values of the best of the M players.  This is my preference.

There are many variations on such criteria.  One could use rms (root-mean-square) deviations, for instance on either OF or DV values.  Or, you could use the sensitivity of the OF to the DV and project the combined impact of the all of the DV ranges on the OF.

 

Stochastic Surfaces

A stochastic (noisy) application is one in which repeated samplings of the OF, at exactly the same DV trial solution, returns a distribution of OF values.   Examples include experimental sampling or Monte Carlo Simulations.   If the surface is stochastic (noisy) then the best player might be the best because of the vagaries of sampling the surface (the OF value).  Another sample at exactly the same location might reveal that the value at the same location is not so good.  So, to prevent an optimizer from finding the phantom best, a fortuitous artifact of all possible stochastic outcomes, reevaluate the OF of the best.  Use the worse of the replicated outcomes to represent the OF-value of that player.  Do this reevaluation prior to each leap-over.  If a worse outcome is likely, it will eventually be expressed, and another player will become the best.

In this case, a Leap-over is: move the worst and reevaluate the best (one replicate, but you could do more).  For M players, there are M initial OF evaluations, then 2 at each move, or 2N at each iteration.  The extra OF evaluation constantly checks “Are you still the best?”, and permits searching for the “best of the worst” not the ultimate, ever there was, a “lucky best”.

In this case, in the end game of surrounding the optimum, the team does not converge on one spot.  Instead, players leap around in the vicinity as the stochastic nature keeps changing the best.  Accordingly, an alternate criterion for convergence is needed.   What I recommend is to observe the OF-value of the worst player (who will change with each leap-over).  As the team gathers in the vicinity of the optimum, the worst player OF-value will fall toward those of the local area, but will not asymptotically approach a single value, it will be subject to the vagaries of the stochastic surface and its OF-value will relax from the initialization worst to a noisy steady state representing the end game vicinity.  The player labeled the worst, will likely change at each iteration.  This is not observing the original worst player.  Use steady-state identification on the worst OF-value at each iteration, and claim convergence when the worst (at each iteration) comes to steady-state.