Genetic Algorithm

[Avidus]

Ive been tasked with creating a Genetic Algorithm to take an input string.
And then using Genetic Algorithms to reproduce what the input is.

So far I have no trouble with taking in the input and manipulating it around.
But the issue is that I dont know how to create a selection of strings filled with random characters (They dont have to be specifically numbers or letters just anything with a value in the unicode table.)
Or even if I set some strings with a scrabbled set of characters, I am still unable to compare how close it is to the input.

To make my question more simple, I have thought of ways for my solution, just not how to implement them, they are:

Use strlen on the input then use that as the size of the random string, then possibly use rand() to fill it with random characters.

And if possible pull my String apart each letter, translate those letters to their binary or unicode number then compare each letter to the letter in the same position of the random string.

Also it would be nice to know a way to have my program evolve until it has the right letters in the string.

Here is a copy of my code. (yes I understand there is some code that isnt needed, some of it is their to make it easier to debug without putting watches on variables.)

#include <iostream>
#include <string>

using namespace std;

int main()
{
char Entry[64];
char Check[64];
int StringsLength = 10;

cout << "Welcome to Genetic Algorithms! " << endl;
cout << "Please input a word or short sentence. " << endl;
cin.getline (Entry,64);

int EntryLength = strlen(Entry);
StringsLength = EntryLength;

strcpy( Check, Entry);
cout << std::endl << Check <<endl;
cout <<" This is what you answered. " << endl;
cout <<" Using Genetic Algorithms this program will attempt to recreate your entry. " << endl;
cout <<" Your Entry was: " << StringsLength << " Spaces long. " << endl;

system("pause");
return 0;
}

Thank you for your time, any constructive response is very appreciated.

[hamsterman]

To create and fill a string with random chars:

char* my_string = new char[EntryLength+1];
my_string[EntryLength] = 0;
for(int i = 0; i < EntryLength; i++) my_string = rand()%256;//or maybe 'a'+rand()%('z'-'a'); ? 

To calculate fitness:

int fit = 0;//0 is your goal
for(int i = 0; i < EntryLength; i++) fit += abs(Entry[i] - my_string[i]);

[Avidus]

Thats a fantastic answer, very very helpful, although it does error now with:
error C2440: '=' : cannot convert from 'int' to 'char *'

[Albatross]

All one needs to do to make that compile is add a [i] somewhere on line 3 of the first snippet.

EDIT: Fixed a typo.

-Albatross

[hamsterman]

a [i] somewhere on line 3 of the first snippet would indeed make it work.
sorry about the error.

[Avidus]

Of course, how could I miss that.

All of this code works perfectly now.
And there is but one problem remaining.

It needs to evolve and eventually get to whatever Entry is.
for testing purposes I stuck the last for loop inside a while loop which is:
while (RandomString != Entry)
followed by a cout << RandomString << endl;
this of course just spams me with the same Randomly generated string.
How would I get my Strings to evolve?

[Albatross]

Here's an idea. Maybe for each character that matches you limit the number of characters that are changed per loop by the random function by making the program skip over that character. Just a thought.

-Albatross

[Avidus]

That is quite a good idea, but im not sure if thats still a genetic algorithm, it sounds more like forced evolution.

[Albatross]

Forced evolution, you say... well, rand() is random. What I could also recommend that maybe is closer to what you're looking for is that ever so often you manipulate the bounds of the randomization process per character to give values that come over time closer and closer to Entry.

-Albatross

[Avidus]

The current idea im trying to implement is to have it generate 10 different random strings.
compare those strings to Entry, take the closest 20% and 2 other random strings out of the 10.
recreate another 10 random strings using the characters from these strings for example

222222222 and 333333333 are random generated.

repoduced result could be 2222233333 and 2323232323

and from those 2323233333 and 2222223232

except on a much more varying scale.

[hamsterman]

This won't bring anything new to the population. The right way to do this, I think would be:
Generate n random strings. Sort them by their fitness. Remove some individuals with the lowest fitness (that is highest, if you use the algorithm I wrote).You'll have to do some copying to keep the population of the right size. Keep some of the best strings untouched. For the rest of them, do mutation or crossover. Crossover is what you just said. Mutation is when you change a random car in a string with something random.

[Avidus]

I was thinking of trying to do a double crossover, but mutation is look like a better choice as the much lower chance of getting local minima. my only problem is im not 100% of how to code it, also just a quick question, i need to change 'my_string' to a 2D array, whats the easiest way to go about that?

Also im very thankful for all of the input so far. :)