Genetic Algorithms

[mmavipc]

What are they?

[quote=Wikipedia, the free encyclopedia]The genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.[/quote]

Cool, how do I make one?

First, find a way to rate the results of your generation. Can be higher = better, or lower = better. Initialize the population with random data. To evolve, first rate and sort the data. Kill off the worst half of the data, and evolve the better half to fill in the missing spots. You can evolve by replacing part of the data with random info, addition, subtration, multiplication, or any other mathematical way to interact with numbers(Data is all just numbers, you should know this). Rinse & Repeat until you get satisfactory data.

Have you made any?

Yes, I have. It takes an input string, and tries to get data to match it. I have it running with a pretty large str right now, Here's a paste of the output.
[quote=Genetic Program]Generation 1336837's lowest badness: 47, top five:
Hello 1, hello all. Let's see how optimized we cam!fuh euh get ukhs#panvç in←h[h,"get thir party in here. What was I saying? I have no clue
Hello 1, hello all. Let's see how optimized we cam!fuh euh get ukhs#panvç in←h[h,"get thir party in here. What was I saying? I have no clue
Hello 1, hello all. Let's see how optimized we cam!fuh euh get ukhs#panvç in←h[h,"get thir party in here. What was I saying? I have no clue
Hello 1, hello all. Let's see how optimized we cam!fuh euh get ukhs#panvç in←h[h,"get thir party in here. What was I saying?▼I hbve no clue
Hello 1, hello a♀l. meu't sde how optimized we cam!fuh euh get ukhs#panvç in←h[h,"get thir party in here. What was I saying? I have no clue[/quote]

You want the horrible messy code for it? Here you go:

// Genetic text thigny.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <time.h>

typedef unsigned int uint;

unsigned int Evolve(std::string *strList, std::string strCorrect, unsigned int uiPop);

std::string Sanitize(std::string input);

int _tmain(int argc, _TCHAR* argv[])
{
	std::string strCorrect = "Hello 1, hello all. Let's see how optimized we can guh guh get this party in hah, get this party in here. What was I saying? I have no clue";

	std::cout << strCorrect << std::endl << "# of pop?: ";

	unsigned int nPop = 0;

	std::cin >> nPop;

	std::cout << "Override string?:";

	std::string strOverride;
	std::cin >> strOverride;

	if(strOverride!="no")
	{
		strCorrect = strOverride;
	}

	bool bTopFive = true;
	std::cout << "Print top five? ";
	std::cin >> bTopFive;

	std::string *strList = new std::string[nPop];

	srand(clock());

	for(uint i = 0; i<nPop; i++)
	{
		for(uint j = 0; j<strCorrect.length(); j++)
		{
			strList[i] += char((rand()%255)+1);
		}
	}

	uint badness = 0;
	uint oldbad = 0;
	uint gen = 1;
	uint oldclock = clock()/CLOCKS_PER_SEC;

	while(true)
	{
		badness = Evolve(strList, strCorrect, nPop);
		if(oldbad != badness || clock()/CLOCKS_PER_SEC > oldclock)
		{
			oldclock = clock()/CLOCKS_PER_SEC;
			std::cout << "Generation " << gen << "'s lowest badness: " << badness;
			if(!bTopFive)
			{
				std::cout << " best str: \"" << Sanitize(strList[0]) << "\"" << std::endl;
			}
			else
			{
				std::cout << ", top five:" << std::endl;
				for(uint i = 0; i<5 && i<nPop; i++)
				{
					std::cout << Sanitize(strList[i]) << std::endl;
				}
			}
		}
		if(badness == 0)
		{
			break;
		}
		oldbad = badness;
		gen++;
	}

	system("pause");

	return 0;
}

unsigned int Evolve(std::string *strList, std::string strCorrect, unsigned int uiPop)
{
	for(uint i = 0; i<(uiPop/2); i++)
	{
		srand(clock());
		strList[(uiPop/2)+i] = "";
		if(rand()%2==0)
		{
			for(uint j = 0; j<strCorrect.length(); j++)
			{
				if(rand()%7 == 4)
				{
					uint randresult = rand()%3;
					if(randresult == 0)
					{
						if(strList[i][j] == 255)
						{
							strList[(uiPop/2)+i] += 1;
						}
						else
						{
							strList[(uiPop/2)+i] += strList[i][j]+1;
						}
					}
					else if(randresult == 1)
					{
						if(strList[i][j] == 1)
						{
							strList[(uiPop/2)+i] += 255;
						}
						else
						{
							strList[(uiPop/2)+i] += strList[i][j]-1;
						}
					}
					else
					{
						strList[(uiPop/2)+i] += rand()%255+1;
					}


					if(rand()%2 == 0)
					{
						for(uint k = j+1; k<strCorrect.length(); k++)
						{
							strList[(uiPop/2)+i] += strList[i][k];
						}
						break;
					}
				}
				else
				{
					strList[(uiPop/2)+i] += strList[i][j];
				}
			}
		}
		else
		{
			for(int j = strCorrect.length()-1; j>=0; j--)
			{
				std::string tmpstr;
				if(rand()%7 == 4)
				{
					uint randresult = rand()%3;
					if(randresult == 0)
					{
						if(strList[i][j] == 255)
						{
							tmpstr = 1;
							strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
						}
						else
						{
							tmpstr = strList[i][j]+1;
							strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
						}
					}
					else if(randresult == 1)
					{
						if(strList[i][j] == 1)
						{
							tmpstr = 255;
							strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
						}
						else
						{
							tmpstr = strList[i][j]-1;
							strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
						}
					}
					else
					{
						tmpstr = rand()%255+1;
						strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
					}


					if(rand()%2 == 0)
					{
						for(int k = j-1; k>=0; k--)
						{
							tmpstr = strList[i][k];
							strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
						}
						break;
					}
				}
				else
				{
					tmpstr = strList[i][j];
					strList[(uiPop/2)+i] = tmpstr + strList[(uiPop/2)+i];
				}
			}
		}
	}

	uint *iBad = (uint*)malloc(sizeof(uint) * uiPop);

	for(uint i = 0; i<uiPop; i++)
	{
		iBad[i] = 0;
		for(uint j = 0; j<strCorrect.length(); j++)
		{
			if(strList[i][j] != strCorrect[j])
			{
				iBad[i] += abs(unsigned char(strList[i][j]) - unsigned char(strCorrect[j]));
			}
		}
	}

	bool bSorting = true;
	std::string strTemp;
	uint uiBTemp;

	while(bSorting)
	{
		bSorting = false;
		for(uint i = 0; i<uiPop-1; i++)
		{
			if(iBad[i] > iBad[i+1])
			{
				uiBTemp = iBad[i];
				strTemp = strList[i];

				iBad[i] = iBad[i+1];
				strList[i] = strList[i+1];

				iBad[i+1] = uiBTemp;
				strList[i+1] = strTemp;

				bSorting = true;
				break;
			}
		}
	}

	uint ret = iBad[0];

	free(iBad);

	return ret;
}

std::string Sanitize(std::string input)
{
	std::string ret = "";
	for(uint i = 0; i<input.length(); i++)
	{
		if(unsigned char(input[i]) == 7)
		{
			ret += " ";
		}
		else
		{
			ret += input[i];
		}
	}
	return ret;
}

I don't work with console input much, so excuse the incorrect use of cin.

Now, discuss.

[zenby]

[lua]function RandToTarget()

local function rl() local r, rn = table.Random(string.Explode("", " !@#$%^&*()-=+qwertyuiopasdfghjklzxcvbnm[]{}\\<>/?~`;:,.\"'|1234567890")), math.random(1,2) if rn == 1 then return r end return r:upper() end
print("This will write random letters until it matches your string.")
while true do

local s = io.read()
local c = 1
local st = ""
local t = 0
while true do

t = t + 1
local l = rl()
print(c.." "..#s.." "..st..l.." "..t)
if l == string.sub(s, c, c) then
st = st..l
c = c + 1
end
if c > #s then
print("Total Attempts: "..t)
break
end

end

end

end[/lua]

This little bit of lua may not be much (and certainly not genetic), but it was able to reproduce your string in 15534 tries :v:

[sim642]

I haven't done anything with GA, but I think I'll soon do just to try.
Anyways the string matcher could be limited to only suitable character set without any control characters as they most probably won't be in your original string.

[Jookia]

I ask you as a fellow programmer to remove the code from the top page. It's possibly the worst example of anything I've ever seen ever. Either that or get your programming rights revoked.

[ZeekyHBomb]

Or instead of bitching you could give constructive criticism.

[Jookia]

I don't know where to ask for constructive criticism. Maybe some comments?

[backwardspy]

I wasn't going to post this because I'm horribly ashamed of the code...
Maybe it'll give someone a laugh (or possibly a heart attack, in which case I do apologise)

#define WIN32_LEAN_AND_MEAN
#include <windows.h>

#include <map>
#include <iostream>
#include <string>	// memcpy lives here usually

const unsigned int MAX_CHROMO = 100;
const unsigned int MAX_GENES = 20;

// Setup some relations to the different operands
enum Op
{
	OP_0 = 0x0,
	OP_1 = 0x1,
	OP_2 = 0x2,
	OP_3 = 0x3,
	OP_4 = 0x4,
	OP_5 = 0x5,
	OP_6 = 0x6,
	OP_7 = 0x7,
	OP_8 = 0x8,
	OP_9 = 0x9,
	OP_ADD = 0xA,
	OP_SUB = 0xB,
	OP_MUL = 0xC,
	OP_DIV = 0xD
};

void PrintEqu(unsigned int Eq[MAX_GENES], bool Preserve = false)
{
	bool expectingNum = true;
			
	// Go through each one of its genes
	for(int i = 0; i < MAX_GENES; i++)
	{
		if(!Preserve)
		{
			if(expectingNum)	// If we need a number...
			{
				if(Eq[i] < 0x0 || Eq[i] > 0x9) continue;	// Not a number; ignore.

				std::cout << Eq[i] << " ";

				expectingNum = false;
			}
			else	// We need an operation (+ - * /)
			{
				if(Eq[i] < 0xA || Eq[i] > 0xD) continue;	// Not an operation, ignore

				switch(Eq[i])
				{
				case(OP_ADD):
					std::cout << "+ ";
					break;
				case(OP_SUB):
					std::cout << "- ";
					break;
				case(OP_MUL):
					std::cout << "* ";
					break;
				case(OP_DIV):
					std::cout << "/ ";
					break;
				}

				expectingNum = true;
			}
		}
		else
		{
			if(Eq[i] >= 0x0 && Eq[i] <= 0x9) std::cout << Eq[i] << " ";
			else if(Eq[i] >= 0xA && Eq[i] <= 0xD)
			{
				switch(Eq[i])
				{
				case(OP_ADD):
					std::cout << "+ ";
					break;
				case(OP_SUB):
					std::cout << "- ";
					break;
				case(OP_MUL):
					std::cout << "* ";
					break;
				case(OP_DIV):
					std::cout << "/ ";
					break;
				}
			}
		}
	}
}

void FindSolution(double Target)
{
	// Make an array of chromosomes
	unsigned int chromo[MAX_CHROMO][MAX_GENES];
	double scores[MAX_CHROMO];	// Keeps track of the scores

	// Generate a random load of chromosomes
	for(int i = 0; i < MAX_CHROMO; i++)
	{
		for(int j = 0; j < MAX_GENES; j++)
		{
			chromo[i][j] = rand() % 13;
		}
	}

	// Now attempt to solve the algorithm
	bool solved = false;
	unsigned int generationCount = 1;
	unsigned int solution[MAX_CHROMO];
	while(!solved)
	{
		// For each chromosome...
		for(int i = 0; i < MAX_CHROMO; i++)
		{
			unsigned int lastOp = 0;
			double runningTotal = 0.0;
			bool expectingNum = true;

			// Go through each one of its genes
			for(int j = 0; j < MAX_GENES; j++)
			{
				if(expectingNum)	// If we need a number...
				{
					if(chromo[i][j] < 0x0 || chromo[i][j] > 0x9) continue;	// Not a number; ignore.

					if(lastOp == 0)	// We haven't hit an operator yet...
					{
						runningTotal = chromo[i][j];
					}
					else	// We HAVE hit an operator
					{
						switch(lastOp)
						{
						case(OP_ADD):
							runningTotal += chromo[i][j];	// Add it
							break;
						case(OP_SUB):
							runningTotal -= chromo[i][j];	// Subtract it
							break;
						case(OP_MUL):
							runningTotal *= chromo[i][j];	// Multiply it
							break;
						case(OP_DIV):
							if(chromo[i][j] != 0x0)
								runningTotal /= chromo[i][j];	// Divide it
							break;
						}
					}

					expectingNum = false;
				}
				else	// We need an operation (+ - * /)
				{
					if(chromo[i][j] < 0xA || chromo[i][j] > 0xD) continue;	// Not an operation, ignore

					lastOp = chromo[i][j];

					expectingNum = true;
				}
			}

			// Score the chromosome based on how well it did
			if(abs(Target - runningTotal) == 0)
			{
				solved = true;

				memcpy(solution, chromo[i], sizeof(unsigned int) * MAX_GENES);

				break;
			}
			scores[i] = 1.0 / abs(Target - runningTotal);
		}

		if(solved)
		{
			break;
		}

		// Add up all the scores
		double totalScore = 0.0;
		for(int i = 0; i < MAX_CHROMO; i++)
		{
			totalScore += scores[i];
		}

		// Now generate an arbitrary sized roulette wheel
		const unsigned int WHEEL_SIZE = 1000;
		unsigned int wheel[WHEEL_SIZE][MAX_GENES];
		unsigned int totalFilled = 0;
		for(int i = 0; i < MAX_CHROMO; i++)
		{
			// Truncate the proportion
			unsigned int proportion = ((scores[i] / totalScore) * (double)WHEEL_SIZE);
			
			totalFilled += proportion;

			for(int j = 0; j < proportion; j++)
			{
				memcpy(wheel[j], chromo[i], sizeof(unsigned int) * MAX_GENES);	// supah fast braindead memcpy
			}
		}

		/// START PARENT STUFF
		unsigned int newChromo[MAX_CHROMO][MAX_GENES];
		for(unsigned int z = 0; z < MAX_CHROMO / 2; z += 2)
		{
			// Now to choose two parents from that wheel
			unsigned int parents[2][MAX_GENES];
			memcpy(parents[0], wheel[rand() % totalFilled], sizeof(unsigned int) * MAX_GENES);	// i feel unsafe :C
			memcpy(parents[1], wheel[rand() % totalFilled], sizeof(unsigned int) * MAX_GENES);	// again...

			// At a certain crossover rate, swap the genes over
			if(rand() % 100 <= 70)	// About 70%
			{
				unsigned int index = rand() % MAX_GENES;

				for(unsigned int i = index; i < MAX_GENES; i++)
				{
					unsigned int tempGene;
					memcpy(&tempGene, &parents[0][i], sizeof(unsigned int));	// seriously now?
					memcpy(&parents[0][i], &parents[1][i], sizeof(unsigned int));	// this is getting ridiculous
					memcpy(&parents[1][i], &tempGene, sizeof(unsigned int));	// /me shoots self
				}
			}

			// Now do some low chance mutation
			for(unsigned int i = 0; i < MAX_GENES; i++)
			{
				if(rand() % 100 <= 1)	// About 0.1%
					parents[0][i] = rand() % 13;
				if(rand() % 100 <= 1)	// About 0.1%
					parents[1][i] = rand() % 13;
			}

			// Put them in the next generation of chromosomes
			memcpy(newChromo[z], parents[0], sizeof(unsigned int) * MAX_GENES);	// dont... say... a word.
			memcpy(newChromo[z + 1], parents[1], sizeof(unsigned int) * MAX_GENES);
		}

		/// END PARENT STUFF

		// Copy over the new chromosome values
		memcpy(chromo, newChromo, sizeof(unsigned int) * MAX_CHROMO * MAX_GENES);

		generationCount++;
	}

	std::cout << std::endl << "=== Solution found after " << generationCount << " generations === " << std::endl;
	PrintEqu(solution);
	std::cout << std::endl << "=== ===" << std::endl << std::endl;
	std::cout << std::endl;
}

int main()
{
	while(true)
	{
		// Seed our random generator nicely
		srand(GetTickCount());

		std::cout << "Enter a target number > ";

		double target;

		// Validate our input
		while(!(std::cin >> target))
		{
			std::cout << std::endl << "That aint a number bro..." << std::endl << std::endl;
			std::cout << "Try again > ";

			// Clear the cin error flags and input buffer
			std::cin.clear();
			std::cin.ignore(1000, '\n');
		}

		// Clear some space
		std::cout << std::endl << std::endl;

		std::cout << "Executing genetic algorithm..." << std::endl;

		FindSolution(target);
	}

	return 0;
}

I wrote this sometime around midnight, for some reason. I have no idea why I made an enum to hold all those operations, that's a stupid way of doing it :v:

Basically you give this thing a number and it's supposed to evolve a right-to-left equation that produces that number.

Example:

Enter a target number > 500

Executing genetic algorithm...

=== Solution found after 384 generations ===
2 + 5 * 9 - 7 * 9 - 4
=== ===

Oh an ignore that random comments to myself everywhere, I start talking to myself about half way down :saddowns:

Edit:
Christ, that code gets worse every time I look at it

[Jookia]

[url]http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/[/url]

I just implemented that as an example program, I'm going to clean it up, comment and post it here in a bit.

[quote]Please enter some ASCII text to be used:
Hello, Facepunch! "I just implemented that as an example program, I'm going to clean it up, comment and post it here in a bit."

Alright, after 837 generations, the top chromosone is: "Hello, Facepunch! "I just implemented that as an example program, I'm going to clean it up, comment and post it here in a bit."", a perfect match![/quote]

[editline]8th January 2011[/editline]

Alrighty, here is is.

[cpp]// [url]http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/[/url]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::sort
using namespace std;

#include <cstdlib> // rand, abs
#include <ctime> // time

string targetText; // The target string to reach.

// Helper methods implemented at the bottom of the file.
bool chromosoneSorter(const string& chromosoneA, const string& chromosoneB);
int getRandomInRange(int start, int end);
int clamp(int number, int start, int end);
bool isASCII(const string& text);

// Returns a fitness based on how close to targetString the chromosone is.
int getFitness(const string& chromosone)
{
int fitness = 0; // Best fitness, no differences.

for(unsigned int i = 0; i < chromosone.length(); ++i)
{
char chromosoneChar = chromosone[i];
char targetChar = targetText[i];

// Subtract the ASCII difference between both characters from the fitness,
// that way 'b' is fitter than 'c' when compared to 'a'.

fitness -= abs(targetChar - chromosoneChar);
}

return fitness;
}

// Create two children from two parents.
void breedTwoChildren(const string& parentA, const string& parentB,
string* childA, string* childB)
{
*childA = parentA;
*childB = parentB;

// Crossover parts of the chromosones.
if(getRandomInRange(0, 5) == 0) // 20% chance of crossover.
{
int crossoverPoint = rand() % parentA.length();

childA->replace(childA->begin(), childA->begin() + crossoverPoint,
parentB.begin(), parentB.begin() + crossoverPoint);

childB->replace(childB->begin(), childB->begin() + crossoverPoint,
parentA.begin(), parentA.begin() + crossoverPoint);
}

// Mutate the children.
if(getRandomInRange(0, 5) == 0) // 20% chance of mutation.
{
// Chose either childA or childB, 50% chance of either.
string* child = ((getRandomInRange(0, 1)) ? childA : childB);

// The idea of this method of mutation is to select a random number in the
// word and choose a random number that's within the range of maxFitnessLoss
// above or below it. This way fitness below maxFitnessLoss won't be loss.
int position = getRandomInRange(0, child->length());

int maxFitnessLoss = 10;
char* actualChar = &(*child)[position];
char letter = *actualChar - maxFitnessLoss;

letter += getRandomInRange(0, (maxFitnessLoss * 2));
letter = clamp(letter, 32, 126); // Don't go outside the ASCII range.

*actualChar = letter;
}
}

// Fills the population with children of breeders.
vector<string> breedPopulation(const vector<string>& breeders,
int populationSize)
{
vector<string> newPopulation;

unsigned int unsignedSize = populationSize; // For the comparison below.

// Go through pairs of breeders and use them as parents to make children
// until newPopulation has at least populationSize.
for(int i = 0; newPopulation.size() < unsignedSize; i += 2)
{
string parentA = breeders[i % (breeders.size() + 1)];
string parentB = breeders[(i + 1) % (breeders.size() + 1)];

string childA;
string childB;

breedTwoChildren(parentA, parentB, &childA, &childB);

newPopulation.push_back(childA);
newPopulation.push_back(childB);
}

// Sheer off excess children.
newPopulation.erase(newPopulation.begin() + populationSize,
newPopulation.end());

return newPopulation;
}

// Does all the genetic stuff and uses the methods above.
void geneticAlgorithm(int generations, int populationSize)
{
vector<string> population;

// Randomize the chromosones.
for(int i = 0; i < populationSize; ++i)
{
string newChromosone;

for(unsigned int j = 0; j < targetText.length(); ++j)
{
// Get a char from the range of 32-126, the printable ASCII characters.
char randomChar = getRandomInRange(32, 126);
newChromosone += randomChar;
}

population.push_back(newChromosone);
}

int generation;

for(generation = 0; generation < generations; ++generation)
{
// The process used to pick which chromosones to breed is a hybrid.
// 1. Keep the top 10% fittest for breeding.
// 2. Take four random chromosones of the 90% fittest and keep the two
// fittest for breeding.

vector<string> breeders = population;
sort(breeders.begin(), breeders.end(), chromosoneSorter);

vector<string> randomBreeders;

int topTenCount = (breeders.size() / 10);

for(int i = 0; i < 4; ++i)
{
// Get a random breeder from the top ten.
int random = getRandomInRange(topTenCount, breeders.size() - 1);

randomBreeders.push_back(breeders[random]);
}

// Remove the 90% of breeders that won't be used then add the random ones.
breeders.erase(breeders.begin() + topTenCount, breeders.end());
breeders.insert(breeders.end(), randomBreeders.begin(),
randomBreeders.end());

// Set the population to the children of the breeders.
population = breedPopulation(breeders, populationSize);

// Perfect match!
if(getFitness(population[0]) == 0)
{
break;
}
}

cout << "\nAlright, after " << generation << " generations, the top" <<
" chromosone is \"" << population[0] << "\",";

if(getFitness(population[0]) == 0)
{
cout << " a perfect match!" << endl;
}
else
{
cout << " with a fitness rating of " << getFitness(population[0]) << "." <<
" (Less is better.)" << endl;
}
}

int main(void)
{
cout << "Please enter some ASCII text to be used:\n";

getline(cin, targetText);

while(!isASCII(targetText))
{
cout << "ASCII characters only, please!" << endl;
getline(cin, targetText);
}

if(targetText == "")
{
return 1;
}

srand(time(0)); // Want randomness.

geneticAlgorithm(1000, 500);
}

// Used for std::sort to sort chromosones by fitness, descending.
bool chromosoneSorter(const string& chromosoneA, const string& chromosoneB)
{
return getFitness(chromosoneA) > getFitness(chromosoneB);
}

inline int getRandomInRange(int start, int end)
{
return start + (rand() % ((end - start) + 1));
}

inline int clamp(int number, int start, int end)
{
int newNumber = number;

if(newNumber < start)
{
newNumber = start;
}

if(newNumber > end)
{
newNumber = end;
}

return newNumber;
}

bool isASCII(const string& text)
{
for(unsigned int i = 0; i < text.length(); ++i)
{
if(clamp(text[i], 32, 126) != text[i])
{
return false;
}
}

return true;
}[/cpp]

[20k]

[url]http://dl.dropbox.com/u/9317774/Genetic.rar[/url]

Here's one i made earlier :v:

[Whitewater]

[url]http://dl.dropbox.com/u/313549/GeneAlgo.zip[/url]

And here's one I made earlier. You just need to write an interface, like the Test class.

[20k]

[QUOTE=Whitewater;27283910][url]http://dl.dropbox.com/u/313549/GeneAlgo.zip[/url]

And here's one I made earlier. You just need to write an interface, like the Test class.[/QUOTE]

your header is rich in functionality :v:

[RyanDv3]

FYI: Genetic algorithm does not mean "make up an extremely inefficient way to copy data".

Do you realize that you are attempting to find an answer by comparing random results [i]to the actual answer[/i]?

I'd go so far as to say you aren't actually doing genetic algorithms, because if you were, then real-world evolution would be starting a pile of mold, comparing it to a human being, mutating, and then repeating this process for several billion years.

It isn't about doing something straightforward in a roundabout way, it's about creating [b]emergent[/b] complexity from simplicity. Or at least that's the reason that I think has the most merit, I guess it's possible that one day we might also use this concept to train a computer to do something that is too complex to program/ define by traditional means.

[20k]

[QUOTE=RyanDv3;27286114]FYI: Genetic algorithm does not mean "make up an extremely inefficient way to copy data".

Do you realize that you are attempting to find an answer by comparing random results [i]to the actual answer[/i]?

I'd go so far as to say you aren't actually doing genetic algorithms, because if you were, then real-world evolution would be starting a pile of mold, comparing it to a human being, mutating, and then repeating this process for several billion years.

It isn't about doing something straightforward in a roundabout way, it's about creating [b]emergent[/b] complexity from simplicity. Or at least that's the reason that I think has the most merit, I guess it's possible that one day we might also use this concept to train a computer to do something something that is too complex to train by traditional means.[/QUOTE]

Yess.. comparing your result to your actual result defeats the point somewhat.

[mmavipc]

[QUOTE=Icedshot;27286360]Yess.. comparing your result to your actual result defeats the point somewhat.[/QUOTE]

then how would the natural selection part of the algo work?

[DrLuke]

Those that die because they're inefficient and thus starve/get killed are out of the game. The others survive. They make children, and those children will get genes mixed from both parents, and maybe 1 or 2 random mutations. If the mutation is useful, it will not die. If the mutation makes it worse, it will eventually die, or survive long enough to breed again and create a new species.

[Gbps]

[QUOTE=DrLuke;27289032]Those that die because they're inefficient and thus starve/get killed are out of the game. The others survive. They make children, and those children will get genes mixed from both parents, and maybe 1 or 2 random mutations. If the mutation is useful, it will not die. If the mutation makes it worse, it will eventually die, or survive long enough to breed again and create a new species.[/QUOTE]
I'm afraid that ascii characters do not have the ability to consume other ascii characters

[DrLuke]

[QUOTE=Gbps;27289617]I'm afraid that ascii characters do not have the ability to consume other ascii characters[/QUOTE]

It really depends how you design your whole algorithm.

[Niteshifter]

[QUOTE=Chris220;27276914]
I wrote this sometime around midnight, for some reason. I have no idea why I made an enum to hold all those operations, that's a stupid way of doing it :v:

Oh an ignore that random comments to myself everywhere, I start talking to myself about half way down :saddowns:
[/QUOTE]

I think everyone talks to themselves in the comments when coding late at night :v:

[RyanDv3]

Here's an idea: have your individuals exist as files within a folder. The file's contents will serve two functions: 1) a string that determines how it targets other filenames for deletion, and 2) a string that determines how it generates new filenames for it's children.

Could possibly use regular expressions for the file-creation/ file-deletion strings. Maybe you wouldn't want to have them delete files, but rather, convert them, which would be how they reproduce, instead of some scheduled reproduction cycle. Handling population size I imagine would be interesting. You might need to introduced some sort of thing that works as food or energy, but obviously more appropriate, not as contrived. The other thing to take in mind is preventing mass-extinction.

[DrLuke]

Why prevent mass extinction? It's part of evolution.

[Smashmaster]

My exceedingly simple algorithm:

Input organism.
Make single copy of input.
Randomize copy a bit.
Test copy against input.
Output whichever is better.

Negative evolution can't occur. After each generation, the new copy will always be either better or the same.

The test is the crux of the algorithm, though. It's what determines what you're looking for and what you want the end product to be.

[Niteshifter]

Not mine, but another example of the GA being implemented.

[media]http://www.youtube.com/watch?v=Fp9kzoAxsA4[/media]

[Ihades]

I tried reading up on GAs but I don't properly understand how this could be of practical use. Could someone explain it to me?

[Samperson123]

[QUOTE=Ihades;27295988]I tried reading up on GAs but I don't properly understand how this could be of practical use. Could someone explain it to me?[/QUOTE]

"Organisms" created through genetic algorithms could be moved into a robot and function in the real world, or could be used to find the strongest structure you could build with a given amount of material. Basically, anything with a quantifiable amount of success could be made with a genetic algorithm.

[mmavipc]

[QUOTE=Ihades;27295988]I tried reading up on GAs but I don't properly understand how this could be of practical use. Could someone explain it to me?[/QUOTE]

[url]http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/[/url]

[Jookia]

The Hello World is a bad example, but it shows the concept well: To use genetics to find the closest 'organism' to the string.

You could always use one to make city layouts, the fitness being based on how many houses can fit in the space while keeping people happy and having enough resources.

[Ihades]

Hm, this seems quite interesting. I'm going to spend sometime on this during my free time, then.

[iPope]

GA is really interesting, I can never think of something to make with them though. Maybe I'll make miniature creatures that are based on how much food they pick up, and have genetic instructions that decide their behaviour.

[20k]

The point of a genetic algorithm isnt to test the results against the answer, but to put the results through a test and gauge how well they do. Testing the results against the answer isnt a genetic algorithm, because when you are trying to adapt something to a specific test, you dont know what your final result wants to be.

[Dr Magnusson]

[QUOTE=Icedshot;27302574]The point of a genetic algorithm isnt to test the results against the answer, but to put the results through a test and gauge how well they do. Testing the results against the answer isnt a genetic algorithm, because when you are trying to adapt something to a specific test, you dont know what your final result wants to be.[/QUOTE]
This isn't true. A genetic algorithm is any kinda of algorithm that adapts itself based on success. You can't really expose programmatic algorithms to natural selection as they aren't alive, nor are in an environment where death is even an option, so you have to introduce these manually, by means of a fitness function and "breeding". Jookia's code is a perfect example of this, while OP's lack the hereditary aspect.

Your statement is actually quite silly, cause without a goal, what will you compare the performance of an algorithm to?

I see where you're coming from, letting an entity with the means to replicate and mutate free in a world, and simply having it adapt to its environment, but in the case of genetic algorithms, there are no inputs apart from the ones you give it, and without any kind of feedback as to how it is doing, it wouldn't know what direction to evolve in.

You cannot have genetic algorithms without artifical selection, which is what Jookia's code employs.

In other news, Vicis and I have been working on something somewhat relevant to this, for Gmod. It's basically a recorder with pattern recognition of sorts. Whenever a player is kicked or banned, it logs a number of variables associated with that player (props, delay between prop spawns, etc.). It compares those values with the values it has already recorded for that kick/ban reason, and checks whether they are similar to the other ones. If the values of previous kicks or bans of this type are similar to those of this one, that would suggest that it is a common factor in determining whether the player is commiting an offence. It then increases the importance (or weight if you're into neural networks) of that charactetistic.

Eventually it will have a list of kick/ban reasons, and for each of them a list of variables associated with them, along with the value it is usually at when admins have thrown the offender out, and their apparent importance.

Here's an example: [URL]http://errur.com/test/Forseti.php?action=browse&ip=80.167.81.30[/URL]

What it can then do is compare those values to those of players currently on the server, and calculate a probability that someone is committing an offence based on how similar those values are.

The basic confidence of the program starts at 0, and currently we've set a maximum confidence of 10. If the confidence is less than 50%, it'll only suggest to admins if it notices something is up. And increase in confidence if the player is then banned for that reason, or an admin gives him some positive feedback on the suggestion. Confidence is decreased if the opposite is given.

The more confident he is over the 50% mark, the smaller probability of an offence in action needs to be before it acts on its own. At 50% the probability must be 90% or higher, and at 100% confidence, it can be as low as 50% probability.

Dear god, wall of text.