ga
Multicellular Evolutionary Simulation with Hamming Space
Data Structures | Defines | Typedefs | Functions | Variables

ga.c File Reference

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

Copyright (C) 2010, 2011 Telford Tendys <telford@lnx-bsp.net>

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.

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)

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

 All Data Structures Files Functions Variables Typedefs Defines