bfgenetic.cpp - mivankovic-blog - Code snippets for my blog

Source path: svn/ trunk/ bfgenetic/ bfgenetic.cpp

‹r3

r36

/*
* This will evolve a output only BF code
*
* Author: Marko Ivankovic
* Version: 0.1
*/
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <cstdlib>

const int ENDLESS_LOOP_THRESHOLD = 10000;
const int MAXIMUM_RANDOM_CODE_SIZE = 1000;

//const std::string targetOutput = "Idem danas kod otorinolaringologa\n";
const std::string targetOutput = "Hello World!\n";

inline int BracketImbalance(const std::string code){
	int openCount = 0;
	for (int i = 0; i < code.size(); i++){
		if ( code[i] == '[' ) {
			if ( openCount < 0 )
				return openCount;
			openCount++;			
		}
		if ( code[i] == ']' ) {
			openCount--;
		}
	}
	return openCount;
}

// Executes brainfuck code. Vanilla brainfuck implementation. 30 000 array. Crash if out of bounds. 8 bit array, no-check.
int bfExec(const std::string& code, const std::string& input, std::string& output){
	int pointer = 0;
	int arrayPointer = 0;
	int inputPointer = 0;
	std::vector<char> array(30000, 0);

	if ( BracketImbalance(code) ) return -1;

	for (int i = 0; i + 1 < code.size(); i++)
		if ( code[i] == '[' && code[i + 1] == ']' ) 
			return -1;

	int retCode = 0;
	
	for (int endlessLoopGuard = 0; endlessLoopGuard < ENDLESS_LOOP_THRESHOLD; endlessLoopGuard++){

		if ( pointer == code.size() ) return endlessLoopGuard;
		
		if ( code[pointer] == '>' ) {
			arrayPointer++;
			if ( arrayPointer > 30000 ) return -1;
		}
		else if ( code[pointer] == '<' ) {
			arrayPointer--;
			if ( arrayPointer < 0 ) return -1;
		}
		else if ( code[pointer] == '+' ) {
			array[arrayPointer]++;
		}
		else if ( code[pointer] == '-' ) {
			array[arrayPointer]--;
		}
		else if ( code[pointer] == '.' ) {
			output += array[arrayPointer];
		}
		else if ( code[pointer] == ',' ) {
			if ( inputPointer != input.size() ){
				array[arrayPointer] = input[inputPointer++];
			}
			else {
				return -1;
			}
		}
		else if ( code[pointer] == '[' ) {
			if ( array[arrayPointer] == 0 ){
				int oc = 1;
				while ( oc ) {
					pointer++;
					if ( code[pointer] == '[' ) oc++;
					else if ( code[pointer] == ']' ) oc--;
				}
			}
		}
		else if ( code[pointer] == ']' ) {
			if ( array[arrayPointer] != 0 ){
				while ( code[pointer] != '[' ) pointer--;
			}
		}

		pointer++;
	}

	return -1;
}

// pure random code
std::string randomCode() {
	std::string code;

	int codeSize = rand() % MAXIMUM_RANDOM_CODE_SIZE + 10;

	for (int i = 0; i < codeSize; i++){
		int choice = rand() % 5;
		if ( choice == 0 )
			code += '>';
		else if ( choice == 1 )
			code += '<';
		else if ( choice == 2 )
			code += '+';
		else if ( choice == 3 )
			code += '-';
		else if ( choice == 4 )
			code += '.';
	}

	return code;
}

// Fitness function.
// The following self explanatory constants are used.
// We are MINIMIZING the function

const int CRASH_FITNESS = 100000000;
const int MISSING_OUTPUT_PENALTY = 50000;
const int TOO_MUCH_OUTPUT_PENALTY = 60000;
const int WRONG_OUTPUT_PENALTY = 50;
const int USELESS_CODE_PENALTY = 1;
const int OFFENDING_OPEN_BRACKET_PENALTY = 100;
const int OFFENDING_CLOSED_BRACKET_PENALTY = 500;


int GeneticFitness(std::string code){
	std::string input = "";
	std::string output = "";
	int rv = bfExec(code, input, output);

	if ( rv != -1 ) {
		int fitness = 0;
		// All-ok!
		std::string expectedOutput = targetOutput;
		int size = expectedOutput.size();

		if ( expectedOutput.size() > output.size() ) {
			fitness += MISSING_OUTPUT_PENALTY * (expectedOutput.size() - output.size());
			size = output.size();
		}
		else if ( expectedOutput.size() < output.size() ){
			fitness += TOO_MUCH_OUTPUT_PENALTY * (output.size() - expectedOutput.size());
		}

		for (int i = 0; i < size; i++) {
			if ( output[i] != expectedOutput[i] )
				fitness += abs(output[i] - expectedOutput[i]) * WRONG_OUTPUT_PENALTY;
		}

		for (int i = 0; i + 1 < code.size(); i++){
			if ( code[i] == '[' && code[i + 1] == ']' ) fitness += USELESS_CODE_PENALTY;
			if ( code[i] == '>' && code[i + 1] == '<' ) fitness += USELESS_CODE_PENALTY;
			if ( code[i] == '<' && code[i + 1] == '>' ) fitness += USELESS_CODE_PENALTY;
			if ( code[i] == '+' && code[i + 1] == '-' ) fitness += USELESS_CODE_PENALTY;
			if ( code[i] == '-' && code[i + 1] == '+' ) fitness += USELESS_CODE_PENALTY;
		}

		fitness += code.size() / 50;
		//fitness += rv;

		return fitness;
	}
	else {
		int fitness = CRASH_FITNESS;

		int balance = BracketImbalance(code);
		fitness += balance * ( balance > 0 ? OFFENDING_OPEN_BRACKET_PENALTY : -OFFENDING_CLOSED_BRACKET_PENALTY );
		
		fitness += code.size();

		return fitness;
	}	
}


struct Individual {
	std::string programCode;
	int fitness;		

	Individual(std::string programCode):programCode(programCode) {
		fitness = GeneticFitness(programCode);
	}

	Individual(){
		programCode = randomCode();
		fitness = GeneticFitness(programCode);
	}

	bool operator< (const Individual& x) const {
		return this->fitness < x.fitness;
	}
};

std::vector<Individual> genePool;

// MUTATE! XULLLLLL! ARGGHHH!
// EXPRESS IN 1/1023-ds (just act if 1 = 0.1%)
int MUTATION_PROBABILITY = 500;
int GROWTH_PROBABILITY = 700;
int SHRINKAGE_PROBABILITY = 1023;

int mutation_command_array[] = { 200, 400, 600, 800, 1000, -1};
char mutation_command_list[] = {'>', '<', '+', '-', '.', ','};

void mutate(std::string& someone){
	// super cool fast mod
	int mutation = rand() & 1023;

	while ( mutation < MUTATION_PROBABILITY ) {
		int mutationType = rand() & 1023;

		if ( someone.size() == 0 ){
			someone = randomCode();		
		}
		else if ( mutationType < GROWTH_PROBABILITY ){
			// so we grow
			int mutationType = rand() & 1023;
			char mutated = 0;

			for (int i = 0; i < 6; i++) {
				if ( mutationType < mutation_command_array[i] ) {
					int mutationLocus = rand() % someone.size();
					someone = someone.substr(0, mutationLocus) + mutation_command_list[i] + someone.substr(mutationLocus, someone.size());
					mutated = 1;
					break;
				}
			}

			if ( !mutated ) {
					// Add [] in correct order to preserve valid code
					int mutationLocusX = rand() % someone.size();
					int mutationLocusY = rand() % someone.size();
					int mutationLocusOne = std::min(mutationLocusX, mutationLocusY);
					int mutationLocusTwo = std::max(mutationLocusX, mutationLocusY);
					someone = someone.substr(0, mutationLocusOne) + '[' + someone.substr(mutationLocusOne, someone.size());
					someone = someone.substr(0, mutationLocusTwo) + ']' + someone.substr(mutationLocusTwo, someone.size());
			}
			
		}
		else if ( mutationType < SHRINKAGE_PROBABILITY && someone.size() > 10 ) {
			// so we shrink			
			int mutationLocus = rand() % someone.size();
			if ( someone[mutationLocus] == '[' ){
				int openCount = 1;
				for (int i = mutationLocus + 1; i < someone.size(); i++){
					if ( someone[i] == '[' )
						openCount++;
					else if ( someone[i] == ']' ){
						openCount--;
						if ( openCount == 0 ){
							someone.erase(i);
							break;
						}
					}
				}
				someone.erase(mutationLocus);
			}
			else if ( someone[mutationLocus] == ']' ){
				someone.erase(mutationLocus);
				int closedCount = 1;
				for (int i = mutationLocus - 2; i > -1; i--){
					if ( someone[i] == ']' )
						closedCount++;
					else if ( someone[i] == '[' ){
						closedCount--;
						if ( closedCount == 0 ){
							someone.erase(i);
							break;
						}
					}
				}
			}
			else
				someone.erase(mutationLocus);
		}

		// why not do it again
		// makes it converge MUCH faster
		mutation = rand() & 1023;
	}
}


// Offspring... You know... Make offspring... Yeah...
std::pair<Individual, Individual> Offspring(const Individual& mother, const Individual& father){
	int smallerSize = std::min(mother.programCode.size(), father.programCode.size());	
	int crossOverPoint = (rand() % (smallerSize - 1)) + 1;

	std::vector<std::string> children(2);

	for (int i = 0; i < crossOverPoint; i++){
		children[0] += mother.programCode[i];
		children[1] += father.programCode[i];
	}

	for (int i = crossOverPoint; i < mother.programCode.size(); i++)
		children[1] += mother.programCode[i];

	for (int i = crossOverPoint; i < father.programCode.size(); i++)
		children[0] += father.programCode[i];

	if ( children[0].size() < 10 )
		children[0] = randomCode();
	if ( children[1].size() < 10 )
		children[1] = randomCode();

	mutate(children[0]);
	mutate(children[1]);

	return std::make_pair(Individual(children[0]), Individual(children[1]));
}

// GENETIC CONSTANTS :D

const int GENE_POOL_SIZE = 16;
const int GENERATION_LIMIT = 10000000;
const int RADIATION_THRESHOLD = 60000;

int RandomGeneticPick(const int& totalFitness){
	int ret = 0;
	int selectedFitness = rand() % totalFitness;
	for ( ;ret < GENE_POOL_SIZE - 1; ret++ ){
		selectedFitness -= genePool[ret].fitness;
		if ( selectedFitness <= 0 ) break;
	}
	return ret;
}

int main() {
	srand(195);

	genePool.resize(GENE_POOL_SIZE);
	std::sort(genePool.begin(), genePool.end());

	for (int generation = 0; generation < GENERATION_LIMIT; generation++) {

		int fitnessSum = 0;
		for (int i = 0; i < GENE_POOL_SIZE; i++)
			fitnessSum += genePool[i].fitness;

		if ( genePool[0].fitness < RADIATION_THRESHOLD ) {
			MUTATION_PROBABILITY = 900 - 900 / genePool[0].fitness;
			mutation_command_array[0] = 100;			
			mutation_command_array[1] = 200;			
			mutation_command_array[2] = 500;			
			mutation_command_array[3] = 800;			
			mutation_command_array[4] = 1000;			
			mutation_command_array[5] = -1;			
		}

		for (int i = 0; i < GENE_POOL_SIZE; i++) {
			int mother = RandomGeneticPick(fitnessSum);
			int father = RandomGeneticPick(fitnessSum);

			std::pair<Individual, Individual> children = Offspring(genePool[mother], genePool[father]);
			genePool.push_back(children.first);
			genePool.push_back(children.second);
		}

		std::sort(genePool.begin(), genePool.end());
		genePool.resize(GENE_POOL_SIZE);

		if ( (generation & ((1<<10) - 1) ) == 0 ) {
			std::string input;
			std::string output;
			int rv = bfExec(genePool[0].programCode, input, output);
			printf("Generation %d. Best fitness %d with bracket imbalance %d\n", generation, genePool[0].fitness, BracketImbalance(genePool[0].programCode) );
			if ( rv != -1 ) printf("Output (%d): ||\n", rv, output.c_str());
			if ( output == targetOutput ) break;
		}
	}

	printf("Final code:\n%s\n", genePool[0].programCode.c_str());

	return 0;
}

Show details Hide details

Change log

r4 by ivankovic.42 on Nov 14, 2009 Diff

Author, version, comment

Go to:

Project members, sign in to write a code review

Older revisions

r3 by ivankovic.42 on Nov 14, 2009 Diff

Added the first brainfuck genetic
programming code

All revisions of this file

File info

Size: 10323 bytes, 387 lines

View raw file