ga
Multicellular Evolutionary Simulation with Hamming Space

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 [] 
Genetic Algorithm Core.
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@lnxbsp.net>
This code is distributed under the Creative Commons "AttributionShareAlike 3.0" SEE: http://creativecommons.org/licenses/bysa/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 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)
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
double adjustment  (  void  ) 
A random pruturbation (or mutation if you prefer) that allows the evolutionary algorithm to continue
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().
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 secondbest 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
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 neardead).
The PPM format is uncompressed and inefficient, but relatively easy to generate.
Pick a random pair of cells, that must be neighbours or nearneighbours. 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 pseudorandom numbers, using a static state variable.
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 ]
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 highside, lowside and how much curve there is in the middle. This allows the agents to tune their attitude to other agents, including some degree of nonlinearity.
TS32* base_hash_matrix = 0 
Used by random generator internals
unsigned char byte_dis[] 
{ 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.
{ { 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 predefined 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
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 highmobility 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