Question

C++. Need some help getting started.

We will also have the following two functions: 1. A mutate function that randomly modifies a chromosome. 2. A crossover function that takes two chromosomes and splits each one at the same spot, then combines them together. Our genetic algorithm works by iterating over generations of chromosomes via the following process: 1. Generate random population. 2. Until we get an answer that is good enough, do the next steps in a loop: (a) Do the following in a loop for twice as many times as our population size: i. Choose a chromosome from our population. With probability mr mutate the chromosome. ii. With probability cr, choose another random chromosome from our population and perform crossover. iii. Add the chromosome over to the new population. If we didn’t perform crossover or mutation this would copy over the chromosome from the previous generation. (b) Sort our new population by fitness. Keep the best half of it. (c) Replace our population by the new population. 3. Print out the best chromosome from the final population. Note that because our mutate function changes a chromosome at random and our crossover function simply combines existing chromosomes, none of the above process explicitly directs our program toward a solution. However, by random modification over a period of time keeping only the most fit chromosomes we can end up at an answer. 3 Our Genetic Algorithm For this exercise, we will implement a simple genetic algorithm. It will attempt to guess the content of a std::string passed as a command-line argument to our program. We will limit our strings to only lower-case letters. Note: if you want, you may include other printable characters, however the below description assumes you are using only lower-case letters. Our chromosomes will store a std::string as data. Mutation will randomly choose a character in the std::string and either increment or decrement it. Crossover will randomly choose an index and create a new string by taking the first part of one of the strings and concatenating it to the end of the other string. For example, suppose one of our chromosomes has the following data: abcdefg. A mutation might result in: abddefg or abcdeeg. Make sure that when mutating, we keep the result within the range for lower-case letters. For example, if the letter is a and we would decrement it, make it wrap to z. Similarly, if the letter is z and we would increment it, make it wrap to a. This makes sure our strings always have only lower-case letters in them. Suppose we have two chromosomes with the following data: one has abcdefg and the other has zyxwvut. A crossover would first randomly choose a position, say 4. This means we are splitting at position 4 so we take the first 4 characters of the first string: abcd and concatenate them with the last 3 characters of the second string: vut to create the new chromosome abcdvut. 2 We will assume that all strings have the same size in our implementation. We also have some target string that we are trying to guess. This is provided as argv[1] to our program. We can generate random chromosomes for our initial population by: Chromosome randomChromosome(int size) { std::ostringstream sout; for (int i = 0; i < size; i++) { sout << (char) ((rand() % 26) + 97); } return Chromosome(sout.str()); } where size is the length of our target string. Note that when we pick a random number, we first make sure it is in the range of [0, 26) then we shift it up by 97 because 97 is a in ASCII. This gives us a random lower-case letter. Our fitness function should return the sum of the differences between each character of the chromosome and the target. For example, given abcd and target string bbcd, the fitness function returns 1 because the first characters are 1 apart and the others are all the same. If we had abcd and target string bcde, our fitness function would return 4 because all four characters are 1 off from the target. Therefore, a fitness of 0 indicates a perfect match. Again, we assume all strings are the same size as the target. If you want to allow strings of different lengths, think about how you can change the fitness function so that it would give strings of the wrong length a poor fitness score. You must implement the mutate and crossover functions of the Chromosome class and the following function to run the algorithm: Chromosome runGA(std::string target, int popSize, double mr, double cr); where target is the target string, popSize is the size of the population we keep on each generation, mr is the mutation rate, and cr is the crossover rate. A main function has already been provided for testing purposes. It assumes the target string, pop size, mutation rate, and crossover rate have been passed as command-line arguments. The mutation rate and crossover rate values tell us how often we perform each operation. They will be in the range [0, 1] and act as probabilities. For example, suppose we have a mutation rate of 0.02 (that is, we mutate 2% of the time). To test if we should perform mutation on this chromosome we generate a random number in the range [0, 1] and check if the number we generated is <= the mutation rate. Because our number was generated at at random, it will fall in the range [0, 0.02] 2% of the time. When it does, we perform mutation. Apply the same logic for cr. Changing the population size will allow more chances for change per generation but make each generation take longer to compute.

#include "Chromosome.h"

Chromosome randomChromosome(int size)
{
std::ostringstream sout;
for (int i = 0; i < size; i++)
{
sout << (char) ((rand() % 26) + 97);
}
return Chromosome(sout.str());
}

Chromosome runGA(std::string target, int popSize, double mr, double cr)
{
// implement genetic algorithm here

// use a vector<Chromosome> for the population
// I recommend using STL algorithms such as std::sort

// remember, the GA is a loop until you find a chromosome
// of fitness 0

// on each iteration, you should be generating a new population
// of twice the size of popSize, filling it with chromosomes
// that have been mutated, crossed, and/or copied based on
// the probabilities given by mr and cr
// then sort it and keep only the best half as the population
// for the next iteration
// when you find a chromosome of fitness 0, you have finished and
// you should return it
}

int main(int argc, char **argv)
{
srand(time(0));
std::string target = argv[1];
int popSize = atoi(argv[2]);
double mr = atof(argv[3]);
double cr = atof(argv[4]);
Chromosome answer = runGA(target, popSize, mr, cr);

std::cout << "Solution found: " << answer << std::endl;
}

#ifndef CHROMOSOME_H
#define CHROMOSOME_H

#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

class Chromosome
{
private:
std::string data;
public:
Chromosome(std::string d);

std::string getData() const;
Chromosome mutate() const;
Chromosome crossover(const Chromosome& other) const;
int fitness(const std::string& target) const;
};

std::ostream& operator<<(std::ostream& os, const Chromosome& c);

#endif

#include "Chromosome.h"

Chromosome::Chromosome(std::string d) : data(d)
{
}

std::string Chromosome::getData() const
{
return data;
}

Chromosome Chromosome::mutate() const
{
// implement mutation here

// your mutate function should randomly choose
// a character to modify then randomly choose
// to either increment or decrement it
// make sure to keep in range of lower-case letters!
}

Chromosome Chromosome::crossover(const Chromosome& c) const
{
// implement crossover here

// your crossover function should randomly choose
// an index in the range of the chromosomes
// then take the first part (up to the index) from *this
// and the last part (from index to end) from c and
// concatenate those together then return the result

  
}

int Chromosome::fitness(const std::string& target) const
{
// computes fitness by sum of differences of each character
// smaller is better (0 is perfect)

int diff = 0;
for (int i = 0; i < data.size(); i++)
{
int change = std::abs(data[i] - target[i]);
if (change > 13) // handles wrap around for letters
{
change = 26 - change;
}
diff += change;
}
return diff;
}

std::ostream& operator<<(std::ostream& os, const Chromosome& c)
{
os << c.getData();
return os;
}