Genetic Algorithm Core. More...

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

Data Structures
struct	cell_S
struct	col_item_S
Defines
#define	WIDTH 640
#define	HEIGHT 480
#define	TEL_RAND_SIZE 6
#define	LOW_BYTE(x) ((unsigned char)(x))
#define	N_COL 7
Typedefs
typedef int	TS32
typedef TS32	TRND32 [TEL_RAND_SIZE]
typedef struct cell_S	cell_T
typedef struct col_item_S	col_item_T
Functions
int	tel_random3 (TRND32 rand_state)
TS32	rand32 (void)
int	random_chance (double p)
unsigned int	hamming32 (unsigned int x1, unsigned int x2)
double	tolfunc (double x, double q_l, double q_m, double q_h)
double	adjustment (void)
double	att (cell_T A, cell_T B)
double	outcome (double att_A, double att_B)
void	do_split (cell_T A, cell_T B)
void	transaction (cell_T A, cell_T B)
void	setup (cell_T *A)
void	point_select (cell_T Ap, cell_T Bp)
int	get_colour (unsigned int bits, double r, double g, double *b)
int	output_frame (void)
int	main ()
Variables
const double	PAYOFF_SUCKER = -20
const double	PAYOFF_WAR = -15
const double	PAYOFF_PEACE = 5
const double	PAYOFF_TEMPTATION = 10
const double	INITIAL_MIN_SPLIT = 100
const double	MAINTENANCE = -3
const double	INITIAL_RES = 2000
const double	INITIAL_TOL = 0.75
const double	INITIAL_MOB = 0.00
const long long	TOTAL_CYCLES = 40000000000LL
const double	MAX_RES = 5000
const double	CONFUSION_FACTOR_1 = 10
const double	CONFUSION_FACTOR_2 = 10
const double	MOBILITY_BLOCKER = 0.3
int	frame = 0
long long	cycle_count = -1
TS32 *	base_hash_matrix = 0
TRND32	rand_state
unsigned char	byte_dis []
cell_T	grid [WIDTH *HEIGHT]
col_item_T	col_items []

Detailed Description

Genetic Algorithm Core.

Author:: Telford Tendys

Date:: 2012-06-10

Simulation of people trading with each other, based on the presumption of a "Prisoner's Dilemma" in a continuous space (makes a sort of saddle shape). Thus either player can cooperate more (maximum 1.0) or less (minimum 0.0) and thus we get payoffs for the encounter. In addition, players have a bitmap that allows them to compare themselves to other players and a tolerance that acts as a bias (players with high tolerance are likely to cooperate with other players even those quite different to themselves, players with low tolerance will only cooperate with players very similar to themselves).

This code is distributed under the Creative Commons "Attribution-ShareAlike 3.0" SEE: http://creativecommons.org/licenses/by-sa/3.0/

At your option you may convert this to the Free Software Foundation's GNU General Public License version 3 or any later version. SEE: http://www.gnu.org/licenses/gpl.html

Define Documentation

#define HEIGHT 480

Total height of the cellular grid (also output image height in pixels)

#define LOW_BYTE ( x ) ((unsigned char)(x))

Extract the low byte of an integer (0 to 255) as unsigned

#define N_COL 7

The number of colours in col_items

#define TEL_RAND_SIZE 6

Maximum size of random state data

#define WIDTH 640

Total width of the cellular grid (also output image width in pixels)

Typedef Documentation

typedef struct cell_S cell_T

This is merely a typedef to make it easier to type "struct cell_S" but it means nothing more than that.

typedef struct col_item_S col_item_T

This is merely a typedef to make it easier to type "struct col_item_S" but it means nothing more than that.

typedef TS32 TRND32[TEL_RAND_SIZE]

Random generator static state data

Function Documentation

double adjustment ( void )

A random pruturbation (or mutation if you prefer) that allows the evolutionary algorithm to continue

double att	(	cell_T *	A,
		cell_T *	B
	)

return [ 0.0 to 1.0 ] where 0.0 is the worst and 1.0 is the best. tol values is taken from A point of view, and the above tolfunc().

void do_split	(	cell_T *	A,
		cell_T *	B
	)

Split one cell into two.

All inheritable traits are copied exactly. Resources are split in half and each side gets the same. Cell division is an instantaneous operation so there is no stage where the cell is "out of operation" due to the reproductive pricess.

int get_colour	(	unsigned int	bits,
		double *	r,
		double *	g,
		double *	b
	)

Convert bit pattern to RGB colour for display purposes.

This does a fairly simple merge of multiple vectors using the best and second-best fit against a fixed list of vectors (based on searching for the shortest Hamming distance).

The output R, G, B values determines the colour for this particular cell, although colours are largely arbitrary, they make it easy to visualise the boundary of cooperative groups, and also tend to reveal the overall diversity within the group. Of course, collapsing a 32 dimensional space down to a 3 dimensional space will necessarily lose some information.

unsigned int hamming32	(	unsigned int	x1,
		unsigned int	x2
	)

Evaluate hamming distance between two 32bit numbers

Returns:: a number between 0 and 32

int main ( )

Setup all the cell values to a reasonable starting value, with decent resources and a flat tolerance function (i.e. ignore any similarity/difference) at a neutral level (i.e. all players take a neutral attitude to each other).

Then loop with random pairs (fast random generation is the bottleneck) of neighbours, and transaction between the neighbours on the basis of above. In addition, small random changes happen to the variables, so that mutation exists in the system as a whole.

double outcome	(	double	att_A,
		double	att_B
	)

Evaluate the outcome of the Prisoner's Dilemma game by taking two attitudes and linearly interpolating between the four extreme possible outcomes: PAYOFF_PEACE, PAYOFF_TEMPTATION, PAYOFF_SUCKER, PAYOFF_WAR

All inputs are bounded between 0 and 1 (inclusive) so callers to this function need not be overly cautious about checking their values are within range.

int output_frame ( void )

Output a frame in PPM format which we can convert to something more practical later (e.g. MPEG video stream). Colour determines approximate allegiance to some group. Overall output intensity determies resource levels (black for dead cells, dark for near-dead).

The PPM format is uncompressed and inefficient, but relatively easy to generate.

void point_select	(	cell_T **	Ap,
		cell_T **	Bp
	)

Pick a random pair of cells, that must be neighbours or near-neighbours. More likely to pick close neighbours than distant neighbours. FIXME: This could probably be better.

TS32 rand32 ( void )

Use the tel_random3() function to supply a stream of pseudo-random numbers, using a static state variable.

Returns:: pseudo-random 32 bit number (signed)

int random_chance ( double p )

Take a probability value (forced to limit between 0 and 1) and calculate whether an event happens (return 1 if it happens 0 otherwize)

void setup ( cell_T * A )

Load initial values into a cell at bootstrap time

int tel_random3 ( TRND32 rand_state )

Generate a random value, based on the given array of state variables (which are also updated by the random generation). Faster than the glibc random generator, possibly not quite as random but pretty good all told.

Output value is in rand_state[ 0 ]

Returns:: always 0

double tolfunc	(	double	x,
		double	q_l,
		double	q_m,
		double	q_h
	)

Parametric parabola made with shape functions and trapped between 0, 1

Allows significant scope for the tolerance function, including high-side, low-side and how much curve there is in the middle. This allows the agents to tune their attitude to other agents, including some degree of non-linearity.

void transaction	(	cell_T *	A,
		cell_T *	B
	)

Evaluate one transaction between a pair of cells

Variable Documentation

TS32* base_hash_matrix = 0

Used by random generator internals

unsigned char byte_dis[]

Initial value:

{
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
}

A lookup table for calculating the Hamming distance between two bytes. Counts the number of 1 bits in a single byte.

col_item_T col_items[]

Initial value:

 {
        { 0x00000000, 1, 0, 0 },
        { 0xFFFFFFFF, 0, 1, 1 },
        { 0xFFFF0000, 0, 1, 0 },
        { 0x0000FFFF, 1, 0, 1 },
        { 0x00FFFF00, 0, 0, 1 },
        { 0xFF0000FF, 1, 1, 0 },
        { 0x3C3C3C3C, 1, 1, 1 },
}

A list of pre-defined colours are here.

These are largely arbitrary but they span a range of primary and secondary RBG colour values (i.e. bright coulours) and they span various orthogonal bitmaps.

const double CONFUSION_FACTOR_1 = 10

Factor for random mistakes and confusion amongst cells. A bigger value here means cells are more likely to misjudge each other when evaluating trust (e.g. cultural patterns might not be properly recognised).

const double CONFUSION_FACTOR_2 = 10

Factor for random mistakes and confusion amongst cells. A bigger value here means cells are more likely to misjudge their own reactions (e.g. over react or under react to an encounter).

long long cycle_count = -1

A counter that controls the length of the simulation

int frame = 0

A frame counter for output images, not all frames are used in the final video. The frame counter goes into the filename

cell_T grid[WIDTH *HEIGHT]

This is the cellular grid

const double INITIAL_MIN_SPLIT = 100

Initial value for cell_S::min_split when system bootstraps

const double INITIAL_MOB = 0.00

Initial value for cell_S::mobility when system bootstraps

const double INITIAL_RES = 2000

Initial value for cell_S::res when system bootstraps

const double INITIAL_TOL = 0.75

Initial value for both cell_S::tol_low and cell_S::tol_high when system bootstraps

const double MAINTENANCE = -3

Regular maintenance cost for all cells, regardless of attitude

const double MAX_RES = 5000

Artificial upper limit on the amount of resources any cell can

const double MOBILITY_BLOCKER = 0.3

Artificial upper limit on high-mobility cells, possibly because of some physical limitation or whatever. If set to 0.0 then all mobility is impossible, but the highest value is 1.0 and cells are allowed to select for LOWER mobility than this value (although experimentally, it seems to always result in a spread from zero up to the limit value).

const double PAYOFF_PEACE = 5

The penalty (i.e. a negative payoff) in return for both sides offering the worst attitude (1.0)

const double PAYOFF_SUCKER = -20

The penalty (i.e. a negative payoff) in return for offering best attitude (1.0) in response to worst attitude (0.0)

const double PAYOFF_TEMPTATION = 10

The penalty (i.e. a negative payoff) in return for offering worst attitude (0.0) in response to best attitude (1.0)

const double PAYOFF_WAR = -15

The penalty (i.e. a negative payoff) in return for both sides offering the worst attitude (0.0)

TRND32 rand_state

Static random state variable, starts all zero when program begins

const long long TOTAL_CYCLES = 40000000000LL

Termination condition for the simulation, can be quite a large number

ga.c File Reference

Data Structures

Defines

Typedefs

Functions

Variables

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation

Variable Documentation