Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

FAQ: comp.ai.genetic part 3/6 (A Guide to Frequently Asked Questions)
Section - Q2: What applications of EAs are there?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Houses ]


Top Document: FAQ: comp.ai.genetic part 3/6 (A Guide to Frequently Asked Questions)
Previous Document: News Headers
Next Document: Q3: Who is concerned with EAs?
See reader questions & answers on this topic! - Help others by sharing your knowledge
     In   principle,   EAs  can  compute  any  computable  function,  i.e.
     everything a normal digital computer can do.

     But EAs are especially badly suited for problems where efficient ways
     of  solving  them  are  already  known,  (unless  these  problems are
     intended to serve as benchmarks).  Special purpose  algorithms,  i.e.
     algorithms  that  have  a  certain amount of problem domain knowledge
     hard coded into them, will usually outperform EAs,  so  there  is  no
     black  magic  in EC.  EAs should be used when there is no other known
     problem solving strategy, and  the  problem  domain  is  NP-complete.
     That's  where  EAs  come  into  play: heuristically finding solutions
     where all else fails.

     Following  is  an  incomplete   (sic!)    list   of   successful   EA
     applications:

 ARTIFICIAL LIFE
     ARTIFICIAL  LIFE  (ALIFE)  systems  attempt  to  simulate the kind of
     behaviour exhibited by real, living  creatures.  Not  all  Artificial
     Life systems employ EVOLUTIONARY ALGORITHMs (see Q4.1).

     Framsticks

     Framsticks  is  a three-dimensional life SIMULATION project. Both the
     physical  structure  of  creatures  and  their  control  systems  are
     evolved.  Evolutionary  algorithms are used with SELECTION, CROSSOVER
     and MUTATION.  Finite element methods are used for  simulation.  Both
     spontaneous and directed EVOLUTIONs are possible.

     This  system  uses  the  standard  EA  framework  to evolve 3D agents
     equipped with neural networks. It has proved to be an attractive tool
     for  people who want to learn about the way evolutionary OPTIMIZATION
     techniques work.

     This is shareware, but all the evolutionary  features  are  available
     free.  The  project  is open, and developers can take part in it, and
     also conduct their own experiments (i.e.   using  their  own  GENETIC
     OPERATORs).   There  are  links  to  the scientific papers on the web
     page, as well as the detailed program documentation. The software  is
     quite general and can be used to study a range of problems, including
     coevolution of body and brain.

     For more details, see: http://www.frams.poznan.pl/

 BIOCOMPUTING
     Biocomputing, or Bioinformatics, is the field of biology dedicated to
     the automatic analysis of experimental data (mostly sequencing data).
     Several  approaches  to  specific  biocomputing  problems  have  been
     described  that  involve  the  use of GA, GP and simulated annealing.
     General information about biocomputing (software,  databases,  misc.)
     can  be found on the server of the European Bioinformatics Institute:
     http://www.ebi.ac.uk/ebi_home.html ENCORE has  a  good  selection  of
     pointers  related  to  this subject.  VSCN provides a detailed online
     course       on        bioinformatics:        http://www.techfak.uni-
     bielefeld.de/bcd/Curric/welcome.html

     There  are  three  main  domains  to  which  GA  have been applied in
     Bioinformatics: protein folding, RNA folding, sequence alignment.

     Protein Folding

     Proteins are one of the essential components of  any  form  of  life.
     They  are  made of twenty different types of amino acid.  These amino
     acids are chained together in order to  form  the  protein  that  can
     contain  from  a  few  to  several thousands residues. In most of the
     cases, the properties and the function of a protein are a  result  of
     its  three  dimensional  structure.  It seems that in many cases this
     structure is a direct consequence of the sequence. Unfortunately,  it
     is  still  very  difficult/impossible to deduce the three dimensional
     structure, knowing only the sequence.  A part  of  the  VSCN  on-line
     bioinformatics  course  is  dedicated  to  the  use of GAs in Protein
     Folding Prediction. It  contains  an  extensive  bibliography  and  a
     detailed  presentation  of  the subject with LOTS of explanations and
     on-line    papers.    The     URL     is:     http://www.techfak.uni-
     bielefeld.de/bcd/Curric/ProtEn/contents.html

     Koza  [KOZA92]  gives  one  example of GP applied to Protein Folding.
     Davis [DAVIS91] gives an example of DNA  conformation  prediction  (a
     closely related problem) in his Handbook of GAs.

     RNA Folding

     Describing  the  tertiary  structure  of an RNA molecule, is about as
     hard as for a protein,  but  describing  the  intermediate  structure
     (secondary  structure)  is  somehow  easier because RNA molecules are
     using the same pairing rules as DNA, (Watson and Crick base pairing).
     There  exist deterministic algorithms that given a set of constraints
     (rules), compute the more stable structure, but: (a) their  time  and
     memory  requirement increase quadratically or more with the length of
     the sequences, and (b) they require simplified rules.  Lots of effort
     has  recently been put into applying GAs to this problem, and several
     papers can be found (on-line if your institute  subscribes  to  these
     journals):

     A genetic Algorithm Based Molecular Modelling Technique For RNA Stem-
     loop Structures H. Ogata, Y. Akiyama and  M  Kanehisa,  Nucleic  Acid
     Research, 1995, vol 23,3 419-426

     An  Annealing Mutation Operator in the GA for RNA folding B.A Shapiro
     and J. C. Wu, CABIOS, 1996, vol 12, 3, 171-180

     The computer Simulation  of  RNA  Folding  Pathway  Using  a  Genetic
     Algorithm  A.P.  Gultyaev,  F.D.H van Batenburg and C. W. A. Pleij in
     Journal of Molecular Biology, 1995, vol 250 37-51

     Simulated Annealing  has  also  been  applied  successfully  to  this
     problem:

     Description  of RNA folding by SA M. Schmitz and G. Steger in Journal
     of Molecular Biology, 1995, 255, 245-266
     Sequence Alignments

     Sequence Alignment is another important  problem  of  Bioinformatics.
     The  aim  is to align together several related sequences (from two to
     hundreds) given a cost function.  For  the  most  widely   used  cost
     functions,  the  problem  has  been shown to be NP-complete.  Several
     attempts have been made using SA:
     Multiple Sequence Alignment Using SA J. Kim, Sakti Pramanik and  M.J.
     Chung, CABIOS, 1994, vol 10, 4, 419-426

     Multiple  Sequence Alignment by Parallel SA M. Isshikawa, T. Koya and
     al, CABIOS, 1993,vol 9, 3, 267-273

     SAM, software which uses Hidden Markov Models for  Multiple  Sequence
     Alignment,  can  use  SA to train the model. Several papers have been
     published on SAM.   The  software,  documentation  and  an  extensive
     bibliography           can           be           found           in:
     http://www.cse.ucsc.edu/research/compbio/sam.html

     More recently, various software using different  methods  like  Gibbs
     sampling or GAs has been developed:

     A Gibbs Sampling Strategy for Multiple Alignment C.E. Lawrence, S. F.
     Altschull and al, Science, October 1993, vol 262, 208-214

     SAGA: Sequence Alignment by Genetic Algorithm C. Notredame  and  D.G.
     Higgins, Nucleic Acid Research, 1995, vol 24, 8,
      1515-1524

     A   beta  release  of SAGA (along with the paper) is available on the
     European   Bioinformatics    Institute    anonymous    FTP    server:
     ftp.ebi.ac.uk/pub/software/unix/saga.tar.Z

 CELLULAR PROGRAMMING: Evolution of Parallel Cellular Machines
     Nature  abounds  in systems involving the actions of simple, locally-
     interacting  components,  that  give  rise  to   coordinated   global
     behavior.   These collective systems have evolved by means of natural
     SELECTION  to  exhibit  striking  problem-solving  capacities,  while
     functioning  within a complex, dynamic ENVIRONMENT.  Employing simple
     yet versatile parallel cellular  models,  coupled  with  EVOLUTIONARY
     COMPUTATION  techniques,  cellular  programming  is  an  approach for
     constructing man-made systems that exhibit  characteristics  such  as
     those manifest by their natural counterparts.

     Parallel  cellular  machines  hold  potential both scientifically, as
     vehicles for studying phenomena of interest in areas such as  complex
     adaptive  systems  and  ARTIFICIAL  LIFE,  as  well  as  practically,
     enabling  the   construction   of   novel   systems,   endowed   with
     evolutionary,  reproductive, regenerative, and learning capabilities.

     Web site: http://lslwww.epfl.ch/~moshes/cp.html

     References:

     Sipper, M. (1997)  "Evolution  of  Parallel  Cellular  Machines:  The
     Cellular Programming Approach", Springer-Verlag, Heidelberg.

     Sipper,  M.  (1996)  "Co-evolving  Non-Uniform  Cellular  Automata to
     Perform Computations", Physica D, 92, 193-208.

     Sipper, M. and  Ruppin,  E.  (1997)  "Co-evolving  architectures  for
     cellular machines", Physica D, 99, 428-441.

     Sipper,  M.  and  Tomassini,  M.  (1996)  "Generating Parallel Random
     Number Generators By Cellular Programming", International Journal  of
     Modern Physics C, 7(2), 181-190.
     Sipper, M. (1997) "Evolving Uniform and Non-uniform Cellular Automata
     Networks", in Annual Reviews of Computational  Physics,  D.  Stauffer
     (ed)

 Evolvable Hardware
     The  idea  of  evolving  machines, whose origins can be traced to the
     cybernetics movement  of  the  1940s  and  the  1950s,  has  recently
     resurged in the form of the nascent field of bio-inspired systems and
     evolvable hardware. The field draws on ideas  from  the  EVOLUTIONARY
     COMPUTATION   domain  as  well  as  on  novel  hardware  innovations.
     Recently, the term evolware has been used to describe  such  evolving
     ware,  with  current  implementations  centering  on  hardware, while
     raising the possibility of using other forms in the future,  such  as
     bioware.   The  inaugural  workshop, Towards Evolvable Hardware, took
     place  in  Lausanne,  in  October  1995,  followed   by   the   First
     International  Conference  on  Evolvable  Systems:  From  Biology  to
     Hardware (ICES96) held in Japan, in October 1996. Another major event
     in the field, ICES98, was held in Lausanne, Switzerland, in September
     1998.

     References:

     Sipper, M. et al (1997) "A Phylogenetic, Ontogenetic, and  Epigenetic
     View   of   Bio-Inspired  Hardware  Systems",  IEEE  Transactions  on
     Evolutionary Computation, 1(1).

     Sanchez,  E.  and  Tomassini,  M.  (eds)  (1996)  "Towards  Evolvable
     Hardware",  Springer-Verlag, Lecture Notes in Computer Science, 1062.

     Higuchi,  T.  et  al  (1997)  "Proceedings  of  First   International
     Conference  on Evolvable Systems: From Biology to Hardware (ICES96)",
     Springer-Verlag, Lecture Notes in Computer Science.

 GAME PLAYING
     GAs can be used to  evolve  behaviors  for  playing  games.  Work  in
     evolutionary  GAME  THEORY  typically  surrounds  the  EVOLUTION of a
     POPULATION of players who meet randomly to play a game in which  they
     each  must  adopt  one  of  a limited number of moves. (Maynard-Smith
     1982).  Let's suppose it is just two moves,  X  and  Y.  The  players
     receive  a reward, analogous to Darwinian FITNESS, depending on which
     combination of moves occurs and which  move  they  adopted.  In  more
     complicated models there may be several players and several moves.

     The  players  iterate such a game a series of times, and then move on
     to a new partner. At the end of all such moves, the players will have
     a cumulative payoff, their fitness.  This fitness can then be used to
     generate a new population.

     The real key in using a  GA  is  to  come  up  with  an  encoding  to
     represent  player's strategies, one that is amenable to CROSSOVER and
     to MUTATION.  Possibilities are to suppose at each iteration a player
     adopts  X with some probability (and Y with one minus such). A player
     can thus be represented as a real number, or  a  bit-string  suitably
     interpreted as a probability

     An  alternative  characterisation  is  to model the players as Finite
     State Machines, or Finite Automata (FA). These can be though of as  a
     simple  flow chart governing behaviour in the "next" play of the game
     depending upon previous plays. For example:

	  100 Play X
	  110 If opponent plays X go to 100
	  120 Play Y
	  130 If opponent plays X go to 100 else go to 120
     represents a strategy that does whatever its opponent did  last,  and
     begins  by  playing  X,  known as "Tit-For-Tat." (Axelrod 1982). Such
     machines can readily be encoded as bit-strings. Consider the encoding
     "1  0  1  0 0 1" to represent TFT.  The first three bits, "1 0 1" are
     state 0. The first bit, "1" is interpreted as "Play  X."  The  second
     bit,  "0"  is interpreted as "if opponent plays X go to state 1," the
     third bit, "1", is interpreted as "if the opponent  plays  Y,  go  to
     state  1."   State 1 has a similar interpretation. Crossing over such
     bit-strings always yields valid strategies.
     SIMULATIONs in the Prisoner's dilemma have been  undertaken  (Axelrod
     1987, Fogel 1993, Miller 1989) of these machines.

     Alternative   representations  of  game  players  include  CLASSIFIER
     SYSTEMs (Marimon, McGrattan and Sargent 1990, [GOLD89]), and  Neural-
     networks  (Fogel and Harrald 1994), though not necessarily with a GA.
     (Fogel  1993),  and  Fogel  and  Harrald  1994  use  an  Evolutionary
     Program).  Chellapilla and Fogel (1999) have evolved a neural network
     which can play checkers (draughts) at near expert level.

     Other methods of evolving a population can be found in Lindgren 1991,
     Glance and Huberman 1993 and elsewhere.

     A  GA  for  playing  the  game  "Mastermind"  has  been produced. See
     http://kal-el.ugr.es/mastermind

     References.

     Axelrod, R. (1987) ``The Evolution  of  Strategies  in  the  Repeated
     Prisoner's Dilemma,'' in [DAVIS91]

     Axelrod,  R  (?) ``The Complexity of Cooperation'' (See the web site,
     which     includes      code      to      implement      tournaments:
     http://pscs.physics.lsa.umich.edu/Software/ComplexCoop.html )

     Chellapilla,  K. and Fogel, D.B. (1999) ``Evolution, neural networks,
     games, and intelligence'' , Proc. IEEE, Sept., pp. 1471-1496.

     Miller, J.H. (1989) ``The Coevolution of  Automata  in  the  Repeated
     Prisoner's Dilemma'' Santa Fe Institute Working Paper 89-003.

     Marimon,  Ramon, Ellen McGrattan and Thomas J. Sargent (1990) ``Money
     as a Medium of Exchange in an Economy with  Artificially  Intelligent
     Agents'' Journal of Economic Dynamics and Control 14, pp. 329--373.

     Maynard-Smith, (1982) Evolution and the Theory of Games, CUP.

     Lindgren, K. (1991) ``Evolutionary Phenomena in Simple Dynamics,'' in
     [ALIFEI].

     Holland, J.H and John Miller (1990) ``Artificially Adaptive Agents in
     Economic  Theory,''  American Economic Review: Papers and Proceedings
     of the 103rd Annual Meeting of the  American  Economics  Association:
     365--370.

     Huberman,  Bernado,  and  Natalie  S.  Glance  (1993)  "Diversity and
     Collective  Action"   in   H.   Haken   and   A.   Mikhailov   (eds.)
     Interdisciplinary Approaches to Nonlinear Systems, Springer.

     Fogel  (1993)  "Evolving Behavior in the Iterated Prisoner's Dilemma"
     Evolutionary Computation 1:1, 77-97

     Fogel, D.B. and Harrald, P. (1994) ``Evolving  Complex  Behaviour  in
     the  Iterated  Prisoner's Dilemma,'' Proceedings of the Fourth Annual
     Meetings of the Evolutionary Programming Society, L.J. Fogel and A.W.
     Sebald eds., World Science Press.

     Lindgren,  K. and Nordahl, M.G.  "Cooperation and Community Structure
     in Artificial Ecosystems", Artificial Life, vol 1:1&2, 15-38
     Stanley, E.A.,  Ashlock,  D.  and  Tesfatsion,  L.  (1994)  "Iterated
     Prisoners  Dilemma  with Choice and Refusal of Partners in [ALIFEIII]
     131-178

 JOB-SHOP SCHEDULING
     The Job-Shop Scheduling  Problem  (JSSP)  is  a  very  difficult  NP-
     complete problem which, so far, seems best addressed by sophisticated
     branch and bound search techniques.   GA  researchers,  however,  are
     continuing  to  make  progress  on  it.   (Davis  85)  started off GA
     research on  the  JSSP,  (Whitley  89)  reports  on  using  the  edge
     RECOMBINATION operator (designed initially for the TSP) on JSSPs too.
     More recent work includes (Nakano 91),(Yamada & Nakano 92), (Fang  et
     al.  93).   The  latter  three  report increasingly better results on
     using GAs on fairly large benchmark JSSPs (from Muth & Thompson  63);
     neither  consistently  outperform branch & bound search yet, but seem
     well on the way. A crucial aspect  of  such  work  (as  with  any  GA
     application)  is  the  method  used to encode schedules. An important
     aspect of some of the recent work on this is that better results have
     been  obtained  by  rejecting the conventional wisdom of using binary
     representations  (as  in  (Nakano  91))  in  favor  of  more   direct
     encodings.  In  (Yamada  & Nakano 92), for example, a GENOME directly
     encodes operation completion times, while in (Fang et al. 93) genomes
     represent  implicit instructions for building a schedule. The success
     of these latter techniques, especially since their  applications  are
     very  important  in  industry, should eventually spawn advances in GA
     theory.

     Concerning the point of using GAs at all on hard job-shop  scheduling
     problems,  the  same  goes here as suggested above for `Timetabling':
     The  GA  approach  enables  relatively  arbitrary   constraints   and
     objectives  to  be incorporated painlessly into a single OPTIMIZATION
     method.  It  is  unlikely  that  GAs  will   outperform   specialized
     knowledge-based  and/or  conventional  OR-based  approaches  to  such
     problems in terms of raw solution quality,  however  GAs  offer  much
     greater  simplicity  and flexibility, and so, for example, may be the
     best method for quick high-quality solutions, rather than finding the
     best  possible  solution at any cost. Also, of course, hybrid methods
     will have a lot to offer, and GAs are far easier to parallelize  than
     typical knowledge-based/OR methods.

     Similar  to  the  JSSP  is  the  Open Shop Scheduling Problem (OSSP).
     (Fang et al. 93) reports an initial attempt at using  GAs  for  this.
     Ongoing  results  from  the same source shows reliable achievement of
     results within less than 0.23% of optimal on moderately  large  OSSPs
     (so  far,  up  to  20x20), including an improvement on the previously
     best known solution for a benchmark 10x10 OSSP. A simpler form of job
     shop  problem  is the Flow-Shop Sequencing problem; recent successful
     work on applying GAs to this includes (Reeves 93)."

     Other scheduling problems

     In contrast  to  job  shop  scheduling  some  maintenance  scheduling
     problems  consider  which  activities  to  schedule  within a planned
     maintenance period, rather than seeking to minimise  the  total  time
     taken  by the activities. The constraints on which parts may be taken
     out of service for  maintenance  at  particular  times  may  be  very
     complex,  particularly as they will in general interact. Some initial
     work is given in (Langdon, 1995).

     References

     Davis, L.  (1985)  "Job-Shop  Scheduling  with  Genetic  Algorithms",
     [ICGA85], 136-140.

     Muth,  J.F. & Thompson, G.L. (1963) "Industrial Scheduling". Prentice
     Hall, Englewood Cliffs, NJ, 1963.
     Nakano, R.  (1991)  "Conventional  Genetic  Algorithms  for  Job-Shop
     Problems", [ICGA91], 474-479.

     Reeves,  C.R.  (1993)  "A Genetic Algorithm for Flowshop Sequencing",
     Coventry Polytechnic Working Paper, Coventry, UK.

     Whitley, D., Starkweather,  T.  &  D'Ann  Fuquay  (1989)  "Scheduling
     Problems  and  Traveling  Salesmen:  The  Genetic  Edge Recombination
     Operator", [ICGA89], 133-140.

     Fang, H.-L., Ross,  P.,  &  Corne  D.  (1993)  "A  Promising  Genetic
     Algorithm  Approach  to Job-Shop Scheduling, Rescheduling & Open-Shop
     Scheduling Problems", [ICGA93], 375-382.

     Yamada, T. & Nakano, R. (1992) "A  Genetic  Algorithm  Applicable  to
     Large-Scale Job-Shop Problems", [PPSN92], 281-290.

     Langdon,  W.B.  (1995)  "Scheduling  Planned  Maintenance of the (UK)
     National Grid", cs.ucl.ac.uk/genetic/papers/grid_aisb-95.ps

 MANAGEMENT SCIENCES
     "Applications of EA in management science and closely related  fields
     like organizational ecology is a domain that has been covered by some
     EA researchers - with considerable bias towards scheduling  problems.
     Since  I believe that EA have considerable potential for applications
     outside  the  rather  narrow  domain  of   scheduling   and   related
     combinatorial  problems,  I  started  collecting references about the
     status quo of EA-applications in  management  science.   This  report
     intends  to  make  available  my findings to other researchers in the
     field. It is a short  overview  and  lists  some  230  references  to
     current as well as finished research projects.  [..]

     "At  the end of the paper, a questionnaire has been incorporated that
     may be used for this purpose. Other comments are also appreciated."

     --- from the Introduction of (Nissen 93)

     References

     Nissen, V. (1993) "Evolutionary Algorithms in Management Science:  An
     Overview  and List of References", Papers on Economics and Evolution,
     edited by the European Study Group for Evolutionary Economics.   This
     report     is     also     avail.     via     anon.      FTP     from
     ftp.gwdg.de/pub/msdos/reports/wi/earef.eps

     Boulding, K.E. (1991) "What is evolutionary economics?",  Journal  of
     Evolutionary Economics, 1, 9-17.

 NON-LINEAR FILTERING
     New  connections  between GENETIC ALGORITHMs and Non Linear Filtering
     Theory have been established.  GAs  have  already  been  successfully
     applied  to  a  large  class of non-linear filtering problems such as
     RADAR / SONAR/ GPS signal processing.  This relatively new branch  of
     GA  application  has  also  lead to new results on the convergence of
     GAs: large deviations, fluctuations...

     Some preprints and references on this topic are available in the  web
     page: http://www-sv.cict.fr/lsp/Delmoral/index.html

     The  new  results  also  points out some natural connections between:
     genetic type algorithms,  information  theory,  non-linear  filtering
     theory, interacting and branching particle systems.

 TIMETABLING
     This  has  been addressed quite successfully with GAs.  A very common
     manifestation of this kind of problem is the timetabling of exams  or
     classes in Universities, etc.

     The  first application of GAs to the timetabling problem was to build
     the schedule  of  the  teachers  in  an  Italian  high  school.   The
     research,  conducted at the Department of Electronics and Information
     of Politecnico di Milano, Italy, showed that a GA was as good as Tabu
     Search,  and  better  than  simulated  annealing,  at finding teacher
     schedules satisfying a number of  hard  and  soft  constraints.   The
     software package developed is now in current use in some high schools
     in Milano. (Colorni et al 1990)

     At  the  Department  of  Artificial   Intelligence,   University   of
     Edinburgh, timetabling the MSc exams is now done using a GA (Corne et
     al. 93, Fang 92). An example  of  the  use  of  GAs  for  timetabling
     classes is (Abramson & Abela 1991).

     In  the  exam  timetabling  case,  the  FITNESS function for a GENOME
     representing a timetable involves computing degrees of punishment for
     various  problems  with  the timetable, such as clashes, instances of
     students having to take  consecutive  exams,  instances  of  students
     having  (eg)  three  or  more  exams  in one day, the degree to which
     heavily-subscribed exams occur late in  the  timetable  (which  makes
     marking harder), overall length of timetable, etc. The modular nature
     of the fitness function has the key to the main potential strength of
     using  GAs  for  this  sort of thing as opposed to using conventional
     search and/or constraint programming methods. The  power  of  the  GA
     approach  is  the  ease  with  which it can handle arbitrary kinds of
     constraints and  objectives;  all  such  things  can  be  handled  as
     weighted  components of the fitness function, making it easy to adapt
     the GA to the  particular  requirements  of  a  very  wide  range  of
     possible overall objectives . Very few other timetabling methods, for
     example, deal with such objectives at all, which shows how  difficult
     it  is  (without  GAs)  to  graft  the  capacity  to handle arbitrary
     objectives onto the basic "find shortest- length  timetable  with  no
     clashes"  requirement.  The  proper  way  to  weight/handle different
     objectives in the fitness function in  relation  to  the  general  GA
     dynamics remains, however, an important research problem!

     GAs thus offer a combination of simplicity, flexibility & speed which
     competes very favorably with other approaches, but  are  unlikely  to
     outperform   knowledge-based  (etc)  methods  if  the  best  possible
     solution is required at any cost. Even then,  however,  hybridisation
     may yield the best of both worlds; also, the ease (if the hardware is
     available!)  of implementing GAs in parallel enhances the possibility
     of  using  them for good, fast solutions to very hard timetabling and
     similar problems.

     References

     Abramson & Abela (1991) "A Parallel Genetic Algorithm for Solving the
     School  Timetabling  Problem",  Technical  Report,  Division of I.T.,
     C.S.I.R.O,  April  1991.   (Division   of   Information   Technology,
     C.S.I.R.O.,  c/o  Dept.  of  Communication  & Electronic Engineering,
     Royal Melbourne Institute of  Technology,  PO  BOX  2476V,  Melbourne
     3001, Australia)

     Colorni  A.,  M. Dorigo & V. Maniezzo (1990).  Genetic Algorithms And
     Highly Constrained Problems: The Time-Table Case. Proceedings of  the
     First International Workshop on Parallel Problem Solving from Nature,
     Dortmund, Germany, Lecture Notes in Computer Science  496,  Springer-
     Verlag,                                                        55-59.
     http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.01-PPSN1.ps.gz

     Colorni A., M. Dorigo & V. Maniezzo (1990).   Genetic  Algorithms:  A
     New  Approach  to  the Time-Table Problem. NATO ASI Series, Vol.F 82,
     COMBINATORIAL OPTIMIZATION,  (Ed.  M.Akguel  and  others),  Springer-
     Verlag,                                                      235-239.
     http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.02-NATOASI90.ps.gz

     Colorni  A.,  M. Dorigo & V. Maniezzo (1990).  A Genetic Algorithm to
     Solve  the  Timetable  Problem.    Technical   Report   No.   90-060,
     Politecnico               di              Milano,              Italy.
     http://iridia.ulb.ac.be/dorigo/dorigo/tec.reps/TR.01-TTP.ps.gz
     Corne, D. Fang, H.-L. & Mellish, C. (1993) "Solving the Modular  Exam
     Scheduling  Problem  with  Genetic  Algorithms".   Proc. of 6th Int'l
     Conf.  on  Industrial  and  Engineering  Applications  of  Artificial
     Intelligence & Expert Systems, ISAI.

     Fang,   H.-L.   (1992)   "Investigating   GAs  for  scheduling",  MSc
     Dissertation,   University   of   Edinburgh   Dept.   of   Artificial
     Intelligence, Edinburgh, UK.

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA




Top Document: FAQ: comp.ai.genetic part 3/6 (A Guide to Frequently Asked Questions)
Previous Document: News Headers
Next Document: Q3: Who is concerned with EAs?

Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
David.Beasley@cs.cf.ac.uk (David Beasley)





Last Update March 27 2014 @ 02:11 PM