Abstract
Genetic type particle methods are increasingly used to sample from complex high-dimensional distributions. They have found a wide range of applications in applied probability, Bayesian statistics, information theory, and engineering sciences. Understanding rigorously these new Monte Carlo simulation tools leads to fascinating mathematics related to Feynman-Kac path integral theory and their interacting particle interpretations. In this chapter, we provide an introduction to the stochastic modeling and the theoretical analysis of these particle algorithms. We also illustrate these methods through several applications.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Genetic Algorithm
- Markov Chain Monte Carlo
- Evolutionary Computation
- Approximate Bayesian Computation
- Evolutionary Computing
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackley, D., Littman, M.: A case for lamarckian evolution. Artifical Life III: SFI studies in the sciences of complexity XVII, 3–10 (1993)
Alba, E., Luque, G.: Performance of Distributed GAs on DNA Fragment Assembly. In: Parallel Evolutionary Computations, pp. 97–116. Springer (2006)
Aldous, D., Vazirani, U.: Go with the winners algorithms. In: Proc. 35th Symp. Foundations of Computer Sci., pp. 492–501 (1994)
Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@home: an experiment in public-resource computing. Commun. ACM 45(11), 56–61 (2002)
Ashlock, D.A.: Evolutionary computation for modeling and optimization. Springer (2006)
Assaraf, R., Caffarel, M., Khelif, A.: Diffusion Monte Carlo methods with a fixed number of walkers. Phys. Rev. E 61, 4566–4575 (2000)
Bäck, T., Hoffmeister, F., Schwefel, H.P.: A survey of evolution strategies. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 2–9. Morgan Kaufmann (1991)
Bäck, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation. IOP Publishing Ltd., Bristol (1997)
Bäck, T., Hammel, U., Schwefel, H.P.: Evolutionary computation: comments on the history and current state. IEEE Trans. Evolutionary Computation 1(1), 3–17 (1997)
Barricelli, N.A.: Esempi numerici di processi di evoluzione. Methodos, 45–68 (1954)
Barricelli, N.A.: Symbiogenetic evolution processes realized by artificial methods. Methodos 9(35-36), 143–182 (1957)
Battiti, R., Brunato, M., Mascia, F.: Reactive Search and Intelligent Optimization. In: Operations Research/Computer Science Interfaces. Springer (2008) doi:10.1007/978-0-387-09624-7
Baum, E.B.: Towards practical ’neural’ computation for combinatorial optimization problems. In: AIP Conference Proceedings 151 on Neural Networks for Computing, pp. 53–58. American Institute of Physics Inc., Woodbury (1987), http://dl.acm.org/citation.cfm?id=24140.24150
Belew, R.K., Booker, L.B. (eds.): Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, San Diego (1991)
Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm intelligence: from natural to artificial systems. Oxford University Press, Inc., New York (1999)
Bremermann, H.J., Rogson, M., Salaff, S.: Global Properties of Evolution Processes. In: Pattee, H.H., Edlsack, E.A., Fein, L., Callahan, A.B. (eds.) Natural Automata and Useful Simulations, pp. 3–41. Spartan Books, Washington, DC (1966)
Broyden, C.G.: The Convergence of a Class of Double-rank Minimization Algorithms: 2. The New Algorithm. IMA Journal of Applied Mathematics 6(3), 222–231 (1970), http://imamat.oxfordjournals.org/cgi/content/abstract/6/3/222 , doi:10.1093/imamat/6.3.222
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.R.: A classification of hyper-heuristic approaches. Handbook of Metaheuristics 146, 1–21 (2010), http://www.springerlink.com/index/XXM7126130381913.pdf
Campillo, F., Rossi, V.: Convolution particle filtering for parameter estimation in general state-space models. In: Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, USA (2006)
Campillo, F., Rossi, V.: Convolution filter based methods for parameter estimation in general state-space models. IEEE Transactions on Aerospace and Electronic Systems 45(3), 1063–1071 (2009)
Cantu-Paz, E.: A survey of parallel genetic algorithms. Calculateurs Paralleles Reseaux et Systems Repartis 10(2), 141–171 (1998), http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=879173
Carpenter, J., Clifford, P., Fearnhead, P.: An improved particle filter for non-linear problems. IEE Proceedings F 146, 2–7 (1999)
Carvalho, H., Del Moral, P., Monin, A., Salut, G.: Optimal Non-linear Filtering in GPS/INS Integration. IEEE-Trans. on Aerospace and Electronic Systems 33(3), 835–850 (1997)
Cerf, R.: Asymptotic convergence of genetic algorithms. Adv. Appl. Probab. 30, 521–550 (1998)
Cérou, F., Del Moral, P., LeGland, F., Lezaud, P.: Limit Theorems for multilevel splitting algorithms in the simulation of rare events (preliminary version). In: Kuhl, M.E., Steiger, N.M., Armstrong, F.B., Joines, J.A. (eds.) Proceedings of the 2005 Winter Simulation Conference (2005)
Cérou, F., Del Moral, P., LeGland, F., Lezaud, P.: ALEA Lat. Am. J. Probab. Math. Stat. 1, 181–203 (2006)
Cérou, F., Del Moral, P., Guyader, A.: A non asymptotic variance theorem for unnormalized Feynman-Kac particle models. Technical Report HAL-INRIA RR-6716 (2008), Annales de l’Institut H. Poincaré, Série: Probabilités(B) 47(3) (2011)
Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Rare event simulation for a static distribution. Research Report RR-6792, INRIA (2009)
Chopin, N.: A sequential particle filter method for static models. Biometrika 89, 539–552 (2002)
Coello Coello, C.: List of references on evolutionary multiobjective optimization, http://www.lania.mx/~ccoello/EMOObib.html
Coello Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems. In: Genetic Algorithms and Evolutionary Computation, vol. 5. Kluwer Academic Publishers, Boston (2002)
Cole, N., Desell, T., Lombraña González, D., Fernández de Vega, F., Magdon-Ismail, M., Newberg, H., Szymanski, B., Varela, C.: Evolutionary Algorithms on Volunteer Computing Platforms: The MilkyWay@Home Project. In: de Vega, F.F., Cantú-Paz, E. (eds.) Parallel and Distributed Computational Intelligence. SCI, vol. 269, pp. 63–90. Springer, Heidelberg (2010)
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed Optimization by Ant Colonies. In: European Conference on Artificial Life, pp. 134–142 (1991)
Di Chio, C., Brabazon, A., Di Caro, G.A., Drechsler, R., Farooq, M., Grahl, J., Greenfield, G., Prins, C., Romero, J., Squillero, G., Tarantino, E., Tettamanzi, A.G.B., Urquhart, N., Uyar, A.Ş. (eds.): EvoApplications 2011, Part II. LNCS, vol. 6625. Springer, Heidelberg (2011)
De Castro, L.N., Timmis, J.: Artificial Immune Systems: A New Computational Intelligence Approach. Springer (2002), http://books.google.com/books?hl=en&lr=&id=aMFP7p8DtaQC&oi=fnd&pg=PA1&dq=Artificial+immune+systems+a+new+computational+intelligence+approach&ots=zHjlTG5TiP&sig=VKMxGqTe4FhtUai-ET3wdQ2mJ78
Del Moral, P.: Non Linear Filtering: Interacting Particle Solution. Markov Processes and Related Fields 2(4), 555–580 (1996)
Del Moral, P.: Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems. Annals of Applied Probability 8(2), 438–495 (1998)
Del Moral, P.: Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications. Springer, New York (2004)
Del Moral, P., Doucet, A.: Particle motions in absorbing medium with hard and soft obstacles. Stochastic Anal. Appl. 22, 1175–1207 (2004)
Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo samplers. J. Royal Statist. Soc. B 68, 411–436 (2006)
Del Moral, P., Doucet, A., Jasra, A.: On Adaptive Resampling Procedures for Sequential Monte Carlo Methods. Research Report INRIA (HAL-INRIA RR-6700), 46p. (October 2008); In: Bernoulli 18(1), 252–278 (2012)
Del Moral, P., Guionnet, A.: On the stability of measure valued processes with applications to filtering. C. R. Acad. Sci. Paris Sér. I Math. 329, 429–434 (1999)
Del Moral, P., Guionnet, A.: On the stability of interacting processes with applications to filtering and genetic algorithms. Annales de l’Institut Henri Poincaré 37(2), 155–194 (2001)
Del Moral, P., Jacod, J.: Interacting Particle Filtering With Discrete Observations. In: Doucet, A., de Freitas, J.F.G., Gordon, N.J. (eds.) Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science, pp. 43–77. Springer (2001)
Del Moral, P., Jacod, J., Protter, P.: The Monte-Carlo Method for filtering with discrete-time observations. Probability Theory and Related Fields 120, 346–368 (2001)
Del Moral, P., Jacod, J.: The Monte-Carlo Method for filtering with discrete time observations. Central Limit Theorems. In: Lyons, T.J., Salisbury, T.S. (eds.) The Fields Institute Communications, Numerical Methods and Stochastics. American Mathematical Society (2002)
Del Moral, P., Kallel, L., Rowe, J.: Modeling genetic algorithms with interacting particle systems. Revista de Matematica, Teoria y Aplicaciones 8(2) (July 2001)
Del Moral, P., Miclo, L.: Asymptotic Results for Genetic Algorithms with Applications to Non Linear Estimation. In: Naudts, B., Kallel, L. (eds.) Proceedings Second EvoNet Summer School on Theoretical Aspects of Evolutionary Computing. Natural Computing. Springer (2000)
Del Moral, P., Miclo, L.: On the Stability of Non Linear Semigroup of Feynman-Kac Type. Annales de la Faculté des Sciences de Toulouse 11(2), (2002)
Del Moral, P., Lezaud, P.: Branching and interacting particle interpretation of rare event probabilities. In: Blom, H., Lygeros, J. (eds.) Stochastic Hybrid Systems: Theory and Safety Critical Applications. Springer, Heidelberg (2006)
Del Moral, P., Miclo, L.: A Moran particle system approximation of Feynman-Kac formulae. Stochastic Processes and their Applications 86, 193–216 (2000)
Del Moral, P., Miclo, L.: Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to non linear filtering. In: Azéma, J., Emery, M., Ledoux, M., Yor, M. (eds.) Séminaire de Probabilités XXXIV. Lecture Notes in Mathematics, vol. 1729, pp. 1–145. Springer (2000)
Del Moral, P., Miclo, L.: Genealogies and Increasing Propagations of Chaos for Feynman-Kac and Genetic Models. Annals of Applied Probability 11(4), 1166–1198 (2001)
Del Moral, P., Miclo, L.: Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups. ESAIM: Probability and Statistics 7, 171–208 (2003)
Del Moral, P., Miclo, L.: Annealed Feynman-Kac models. Comm. Math. Phys. 235, 191–214 (2003)
Del Moral, P., Rémillard, B., Rubenthaler, S.: Introduction aux Probabilités. Ellipses Edition (2006)
Del Moral, P., Rio, E.: Concentration inequalities for mean field particle models. Technical report HAL-INRIA RR-6901 (2009). Annals of Applied Probability 21(3), 1017–1052 (2011)
Del Moral, P., Hu, P., Wu, L.: On the Concentration Properties of Interacting Particle Processes. Foundations and Trends in Machine Learning 3(3-4), 225–389 (2012)
Del Moral, P., Rigal, G., Salut, G.: Estimation and nonlinear optimal control: An unified framework for particle solutions LAAS-CNRS, Toulouse, Research Report no. 91137, DRET-DIGILOG- LAAS/CNRS contract (April 1991)
Del Moral, P., Rigal, G., Salut, G.: Nonlinear and non Gaussian particle filters applied to inertial platform repositioning. LAAS-CNRS, Toulouse, Research Report no. 92207, STCAN/DIGILOG-LAAS/CNRS Convention STCAN no. A.91.77.013, 94p. (September 1991)
Del Moral, P., Rigal, G., Salut, G.: Estimation and nonlinear optimal control: Particle resolution in filtering and estimation. Experimental results. Convention DRET no. 89.34.553.00.470.75.01, Research report no.2, 54p. (January 1992)
Del Moral, P., Rigal, G., Salut, G.: Estimation and nonlinear optimal control: Particle resolution in filtering and estimation. Theoretical results Convention DRET no. 89.34.553.00.470.75.01, Research report no.3, 123p. (October 1992)
Del Moral, P., Noyer, J.-C., Rigal, G., Salut, G.: Particle filters in radar signal processing: detection, estimation and air targets recognition. LAAS-CNRS, Toulouse, Research Report no. 92495 (December 1992)
Del Moral, P., Rigal, G., Salut, G.: Estimation and nonlinear optimal control: Particle resolution in filtering and estimation. Studies on: Filtering, optimal control, and maximum likelihood estimation. Convention DRET no. 89.34.553.00.470.75.01. Research report no.4, 210p. (January 1993)
Del Moral, P., Noyer, J.C., Rigal, G., Salut, G.: Traitement non-linéaire du signal par réseau particulaire: Application RADAR. In: Proceedings XIV Colloque GRETSI, Traitement du Signal et des Images, Juan les Pins, France, pp. 399–402 (September 1993)
Del Moral, P., Noyer, J.C., Salut, G.: Resolution particulaire et traitement non linéaire du signal: Application radar/sonar. Revue du Traitement du Signal (Septembre 1995)
Doucet, A., de Freitas, J.F.G., Gordon, N.J. (eds.): Sequential Monte Carlo Methods in Practice. Springer, New York (2001)
Doucet, A., Godsill, S.J., Andrieu, C.: On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing 10, 197–208 (2000)
Doucet, A., Johansen, A.M.: A tutorial on particle filtering and smoothing: fifteen years later. In: Crisan, D., Rozovsky, B. (eds.) Handbook of Nonlinear Filtering. Cambridge University Press (2009)
Eiben, A.E., Bäck, T.: Empirical investigation of multiparent recombination operators in evolution strategies. Evolutionary Computation 5(3), 347–365 (1997)
Eiben, A.E., Hinterding, R., Hinterding, A.E.E.R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3, 124–141 (2000)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer (2003)
Eiben, A., Schut, M.: New ways to calibrate evolutionary algorithms. In: Advances in Metaheuristics for Hard Optimization. Natural Computing, pp. 153–177. Springer (2008), http://dblp.uni-trier.de/db/conf/ncs/metaheuristics2008.html#EibenS08
Ellouze, M., Gauchi, J.P., Augustin, J.C.: Global sensitivity analysis applied to a contamination assessment model of Listeria monocytogenes in cold smoked salmon at consumption. Risk Anal. 30, 841–852 (2010)
Ellouze, M., Gauchi, J.P., Augustin, J.C.: Use of global sensitivity analysis in quantitative microbial risk assessment: Application to the evaluation of a biological time temperature integrator as a quality and safety indicator for cold smoked salmon. In: Food Microbiol. (2010), doi:10.1016/j.fm.2010.05.022
Fearnhead, P.: Computational methods for complex stochastic systems: A review of some alternatives to MCMC. Statistics and Computing 18, 151–171 (2008)
Fletcher, R., Powell, M.: A rapidly convergent descent method for minimization. Computer Journal 6, 163–168 (1963)
Fletcher, R., Reeves, C.: Function minimization by conjugate gradients. Computer Journal 7, 149–154 (1964)
Fletcher, R.: A new approach to variable metric algorithms. The Computer Journal 13(3), 317–322 (1970), http://comjnl.oxfordjournals.org/cgi/content/abstract/13/3/317 , doi:10.1093/comjnl/13.3.317
Gauchi, J.P., Vila, J.P., Coroller, L.: New prediction confidence intervals and bands in the nonlinear regression model: Application to the predictive modelling in food. Communications in Statistics, Simulation and Computation 39(2), 322–330 (2009)
Gauchi, J.P., Bidot, C., Augustin, J.C., Vila, J.P.: Identification of complex microbiological dynamic system by nonlinear filtering. In: 6th Int. Conference on Predictive Modelling in Foods, Washington DC (2009)
Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: Multilevel splitting for estimating rare event probabilities. Operations Research 47, 585–600 (1999)
Glover, F.: Heuristics for integer programming using surrogate constraints. Decision Sciences 8(1), 156–166 (1977), http://dx.doi.org/10.1111/j.1540-5915.1977.tb01074.x , doi:10.1111/j.1540-5915.1977.tb01074.x
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986), http://dx.doi.org/10.1016/0305-05488690048-1 , doi:10.1016/0305-0548(86)90048-1
Glover, F.: A template for scatter search and path relinking. In: Hao et al. [93], pp. 1–51 (1997)
Glynn, P.W., Ormoneit, D.: Hoeffding’s inequality for uniformly ergodic Markov chains. Statist. Probab. Lett. 56(2), 143–146 (2002)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989)
Goldfarb, D.: A family of variable metric updates derived by variational means. Mathematics of Computation 24, 23–26 (1970)
Gordon, N.J., Salmond, D., Smith, A.F.M.: A novel approach to state estimation to nonlinear non-Gaussian state estimation. IEE Proceedings F 40, 107–113 (1993)
Grassberger, P.: Pruned-enriched Rosenbluth method: Simulations of θ polymers of chain length up to 1 000 000. Phys. Rev. E, 3682–3693 (1997)
Hansen, N., Müller, S.D., Koumoutsakos, P.: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11(1), 1–18 (2003), http://dx.doi.org/10.1162/106365603321828970 , doi:10.1162/106365603321828970
Hansen, N., Ostermeier, A., Gawelczyk, A.: On the adaptation of arbitrary normal mutation distributions in evolution strategies: The generating set adaptation. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 57–64. Morgan Kaufmann Publishers Inc., San Francisco (1995), http://dl.acm.org/citation.cfm?id=645514.657936
Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.): AE 1997. LNCS, vol. 1363. Springer, Heidelberg (1998)
Harris, T.E., Kahn, H.: Estimation of particle transmission by random sampling. Natl. Bur. Stand. Appl. Math. Ser. 12, 27–30 (1951)
Herrera, F., Lozano, M.: Heuristic Crossovers for Real-Coded Genetic Algorithms Based on Fuzzy Connectives. In: Ebeling, W., Rechenberg, I., Voigt, H.-M., Schwefel, H.-P. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 336–345. Springer, Heidelberg (1996), http://www.springerlink.com/content/y42m98n165872533 , doi:10.1007/3-540-61723-X_998
Herrera, F., Lozano, M., Sánchez, A.M.: A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study. Int. J. Intell. Syst. 18(3), 309–338 (2003), http://dx.doi.org/10.1002/int.10091 , doi:10.1002/int.10091
Herrera, F., Lozano, M., Verdegay, J.: Fuzzy connective based crossover operators to model genetic algorithms population diversity. Tech. Rep. DECSAI-95110. University of Granada, Spain (1995)
Herrera, F., Lozano, M., Verdegay, J.: Dynamic and heuristic fuzzy connectives-based crossover operators for controlling the diversity and convergence of real-coded genetic algorithms. Int. J. Intell. Syst. 11, 1013–1041 (1996)
Herrera, F., Lozano, M., Verdegay, J.: Fuzzy connectives based crossover operators to model genetic algorithms population diversity. Fuzzy Set. Syst. 92(1), 21–30 (1997), doi:10.1016/S0165-0114(96)00179-0
Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Research NBS 49(6), 409–436 (1952)
Hestenes, M.R.: Iterative methods for solving linear equations. Report 52-9, NAML (1951); reprinted in J. Optimiz. Theory App. 11, 323–334 (1973)
Hetherington, J.H.: Observations on the Statistical Iteration of Matrices. Phys. Rev. A. 30, 2713–2719 (1984)
Hinterding, R., Michalewicz, Z., Eiben, A.E.: Adaptation in Evolutionary Computation: A Survey. In: Proceedings of the 4th IEEE International Conference on Evolutionary Computation, pp. 65–69 (1997), http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=592270
Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)
Hooke, R., Jeeves, T.: Direct search solution of numerical and statistical problems. Journal of the ACM 8(2), 212–229 (1961), doi: http://doi.acm.org/10.1145/321062.321069
Horn, J.: Multicriteria decision making and evolutionary computation. In: Handbook of Evolutionary Computation, Institute of Physics Publishing, London (1997)
Ikonen, E., Del Moral, P., Najim, K.: A genealogical decision tree solution to optimal control problems. In: IFAC Workshop on Advanced Fuzzy/Neural Control, Oulu, Finland, pp. 169–174 (2004)
Ikonen, E., Najim, K., Del Moral, P.: Application of genealogical decision trees for open-loop tracking control. In: Proceedings of the16th IFAC World Congress, Prague, Czech (2005)
Ingber, L.: Adaptive simulated annealing (asa), global optimization c-code. Tech. rep. Caltech Alumni Association (1993)
Ingber, L.: Simulated annealing: Practice versus theory. Math. Comput. Model. 18(11), 29–57 (1993)
Ingber, L.: Adaptive simulated annealing (asa): Lessons learned. Control and Cybern. 25, 33–54 (1996)
Ingber, L.: Adaptive simulated annealing (asa) and path-integral (pathint) algorithms: Generic tools for complex systems. Tech. rep. Chicago, IL (2001)
Ingber, L., Rosen, B.: Genetic algorithms and very fast simulated reannealing: A comparison. Math. Comput. Model. 16(11), 87–100 (1992)
Johansen, A.M., Del Moral, P., Doucet, A.: Sequential Monte Carlo Samplers for Rare Events. In: Proceedings of 6th International Workshop on Rare Event Simulation, Bamberg, Germany (2006)
Jong, K.A.D.: Evolutionary computation - a unified approach. MIT Press (2006)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995), doi:10.1109/ICNN.1995.488968
Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983), citeseer.ist.psu.edu/kirkpatrick83optimization.html
Kitagawa, G.: Monte Carlo filter and smoother for non-Gaussian nonlinear state space models. J. Comp. Graph. Statist. 5, 1–25 (1996)
Kolokoltsov, V.N., Maslov, V.P.: Idempotent analysis and its applications. Mathematics and its Applications, vol. 401. Kluwer Academic Publishers Group, Dordrecht (1997); Translation of Idempotent analysis and its application in optimal control, Russian, Nauka Moscow (1994); translated by Nazaikinskii, V. E. With an appendix by Pierre Del Moral : Maslov Optimization Theory: Optimality Versus Randomness, pp. 243–302
Künsch, H.R.: State-space and hidden Markov models. In: Barndorff-Nielsen, O.E., Cox, D.R., Kluppelberg, C. (eds.) Complex Stochastic Systems, pp. 109–173. CRC Press (2001)
Lagarias, J., Reeds, J., Wright, M., Wright, P.: Convergence properties of the Nelder-Mead simplex algorithm in low dimensions. SIAM J. Optimiz. 9, 112–147 (1998)
Langdon, W., Poli, R.: Foundations of Genetic Programming, vol. 5. Springer (2002), http://discovery.ucl.ac.uk/124583/
Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2001)
Martin, O., Otto, S.W., Felten, E.W.: Large-step markov chains for the traveling salesman problem. Complex Systems 5, 299–326 (1991)
Melik-Alaverdian, V., Nightingale, M.P.: Quantum Monte Carlo methods in statistical mechanics. Internat. J. of Modern Phys. C. 10, 1409–1418 (1999)
Metropolis, N., Ulam, S.: The Monte Carlo Method. Journal of the American Statistical Association 44(247), 335–341 (1949)
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953), http://link.aip.org/link/?JCP/21/1087/1 , doi:10.1063/1.1699114
Michalewicz, Z.: Genetic algorithms + data structures = evolution programs, 2nd, extended edn. Springer-Verlag New York, Inc., New York (1994)
Mitavskiy, B., Rowe, J.: An Extension of Geiringer’s Theorem for a Wide Class of Evolutionary Search Algorithms. Evolutionary Computation 14(1), 87–118 (2006)
Mitavskiy, B., Rowe, J., Wright, A., Schmitt, L.: Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm. Genetic Programming and Evolvable Machines 9(2), 109–123 (2008)
Mladenović, N.: A variable neighborhood algorithm – a new metaheuristics for combinatorial optimization. In: Abstracts of Papers Presented at Optimization Days, Montreal (1995)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997), http://dx.doi.org/10.1016/S0305-05489700031-2 , doi:10.1016/S0305-0548(97)00031-2
Moscato, P.: Memetic algorithms: a short introduction. In: Corne, D., Dorigo, M., Glover, F., Dasgupta, D., Moscato, P., Poli, R., Price, K. (eds.) New Ideas in Optimization, pp. 219–234. McGraw-Hill Ltd., UK (1999), http://dl.acm.org/citation.cfm?id=329055.329078
Mühlenbein, H., Schlierkamp-Voosen, D.: Analysis of selection, mutation and recombination in genetic algorithms. Evolution and Biocomputation, 142–168 (1995)
Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7(4), 308–313 (1965), http://comjnl.oxfordjournals.org/cgi/content/abstract/7/4/308 , doi:10.1093/comjnl/7.4.308
Neri, F., Cotta, C., Moscato, P.: Handbook of Memetic Algorithms. SCI. Springer (2011), http://books.google.lu/books?id=uop6UvKu8q4C
Nocedal, J.: Updating quasi-newton matrices with limited storage. Math. Comput. 35(151), 773–782 (1980), http://www.jstor.org/stable/2006193
Pelikan, M., Goldberg, D.E., Lobo, F.G.: A survey of optimization by building and using probabilistic models. Comput. Optim. Appl. 21(1), 5–20 (2002), http://dx.doi.org/10.1023/A:1013500812258 , doi:10.1023/A:1013500812258
Polak, E., Ribière, G.: Note sur la convergence des méthodes de directions conjuguées. Revue Française d’informatique et de Recherche Opérationnelle 16, 35–43 (1969)
Powell, M.: On the Convergence of the Variable Metric Algorithm. Journal of the Institute of Mathematics and its Applications 7, 21–36 (1971)
Rao, S., Shanta, C.: Numerical Methods: With Program in Basic, Fortan, Pascal & C++. Orient Blackswan (2004)
Reynolds, R.G., Sverdlik, W.: Problem solving using cultural algorithms. In: International Conference on Evolutionary Computation, pp. 645–650 (1994)
Rosenbluth, M.N., Rosenbluth, A.W.: Monte-Carlo calculations of the average extension of macromolecular chains. J. Chem. Phys. 23, 356–359 (1955)
Vila, J.-P., Rossi, V.: Nonlinear filtering in discret time: A particle convolution approach. Biostatistic Group of Montpellier, Technical Report 04-03 (2004), http://vrossi.free.fr/recherche.html
Rudolph, G.: Convergence of Evolutionary Algorithms in General Search Spaces. In: International Conference on Evolutionary Computation, pp. 50–54 (1996)
Rudolph, G.: Finite Markov Chain Results in Evolutionary Computation: A Tour d’Horizon. Fundam. Inform. 35(1-4), 67–89 (1998)
Schmitt, F., Rothlauf, F.: On the Importance of the Second Largest Eigenvalue on the Convergence Rate of Genetic Algorithms. In: Beyer, H., Cantu-Paz, E., Goldberg, D., Parmee, Spector, L., Whitley, D. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pp. 559–564. Morgan Kaufmann Publishers, San Francisco (2001)
Schwefel, H.P., Rudolph, G.: Contemporary Evolution Strategies. In: Morán, F., Merelo, J.J., Moreno, A., Chacon, P. (eds.) ECAL 1995. LNCS, vol. 929, pp. 893–907. Springer, Heidelberg (1995)
Shanno, D.: Conditioning of quasi-newton methods for function minimization. Math. Comput. 24(111), 647–656 (1970)
Shewchuk, J.: An introduction to the conjugate gradient method without the agonizing pain. Tech. rep., Carnegie Mellon University, Pittsburgh, Pittsburgh, PA, USA (1994), http://portal.acm.org/citation.cfm?id=865018
Solis, F., Wets, R.B.: Minimization by random search techniques. Math. Oper. Res. 6, 19–30 (1981)
Spears, W.M., Jong, K.A.D., Ba, T., Fogel, D.B., Garis, H.D.: An overview of evolutionary computation. Evolutionary Computation 667(1), 442–459 (1993), http://www.springerlink.com/index/Y03055H012777681.pdf
Spendley, W., Hext, G., Himsworth, F.: Sequential application of simplex designs in optimisation and evolutionary operation. Technometrics 4(4), 441–461 (1962)
Stadler, P.: Towards a theory of landscapes. In: Lopéz-Peña, R., Capovilla, R., García-Pelayo, R., Waelbroeck, H., Zertuche, F. (eds.) Complex Systems and Binary Networks, vol. 461, pp. 77–163. Springer, Berlin (1995)
Stadler, P., Flamm, C.: Barrier trees on poset-valued landscapes. Genet. Program. Evol. M. 4(1), 7–20 (2003), http://dblp.uni-trier.de/db/journals/gpem/gpem4.html%5c#StadlerF03
Stewart, C.A., Mueller, M.S., Lingwall, M.: Progress Towards Petascale Applications in Biology: Status in 2006. In: Lehner, W., Meyer, N., Streit, A., Stewart, C. (eds.) Euro-Par Workshops 2006. LNCS, vol. 4375, pp. 289–303. Springer, Heidelberg (2007), http://dl.acm.org/citation.cfm?id=1765606.1765638
Storn, R., Price, K.: Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. J. of Global Optimization 11(4), 341–359 (1997), http://dx.doi.org/10.1023/A:1008202821328 , doi:10.1023/A:1008202821328
Surhone, L.M., Tennoe, M.T., Henssonow, S.F.: Leiden Classical. VDM Verlag Dr. Mueller AG & Company Kg (2010)
Tantar, E., Dhaenens, C., Figueira, J.R., Talbi, E.G.: A priori landscape analysis in guiding interactive multi-objective metaheuristics. In: IEEE Congress on Evolutionary Computation, pp. 4104–4111 (2008)
Tantar, E., Schuetze, O., Figueira, J.R., Coello, C.A.C., Talbi, E.G.: Computing and selecting epsilon-efficient solutions of 0,1-knapsack problems. In: Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems. Lecture Notes in Econom. and Math. Systems, vol. 634, pp. 379–387 (2010)
Tsang, E., Voudouris, C.: Fast local search and guided local search and their application to British Telecom’s workforce scheduling problem. Oper. Res. Lett. 20(3), 119–127 (1997), http://www.sciencedirect.com/science/article/pii/S0167637796000429 , doi:10.1016/s0167-6377(96)00042-9
Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325–336 (1990), http://dx.doi.org/10.1007/BF00202749 , doi:10.1007/BF00202749
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Berlin Heidelberg
About this chapter
Cite this chapter
Del Moral, P., Tantar, AA., Tantar, E. (2013). On the Foundations and the Applications of Evolutionary Computing. In: Tantar, E., et al. EVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation. Studies in Computational Intelligence, vol 447. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32726-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-32726-1_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32725-4
Online ISBN: 978-3-642-32726-1
eBook Packages: EngineeringEngineering (R0)