Parallel Problem Solving from Nature

Last updated
Parallel Problem Solving from Nature
StudentHelpersReady4PPSN 20160917 095300.jpg
Student helpers ready for PPSN 2016 in Edinburgh
StatusActive
GenreConference
FrequencyBiennially
Years active34
Inaugurated1990 (1990)
FoundersBernard Manderick, Reinhard Männer, Heinz Mühlenbein and Hans-Paul Schwefel
Most recent2020
Next event2022
AreaEurope
Website https://ppsn2022.cs.tu-dortmund.de/

Parallel Problem Solving from Nature, or PPSN, is a research conference focusing on the topic of natural computing.

Contents

Other conferences in the area include the ACM Genetic and Evolutionary Computation Conference (GECCO), the IEEE Congress on Evolutionary Computation (CEC) and EvoStar (Evo*).

In 2020 PPSN got a CORE rank of A, [1] corresponding to an "excellent conference, and highly respected in a discipline area". [2]

History

The idea behind PPSN emerged around 1989-1990 when Bernard Manderick, Reinhard Männer, Heinz Mühlenbein, and Hans-Paul Schwefel, realised they shared a common field of study that was not covered by the conferences on Operations Research, Physics, or Computer Science they attended regularly. [3]

The field of Genetic Algorithms had already been established in the form of the ICGA conference in 1985, but the "fathers" of PPSN wanted a wider focus, with algorithms that included problem solving, parallel computing and the use of natural metaphors (such as Darwinian evolution or Boltzmann dynamics).

The success of the first PPSN event at Dortmund encouraged its organisers to start a biennial conference series, as a European counterpart to the American-based ICGA (which in 1999 merged with the Genetic Programming conference to give rise to GECCO).

Analogies to natural processes included the thermodynamic process of annealing, immune systems and neural networks, as well as other paradigms, with Darwinian evolution being by far the most frequently used metaphor.

In this way, evolutionary algorithms and evolutionary computation became the common denominator for the PPSN approach to problem solving by mimicking evolutionary principles like population, birth and death, mutation, recombination, and natural selection.

Editions

So far, seventeen PPSN conferences have been held: Dortmund (October 1–3, 1990), Brussels (September 28–30, 1992), Jerusalem (October 9–14, 1994), Berlin (September 22–26, 1996), Amsterdam (September 27–30, 1998), Paris (September 16–20, 2000), Granada (September 7–11, 2002), Birmingham (September 18–22, 2004), Reykjavik (September 9–13, 2006), Dortmund (September 13–17, 2008), Krakow (September 11–15, 2010), Taormina (Sicily) (September 1–5, 2012), Ljubljana (September 13–17, 2014), Edinburgh (September 17–21, 2016), Coimbra (September 8–12, 2018) Leiden (September 5–9, 2020), Dortmund (September 10-14, 2022), and Hagenberg (September 14-18, 2024).

The last-but-one edition, held in Leiden, counted on Thomas Bäck and Mike Preuss as General Chairs and Carola Doerr, Michael Emmerich and Heike Trautmann as Programme Committee Chairs. André Deutz and Hao Wang were Proceedings Chairs and Anna Esparcia-Alcázar, Ofer Shir and Vanessa Volz were Workshops, Tutorials and Competitions Chairs, respectively; Anna Kononova was Local Chair.

Proceedings

Proceedings of PPSN have been historically published by Springer in the Lecture Notes in Computer Science (LNCS) series (except in the second edition in 1992).

Keynote speakers

1998 Grzegorz Rozenberg, Nicholas Gessler, and Lawrence Davis 2000 Aaron Sloman, Luc Steels and Henrik Hautop Lund2002 Alexander Nareyek, Roderic Guigó and William Hart2004 Mandyam V. Srinivasan, Benjamin W. Wah and C. Lee Giles
2006 Herschel Rabitz, Nadia Busi, and Edward Tsang 2008 Levent Tunçel, Thomas Breitling and Arndt von Haeseler 2010 Jon Garibaldi, Zbigniew Michalewicz and Darrell Whitley2012 Angelo Cangelosi, Natalio Krasnogor, Panos M. Pardalos, and Leslie G. Valiant
2014 Jadran Lenarčič, Thomas Bäck, A. E. (Gusz) Eiben,2016 Susan Stepney, Josh Bongard and Andrew Philippides2018 Ahmed Elgammal, Francis Heylighen and Kurt Mehlhorn 2020 Eric Postma, Carme Torras and Christian Stöcker

Related Research Articles

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Evolutionary computation</span> Trial and error problem solvers with a metaheuristic or stochastic optimization character

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks (ANN), parameters, and rules. It is most commonly applied in artificial life, general game playing and evolutionary robotics. The main benefit is that neuroevolution can be applied more widely than supervised learning algorithms, which require a syllabus of correct input-output pairs. In contrast, neuroevolution requires only a measure of a network's performance at a task. For example, the outcome of a game can be easily measured without providing labeled examples of desired strategies. Neuroevolution is commonly used as part of the reinforcement learning paradigm, and it can be contrasted with conventional deep learning techniques that use backpropagation with a fixed topology.

In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population, and is analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions may be mutated before being added to the population.

In computer science, an evolution strategy (ES) is an optimization technique based on ideas of evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.

In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involving real numbers, integers, and/or various data structures such as lists, arrays, bit vectors, and strings. The name is derived from the fact that these expressions are interpreted within ("modulo") a certain formal theory in first-order logic with equality. SMT solvers are tools that aim to solve the SMT problem for a practical subset of inputs. SMT solvers such as Z3 and cvc5 have been used as a building block for a wide range of applications across computer science, including in automated theorem proving, program analysis, program verification, and software testing.

In computer science, the International Conference on Computer-Aided Verification (CAV) is an annual academic conference on the theory and practice of computer-aided formal analysis of software and hardware systems, broadly known as formal methods. Among the important results originally published in CAV are techniques in model checking, such as Counterexample-Guided Abstraction Refinement (CEGAR) and partial order reduction. It is often ranked among the top conferences in computer science.

<span class="mw-page-title-main">Hans-Paul Schwefel</span> German computer scientist

Hans-Paul Schwefel is a German computer scientist and professor emeritus at University of Dortmund, where he held the chair of systems analysis from 1985 until 2006. He is one of the pioneers in evolutionary computation and one of the authors responsible for the evolution strategies (Evolutionsstrategien). His work has helped to understand the dynamics of evolutionary algorithms and to put evolutionary computation on formal grounds.

<span class="mw-page-title-main">HyperNEAT</span>

Hypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks (ANNs) with the principles of the widely used NeuroEvolution of Augmented Topologies (NEAT) algorithm developed by Kenneth Stanley. It is a novel technique for evolving large-scale neural networks using the geometric regularities of the task domain. It uses Compositional Pattern Producing Networks (CPPNs), which are used to generate the images for Picbreeder.orgArchived 2011-07-25 at the Wayback Machine and shapes for EndlessForms.comArchived 2018-11-14 at the Wayback Machine. HyperNEAT has recently been extended to also evolve plastic ANNs and to evolve the location of every neuron in the network.

<span class="mw-page-title-main">Rastrigin function</span> Function used as a performance test problem for optimization algorithms

In mathematical optimization, the Rastrigin function is a non-convex function used as a performance test problem for optimization algorithms. It is a typical example of non-linear multimodal function. It was first proposed in 1974 by Rastrigin as a 2-dimensional function and has been generalized by Rudolph. The generalized version was popularized by Hoffmeister & Bäck and Mühlenbein et al. Finding the minimum of this function is a fairly difficult problem due to its large search space and its large number of local minima.

RP, the International Conference on Reachability Problems is an annual academic conference in the field of computer science.

The Extended Semantic Web Conference, formerly known as the European Semantic Web Conference, is a yearly international academic conference on the topic of the Semantic Web. The event began in 2004, as the European Semantic Web Symposium. The goal of the event is "to bring together researchers and practitioners dealing with different aspects of semantics on the Web".

The International Conference on Service Oriented Computing, short ICSOC, is an annual conference providing an outstanding forum for academics, industry researchers, developers, and practitioners to report and share groundbreaking work in service-oriented computing. ICSOC has an 'A' rating from the Excellence in Research in Australia (ERA). Calls for Papers are regularly published on WikiCFP and on the conference website. The conference is also listed in Elsevier's Global Events List.

<span class="mw-page-title-main">EvoStar</span> International evolutionary computation event

EvoStar, or Evo*, is an international scientific event devoted to evolutionary computation held in Europe. Its structure has evolved over time and it currently comprises four conferences: EuroGP the annual conference on Genetic Programming, EvoApplications, the International Conference on the Applications of Evolutionary Computation, EvoCOP, European Conference on Evolutionary Computation in Combinatorial Optimisation, and EvoMUSART, the International Conference on Computational Intelligence in Music, Sound, Art and Design. According to a 2016 study EvoApplications is a Q1 conference, while EuroGP and EvoCOP are both Q2. In 2021, EuroGP, EvoApplications and EvoCOP obtained a CORE rank B.

The biennial Artificial Evolution (AE) conference is held in France every two years, in early fall. The Parallel Problem Solving from Nature (PPSN) conference is held at the same period, but even years. EA is dedicated to techniques that simulate natural evolution. Proceedings of AE are published by Springer-Verlag in their LNCS serie.

The population model of an evolutionary algorithm (EA) describes the structural properties of its population to which its members are subject. A population is the set of all proposed solutions of an EA considered in one iteration, which are also called individuals according to the biological role model. The individuals of a population can generate further individuals as offspring with the help of the genetic operators of the procedure.

In computer science and mathematical logic, Cooperating Validity Checker (CVC) is a family of satisfiability modulo theories (SMT) solvers. The latest major versions of CVC are CVC4 and CVC5 ; earlier versions include CVC, CVC Lite, and CVC3. Both CVC4 and cvc5 support the SMT-LIB and TPTP input formats for solving SMT problems, and the SyGuS-IF format for program synthesis. Both CVC4 and cvc5 can output proofs that can be independently checked in the LFSC format, cvc5 additionally supports the Alethe and Lean 4 formats. cvc5 has bindings for C++, Python, and Java.

Constrained Horn clauses (CHCs) are a fragment of first-order logic with applications to program verification and synthesis. Constrained Horn clauses can be seen as a form of constraint logic programming.

References

  1. ↑ Parallel Problem Solving from Nature, CORE Conference Portal, http://portal.core.edu.au/conf-ranks/1676/ [accessed Nov 8 2020]
  2. ↑ CORE Conference Ranking, https://www.core.edu.au/conference-portal [accessed Nov 8 2020]
  3. ↑ Günter Rudolph's PPSN page at TU Dortmund, https://ls11-www.cs.tu-dortmund.de/rudolph/ppsn [accessed Jul 24 2020]
  4. ↑ Parallel Problem Solving from Nature – PPSN XVIII 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14–18, 2024, Proceedings, Part I. Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tušar, Penousal Machado, Thomas Bäck (Eds). Lecture Notes in Computer Science 15148, 2024, ISBN   978-3-031-70054-5, doi:10.1007/978-3-031-70055-2
  5. ↑ Parallel Problem Solving from Nature – PPSN XVIII 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14–18, 2024, Proceedings, Part II. Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tušar, Penousal Machado, Thomas Bäck (Eds). Lecture Notes in Computer Science 15149, 2024, ISBN   978-3-031-70067-5, doi:10.1007/978-3-031-70068-2
  6. ↑ Parallel Problem Solving from Nature – PPSN XVIII 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14–18, 2024, Proceedings, Part III. Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tušar, Penousal Machado, Thomas Bäck (Eds). Lecture Notes in Computer Science 15150, 2024, ISBN   978-3-031-70070-5, doi:10.1007/978-3-031-70071-2
  7. ↑ Parallel Problem Solving from Nature – PPSN XVIII 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14–18, 2024, Proceedings, Part I. Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Heike Trautmann, Tea Tušar, Penousal Machado, Thomas Bäck (Eds). Lecture Notes in Computer Science 15151, 2024, ISBN   978-3-031-70084-2, doi:10.1007/978-3-031-70085-9
  8. ↑ Parallel Problem Solving from Nature – PPSN XVI 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5–9, 2020, Proceedings, Part I. Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, Heike Trautmann (Eds). Lecture Notes in Computer Science 12269, 2020, ISBN   978-3-030-58112-1, doi:10.1007/978-3-030-58112-1
  9. ↑ Parallel Problem Solving from Nature – PPSN XVI 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5–9, 2020, Proceedings, Part II. Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, Heike Trautmann (Eds). Lecture Notes in Computer Science 12270, 2020, ISBN   978-3-030-58111-4, doi:10.1007/978-3-030-58115-2
  10. ↑ Parallel Problem Solving from Nature – PPSN XV. 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I. Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, Darrell Whitley (Eds). Lecture Notes in Computer Science 11101, 2018, ISBN   978-3-319-99252-5, doi:10.1007/978-3-319-99253-2
  11. ↑ Parallel Problem Solving from Nature – PPSN XV. 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II. Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, Darrell Whitley (Eds). Lecture Notes in Computer Science 11102, 2018, ISBN   978-3-319-99258-7, doi:10.1007/978-3-319-99259-4
  12. ↑ Parallel Problem Solving from Nature – PPSN XIV 14th International Conference, Edinburgh, UK, September 17–21, 2016, Proceedings. Julia Handl, Emma Hart, Peter R. Lewis, Manuel López-Ibáñez, Gabriela Ochoa, Ben Paechter (Eds). Lecture Notes in Computer Science 9921, 2016, ISBN   978-3-319-45822-9 doi:10.1007/978-3-319-45823-6
  13. ↑ Parallel Problem Solving from Nature – PPSN XIII 13th International Conference, Ljubljana, Slovenia, September 13–17, 2014. Proceedings. Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, Jim Smith (Eds). Lecture Notes in Computer Science book series 8672, 2014, ISBN   978-3-319-10761-5 doi:10.1007/978-3-319-10762-2
  14. ↑ Parallel Problem Solving from Nature - PPSN XII, 12th International Conference, Taormina, Italy, September 1–5, 2012, Proceedings, Part I. Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, Mario Pavone (Eds). Lecture Notes in Computer Science 7491, 2012, ISBN   978-3-642-32936-4 doi:10.1007/978-3-642-32937-1
  15. ↑ Parallel Problem Solving from Nature - PPSN XII, 12th International Conference, Taormina, Italy, September 1–5, 2012, Proceedings, Part II. Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, Mario Pavone (Eds). Lecture Notes in Computer Science 7492, 2012 ISBN   978-3-642-32963-0 doi:10.1007/978-3-642-32937-1
  16. ↑ Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, Kraków, Poland, September 11–15, 2010, Proceedings, Part I. Robert Schaefer, Carlos Cotta, Joanna Kolodziej, Günter Rudolph (Eds). Lecture Notes in Computer Science 6238, Springer 2010, ISBN   978-3-642-15843-8
  17. ↑ Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, Kraków, Poland, September 11–15, 2010, Proceedings, Part I. Robert Schaefer, Carlos Cotta, Joanna Kolodziej, Günter Rudolph (Eds). Lecture Notes in Computer Science 6239, Springer 2010, ISBN   978-3-642-15870-4
  18. ↑ Parallel Problem Solving from Nature - PPSN X, 10th International Conference Dortmund, Germany, September 13–17, 2008, Proceedings. Günter Rudolph, Thomas Jansen, Simon M. Lucas, Carlo Poloni, Nicola Beume (Eds.). Lecture Notes in Computer Science 5199, Springer 2008, ISBN   978-3-540-87699-1
  19. ↑ Parallel Problem Solving from Nature - PPSN IX, 9th International Conference, Reykjavik, Iceland, September 9–13, 2006, Proceedings. Thomas Philip Runarsson, Hans-Georg Beyer, Edmund K. Burke, Juan Julián Merelo Guervós, L. Darrell Whitley, Xin Yao (Eds.), Lecture Notes in Computer Science 4193, Springer 2006, ISBN   3-540-38990-3
  20. ↑ Parallel Problem Solving from Nature - PPSN VIII, 8th International Conference, Birmingham, UK, September 18–22, 2004, Proceedings. Xin Yao, Edmund K. Burke, José Antonio Lozano, Jim Smith, Juan Julián Merelo Guervós, John A. Bullinaria, Jonathan E. Rowe, Peter Tiño, Ata Kabán, Hans-Paul Schwefel (Eds.), Lecture Notes in Computer Science 3242, Springer 2004, ISBN   3-540-23092-0
  21. ↑ Parallel Problem Solving from Nature - PPSN VII, 7th International Conference, Granada, Spain, September 7–11, 2002, Proceedings. Juan Julián Merelo Guervós, Panagiotis Adamidis, Hans-Georg Beyer, José Luis Fernández-Villacañas Martín, Hans-Paul Schwefel: (Eds.), Lecture Notes in Computer Science 2439, Springer 2002, ISBN   3-540-44139-5
  22. ↑ Parallel Problem Solving from Nature - PPSN VI, 6th International Conference, Paris, France, September 18–20, 2000, Proceedings. Marc Schoenauer, Kalyanmoy Deb, Günter Rudolph, Xin Yao, Evelyne Lutton, Juan Julián Merelo Guervós, Hans-Paul Schwefel: (Eds.), Lecture Notes in Computer Science 1917, Springer 2000, ISBN   3-540-41056-2
  23. ↑ Parallel Problem Solving from Nature - PPSN V, 5th International Conference, Amsterdam, the Netherlands, September 27–30, 1998, Proceedings. A. E. Eiben, Thomas Bäck, Marc Schoenauer, Hans-Paul Schwefel (Eds.), Lecture Notes in Computer Science 1498, Springer 1998, ISBN   3-540-65078-4
  24. ↑ Parallel Problem Solving from Nature - PPSN IV, International Conference on Evolutionary Computation. The 4th International Conference on Parallel Problem Solving from Nature, Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, Hans-Paul Schwefel (Eds.), Berlin, Germany, September 22–26, 1996, Proceedings. Lecture Notes in Computer Science 1141, Springer 1996, ISBN   3-540-61723-X
  25. ↑ Parallel Problem Solving from Nature - PPSN III, International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature, Yuval Davidor, Hans-Paul Schwefel, Reinhard Männer (Eds.), Jerusalem, Israel, October 9–14, 1994, Proceedings. Lecture Notes in Computer Science 866, Springer 1994, ISBN   3-540-58484-6
  26. ↑ Parallel Problem Solving from Nature 2, PPSN-II, Reinhard Männer, Bernard Manderick (Eds.), Brussels, Belgium, September 28–30, 1992. Elsevier 1992, ISBN   978-0444897305
  27. ↑ Parallel Problem Solving from Nature, 1st Workshop, PPSN I, Dortmund, Germany, October 1–3, 1990, Proceedings. Hans-Paul Schwefel, Reinhard Männer (Eds.), Lecture Notes in Computer Science 496, Springer 1991, ISBN   3-540-54148-9
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.