Introduction – updated 2022-05-14
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 (constraints, saddle, inflection, ridges, discontinuities, numerical striations, flat spots, integers, classifications, stochastic, etc.).
Real-data applications have included steady-state applications (neural network modeling to predict student performance, and device calibration), dynamic process modeling (viscoelastic responses, and pilot-scale heat exchange, distillation, and absorption), 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, so the visitor can assess several measures of optimization aspects for several optimization algorithms. 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 has coded the Leapfrogging optimizer for use with Python and C/C++. The Python package is available on PyPi and can be viewed here: https://pypi.org/project/lpfgopt/ The package with corresponding documentation and source code, and a dynamic-link library written in C have been officially released on GitHub under the MIT license. The release can be viewed here: https://github.com/flythereddflagg/lpfgopt/releases
For a YouTube Webinar about LF visit: https://www.youtube.com/watch?v=86W71ocI8Ww
Method Overview
Start with a randomly placed team of players (alternately termed swarm of particles, individuals, trial solutions) in feasible spots in the range of decision variable (DV) space thought to be of interest.
Evaluate the objective function (OF) value for each player, and determine the one with best and the one with 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 DV “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. It is also the police/military term for sequential move of agents toward a target.
The leap-over may place the player at an OF value that is still the worst, or into an infeasible region (where it cannot generate an OF value because it violates constraints, leads to an execution error in the OF calculation, etc.). If so, it remains the worst player, 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. Chapter 35 in my book Engineering Optimization (2018, Wiley, ISBN-13:978-1118936337, ISBN-10:1118936337) provides guides to the probability of number of leap-overs to convergence, finding the global optimum, and other algorithm attributes.
The equation set above that determines the leap-to position 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 ratio of the leap-into-to-leap-from window dimension is less than e=2.718…, otherwise the team will diverge.) 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. Simplistically, I recommend that the number of players is 10 times the number of DVs, M=10N, and that the leap-into window size is the same as the leap-from. This is from experience, and a user-convenience view point. I present analysis of rates of convergence and probability of finding the global in my in-process optimization book, that reveals an optimal number of players and leap-to amplification factor to maximize the probability of finding the global and minimize the number of function evaluations to converge. An optimal rule for LF choices is to use 1 for the leap-over window size ratio and M=max(20, 5N) for the number of players.
You might want to start LF optimization with fewer than the recommended number of players. That is OK. Simply retain the old leap from player positions while adding the new leap-to positions until you have the desired number of players. Or, add new players randomly within a comfortable range to reach the desired number.
Note that 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 (per number of DVs), representing N OF evaluations per iteration, which is roughly equivalent to the work per iteration of an incremental steepest descent method, and a cyclic heuristic search. It is slightly fewer OF evaluations per iteration than Hooke-Jeeves, and much fewer than a Newton-type or other second-order type of search. Not all players will move in an iteration. There are two reasons: 1) M>N; and 2) the worst could jump to a new spot, remain the worst, and jump again.
Eliminating the worst is the driving philosophy of the Leapfrogging (LF), 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. Like them, LF moves the worst. By contrast, most optimization algorithms 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 of the DV values. Test for each DV. Test after an iteration, after N leap-overs. When the range on each DV 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 convergence range for each DV (the implication of the DV effect on the OF might not be obvious until after the DV* has been found), and for 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 to do this for each of the DV values. Further, since the LF algorithm requires identification of the best and worst OF values, 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 each iteration, after N leap-overs. Once converged, report the DV and OF values of the best of the M players. This is my preference. (I live life making choices like this, when choosing where and when to buy gasoline, what electronic products to buy, what to eat, etc. It seems to work.)
There are many variations on such convergence 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, then another player will become the best.
In this case, a Leap-over is: 1) Reevaluate the supposed best player (one replicate, but you could do more). Its new OF will be higher or lower. If it remains the best in the cluster, use it as the best. If it does not remain the best find the new best from the other players. 2) Leap the worst over the best. 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 “phantom 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, a deterministic classical convergence criterion cannot be used, 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 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 Steady-State & Transient Detection.