commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles Sadowski <gil...@harfang.homelinux.org>
Subject Re: [Math] "FixedElapsedTime" in genetic algorithm
Date Thu, 15 Nov 2012 10:59:47 GMT
Hello.

> > [...]
> >>>>>>
> >>>>> I have never read this part of CM yet. But just this makes me think
that the
> >>>>> "FixedElapsedTime" class should not exist in CM. Indeed, using it
makes the
> >>>>> algorithm behave differently at each run!
> >>>>> I don't deny the usefulness of allotting some amount of time for
a
> >>>>> computation, but this has absolutely nothing to do with genetic
algorithms
> >>>>> (nor any others).
> >>>>> CM can help in implementing this high-level requirement, by allowing
> >>>>> <some search algorithm> to be restarted with the result of
a previous run
> >>>>> but IMHO it is a bad idea to have the various CM codes directly
implement
> >>>>> that functionality.
> >>>>
> >>>> I disagree.  This looks like a useful feature to me, contributed by
> >>>> a user.  GA algorithms are by nature iterative with run-time
> >>>> evaluated StoppingConditions.  FixedElapsedTime is a reasonable
> >>>> stopping condition supported by other GA frameworks.  The feature is
> >>>> well-documented, so users know exactly what it does.  In particular,
> >>>> the number of generations is not fixed, so using this
> >>>> StoppingCondition does not guarantee the same results on successive
> >>>> runs with the same input parameters.  GAs are often
> >>>> non-deterministic for other reasons (randomness in mutation), so
> >>>> this is not a practical issue for those choosing to use the feature.
> >>>>
> >>>
> >>> This one is really not worth a fight, but something which you have to adapt
> >>> depending on the machine on which you run your program can only be qualified
> >>> as a toy feature (IMHO): Unless we talk about real-time processing (which
GA
> >>> are not really suited for...), some fixed amount of time can be too small
> >>> (solution not found on a "slow" machine) or too large (solution found long
> >>> before the end of the alloted time slot, but the algo keeps the CPU busy).
> >>>
> >>> As for "non-deterministic", we had several discussions on this ML about
> >>> being able to control the pseudo-random behaviour of the algorithms, by
> >>> using a fixed seed. This is the same here, should you use the same seed,
> >>> the search should go through the same steps. But in this case, it is
> >>> _impossible_ to reproduce the same result since the number of generations
> >>> will depend on how busy the machine is with other processes.
> >>
> >> tbh I do not see the issue here.
> >>
> >> As Phil pointed out, this is a commonly used stopping condition for GAs
> >> so it makes sense to have it supported by default.
> >>
> >> I do not see the link to a discussion about deterministic behavior of
> >> algorithms. It is much more similar to a fixed iteration count (a
> >> stopping condition that already exists), whereas in this case it is
> >> time-based (if a user prefers it this way).
> > 
> > I just re-read my post and wanted to clarify:
> > 
> >  * the algorithm is deterministic
> >  * the result of course not, as it depends on the number of generations
> > 
> > So you are right, getting the same result with such a stopping condition
> > is indeed tricky, but sometimes this is not the goal. You just want to
> > get the best solution so far, even if it is not the best possible.
> 
> ah, I do write stupid things today.

I don't see what you mean here; you were iteratively :-) arriving to the
conclusion I indicated. An algorithm is, by definition, a deterministic
procedure: the seeming randomness comes from choosing the RNG seed, either
randomly (e.g. from the current time) or fixed. In the latter case, we
want a given algorithm, to produce the same result when provided with the
same input. This is just not true with the fixed time criterion (in a
multi-task computing environment, or for two different machines even if they
are single-task).
[With the "fixed generation count" criterion, you always get the same
solution in successive runs, on fast and on slow machines.]

> Phil explained it much better, I will be quit on the topic ;-)

There is a confusion between a well explained and a meaningful feature for
the CM library. If CM is the repository for anything that can be well
explained and coded in Java, that feature is fine... :-}  As I've said
recently, I interpret the CM's goal a little differently.


Gilles

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message