Generation evolution problem

[Vikas Agrawal]

Hello All:

I have been facing some weird problem. I am copying my output for each generation here:

My candidate solution is a Map<String, List<String>> with key being the driver and List being the list of strings of jobs that need to be completed. I am trying to minimize the weighted total time to cover all the locations to pickup or deliver all the jobs. If you see below, Generation 6 and 7 are exactly same but the weighted score is increased from 1.2878866772402855  to 1.2904243457573354. This makes no sense to me as they both are exactly same. The weighted total time should stay the same or go down with each generation, but definitely not increase. I understand this might be too little info to fully understand what's going on, but thought of throwing it out there and see if anybody else faced the same problem.

Thanks,

Vikas

==========================================================

Generation 0: {DB10=[J9P, J9D], DB11=[J16P, J16D], DC3=[J10P, J10D], DS13=[J1P, J1D], DC12=[J3P, J3D, J7P, J7D], DS5=[J2P, J2D, J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D], DC7=[J14P, J14D], DB13=[J11P, J11D], DA2=[J6P, J6D], DS4=[J4P, J4D]}: 1.491316510705789 weighted_score

Generation 1: {DE3=[J6P, J6D], DB7=[J16P, J16D], DS7=[J2P, J2D], DB11=[J9P, J9D], DC2=[J14P, J14D, J15P, J15D, J1P, J1D], DC14=[J7P, J7D], DC16=[J4P, J4D, J8P, J8D], DS6=[J10P, J10D], DS3=[J5P, J5D, J12P, J12D], DC8=[J3P, J3D, J13P, J13D], DB5=[J11P, J11D]}: 1.4311559159397305 weighted_score

Generation 2: {DB11=[J16P, J16D], DS16=[J2P, J2D], DB12=[J9P, J9D], DC3=[J1P, J1D, J14P, J14D], DE14=[J6P, J6D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS5=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D], DB13=[J11P, J11D], DS4=[J4P, J4D]}: 1.376675344964314 weighted_score

Generation 3: {DB11=[J16P, J16D], DS16=[J2P, J2D], DB12=[J9P, J9D], DC3=[J1P, J1D, J14P, J14D], DE14=[J6P, J6D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS5=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D], DB13=[J11P, J11D], DS4=[J4P, J4D]}: 1.3776269706582078 weighted_score

Generation 4: {DB11=[J16P, J16D], DS16=[J2P, J2D], DB12=[J9P, J9D], DC3=[J1P, J1D, J14P, J14D], DE14=[J6P, J6D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS5=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D], DB13=[J11P, J11D], DS4=[J4P, J4D]}: 1.376675344964314 weighted_score

Generation 5: {DS16=[J2P, J2D], DB11=[J16P, J16D, J11P, J11D], DC3=[J1P, J1D, J14P, J14D], DB12=[J9P, J9D], DE14=[J6P, J6D], DC1=[J4P, J4D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS2=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D]}: 1.2878866772402855 weighted_score

Generation 6: {DS16=[J2P, J2D], DB11=[J16P, J16D, J11P, J11D], DC3=[J1P, J1D, J14P, J14D], DB12=[J9P, J9D], DE14=[J6P, J6D], DC1=[J4P, J4D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS2=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D]}: 1.2878866772402855 weighted_score

Generation 7: {DS16=[J2P, J2D], DB11=[J16P, J16D, J11P, J11D], DC3=[J1P, J1D, J14P, J14D], DB12=[J9P, J9D], DE14=[J6P, J6D], DC1=[J4P, J4D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS2=[J5P, J5D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DS3=[J15P, J15D]}: 1.2904243457573354 weighted_score

Generation 8: {DB11=[J16P, J16D, J11P, J11D, J9P, J9D], DC3=[J1P, J1D, J14P, J14D], DS14=[J2P, J2D], DE14=[J6P, J6D], DC1=[J4P, J4D], DC12=[J3P, J3D, J7P, J7D, J10P, J10D], DS10=[J12P, J12D], DS2=[J5P, J5D], DC17=[J8P, J8D, J13P, J13D], DS3=[J15P, J15D]}: 1.2829699444885012 weighted_score

Generation 9: {DB11=[J16P, J16D, J11P, J11D], DB12=[J9P, J9D], DC3=[J1P, J1D, J14P, J14D], DE14=[J6P, J6D], DC1=[J4P, J4D], DC12=[J3P, J3D, J10P, J10D], DS2=[J5P, J5D, J2P, J2D], DC9=[J15P, J15D], DC17=[J8P, J8D, J12P, J12D, J13P, J13D], DC7=[J7P, J7D]}: 1.2666337034099922 weighted_score

=====================================================================================

[Daniel Dyer]

On Tue, 11 Nov 2014 18:59:34 -0000, Vikas Agrawal <avi...@gmail.com> wrote:

> Hello All:
>
> I have been facing some weird problem. I am copying my output for each
> generation here:
>
> My candidate solution is a Map<String, List<String>> with key being the
> driver and List being the list of strings of jobs that need to be
> completed. I am trying to minimize the weighted total time to cover all
> the
> locations to pickup or deliver all the jobs. If you see below,
> Generation 6
> and 7 are exactly same but the weighted score is increased from
> 1.2878866772402855 to 1.2904243457573354. This makes no sense to me as
> they both are exactly same. The weighted total time should stay the same
> or
> go down with each generation, but definitely not increase. I understand
> this might be too little info to fully understand what's going on, but
> thought of throwing it out there and see if anybody else faced the same
> problem.

How are you calculating your weighted score? Is it deterministic (i.e.
will it always give the same result for the same input)?

Also, are you using elitism? If not, it's possible for the fittest
individual in a generation to be less fit than the fittest individual from
the previous generation.

Dan.

--
Daniel Dyer

[Vikas Agrawal]

My weighted score is not deterministic. It's stochastic in nature meaning it might produce different result even for the same input. Is that the problem?

Yes I am using elitism. I set it to 3.

--
You received this message because you are subscribed to the Google Groups "Watchmaker Framework for Evolutionary Computation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to watchmaker+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alfonso Garcia]

Vikas,

Definitely, the non-deterministic nature of the score is the source of your problem. And elitism does not solve it, because what may belong to the elite in one generation does not have to be also in the elite for the next generation, as the score is not the same across generations.

In my case I realized that it was due to using the stock RecommenderEvaluator. Each time you call evaluate(), it splits randomly the data set into two partitions. I created a slightly different version which precomputes the train and data sets and keeps them constant over the evolution steps, making the scores across generations stable. Your solution may have to be different.

To unsubscribe from this group and stop receiving emails from it, send an email to watchmaker+...@googlegroups.com.

[Vikas Agrawal]

Hello Alfonso,

Thanks for your reply. I really appreciate it. Are you overriding the following method?

protected List<EvaluatedCandidate<T>> evaluatePopulation(List<T> population)

inside

public abstract class AbstractEvolutionEngine<T> implements EvolutionEngine<T>

May be I need to do the same.

Thanks,

Vikas

[Alfonso Garcia]

Not quite, Vikas. My mind slipped while writing and I assumed that everyone knows about my particular project, so my mention of RecommenderEvaluator was a reference to the Apache Mahout class that is used to rate the quality of the recommendations..

I'm using Watchmaker to build a GA that creates recommenders using Apache Mahout, and the evaluators for those recommenders are the source of randomness in my case, so I had to override the Mahout class that scores them, not any Watchmaker class.