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
