monarch_dodra:

> struct S
> {
>     int opCmp(S b)
>     {
>       if(v[0] < b.v[0]) return -1;
>       if(v[0] > b.v[0]) return  1;
>       return 0;
>     }
>     int[] v;
> }
> ...
> Or did you mean something else?

I meant without a definend opCmp. So this is not your problem.

Bye,
bearophile

On Monday, 30 July 2012 at 12:36:21 UTC, maarten van damme wrote:
> For fun I started implementing a program that uses genetics
> algorithm's to solve the travelling salesman problem. I want to sort
> an array of chromosome structures according to their fitness. I now
> get the error:
>
> core.exception.AssertError@C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.
> d(6714): Failed to sort range of type chromosome[]. Actual result is: [chromosom
> e([city(20, 0), city(25, 25), city(10, 65), city(50, 50), city(75, 30), city(0,
> 10)]), chromosome([city(10, 65), city(50, 50), city(25, 25), city(75, 30), city(
> ...
>
> I have no idea what is wrong with my code and the error is not very informative.
> Does anyone have any idea as to what the problem could be?
>
> (full code is at
> https://dl.dropbox.com/u/15024434/travelling_salesman.d , If it's not
> something obvious then I'm going to try to reduce it to something as
> small as possible)
>
> Maarten

Just saw your code. Intriguing.

I'll have to stick with my gut feeling that sorting values by calculating a floating point value on the fly is not optimal.

BTW: This:
workers=array(sort!(fitnessCompare)(workers));
is equivalent to:
workers.sort!fitnessCompare();
The point of sort's return value is that it is typed as sorted, but you don't need to array->reassign.


Now, if instead of defining fitnessCompare, you use "schwartzSort", a sort made to sort things depending on the result of a function, calling the function one (AND ONLY ONCE) for each value:

Replace
workers.sort!fitnessCompare();
with
workers.schwartzSort!(fitness,"a > b")();

Then the sort works correctly. And schwartzSort ALSO validates the resulting sort.

Sorry I can't *certify* what the problem is, but at least you have a workaround ;)

Great, with that workaround everything works correctly now.

I can finally start playing around with my salesman's dna :p

There is one little problem left, the comparing problem. I can't really define an opcmp because a city isn't smaller or bigger than another city, it's simply another city. I tried defining opEquals but it still refuses to work (could be a problem on my end though).

To clear things out: Comparing an array of structs with inside a dynamic array fails unless you add an opCmp (?or opEquals?) function to that struct.

I thought comparing failed because the references to those dynamic arrays were different and that he was comparing references instead of values.

On Monday, 30 July 2012 at 19:17:30 UTC, bearophile wrote:
> monarch_dodra:
>
>> struct S
>> {
>>    int opCmp(S b)
>>    {
>>      if(v[0] < b.v[0]) return -1;
>>      if(v[0] > b.v[0]) return  1;
>>      return 0;
>>    }
>>    int[] v;
>> }
>> ...
>> Or did you mean something else?
>
> I meant without a definend opCmp. So this is not your problem.
>
> Bye,
> bearophile

I don't get it? If you don't define an opCmp, then you can't compare the elements. At that point, sort won't "fail", it just won't compile...?

On Monday, July 30, 2012 21:17:29 bearophile wrote:
> I meant without a definend opCmp. So this is not your problem.

I'd actually argue that structs without opCmp shouldn't have it implicitly defined. It's just begging for bugs otherwise.

- Jonathan M Davis

On Monday, 30 July 2012 at 20:01:59 UTC, maarten van damme wrote:
> Great, with that workaround everything works correctly now.
>
> I can finally start playing around with my salesman's dna :p
>
> There is one little problem left, the comparing problem. I can't
> really define an opcmp because a city isn't smaller or bigger than
> another city, it's simply another city. I tried defining opEquals but
> it still refuses to work (could be a problem on my end though).

Why do you want to sort the cities?

you need to define an opCmp to do that (not opEquals).

While you *can* deterministically sort the cities using an arbitrary norm (eg Manhattan distance), the end result will be mostly an artificial ordering.
http://en.wikipedia.org/wiki/Manhattan_distance

On 07/30/2012 05:36 AM, maarten van damme wrote:
>
> I have no idea what is wrong with my code and the error is not very informative.
> Does anyone have any idea as to what the problem could be?
>

Congratulations, it looks like you've hit a compiler bug.

http://d.puremagic.com/issues/show_bug.cgi?id=8476

quickest fix: change return type of fitness to real.

On 07/30/2012 02:36 PM, maarten van damme wrote:
> For fun I started implementing a program that uses genetics
> algorithm's to solve the travelling salesman problem. I want to sort
> an array of chromosome structures according to their fitness. I now
> get the error:
>
> core.exception.AssertError@C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.
> d(6714): Failed to sort range of type chromosome[]. Actual result is: [chromosom
> e([city(20, 0), city(25, 25), city(10, 65), city(50, 50), city(75, 30), city(0,
> 10)]), chromosome([city(10, 65), city(50, 50), city(25, 25), city(75, 30), city(
> ...
>
> I have no idea what is wrong with my code and the error is not very informative.
> Does anyone have any idea as to what the problem could be?
>
> (full code is at
> https://dl.dropbox.com/u/15024434/travelling_salesman.d , If it's not
> something obvious then I'm going to try to reduce it to something as
> small as possible)
>
> Maarten

I'd claim it is a 32 bit specific compiler bug, but it is likely that
someone will differ.



reduced test case:

float foo(){
  auto f = 3f;
  return 1/f;
}
void main(){ assert(foo() == foo()); }

The problem is presumably that one of the operands is truncated to
float while the other remains at register precision.



workaround:

bool fitnessCompare(chromosome first,chromosome second){
  auto a = fitness(first), b = fitness(second);
  return a>b;
}

(the reason schwartzSort works is because it caches the fitnesses,
which is better anyway.)




I realize that the code is just for fun, but I have some comments:

- don't .dup stuff just in order to index directly. it never has
any effect other than performance degradation. (this could be a
compiler warning)

- crossOver and mutate mutate their parameters in-place. I assume this
is by mistake. reproduce effectively inserts every element a couple
times because of this -- this is why the bug manifests reliably.
(const, immutable annotations?)

- make use of $

int from=uniform(0,victim.dna.length);
int to=uniform(0,victim.dna.length);
swap(victim.dna[from],victim.dna[to]);

=>

swap(victim.dna[uniform(0,$)],
     victim.dna[uniform(0,$)]);

- sort is in-place

workers=array(sort!(fitnessCompare)(workers));

=>

sort!fitnessCompare(workers)

- mark local functions static if they do not need to access the
enclosing context.

- use size_t for array iteration variables (if necessary)

for(int x=0;x<cities.length-1;x++)
    travelled+=distance(cities[x],cities[x+1]);

=>

for(size_t x=1;x<cities.length;x++)
    travelled+=distance(cities[x-1],cities[x]);

I also removed the subtraction from the array length. This would be
correct in this case because cities.length>=2 is guaranteed, but it is
an error prone pattern.

- another way to do it is to drop the loop completely and to use
ranges instead:

return zip(cities,cities.drop(1))
      .map!(a=>distance(a.expand))
      .reduce!"a+b";


The benefit is that this is now obviously correct.


You might also want to consider not building up the cities array
and computing the terms at the boundary explicitly instead:

return distance(city(0,0), victim.dna[0]) +
       distance(victim.dna[$-1], city(0,0)) +
       zip(victim.dna, victim.dna.drop(1))
      .map!(a=>distance(a.expand))
      .reduce!"a+b";

The goal is to craft the shortest code possible that is still
efficient and easy to follow.

- type deduction?


further comments whose application does not lead to immediate benefit:

- in contracts are better specified in their dedicated section to push
the requirements onto the caller.

- consider for(;;) as a means for indefinite looping.

- the convention is upper case for type names

On 07/30/2012 03:52 PM, monarch_dodra wrote:
> ...
> Your looks OK, and I doubt you are mutating. I only see floating point
> gotchas:
> If a chromosome travels nothing, then his fitness is 1/0 = NaN.
>

1/0 evaluates to Inf

> NaN then compares false with everything, making it un-transitive, and
> potentially breaking your cmp. COuld you try the algo with "return
> 1/(1+travelled)".
>
> That, or because of the non-deterministic nature  of floating point
> calculation,

Floating-point computation is deterministic.

> I'd create an array containing all the fitnesses, and sort
> using that. This should avoid any "re-evaluation error".

monarch_dodra, I'm not trying to order cities, I'm trying to filter out duplicate's in my dna chromosomes and "==" isn't working on structs that encapsulates dynamic arrays.

And I can compare elements without defining opCmp. I've written a function that calculates the distance travelled when going to the cities according to that dna and sort using that.

It looks like you didn't really get how or what I'm trying to do (I don't blame you, I'm terrible at explaining things). You should really look at the code, most things are more obvious there.

Ellery,
When I change it so it uses double