#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <tuple>
#ifndef EXIT_SUCCESS
#define EXIT_SUCCESS 0
#endif
namespace intelligence {
const unsigned CHARCODE_BEGIN = 97 ;
const unsigned CHARCODE_END = 122 ;
class Chromosome {
std::vector<char> _genes ;
public :
Chromosome(): _genes{} {}
Chromosome( unsigned short geneSize ) {
for( int i = 0 ; i < geneSize ; i++ )
_genes.push_back( CHARCODE_BEGIN + rand() % (CHARCODE_END-CHARCODE_BEGIN+1) ) ;
}
float calculateFitness( const std::string& target ) {
float fitnessScore = 0.0f ;
for( int i = 0 ; i < _genes.size() ; i++ ) {
if( _genes[i] == target[i] )
fitnessScore++ ;
}
return pow( fitnessScore / target.length(), 2 ) ;
//return fitnessScore / target.length() ;
}
Chromosome crossover( const Chromosome& other ) {
Chromosome child ;
std::vector<char> newGenes ;
int midPoint = rand() % other.size() ;
for( int i = 0 ; i < this->size() ; i++ ) {
if( i > midPoint )
newGenes.push_back( other.getGene( i ) ) ;
else
newGenes.push_back( this->_genes[i] ) ;
}
child.setGenes( newGenes ) ;
return child ;
}
void mutate( float mutationRate ) {
std::replace_if( _genes.begin(), _genes.end(), [mutationRate]( char unused ) {
return ( ((rand() % 100) * 0.01f) < mutationRate ) ;
}, CHARCODE_BEGIN + rand() % (CHARCODE_END-CHARCODE_BEGIN+1) ) ;
}
void setGenes( const std::vector<char> genes ) {
_genes = genes ;
}
std::vector<char> getGenes() const{ return _genes ; }
char getGene( int idx ) const{ return _genes[idx] ; }
unsigned int size() const{ return _genes.size() ; }
} ;
class Population {
std::vector<Chromosome> _population ;
unsigned short _generation ;
unsigned short _mutationRate ;
std::string _target ;
public :
Population( unsigned short popSize, const std::string target, unsigned short mutationRate ): _target(target),
_mutationRate(mutationRate), _generation(0) {
for( int i = 0 ; i < popSize ; i++ )
_population.push_back( Chromosome( target.length() ) ) ;
}
void acceptReject() {
std::vector<Chromosome> newPopulation ;
unsigned short maxFitness = getHighestFitnessScore() ;
for( unsigned int i = 0 ; newPopulation.size() < _population.size() ; i++ ) {
Chromosome parentA = _population[ rand() % _population.size() ] ;
Chromosome parentB = _population[ rand() % _population.size() ] ;
float randomScore = 0.01f + (rand() % maxFitness) * 0.01f ;
float parentAScore = parentA.calculateFitness( _target ) ;
float parentBScore = parentB.calculateFitness( _target ) ;
if( (parentAScore > randomScore) && (parentBScore > randomScore) ) {
Chromosome child = parentA.crossover( parentB ) ;
child.mutate( _mutationRate ) ;
newPopulation.push_back( child ) ;
}
}
_population = newPopulation ;
_generation++ ;
}
void run() {
float bestScore = 0.0f ;
std::cout << "Target: " << _target << '\n' ;
while( bestScore < 1.0f ) {
std::tuple<std::string, float> info ;
info = getHighestFitness() ;
bestScore = std::get<1>(info) ;
std::cout << "Generation: " << _generation << "; Best Guess: " << std::get<0>(info) << "; Best Score: " << bestScore*100 << "%\n" ;
acceptReject() ;
}
}
unsigned getHighestFitnessScore() {
float highest = 0.0f ;
for( auto itr : _population ) {
float fitnessScore = itr.calculateFitness( _target ) ;
if( fitnessScore > highest )
highest = fitnessScore ;
}
return unsigned(highest * 100) ;
}
std::tuple<std::string, float> getHighestFitness() {
std::vector<char> highestString ;
float highestScore = 0.0f ;
for( auto itr : _population ) {
float fitnessScore = itr.calculateFitness( _target ) ;
if( fitnessScore > highestScore ) {
highestScore = fitnessScore ;
highestString = itr.getGenes() ;
}
}
std::string s( highestString.begin(), highestString.end() ) ;
return std::make_tuple( s, highestScore ) ;
}
} ;
}
void printGenes( const std::vector<char>& genes ) {
for( auto itr: genes )
std::cout << itr ;
std::cout << '\n' ;
}
int main() {
srand( time(NULL) ) ;
std::string target ;
std::cout << "Enter Target Phrase: " ;
std::getline( std::cin, target ) ;
intelligence::Population p( 1500, target, 0.05f ) ;
p.run() ;
return EXIT_SUCCESS ;
}