gen.c

一遗传算法的例子源程序

#include <stdlib.h>
#include <string.h>
#include "lithos.h"

static int __cdecl compare(const Program *p0, const Program *p1)
{
	if (p1->fitness < p0->fitness)
		return -1;
	if (p1->fitness > p0->fitness)
		return 1;
	return p1->sort - p0->sort;
}

static int chooseParent()
{
	int i;
	for (i = 0; i < tournamentSize; i++)
	{
		int p = random() % population;
		tournament[i] = programs[p];
		tournament[i].index = p;
		tournament[i].sort = random();
	}
	qsort(tournament, tournamentSize, sizeof(Program), compare);
	return tournament[0].index;
}

static void copy(Program *from, Program *to)
{
	memcpy(to->code, from->code, from->size);
	to->size = from->size;
}

static int isLabel(int i)
{
	return i == LABEL0 || i == LABEL1;
}

static int findBlocks(char *code, int size, int *blocks)
{
	int i;
	int j = 0;
	blocks[j++] = 0;
	for (i = 0; i < size - 1; i++)
		if (isLabel(code[i]) && !isLabel(code[i + 1]) ||
			!isLabel(code[i]) && isLabel(code[i + 1]))
			blocks[j++] = i;
	blocks[j++] = size;
	return j;
}

static int chooseBlock(int i, int n)
{
	while (random() % 2)
		if (random() % 2)
		{
			if (i > 0)
				i--;
		}
		else
			if (i < n - 1)
				i++;
	return i;
}

static void crossover(Program *p, Program *p1)
{
	int n0, n1;
	int n;
	int b;
	int i, j;

	n0 = findBlocks(p->code, p->size, blocks0);
	n1 = findBlocks(p1->code, p1->size, blocks1);

	n = n0;
	if (n > n1)
		n = n1;
	b = random() % n;

	i = blocks0[chooseBlock(b, n0)];
	j = blocks1[chooseBlock(b, n1)];

	n = p1->size - j;
	if (n > maxSize - i)
		n = maxSize - i;
	memcpy(p->code + i, p1->code + j, n);
	p->size = i + n;
}

static void mutate(Program *p)
{
	do
	{
		int op;
		int i;

		if (p->size == 0)
			op = 0;
		else if (p->size == maxSize)
			op = 1 + random() % 2;
		else
			op = random() % 3;

		switch (op)
		{
		case 0:
			i = random() % (p->size + 1);
			memmove(p->code + i + 1, p->code + i, p->size - i);
			p->code[i] = random() % INSTRUCTIONS;
			p->size++;
			break;
		case 1:
			i = random() % p->size;
			p->code[i] = random() % INSTRUCTIONS;
			break;
		case 2:
			i = random() % p->size;
			memmove(p->code + i, p->code + i + 1, p->size - i - 1);
			p->size--;
			break;
		}
	}
	while (random() % 2);
}

void nextGeneration()
{
	int i;
	for (i = 0; i < population; i++)
		programs[i].sort = random();
	qsort(programs, population, sizeof(Program), compare);

	for (i = overselectionRate; i < population; i++)
	{
		int p = chooseParent();
		copy(&programs[p], &newPrograms[i]);
		if (choose(crossoverRate, mutationRate))
		{
			int p1 = chooseParent();
			crossover(&newPrograms[i], &programs[p1]);
		}
		else
			mutate(&newPrograms[i]);
	}

	for (i = overselectionRate; i < population; i++)
		copy(&newPrograms[i], &programs[i]);

	for (i = 0; i < population; i++)
		programs[i].fitness = 0;

	evaluated = 0;
	generations++;
	printf("Generation %d\n", generations);
}