The Computational Beauty of Nature
Computer Explorations of Fractals, Chaos,
Complex Systems, and Adaptation

About the Book
  · title page
  · home*
  · cover artwork
  · jacket text
  · table of contents
  · the author*
  · ordering information
Book Contents
  · three themes
  · part synopses
  · selected excerpts
  · all figures from book
  · quotes from book
  · glossary from book
  · bibliography
  · slide show
Source Code
  · overview &
  · FAQ list*
  · download source code
  · java applets
  · news*
  · reviews & awards
  · errata
  · for educators
  · bibliography (BibTeX format)
  · other links
GATASK Documentation



       gatask - solve a task assignment problem via a genetic


       gatask -help
       gatask [-specs string]  [-size  integer]  [-gens  integer]
              [-seed  integer]  [-crate  double]  [-mrate double]
              [-pbase double]


       Use a genetic algorithm to solve a task assignment problem
       with  user-specified  costs.  This program illustrates how
       GAs can perform combinatorial optimization.   Reproduction
       of  strings  entails special crossover and mutation opera-
       tions which preserve constraints on the form  of  feasible
       solutions with strings being selected based on fitness.


       -specs string
              Problem specification file.

       -size integer
              Population size.

       -gens integer
              Number of generations.

       -seed integer
              Random seed.

       -crate double
              Crossover rate.

       -mrate double
              Mutation rate.

       -pbase double
              Exponentiation base.


       Feasible  solutions  are  represented  as  an array of LEN
       integers which must contain all integers between 0 and LEN
       -  1 to denote which person performs which task.  As such,
       the mutation and crossover operators  have  to  be  subtly
       redefined  so  that candidate solutions are still feasible
       after they are crossed and mutated.

       For mutation, we simply swap two locations in  a  solution

       Crossing two solutions is a little more complicated.  Con-
       sult the source code to see how it's done in a manner that

       preserves the feasibility of the two children while blend-
       ing portions of each parent solution.

       The fitness function works in  three  steps.   First,  the
       score of a solution is calculated and denoted the raw fit-
       ness.  The scaled fitness is then set  to  pow(PBASE,  raw
       fitness  -  worst raw fitness).  The normalized fitness is
       then set to the scaled fitness divided by the sum  of  the
       scaled  fitnesses.   Thus  the  sum of the normalized fit-
       nesses must be equal to one while  a  string  with  a  raw
       score  of one better than another string is PBASE times as
       likely to reproduce, where PBASE  is  the  value  supplied
       with the -pbase option.


       No  sanity  checks  are performed to make sure that any of
       the options make sense.


       Copyright (c) 1997, Gary William Flake.

       Permission granted for any use according to  the  standard
       GNU ``copyleft'' agreement provided that the author's com-
       ments are neither modified nor removed.   No  warranty  is
       given or implied.

Copyright © Gary William Flake, 1998-2002. All Rights Reserved. Last modified: 30 Nov 2002