_GENETIC ALGORITHMS_
by Mike Morrow


[LISTING ONE]

/*** GASystem -- Mike Morrow -- Objective function **/

#include "ga.h"

void objinit()
{
}

FIT_TYPE objective(s, len)
SEQ s;
int len;
{
	FIT_TYPE n;
	unsigned int i;
	static char tgt[] = "HELLOTHERE";
	
	n = 0;
	for(i = 0; i < len && i < sizeof tgt - 1; i++)
		if(tgt[i] == s[i])
			n++;
	
	return n;
}

void objshow(s, len, fitness)
SEQ s;
int len;
FIT_TYPE fitness;
{
	printf("%d		", fitness);
	while(len--) printf(" %c", *s++);
	puts("");
}

void objdumpdone()
{

}


[LISTING TWO]

/*** GASystem -- Mike Morrow -- Objective function.  Evaluates a set of 
* directions as applied to a maze. The closer the set of directions gets to 
* the end of the maze, the higher the fitness of that set of directions.
**/

#include "ga.h"
#include <stdio.h>

/** A set of directions is made up of the following **/
#define NORTH   0
#define	EAST	1
#define WEST	2
#define SOUTH	3

/** Define the maze **/
#if MSDOS
#define BLOCK	(char) 178		/* block char on PC */
#define SPACE	' '
#else
#define BLOCK	'@'
#define SPACE	' '
#endif

#define	_			BLOCK,
#define A			SPACE,

#define	MAZEX	17
#define MAZEY	13

typedef char MAZE[MAZEY][MAZEX];
typedef char DISPLINE[80];

static CONST MAZE maze =
{
	_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
	_ A A A A A A A _ _ _ _ _ _ _ A _
	_ A _ _ A _ _ _ _ _ A A _ _ _ A _
	_ A _ _ A A A A A A A _ _ A A A _
	_ A _ _ A _ _ _ A _ _ _ _ A _ _ _
	_ A _ _ _ _ _ _ A A A _ _ A _ A _
	_ A _ _ A _ _ _ _ _ _ _ _ A _ A _
	_ A A A A A A _ _ _ A A A A _ A _
	_ _ _ _ A _ _ _ A _ A _ _ A _ A _
	_ A _ _ A _ A A A _ A A _ A A A _
	_ A A A A _ _ _ A _ _ _ _ _ _ A _
	_ A _ _ A A A A A A A A A A A A _
	_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
};

/** Maze runners start at this point in the maze **/
#define MAZESTARTX	10
#define MAZESTARTY	11

/** Maze runners' goal is this point in the maze **/
#define MAZEENDX	7
#define MAZEENDY	1

/** How far from the MAZEEND is this set of points (x, y)? **/
#define DIST(x, y) ((MAZEENDX - x) * (MAZEENDX - x) + (MAZEENDY - y) 
                                                             * (MAZEENDY - y))

/** What is the longest distance in a maze this size? **/
#define MAXDIST ((MAZEX * MAZEX) + (MAZEY * MAZEY))




#if __STDC__ || __ZTC__
static int mazerun(SEQ s, int len, unsigned int *xp, unsigned int *yp);
static int xroads(int x, int y);
#else
static int mazerun();
static int xroads();
#endif

void objinit()
{
	char exebuff[80];
	
       /** set parameters.  High allele should be SOUTH, low allele 
       * should be NORTH. **/
	sprintf(exebuff, "HIA = %d", SOUTH);
	exec(exebuff);

	sprintf(exebuff, "LOWA = %d", NORTH);
	exec(exebuff);

        /** For starters, give a gene this many elements. User may want to 
        * experiment with this parameter anyway. **/
	sprintf(exebuff, "LEN = 15");
	exec(exebuff);
}

/*** This function evaluates a gene's sequence of directions. It returns
* a fitness value. ***/
FIT_TYPE objective(s, len)
SEQ s;
int len;
{
	FIT_TYPE dist;
	unsigned int x, y;
	int n_moves;

   /** Run through maze using directions in s. x and y will get final position 
   * we reach. n_moves will get number of moves it took to get there. **/
	n_moves = mazerun(s, len, &x, &y);
	
	/** The fitness of that path through maze is distance from MAZEEND.**/
	dist = DIST(x, y);
	
	/** Convert: lower distances imply higher fitness value. **/
	dist = (FIT_TYPE)MAXDIST - dist;
	
	/** Scale down result. 	**/
	dist = (dist * dist) >> 12;
	
	/** Plus a bonus for brevity. 	**/
	dist += 5 * (FIT_TYPE) (len - n_moves);

	return dist;
}

static CONST char i_to_c[] = "NEWS";

#define N_PER_DISP_BLOCK	5

static DISPLINE displines[N_PER_DISP_BLOCK];
static int n_lines = 0;
static MAZE disp_maze;

void objshow(s, len, fitness)
SEQ s;
int len;
FIT_TYPE fitness;
{
	unsigned int x, y;
	int n_moves;
	DISPLINE buff;
	
	if(! n_lines)
		memcpy(disp_maze, maze, sizeof maze);
		
	n_moves = mazerun(s, len, &x, &y);
	
	disp_maze[y][x] = '0' + n_lines;
	
	sprintf(displines[n_lines], "%6d    ", fitness);
	while(len--)
	{
		if(*s > SOUTH)
			sprintf(buff, " %d!", *s++);
		else
			sprintf(buff, " %c", i_to_c[*s++]);
		strcat(displines[n_lines], buff);
	}

	sprintf(buff, " : (%2d, %2d); %2d moves", x, y, n_moves);
	strcat(displines[n_lines], buff);
	
	n_lines++;
	if(n_lines == N_PER_DISP_BLOCK)
		objdumpdone();
}

void objdumpdone()
{
	unsigned int i, x, y;
	
	if(! n_lines)
		return ;
	
	for(i = 0; i < n_lines; i++)
	{
		printf("%d)	%s\n", i, displines[i]);
	}
	
	puts("");
	for(y = 0; y < MAZEY; y++)
	{
		printf("		");
		for(x = 0; x < MAZEX; x++)
		{
				putchar(disp_maze[y][x]);
		}
		puts("");
	}
	n_lines = 0;
	puts("\n\n");
}

/** Run through maze with directions given in s.  *xp and *yp are set to final 
* coords that we end up with. This function returns number of moves it took to
* run maze. It will terminate when moves in s are used up, or when we arrive 
* at the end of maze. **/
static int mazerun(s, len, xp, yp)
SEQ s;
int len;
unsigned int *xp, *yp;
{
	register int x, y;
	register SEQ dirs;
	int n_moves;

	
	x = MAZESTARTX;
	y = MAZESTARTY;
	dirs = s;
	n_moves = 0;
	
        while(len-- && ! (x == MAZEENDX && y == MAZEENDY))
        {
                switch(*dirs++)
                {
                        case NORTH:
                             while(maze[y - 1][x] == SPACE)
                             {
                                y--;
                                if(xroads(x, y))
                                break;
                              }
                         break;
				
			case EAST:
				while(maze[y][x + 1] == SPACE)
				{
					x++;
					if(xroads(x, y))
						break;
				}	
				break;
				
			case WEST:
				while(maze[y][x - 1] == SPACE)
				{
					x--;
					if(xroads(x, y))
						break;
				}	
				break;
				
			case SOUTH:
				while(maze[y + 1][x] == SPACE)
				{
					y++;
					if(xroads(x, y))
						break;
				}
				break;
				
		default:
 		printf("Error in objective(), got allele = %d!", *(dirs - 1));
				break;
		}
		n_moves++;
	}
	*xp = x;
	*yp = y;
	
	return n_moves;
}

/** If this is a cross roads in maze, i.e. there are more than two exits 
* from the current cell, then return TRUE. **/
static int xroads(x, y)
int x, y;
{
	char exits;
	
	exits = (maze[y][x+1] != SPACE) + (maze[y][x-1] != SPACE) +
		(maze[y+1][x] != SPACE) + (maze[y-1][x] != SPACE);
	return exits < 2;
}