This page will look better in a graphical browser that supports web standards, but is accessible to any browser or internet device.

Served by Samwise.

JSim Optimization Algorithms

This page is for the current JSim version 2.0 and higher. Click here for the earlier JSim 1.6 version.

Introduction

There is no perfect optimization algorithm that is best for all problems. Optimization algorithms vary in their approach, efficiency, robustness and applicability to particular problem domains. This document describes the optimization algorithms currently supported by JSim in some detail so users can make intelligent use of them. JSim's currently available optimizers are listed below. Other algorithms are in development.

Prerequisites:

Contents:

Overview

Some terminology is useful when discussing the merits of optimization algorithms:

All of JSim's currently available optimization algorithms share the following control parameters:

Algorithm-specific control parameters are listed with each algorithm description.

Simplex

JSim's simplex is a bounded, non-linear steepest-descent algorithm. This algorithm does not currently support parallel processing. (description needs work)

Algorithm-specific control parameters:

Reference: Dantzig GB, Orden A, Wolfe P: The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific J Math. 1955;5(2): 183–195.

GGopt

GGopt is an unbounded non-linear algorithm originally written by Glad and Goldstein. This algorithm does not currently support parallel processing. (description needs work)

Algorithm-specific control parameters:

Reference: Bassingthwaighte JB, Chan IS, Goldstein AA, et al.: GGOPT: an unconstrained non-linear optimizer. Comput Methods Programs Biomed. 1988;26(3): 275–81. PubMed link

Nelder-Mead

Nelder-Mead is an unbounded, steepest descent algorithm by Nelder and Mead. It is also called non-linear Simplex. This algorithm supports multiprocessing (MP).

During each iteration in a P-parameter optimization, this algorithm performs a P or P+1 parmeter queries (model runs). Several additional single queries are also performed. Ideal MP speedup on an N-processor system on be roughly of order P (if P is a factor of N), or order N (if N is a factor of P).

This algorithm differs from the previously available JSim "Simplex" (above) in that:

Algorithm-specific control parameters:

Reference: Nelder JA, Mead R: A simplex method for function minimization. The Computer Journal. 1965;7(4): 308–313.

GridSearch

GridSearch is a bounded, parallel algorithm. The algorithm operates via progressively restricted search of parameter space on a regularly spaced grid of npoints per dimension. Each iteration, npoints^nparm points are searched for the minimum residual. Each parameter dimension is then restricted to one grid delta around that minimum and the search repeats until stopping criteria are met.

Search bounds in each dimension narrow by a factor of at least 2/(npoints-1) each iteration. Thus, npoints must be at least 4. Each iteration requires up to npoints^nparm residual calculations. Residual calculations are reused when possible, and this reuse is most efficient when npoints is 1 + 2^N for some N. Therefore, npoints defaults to 5, which is the smallest "efficient" value.

This algorithm is very not efficient for very smooth residual functions in high-dimensional space. It works well on noisy functions when low accuraccy situations (e.g. 3 significant digits required). With npoints large, it copes well with multiple local minima. An effective strategy may be to use several interations of GridSearch to estimate a global minimum, and then use a steepest-descent algorithm to fine tune the answer.

The number of points searched during each iteration is typically large compared to the number of available processors. Typical MP speedup on an N-processor system is therefore on the order of N.

Algorithm-specific control parameters:

Reference: Kolda TG, Lewis RM, Torczon V: Optimization by direct search: New perspectives on some classical and modern methods. Siam Review. 2003;45(3): 385–482.

NL2SOL

This version of Nl2sol is derived from NL2SOL, a library of FORTRAN routines which implement an adaptive nonlinear least-squares algorithm. It has been modified to perform all calculations in double precision. It is an unbounded optimizer. This optimizer does not support multi-processing.

Algorithm-specific control parameters:

References:

Sensop

Sensop is a variant of Levenberg-Marquardt algorithm that utilized the maximum parameter sensitivity to determine step size. It is a bounded optimizer, supporting multiprocessing.

Algorithm-specific control parameters:

The JSim java implimented Sensop algorithm can be found here (Github).

Reference: Chan IS, Goldstein AA, Bassingthwaighte JB: SENSOP: a derivative-free solver for non-linear least squares with sensitivity scaling. Ann Biomed Eng. 1993;21(6): 621–31. PubMed link.

Simulated Annealing

Simulated annealing is an algorithm inspired by the annealing process in metullurgy. As the problem "cools" from its initial "temperature", random fluctuations of model parameters are reduced. JSim implements a bounded version of this algorithm that supports multiprocessing.

Algorithm-specific control parameters:

The JSim java implimented Simulated Annealing algorithm can be found here (Github).

Reference: Kirkpatrick S, Gelatt CD Jr, Vecchi MP: Optimization by simulated annealing. Science. 1983; 220(4598): 671–680

Genetic Algorithms

This algorithm is available only in JSim version 2.01 and above.

Genetic algorithms are a family of algorithms that generate a population of candidate solutions and then select the best solutions in each iteration. A new population of solutions is created during each iteration. There are different ways of specifying how a new population is generated from the existing population. The error calculation is used to score and rank the candidate solution. The "fit" individuals in the existing population are selected using one of three methods: (1) roulette-wheel, (2) tournament selection, or (3) elitism. In the roulette-wheel method, the probability of a solution being selected is inversely proportional to the error. In the tournament selection, two random solutions are selected and the one with the lower error is placed in the new population. In elitism, all the solutions with the lowest errors (with a cutoff fraction) are selected. New solutions are selected by "mutating" and "crossing over" existing solutions.

Algorithm-specific control parameters:

The JSim java implimented Genetic algorithm can be found here (Github). The JSim genetic algorithm supports multiprocessors (parallel processing).

Reference: Holland JH: Adaptation in natural and artificial Systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press. 1992; 183.

Particle Swarm Algorithm (PSO)

This algorithm is available only in JSim version 2.19 and above.

The PSO algorithm works by having swarm candidate solutions (called particles) that move around in the search-space according to a few simple rules. The movements of the particles are guided by their own best known position in the search-space as well as the entire swarm's best known position. When improved positions are being discovered these will then come to guide the movements of the swarm. The process is repeated and by doing so it is hoped, but not guaranteed, to converge to a minimum value. This optimization can be useful when fitting a large number of parameters (>10) when estimates of their values are unknown or have a large range of values. The PSO algorithm supports multiprocessors (parallel processing) in JSim release v 2.20 and later.

Algorithm-specific control parameters:

Further work/issues:

The JSim java implimented Particle Swarm algorithm can be found here (Github).

Reference: James Kennedy and Russell C. Eberhart. Particle swarm optimization. In Proceedings of the 1995 IEEE International Conference on Neural Networks, pages 1942–1948, Piscataway, New Jersey, 1995. IEEE Service Center. IEEE paper.

Principle Axis Algorithm (PRAXIS)

This algorithm is available only in JSim version 2.20 and above.

PRAXIS seeks an M-dimensional point X (parameters to fit) which minimizes a given fitness, or cost, function. PRAXIS minimizes along directions that are conjugates of each other to locate a minima and is a derivative free optimizer. The code is a refinement of Powell's method of conjugate search directions and the fitness function need not be smoothly differentiable.

Algorithm-specific control parameters:

The JSim java implimented PRAXIS algorithm can be found here (Github).

Reference:

Comments or Questions?

[This page was last modified 25Jun20, 10:57 am.]

Model development and archiving support at physiome.org provided by the following grants: NIH U01HL122199 Analyzing the Cardiac Power Grid, 09/15/2015 - 05/31/2020, NIH/NIBIB BE08407 Software Integration, JSim and SBW 6/1/09-5/31/13; NIH/NHLBI T15 HL88516-01 Modeling for Heart, Lung and Blood: From Cell to Organ, 4/1/07-3/31/11; NSF BES-0506477 Adaptive Multi-Scale Model Simulation, 8/15/05-7/31/08; NIH/NHLBI R01 HL073598 Core 3: 3D Imaging and Computer Modeling of the Respiratory Tract, 9/1/04-8/31/09; as well as prior support from NIH/NCRR P41 RR01243 Simulation Resource in Circulatory Mass Transport and Exchange, 12/1/1980-11/30/01 and NIH/NIBIB R01 EB001973 JSim: A Simulation Analysis Platform, 3/1/02-2/28/07.