TUTORIALS
All tutorials will take place on Sunday, September 2nd, 2012.
Introduction to Bioinformatics
Jaume Bacardit, University of Nottingham, UK
Abstract
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.
Short Bio
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
Juergen Branke, University of Warwick, UK
Abstract
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.
Short Bio
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
Pierre Collet, Strasbourg University, France
Abstract
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.
Short Bio
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
Holger H. Hoos, University of British Columbia, Canada
Abstract
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.
Short Bio
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.)
Ant Colony Optimization
Vittorio Maniezzo, University of Bologna, Italy
Abstract
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.
Short Bio
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).
Tutorial on Estimation of Distribution Algorithms
Martin Pelikan, University of Missouri in St. Louis, USA
Abstract
Estimation of distribution algorithms (EDAs) guide the search for the optimum by building and sampling explicit probabilistic models of promising candidate solutions. However, EDAs are not only optimization techniques; besides the optimum or its approximation, EDAs provide practitioners with a series of probabilistic models that reveal a lot of information about the problem being solved. This information can in turn be used to design problem-specific neighborhood operators for local search, to bias future runs of EDAs on a similar problem, or to create an efficient computational model of the problem. EDAs have been successfully applied to many complex problems, from stock trading to groundwater remediation system design. The tutorial on EDAs will provide an introduction to EDAs and review some of the major research directions in this area. Strengths and weaknesses of different EDAs will be discussed and suggestions will be provided to help practitioners to choose the best EDA for their problem. EDAs are also known as probabilistic model-building genetic algorithms (PMBGAs) and iterated density-estimation evolutionary algorithms (IDEAs).
Short Bio
Martin Pelikan received Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 2002. He is now an associate professor at the Department of Mathematics and Computer Science at the University of Missouri. 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. Pelikan has worked as a researcher in genetic and evolutionary computation since 1995. His most important contributions to genetic and evolutionary computation are the Bayesian optimization algorithm (BOA), the hierarchical BOA (hBOA), the scalability theory for BOA and hBOA, and the efficiency enhancement techniques for BOA and hBOA. His current research focuses on extending BOA and hBOA to other problem domains, applying genetic and evolutionary algorithms to real-world problems with the focus on physics, bioinformatics and machine learning, and designing new efficiency enhancement techniques for BOA and other evolutionary algorithms.
Complex Systems Science in its thirties
Roberto Serra, University of Modena and Reggio Emilia, Italy
Abstract
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.
Short Bio
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
Lee Spector, Hampshire College, USA
Abstract
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.
Short Bio
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