Actually it's pretty simple.
A genetic algorithm has one or more objective functions.
An objective function defines the goal of the GA. As an
example, if you were doing crew scheduling, the objective
function might be the schedule with the shortest overall time.
So the objective function is "minimize span time"
A schedule is represented as a genome (or chromosome).
This might consist of the jobs, the duration, the possible
crew assignment, the priority, and earliest start time).
The Genetic Algorithm might initially generate a few hundred
possible schedules with different combinations of jobs and crews.
Each combination must be "feasible" (as an example, a crew must
have the proper skills and resources to perform the job,
and the crew must work in the same geographic region).
SCHEDULING:
The GA then runs each candidate schedule through an actual
resource-constrained scheduler to produce a schedule (the
scheduler actually computes the start and end times for
each job given the crew). We then measure the "fitness"
of each schedule in terms of the objective function. As an
example, the fitness might be the sum of the differences
between the earliest possible start and the actual start for each
job in the schedule. Obviously, schedules that have all or most
of their jobs starting at or close to the earliest possible start will have
fitness values close to zero. Those with jobs that were scheduled later
in their possible windows of opportunity or slipped past their required
finish dates will have very large fitness values. Hence, in this case,
our goal is to minimize the fitness value -- to find the schedule with the
smallest fitness value.
After processing each candidate schedule (each chromosome) and
computing the fitness value for each schedule, we (1) decide
whether it is time to stop and use the fittest schedule or (2) breed
a new generation of schedules and test them for fitness. If it's not
time to stop (see below), we sort the population in descending order
by fitness. We apply any number of selection methods to keep the
top X fittest schedules. We mate or perform a cross-over on some
number of the fittest schedules to produce new candidate schedules.
And we might also mutate some of the chromosomes to produce
a few new entries in the population (this is a form of annealing to
keep us from both prematurely converging and also to keep the GA
from rolling around in a local minimum). With a new population
in hand we repeat the process by looping back to SCHEDULING.
There are any number of methods to decide when to stop a GA.
We can stop a GA after N number of cycles (and this usually a
failsafe check to keep a GA form running forever). But usually we
look at the over all change in the fitness function. If the fitness function
is not changing more than some very small increment (the "epsilon")
or if the fitness function is oscillating between a few values, then it
is time to quit.
Genetic algorithms can support mult-objective and multi-constraint
problems (a constraint is an inviolate restriction on the boundaries
of the problem space. An objective is a population state that may or
may not exist, such as an optimal schedule). Thus a crew scheduler
might have several simultaneous objectives: minimize time,
maximize crew use, minimize costs. In many cases not all objectives
can be achieved and the saddle point in the objective space represents
a balanced trade-off between these objectives.
So... a objective function defines what the GA is seeking. And
the fitness defines how well a particular genome expresses this
objective function.
Sorry to ramble on, but keep in mind that my description is very cursory.
The pragmatics of chromosome design, population size estimation,
cross-over and mutation rates, the methods for eliminating duplicate
genomes (a performance factor not often discussed but which is critical
in all real-world, non-toy problems), and the techniques for evaluating
the solution space bounded by hard constraints and multiple objective
functions is very complicated.
BTW, a genome need not be a bit string. In fact, the crew scheduling GA
uses real (floating point) numbers as its chromosome and, perhaps
counter-intuitively, runs much faster than equivalent bit string chromosomes
for very large problems (900 crews, 230,000 jobs with constraints
involving both fixed and time-varying consumable resources).
Earl
EarlCoxReports, LLC
Insight, Intelligence & Tools
www.earlcoxreports.com
2221 Glengate Circle
Morrisville, NC 27560
(O) (919) 678-0477
(C) (919) 302-6791
AUTHOR:
"The Fuzzy Systems Handbook" (1994)
"Fuzzy Logic for Business and Industry" (1995)
"Beyond Humanity: CyberEvolution and Future Minds"
(1996, with Greg Paul, Paleontologist/Artist)
"The Fuzzy Systems Handbook, 2nd Ed." (1998)
"Machine Intelligence Tools for
Data Mining and Knowledge Discovery"
(due Early Summer 2004)
"joss b" <jossblowing@yahoo.co.uk> wrote in message
news:85ea2455.0404071736.397645e3@posting.google.com...
> Hello all,
>
> I'm pretty new to the GA topic, having just started out of curiosity
> the other day. I managed to build a simple GA to evolve a sentence in
> Perl which was pretty cool :) Anyhow, from the reading I've been
> seeing the words objective and fitness function used interchangeably,
> but I'm sure I've read elsewhere that the objective function can
> actually be considered something else altogether. Such as, the actual
> input into the GA. So would that be the bit string we are aiming to
> evolve? And the fitness is the actual measure of how fit the string
> is?
>
> I'm a little confused so I would greatly appreciate anyone putting
> things into layman's terms.
>
> thanks a million,
>
> joss
|
Search |
Post Question |
Groups |
Stream |
About |
Register
jossblowing
1248 articles. 
5 followers. 
2 Replies
637 Views
