An intelligent multi-restart memetic algorithm for box constrained global optimisation

J. Sun, J. M. Garibaldi, N. Krasnogor, Q. Zhang

Research output: Contribution to journalArticle

22 Citations (Scopus)
13 Downloads (Pure)

Abstract

In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649–664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.
Original languageEnglish
Pages (from-to)107-147
Number of pages41
JournalEvolutionary Computation
Volume21
Issue number1
Early online date12 Mar 2013
DOIs
Publication statusPublished - 2013
Externally publishedYes

Fingerprint

Constrained Global Optimization
Memetic Algorithm
Restart
Constrained optimization
Global optimization
Evolutionary algorithms
Evolutionary Algorithms
Sampling Strategy
Multivariate Models
Probability Model
Sampling
Derivatives
Derivative-free
Continuous Optimization
Basin of Attraction
Comparison Result
Global Optimum
Evolutionary Computation
Test function
Decoupling

Cite this

Sun, J. ; Garibaldi, J. M. ; Krasnogor, N. ; Zhang, Q. / An intelligent multi-restart memetic algorithm for box constrained global optimisation. In: Evolutionary Computation. 2013 ; Vol. 21, No. 1. pp. 107-147.
@article{322e84f955aa47fb875a9697f45802b1,
title = "An intelligent multi-restart memetic algorithm for box constrained global optimisation",
abstract = "In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649–664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.",
author = "J. Sun and Garibaldi, {J. M.} and N. Krasnogor and Q. Zhang",
year = "2013",
doi = "10.1162/EVCO_a_00068",
language = "English",
volume = "21",
pages = "107--147",
journal = "Evolutionary Computation",
issn = "1063-6560",
publisher = "MIT Press Journals",
number = "1",

}

An intelligent multi-restart memetic algorithm for box constrained global optimisation. / Sun, J.; Garibaldi, J. M.; Krasnogor, N.; Zhang, Q.

In: Evolutionary Computation, Vol. 21, No. 1, 2013, p. 107-147.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An intelligent multi-restart memetic algorithm for box constrained global optimisation

AU - Sun, J.

AU - Garibaldi, J. M.

AU - Krasnogor, N.

AU - Zhang, Q.

PY - 2013

Y1 - 2013

N2 - In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649–664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.

AB - In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649–664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.

U2 - 10.1162/EVCO_a_00068

DO - 10.1162/EVCO_a_00068

M3 - Article

VL - 21

SP - 107

EP - 147

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1063-6560

IS - 1

ER -