tutorial

Description

FrEAKFree Evolutionary Algorithm KitModule Developer’s GuideProject group 427Patrick Briest Dimo BrockhoffBastian Degener Matthias EnglertChristian Gunia Oliver HeeringMichael Leifhelm Kai PlociennikHeiko Ro¨glin Andrea SchweerDirk Sudholt Stefan TannenbaumThomas Jansen Ingo WegenerVersion 0.2February 10, 2004Contents1 Introduction 32 Basic Concepts 42.1 About Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Individuals and Populations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 The Event System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Implementing Search Spaces 103.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Implementing the Search Space Permutation . . . . . . . . . . . . . . . . . . 103.3 Dimension and Size of Search Spaces . . . . . . . . . . . . . . . . . . . . . . . 113.4 The Genotype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.5 Finishing the Implementation of Permutation . . . . . . . . . . . . . . . . . . 154 Implementing Fitness Functions and Fitness Transformers 174.1 Overview of Fitness Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 The Class AbstractSingleObjectiveFitnessFunction . . . . . . . . . . . . . . . 184.3 The Class ...

Informations

• Publié par: Zewyer
• Nombre de lectures: 15
• Langue: English

Extrait

FrEAK

Free Evolutionary Algorithm Kit

Module Developer’s Guide

Project group 427

Patrick Briest Dimo Brockhoff Bastian Degener Matthias Englert Christian Gunia Oliver Heering Michael Leifhelm Kai Plociennik Heik R¨glin Andrea Schweer o o Dirk Sudholt Stefan Tannenbaum

Thomas Jansen Ingo Wegener

Version 0.2

February 10, 2004

Contents

1 Introduction 2 Basic Concepts 2.1 About Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Individuals and Populations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 The Event System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Implementing Search Spaces 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Implementing the Search SpacePermutation. . . . . . . . . . . . . . .. . . 3.3 Dimension and Size of Search Spaces . . . . . . . . . . . . . . . . . . . . . . . 3.4 The Genotype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Finishing the Implementation ofPermutation. . . . . . . . . . . . . . . . . . 4 Implementing Fitness Functions and Fitness Transformers 4.1 Overview of Fitness Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The ClassA. . . . . . . . . . . .bstractSingleObjectiveFitnessFunction . . . 4.3 The ClassA. . . . . . . . . . . .bstractMultiObjectiveFitnessFunction . . . . 4.4 The ClassAbstractStatiniScOelgcejbevittnFisFesctunnio. . . . . . .. 4.5 The ClassAbstStatractOitluMcievitcejbsFestnFinioctun. . . . . . . .. 4.6 ImplementingOneMax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Overview of Fitness Transformers . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 The InterfacerasTfonserrmiFsent. . . . . . . . . . . . . . . . . .. . . . . 4.9 ImplementingrmeoriffAfsnarTen. . . . . . . . . . . . . . . . . . . . . . . . 5 Implementing Genotype-Mappers 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 The InterfaceMapper. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5.3 Implementing theStrtiBappeingMr. . . . . . . . . . . . . . . . . .. . . . . 6 Implementing Operators 6.1 Available Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 General Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Plugging yourOperatorinto FrEAK. . . . . . . . . . . . . . . . . . . . . . . 6.4 ImplementingonrofinUitceleSm. . . . . . . . . . . . . . . . . . . .. . . . .

1

3 4 4 5 6 7 10 10 10 11 13 15 17 17 18 18 19 20 20 22 22 23 27 27 28 28 30 30 31 31 32

6.5 Extending Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Floating Number of Ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Implementing Parameter Controllers 7.1 Adding Parameters to a Parameter Controller . . . . . . . . . . . . . . . . . . 7.2 Accessing Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Unassigned Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.2 An example event handling method . . . . . . . . . . . . . . . . . . . 8 Implementing Population Models 8.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 The ClassnageonMartcartsbAitalupoP. . . . . . . . . . . . . . . . . . . . . 8.3 ImplementingtsPlaraMlelitlurats. . . . . . . . . . . . . . . . . . . . . . . 9 Implementing Stopping Criteria 9.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 The ClassrCtireoitSpoipgnnstAbctra. . . . . . . . . . . . . . . . .. . . . 9.3 The ClasscaGtnereAsbrtiretnoinpprigCioattonS. . . . . . . . . . . . . . 9.4 ImplementingeRcamimuOtpdhe. . . . . . . . . . . . . . . . . . . . . . . . . . 10 Implementing Observers 10.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 ImplementingAverentiFegass. . . . . . . . . . . . . . . . . . . .. . . . . . 11 Implementing Views 11.1 Implementig Views with FrEAK Swing Models . . . . . . . . . . . . . . . . . 11.1.1 Views Using Text Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Views Using Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Implementing FrEAK Swing Models . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 FrEAK Swing Models for Text Fields . . . . . . . . . . . . . . . . . . 11.2.2 FrEAK Swing Models for Tables . . . . . . . . . . . . . . . . . . . . . 12 Advanced Concepts 12.1 Configurable Modules and Inspectors . . . . . . . . . . . . . . . . . . . . . . . 12.1.1 The InterfaceConfigurable. . . . . . . . . . . . . . . . . .. . . . . 12.1.2 The Standard Inspector . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.3 Customizing Inspectors . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 How to Deal with Property Constraints . . . . . . . . . . . . . . . . . . . . . 12.2.1 Modules with Independent Properties . . . . . . . . . . . . . . . . . . 12.2.2 Modules with Interdependent Properties . . . . . . . . . . . . . . . . . 12.3 How to Cope with Dependencies among Modules . . . . . . . . . . . . . . . . 12.3.1 Indicating Incompatibilities withtestSchedule. . . . . . . . . . . . . 12.3.2 Adjusting Modules to a Modified Schedule viainitialize. . . . . . 12.3.3 Altering other Modules on your Module’s Own . . . . . . . . . . . . . 12.4 The Tag System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.5 Using Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

37 37 38 39 39 39 40 41 41 41 42 44 44 44 45 45 48 48 48 52 52 53 55 60 61 62 65 65 65 67 67 68 68 69 69 69 71 72 72 73

Chapter 1

Introduction

This document describes how to adapt and extend FrEAK to requirements which are not met by the basic system. It is possible to include new modules like, e.g., search spaces, fitness functions, and operators. To make the text more readable and to make it easier for the reader to navigate through the source code, we use a font convention in the following. When a notion is first introduced, it is printed inthis fontthere is a corresponding class or, and if method in the Java sources of FrEAK, its name is printed inthis fontin parantheses after the notion introduced. The programming language used in FrEAK is Java. The system consists of two parts. On the one hand, there are the core system and the GUI which make up the basic functionality of FrEAK and provide a general framework for the creation and simulation of evolutionary algorithms. On the other hand, there are lots ofmodules(Module) that represent components of evolutionary algorithms and bring this framework alive. FrEAK has been designed to be expandable so that new modules can be implemented and added easily. So here, you learn how to create your own modules and fit them into the framework of FrEAK. Every time FrEAK is started, it parses its package structure, collects all modules it finds and offers them for use. Therefore, extending the system with further modules means simply implementing, compiling, and copying them into the right directory. Chapter 2 explains the basic concepts of FrEAK. The following Chapters refer to these basic concepts, so if you want to gain full understanding of how modules work, you should start reading there. If you want to dive into the creation of specific modules directly, you can skip Chapter 2 and start reading the Chapters 3 to 11. Here the shortest ways to implementing modules with basic functionality are explained. Chapter 12 then presents some of the advanced concepts of FrEAK. So, if you want to make use of all the functionality provided with FrEAK, you may find some inspiration there.

3

Chapter 2

Basic Concepts

In this chapter, we have a look at some fundamental concepts which have to be known when implementing modules for FrEAK. This gives a better understanding of the internal structure of FrEAK that will help you to understand the following chapters about implementing specific modules.

2.1 About Modules

Modules are components used to create and simulate evolutionary algorithms. E.g., search spaces, fitness functions, and operators are modules. There are several different types of modules that used within aschedule are objects that contain all the information. Schedules to run a simulation of evolutionary algorithms. To learn more about schedules, please refer to theUser’s Guide. FrEAK uses a hierarchy of interfaces to define modules and the different types of modules (SearchSpace,noitcnuFssentiF Parallel to that, there is a hierarchy of abstract, etc.). classes (stAbctraraeSpShceca,ractFitnessFunctointsbA implement the cor- that, etc.) responding interfaces and provide functionality that is commonly used in most modules. So, when writing your own module, you don’t have to start from scratch. Instead, you can extend the abstract class that is closest to your type of module and be sure that much work will be done by the abstract class. The abstract classes for the different types of modules, e.g.,ecapShcraeSttscbaArand AbstractFitnessFunction, are explained in detail in the corresponding chapters.

The InterfaceModule

At the top of the module hierarchy in FrEAK stands the interfaceModule interface. This contains the following three methods that shall be explained here. (The other methods will be explained later on in different contexts.)

4

public String getName() public String getDescription() public void testSchedule(Schedule schedule) throws UnsupportedEnvironmentException The first two methods are for GUI displaying purposes. The methodgetName()should return a human readable, very short description of what the module is or does. This name is then displayed in lists of modules within the GUI. The second methodtDesgeitnorcpi)(should return a longer description of what the module does, which informs the user more precisely about the functionality of the module. The methodtestScheduleby FrEAK to determine whether the module is ableis used to run within the current schedule. Some modules depend on other parts of the sched- ule, e.g., some selection operators require the schedule to have a single objective fitness function. Modules that are not able to run within the specified schedule simply throw an UnsupportedEnvironmentExceptionto indicate that they are not to be used in the schedule. Section 12.3.1 in the advanced concepts chapter explains the application of this method in detail.

2.2 Properties Modules may have attributes which determine their behavior and which may be edited in the GUI. These attributes are calledproperties(Property). There is a property system in FrEAK to make it easier to implement such properties. First of all, there is an interfaceConfigurablethat is to be implemented by modules that use properties. This interface is described in detail in Section 12.1.1, but you don’t need to worry about it because the abstract classes already implement all necessary methods. So, if you stick to the abstract classes, theConfigurableinterface is just a tag interface indicating that this module can be configured. So what’s important here is that the GUI enables configuration of a module only in case the module implements the interfaceConfigurable. Tip: If you create modules with properties, don’t forget to implement theConfigurableinter- face. Without the interface, the GUI won’t show a configuration dialog for your module. One fundamental concept of properties in FrEAK is that properties are not of primitive types but instances of classes. This means that if you want to use a property of a primitive type, you must wrap it in the wrapper class provided injava.lang. The only thing you have to do to make properties visible to the system is write getter and setter methods for them. By convention, the method signatures for a property with name “X” and type “Type” are public void setPropertyX(Type) public Type getPropertyX()

5

As an example, we want to have a property named “Probability” of type float in our class. The attribute, getter, and setter method could look like this: private float probability; public Float getPropertyProbability(){ return(new Float(probability)); } public void setPropertyProbability(Float f){ probability = f.floatValue(); } Tip: In case you write a module that modifies properties within other modules, you should read Section 12.3 in the advanced concepts chapter. There, problems with dependencies among modules are described and possible solutions are presented.

Descriptions of Properties There are two methods you can implement to give the user information about your properties. For a property with name “X” these are: public String getShortDescriptionForX() public String getLongDescriptionForX() In the case ofrtDescrigetSho(X)tpoiFnrothe method should return a name or a very short description of the property. This description is used in the GUI in tables where values of properties are set. Therefore, the description must be short. The method)(LtnoegcripgDesForXtionshould return a longer description which is used in the GUI for telling the user in more detail what this property is about.

2.3 Individuals and Populations Most of the module types work with individuals, so you should know how individuals are represented in FrEAK.

Individuals Individuals are instances of the classIndividualand contain a genotype, a list oftags, and a date of birth that represents the generation the individual was created in. The tag system is an advanced concept that is explained later on in Section 12.4. Individuals are to be handled read-only, so variation operators that modify genotypes or tags have to create new individuals instead of modifying attributes directly. 6

Populations Individuals are passed through the graph wrapped in so-called individual lists. This is a simple data structure providing an order of the individuals contained and random access by positions. The appendant interfacenIstLividialduprovides simple operations like adding, accessing, and removing individuals. Furthermore, you may access individuals by theirrank, i.e. a position of the individual inside a sequence sorted by fitness values. So, is it easy to access a best individual or the set of best individuals, to be correct. For names and details on the methods provided byIiLsltsvidnaudi, please look at the javadoc documentation of the class. Please note thatndivIsiLlaudist when an operatorare to be handled read-only, too. So, wants to add, remove, or exchange individuals, a newtlLisiduandivIhas to be created prior to the modifications. Tip: Please keep in mind that individuals as well as individual lists are to be handled read- only and must not be modified directly. You should therefore always work on clones instead of the original objects if you intend to perform modifications. Setting new at- tributes directly or altering the original list may cause unpredictable results, such as ConcurrentModificationExceptions. AsLlsitdnIvidiau this purpose, you Foris an interface, it cannot be instantiated directly. may use the classPopulationthat implementsstLialduvidiInand is backed by an instance ofjva.atu.AilayrrstLi.

2.4 The Event System

There is an event system in FrEAK which is used by many modules of the system. For example, there are modules calledobserverswhich use the event system to observe parts of the simulated algorithm. We will later look more closely at observers in Chapter 10. For now, we only take them as a motivation to look at the event system.

The Event Interfaces Infreak.core.eventwe find the event interfaces used in FrEAK. For each event defined, there are three interfaces. For example, the interfaces associated with theRunEventevent which is fired each time a run is started or finished, areRunEvent,netsiLtnrevenERu, and RunEventSource. The most important method (for you as the developer of modules) is the event handling method in the event listener interface. In some of these interfaces, there are multiple event handling methods. You can take a look at some of the interfaces in the package to get an impression of these methods.

7

Working with Events As an example, imagine anObserverthat puts out the best observed individual within the current run. This observer can either observe the current population or it can focus on individuals flowing out of an operator, e.g., to determine which variation operator produces the best results. Our observer must be informed of two things. Firstly, it must be informed when new individ- uals are to be observed at the event source. Secondly, it must be informed when the current run is finished to be able to reset the attribute containing the best individual. The observer would then implement the following two event listener interfaces:

IndividualListEventListener RunEventListener

These listener interfaces contain methods that are called when an event is fired, as you probably know from other event systems like e.g. in Java Swing. What’s different in FrEAK is the event registering procedure.

Registering at the Event System Due to the flexibility of FrEAK, some modules in the schedule may be replaced by other modulesatanytime.So,eventsourcesthatalreadycontaineventlistenersmaygetlost.To avoid this problem, FrEAK uses a central class to integrate modules in the event system and to keep track of changes in event sources. This class it called theevent controller (ContveEllretnor All modules have to register at the event controller) of the schedule. to receive events. Tip: It is necessary that event registration takes place by means of the schedule’s event controller. In case you add an event listener to an event source directly, the event system will be deranged if either the event source or the event listener is replaced by another module. Before we can understand the event registering code we have to know a distinction within the FrEAK event system:staticandnon-staticevents. This concept is easy to understand: Sometimes, you already know at compile time which object will send the event you want to receive. For example, our observer class knows that theRunEventevent it wants to receive will be sent by theSchedule events are called. Such static. On the other hand, it may be that the event source for your events is not known until run time. In case of our observer, it is intended that the event source for thednviIuaidislLvetEnt can be set by the user at run time. Such events are called non-static. The interfaceModuleprovides a method()entsetvErcaeto register event listeners at event sources. This method is called by the event system at the right time to give modules the

8

opportunity to register themselves. Events are then registered by calling anaddEventmethod provided by the event controller. Tip: Don’t forget to register your module to events, or else your module won’t receive any events! Let’s take a look at the implementation ofcreateEventsas it might look like in our observer.

public void createEvents() { EventController eventController = getSchedule().getEventController(); eventController.addEvent(this, RunEvent.class, getSchedule()); eventController.addEvent(this, "Get individuals from", IndividualListEvent.class, getSchedule().getPopulationManager()); }

From the schedule, theEllroerntventCois retrieved and theaddEventmethods are called. The distinction between static and non-static events is made by calling the right method. There are threeaddEventmethods in thellerEevtnoCtnorclass:

addEvent(EventListener l, Class type, EventSource s) addEvent(EventListener l, String name, Class type) addEvent(EventListener l, String name, Class type, EventSource s)

The first one is for static events. Our observer calls this method to register at the schedule forRunEvents. TheEventListener, the type of the event and the desiredEventSource are passed and that is all that has to be done. The type of event is the javaClassobject representing the interface for the event. In the source code above you can see how this argument is constructed. The next two methods are for non-static events. TheStringpassed is for GUI displaying purposes so the user can see what kind of event is handled. The observer tells the GUI to display the string ”Get individuals from”. The last method contains an additional optional argument to set a default event source for the module. This is the case in our observer: the default event source is the schedule’s population manager that contains the current population. (To learn more about population managers, refer to Chapter 8 or the User’s Guide.) So, by default, our observer observes the current population. But since this event is non-static, the user is able to alter the event source in the GUI and to choose, e.g., the outport of a mutation operator instead.

9

Chapter 3

Implementing Search Spaces

3.1 Overview

The selection of a search space is central to every evolutionary algorithm. The search space is the place where thegenotypes Forof the individuals live in. example, a very common search space is the set{01} n search space is one of the standard search spaces contained. This  in FrEAK, it is calledBit String a new search space in FrEAK is not very. Implementing complicated, it is demonstrated using the example of the search spacePermutationin the following section.

3.2 Implementing the Search SpaceutrmioatneP

We want to extend FrEAK with a new search space which represents the set of all permu- tations in thesymmetric groupS n . For instance, the fitness functionSortworks on this search space. Search spaces in FrEAK must implement the interfaceSearchSpaceand must be placed in the packagerfae.komudle.searchspace Insteador in one of its subpackages. of implementing all methods by hand, you should extend the classaecrcaStsbrtAcepahS because this class by default implements the InterfaceSearchSpaceand contains default implementations of the methods in the interfacesModule(see Chapter 2.1) already. start We with implementing some methods from the interfaceModulewhich provide a name and a description of the search space which can be displayed in the GUI.

public class Permutation extends AbstractSearchSpace implements Configurable, HasDimension { private int dimension; public Permutation(Schedule schedule) { super(schedule); dimension = 40;

10