/* Overcomplicated way to print Hello, world! using a Genetic Algorithm. https://en.wikipedia.org/wiki/Genetic_algorithm */ #include #include #include #include #include #include #include namespace Dennis { namespace Random { std::mt19937 mt( std::time( nullptr ) ); template T getRandom( T min, T max, typename std::enable_if< std::is_integral::value >::type* = nullptr ) { return std::uniform_int_distribution( min, max )( mt ); } template T getRandom( T min, T max, typename std::enable_if< std::is_floating_point::value >::type* = nullptr ) { return std::uniform_real_distribution( min, max )( mt ); } template std::size_t rouletteWheel( double total, const Container& container, UnaryFunction&& func ) { double target = getRandom( 0.0, total ); std::size_t index = 0; for(; index < container.size(); ++index ) { target -= func( index ); if( target <= 0.0 ) break; } assert( target <= 0.0 ); return index; } template std::size_t rouletteWheel( double total, const Container& container ) { auto func = [&container]( std::size_t index ){ return container[index]; }; return rouletteWheel( total, container, func ); } } class GA { private: struct DNA { std::string dna = "" ; double fitness = 0.0; }; public: GA( const std::string& target ); int run(); private: void initGeneration(); void nextGeneration(); DNA crossOver(); void mutate( DNA& child ); double calcFitness( const std::string& s ) const; DNA getBest( const DNA& currentBest, const DNA& other ) const; bool timeout() const; private: std::string mTarget; std::vector mPopulation; DNA mBest; int mTimer; static constexpr std::size_t MAX_POPULATION = 2000; static constexpr double CROSSOVER_RATE = 0.9; static constexpr double MUTATION_RATE = 0.001; }; GA::GA( const std::string& target ) :mTarget( target ) ,mTimer( clock() ) { assert( !target.empty() ); initGeneration(); } int GA::run() { bool success = true; int generations = 1; while( mBest.dna != mTarget ) { nextGeneration(); ++generations; if( timeout() ) { success = false; break; } } std::cout << ( success ? mBest.dna : "Failed to generate output within time, sololearn is slow..., try again :(" ) << std::endl; return !success; } void GA::initGeneration() { std::generate_n( std::back_inserter( mPopulation ), MAX_POPULATION, [this]() -> DNA { DNA d; std::generate_n( std::back_inserter( d.dna ), mTarget.size(), [](){ return Random::getRandom( 32, 126 ); } ); d.fitness = calcFitness( d.dna ); mBest = getBest( mBest, d ); return d; } ); } void GA::nextGeneration() { DNA nextBest = mBest; std::vector newGeneration; newGeneration.reserve( mPopulation.size() ); for( const auto& p: mPopulation ) { if( Random::getRandom( 0.0, 1.0 ) < CROSSOVER_RATE ) { DNA child = crossOver(); newGeneration.push_back( child ); } else { newGeneration.push_back( p ); } DNA& child = newGeneration.back(); mutate( child ); child.fitness = calcFitness( child.dna ); nextBest = getBest( mBest, child ); } newGeneration.pop_back(); newGeneration.push_back( mBest ); mBest = nextBest; mPopulation = newGeneration; } GA::DNA GA::crossOver() { double totalFitness = std::accumulate( mPopulation.begin(), mPopulation.end(), 0.0, []( double count, const DNA& d ){ return count + d.fitness; } ); auto func = [this]( std::size_t index ){ return mPopulation[index].fitness; }; const DNA& parent1 = mPopulation[ Random::rouletteWheel( totalFitness, mPopulation, func ) ]; const DNA& parent2 = mPopulation[ Random::rouletteWheel( totalFitness, mPopulation, func ) ]; assert( parent1.dna.size() == parent2.dna.size() ); DNA child; child.dna.reserve( parent1.dna.size() ); for( std::size_t i = 0; i < parent1.dna.size(); ++i ) { child.dna.push_back( Random::getRandom( 0, 1 ) == 0 ? parent1.dna[i] : parent2.dna[i] ); } return child; } void GA::mutate( DNA& child ) { for( auto& i : child.dna ) { if( Random::getRandom( 0.0, 1.0 ) < MUTATION_RATE ) { i = Random::getRandom( 32, 126 ); } } } double GA::calcFitness( const std::string& s ) const { double r = 0; for( std::size_t i = 0; i < s.size(); ++i ) if( s[i] == mTarget[i] ) ++r; return std::pow( r / mTarget.size(), 4 ); } GA::DNA GA::getBest( const DNA& currentBest, const DNA& other ) const { return currentBest.fitness > other.fitness ? currentBest : other; } bool GA::timeout() const { return ( clock() - mTimer ) > 3000; } } int main() { Dennis::GA ga( "Hello, world!" ); return ga.run(); }

Hello, world! Genetic Algorithm