You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Gilles Sadowski <gi...@harfang.homelinux.org> on 2012/11/15 02:23:37 UTC
[Math] "FixedElapsedTime" in genetic algorithm (Was: svn commit:
r1409352 - ...)
On Wed, Nov 14, 2012 at 04:38:47PM -0800, Phil Steitz wrote:
> On 11/14/12 4:05 PM, Gilles Sadowski wrote:
> > Hi.
> >
> > On Wed, Nov 14, 2012 at 08:09:52PM -0000, tn@apache.org wrote:
> >> Author: tn
> >> Date: Wed Nov 14 20:09:51 2012
> >> New Revision: 1409352
> >>
> >> URL: http://svn.apache.org/viewvc?rev=1409352&view=rev
> >> Log:
> >> Reduce sleep time in unit test to prevent possible race condition.
> >>
> >> Modified:
> >> commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
> >>
> >> Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
> >> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java?rev=1409352&r1=1409351&r2=1409352&view=diff
> >> ==============================================================================
> >> --- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java (original)
> >> +++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java Wed Nov 14 20:09:51 2012
> >> @@ -59,7 +59,7 @@ public class FixedElapsedTimeTest {
> >>
> >> while (!tec.isSatisfied(pop)) {
> >> try {
> >> - Thread.sleep(500);
> >> + Thread.sleep(50);
> >> } catch (InterruptedException e) {
> >> // ignore
> >> }
> >>
> > 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.
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] "FixedElapsedTime" in genetic algorithm
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
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
Re: [Math] "FixedElapsedTime" in genetic algorithm (Was: svn commit:
r1409352 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On 11/15/2012 09:55 AM, Thomas Neidhart wrote:
> On 11/15/2012 09:08 AM, Thomas Neidhart wrote:
>> On 11/15/2012 02:23 AM, Gilles Sadowski wrote:
>>> On Wed, Nov 14, 2012 at 04:38:47PM -0800, Phil Steitz wrote:
>>>> On 11/14/12 4:05 PM, Gilles Sadowski wrote:
>>>>> Hi.
>>>>>
>>>>> On Wed, Nov 14, 2012 at 08:09:52PM -0000, tn@apache.org wrote:
>>>>>> Author: tn
>>>>>> Date: Wed Nov 14 20:09:51 2012
>>>>>> New Revision: 1409352
>>>>>>
>>>>>> URL: http://svn.apache.org/viewvc?rev=1409352&view=rev
>>>>>> Log:
>>>>>> Reduce sleep time in unit test to prevent possible race condition.
>>>>>>
>>>>>> Modified:
>>>>>> commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>>>>
>>>>>> Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java?rev=1409352&r1=1409351&r2=1409352&view=diff
>>>>>> ==============================================================================
>>>>>> --- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java (original)
>>>>>> +++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java Wed Nov 14 20:09:51 2012
>>>>>> @@ -59,7 +59,7 @@ public class FixedElapsedTimeTest {
>>>>>>
>>>>>> while (!tec.isSatisfied(pop)) {
>>>>>> try {
>>>>>> - Thread.sleep(500);
>>>>>> + Thread.sleep(50);
>>>>>> } catch (InterruptedException e) {
>>>>>> // ignore
>>>>>> }
>>>>>>
>>>>> 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.
Phil explained it much better, I will be quit on the topic ;-)
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] "FixedElapsedTime" in genetic algorithm (Was: svn commit:
r1409352 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On 11/15/2012 09:08 AM, Thomas Neidhart wrote:
> On 11/15/2012 02:23 AM, Gilles Sadowski wrote:
>> On Wed, Nov 14, 2012 at 04:38:47PM -0800, Phil Steitz wrote:
>>> On 11/14/12 4:05 PM, Gilles Sadowski wrote:
>>>> Hi.
>>>>
>>>> On Wed, Nov 14, 2012 at 08:09:52PM -0000, tn@apache.org wrote:
>>>>> Author: tn
>>>>> Date: Wed Nov 14 20:09:51 2012
>>>>> New Revision: 1409352
>>>>>
>>>>> URL: http://svn.apache.org/viewvc?rev=1409352&view=rev
>>>>> Log:
>>>>> Reduce sleep time in unit test to prevent possible race condition.
>>>>>
>>>>> Modified:
>>>>> commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>>>
>>>>> Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java?rev=1409352&r1=1409351&r2=1409352&view=diff
>>>>> ==============================================================================
>>>>> --- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java (original)
>>>>> +++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java Wed Nov 14 20:09:51 2012
>>>>> @@ -59,7 +59,7 @@ public class FixedElapsedTimeTest {
>>>>>
>>>>> while (!tec.isSatisfied(pop)) {
>>>>> try {
>>>>> - Thread.sleep(500);
>>>>> + Thread.sleep(50);
>>>>> } catch (InterruptedException e) {
>>>>> // ignore
>>>>> }
>>>>>
>>>> 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.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] "FixedElapsedTime" in genetic algorithm (Was: svn commit:
r1409352 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On 11/15/2012 02:23 AM, Gilles Sadowski wrote:
> On Wed, Nov 14, 2012 at 04:38:47PM -0800, Phil Steitz wrote:
>> On 11/14/12 4:05 PM, Gilles Sadowski wrote:
>>> Hi.
>>>
>>> On Wed, Nov 14, 2012 at 08:09:52PM -0000, tn@apache.org wrote:
>>>> Author: tn
>>>> Date: Wed Nov 14 20:09:51 2012
>>>> New Revision: 1409352
>>>>
>>>> URL: http://svn.apache.org/viewvc?rev=1409352&view=rev
>>>> Log:
>>>> Reduce sleep time in unit test to prevent possible race condition.
>>>>
>>>> Modified:
>>>> commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>>
>>>> Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java
>>>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java?rev=1409352&r1=1409351&r2=1409352&view=diff
>>>> ==============================================================================
>>>> --- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java (original)
>>>> +++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/genetics/FixedElapsedTimeTest.java Wed Nov 14 20:09:51 2012
>>>> @@ -59,7 +59,7 @@ public class FixedElapsedTimeTest {
>>>>
>>>> while (!tec.isSatisfied(pop)) {
>>>> try {
>>>> - Thread.sleep(500);
>>>> + Thread.sleep(50);
>>>> } catch (InterruptedException e) {
>>>> // ignore
>>>> }
>>>>
>>> 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).
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org