Genetic Algorithms:

Description of Tutorial

The Introduction to Genetic Algorithms Tutorial is aimed at GECCO attendees with limited knowledge of genetic algorithms, and will start “at the beginning,” describing first a “classical” genetic algorithm in terms of the biological principles on which it is loosely based, then present some of the fundamental results that describe its performance. It will cover many variations on the classical model, some successful applications of genetic algorithms, and advances that are making genetic algorithms more useful.

Erik Goodman

Biosketch: Erik Goodman is a Professor of Electrical and Computer Engineering and of Mechanical Engineering at Michigan State University. He studied genetic algorithms under John Holland at the University of Michigan, before they had been named. His use of a genetic algorithm in 1971 to solve for 40 coefficients of a highly nonlinear model of a bacterial cell was the first known GA application on a real-world problem, and ran for nearly a year on a dedicated computer. He has used genetic algorithms in his research ever since, including for parameterization of complex ecosystem models, for evolution of cooperative behavior in artificial life, for factory layout and scheduling, for protein folding and ligand docking, for design of shape and layup of composite structures, and for data mining and pattern classification.

Much of his recent research has been in development of new types of parallel genetic algorithms and in design methods for mechatronic systems using genetic programming. He is co-founder and VP Technology of Red Cedar Technology, which provides tools for automated engineering design based on evolutionary computation. He chaired ICGA-97 and GECCO-2001, chaired GECCO’s sponsoring organization, ISGEC, from 2001-2004, and he served as Chair of ACM SIGEVO, its successor. He continues serving on the SIGEVO executive committee.

Probabilistic Model-Building Algorithms (PMBGAs)

Description of Tutorial

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. PMBGAs are also known as estimation of distribution algorithms (EDAs) and iterated density-estimation algorithms (IDEAs).

Replacing traditional crossover and mutation operators by building and sampling a probabilistic model of promising solutions enables the use of machine learning techniques for automatic discovery of problem regularities and exploitation of these regularities for effective exploration of the search space. Using machine learning in optimization enables the design of optimization techniques that can automatically adapt to the given problem. There are many successful applications of PMBGAs, for example, Ising spin glasses in 2D and 3D, graph partitioning, MAXSAT, feature subset selection, forest management, groundwater remediation design, telecommunication network design, antenna design, and scheduling.

The tutorial Probabilistic Model-Building GAs will provide a gentle introduction to PMBGAs with an overview of major research directions in this area. Strengths and weaknesses of different PMBGAs will be discussed and suggestions will be provided to help practitioners to choose the best PMBGA for their problem.

Martin Pelikan

Biosketch: Martin Pelikan received Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 2002. Since 2003 he has been an assistant professor at the Dept. of Mathematics and Computer Science at the University of Missouri in St. Louis. In 2006 Pelikan founded the Missouri Estimation of Distribution Algorithms Laboratory (MEDAL). Prior to joining the University of Missouri, he worked at the Illinois Genetic Algorithms Laboratory (IlliGAL), the German National Center for Information Technology in Sankt Augustin, the Slovak University of Technology in Bratislava, and the Swiss Federal Institute of Technology (ETH) in Zurich.

Description of Tutorial

When Learning Classifier Systems (LCSs) were introduced by John H. Holland in the 1970s, the intention was the design of a highly adaptive cognitive system. Since the introduction of the accuracy-based XCS classifier system by Stewart W. Wilson in 1995 and the modular analysis of several LCSs thereafter, it was shown that LCSs can effectively solve data-mining problems, reinforcement learning problems, other predictive problems, and cognitive control problems. It was shown that performance is machine learning competitive, but learning is taking place online and is often more flexible and highly adaptive. Moreover, system knowledge can be extracted easily.The Learning Classifier System tutorial provides a gentle introduction to LCSs and their general functioning. It surveys the current theoretical understanding as well as most successful LCS applications to various problem types. The tutorial ends with a discussion of the most promising areas for future applications.

Martin V. Butz

Biosketch: Martin V. Butz received his Diploma in computer science from the University of Wuerzburg, Germany in 2001 with the thesis topic: “Anticipatory Learning Classifier Systems”. He then moved on to the University of Illinois at Urbana-Champaign for his PhD studies under the supervision of David E. Goldberg. Butz finished his PhD in computer science on “Rule-based evolutionary online learning systems: Learning Bounds, Classification, and Prediction” in October, 2004. The thesis puts forward a modular, facet-wise system analysis for Learning Classifier Systems (LCSs) and analyzes and enhances the XCS classifier system.

Coevolution

Description of Tutorial

Recent advances in coevolutionary algorithm design and theory stimulate a need for tutorials that provide insight into these advances. We present material on coevolutionary computation in two tutorials; we emphasize core concepts, but also flesh them out into application.

The Introductory Tutorial on Coevolution is aimed at those with basic working knowledge of evolutionary computation, but limited knowledge of coevolution. This tutorial will outline the potential advantages of coevolution, explain terminology, underscore the key ideas that help frame our understanding of these methods, develop a simple algorithm with variants, then explore some of the issues and phenomena that are particular to coevolution.

The Advanced Tutorial on Coevolution is aimed at attendees who have a working knowledge of coevolution, but who wish to learn more about the modern algorithmic and analytical approaches to coevolutionary computation. We will present a more detailed discussion of how coevolutionary algorithms work (or fail to). We will also examine several successful modern coevolutionary algorithms and deconstruct them to reveal the principles behind their successful operation.

Specific topics that will be covered over the two tutorials include, among others, solution concepts, monotonic progress, underlying objectives, informativeness, gradient (and its loss), monitoring methods, methods of interaction and evaluation, and key representation issues unique to coevolution.

Sevan G. Ficici

Sevan G. Ficici .- He is currently a Post-Doctoral Fellow in computer science at Harvard University; he obtained his Ph.D. from Brandeis University working under Jordan Pollack. Sevan has worked broadly in the field of multi-agent systems and learning for over a decade. His Ph.D. work focused on coevolutionary learning in multi-agent systems. At Harvard, Sevan is working with Avi Pfeffer to develop computational models of human behavior in multi-agent domains and construct computer agents that utilize these models to interact successfully with human participants. Sevan was chair of the coevolution track at GECCO 2006.

Genetic Programming Theory

Description of Tutorial

GP is a complex adaptive system with zillions of degrees of freedom. Experimental studies require the experimenter to choose which problems, parameter settings and descriptors to use. Plotting the wrong data increases the confusion about GP's behaviour, rather than clarify it.

We treat GP as a search process and explain its behaviour by considering the search space, in terms of its size, its limiting fitness distributions and also the halting probability. Then we shall use modern schema theory to characterise GP search. We finish with lessons and implications.

Knowledge of genetic programming will be assumed.

Riccardo Poli

Biosketches: Riccardo Poli is a professor in the Department of Computer Science at Essex. His main research interests include genetic programming (GP) and the theory of evolutionary algorithms. In July 2003 Prof.Poli was elected a Fellow of The International Society for Genetic and Evolutionary Computation (ISGEC) ``... in recognition of sustained and significant contributions to the field and the community''. He has published over 180 refereed papers on evolutionary algorithms (particularly genetic programming), neural networks and image/signal processing. With W.B.Langdon, he has co-authored the book Foundations of Genetic Programming . He has been co-founder and co-chair of EuroGP, the European Conference on Genetic Programming for 1998, 1999, 2000 and 2003.

Description of Tutorial

The "No Free Lunch" theorem is now more than 10 years old; it asserts that all possible search algorithms have the same expected behavior over all possible discrete search problems. But there is more than this to No Free Lunch (NFL). NFL also holds over finite sets of functions, some of which are compressible and some of which are not. A focused form of NFL also holds for very small finite groups of parameter optimization problems encoded using Binary and Gray Code representations. Some observations that hold when NFL is applied over all possible discrete functions are not true when NFL holds over a finite set.

Variants of local search are capable of beating random enumeration (and side stepping NFL) over large classes of problems of bounded complexity. The talk will also explore what NFL tells us about how to construct, compare and evaluate search algorithms.

Darrell Whitley

Biosketch: Darrell Whitley is Professor and Chair of Computer Science at Colorado State University. He was the Chair of the Governing Board of the International Society for Genetic Algorithms from 1993 to 1997. He was editor-in-chief of the journal Evolutionary Computation from 1997 to 2003.

Bioinformatics:

Description of Tutorial

Bioinformatics is an interdisciplinary field of study that blends computer science and statistics with the biological sciences. Important objectives of bioinformatics include the storage, management and retrieval of high-dimensional biological data and the detection, characterization, and interpretation of patterns in such data. The goal of this tutorial is to provide an entry-level introduction to bioinformatics for those hoping to apply genetic and evolutionary computation to solving complex biological problems. Specific examples of how methods such as genetic programming have been applied in bioinformatics will be presented.

Jason H. Moore

Biosketch: Jason H. Moore, Ph.D.: Dr. Moore received his M.S. in Statistics and his Ph.D. in Human Genetics from the University of Michigan. He then served as Assistant Professor of Molecular Physiology and Biophysics (1999-2003) and Associate Professor of Molecular Physiology and Biophysics with tenure (2003-2004) at Vanderbilt University. While at Vanderbilt, Dr. Moore held an endowed position as an Ingram Asscociate Professor of Cancer Research. He also served as Director of the Bioinformatics Core and Co-Founder and Co-Director of the Vanderbilt Advanced Computing Center for Research and Education (ACCRE).

Description of Tutorial

Many real-world search and optimization problems are naturally posed as non-linear programming problems having multiple conflicting objectives.

Due to lack of suitable solution techniques, such problems are usually artificially converted into a single-objective problem and solved. The difficulty arises because multi-objective optimization problems give rise to a set of Pareto-optimal solutions, each corresponding to a certain trade-off among the objectives. It then becomes important to find not just one Pareto-optimal solution but as many of them as possible.

Classical methods are found to be not efficient because they require repetitive applications to find multiple Pareto-optimal solutions and in some occasions repetitive applications do not guarantee finding distinct Pareto-optimal solutions. The population approach of evolutionary algorithms (EAs) allows an efficient way to find multiple Pareto-optimal solutions simultaneously in a single simulation run.

In this tutorial, we shall contrast the differences in philosophies between classical and evolutionary multi-objective methodologies and provide adequate fundamentals needed to understand and use both methodologies in practice.

Particularly, major state-of-the-art evolutionary multi-objective optimization (EMO) methodologies will be presented and various related issues such as performance assessment and preference articulation will be discussed. Thereafter, three main application areas of EMO will be discussed with adequate case studies from practice -- (i) applications showing better decision-making abilities through EMO, (ii) applications exploiting the multitude of trade-off solutions of EMO in extracting useful information in a problem, and (iii) applications showing better problem-solving abilities in various other tasks (such as, reducing bloating, solving single-objective constraint handling, and others).

Clearly, EAs have a niche in solving multi-objective optimization problems compared to classical methods. This is why EMO methodologies are getting a growing attention in the recent past. Since this is a comparatively new field of research, in this tutorial, a number of future challenges in the research and application of multi-objective optimization will also be discussed.

This tutorial is aimed for both novices and users of EMO. Those without any knowledge in EMO will have adequate ideas of the procedures and their importance in computing and problem-solving tasks. Those who have been practicing EMO will also have enough ideas and materials for future research, know state-of-the-art results and techniques, and make a comparative evaluation of their research.

Eckart Zitzler

Biosketches: Eckart Zitzler received degrees from University of Dortmund in Germany (diploma in computer science) and ETH Zurich in Switzerland (doctor of technical sciences). Since 2003, he has been Assistant Professor for Systems Optimization at the Computer Engineering and Networks Laboratory at the Department of Information Technology and Electrical Engineering of ETH Zurich, Switzerland. His research focuses on bio-inspired computation, multiobjective optimization, computational biology, and computer engineering applications. Dr. Zitzler was General Co-Chairman of the first three international conferences on evolutionary multi-criterion optimization (EMO 2001, EMO 2003, and EMO 2005)

Addresses:
Eckart Zitzler

Computer Engineering (TIK), ETH Zurich
Gloriastr. 35, 8092 Zurich, Switzerland
Phone:+41-1-6327066 Fax:+41-1-6321035
http://www.tik.ee.ethz.ch/~zitzler/

Kalyanmoy Deb

Professor Phone : +91 512 2597205 (O)
Department of Mechanical Engineering +91 512 2598310 (H)
Indian Institute of Technology, Kanpur Fax : +91 512 2597205, 2590007
Kanpur, Pin 208 016, INDIA
http://www.iitk.ac.in/kangal/deb.htm

Description of Tutorial

Successful and efficient use of evolutionary algorithms (EAs) depends on the choice of the problem representation - that is, the genotype and the mapping from genotype to phenotype - and on the choice of search operators that are applied to this representation. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation.

In EA practice one can distinguish two complementary approaches. The first approach uses indirect representations where a solution is encoded in a standard data structure, such as strings, vectors, or discrete permutations, and standard off-the-shelf search operators are applied to these genotypes.

To evaluate the solution, the genotype needs to be mapped to the phenotype space. The proper choice of this genotype-phenotype mapping is important for the performance of the EA search process. The second approach, the direct representation, encodes solutions to the problem in its most 'natural' space and designs search operators to operate on this representation.

Research in the last few years has identified a number of key concepts to analyse the influence of representation-operator combinations on EA performance.

These concepts are

• locality,
• redundancy, and
• bias.

Locality is a result of the interplay between the search operator and the genotype-phenotype mapping. Representations are redundant if the number of phenotypes exceeds the number of possible genotypes. Furthermore, redundant representations can lead to biased encodings if some phenotypes are on average represented by a larger number of genotypes. Finally, a bias need not be the result of the representation but can also be caused by the search operator.

The tutorial gives a brief overview about existing guidelines for representation design, illustrates the different aspects of representations, gives a brief overview of theoretical models describing the different aspects, and illustrates the relevance of the aspects with practical examples.

It is expected that the participants have a basic understanding of EA principles.

Franz Rothlauf

Biosketch: Franz Rothlauf received a Diploma in Electrical Engineering from the University of Erlangen, Germany, a Ph.D. in Information Systems from the University of Bayreuth, Germany, a Habilitation from the university of Mannheim, Germany, in 1997, 2001, and 2007, respectively. He is currently full professor at the Department of Information Systems, Mainz University, Germany. He has published more than 45 technical papers in the context of evolutionary computation, co- edited several conference proceedings, and is author of the book "Representations for Genetic and Evolutionary Algorithms" which is published in a second edition in 2006.

His main research interests are problem representations for heuristic search approaches especially evolutionary algorithms. For several years he was a visiting researcher at the Illinois Genetic Algorithm Laboratory (IlliGAL). He is a member of the Editorial Board of Evolutionary Computation Journal, Information Sciences, and Journal of Artificial Evolution and Applications. He has been organizer of several workshops on representations issues, chair of EvoWorkshops in 2005 and 2006, co-organizer of the European workshop series on "Evolutionary Computation in Communications, Networks, and Connected Systems", co-organizer of the European workshop series on "Evolutionary Computation in Transportation and Logistics", and co-chair of the program commitee of the GA track at GECCO 2006. He is conference chair of GECCO 2009.

Description of Tutorial

Classical optimization methods are often too restrictive to be applied to practical problem solving due to a number of limitations in their working principles: convexity requirement, continuity of search space, unimodality, single-objectiveness etc. Unfortunately, most practical optimization problems have all but the above properties. Evolutionary algorithms belong to a class of stochastic optimization algorithms which, although do not always guarantee finding the optimal solution, often are the only viable choices to solve those problems to near-optimality. In this tutorial, we shall discuss a number of properties and operators which provide EAs the necessary platform to solve such complex optimization problems. Every aspect will be contrasted with competitive classical methods and will be illustrated with interesting case studies.

Contents:

1. Practical optimization problems and their characteristics
1.1 Large dimension (variables and constraints)
1.2 Non-linear constraints
1.3 Discontinuities, non-differentiability, discreteness of search space
1.4 Multi-modalities (multiple optima, local and global)
1.5 Multi-objectivity (multiple conflicting objectives, trade-off solutions)
1.6 Uncertainties in variables and objectives (robust design, reliability-based design, handling noise)
1.7 Large computational time for evaluation (need for approximate eval. using RSM, Kriging, neural nets etc.)
1.8 Imprecise description of variables and objectives (need for fuzzy logic and rough set descriptions)
1.9 Dynamic optimization problems in which optimization problem changes with time (iteration counter)

2. Efficient evolutionary algorithms for practical optimization (Modifications to a basic EA will be discussed to handle each issue of item 1. Reasons for their success will be given. Moreover, to illustrate at least one case study for each case will be discussed to drive the point home)

3. Beyond optimization: Unveiling innovation and innovative principles for being optimum (EAs allow finding multiple optimal solutions in one simulation. These solutions can be analyzed for commonality principles which often give rise to innovative principles about solving the problem which were not known before and not possible to achieve by other means. A number of interesting case studies will be discussed to illustrate the innovative principles which can be deciphered by this process. This task has a tremendous application in engineering design activities.)

Who should attend?

All those who are interested in practical optimization and practical problem solving will be interested in this tutorial. Besides getting a feel for the differences between evolutionary optimization and their classical counterparts, participants will get a feel that evolutionary optimization provides a more (w)holistic optimization which can not only be used to just find the optimum or near-optimum solution, but to look beyond and gain a plethora of important insights about solving the problem at hand.

Kalyanmoy Deb

Biosketch: Kalyanmoy Deb is a Professor of Mechanical Engineering at Indian Institute of Technology Kanpur, India. He is the recipient of the prestigious Shanti Swarup Bhatnagar Prize in Engineering Sciences for the year 2005. He has also received the `Thomson Citation Laureate Award' from Thompson Scientific for having highest number of citations in Computer Science during the past ten years in India. Recently he received the MCDM Edgeworth-Pareto Award from Intl. Soecity on Multiple Criterion Decision Making (MCDM). He is a fellow of Indian National Academy of Engineering (INAE), Indian National Academy of Sciences, and International Society of Genetic and Evolutionary Computation (ISGEC). He has received Fredrick Wilhelm Bessel Research award from Alexander von Humboldt Foundation in 2003.

His main research interests are in the area of computational optimization, modeling and design, and evolutionary algorithms. He has written two text books on optimization and more than 200 international journal and conference research papers.

Kalyanmoy Deb
Professor of Mechanical Engineering
Department of Mechanical Engineering
Indian Institute of Technology Kanpur
Kanpur, PIN 208016, India
Email:
Web: http://www.iitk.ac.in/kangal/deb.htm

The tutorial enables attendees to analyze the computational complexity of evolutionary algorithms and other search heuristics in a rigorous way. An overview of the tools and methods developed within the last 15 years is given and practical examples of the application of these analytical methods are presented.

Thomas Jansen

Biosketches: Thomas Jansen, born 1969, studied Computer Science at the University of Dortmund, Germany. He received his diploma (1996) and Ph.D. (2000) there. From September 2001 to August 2002 he stayed as a Post-Doc at Kenneth De Jong's EClab at the George Mason University in Fairfax, VA. Since September 2002 he holds a position as Juniorprofessor for Computational Intelligence at the University of Dortmund. He is an associate editor of Evolutionary Computation (MIT Press). His research is centered around the theoretical analysis of evolutionary algorithms.

There are many interesting things we can study about genetic algorithms from a theoretical point of view. There are structural issues, such as how to design operators for different search spaces, and there are dynamical issues, such as working out where a GA will spend most of its time, and how long does it take to get