Regular PapersNo Access

ADAPTIVE LEARNING SEARCH, A NEW TOOL TO HELP COMPREHENDING METAHEURISTICS

Université Paris XII Val-de-Marne, Laboratoire Images, Signaux et Systèmes Intelligents (LISSI, EA 3956), 61, avenue du Général de Gaulle, 94010 Créteil, France

Search for more papers by this author

JEAN-PHILIPPE AUMASSON

Security and Cryptography Laboratory, EPFL, Switzerland

Search for more papers by this author

WALID TFAILI

Université Paris XII Val-de-Marne, Laboratoire Images, Signaux et Systèmes Intelligents (LISSI, EA 3956), 61, avenue du Général de Gaulle, 94010 Créteil, France

Search for more papers by this author

, and

PATRICK SIARRY

Université Paris XII Val-de-Marne, Laboratoire Images, Signaux et Systèmes Intelligents (LISSI, EA 3956), 61, avenue du Général de Gaulle, 94010 Créteil, France

Search for more papers by this author

https://doi.org/10.1142/S0218213007003370Cited by:9 (Source: Crossref)

Abstract

The majority of the algorithms used to solve hard optimization problems today are population metaheuristics. These methods are often presented under a purely algorithmic angle, while insisting on the metaphors which led to their design. We propose in this article to regard population metaheuristics as methods making evolution a probabilistic sampling of the objective function, either explicitly, implicitly, or directly, via processes of learning, diversification, and intensification. We present a synthesis of some metaheuristics and their functioning seen under this angle, called Adaptive Learning Search. We discuss how to design metaheuristics following this approach, and propose an implementation with our Open Metaheuristics framework, along with concrete examples.

Keywords:

References

E. H. L. Aarts and P. J. M. Van Laarhoven, Philips Journal of Research 40, 193 (1985). Google Scholar
S. Baluja. Population-based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. Technical Report CMU-CS-94-163, Carnegie Mellon University, 1994 . Google Scholar
S. Baluja, Advances in Neural Information Processing Systems 9, 319 (1997). Google Scholar
S. Baluja and R. Caruana, Removing the Genetics from the Standard Genetic Algorithm, International Conference on Machine Learning, eds. A. Prieditis and S. Russel (Morgan Kaufmann) pp. 38–46. Google Scholar
S. Baluja and S. Davies , Fast probabilistic modeling for combinatorial optimization , Fifteenth National Conference on Artificial Intelligence, Tenth Conference on Innovative Applications of Artificial Intelligence ( Madison, Wisconsin ) . Google Scholar
P. A. N. Bosman and D. Thierens. An algorithmic framework for density estimation based evolutionary algorithm. Technical Report UU-CS-1999-46, Utrech University, 1999 . Google Scholar
P. A. N. Bosman and D. Thierens, Continuous iterated density estimation evolutionary algorithms within the IDEA framework, Proceedings of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Computation Conference GECCO-2000, eds. M. Muehlenbein and A. O. Rodriguez (Morgan Kauffmann, 2000) pp. 197–200. Google Scholar
P.A.N. Bosman and D. Thierens. IDEAs based on the normal kernels probability density function. Technical Report UU-CS-2000-11, Utrecht University, 2000 . Google Scholar
V. Cerny, J. of Optimization Theory and Applications 45(1), 41 (1985). Crossref, Web of Science, Google Scholar
A. Colorni, M. Dorigo and V. Maniezzo, Distributed Optimization by Ant Colonies, Proceedings of ECAL'91 - First European Conference on Artificial Life, eds. F. Varela and P. Bourgine (Elsevier Publishing, 1992) pp. 134–142. Google Scholar
M. Creutz, Physical Review Letters 50(19), 1411 (1983). Crossref, Web of Science, Google Scholar
P. M. C. De Oliveira. Broad Histogram : An Overview. arxiv :cond-mat/0003300v1, 2000 . Google Scholar
K. Deb and P. N. Suganthan, IEEE Congress on Evolutionary Computation (2005). Google Scholar
R. Dorne and C. Voudouris, Metaheuristics: computer decision-making (Kluwer Academic Publishers, Norwell, MA, USA, 2004) pp. 237–256. Google Scholar
J. Dréo, J.-Ph. Aumasson, and W. Tfaili. Open Metaheuristics. http://ometah.berlios.de, 2005 . Google Scholar
J. Dréo, J.-C. Nunes and P. Siarry, Computerized Medical Imaging and Graphics (2007), DOI: 10.1016/j.compmedimag.2006.07.004. Google Scholar
J. Dréo et al. , Retinal angiogram registration by estimation of distribution algorithm , 6th IFAC Symposium on Modelling and Control in Biomedical Systems (IFAC 2006) ( 2006 ) . Google Scholar
J. Dréo et al. , Metaheuristics for hard optimization ( Springer , 2006 ) . Google Scholar
J. E. Eiben and A. E. Smith , Introduction to Evolutionary Computing ( Springer Verlag , 2003 ) . Crossref, Google Scholar
A. M. Ferrenberg and R. H. Swendsen, Physical Review Letters 63, 1195 (1989). Crossref, Web of Science, Google Scholar
A. Fink and S. Voß, Computers and Industrial Engineering 37(1–2), 281 (1999). Crossref, Web of Science, Google Scholar
L. J. Fogel , A. J. Owens and M. J. Walsh , Artifical Intelligence through Simulated Evolution ( Wiley , 1966 ) . Google Scholar
E. Gamma et al. , Design Patterns: Elements of Reusable Object-Oriented Software , Addison-Wesley Professional Computing Series ( Addison Wesley Professional , 1994 ) . Google Scholar
Erich Gammaet al., Design patterns: Abstraction and reuse of object-oriented design, Lecture Notes in Computer Science 707 (1993) pp. 406–431. Crossref, Google Scholar
D. E. Goldberg , Genetic Algorithms in Search, Optimization and Machine learning ( Addison-Wesley , 1989 ) . Google Scholar
G. Harik. Linkage learning in via probabilistic modeling in the EcGA. Technical Report 99010, IlliGAL, 1999 . Google Scholar
G. Harik, F. G. Lobo and D. E. Goldberg, The compact genetic algorithm, IEEE Conference on Evolutionary Computation pp. 523–528. Google Scholar
W. K. Hastings, Biometrika 57, (1970). Google Scholar
J. H. Holland, J. Assoc. Comput. Mach. 3, 297 (1962). Google Scholar
K. Hukushima and K. Nemoto, Journal of the Physical Society of Japan 65, 1604 (1996). Crossref, Web of Science, Google Scholar
Y. Iba. Population Annealing: An approach to finite-temperature calculation. In Joint Workshop of Hayashibara Foundation and SMAPIP. Hayashibara Forum, 2003 . Google Scholar
M. Jenkinson and S. Smith, Medical Image Analysis 5, 143 (2001). Crossref, Web of Science, Google Scholar
M. Jones. An Object-Oriented Framework for the Implementation of Search Techniques. PhD thesis, University of East Anglia, 2000 . Google Scholar
Maarten Keijzeret al., Artificial Evolution 231 (2001). Google Scholar
J. Kertesz and I. Kondor (eds.) , Advances in Computer Simulation ( Springer-Verlag , 1998 ) . Crossref, Google Scholar
S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science 220(4598), 671 (1983). Crossref, Web of Science, Google Scholar
P. Larra˜naga and J. A. Lozano (eds.) , Estimation of Distribution Algorithms, A New Tool for Evolutionary Computation ( Kluwer Academic Publishers , 2002 ) . Crossref, Google Scholar
F. Liang and W. H. Wong, Statistica Sinica 10, (2000). Google Scholar
N. Metropoliset al., Journal of Chemical Physics 21, 1087 (1953). Crossref, Web of Science, Google Scholar
N. Monmarché, E. Ramat, G. Dromel, M. Slimane, and G. Venturini. On the similarities between AS, BSC and PBIL: toward the birth of a new meta-heuristics. E3i 215, Université de Tours, 1999 . Google Scholar
N. Monmarchéet al., Probabilistic search with genetic algorithms and ant colonies, Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop, ed. A. S. Wu pp. 209–211. Google Scholar
H. Mühlenbein and G. Paaß, Binary parameters, Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature (1996) pp. 178–187. Crossref, Google Scholar
J. A. Nelder and R. Mead, Computer Journal 7, 308 (1965). Crossref, Web of Science, Google Scholar
M. E. J. Newman and R. G. Palmer. Error estimation in the histogram Monte Carlo method., 1998 , arxiv:cond-mat/98043006 . Google Scholar
Y. Okamoto and U. H. E. Hansmann, Journal Physical Chemistry 99, 11276 (1995). Crossref, Web of Science, Google Scholar
I. Rechenberg , Cybernetic Solution Path of an Experimental Problem , Royal Aircraft Establishment Library Translation ( 1965 ) . Google Scholar
M.G.C. Resende. Greedy randomized adaptive search procedures (GRASP). Technical Report TR 98.41.1, AT&T Labs-Research, 2000 . Google Scholar
N. Ritteret al., IEEE Trans. On Medical Imaging 18, 404 (1999). Crossref, Web of Science, Google Scholar
J. Rumbaugh , I. Jacobson and G. Booch , The Unified Modeling Language Reference Manual ( Addison-Wesley , 1999 ) . Google Scholar
G. Syswerda, Simulated Crossover in Genetic Algorithms, Second workshop on Foundations of Genetic Algorithms, ed. L. D. Whitley (Morgan Kaufmann, 1993) pp. 239–255. Google Scholar
É. D. Taillard , A statistical test for comparing success rates , Metaheuristic international conference MIC'03 ( 2003 ) . Google Scholar
É. D. Taillardet al., European Journal of Operational Research 135(1), 1 (1998). Crossref, Web of Science, Google Scholar
E. Triki, Y. Collette and P. Siarry, European Journal of Operational Research 166, 77 (2005). Crossref, Web of Science, Google Scholar
D. Tschumperlé. Cimg library. Available at http://cimg.sourceforge.net/, 2005 . Google Scholar
S. Voß and D. L. Woodruff , Optimization Software Class Libraries , OR/CS Interfaces Series ( Kluwer , Dordrecht , 2002 ) . Crossref, Google Scholar
O. Wendt and W. König. Cooperative Simulated Annealing: How Much Cooperation is Enough ? Technical Report 97-19, Institute of Information Systems, Goethe University, Frankfurt, 1997 . Google Scholar