Re: GAs: linear rather than generational evolution?...

On Tue, 25 Mar 2008 15:22:19 +1000, cr88192 wrote:

[...]

well, I am not sure how many people here make use of Genetic Algos...

Most, I'd assume - this is a genetic algorithms newsgroup...

I guess in my case, I have sometimes. I guess though in most cases they
are too slow to be of much practical use.

Too slow compared to what? They are certainly used in practice and
therefore, one might assume, of "practical use". They may not, of course,
be the "best" algorithm (whatever one chooses to mean by that) for any
*particular* problem. They are probably most useful in general for
problems where there is no known analytic solution, or no known good
heuristics for narrowing down search.

Genetic algorithms fall into the class of "stochastic search" algorithms,
in that there is a random element to searching the solution space
(simulated annealing is another popular - and useful - stochastic search
algorithm). Stochastic search algorithms are only going to work better
than random (or indeed exhaustive) search on problems where there is some
structure to the solution space that may be exploited by the variational
mechanism of the algorithm (for GAs that means mutation,
recombination, ...) in the sense that a variation on a given candidate
solution should be more likely than a random candidate solution to be of
good quality.

[...]

now, here is something I have done recently: a variant of a GA was
implemented, but I reworked the algo so that it was linear/iterative,
rather than generational.

whether or not it is still a GA, I am not sure, but oh well...

I'd be inclined to call any algorithm that has some form of variation and
differential selection (i.e. selection on the basis of how good the
candidate solution is) of candidate solutions a "genetic algorithms" -
although that would, I suppose, include simulated annealing. You might
want to include "population-based" in your definition. Anyway, it's
unimportant how you choose to label your algorithm.

[...]

the algo itself works about like this:

when fetching a vector:
two vectors are picked from the population (with a strong bias
towards
the "good" end);
these vectors are 'bred', and the resultant vector is returned.

when returning a vector:
the oldest vector in the population is discarded; the new vector is
inserted in its respective position.

Google for "steady-state GA".

note that I discard the oldest, not the worst, for the main reason that
there is a risk of "flukes" (generally bad vectors that 'got lucky' on
some of the tests, and they remain lodged near the front of the list by
their unreasonably good success, thus screwing over the process).

That's reasonable. It's quite common also to replace a randomly chose
population member.

by eliminating the oldest vectors, this problem can be reduced (this is
less of a problem with the generational approach, since the whole
population is re-evaluated for each generation, flukes will not remain
lodged at the front). it is assumed that good vectors will be created
faster than they will be destroyed.

another issue is mutation rate:
mutation rate is important, since if it is too low, the algo will take a
super long time to adapt (or get stuck somewhere along the way); if it
is too high, then it is not possible to settle on a good answer, as the
vectors will fly around in the general area, but never really adjust
themselves to the exact values.

Yes.

with a generational approach, one solution is to steadily vary the
mutation rate, using a high mutation rate in earlier generations and
steadily dropping it as time moves on.

now, without generations this option is no longer available.

Why ever not? What's stopping you from lowering the mutation rate as
search progresses?

the idea
was then to add a mini version of the algo, and use it mostly for
adapting the mutation rate (in turn, the algo adapts itself, as it is
adapted by its own output...).

There has been tons of work along these lines. Google for "adaptive
mutation rate" + GA

basically, whenever a value comes back, the current mutation rate is
also re-added to its own population, and sorted using the same error as
the main vectors (I guess it would also be possible to use this as
sideband data for the main population, or even as an "extra" component
within the vectors).

well, in any case, the basic idea is that the mutation rate will also
adapt in the direction that leads to more accurate results.

Read about "evolution strategies"

http://en.wikipedia.org/wiki/Evolution_strategies

[...]

I don't know if these are tolerable results or not, oh well...

Results are "tolerable" if they're tolerable *to you*. If what you really
meant was "could I have achieved better results with some different
algorithm?" then... who knows?

--
Lionel B
.

Relevant Pages

  • Re: GAs: linear rather than generational evolution?...
    ... be the "best" algorithm for any ... implemented, but I reworked the algo so that it was linear/iterative, ... another issue is mutation rate: ... I guess I had assumed that such an algo would be used for a continuously adapting system, ...
    (comp.ai.genetic)
  • Re: Cutting stock problem
    ... > mutation rate and population being the two key values. ... Simulated annealing addresses that. ... starts with a high mutation rate, ... I'd try a reasonably greedy algorithm to get a starting solution, ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... If you only learn the beautiful side of programming, ... but won't work in practice'", Kant replied to certain of his critics ... elegance and beauty from the fact that we developed this algorithm ... edumocational theory in which the students shall try, ...
    (comp.programming)
  • Re: Theoretical Computer Science and Disassemblers
    ... :following that algorithm would always produce a correct result, ... humans are not bound by such laws of computability as those which apply to ... :Differentiating code and data (and data types, ... However, in practice, it is not that big a problem. ...
    (alt.lang.asm)
  • Re: Minimization principal for evolution
    ... Part of evolution is ... etc.) rather than arms-race ... But a disadvantage when genetic algorithms are ... You use a genetic algorithm to do the actual optimizing, ...
    (sci.bio.evolution)