1. Introduction & acknowledgement




Скачать 138.61 Kb.
Название1. Introduction & acknowledgement
страница1/13
Дата28.11.2012
Размер138.61 Kb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   ...   13


An overview of promising evolutionary

algorithms

The practical use of Evolutionary Computing


Martin Visser (mjvisser@cs.vu.nl)

Free university, Amsterdam


August 2003


Abstract

This paper intends to give an overview of real-world and academical problems that can be successfully solved by using an evolutionary computing (EC) approach. A bird’s eye view is taken to do this whilst hard academical evidence proving the superiority of evolutionary algorithms (EAs) of other methods is still scarce. From this perspective a selection of problems that are currently investigated with evolutionary techniques are described and it is pointed out why EAs can work well on these problems. We conclude with a practical description of what the advantages and disadvantages of EAs are in real-world problems and how their paradigm might be exploited further.


0. Table of contents


1. Introduction & acknowledgement 3

2. Explaining evolutionary algorithms 4

2.1. A short history 4

2.2. The basic principles 4

2.3. When to use an evolutionary approach 7

3. Scope 10

4. Categorization of EC research 13

4.1. Combinatiorial optimization 13

4.1.1. Scheduling 13

4.1.2. Timetabling 15

4.1.3. Graphs 16

4.1.4. Knapsack 18

4.1.5. Arc routing 19

4.2. Design 21

4.3. Image analysis 23

4.4. Decision support systems / controllers 25

4.5. Machine learning 27

4.6. Data-mining 29

4.7. Geometrical optimization / search 31

4.8. Arts 32

4.9 Other 33

5. Conclusions 34

6. References 36

1. Introduction & acknowledgement


This paper has been written for the “BWI werkstuk” course at the Free University (VU) in Amsterdam. This course is meant as a literature research in the final year of the study Business Mathematics & Computer Science1.


After following the course “Evolutionary computing” (EC) taught by Guszti Eiben I became inspired by the way this (r)evolutionary approach tackles large, complex problems. The different viewpoint and the natural interpretation of such algorithms seem to be very flexible and capable of solving problems while remaining simple and elegant as an algorithm. In cooperation with Guszti Eiben the subject of reviewing promising applications of this powerful solver arose.


Of course the list of problems for which evolutionary algorithms (EAs) are possible solvers laid out in this paper is not (at all) exhaustive. It intends only to give an impression of the sheer possibilities of using an evolutionary technique. Furthermore we will not go into implementation issues and specific EC-bound theory to keep the document open for people from outside the field of EC. In this paper we stress the possibilities and practical use of EC and not the shortcomings or theoretical background of EC.


For people already familiar with the concept of EC the next chapter may be skipped. It sketches the history of EC, the basic concepts in building an EA and discusses the types of problems where to it can be applied. In chapter 3 we determine a scope for chapter 4. In this chapter a categorized list is given of promising application areas. For all of the categories we state the nature of the problem and how EC can be incorporated as a solver to get better solutions.

2. Explaining evolutionary algorithms

2.1. A short history


Evolutionary computing (EC) is a relatively new field in the Artificial Intelligence (AI). If we look at its history we see that around the forties and fifties the initial ideas for using an evolutionary approach for solving problems where developed. In the sixties these ideas materialized into different algorithmical structures all sharing an evolutionary component. Three different evolutionary streams formed all invented by separate researchers. Not in any specific order these where Evolutionary Programming (EP) by Lawrence Fogel, Genetic Algorithms (GA) by J. Holland and Evolution Strategies (ES) by I. Rechenberg/H. Schewefel. Though debated continuously throughout EC history which algorithm had the most potential as a problem solver, these streams displayed huge resemblances in their way of solving things but all of them had their own typical features and successful problem solving characteristics (see [4]). In the nineties Genetic Programming (GP) by J. Koza was born which can be seen as a generalization of GAs. Only from then on these four streams blended into one specific area in the AI, Evolutionary Computing.


The main difference between these four types of Evolutionary Algorithms (EAs) is the representation they use to model decision problems, something that turned out to be vital for the effectiveness of the algorithm [8]. What they have in common is their approach to tackle problems by using the Darwinian principle of natural selection. As Darwin noticed in the mid nineteenth century, biological organisms seem to evolve over time. This evolvement or evolution seems to create environmentally adapted (and thus “better” or as Darwin proposed “fitter”) species, as each species would breed new generations. The adaptation process is accomplished through a process of mutation, crossover and natural selection (see also [5]). We will now show how EC adopted this principle to solve decision problems.

  1   2   3   4   5   6   7   8   9   ...   13

Похожие:

1. Introduction & acknowledgement iconAcknowledgement I am grateful to the Council of the Eugenics Society for the help they have given me, and for permitting me to see and to quote from the Society's Minute Books. Introduction

1. Introduction & acknowledgement iconAcknowledgement

1. Introduction & acknowledgement iconKeywords Workflow Management Systems, xml store, Petri net, dpnml, Reactive xml, peer-2-peer and distributed system. Acknowledgement

1. Introduction & acknowledgement iconStudents studying for Bio U117 Exam 1 should only review the sections «Introduction and terminology», «Basic chemistry», «Cells and membrane transport
...
1. Introduction & acknowledgement iconI introduction

1. Introduction & acknowledgement iconI. Introduction

1. Introduction & acknowledgement iconI. Introduction

1. Introduction & acknowledgement iconA. Introduction

1. Introduction & acknowledgement iconA. Introduction

1. Introduction & acknowledgement iconI. Introduction

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница