View mode: basic / threaded / horizontal-split · Log in · Help
July 30, 2012
sorting failed error
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
July 30, 2012
Re: sorting failed error
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

I couldn't have access to your code, but my *guess* would be that 
the provided "less", or in your probable case, your "opCmp", is 
not transitive.

Eg, if you have 3 cities A, B and C, then if A<B and B<C, then 
you MUST have A<C.

Could you post here your implementation of opCmp?

If you are trying to implement traveling salesman, then I don't 
think "sort" is the algorithm should be using.
July 30, 2012
Re: sorting failed error
My cmp is :

bool fitnessCompare(chromosome first,chromosome second){
		return fitness(first)>fitness(second);
}

float fitness(chromosome victim){
	city[] cities=victim.dna;
	
	//we need to start from home and return to home
	cities=city(0,0) ~ cities;
	cities~=city(0,0);
	
	float travelled=0f;
	for(int x=0;x<cities.length-1;x++)
		travelled+=distance(cities[x],cities[x+1]);

	return 1/travelled;
}



I've posted my code too on pastebin : http://pastebin.com/7927Hpv2
July 30, 2012
Re: sorting failed error
On Monday, 30 July 2012 at 13:27:58 UTC, maarten van damme wrote:
> My cmp is :
>
> bool fitnessCompare(chromosome first,chromosome second){
> 		return fitness(first)>fitness(second);
> }
>
> float fitness(chromosome victim){
> 	city[] cities=victim.dna;
> 	
> 	//we need to start from home and return to home
> 	cities=city(0,0) ~ cities;
> 	cities~=city(0,0);
> 	
> 	float travelled=0f;
> 	for(int x=0;x<cities.length-1;x++)
> 		travelled+=distance(cities[x],cities[x+1]);
>
> 	return 1/travelled;
> }
>
>
>
> I've posted my code too on pastebin : 
> http://pastebin.com/7927Hpv2

That seems like a reasonable cmp function. But on the expensive 
side, but that is irrelevant.

I can't access any internet share sites from where I am, so I 
can't dig in much further than that. The assertion you are 
hitting is one that is called after the sort is done, to make 
sure the elements are indeed sorted. In your case, after the 
sort, the elements are not sorted :/

The way I see it, there could be 1 of 2 issues:
*A bad cmp function.
*Data that mutates during sort.

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.

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, I'd create an array containing all the 
fitnesses, and sort using that. This should avoid any 
"re-evaluation error".
July 30, 2012
Re: sorting failed error
maarten van damme:

> I have no idea what is wrong with my code and the error is not 
> very informative.

As first step I suggest to add a space after commas, before 
brackets, around operators, etc. The improved readability helps 
spot the bugs.

Adding Contracts and other asserts sometimes helps. Adding some 
unit tests sometimes helps.

Bye,
bearophile
July 30, 2012
Re: sorting failed error
it is guaranteed to never be 0 because it always contains all cities
so it will always travel something unless there are no cities or when
all cities are in the same place (in which case the task to solve is
senseless).

I'll create an array containing all finesses and try sorting using that.

And bearophile, you're right. it was supposed to be a very quick
program just for fun to see how powerful genetics can be. (read about
them yesterday.Never looked at a complete implementation and I'm
trying to see how far I'd get with some simple rules. My cross over
function isn't really that good...)

I really dislike contracts, they kind off blow your function up while
adding not that much. I'll add some unit tests.
July 30, 2012
Re: sorting failed error
maarten van damme:

> I really dislike contracts, they kind off blow your function up 
> while adding not that much. I'll add some unit tests.

They make your programs more robust. Contracts are used to spot 
bugs in your code and not to validate data coming from the 
"outside world".

As most other tools there are few ways to use them well, and many 
ways to use them badly. I suggest you to read about the meaning 
of Contract programming, so maybe you will learn to appreciate 
them.

Bye,
bearophile
July 30, 2012
Re: sorting failed error
2012/7/30 bearophile <bearophileHUGS@lycos.com>:
> maarten van damme:
>
>
>> I really dislike contracts, they kind off blow your function up while
>> adding not that much. I'll add some unit tests.
>
>
> They make your programs more robust. Contracts are used to spot bugs in your
> code and not to validate data coming from the "outside world".
>
> As most other tools there are few ways to use them well, and many ways to
> use them badly. I suggest you to read about the meaning of Contract
> programming, so maybe you will learn to appreciate them.
>
> Bye,
> bearophile

I certainly will. Andrei's chapter didn't convince me but maybe
reading something more specialized to contract programming
specifically will convince me :)

About my pass-by-value problem, I am not used to working with structs,
I usually work with classes. That's why I completely forgot about
post-blit constructors... Still my sorting problem isn't sorted out.
July 30, 2012
Re: sorting failed error
maarten van damme:

> Still my sorting problem isn't sorted out.

Another possible cause: in D if you sort structs that contain 
dynamic arrays, the actual contents of the arrays is ignored. 
This is a HUGE bug in DMD.

Bye,
bearophile
July 30, 2012
Re: sorting failed error
On Monday, 30 July 2012 at 18:50:24 UTC, bearophile wrote:
> maarten van damme:
>
>> Still my sorting problem isn't sorted out.
>
> Another possible cause: in D if you sort structs that contain 
> dynamic arrays, the actual contents of the arrays is ignored. 
> This is a HUGE bug in DMD.
>
> Bye,
> bearophile

Could you share the bug report? This works fine for me... :

----
import std.stdio;
import std.range;
import std.algorithm;
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;
}

void main()
{
  S[3] ss;
  ss[0].v = [1, 2].array();
  ss[1].v = [5, 6].array();
  ss[2].v = [3, 4].array();
  writeln(ss[]);
  ss[].sort();
  writeln(ss[]);
}
----

Or did you mean something else?
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home