simplistic genetic TSP solver, circa May 2010 (you need tspdata.h to run it)

Makefile

tspsolve: tspsolve.c tspdata.h
	gcc -O3 -s -mtune=core2 -std=c99 -W -Wall -lm tspsolve.c -o tspsolve

tspsolve.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include "tspdata.h"

#define NCITIES 140
#define NPOPULATION 250


// random number generator (multiply-with-carry, period 2^128-1)
static uint32_t rnd_x, rnd_y, rnd_z, rnd_w;
static void rnd_seed(int seed) {
	srand(seed);
	rnd_x = rand() * RAND_MAX + rand();
	rnd_y = rand() * RAND_MAX + rand();
	rnd_z = rand() * RAND_MAX + rand();
	rnd_w = rand() * RAND_MAX + rand();
}
static int rnd_seedany(void) {
	int seed = time(NULL);
	rnd_seed(seed);
	return seed;
}
static uint32_t rnd_gen(void) {
	uint32_t t = (rnd_x ^ (rnd_x << 11));
	rnd_x = rnd_y; rnd_y = rnd_z; rnd_z = rnd_w;
	rnd_w = (rnd_w ^ (rnd_w >> 19)) ^ (t ^ (t >> 8));
	return rnd_w;
}


typedef int pop[NCITIES]; // population type

double costn(int a, int b) {
	return hypot(cities[a].x - cities[b].x, cities[a].y - cities[b].y);
}

double costp(const pop c) {
	double sum = costn(c[0], c[NCITIES-1]);
	for (int i = 1; i < NCITIES; ++i) {
		sum += costn(c[i-1], c[i]);
	}
	return sum;
}

void populatep(pop c) {
	for (int i = 0; i < NCITIES; ++i) {
		c[i] = i;
	}

	for (int i = NCITIES - 1; i > 1; --i) {
		// swap c[target] and c[i], where 0 <= target < i
		unsigned target = rnd_gen() % (i-1);
		int tmp = c[target];
		c[target] = c[i];
		c[i] = tmp;
	}
}

void mutatep(pop c) {
	unsigned target1 = rnd_gen() % NCITIES;
	unsigned target2 = rnd_gen() % NCITIES;
	int tmp = c[target1];
	c[target1] = c[target2];
	c[target2] = tmp;
}

// note: this function is one-way combination!
// it is possible that c1 == r, but not c2 == r
void crossoverp(const pop c1, const pop c2, pop r) {
	uint32_t visited[NCITIES / 32 + 1] = {0};
	int pivot = rnd_gen() % NCITIES; // so c1[0..pivot-1] plus c2's other nodes are combined
	for (int i = 0; i < pivot; ++i) {
		r[i] = c1[i];
		visited[r[i] / 32] |= 1 << (r[i] % 32);
	}
	for (int i = pivot, j = 0; i < NCITIES && j < NCITIES; ++j) {
		if ((visited[c2[j] / 32] >> (c2[j] % 32)) & 1) {
			// visited, skip it
		} else {
			r[i++] = c2[j];
		}
	}
}

void copyp(pop dest, const pop src) {
	memcpy(dest, src, sizeof(pop));
}

void printp(const pop c) {
	int zeropoint = -1;
	for (int i = 0; i < NCITIES; ++i) {
		if (c[i] == 0) {
			zeropoint = i;
			break;
		}
	}
	printf("(%d", c[zeropoint]);
	for (int i = 1; i < NCITIES; ++i) printf(" %d", c[(i+zeropoint) % NCITIES]);
	printf(")");
}


typedef struct {
	pop p[NPOPULATION];
	double f[NPOPULATION]; // fitness value set by updateg
	double avgf; // average fitness value set by updateg
	int ord[NPOPULATION]; // ascending order of fitness values (the best first)
} gen; // generation type

#define MUTATIONRATE 0.05
#define CROSSOVERRATE 0.05
#define REGENERATERATE 0.02

void populateg(gen *g) {
	for (int i = 0; i < NPOPULATION; ++i) {
		populatep(g->p[i]);
		g->f[i] = -1.0;
	}
}

void crossoverg(gen *g) {
	for (int i = 0; i < (int)(NPOPULATION * CROSSOVERRATE); ++i) {
		unsigned target1 = rnd_gen() % NPOPULATION;
		unsigned target2 = rnd_gen() % NPOPULATION;
		if (target1 != target2) {
			crossoverp(g->p[target1], g->p[target2], g->p[target1]);
			g->f[target1] = -1.0;
		}
	}
}

void mutateg(gen *g) {
	for (int i = 0; i < (int)(NPOPULATION * MUTATIONRATE); ++i) {
		unsigned target = rnd_gen() % NPOPULATION;
		mutatep(g->p[target]);
		g->f[target] = -1.0;
	}
}

// damn, qsort is not so modular!
static gen *comparep_g;
static int comparep(const void *a, const void *b) {
	int i = *(const int *)a, j = *(const int *)b;
	if (comparep_g->f[i] < comparep_g->f[j]) {
		return -1;
	} else if (comparep_g->f[i] > comparep_g->f[j]) {
		return +1;
	} else {
		return 0;
	}
}

void updateg(gen *g) {
	double sumf = 0.0;
	for (int i = 0; i < NPOPULATION; ++i) {
		if (g->f[i] < 0.0) g->f[i] = costp(g->p[i]);
		sumf += g->f[i];
	}
	g->avgf = sumf / NPOPULATION;

	// calculate the sorted order
	for (int i = 0; i < NPOPULATION; ++i) {
		g->ord[i] = i;
	}
	comparep_g = g;
	qsort(g->ord, NPOPULATION, sizeof(int), &comparep);
}

void regenerateg(gen *g) {
	for (int i = 0; i < (int)(NPOPULATION * REGENERATERATE); ++i) {
		int good = g->ord[i];
		int bad = g->ord[(NPOPULATION-1)-i];
		copyp(g->p[bad], g->p[good]); // overwrite
		g->f[bad] = g->f[good];
	}
}

#define MAXITERATION 100000000
#define REPORTINTERVAL 10000

int main(int argc, char **argv) {
	int useinit = 0;
	pop init;
	if (argc == 1 + NCITIES) {
		uint32_t appeared[NCITIES / 32 + 1] = {0};
		for (int i = 0; i < NCITIES; ++i) {
			init[i] = atoi(argv[i+1]);
			if (init[i] < 0 || init[i] >= NCITIES || ((appeared[init[i] / 32] >> (init[i] % 32)) & 1)) {
				fprintf(stderr, "The initial population is incorrect!\n");
				return 1;
			}
			appeared[init[i] / 32] |= 1 << (init[i] % 32);
		}
		useinit = 1;
	}

	printf("Random seed: %08x\n", rnd_seedany());

	gen g;
	populateg(&g);

	double bestf = 999999999.0, prevbestf = -1.0;
	pop best;
	if (useinit) {
		bestf = costp(init);
		copyp(best, init);
	}
	for (int i = 0; i < MAXITERATION; ++i) {
		crossoverg(&g);
		mutateg(&g);
		updateg(&g);
		if (bestf > g.f[g.ord[0]]) {
			bestf = g.f[g.ord[0]];
			copyp(best, g.p[g.ord[0]]);
		}
		if (i % REPORTINTERVAL == 0) {
			printf("[generation %d] average fitness: %.8f / best fitness: %.8f / best fitness so far: %.8f\n",
					i, g.avgf, g.f[g.ord[0]], bestf);
			if (bestf != prevbestf) {
				printp(best);
				printf("\n");
			}
			prevbestf = bestf;

			// insert the best population in the middle of generation so it won't be removed by regenerateg
			copyp(g.p[g.ord[NPOPULATION/2]], best);
			g.f[g.ord[NPOPULATION/2]] = bestf;
		}
		regenerateg(&g);
	}
}