All tutorials will take place on Sunday, September 2nd, 2012.
Introduction to Bioinformatics
Bioinformatics is a very fascinating research area where many disciplines such as mathematics, computer science, engineering, etc. are put together to solve biological problems and bring new insight into our understanding of how life works. Biotechnological advances in the last decades have brought a continuously growing supply of biological data that requires non-trivial data analysis and management, from the handling, curation and efficient retrieval of biological data to the detection and analysis of patterns in such datasets.
This tutorial will provide an introductory description of the field of bioinformatics and the challenges and opportunities available in this discipline, with particular examples of how genetic and evolutionary computation can be applied to tackle such problems. The tutorial will cover basic molecular biology concepts, common bioinformatics algorithms applied across all kinds of biological data, specialised algorithms for specific types of data (e.g. dna, rna, proteins) and the broad field of biological data mining with several examples of the usage of evolutionary computation methods for such tasks.
Jaume Bacardit received a BEng and MEng in Computer Engineering and a PhD in Computer Science from the Ramon Llull University in Barcelona, Spain in 1998, 2000 and 2004, respectively. His PhD thesis involved the adaptation and application of Learning Classifier Systems to Data Mining tasks in terms of scalability, knowledge representations and generalization capacity.
In 2008 he was appointed as a Lecturer in Bioinformatics at the University of Nottingham. This is a joint post between the schools of Biosciences (MyCiB research group) and Computer Science (Interdisciplinary Computing and Complex Systems research group) with the aim of developing interdisciplinary research at the interface of both disciplines.
His research interests include the application of Learning Classifier Systems and other kinds of Evolutionary Learning to data mine large-scale challenging datasets and, in a general sense, the use of data mining and knowledge discovery for biological domains.
He was the PI of the EPSRC-funded project “Principled Application of Learning Classifier Systems to Large-Scale Challenging Datasets: LCSxLCD” (£101,458) and CI of the FP7 ICT- FET Open Initiative-funded CADMAD project (£371,290). From 2007 to 2010 he was a co-organiser of the International Workshop on Learning Classifier Systems (IWLCS), and has been in the organising committee of the Genetic and Evolutionary Computation Conference (GECCO) in 2010 and 2011. He was the chair of the “Genetics-Based Machine Learning” track in GECCO-2009 and the co-chair of the stream on “Bioinformatics, Systems and Synthetic Biology” of the OR53 conference. He has published more than 40 refereed papers, has given 7 invited talks, has edited two books and one special issues of a journal. He currently has two PhD students.
Evolutionary Multi-Objective Optimization
Many practical optimization problems are multi-objective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. As a result, there is usually not one optimal solution, but a set of Pareto-optimal solutions with different trade-offs. Which of these solutions is best depends on the decision maker’s preferences. As evolutionary algorithms always work with a population of solutions, this opens new opportunities in dealing with multi-objective problems by searching for multiple alternatives simultaneously. Consequently, evolutionary multi-objective optimization has become one of the most active research areas in evolutionary computation. This tutorial will give an in-depth introduction to evolutionary multi-objective optimization, with a particular focus on some of the more recent research trends such as the integration of user preferences.
Juergen Branke is Professor of Operational Research and Systems at Warwick Business School (UK). He has been an active researcher in evolutionary computation for 15 years, and has published more than 130 papers in international peer-reviewed journals and conferences. Prof. Branke is associate editor of the Journal of Heuristics and the Evolutionary Computation Journal. He was also co-founder of the Dagstuhl Workshop Series on Multiobjective Optimization, which brought together, for the first time, the communities of evolutionary multiobjective optimization and multi-criteria decision making.
Implementing artificial evolution on GPGPU-based computing eco-systems with the EASEA-CLOUD massively parallel platform
With the advent of GPGPU cards, all computers are becoming massively parallel systems that are very difficult to program efficiently. Indeed, the next generation of NVIDIA cards will provide 1024 cores grouped into multi-processors of 32 SIMD cores. This means that in order to efficiently execute an existing algorithm on a single PC with a hexacore CPU and a top notch GPGPU card, one should decompose the algorithm into 6 major tasks and 1024 minor ones which, 32 by 32, should execute the same instruction at the same time!
Because of necessary synchronizations between cores and data exchanges, exploiting efficiently such a machine (a standard PC) is virtually impossible with standard algorithms.
Fortunately, Complex Systems produce results that emerge from the multi-level interaction of many independent entities that can be directly implemented in a very efficient way on multi-level massively parallel machines such as the ones described above.
This tutorial will show how the EASEA-CLOUD massively parallel evolutionary platform implements evolutionary algorithms (that can optimize nearly any kind of continous, discrete, combinatorial, mixed problems) as a kind of Complex System, where entities are individuals that interact through genetic operators, not only on one machine, but on computing eco-systems such as clusters or grids of GPGPU machines, or a cloud of computers.
After a PhD in 1997 in virtual reality, Pierre Collet joined INRIA from 1998 to 2000, where he developed the EAsy Specification of Evolutionary Algorithms (EASEA) language. He then went to the French Ecole Polytechnique, as a researcher for the European DREAM project, that used EASEA as a programming language. After several years as associate professor at Université du Littoral, he was appointed full professor at Université de Strasbourg in 2007, where he leads the BFO (theoretical bioinformatics, data-mining and stochastic optimization) team of the ICUBE laboratory. In 2011, he was appointed Head of the department of Computer Science of the Strasbourg University. The EASEA language has now become a parallelization platform, that was quoted in a Science paper for its contribution to the finding of a new zeolite crystalline structure. A $500K research project called EASEA-CLOUD is starting in 2012 to port EASEA on the Grid and on the Cloud.
Programming by Optimisation - A new Paradigm for Developing High-Performance Software
When creating software, particularly solvers for computationally challenging problems, developers frequently explore multiple ways of achieving certain tasks. Often, these alternatives are eliminated or abandoned early in the process, based on the belief that the flexibility afforded by them would be difficult or impossible to exploit later. Programming by Optimisation (PbO) is a design paradigm that aims to avoid such premature design choices and to actively develop promising alternatives for parts of the design. Rather than build a single program for a given purpose, software developers specify a rich and potentially large design space of programs. From this specification, programs that perform well in a given use context are generated automatically through powerful optimisation techniques. PbO allows human experts to focus on the creative task of imagining possible mechanisms for solving given problems or subproblems, while the tedious job of determining what works best in a given use context is performed automatically, substituting human labor with computation. Furthermore, using PbO, per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.
In this tutorial, I will share the vision of how PbO can fundamentally change the way challenging computational problems are solved in the future. I will present examples from work done in my own group and elsewhere that clearly illustrate the viability and promise of the approach. These examples will cover substantial advances in the state of the art (often by orders of magnitude) in SAT-based software verification, planning and timetabling, as well as mixed integer programming - perhaps the most widely used approach for solving optimisation problems in industry. I will demonstrate the tools currently available to support PbO-based software development and outline additional support currently under development.
Holger H. Hoos is a Professor for Computer Science and a Faculty Associate at the Peter Wall Institute for Advanced Studies at the University of British Columbia (Canada). His main research interests span empirical algorithmics, artificial intelligence, bioinformatics and computer music. He is known for his work on the automated design of high-performance algorithms and on stochastic local search methods. Holger is a co-author of the book "Stochastic Local Search: Foundations and Applications", and his research has been published in numerous book chapters, journals, and at major conferences in artificial intelligence, operations research, molecular biology and computer music. Since 2009, he serves as President of the Canadian Artificial Intelligence Association (CAIAC). Currently, his group is helping UBC to produce better exam timetables, Actenum Inc. to increase production efficiency in the oil and gas industry, and IBM to improve their CPLEX optimisation software, which is used by 50% of the world's largest companies and thousands of universities.
(For further information, see Holger's web page at http://www.cs.ubc.ca/~hoos.)
Computational Intelligence and Games
Games are a rather young but fast growing application domain where methods of computational intelligence, and thus evolutionary computation, are widely applied. This tutorial gives a brief overview of the area and highlights the several research and application opportunities for computational intelligence and evolutionary computation methods. It also provides in-depth perspective on specific classes of problems where evolutionary computation has proved very successful. In particular, it covers the automatic/assisted design of game intelligence (NPC), the procedural generation of game contents (PCG), interactive evolution of personalized content, etc.
Pier Luca Lanzi is an associate professor at the Politecnico di Milano, Dipartimento di Elettronica e Informazione. His research areas include evolutionary computation and machine learning. He is interested in applications to data mining, autonomous agents, and videogames. He is member of the editorial board of the “Evolutionary Computation Journal” and Editor in chief of SIGEVOlution, the ACM Newsletter of SIGEVO, the Special Interest Group on Genetic and Evolutionary Computation.
Ant Colony Optimization
Ant Colony Optimization (ACO) is now 20 years old. During these years several – not to say many – researchers have contributed to the field. Some contributions kept close contact with the original natural metaphor, some were more mathematically oriented; some contributions were small variations of the original ant system, some departed much from it; some contributions considered only combinatorial optimization problems, some extended by much the spectrum of possible applications; some contributions were primarily of academic interest, some made their way to the market. This tutorial will focus on the latter of each mentioned pair.
Hands-on examples of design and implementation of an ACO system will be presented.
Vittorio Maniezzo is full professor of computer science at the department of Computer Science of the University of Bologna. His research interests are centered on the design of new algorithmic approaches for solving real-world problems, with special emphasis on problems which can be amened to a combinatorial optimization model. He was one of the original designers of the ant colony optimization approach (ACO), an approach which takes inspiration from the behavior of ant colonies and which enjoyed a significant success in the international optimization community. There is now a series of international workshops entirely dedicated to Ant Colony Optimization and dedicated sections of international journals and streams in leading international conferences in the area of computational optimization. Besides ant colony optimization, Vittorio Maniezzo is interested in algorithmic hybrids of metaheuristic approaches with mathematic programming techniques. He conceived what has turned out to be a series of international conferences dedicated to this type of hybrids (Matheuristics).
Complex Systems Science in its thirties
Complex Systems Science is no longer new, so it is appropriate to try to provide a comprehensive view. This will be done in the spirit of a tutorial, therefore the various aspects that will be considered will be described without assuming previous high-level knowledge.
After a brief historical sketch of the development of Complex Systems Science (CSS for short), that will comprise an excursus on its major concepts, achievements and open questions, two key concepts and two major applications in biology will be analyzed in some detail.
Roberto Serra graduated in Physics at the Bologna University, and later performed research activities in the industrial groups Eni and Montedison, where he served as director of the Environmental Research Centre until 2003. Since 2004 he is full professor of Computer Science and Engineering at the Modena and Reggio Emilia University.
His research interests concern several aspects of the dynamics of complex systems, paying particular attention to biological and social systems, and to the dynamical approach to Artificial Intelligence.
He published more than 130 papers in international journals and refereed conference proceedings, and is co-author of four books. He has been responsible of several research projects, funded by companies, by the Italian Ministry for Scientific Research (Miur), by the National Research Council (CNR) and by the European Union. He has served as a member of the program committee of several international conferences, and has delivered various invited talks and seminars.
He recently chaired two international conferences, one on Artificial Life and Evolutionary Computation (Venice, 2008) and one on Artificial Intelligence (Reggio Emilia, 2009).
Roberto Serra has also been president of AI*IA (Associazione Italiana per l’ Intelligenza Artificiale) and is currently chairman of the Science Board of the European Centre for Living Technologies.
Expressive Genetic Programming
The language in which evolving programs are expressed can have significant impacts on the problem-solving capabilities of a genetic programming system. These impacts stem both from the absolute computational power of the languages that are used, as elucidated by formal language theory, and from the ease with which various computational structures can be produced by random code generation and by the action of genetic operators. Highly expressive languages can facilitate the evolution of programs for any computable function using, when appropriate, multiple data types, evolved subroutines, evolved control structures, evolved data structures, and evolved modular program and data architectures. In some cases expressive languages can even support the evolution of programs that express methods for their own reproduction and variation (and hence for the evolution of their offspring).
This tutorial will begin with a comparative survey of approaches to the evolution of programs in expressive programming languages ranging from machine code to graphical and grammatical representations. Within this context it will then provide a detailed introduction to the Push programming language, which was designed specifically for expressiveness and specifically for use in genetic programming systems. Push programs are syntactically unconstrained but can nonetheless make use of multiple data types and express arbitrary control structures, supporting the evolution of complex, modular programs in a particularly simple and flexible way. The Push language will be described and ten years of Push-based research, including the production of human-competitive results, will be briefly surveyed. The tutorial will conclude with a discussion of recent enhancements to Push that are intended to support the evolution of complex and robust software systems.
Lee Spector is a Professor of Computer Science in the School of Cognitive Science at Hampshire College in Amherst, Massachusetts, and an adjunct professor in the Department of Computer Science at the University of Massachusetts, Amherst. He received a B.A. in Philosophy from Oberlin College in 1984 and a Ph.D. from the Department of Computer Science at the University of Maryland in 1992. His areas of teaching and research include genetic and evolutionary computation, quantum computation, and a variety of intersections between computer science, cognitive science, evolutionary biology, and the arts. He is the Editor-in-Chief of the journal Genetic Programming and Evolvable Machines (published by Springer) and a member of the editorial board of Evolutionary Computation (published by MIT Press). He is also a member of the SIGEVO executive committee and he was named a Fellow of the International Society for Genetic and Evolutionary Computation.
More info: http://hampshire.edu/lspector