C++. Need some help getting started. We will also have the following two functio
ID: 3678637 • Letter: C
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;
}
Explanation / Answer
#include <string>
#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <math.h>
using std::string;
#define CROSSOVER_RATE 0.7
#define MUTATION_RATE 0.001
#define POP_SIZE 100 //must be an even number
#define CHROMO_LENGTH 300
#define GENE_LENGTH 4
#define MAX_ALLOWABLE_GENERATIONS 400
#define RANDOM_NUM ((float)rand()/(RAND_MAX+1))
// define a data structure which will define a chromosome
struct chromo_typ
{
//the binary bit string is held in a std::string
string bits;
float fitness;
chromo_typ(): bits(""), fitness(0.0f){};
chromo_typ(string bts, float ftns): bits(bts), fitness(ftns){}
};
/////////////////////////////////prototypes/////////////////////////////////////////////////////
void PrintGeneSymbol(int val);
string GetRandomBits(int length);
int BinToDec(string bits);
float AssignFitness(string bits, int target_value);
void PrintChromo(string bits);
void PrintGeneSymbol(int val);
int ParseBits(string bits, int* buffer);
string Roulette(int total_fitness, chromo_typ* Population);
void Mutate(string &bits);
void Crossover(string &offspring1, string &offspring2);
int main()
{
//seed the random number generator
srand((int)time(NULL));
while (true)
{
//storage for our population of chromosomes.
chromo_typ Population[POP_SIZE];
//get a target number from the user. (no error checking)
float Target;
cout << " Input a target number: ";
cin >> Target;
cout << endl << endl;
//first create a random population, all with zero fitness.
for (int i=0; i<POP_SIZE; i++)
{
Population[i].bits = GetRandomBits(CHROMO_LENGTH);
Population[i].fitness = 0.0f;
}
int GenerationsRequiredToFindASolution = 0;
//we will set this flag if a solution has been found
bool bFound = false;
//enter the main GA loop
while(!bFound)
{
float TotalFitness = 0.0f;
// test and update the fitness of every chromosome in the
// population
for (int i=0; i<POP_SIZE; i++)
{
Population[i].fitness = AssignFitness(Population[i].bits, Target);
TotalFitness += Population[i].fitness;
}
for (i=0; i<POP_SIZE; i++)
{
if (Population[i].fitness == 999.0f)
{
cout << " Solution found in " << GenerationsRequiredToFindASolution << " generations!" << endl << endl;;
PrintChromo(Population[i].bits);
bFound = true;
break;
}
}
// by applying crossover and mutation. Do this until the desired number of offspring
// have been created.
//define some temporary storage for the new population we are about to create
chromo_typ temp[POP_SIZE];
int cPop = 0;
//loop until we have created POP_SIZE new chromosomes
while (cPop < POP_SIZE)
{
// we are going to create the new population by grabbing members of the old population
string offspring1 = Roulette(TotalFitness, Population);
string offspring2 = Roulette(TotalFitness, Population);
//add crossover dependent on the crossover rate
Crossover(offspring1, offspring2);
//now mutate dependent on the mutation rate
Mutate(offspring1);
Mutate(offspring2);
//fitness scores)
temp[cPop++] = chromo_typ(offspring1, 0.0f);
temp[cPop++] = chromo_typ(offspring2, 0.0f);
}//end loop
//copy temp population into main population array
for (i=0; i<POP_SIZE; i++)
{
Population[i] = temp[i];
}
++GenerationsRequiredToFindASolution;
// exit app if no solution found within the maximum allowable number
// of generations
if (GenerationsRequiredToFindASolution > MAX_ALLOWABLE_GENERATIONS)
{
cout << "No solutions found this run!";
bFound = true;
}
}
cout << " ";
}//end while
return 0;
}
//get random bits
string GetRandomBits(int length)
{
string bits;
for (int i=0; i<length; i++)
{
if (RANDOM_NUM > 0.5f)
bits += "1";
else
bits += "0";
}
return bits;
}
// get binary to decimal
int BinToDec(string bits)
{
int val = 0;
int value_to_add = 1;
for (int i = bits.length(); i > 0; i--)
{
if (bits.at(i-1) == '1')
val += value_to_add;
value_to_add *= 2;
}//next bit
return val;
}
int this_gene = 0;
for (int i=0; i<CHROMO_LENGTH; i+=GENE_LENGTH)
{
//convert the current gene to decimal
this_gene = BinToDec(bits.substr(i, GENE_LENGTH));
if (bOperator)
{
if ( (this_gene < 10) || (this_gene > 13) )
continue;
else
{
bOperator = false;
buffer[cBuff++] = this_gene;
continue;
}
}
//find a gene which represents a number
else
{
if (this_gene > 9)
continue;
else
{
bOperator = true;
buffer[cBuff++] = this_gene;
continue;
}
}
}
for (i=0; i<cBuff; i++)
{
if ( (buffer[i] == 13) && (buffer[i+1] == 0) )
buffer[i] = 10;
}
return cBuff;
}
float AssignFitness(string bits, int target_value)
{
//holds decimal values of gene sequence
int buffer[(int)(CHROMO_LENGTH / GENE_LENGTH)];
int num_elements = ParseBits(bits, buffer);
for (int i=0; i < num_elements-1; i+=2)
{
switch (buffer[i])
{
case 10:
result += buffer[i+1];
break;
case 11:
result -= buffer[i+1];
break;
case 12:
result *= buffer[i+1];
break;
case 13:
result /= buffer[i+1];
break;
}
}
// Now we calculate the fitness.
// and assign an arbitarily high fitness score if this is so.
if (result == (float)target_value)
return 999.0f;
else
return 1/(float)fabs((double)(target_value - result));
// return result;
}
void PrintChromo(string bits)
{
//holds decimal values of gene sequence
int buffer[(int)(CHROMO_LENGTH / GENE_LENGTH)];
//parse the bit string
int num_elements = ParseBits(bits, buffer);
for (int i=0; i<num_elements; i++)
{
PrintGeneSymbol(buffer[i]);
}
return;
}
void PrintGeneSymbol(int val)
{
if (val < 10 )
cout << val << " ";
else
{
switch (val)
{
case 10:
cout << "+";
break;
case 11:
cout << "-";
break;
case 12:
cout << "*";
break;
case 13:
cout << "/";
break;
}//end switch
cout << " ";
}
return;
}
// Mutates a chromosome's bits dependent on the MUTATION_RATE
void Mutate(string &bits)
{
for (int i=0; i<bits.length(); i++)
{
if (RANDOM_NUM < MUTATION_RATE)
{
if (bits.at(i) == '1')
bits.at(i) = '0';
else
bits.at(i) = '1';
}
}
return;
}
void Crossover(string &offspring1, string &offspring2)
{
if (RANDOM_NUM < CROSSOVER_RATE)
{
//create a random crossover point
int crossover = (int) (RANDOM_NUM * CHROMO_LENGTH);
string t1 = offspring1.substr(0, crossover) + offspring2.substr(crossover, CHROMO_LENGTH);
string t2 = offspring2.substr(0, crossover) + offspring1.substr(crossover, CHROMO_LENGTH);
offspring1 = t1; offspring2 = t2;
}
}
float FitnessSoFar = 0.0f;
for (int i=0; i<POP_SIZE; i++)
{
FitnessSoFar += Population[i].fitness;
if (FitnessSoFar >= Slice)
return Population[i].bits;
}
return "";
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.