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

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.

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

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".

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

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.

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

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.

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

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?