Re: " GA Instable

On Sun, 23 Nov 2003 13:03:49 +0000 (UTC), "Kent Paul Dolan"
<[EMAIL PROTECTED]> wrote:

>"gpapak" <[EMAIL PROTECTED]> wrote:
>
>> I'm using a simple genetic algorithm to solve a
>> maximization problem and I encounter the following
>> problem:
>
>> Contiguous runnings of the algoritm "may" be resulted to
>> different solutions with big distances between them!!!
...[snip]
>
>> Why this event is happened and due to ??
>
>This is very common in genetic algorithms, which aren't
>nearly as easy to implement as they look.
>
>First, there is a problem called "local optimums", which
>mainly means if your balance between speed of solution and
>amount of mutation or strength of other attempts to keep
>a diverse (having lots of essentially different solutions)
>population in your GA isn't good, the GA will jump on the
>first fairly good solution it finds and never let go; so
>increasing mutation might help.  Since different runs, due
>to randomness, are likely to grab different first fairly good
>solutions, what you are seeing happens.  It is also possible
>to have too _much_ mutation, and have it destroy all
>attempts to nudge toward a solution.
>
...[snip]
>Third, too small a population might not sample enough of the
>problem space to have any chance of finding a good solution,
>so population sizes in the hundreds or even thousands may be
>needed.
>
>A good start is to use a large initially random population
>and *no mutation at all*, then in subsequent runs, to up the
>mutation-at-all rate by 0.005 at most per try, and the "how
>much mutation per occurance" rate also keep small, until you
>find a working combination. Each setting of course should be
>used for several tries to see if you are getting convergence
>to similar solutions or still having the trouble you describe.
>
>I hope that helps, and I hope even more my rather poor writing
>style makes it across the second-language barrier.
>

It is possible sometimes to get a sense of how many local optima there
are, by starting with a large initial population and running the GA
with *no crossover*, using a local hill climbing method.  Eventually
each individual in the population will find its local optiimum.  If
there are as many distinct local optima as there are members of your
population, you have a very messy problem.

Sometimes it can be helpful to use hill climbing to place all the
individuals at local optiima, then turn on crossover and see if new
optima are found.

In the long run, the key to GA success is to choose a representation
for your problem which, together with your crossover operators and
mutation operators: a) ensures that each child produced by crossover
or mutation  is a valid solution,  b) ensures that each gene in a
child has the same "meaning" as the corresponding gene in the parents,
and c) constructs children from blocks of genes that are reasonably
likely to contain gene sets responsible for the high fitness of the
parents.  With regard to (c), the arrangement of genes on a chromosome
can be important, and for some problems a linear chromosome and one-
or two-point crossover simply don't work.

Steve