Dreaming of Metaheuristics

An EDA in a few lines of python

nojhan — Mon, 23 Jun 2008 21:55:00 +0200

About an interesting post I have already commented, Julian Togelius said: "I know roughly what an EDA does, but I couldn't sit down an implement one on the spot [...]"

I personally think that estimation of distribution algorithms (EDA) are some of the more elegant an easy to use metaheuristics. Obviously, this highly depends of the mind configuration :-) Anyway, as a piece of code is more comprehensive than a long speech, I've made a very simple and small EDA in python, to illustrate my thought.

This is a simple continuous EDA using a (also simple) normal probability density function to optimize a (once more simple) function with two variables. As you can see, the code is (guess what ?) simple, only a few lines with some scipy functions, and that's it.

from scipy import *



# The problem to optimize

def x2y2( x ):

        return x[0]**2 +
x[1]**2



class eda:

        def __init__(self,
of):

                #
Algorithm parameters

                self.iterations
= 100

                self.sample_size
= 100

                self.select_ratio
= 0.5

                self.epsilon
= 10e-6



                #
class members

                self.objective_function
= of

                self.dimensions
= 2

                self.sample
= []

                self.means
= []

                self.stdevs
= []        

                self.debug
= False



        def run(self):


                #
uniform initialization

                self.sample
= random.rand( self.sample_size, self.dimensions+1 )

                #
cosmetic

                self.sample
= self.sample * 200 - 100



                self.evaluate()


                


                #
main loop

                i
= 0

                while i
< self.iterations:

                        i
+= 1

                        self.dispersion_reduction()


                        self.estimate_parameters()


                        self.draw_sample()


                        self.evaluate()




                #
sort the final sample

                self.sample_sort()


                #
output the optimum

                print "#[
x y f(x,y) ]"

                print self.sample[0]




        def sample_sort(self):


                #
sort rows on the last column

                self.sample
= self.sample[ argsort( self.sample[:,-1], 0 ) ]



        def dispersion_reduction(self):


                self.sample_sort()




                #
number of points to select

                nb
= int( floor( self.sample_size * self.select_ratio ) )



                #
selection

                self.sample
= self.sample[:nb]



        def estimate_parameters(
self ):

                #
points sub array (without values)

                mat
= self.sample[:,:self.dimensions]

                


                #
row means (axis 0 in scipy)

                self.means
= mean( mat, 0 )

                


                #
row standard deviation

                self.stdevs
= std( mat, 0 )



        def draw_sample(self):


                #
for each variable to optimize

                for i
in xrange(self.dimensions):

                        #
if the dispersion is null

                        if self.stdevs[i]
== 0.0:

                                #
set it to a minimal value

                                self.stdevs[i]
= self.epsilon

                


                #
empty sample

                self.sample
= zeros( (self.sample_size, self.dimensions+1) )

                


                #
for each point

                for i
in xrange( self.sample_size ):

                        #
draw in random normal

                        p
= random.normal( self.means, self.stdevs )

                        #
put it into the sample

                        self.sample[i][:self.dimensions]
= p



        def evaluate(self):


                #
for each point

                for i
in xrange( self.sample_size ):

                        d
= self.dimensions

                        #
call the objective function

                        #  
the third element is the result of the objective function call

                        #  
taking the first two elements as variables

                        self.sample[i][-1]  =
self.objective_function( self.sample[i][:d] )



if __name__=="__main__":

        a = eda( x2y2 )

        a.run()

See also the file alone with a debug mode, to see how it works in details.

Metaheuristic validation in a nutshell

nojhan — Wed, 18 Jun 2008 20:20:00 +0200

People using metaheuristics often forget that the price to pay for their ease of adaptation to a new problem is the hard validation work. There is several things to keep in mind when using a metaheuristic, especially when one want to prove that they work in practice.

This (kind of) mind map try to list what you should do, and a short set of main tools to do it. It is not always mandatory to use all the tools, sometimes it is just a matter of choice (like for the parameter setting), sometimes the more you do, the better it is (like for performance assessment).

The graphic has been drawn in SVG, and I have put some references in a very small font at the bottom of some boxes. Thus, it would be more confortable to view it in Firefox or in Inkscape, and to zoom where needed. Try the SVG version.

A chronology of metaheuristics

nojhan — Mon, 03 Mar 2008 14:33:00 +0100

At last, I found some time to translate my chronology of metaheuristics I have made for the french Wikipedia. I put it here for the records, but you will find a more up-to-date version on the english Wikipedia article about Metaheuristics.

Timeline

Detailled chronology

1952 : first works on stochastics optimization methods^[1].
1954 : Barricelli carry out the firsts simulations of the evolution process and use them on general optimization problems^[2].
1965 : Rechenberg conceives the first algorithm using evolution strategies^[3].
1966 : Fogel, Owens et Walsh propose evolutionary programming^[4].
1970 : Hastings conceive the Metropolis-Hastings algorithm, which can sample any probability density function^[5].
1970 : John Horton Conway works on the game of life, the most known cellular automata nowadays.
1975 : working on cellular automata, John Holland propose the firsts genetic algorithms^[6].
1980 : Smith come through genetic programming^[7].
1983 : refering to the work of Hastings, Kirkpatrick, Gelatt and Vecchi conceive the simulated annealing^[8].
1985 : independently, Černý propose the same algorithm^[9].
1986 : the first mention of the term meta-heuristic is done by Fred Glover, during the conception of tabu search^[10]

1986 : Farmer, Packard and Perelson work on artificial immune systems^[11].
1988 : the first conference on genetic algorithms is organized at the University of Illinois at Urbana-Champaign.
1988 : works on the collective behaviour of ants finds an application in artificial intelligence^[12].
1988 : Koza register his first patent on genetic programming^[13].
1989 : Goldberg publish one of the most known book on genetic algorithms^[14].
1989 : Evolver, the first optimisation software using genetic algorithm, is released by the Axcelis company.
1989 : the term memetic algorithm appear^[15].
1990 : the ant colony algorithms are proposed by Marco Dorigo, in its Ph.D. thesis^[16].
1993 : the term "evolutionary computation" is spreading itself, with the publication of the eponymous journal, published by the Massachusetts Institute of Technology.
1995 : Feo and Resende propose the Greedy randomized adaptive search procedure (GRASP)^[17].
1995 : Kennedy and Eberhart conceive the particle swarm optimization^[18]^[19].
1996 : Mühlenbein and Paaß work on estimation of distribution algorithms^[20].
1997 : Storn and Price propose a differential evolution algorithm^[21].
1997 : Rubinstein works on the cross entropy method^[22].
1999 : Boettcher propose the extremal optimization^[23].
2000 : firsts interactive genetic algorithms^[24].

References

↑ V. Angel, La rugosité des paysages : une théorie pour la difficulté des problèmes d’optimisation combinatoire relativement aux métaheuristiques, thèse de doctorat de l’université de Paris-Sud, Orsay, 1998.
↑ J. Dreo, J.-P. Aumasson, W. Tfaili, P. Siarry, Adaptive Learning Search, a new tool to help comprehending metaheuristics, to appear in the International Journal on Artificial Intelligence Tools.
↑ El-Ghazali Talbi, A taxonomy of hybrid metaheuristics, Journal of Heuristics, volume 8, n^o 2, pages 541-564, septembre 2002
↑ (en) exemples de fonctions de tests pour métaheuristiques d’optimisation de problèmes continus.
↑ W. Dullaert, M. Sevaux, K. Sörensen et J. Springael, Applications of metaheuristics, numéro spécial du European Journal of Operational Research, n^o 179, 2007.
↑ Robbins, H. and Monro, S., A Stochastic Approximation Method, Annals of Mathematical Statistics, vol. 22, pp. 400-407, 1951
↑ Barricelli, Nils Aall, Esempi numerici di processi di evoluzione, Methodos, pp. 45-68, 1954
↑ Rechenberg, I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation, 1965
↑ Fogel, L., Owens, A.J., Walsh, M.J., Artificial Intelligence through Simulated Evolution, Wiley, 1966
↑ W.K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika, volume 57, n^o 1, pages 97-109, 1970
↑ Holland, John H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975
↑ Smith, S.F., A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh), 1980
↑ S. Kirkpatrick, C. D. Gelatt et M. P. Vecchi, Optimization by Simulated Annealing, Science, volume 220, n^o 4598, pages 671-680, 1983
↑ V. Cerny, A thermodynamical approach to the travelling salesman problem : an efficient simulation algorithm Journal of Optimization Theory and Applications, volume45, pages 41-51, 1985
↑ Fred GLover, Future Paths for Integer Programming and Links to Artificial Intelligence, Comput. & Ops. Res.Vol. 13, No.5, pp. 533-549, 1986
↑ J.D. Farmer, N. Packard and A. Perelson, The immune system, adaptation and machine learning, Physica D, vol. 22, pp. 187--204, 1986
↑ F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie, 1988
↑ Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. United States Patent 4,935,877. Filed May 20, 1988. Issued June 19, 1990
↑ Goldberg, David E., Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA., 1989
↑ P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, 1989.
↑ M. Dorigo, Optimization, Learning and Natural Algorithms, Thèse de doctorat, Politecnico di Milano, Italie, 1992.
↑ Feo, T., Resende, M., Greedy randomized adaptive search procedure, Journal of Global Optimization, tome 42, page 32--37, 1992
↑ Eberhart, R. C. et Kennedy, J., A new optimizer using particle swarm theory, Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43, 1995
↑ Kennedy, J. et Eberhart, R. C., Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995
↑ Mülhenbein, H., Paaß, G., From recombination of genes to the estimation of distribution I. Binary parameters, Lectures Notes in Computer Science 1411: Parallel Problem Solving from Nature, tome PPSN IV, pages 178--187, 1996
↑ Rainer Storn, Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, Journal of Global Optimization, volume 11, n^o 4, pages 341-359, 1997
↑ Rubinstein, R.Y., Optimization of Computer simulation Models with Rare Events, European Journal of Operations Research, 99, 89-112, 1997
↑ Stefan Boettcher, Allon G. Percus, "Extremal Optimization : Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)
↑ Takagi, H., Active user intervention in an EC Search, Proceesings of the JCIS 2000

The problem with spreading new metaheuristics

nojhan — Mon, 03 Mar 2008 11:19:00 +0100

Marcelo De Brito had interesting thoughts about what he call New Wave Of Genetic Algorithms. He is surprised that when "evolutionary computation" is applied to a new problem, the first algorithm used is the good old canonic genetic algorithm, despite that there exist active researchs on Estimation of Distribution Algorithms. Julian Togelius write that it may be because people does not understand other algorithms, or even know that anything else exists.

I think that is definitely true. This subject is a kind of hobby for me. Indeed, as I have came from ecology to applied mathematics, I feel like a kind of generalist researcher, not being able to be the best somewhere, but trying to be as good as possible on several fields. Concerning the field of what Marcelo called NWOGA, I would like to emphasize some other things.

As David E. Goldberg say in its courses, genetic algorithm is the term everybody use. For specialist, a GA is just a kind of "evolutionary algorithm", with specific rules, that are more defined by history than by anything else.

The litterature on evolutionary computation is quite big, the first algorithm being designed in 1965 (evolutionary strategies, followed by evolutionary programming in 1966), making it difficult to spread deep changes on basic concepts.

There exist a lot more stochastic algorithms for global optimization than just evolutionary ones. I prefer to call the stochastic metaheuristics, or simply metaheuristics, because this lead to far less bias than a metaphoric naming (cf. the previous post on classification of metaheuristics).

For example, during my PhD thesis, I was convinced that some Ant Colony Optimization algorithms were just equivalent to Estimation of Distribution Algorithms, when talking about continuous problems. Moreover, I'm now convinced that a lot of metaheuristics just shares some common stochastic sampling processes, that are not specifiquely related to evolution. For example, mathematically, Simulated Annealing is just a kind of EDA using an approximation of the objective function as a model (or inversely, of course).

As Julian says: I know roughly what an EDA does, but I couldn't sit down an implement one on the spot. This is, in my humble opinion, one of the more important thing to keep in mind. Indeed, there exist more and more papers claming that a correct parameter setting of a metaheuristic can lead to the performances of any competing metaheuristic.

Thus, the true discriminatory criterion is not the fantasised intrinsic capability, but the ease of implementation and parameter setting on a specific problem. In other words, choose the algorithm you like, but be aware that there exists a lot of other ones.

Classification of metaheuristics

nojhan — Fri, 12 Oct 2007 00:00:00 +0200

I eventually find some time to try a graphical representation of how metaheuristics could be classified.

Here is a slidified version, that shows each classes independently:

And a static image version:

Note that some metaheuristics are not completely contained in certains classes, this indicate that the method could be considered as part of the class or not, depending on your point of view.

I have reported the following metaheuristics:

genetic programming, genetic algorithms, differential evolution,
evolution strategies,
estimation of distribution algorithms,
particle swarm optimization,
ant colony optimization,
simulated annealing,
tabu search,
GRASP,
variable neighborhood search,
iterated, stochastic and guided local search.

And the following classes :

metaheurisitcs vs local search,
population metaheuristics vs trajectory-based ones,
evolutionary computation or not,
nature-inspired methods or not,
dynamic objective function vs static ones,
memory-based algorithms vs memory-less,
implicit, explicit or direct metaheuristics.

I proposed the last class, so that it may not be well-known. You will find more informations about it in the following paper: Adaptive Learning Search, a new tool to help comprehending metaheuristics, J. Dreo, J.-P. Aumasson, W. Tfaili, P. Siarry, International Journal on Artificial Intelligence Tools, Vol. 16, No. 3.. - 1 June 2007

I didn't placed a stochastic category, as it seems a bit difficult to represent graphically. Indeed, a lot of methods could be "stochasticized" or "derandomized" in several ways.

There is surely several lacks or errors, feel free to give your point of view with a trackback, an email or by modifying the SVG source version (comments are disabled due to spam that I didn't have time to fight accurately).

Hybridization : estimation of distribution as a meta-model filter generator for metaheuristics ?

nojhan — Fri, 27 Jul 2007 00:00:00 +0200

An interesting idea is to use meta-model (a priori representation of the problem) as a filter to bias the sample produced by metaheuristics. This approach seems especially promising for engineering problem, where computing the objective function is very expensive.

One simple form of meta-model is a probability density function, approximating the shape of the objective function. This PDF could thus be used to filter out bad points before evaluation.

Why, then, do not directly use EDA to generate the sample ? Because one can imagine that the problem shape is not well known, and that using a complex PDF is impossible (too expensive to compute, for example). Then, using a classical indirect metaheuristic (let say an evolutionary algorithm) should be preferable (computationnaly inexpensive) for the sample generation. If one know a good approximation to use for the distribution of the EDA (not too computationnaly expensive), one can imagine using the best part of the two worlds.

An example could be a problem with real variable : using an EDA with a multi-variate normal distribution is computationnaly expensive (due to the estimation of the co-variance, mainly), and using a mixture of gaussian kernels makes difficult to have an a priori on the problem. Thus, why not using a indirect metaheuristic to handle the sample generation, and use a meta-model which parameters are estimated from the previous sample, according to a chosen distribution ?

One more hybridization to try...

Error metrics

nojhan — Thu, 05 Jul 2007 00:00:00 +0200

Many metrics are used to assess the quality of approximation found by metaheuristics. Two of them are used really often: distance to the true optimum according to its position and to its value.

Unfortunately, the objective function's shape can vary a lot in real-world problem, making these metrics difficult to interpret. For example, if the optimum is in a very deep valley (in value), a solution close to it in position may not signifiate that the algorithm have well learn the shape of it. Inversely, a solution close to an optimum in value may not signifiate that it is in the same valley.

One metric that can counter thse drawbacks is a distance taking into account the parameters of the problem as well as the value dimension.

Anyway, the question of the type of distance to use is dependent of the problem.

Random draw in a sphere

nojhan — Wed, 28 Mar 2007 00:00:00 +0200

When adapting combinatorial metaheuristics to continuous problems, one sometimes use a sphere as an approximation of the "neighborhood". The idea is thus to draw the neighbours around a solution, for example in order to apply a simple mutation in a genetic algorithm.

Sometimes, one choose to use an uniform law, but how to draw random vectors uniformly in an hyper-sphere ?

The first idea that comes to mind is to use a polar coordinate system and draw the radius r and the angles a₁...a₂...a_i...a_N with a uniform law. Then, one convert the coordinates in the rectangular system, x₁...x₂...x_i...x_N.

The result is interesting for a metaheuristic design, but is not a uniform distribution:

The correct method is to draw each x_i according to: x_i=(r_i^1/Na_i)/√(∑(a_i))
(in L^AT_EX : $x_{i}=\frac{r^{\frac{1}{N}}_i\cdot a_{i}}{\sqrt{{\displaystyle \sum _{j=1}^{N}a_{i}}}}$ )

With r_i uniformly drawn in U_0,1 and a following a normal law N_O,1

The result is then a true uniform distribution:

Credits goes to Maurice Clerc for detecting and solving the problem.

Evolving Objects 1.0 is out

nojhan — Sun, 07 Jan 2007 00:00:00 +0100

The EO framework has just reached the 1.0 version. This is one of the most interesting library for metaheuristics.

It is a templatized C++ framework, with a component based architecture. EO is focused on "evolutionary computing" (a synonym of metaheuristics, imho) and can be used for any population-base metaheuristics. There exists versions for local searches, multi-objective optimization or parallel architectures... a real good piece of software :-)

Random and learning

nojhan — Thu, 21 Dec 2006 00:00:00 +0100

The Machine Learning (Theory) blog, by John Langford, has a very intersting post on "Explicit Randomization in Learning algorithms".

The post and its comments are talking about machine-learning, but can largely be applied to metaheuristics. The page is listing several reason for using randomization, from which some are of special intersts for metaheuristics:

symmetry breaking as a way to make decision, which is of great importance for metaheuristics, which must learn and choose where are the "promising regions";
overfit avoidance, which is related to the intensification/diversification balance problem;
adversary defeating and bias suppression, which can be interpreted as trying to design a true meta-heuristic (i.e. that can be applied on several problems without major changes).

Of course, it should be possible to design a completely deterministic algorithm that takes decisions, achieve a correct i/d balance and can tackle all problems... Even if this force to integrate the problems themselves in the algorithm, it should be possible. The drawback is that it is computationally intractable.

In fact, metaheuristics (and, as far as I understand, machine-learning algorithms) are located somewhere between random search algorithms and deterministic ones. The compromise between these two tendencies is dependent of the problem and of the offered computational effort.

Metaheuristics and machine-learning

nojhan — Tue, 19 Dec 2006 00:00:00 +0100

Metaheuristics and machine-learning algorithms shares a large number of characteristics, like stochastic processes, manipulaton of probability density functions, etc.

One of the interesting evolution of the research on metaheuristics these years is the increasing bridge-building with machine-learning. I see at least two interesting pathways: the use of metaheuristics in machine-learning and the use of machine-learning in metaheuristics.

The first point is not really new, machine-learning heavily use optimization, and it was natural to try stochastic algorithms where local search or exact algorithms failed. Nevertheless, there is now a sufficient litterature to organize some special sessions in some symposium. For 2007, there will be a special session on Genetics-Based Machine Learning at CEC, and a track on Genetics-Based Machine Learning and Learning Classifier Systems at GECCO. These events are centered around "genetic" algortihm (see the posts on the IlliGAL blog : 1, 2), despite the fact that there are several papers using other metaheuritics, like simulated annealing, but this is a common drawback, and does not affect the interest of the subject.

The second point is less exploited, but I find it of great interest. A simple example of what can be done with machine-learning inside metaheuristic can be shown with estimation of distribution algorithms. In these metaheuristics, a probability density function is used to explicitely build a new sample of the objective function (a "population", in the evolutionary computation terminology) at each iteration. It is then crucial to build a probability density function that is related to the structure of the objective function (the "fitness landscape"). There, it should be really interesting to build the model of the pdf itself from a selected sample, using a machine-learning algorithm. There is some interesting papers talking about that.

If you mix these approaches with the problem of estimating a Boltzmann distribution (the basis of simulated annealing), you should have an awesome research field...

Metaheuristics and experimental research

nojhan — Sun, 10 Dec 2006 00:00:00 +0100

Springer has just published a book on "Experimental Research in Evolutionary Computation", written by Thomas Bartz-Beielstein.

Thomas Bartz-Beielstein is working on the statistical analysis of the behaviour of metaheuristics (see its tutorials at GECCO and CEC), and the publication of its book is a really great thing. I haven't read it yet, but the table of content seems really promising. There is a true need for such work in the metaheuristics community, and in stochastic optimization in general.

A friend said to me that the lack of experimental culture in the computer science community was a form of consensus, perhaps because theoretical aspects of mathematics was the "only way to make true science". This is a true problem when you deal with stochastic algorithm, applied to real world problem. Despite the fact that several papers early call for more rigourous experimental studies of metaheuristcs (E.D. Taillard has written papers on this problem several years ago, for example), the community does not seems to quickly react.

Yet, things are changing, after the series of CEC special sessions on benchmark for metaheuristics, there is more and more papers on how to test stochastic optimization algorithms and outline the results. I think this book is coming timely... the next step will be to promote the dissemination of the results data (and code!), in an open format, along with the papers.

Frameworks for metaheuristics

nojhan — Sat, 28 Oct 2006 06:34:00 +0200

Note that descriptions are picked up from the web sites of the projects.

As one can see, most of these softwares are designed for evolutionnary algorithms, but I recommend you to try out some of the generic frameworks, because "genetic" algorithms are not always the best choice for solving an optimization problem, despite their wide spread.

Here are the frameworks I would recommend. These frameworks are free softwares, you can use, look at the code, modify it and redistribute it (precious qualities for frameworks).

I would also recommend C or C++, which permits to implement fast programs, while using object oriented programming. C++ compilers are also available for a large choice of plateforms (with a special distinction for GCC, which is free software). A fast progam is crucial for testing algorithms on real problems and using a well-known langage is a good idea.

The main idea beside the design of the framework is specified as one of the following keywords:

template: design a new algorithm concist in extending a base class, perhaps the simple object model to understand, but it can be difficult to re-use existing code.
component: design a new algorithm concist in select its component from availables operators, make it easy to implement algorithms, but it can be quite difficult to understand the underlying model. It can be hard to add new algorithm paradigm (generaly used for evolutionnary algorithms).
function: design a new algorithm concist in use the framework's primitives. Simple to understand, but one must learn the primitives to use and code a lot of stuff.

Favorites

Here is my list :

Open Metaheuristics: a library aimed at the conception of metaheuristics (i.e. genetic/evolutionnary algorithms, tabu search, simulated annealing, ant colony algorithms, etc.). One of the main goal of oMetah is to permit rigourous empirical tests of metaheuristics, through a statistical approach. (C++, LGPL, template)
*EO: a set of paradigm-free Evolutionary Computation libraries dedicated to the flexible design of EAs through evolving objects superseding the most common dialects (Genetic Algorithms, Evolution Strategies, Evolutionary Programming and Genetic Programming). (C++, GPL, component)
Sferes: a framework that gathers an evolution framework with a simulation framework. It is dedicated to experiments involving the design of artificial agents through artificial evolutionary algorithms, like Genetic Algorithms or Evolution Strategies. (C++, CeCILL, component)
openBEAGLE: Evolutionary Computation (EC) framework. (C++, LGPL, component).
PISA: Platform and Programming Language Independent Interface for Search Algorithms. PISA is mainly dedicated to multi-objective search, where the optimization problem is characterized by a set of conflicting goals and not just one criterion that needs to be optimized. (C, BSD, function)
GAlib: defines classes for using genetic algorithms to do optimization in any C++ program using any representation and genetic operators. The distribution includes extensive documentation and many examples.. (C++, MIT, component)
MOMHLib++: a library of C++ classes that implements a number of multiple objective metaheuristics. It has been developed on the basis of former implementations of Pareto simulated annealing (PSA) and multiple objective genetic local search (MOGLS). (C++, GPL, template).
ECJ Java Evolutionary Computation Research System. (Java, AFL, component)

Other

These frameworks are not those which I would recommend, but they have some properties that could be intersting :

Python Genetic Programming Project: implements a Genetic Programming System in Python. (Python, GPL)
HeuristicLab: A Paradigm-Independent and Extensible Environment for Heuristic Optimization. (C#/.NET, Proprietary)

If you want to find out more and more frameworks, try searching "genetic" on source forge

Many of these projects are dead, be carefull if you need a maintained framework. Take a close look to the project activity, generally, the number of developers and file releases give you a good idea of the framework vitality. Also check if it is a student's project for a training course or if it is made by professional researchers.

Confirmation of the biological foundations of particle swarm optimization

nojhan — Sun, 10 Sep 2006 00:00:00 +0200

Particle swarm optimization (PSO) is based on biological (and theorical physic) work concerning self-organizaton in animals groups. Up to now, theory explained that animals must adjust their direction in order to set up a group. PSO use this concept to build a set of vectors that will exlpore the search space of an optimization problem, while converging on an optimum.

One key prediction of the theory is a transition between the recruitment of the individuals and the collective motion. This transition "from disorder to order" has been proved in situ by biologists, while studying locusts. They have filmed during 8 hours a group of 5 to 120 desert locusts, in a circular cockpit, and analysed the motions datas. The study shows that, at low density (under 25 individuals/m2), the animals moves independently. When reaching 25 to 60 locusts/m2, they form collective groups, which direction can vary abruptly. Beyond 75 locusts/m2, the coordinated marching is homogen.

While this should not change the use of PSO, which is a simplified model, it is always interesting to consider works talking about this transition between order and chaos, in self-organized systems. Indeed, this transition can also occurs in metaheuristics, and is perhaps interesting for further research, like in dynamical optimization.

<a href="http://www.sciencemag.org/cgi/content/abstract/312/5778/1402" hreflang="en">From Disorder to Order in Marching Locusts</a>, Buhl et al., Science, Vol. 312. no. 5778, pp. 1402 - 1406, 2 june 2006.

Finding references about metaheuristics (and computer science)

nojhan — Fri, 01 Sep 2006 00:00:00 +0200

The Internet is rapidly becoming the first place to search for scientific papers. But the number of places gathering ressources becomes really high. Here is a list of web sites with free access. These are places where you can find some stuff about metaheuristics, I have not include all the available databases (nor journals web pages), despite the fact that metaheuristics are often apply to a wide range of fields.

Online collective bibliography managers are really usefull for picking references when surfing on journal sites, they permits to automatically gather the reference's informations, tag them, share your list with others and export it in your local reference manager.
- CiteUlike: really intersting for computer science, see my user page, the metaheuristics group, the evolutionary computation group and the optimization group. With watchlist and syndication based on RSS.
- Connotea, more aim at clinicians and biologist.
digital libraries or paper databases:
- CiteSeer, search for citations and papers, show citations inside each papers, permits corrections on items, really interesting for computer science.
- ScienceDirect, database, require registration, make available a watchlist based on email alerts.
- arXiv, an e-print service, well formated ressources, RSS syndication.
- Springer Links, books & papers database, RSS syndication, watchlist for registered users.
- ACM portal, digital library, no syndication or free watchlist for registered users.
- IEEE Xplore, database, no syndication, no watchlist, email alerts at field level only.
- The Collection of Computer Science Bibliographies, database, RSS syndication.
- PubMed, database, emails alerts for registered users.
- Backwell Synergy, database, RSS/Atom syndication, email alerts.
- Optimization Online, e-print about optimization, monthly email alerts.
- Scitation, database, no syndication, no free email alerts.
- Wiley InterScience, database, no syndication, emails alerts for registerd users.
generalistic search-engines:
- Scirus
- Google Scholar

Metaheuristics & benchmarks at CEC

nojhan — Wed, 30 Aug 2006 00:00:00 +0200

The IEEE Congress on Evolutionary Computation (CEC) is a well-known event that take place every year.

Since 2005, there is an interesting group of special sessions, organized by Ponnuthurai Nagaratnam Suganthan:

2005, Real-Parameter Optimization,
2006, Constrained Real-Parameter Optimization,
2007, Performance Assessment of Multi-Objective Optimization Algorithms.

What is really interesting in these sessions is the systematic presence of an implemented generalistic benchmark, built after discussion between researchers.

This is an extremely necessary practice, which is, unfortunately, not generalized. Indeed, this is the first step toward a rigourous performance assessment of metaheuristics (the second one being a true statistical approach, and the third one a considered data presentation).

Some blogs about metaheuristics

nojhan — Fri, 25 Aug 2006 00:00:00 +0200

As this blog is just starting, I have searched some peoples talking about metaheuristics, and found some that are really interesting.

IlliGAL Blogging: the blog of David E. Goldberg... well, he is a great researcher and everybody knows his work. His blog is really interesting.
Pensive Pondering: an awesome blog, Jason Brownlee talks about biologically inspired computation. Surprisingly, I found an old post on his blog about the definition of metaheuristics, where one can see that we share a lot of common ideas on the subject (see the previous post).
Adaptare: Julián García writes on "Evolutionary computation, evolutionary dynamics, cultural evolution and the like", an interesting and active blog.

These are the best blogs I have found, you will find some other (less interesting) blogs in my OPML feedlist.

What are metaheuristics ?

nojhan — Wed, 23 Aug 2006 00:00:00 +0200

Despite the title of this blog, the term metaheuristic is not really well defined.

One of the first occurence of the term can (of course) be found in a paper by Fred Glover^[1]: Future Paths for Integer Programming and Links to Artificial Intelligence^[2]. In the section concerning tabu search, he talks about meta-heuristic:

Tabu search may be viewed as a "meta-heuristic" superimposed on another heuristic. The approach undertakes to transcend local optimality by a strategy of forbidding (or, more broadly, penalizing) certain moves.

In the AI field, a heuristic is a specific method that help solving a problem (from the greek for to find), but how must we understand the meta word ? Well, in greek, it means "after", "beyond" (like in metaphysic) or "about" (like in metadata). Reading Glover, metaheuristics seems to be heuristics beyond heuristics, which seems to be a good old definition, but what is the definition nowadays ? The litterature is really prolific on this subject, and the definitions are numerous.

There is at least three tendencies :

one that consider that the most important part of metaheuristcs is the gathering of several heuristics,
one other that promotes the fact that metaheuristics are designed as generalistic methods, that can tackle several problems without major changes in their design,
the last one that use the term only for evolutionnary algorithms when they are hybridicized with local searches (methods that are called memetic algorithms in the other points of vue).

The last one is quite minor in the generalistic litterature, it can mainly be found in the field of evolutionnary computation, separate out the two other tendencies is more difficult.

Here are some definitions gathered in more or less generalistic papers:

"iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space" (Osman and Laporte, 1996^[3])

"(metaheuristics) combine basic heuristic methods in higher level frameworks aimed at efficiently and effectively exploring a search space" (Blum and Roli, 2003^[4])

"a metaheuristic can be seen as a general-purpose heuristic method designed to guide an underlying problem-specific heuristic (...) A metaheuristic is therefore a general algorithmic framework which can be applied to different optimization problems with relative few modifications to make them adapted to a specific problem." (Dorigo and Stützle, 2004^[5])

"(metaheuristics) apply to all kinds of problems (...) are, at least to some extent, stochastic (...) direct, i.e. they do not resort to the calculation of the gradients of the objective function (...) inspired by analogies: with physics, biology or ethology" (Dréo, Siarry, Petrowski and Taillard, 2006^[6])

One can summarize by enumerating the expected characteristics:

optimization algorithms,
with an iterative design,
combining low level heuristics,
aiming to tackle a large scale of "hard" problems.

As it is pointed out by the last reference, a large majority of metaheuristics (well, not to say all) use at least one stochastic (probabilistic) process and does not use more information than the solution and the associated value(s) of the objective function.

Talking about combining heuristics seems to be appropriate for Ant Colony Optimization, that specifically needs one (following Dorigo's point of vue), it can be less obvious for Evolutionnary Algorithms. One can consider that mutation, or even the method's strategy itself, is a heuristic, but isn't it too generalistic to be called a heuristic ?

If we forget the difficulty to demarcate what can be called a heuristic and what is the scope of the term meta, one can simply look at the use of the term among specialists. Despite the fact that the definition can be used in several fields (data mining, machine learning, etc.), the term is used for optimization algorithms. This is perhaps the best reason among others: the term permits to separate a research field from others, thus adding a little bit of marketing...

I would thus use this definition:

Metaheuristics are algorithms designed to tackle "hard" optimization problems, with the help of iterative stochastic processes. These methods are manipulating direct samples of the objective function, and can be applied to several problems without major changes in their design.

Notes

[1] A recurrent joke says that whatever is your new idea, it has already be written down by Glover

[2] Comput. & Ops. Res.Vol. 13, No.5, pp. 533-549, 1986

[3] Metaheuristic: A bibliography, Annals of Operations Research, vol. 63, pp. 513-623, 1996

[4] Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys, vol. 35, issue 3, 2003

[5] Ant Colony Optimization, MIT Press, 2004

[6] Metaheuristics for Hard Optimization, Springer, 2006

A new book about "stigmergic optimization"

nojhan — Tue, 22 Aug 2006 00:00:00 +0200

Springer has published a new book in their Studies in Computational Intelligence series.

Edited by Abraham, Grosan and Ramos, it covers "Stigmergic Optimization". Looking at the table of content, one can see that we talk about Ant Colony Optimization.

Of course, it also get onto the so-called swarm intelligence and self-organization, but also onto Particle Swarm Optimization, which is a method that gather more and more researchers these months.

Introductive bibliography to metaheuristics for hard optimization

nojhan — Wed, 02 Aug 2006 00:00:00 +0200

Note that this bibliography is quite old (2003) and aim french students.

If you need only one reference, this is (of course, because I'm one of the authors) this one :

Dréo, J. ; Petrowski, A. ; Taillard, E. ; Siarry, P. ; Metaheuristics for Hard Optimization Methods and Case Studies, Springer, 2006, XII, 369 p., 140 illus., Hardcover. ISBN: 3-540-23022-X

General

Books

Glover, F. W. ; Kochenberger, G. A. ; 2003 : Handbook of Metaheuristics, Kluwer Academic Publishers, International series in operations research and management science, Boston Hardbound.

Teghem, J. ; Pirlot, M. ; 2002 : Optimisation approchée en recherche opérationnelle. Recherches locales, réseaux neuronaux et satisfaction de contraintes, Hermès.

Pham, D.T. ; Karaboga, D. ; 2000 : Intelligent optimisation techniques. Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks, Springer.

Saït, S.M. ; Youssef, H. ; 1999 : Iterative computer algorithms with applications in engineering, IEEE Computer Society Press.

Reeves, C.R., 1995 : Modern Heuristic Techniques for Combinatorial Problems, Mc Graw-Hill, Advances topics in computer science.

Algorithms

Simulated Annealing

Books

Siarry, P.; Dreyfus, G. ; 1989 : La méthode du recuit simulé : théorie et applications, ESPCI -- IDSET, 10 rue Vauquelin, 75005 Paris.

Tabu Search

Books

Glover, F. ; Laguna, M. ; 1997 : Tabu search, Kluwer Academic Publishers, Dordrecht.

Articles

Glover, F. ; 1989 : Tabu search --- part I, ORSA Journal on Computing, vol. 1, 190--206.

Glover, F. ; 1990 : Tabu search --- part II, ORSA Journal on Computing, vol. 2, 4--32.

Evolutionary Algorithms (aka Genetic Algorithm)

Books

Baeck, T. ; Fogel, D. B. ; Michalewicz, Z. ; 2000 : Evolutionary computation 1: basic algorithms and operators, Institute of Physics Publishing.

Baeck, T. ; Fogel, D. B. ; Michalewicz, Z. ; 2000 : Evolutionary computation 2: advanced algorithms and operators, Institute of Physics Publishing.

Goldberg, D. E. ; 1994 : Algorithmes génétiques. exploration, optimisation et apprentissage automatique, Addison-Wesley France.

Koza, J. R. ; 1992 : Genetic programming I: on the programming of computers by means of natural selection, MIT Press.

Koza, J. R. ; 1994 : Genetic programming II: automatic discovery of reusable programs, MIT Press.

Ant Colony Algorithms

Books

Bonabeau, E. ; Dorigo, M. ; Theraulaz, G. ; 1999 : Swarm Intelligence, From Natural to Artificial Systems, Oxford University Press.

Greedy Randomized Adaptive Search Procedure (GRASP)

Tech Reports

Resende, M.G.C. ; 2000 : Greedy randomized adaptive search procedures (GRASP), AT&T Labs-Research, TR 98.41.1.

Partical Swarm Optimization

Books

Eberhart, R.C. ; Kennedy, J. ; Shi, Y. ; 2001 : Swarm Intelligence, Morgan Kaufmann, Evolutionnary Computation.

Estimation of Distribution Algorithms

Books

Larranaga, P. ; Lozano, J.A. ; 2002 : Estimation of Distribution Algorithms, A New Tool for Evolutionnary Computation, Kluwer Academic Publishers, Genetic Algorithms and Evolutionnary Computation.

Dreaming of Metaheuristics

An EDA in a few lines of python

Metaheuristic validation in a nutshell

A chronology of metaheuristics

Timeline

Detailled chronology

References

The problem with spreading new metaheuristics

Classification of metaheuristics

Hybridization : estimation of distribution as a meta-model filter generator for metaheuristics ?

Error metrics

Random draw in a sphere

Evolving Objects 1.0 is out

Random and learning

Metaheuristics and machine-learning

Metaheuristics and experimental research

Frameworks for metaheuristics

Favorites

Other

Confirmation of the biological foundations of particle swarm optimization

Finding references about metaheuristics (and computer science)

Metaheuristics & benchmarks at CEC

Some blogs about metaheuristics

What are metaheuristics ?

Notes

A new book about "stigmergic optimization"

Introductive bibliography to metaheuristics for hard optimization

General

Books

Algorithms

Simulated Annealing

Books

Tabu Search

Books

Articles

Evolutionary Algorithms (aka Genetic Algorithm)

Books

Ant Colony Algorithms

Books

Greedy Randomized Adaptive Search Procedure (GRASP)

Tech Reports

Partical Swarm Optimization

Books

Estimation of Distribution Algorithms

Books

Related Topics

Multi-Objective Optimization

Books

Constrainted Optimization

Books

Self-Organization

Books