Tutorials will take place on September 12, 2010.
Evolutionary algorithms have been shown to be espe- cially successful when dealing with multi-objective problems. The area of evolutionary multi-objective optimization has grown rapidly during the last years. In this tutorial, we give an overview on the different results that have been achieved on the theoretical aspects of evolutionary multi-objective op- timization.
There has been a lot of progress on the foundational side of evolution- ary multi-objective optimization. The first part of the tutorial will cover convergence and runtime analysis of evolutionary multi-objective optimiza- tion. We will also discuss how multi-objective models of single-objective optimization problems can provably lead to faster evolutionary algorithms for different combinatorial optimization problems.
How to achieve a good spread over the Pareto front is one of the big questions in evolutionary multi-objective optimization. Therefore the sec- ond part is dedicated to several diversity mechanisms, particularly the hy- pervolume indicator. This indicator plays an important role and has found many applications. We present recent results on complexity and approxima- bility of the hypervolume and discuss what they imply for applications.
Frank Neumann studied Technical Computer Science in Dortmund and Kiel, Germany. He received his diploma and Ph.D. from the Christian- Albrechts-University of Kiel in 2002 and 2006, respectively. Currently, he is the coordinator of the research area “Bio-inspired Computation” within the Algorithms and Complexity Group at the Max Planck Institute for In- formatics in Saarbruecken, Germany. In his work, he considers theoretical aspects of evolutionary computation methods in particular for combinatorial and multi-objective optimization problems and has received six best paper awards at leading international conferences such as GECCO and PPSN. Frank has been a co-chair of the track “Formal Theory” at GECCO 2007 and the chaired of the track “Evolutionary Combinatorial Optimization” at GECCO 2008. He has given tutorials on “Computational Complexity and Evolutionary Computation” (together with Thomas Jansen) at GECCO (2007-2010) and a tutorial on “Computational Complexity of Evolutionary Computation in Combinatorial Optimization” at PPSN 2008 (together with Carsten Witt).
More information can be found at http://www.mpi-inf.mpg.de/~fne
Tobias Friedrich received his MSc in computer science from the Uni- versity of Sheffield, UK, in 2002 and his diploma in mathematics from the University of Jena, Germany, in 2005. In 2007 he obtained a PhD in theo- retical computer science from the Saarland University, Germany. Currently, he is a member of the Algorithms Group in the International Computer Science Institute Berkeley, USA. The central topic of his work are random- ized algorithms (both classical and evolutionary) and randomized methods in mathematics and computer science in general. The last two years, Tobias won two best paper awards in the tracks “Genetic Algorithms” (GECCO 2008) and “Evolutionary Multiobjective Optimization” (GECCO 2009).
More information can be found at http://www.mpi-inf.mpg.de/~tfried
It is well known that for many practical optimization problems, especially from the domain of combinatorial optimization, "pure" evolutionary algorithms (EAs) are not as effective as more sophisticated hybrid approaches combining concepts of evolutionary computation with problem-specific procedures, other metaheuristics, exact optimization techniques, or methods from the fields of artificial intelligence or operations research. The general idea is to "exploit the best of different worlds" and to benefit from synergy by such combinations. Numerous publications of the recent years and dedicated scientific workshops document the significance of this trend and specific research area.
This tutorial starts with an overview on the most commonly used hybridization techniques such as decoder-based EAs, embedding local search procedures in EAs, and exploiting concepts of simulated annealing, tabu search, path relinking, very large neighborhood search, and other metaheuristics. A systematic classification of hybrid approaches will then be discussed, leading to further approaches, especially also including collaborative combinations, in which different search strategies cooperate in a looser form.
In the remainder, we will in particular focus on combinations of EAs with branch-and-bound and (integer) linear programming methods. Discussed topics include solution merging, strategic guidance of evolutionary algorithms by means of linear programming and Lagrangian relaxations, and exploiting EAs and other metaheuristics within exact branch-and-bound frameworks. Not so common but highly promising ideas such as applying metaheuristics for cut and column generation are addressed.
Prof. Günther Raidl heads the Algorithms and Data Structures group of the Institute of Computer Graphics and Algorithms at the Vienna University of Technology. In September 2005 he received a professorship position for combinatorial optimization at this University. Before, he was Research Assistant, Lecturer and Assistant Professor at the Vienna University of Technology. Prof. Günther Raidl received his master degree in Computer Science in 1992 and his PhD in 1994 and completed his habilitation in Practical Computer Science in 2003 at the Vienna University of Technology.
His research interests include algorithms and data structures in general, combinatorial and continuous optimization, mathematical programming techniques, metaheuristics, hybrid optimization approaches, evolutionary computation, network design, cutting and packing, transport optimization, warehouse logistics, scheduling, and bioinformatics.
Günther Raidl is associate editor for the International Journal of Metaheuristics and the Evolutionary Computation Journal. Furthermore he is co-founder and steering committee member of the European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP) and has been editor-in-chief of the 2009 Genetic and Evolutionary Computation Conference (GECCO). He has (co-)edited 12 books and authored over 100 reviewed articles in journals, books, and conference proceedings.
More information can be found at http://www.ads.tuwien.ac.at/raidl/
Recent years have seen the application of multiple Natural Computing (NC) algorithms for the purposes of financial modelling. Particular features of financial markets including their dynamic and interconnected characteristics bear parallel with processes in the natural world and prima facie, this makes NC methods ‘interesting’ for financial modelling applications. Another feature of both natural and financial environments is the phenomenon of emergence, or the activities of multiple individual agents combining to co-evolve their own environment. The scale of NC applications in finance is illustrated by Chen & Kuo who list nearly 400 papers that had been published by 2001 on the use of evo- lutionary computation alone in computational economics and finance. Since then several hundred additional papers have been published underscoring the continued growth in this application area.
Some of the major areas of financial applications using NC methods are: forecasting, algorithmic trading, portfolio management, risk management, derivatives modelling and market modelling. In this tutorial, we describe the utility of NC methods for a range of topics in finance and highlight interesting, open, areas of research.
Professor Anthony Brabazon is currently Head of Research in the School of Business at University College Dublin. His primary research interests concern the development of natural computing theory and the application of natural computing algorithms to real-world problems, particularly in the domain of finance. He is co-founder and co-director (with Dr. Michael O'Neill, School of Computer Science and Informatics, UCD) of the Natural Computing Research and Applications Group at UCD (see http://ncra.ucd.ie). The NCRA engages in both basic and applied research in natural computing methodologies. The NCRA is the only dedicated natural computing research facility in Ireland. Prof. Brabazon is also Director of FMC2 a large research group in financial mathematics and computation (www.fmc-cluster.org). This research group is funded via Science Foundation Ireland and industrial collaborators.
Anthony has an established publication record in the field of evolutionary computation / natural computing with in excess of 120 peer-reviewed publications. He has authored / edited several books including 'Biologically Inspired Algorithms for Financial Modelling' and 'Natural Computing in Computational Finance' (Volumes I, II and III), all published by Springer. As well as sitting on the editorial boards of several journals, Anthony is a regular reviewer for a wide range of journals in natural computing, operations research and finance. He is a regular member of programme committees at major conferences in the field of natural computing, including GECCO (Genetic and Evolutionary Computation Conference), IEEE Congress on Evolutionary Computation, and EuroGP (European Conference on Genetic Programming). He is founder and co-Chair of EvoFin, the only dedicated European research workshop on the application of evolutionary algorithms to computational finance and economics and is also a member of the IEEE Computational Finance and Economics Technical Committee.
More information can be found at http://www.ucd.ie/research/people/business/dranthonybrabazon/
Dr. O'Neill is a founder of the UCD Natural Computing Research Applications group with Prof. Anthony Brabazon, and is a Senior Lecturer in the UCD School of Computer Science & Informatics. He is the lead author of the seminal book on Grammatical Evolution, and is independently ranked as one of the top 10 researchers in Genetic Programming.
Dr. O'Neill has published in excess of 170 peer-reviewed publications including 3 Monographs. In 2009 he published the second book on Grammatical Evolution, "Foundations in Grammatical Evolution for Dynamic Environments" with Ian Dempsey and Anthony Brabazon, and in 2006 he published the book on "Biologically Inspired Algorithms for Financial Modelling" with Prof. Brabazon. He has over 1000 citations, and a H-index of 17. Dr. O'Neill has co-authored a number of successful funding applications with a total value over €7 Million.
Michael is currently a Chair of the Genetic Programming Track of the ACM Genetic and Evolutionary Computation Conference 2010, and Co-Chair and Founder of the European Workshop on Evolutionary Computation in Finance & Economics (EvoFIN 2009). Dr. O'Neill is on the Editorial Boards of the Journal of Artificial Evolution and Applications, and the International Journal of Innovative Computing and Applications. He has acted as External Examiner for a number of PhDs in the field of Evolutionary Computation.More information can be found at http://www.ucd.ie/research/people/computerscienceinformatics/drmichaeloneill
Scheduling is a key issue in distributed computing and has been largely investigated in the past for traditional distributed computing environments, including clusters and supercomputers. With the fast development of Internet and the emerging new distributed computing paradigms such as Grid Computing, P2P computing, Cloud Computing, etc., scheduling has attracted again the attention of many researchers and developers from academia and industry. For such new computing paradigms, the design of efficient schedulers is a must in order to leverage the enormous computing capacity offered by large scale distributed systems such as Grid and P2P systems.
Scheduling problems, in most general formulations, are known to be NP-hard problems. The versions of scheduling for large scale distributed environments inherit many of the characteristics of scheduling in traditional distributed environments. However, the problem becomes even more challenging due to new characteristics and requirements of large scale distributed environments, among which we could distinguish the dynamics of the system, the high degree of heterogeneity of resources and tasks/applications, the high heterogeneity of interconnection networks, scalability and efficiency requirements, the multi-objectivity, the presence of local schedulers as well as local policies on resources that spawn different administrative domains, security issues, etc. In view of the complexity of the problem, obviously, heuristic and meta-heuristic methods are the de facto approach to deal in practice with the problem.
In this tutorial we will review the state of the art in heuristic/meta-heuristic methods for scheduling problems in large scale distributed environments and will focus on the following:
-
Introduce large scale distributed environments with an emphasis on Grid systems.
Introduce scheduling problems, their requirements and formal definitions as multi-objective optimization problems.
Present the application of ad hoc methods to scheduling problems.
Present the application of local search based methods to scheduling problems with special emphasis to Tabu Search.
Present the application of population based methods (Genetic Algorithms and Memetic Algorithms —both unstructured and structured) to scheduling problems.
The study of the performance of the heuristic and meta-heuristic based schedulers using a Grid simulator.
Fatos Xhafa holds a PhD in Computer Science from the Technical University of Catalonia (UPC, Barcelona, Spain) in 1998. He is currently Associate Professor at the Department of Languages and Informatic Systems (LSI) of the UPC and member of the ALBCOM Research Group of LSI Department. His current research interests include parallel algorithms, combinatorial optimization, approximation and meta-heuristics, distributed programming, Grid and P2P computing. His research is supported by research projects from Spain, European Union and NSF/USA. He has published in leading international journals and conferences and has served in the Organizing Committees of several conferences and workshops. Recently, he served as General Co-Chair of INCOS-2009, PC Co-Chair of AINA-2010 and General Co-Chair of CISIS-2010. He is also member of editorial board of several international journals.
More information can be found at http://www.lsi.upc.es/~fatos/
To be filled
To be filled.
More information can be found at http://dydaktyka.polsl.pl/KWMIMKM/TBurczynski.aspx
Computational social choice is a new research field spanning computer science, artificial intelligence, economics, and operations research and its main goal is to provide computational study of various collective decision-making mechanisms. During the last decade, one of the most prominent topics studied within computational social choice was computational complexity of elections. Researchers were interested both in the hardness of determining winners and in the complexity of manipulating results of elections. Unfortunately, almost all results regarding the complexity of elections are theoretical. It is, thus, crucial that theoretical findings be verified in practice and one of the purposes of this talk is to encourage more applied researchers to enter the field.
The talk will start with a very brief presentation of the most commonly studied election model and of several interesting voting systems. In particular, we will be looking at plurality, scoring protocols, and the voting system of Dodgson (the author of Alice’s Adventures in Wonderland, better known by his pen-name Lewis Carol). Dodgson’s voting will be our showcase of an election system which is, in some sense, very desirable but for which even computing the winner is remarkably difficult.
Further on, we will consider several other voting problems, such as the complexity of determining if a given candidate still has a chance of winning given partial information regarding the votes, and the issues of manipulating elections. For each of these problems we will discuss the strengths and limitations of currently known results and provide some intuition as to what further results would be desirable.
Dr Piotr Faliszewski is an assistant professor (adiunkt) at the Department of Computer Science at the AGH University of Science and Technology, which he joined in the spring of 2009. Before, he was a graduate student at the Univeristy of Rochester and worked as a lecturer at the Rochester Institute of Technology. Dr Piotr Faliszewski defended his PhD thesis on the computational complexity of manipulating elections in 2008, at the University of Rochester
His interests include widely understood algorithms and computational complexity theory, in particular as applied to computational social choice, a new research field spanning computer science, artificial intelligence, economics, and operations research. The goal of computational social choice is to provide computational perspective on collective decision making (either by people or software agents). Dr Piotr Faliszewski is also interested in algorithmic game theory, focusing on cooperative games and their solution concepts.
Piotr Faliszewski is on the program committee of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010) and on the program committee of the 3rd International Workshop on Computational Social Choice (COMSOC-2010). He has coauthored over 20 peer-reviewed articles in journals, conference proceedings, and books.
More information can be found at http://home.agh.edu.pl/~faliszew/