![]() |
|||
![]()
|
![]() |
![]() |
![]() |
3.1.3. Genetic Algorithm Approach Implementation of a genetic algorithm (GA) approach for GUESS is done using the Evolutionary Object System (EOS) developed by Man Machine Interfaces, Inc. EOS is a C++ class library for creating genetic algorithms. The first decision that must be made is how to encode the schedule information as a chromosome. The standard encoding used in most classical genetic algorithm work is binary encoding. Each gene with the chromosome is a series of bits. The genes are linked together to build a long chromosome. EOS supports a variety of other possible encodings; however, the binary encoding is the most generic and was also recommended by the EOS vendor; so the decision was made to use the binary encoding in the implementation of a genetic algorithm within GUESS. The only significant variable information associated with the schedule is the time at which each event is scheduled to occur. GUESS assumes that the duration of an event is fixed and determined by the user at the time the event is entered; therefore, the only significant information that must be associated with the event is the starting time of the event. Each event has a specific gene within the chromosome. The gene occupies a series of bits of size Time that are sufficient to record the starting time of an event. The calculation of fitness comprises the core of the genetic algorithm. The basis of calculating the fitness was chosen to be the schedule satisfaction normalized to a positive number. Division by the number of events that cannot be scheduled (due to resource conflicts) is done to impose a stiff penalty to resource constraint violations. Without the penalty, the genetic algorithm tends to produce solutions with unschedulable events in alarming frequency. After experimentation, it was decided that an elitist replacement strategy with a uniform crossover breeding approach would be used. The elitist replacement strategy replaces the worst individuals in the next generation with the best individuals from the current generation. This strategy was used because it appeared during preliminary analysis that some of the good solutions were being lost in the reproduction process. Uniform crossover mates two chromosomes by introducing a randomly generated crossover mask. Genes represented by bits set in the mask are taken from the mother; genes represented by cleared bits in the mask are taken from the father. This appeared to give the best results in the trials. A population size of 10 and allowing the algorithm to continue for 10 generations before stopping gives excellent results. The genetic algorithm yields very tight compact schedules with events scheduled in the minimum time span required. By contrast, while satisfying the schedule constraints, the traditional methods, namely suggestion tabulator and hill climbing, tend to do so by spreading out the schedule and increasing the schedule makespan. The length of time that the genetic algorithm takes is due mainly to the need to calculate schedule satisfaction for multiple schedules each generation. Compounding this is the requirement to process many generations before arriving at the solution. By contrast, the hill climbing and suggestion tabulator deal with the schedule in a much more localized manner. Each event has its satisfaction calculated individually and is then moved accordingly, resulting in fewer satisfaction calculations in arriving at a final solution.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |