Non-Uniform CA Designer (C++, GAlib, Boost)

/*
 * Copyright (C) 2009 Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
 *
 * This file is part of nucad (Non-Uniform CA Designer).
 *
 * nucad is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * nucad is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with nucad.  If not, see <http://www.gnu.org/licenses/>.
 */
 
/**
 * @file CaDesigner.cpp
 * Implementation of GaCaRules, GaCaRulesSet and class CaDesigner with its base
 * classes and observers.
 */
 
#include "config.h"
#include "CaDesigner.h"
#include "Color.h"
 
#ifndef GA_PARTIAL_RESULTS
#   define GA_PARTIAL_RESULTS 0
#endif
 
#ifndef BUILDING_DOX
#   if GA_PARTIAL_RESULTS
#      include <fcntl.h>
#      include <unistd.h>
#   endif
 
#   include <iomanip>
#   include <list>
#   include <math.h>
#   include <set>
 
#   include <boost/lexical_cast.hpp>
 
#   include <ga/GA1DBinStrGenome.h>
#   include <ga/GASimpleGA.h>
#   include <ga/GAStatistics.h>
#endif // BUILDING_DOX
 
#if 0
#include <ga/GASStateGA.h>
#include <ga/GAIncGA.h>
#include <ga/GADemeGA.h>
#endif
 
/**
 * Change this typedef to use another GA algorithm. Tested with GASimpleGA,
 * GASteadyStateGA, GAIncrementalGA and GADemeGA.
 */
typedef GASimpleGA TGeneticAlgorithm;
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// GaCaRules implementation
#ifndef BUILDING_DOX
struct GaCaRules::Private {
    size_t size;
    GABinaryString bs;
 
    Private(unsigned size_):
        size(size_),
        bs(size_*size_*RULE_WIDTH)
    {
    }
};
#endif
 
GaCaRules::GaCaRules():
    d(new Private(1))
{
    // dummy constructor used by GaCaRulesCmpDecorator
}
 
GaCaRules::GaCaRules(const std::string &str):
    d(new Private(1))
{
    // guess CA size
    size_t len = str.size();
    size_t caSize = static_cast<size_t>(sqrt(
                static_cast<float> (len / RULE_WIDTH)));
 
    if (caSize*caSize*RULE_WIDTH != len)
        // unexpected size of input
        throw std::runtime_error("GaCaRules::GaCaRules: input error (not handled)");
 
    // deserialize
    d->size = caSize;
    d->bs.resize(len);
    for (unsigned i = 0; i < len; ++i)
        d->bs.bit(i, boost::lexical_cast<bool>(str[i]));
}
 
GaCaRules::GaCaRules(size_t size, const GABinaryString &bs):
    d(new Private(size))
{
    // deep copy
    d->bs.copy(bs);
}
 
GaCaRules::GaCaRules(const GaCaRules &other):
    d(new Private(other.d->size))
{
    // deep copy
    d->bs.copy(other.d->bs);
}
 
GaCaRules::~GaCaRules() {
    delete d;
}
 
GaCaRules* GaCaRules::clone() const {
    return new GaCaRules(*this);
}
 
void GaCaRules::getRuleAtPos(Pos pos, TRule5N &rule) const {
    // FIXME: should it respect the CA_CYCLIC_NEIGHBORHOOD compile-time option?
    int offset = pos.row * d->size + pos. col;
    offset *= RULE_WIDTH;
    for (int i = 0; i < RULE_WIDTH; ++i) {
        assert(i + offset < d->bs.size());
        rule[i] = d->bs.bit(i + offset);
    }
}
 
size_t GaCaRules::size() const {
    return d->bs.size();
}
 
bool GaCaRules::operator[] (unsigned index) const {
    return d->bs.bit(index);
}
 
std::ostream& operator<< (std::ostream &str, const GaCaRules &data) {
    for (unsigned i = 0; i < data.size(); ++i)
        str << data[i];
    return str;
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// CaDesigner implementation
#ifndef BUILDING_DOX
struct CaDesigner::Private {
    CaEvaluator               *evaluator;
    CaDesigner                *solver;                  ///< pointer to self
    float                     maxFitness;
    GA1DBinaryStringGenome    *genome;
    TGeneticAlgorithm         *ga;
    GaCaRulesSet              *resultSet;
 
    static float fitness(GAGenome &);
};
#endif
 
// protected
CaDesigner::CaDesigner (CaEvaluator *evaluator):
    d(new Private)
{
    d->evaluator = evaluator;
    d->solver = this;
    d->maxFitness = 0.0;
 
    const size_t caSize = evaluator->caSize();
    const size_t genomeSize = caSize * caSize * RULE_WIDTH;
    d->genome = new GA1DBinaryStringGenome(genomeSize, Private::fitness, d);
 
    d->ga = new TGeneticAlgorithm(*(d->genome));
    d->ga->populationSize(GA_POP_SIZE);
    d->ga->nGenerations(GA_INITAL_NGEN);
 
    d->resultSet = new GaCaRulesSet;
}
 
CaDesigner::~CaDesigner() {
    delete d->resultSet;
    delete d->ga;
    delete d->genome;
    delete d;
}
 
// it is not safe to call virtual methods in constructor
CaDesigner* CaDesigner::create (CaEvaluator *evaluator) {
    CaDesigner *obj = new CaDesigner(evaluator);
    obj->initialize();
    return obj;
}
 
const GAStatistics& CaDesigner::getStatistics() const {
    return d->ga->statistics();
}
 
int CaDesigner::getSolutionsCount() {
    return d->resultSet->size();
}
 
int CaDesigner::stopAtGeneration() const {
    return d->ga->nGenerations();
}
 
float CaDesigner::minFitness() {
    return d->ga->statistics().offlineMin();
}
 
float CaDesigner::avgFitness() {
    return d->ga->statistics().offlineMax();
}
 
float CaDesigner::maxFitness() {
    return d->maxFitness;
}
 
// protected
void CaDesigner::initialize() {
    GARandomSeed();
    d->maxFitness = 0.0;
    d->ga->initialize();
    d->ga->nGenerations(GA_INITAL_NGEN);
}
 
// protected
void CaDesigner::doStep() {
    GAGeneticAlgorithm &ga= *(d->ga);
    ga.step();
    if (ga.done()) {
        this->stop();
        GAStatistics stats= ga.statistics();
        const int generation = stats.generation();
        std::cerr << Color(C_YELLOW) << "--- Stopped by GAlib in "
            << generation << ". generation"
            << Color(C_NO_COLOR) << std::endl;
    }
}
 
float CaDesigner::Private::fitness(GAGenome &genome) {
    // static to non-static binding
    Private *d = reinterpret_cast<Private *>(genome.userData());
    CaEvaluator *evaluator = dynamic_cast<CaEvaluator *>(d->evaluator);
    CaDesigner *solver = dynamic_cast<CaDesigner *>(d->solver);
    const GABinaryString &bs= dynamic_cast<GABinaryString &>(genome);
    GaCaRulesSet *resultSet= dynamic_cast<GaCaRulesSet *>(d->resultSet);
 
    // compute fitness
    GaCaRules data(evaluator->caSize(), bs);
    float fitness = evaluator->eval(&data);
    if (d->maxFitness < fitness) {
        // compute nGenerations bonus
        float conFit = 1.0;
        for (unsigned i = 0; i < GA_PER_FIT_NGEN_POWER; ++i)
            conFit *= fitness;
        int total = static_cast<int>(conFit * GA_PER_FIT_NGEN);
        if (total < GA_INITAL_NGEN)
            total = GA_INITAL_NGEN;
        total += d->ga->statistics().generation();
        if (d->ga->nGenerations() < total)
            d->ga->nGenerations(total);
 
        // update maxFitness and notify observers
        d->maxFitness = fitness;
        solver->notify();
 
#if GA_PARTIAL_RESULTS
        // FIXME: use observer for this
        // FIXME: read fd as cmd-line argument
        const int fd = 3;
        if (-1 != fcntl(fd, F_GETFD)) {
            std::ostringstream str;
            str << data << std::endl;
            const std::string &text = str.str();
            // FIXME: repeat write(2) on EINTR
            write(fd, text.c_str(), text.size());
        }
#endif
    }
 
    if (1.0 <= fitness) {
        size_t last = resultSet->size();
        resultSet->add(data.clone());
        if (last != resultSet->size()) {
            // notify observers
            solver->notify();
 
            // FIXME: use observer for this
            std::cout << data << std::endl;
        }
    };
 
    return fitness;
}
 
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// AbstractSubject implementation
#ifndef BUILDING_DOX
struct AbstractSubject::Private {
    typedef std::list<IObserver *> TContainer;
    TContainer container;
};
#endif
 
AbstractSubject::AbstractSubject():
    d(new Private)
{
}
 
AbstractSubject::~AbstractSubject() {
    // ATTENTION: Observers are not deleted on object destruction
    delete d;
}
 
void AbstractSubject::addObserver(IObserver *observer) {
    d->container.push_back(observer);
}
 
void AbstractSubject::notify() {
    Private::TContainer::iterator iter;
    for(iter=d->container.begin(); iter!=d->container.end(); iter++) {
        IObserver *observer = *iter;
        observer->notify();
    }
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// AbstractProcess implementation
#ifndef BUILDING_DOX
struct AbstractProcess::Private {
    bool running;
    int steps;
};
#endif
 
AbstractProcess::AbstractProcess():
    d(new Private)
{
    d->running = false;
    d->steps = 0;
}
 
AbstractProcess::~AbstractProcess() {
    delete d;
}
 
void AbstractProcess::start() {
    for(d->running=true; d->running; d->steps++) {
        this->doStep();
        this->notify();
    }
}
 
void AbstractProcess::stop() {
    d->running = false;
}
 
void AbstractProcess::reset() {
    d->running = false;
    d->steps = 0;
    this->initialize();
}
 
int AbstractProcess::getStepsCount() {
    return d->steps;
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// AbstractProcessWatched implementation
#ifndef BUILDING_DOX
struct AbstractProcessWatched::Private {
    static const long RATIO = CLOCKS_PER_SEC/1000L;
    clock_t start;
    long total;
    bool running;
    long currentElapsed() {
        clock_t diff = clock() - start;
        return diff/RATIO;
    }
};
#endif
 
AbstractProcessWatched::AbstractProcessWatched():
    d(new Private)
{
    d->total = 0;
    d->running = false;
}
 
AbstractProcessWatched::~AbstractProcessWatched() {
    delete d;
}
 
void AbstractProcessWatched::start() {
    d->start = clock();
    d->running = true;
    // Delegate to base
    AbstractProcess::start();
}
 
void AbstractProcessWatched::stop() {
    if (d->running) {
        d->running = false;
        d->total += d->currentElapsed();
    }
    // Delegate to base
    AbstractProcess::stop();
}
 
void AbstractProcessWatched::reset() {
    d->running = false;
    d->total = 0;
    // Delegate to base
    AbstractProcess::reset();
}
 
long AbstractProcessWatched::getTimeElapsed() {
    long total = d->total;
    if (d->running)
        total+= d->currentElapsed();
    return total;
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// GaCaRulesSet implementation
#ifndef BUILDING_DOX
struct GaCaRulesSet::Private {
    class GaCaRulesCmpDecorator: public GaCaRules {
        public:
            GaCaRulesCmpDecorator(GaCaRules *item):
                item_(item)
            {
            }
            void dispose() {
                delete item_;
            }
            virtual size_t size() const {
                return item_->size();
            }
            virtual bool operator[] (unsigned index) const {
                return item_->operator[] (index);
            }
            virtual GaCaRules* clone() const {
                return item_->clone();
            }
            bool operator< (const GaCaRulesCmpDecorator &other) const {
                for(unsigned i=0; i<size(); i++) {
                    if (!this->operator[](i) && other[i])
                        return true;
                    else if (this->operator[](i) && !other[i])
                        return false;
                }
                return false;
            }
        private:
            GaCaRules *item_;
    };
    typedef std::set<GaCaRulesCmpDecorator> TSet;
    TSet set;
 
    void add(GaCaRules *item) {
        GaCaRulesCmpDecorator comparableItem(item);
        if (set.end()==set.find(comparableItem))
            set.insert(comparableItem);
        else
            comparableItem.dispose();
    }
};
#endif // BUILDING_DOX
 
GaCaRulesSet::GaCaRulesSet():
    d(new Private)
{
}
 
GaCaRulesSet::~GaCaRulesSet() {
    this->clear();
    delete d;
}
 
size_t GaCaRulesSet::size() const {
    return d->set.size();
}
 
void GaCaRulesSet::add(GaCaRules *item) {
    d->add(item);
}
 
void GaCaRulesSet::clear() {
    Private::TSet::iterator iter;
    for(iter=d->set.begin(); iter!=d->set.end(); iter++) {
        Private::GaCaRulesCmpDecorator &i= 
            const_cast<Private::GaCaRulesCmpDecorator &>(*iter);
        i.dispose();
    }
    d->set.clear();
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// SolutionsCountStop implementation
#ifndef BUILDING_DOX
struct SolutionsCountStop::Private {
    CaDesigner *solver;
    int               minCountOfSolutions;
};
#endif
 
SolutionsCountStop::SolutionsCountStop(CaDesigner *solver, int minCountOfSolutions):
    d(new Private)
{
    d->solver = solver;
    d->minCountOfSolutions = minCountOfSolutions;
}
 
SolutionsCountStop::~SolutionsCountStop() {
    delete d;
}
 
void SolutionsCountStop::notify() {
    const int nSolutions= d->solver->getSolutionsCount();
    if (nSolutions >= d->minCountOfSolutions)
        d->solver->stop();
}
 
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// TimedStop implementation
#ifndef BUILDING_DOX
struct TimedStop::Private {
    AbstractProcessWatched *process;
    long msec;
};
#endif
 
TimedStop::TimedStop(AbstractProcessWatched *process, long msec):
    d(new Private)
{
    d->process = process;
    d->msec = msec;
}
 
TimedStop::~TimedStop() {
    delete d;
}
 
void TimedStop::notify() {
    long elapsed = d->process->getTimeElapsed();
    if (elapsed > d->msec) {
        std::cerr << Color(C_YELLOW) << "--- Run timed out"
            << Color(C_NO_COLOR) << std::endl;
        d->process->stop();
    }
}
 
namespace {
    void writeStats(CaDesigner *solver, std::ostream &str) {
        GAStatistics stats = solver->getStatistics();
        const int generation = stats.generation();
        const int stopAtGeneration = solver->stopAtGeneration();
        const float timeElapsed = solver->getTimeElapsed()/1000.0;
        const float timeRemaining = timeElapsed / generation
            * (stopAtGeneration - generation);
 
#if (1 < GA_POP_SIZE)
        str << " (avg:" << FixedFloat(3,1) << solver->avgFitness() * 100.0
            << ", min:" << FixedFloat(3,1) << solver->minFitness() * 100.0
            << ")";
#endif
        str << ", generation " << Color(C_LIGHT_GREEN)
            << std::setw(8) << generation << Color(C_NO_COLOR)
            << " of " << std::setw(8) << stopAtGeneration
            << ", time elapsed: " << Color(C_YELLOW)
            << FixedFloat(6,2) << timeElapsed << " s" << Color(C_NO_COLOR)
            << ", ttl = " << FixedFloat(6,2) << timeRemaining << " s";
    }
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// FitnessWatch implementation
#ifndef BUILDING_DOX
struct FitnessWatch::Private {
    CaDesigner          *solver;
    std::ostream        &stream;
    float               maxFitness;
 
    Private(std::ostream &streamTo): stream(streamTo) { }
};
#endif
 
FitnessWatch::FitnessWatch(CaDesigner *solver, std::ostream &streamTo):
    d(new Private(streamTo))
{
    d->solver = solver;
    d->maxFitness = 0.0;
}
 
FitnessWatch::~FitnessWatch() {
    delete d;
}
 
void FitnessWatch::notify() {
    CaDesigner *solver= d->solver;
    float maxFitness = solver->maxFitness();
    if (maxFitness <= d->maxFitness)
        // Fitness not changed
        return;
 
    GAStatistics stats = solver->getStatistics();
    if (0 == stats.generation())
        return;
 
    // Save maxFitness for next call
    d->maxFitness = maxFitness;
 
    d->stream << "---    satisfaction:" << Color(C_LIGHT_BLUE)
        << FixedFloat(3,1) << maxFitness*100.0 << "%"
        << Color(C_NO_COLOR);
    writeStats(solver, d->stream);
    d->stream << std::endl;
}
 
void FitnessWatch::reset() {
    d->maxFitness = 0.0;
}
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// ResultsWatch implementation
#ifndef BUILDING_DOX
struct ResultsWatch::Private {
    CaDesigner   *solver;
    std::ostream        &stream;
    int                 nResults;
 
    Private(std::ostream &streamTo): stream(streamTo) { }
};
#endif
 
ResultsWatch::ResultsWatch(CaDesigner *solver, std::ostream &streamTo):
    d(new Private(streamTo))
{
    d->solver = solver;
    d->nResults = 0;
}
 
ResultsWatch::~ResultsWatch() {
    delete d;
}
 
void ResultsWatch::notify() {
    CaDesigner *solver= d->solver;
    const int nResults= solver->getSolutionsCount();
    if (nResults <= d->nResults)
        return;
    d->nResults = nResults;
 
    GAStatistics stats = solver->getStatistics();
    if (0 == stats.generation())
        return;
 
    d->stream << Color(C_LIGHT_BLUE) << "--- " << std::setw(6) << nResults
        << ". solution found" << Color(C_NO_COLOR);
    writeStats(solver, d->stream);
    d->stream << std::endl;
}
 
#ifndef BUILDING_DOX
struct ProgressWatch::Private {
    AbstractProcess *process;
    int             stepsTotal;
    int             last;
    std::ostream    &stream;
 
    Private(std::ostream &streamTo): stream(streamTo) { }
};
#endif
 
ProgressWatch::ProgressWatch(AbstractProcess *process, int stepsTotal, std::ostream &streamTo):
    d(new Private(streamTo))
{
    d->process = process;
    d->stepsTotal = stepsTotal;
    d->last = 0;
}
 
ProgressWatch::~ProgressWatch() {
    delete d;
}
 
void ProgressWatch::notify() {
 
    // Check percentage value
    const int currentStep= d->process->getStepsCount();
    const int percents=
        currentStep*100 /
        d->stepsTotal;
    if (percents == d->last)
        return;
    d->last = percents;
 
    // Write out message
    d->stream
        << Color(C_GREEN) << "--- Progress:"
        << std::setw(3) << percents << "%"
        << Color() << std::endl;
}