write a C or C++ program that can read a txt file(test.txt) to perform a Crossov
ID: 3592633 • Letter: W
Question
write a C or C++ program that can read a txt file(test.txt) to perform a Crossover operation and the add time constraint to GA (genetic algorithm). The pseudo-code for the genetic algorithm is given as follows:
Initialize Population
Compute Fitness
while (not stop)
Crossover
Mutation
Compute Fitness
Roulette Wheel
Selection
Output the best schedule
The Crossover operation that you are going to implement is the two-point crossover. That is randomly selecting two positions, copy one block from a parent and copy the other two blocks from another parent accordingly shown as follows.
A B C D E F G H (Parent 1)
H A C D E F B G (Child)
E H A D B C G F (Parent 2)
For time, you may use clock(). The unit for time should be in seconds.
Explanation / Answer
main.cpp
#include <string>
#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <math.h>
using std::string;
#define CROSS 0.7
#define MUTATION 0.001
#define POPS 100
#define CHROM_LNT 300
#define GENE_LNT 4
#define ALLOW_GEN 400
#define RAND((float)rand()/(RAND_MAX+1))
struct chromType
{
string bit;
float fitties;
chromType(): bit(""), fitties(0.0f){};
chromType(string bts, float ftns): bit(bts), fitties(ftns){}
};
void dispGeneSym(int values);
string getRand(int lnt);
int bin2Dec(string bit);
float assFit(string bit, int tarVal);
void dispChrom(string bit);
void dispGeneSym(int values);
int parsingBit(string bit, int* buff);
string Roulette(int totFit, chromType* polulat);
void Mutate(string &bit);
void Crossover(string &off1, string &off2);
int main()
{
srand((int)time(NULL));
while (true)
{
chromType polulat[POPS];
float targets;
cout << " Input a target number: ";
cin >> targets;
cout << endl << endl;
for (int uu=0; uu<POPS; uu++)
{
polulat[uu].bit = getRand(CHROM_LNT);
polulat[uu].fitties = 0.0f;
}
int genForSoln = 0;
bool isFound = false;
while(!isFound)
{
float totFitties = 0.0f;
for (int uu=0; uu<POPS; uu++)
{
polulat[uu].fitties = assFit(polulat[uu].bit, targets);
totFitties += polulat[uu].fitties;
}
for (uu=0; uu<POPS; uu++)
{
if (polulat[uu].fitties == 999.0f)
{
cout << " Solution found in " << genForSoln << " generations!" << endl << endl;;
dispChrom(polulat[uu].bit);
isFound = true;
break;
}
}
chromType temporary[POPS];
int pops = 0;
while (pops < POPS)
{
string off1 = Roulette(totFitties, polulat);
string off2 = Roulette(totFitties, polulat);
Crossover(off1, off2);
Mutate(off1);
Mutate(off2);
temporary[pops++] = chromType(off1, 0.0f);
temporary[pops++] = chromType(off2, 0.0f);
}
for (uu=0; uu<POPS; uu++)
{
polulat[uu] = temporary[uu];
}
++genForSoln;
if (genForSoln > ALLOW_GEN)
{
cout << "No solutions found this run!";
isFound = true;
}
}
cout << " ";
}
return 0;
}
string getRand(int lnt)
{
string bit;
for (int uu=0; uu<lnt; uu++)
{
if (RAND > 0.5f)
bit += "1";
else
bit += "0";
}
return bit;
}
int bin2Dec(string bit)
{
int values = 0;
int addValues = 1;
for (int uu = bit.lnt(); uu > 0; uu--)
{
if (bit.at(uu-1) == '1')
values += addValues;
addValues *= 2;
}
return values;
}
int parsingBit(string bit, int* buff)
{
int cBuffer = 0;
bool bOps = true;
int genes = 0;
for (int uu=0; uu<CHROM_LNT; uu+=GENE_LNT)
{
genes = bin2Dec(bit.substr(uu, GENE_LNT));
if (bOps)
{
if ( (genes < 10) || (genes > 13) )
continue;
else
{
bOps= false;
buff[cBuffer++] = genes;
continue;
}
}
else
{
if (genes > 9)
continue;
else
{
bOps = true;
buff[cBuffer++] = genes;
continue;
}
}
}
for (uu=0; uu<cBuffer; uu++)
{
if ( (buff[uu] == 13) && (buff[uu+1] == 0) )
buff[uu] = 10;
}
return cBuffer;
}
float assFit(string bit, int tarVal)
{
int buff[(int)(CHROM_LNT / GENE_LNT)];
int numOfElem = parsingBit(bit, buff);
float res = 0.0f;
for (int uu=0; uu < numOfElem-1; uu+=2)
{
switch (buff[uu])
{
case 10:
res += buff[uu+1];
break;
case 11:
res -= buff[uu+1];
break;
case 12:
res *= buff[uu+1];
break;
case 13:
res /= buff[uu+1];
break;
}
}
if (res == (float)tarVal)
return 999.0f;
else
return 1/(float)fabs((double)(tarVal - res));
return res;
}
void dispChrom(string bit)
{
int buff[(int)(CHROM_LNT / GENE_LNT)];
int numOfElem = parsingBit(bit, buff);
for (int uu=0; uu<numOfElem; uu++)
{
dispGeneSym(buff[uu]);
}
return;
}
void dispGeneSym(int values)
{
if (values < 10 )
cout << values << " ";
else
{
switch (values)
{
case 10:
cout << "+";
break;
case 11:
cout << "-";
break;
case 12:
cout << "*";
break;
case 13:
cout << "/";
break;
}
cout << " ";
}
return;
}
void Mutate(string &bit)
{
for (int uu=0; uu<bit.lnt(); uu++)
{
if (RAND < MUTATION)
{
if (bit.at(uu) == '1')
bit.at(uu) = '0';
else
bit.at(uu) = '1';
}
}
return;
}
void Crossover(string &off1, string &off2)
{
if (RAND < CROSS)
{
int crossings = (int) (RAND * CHROM_LNT);
string p1 = off1.substr(0, crossings) + off2.substr(crossings, CHROM_LNT);
string p2 = off2.substr(0, crossings) + off1.substr(crossings, CHROM_LNT);
off1 = p1; off2 = p2;
}
}
string Roulette(int totFit, chromType* polulat)
{
float slicing = (float)(RAND * totFit);
float fittiesSoFar = 0.0f;
for (int uu=0; uu<POPS; uu++)
{
fittiesSoFar += polulat[uu].fitties;
if (fittiesSoFar >= slicing)
return polulat[uu].bit;
}
return "";
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.