//---------------------------------------------------------------------
//  Algorithmic Conjurings: Natural Algorithms
//
//  BlackBox.cpp
//  version 1.0.1
//-----------------------------------------------------------------------
//
//  COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//  
//  If you modify this file, you may insert additional notices
//  immediately following this sentence.
//  
//  Copyright 1994-2001 Scott Robert Ladd.
//  All rights reserved, except as noted herein.
//  
//  This computer program source file is supplied "AS IS". Scott Robert
//  Ladd (hereinafter referred to as "Author") disclaims all warranties,
//  expressed or implied, including, without limitation, the warranties
//  of merchantability and of fitness for any purpose. The Author
//  assumes no liability for direct, indirect, incidental, special,
//  exemplary, or consequential damages, which may result from the use
//  of this software, even if advised of the possibility of such damage.
//  
//  The Author hereby grants anyone permission to use, copy, modify, and
//  distribute this source code, or portions hereof, for any purpose,
//  without fee, subject to the following restrictions:
//  
//      1. The origin of this source code must not be misrepresented.
//  
//      2. Altered versions must be plainly marked as such and must not
//         be misrepresented as being the original source.
//  
//      3. This Copyright notice may not be removed or altered from any
//         source or altered source distribution.
//  
//  The Author specifically permits (without fee) and encourages the use
//  of this source code for entertainment, education, or decoration. If
//  you use this source code in a product, acknowledgment is not required
//  but would be appreciated.
//  
//  Acknowledgement:
//      This license is based on the wonderful simple license that
//      accompanies libpng.
//
//-----------------------------------------------------------------------
//
//  For more information on this software package, please visit
//  Scott's web site, Coyote Gulch Productions, at:
//
//      http://www.coyotegulch.com
//  
//-----------------------------------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <climits>

#ifdef __GNUC__
#define showbase ""
#endif

using namespace std;

//-------------------------------------------------------------------
// this is the mystery function; it returns the number of bits in
// the argument that match the bits in the 'secret' number
long BlackBox(long x)
{
    // test value -- the speed of light in meters per second
    static const long secret =  299792458L;
    
    long fitness  = 0L;
    long mask = 1L;
    
    // count matching bits
    for (int i = 0; i < 32; ++i)
    {
        if ((x & mask) == (secret & mask))
            ++fitness;
        
        mask <<= 1;
    }
    
    // return fitness between 0 and 32
    return fitness;
}

//-------------------------------------------------------------------
// utility to generate random floating-point value
inline float getRandomFloat()
{
    return (float(rand()) / float(RAND_MAX));
}

//-------------------------------------------------------------------
// a genetic algorithm to optimize the output of BlackBox
void OptimizeBlackBox
    (
    size_t populationSize,
    size_t numGenerations,
    float  crossoverRate,
    float  mutationRate,
    bool   elitismEnabled,
    bool   fitnessScalingEnabled,
    ostream & display
    )
{
    // display header
    display << endl
            << "BlackBox Optimization (C++)" << endl
            << "---------------------------" << endl
            << endl 
            << setprecision(7);

    #ifndef __GNUC__
    display.setf(ios::boolalpha);
    #endif

    // adjust any invalid parameters
    if (populationSize < 10)
        populationSize = 10;

    if (numGenerations < 1)
        numGenerations = 1;

    if (crossoverRate < 0.0F)
        crossoverRate = 0.0F;
    else
        if (crossoverRate > 1.0F)
            crossoverRate = 1.0;

    if (mutationRate < 0.0F)
        mutationRate = 0.0F;
    else
        if (mutationRate > 1.0F)
            mutationRate = 1.0;

    // display parameters for this run
    display << " population size: " << populationSize << endl
            << "# of generations: " << numGenerations << endl
            << "  crossover rate: " << crossoverRate * 100.0F << "%" << endl
            << "   mutation rate: " << mutationRate * 100.0F << "%" << endl
            << " scaling enabled: " << fitnessScalingEnabled   << endl
            << " elitism enabled: " << elitismEnabled << endl << endl;

    // allocate population and fitness buffers
    long * population = new long[populationSize];
    long * children   = new long[populationSize];
    long * fitness    = new long[populationSize];
    
    // various variables
    long  valueMostFit, fitnessHighest, fitnessLowest, mask;
    float totalFitness, fitnessAverage;
    size_t i, generationCounter, selection, father, mother, start;
    
    // create initial population with random values
    for (i = 0; i < populationSize; ++i)
        population[i] = long(rand());
    
    // start with generation zero
    generationCounter = 0;
    
    while (true) // loop breaks in the middle
    {
        // initialize for fitness testing
        fitnessLowest  = LONG_MAX;
        fitnessHighest = -1L;
        totalFitness   = 0.0F;
        
        // fitness testing
        for (i = 0; i < populationSize; ++i)
        {
            // call fitness function and store result
            fitness[i] = BlackBox(population[i]);
            
            // keep track of best fitness
            if (fitness[i] > fitnessHighest)
            {
                fitnessHighest = fitness[i];
                valueMostFit = population[i];
            }
            
            // keep track of least fitness
            if (fitness[i] < fitnessLowest)
                fitnessLowest = fitness[i];
            
            // total fitness
            totalFitness += float(fitness[i]);
        }
        
        // make sure we have at least some fitness values
        if (totalFitness == 0.0F)
        {
            display << "** Population has total fitness of zero -- optimzation terminated." << endl;
            break;
        }
        
        // compute average fitness
        fitnessAverage = totalFitness / float(populationSize);

        // display stats for this generation
        display << setw(4) << generationCounter;
        display.setf(ios::internal);
        display << " best: " << hex << showbase << setfill('0')
                << setw(10) << valueMostFit << setfill(' ');
        display.unsetf(ios::internal);
        display << ", fitness = " << dec << setw(2) << fitnessHighest
                << ", average fitness = " << fitnessAverage
                << endl;
        
        // jump out if we've found the solution
        if (fitnessHighest == 32L)
        {
            display << "** Optimization complete!" << endl;
            break;
        }
        
        // if enabled, scale fitness values
        if (fitnessScalingEnabled)
        {
            // ensures that the least fitness is one
            ++fitnessLowest;
            
            // recalculate total fitness to reflect scaled values
            totalFitness = 0.0F;
            
            for (i = 0; i < populationSize; ++i)
            {
                fitness[i]   -= fitnessLowest;     // reduce by smallest fitness
                fitness[i]   *= fitness[i];        // square result of above
                totalFitness += float(fitness[i]); // add into total fitness
            }
        }
        
        // exit if this is final generation
        if (generationCounter == numGenerations)
        {
            display << "** Done" << endl;
            break;
        }
        
        // if elitist selection, replace first item with best
        if (elitismEnabled)
        {
            children[0] = valueMostFit;
            start = 1;
        }
        else
            start = 0;
        
        // create new population
        for (i = start; i < populationSize; ++i)
        {
            // roulette-select parent
            selection = (size_t)(getRandomFloat() * totalFitness);
            father    = 0;
            
            while (selection > fitness[father])
            {
                selection -= fitness[father];
                ++father;
            }
            
            // crossover reproduction
            if (getRandomFloat() <= crossoverRate)
            {
                // roulette-select second parent
                selection = (size_t)(getRandomFloat() * totalFitness);
                mother = 0;
                
                while (selection > fitness[mother])
                {
                    selection -= fitness[mother];
                    ++mother;
                }
                
                // mask of bits to be copied from first parent
                mask = 0xFFFFFFFFL << (int)(getRandomFloat() * 32.0F);
                
                // new string from two parents
                children[i] = (population[father] & mask) | (population[mother] & (~mask));
            }
            else
            {
                // one parent, no crossover reproduction
                children[i] = population[father];
            }
            
            // mutation
            if (getRandomFloat() < mutationRate)
            {
                // select bit to be changed
                mask = 1L << (long)(getRandomFloat() * 32.0F);
                
                // flip the bit
                if (children[i] & mask)
                    children[i] &= ~mask;
                else
                    children[i] |= mask;
            }
        }
        
        // exchange old population with new one
        long * temp = children;
        children    = population;
        population  = temp;

        // increment generation
        ++generationCounter;
    }
        
    // delete population and fitness arrays
    delete [] population;
    delete [] children;
    delete [] fitness;
}
    
int main(int argc, char* argv[])
{
    // initialize psuedo-random number generator
    srand((unsigned)time(NULL));

    // main function    
    OptimizeBlackBox(100,50,1.0F,0.1F,true,true,cout);

    return 0;
}