Q2: What applications of EAs are there?
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:
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. 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
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, (to appear).
Fang, H.-L. (1992) "Investigating GAs for scheduling", MSc
Dissertation, University of Edinburgh Dept. of Artificial
Intelligence, Edinburgh, UK.
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)
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
gwdu03.gwdg.de:/pub/msdos/reports/wi/earef.eps
Boulding, K.E. (1991) "What is evolutionary economics?", Journal of
Evolutionary Economics, 1, 9-17.
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 as
a means of conducting something akin to Roulette-Wheel SELECTION 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 by
interpreting the decimal value of the bit string as the inverse of
the 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).
Other methods of evolving a POPULATION can be found in Lindgren 1991,
Glance and Huberman 1993 and elsewhere.
References.
Axelrod, R. (1987) ``The Evolution of Strategies in the Repeated
Prisoner's Dilemma,'' in [DAVIS91]
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
Go Back Up
Go To Previous
Go To Next