fbpx

C++: Evolutionary Algorithm

Bjarne-stroustrup
 

Starting with:

  • The target string: "METHINKS IT IS LIKE A WEASEL".
  • An array of random characters chosen from the set of upper-case letters together with the space, and of the same length as the target string. (Call it theparent).
  • A fitness function that computes the ‘closeness’ of its argument to the target string.
  • A mutate function that given a string and a mutation rate returns a copy of the string, with some characters probably mutated.
  • While the parent is not yet the target:
  • copy the parent C times, each time allowing some random probability that another character might be substituted using mutate.
  • Assess the fitness of the parent and all the copies to the target and make the most fit string the new parent, discarding the others.
  • repeat until the parent converges, (hopefully), to the target.

#include <string>
#include <cstdlib>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>

std::string allowed_chars = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// class selection contains the fitness function, encapsulates the
// target string and allows access to it's length. The class is only
// there for access control, therefore everything is static. The
// string target isn't defined in the function because that way the
// length couldn't be accessed outside.
class selection
{
public:
	// this function returns 0 for the destination string, and a
	// negative fitness for a non-matching string. The fitness is
	// calculated as the negated sum of the circular distances of the
	// string letters with the destination letters.
	static int fitness(std::string candidate)
	{
		assert(target.length() == candidate.length());

		int fitness_so_far = 0;

		for (int i = 0; i < target.length(); ++i)
		{
			int target_pos = allowed_chars.find(target[i]);
			int candidate_pos = allowed_chars.find(candidate[i]);
			int diff = std::abs(target_pos - candidate_pos);
			fitness_so_far -= std::min(diff, int(allowed_chars.length()) - diff);
		}

		return fitness_so_far;
	}

	// get the target string length
	static int target_length() { return target.length(); }
private:
	static std::string target;
};

std::string selection::target = "METHINKS IT IS LIKE A WEASEL";

// helper function: cyclically move a character through allowed_chars
void move_char(char& c, int distance)
{
	while (distance < 0)
	distance += allowed_chars.length();
	int char_pos = allowed_chars.find(c);
	c = allowed_chars[(char_pos + distance) % allowed_chars.length()];
}

// mutate the string by moving the characters by a small random
// distance with the given probability
std::string mutate(std::string parent, double mutation_rate)
{
	for (int i = 0; i < parent.length(); ++i)
	if (std::rand()/(RAND_MAX + 1.0) < mutation_rate)
	{
		int distance = std::rand() % 3 + 1;
		if(std::rand()%2 == 0)
		move_char(parent[i], distance);
		else
		move_char(parent[i], -distance);
	}
	return parent;
}

// helper function: tell if the first argument is less fit than the
// second
bool less_fit(std::string const& s1, std::string const& s2)
{
	return selection::fitness(s1) < selection::fitness(s2);
}

int main()
{
	int const C = 100;

	std::srand(time(0));

	std::string parent;
	for (int i = 0; i < selection::target_length(); ++i)
	{
		parent += allowed_chars[std::rand() % allowed_chars.length()];
	}

	int const initial_fitness = selection::fitness(parent);

	for(int fitness = initial_fitness;
	fitness < 0;
	fitness = selection::fitness(parent))
	{
		std::cout << parent << ": " << fitness << "\n";
		double const mutation_rate = 0.02 + (0.9*fitness)/initial_fitness;
		typedef std::vector<std::string> childvec;
		childvec childs;
		childs.reserve(C+1);

		childs.push_back(parent);
		for (int i = 0; i < C; ++i)
		childs.push_back(mutate(parent, mutation_rate));

		parent = *std::max_element(childs.begin(), childs.end(), less_fit);
	}
	std::cout << "final string: " << parent << "\n";
}

Example output:

BBQYCNLDIHG   RWEXN PNGFTCMS: -203
ECPZEOLCHFJBCXTXFYLZQPDDQ KP: -177
HBSBGMKEEIM BUTUGWKWNRCGSZNN: -150
EEUCGNKDCHN  RSSITKZPRBESYQK: -134
GBRFGNKDAINX TVRITIZPSBERXTH: -129
JEUFILLDDGNZCWYRIWFWSUAERZUI: -120
JESGILIGDJOZCWXRIWFVSXZESXXI: -109
JCSHILIIDIOZCTZOIUIVVXZEUVXI: -93
KDSHHLJIDIOZER LIUGXVXXFWW I: -76
KDSHGNMIDIOZHR LIUHXWXWFWW L: -69
LDSHHNMLDIOZKR LGSEXWXWFYV L: -59
LDSHHNMNDIOYKU LGSEXY WFYV M: -55
LCSHHNMLDHR IT LGSEZY WFYSBM: -44
LCSHHNMNBIR IT LGSEZY WFASBM: -36
LCSHHNMQBIQ JT LGQEZY WFASBM: -33
LCSIHNMRBIS JT LGQE Y WFASBM: -30
LESIHNMSBIS JR LGQE Y WFASBM: -27
LESIJNMSBIS JR LHOE A WFASBM: -21
LERIJNJSBIS JR LHOF A WFASEM: -19
LERIJNJSBIS JR LHLF A WFASEM: -16
NERIJNJS IS JR LHLF A WFASEM: -14
NERIJNJS IS JS LHLF A WFASEM: -13
NERIJNKS IS JS LHLF A WFASEM: -12
NERIJNKS IS JS LHKF A WFASEM: -11
NERIJNKS IS JS LHKF A WFASEM: -11
NERIJNKS IS JS LHKF A WEASEM: -10
NERIJNKS IS JS LHKF A WEASEM: -10
NERIJNKS IS JS LHKF A WEASEL: -9
NERIJNKS IS JS LHKF A WEASEL: -9
NETIJNKS IS JS LHKF A WEASEL: -7
NETIJNKS IS JS LHKF A WEASEL: -7
NETIJNKS IT JS LHKF A WEASEL: -6
NETIINKS IT JS LHKF A WEASEL: -5
NETIINKS IT JS LHKE A WEASEL: -4
NETHINKS IT JS LHKE A WEASEL: -3
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
METHINKS IT JS LIKE A WEASEL: -1
METHINKS IT JS LIKE A WEASEL: -1
METHINKS IT JS LIKE A WEASEL: -1
final string: METHINKS IT IS LIKE A WEASEL

SOURCE

Content is available under GNU Free Documentation License 1.2.