Population.h

Go to the documentation of this file.

/*
 * GALib v2.0- A simple C++ library for Genetic Algorithms
 * Arthur van Dam <dam@math.uu.nl>
 * $Id: Population.h 441 2007-11-15 16:55:50Z adam $
 */
#ifndef __GAL_POPULATION_H
#define __GAL_POPULATION_H

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include "Util.h"
#include "Chromosome.h"
#include "Problem.h"

#define DOUBLE_MAX 1.7E+308
namespace gal {

    template <class T> class Population {
    private:
        Problem<T>* _problem;                   /* problem with obj. func. and Chromosome constructors */
        std::vector<Chromosome<T>* > _members;  /* population members */
        std::vector<double> _objvalues;         /* Cached objective values of curr. generation */       
        std::vector<double> _fitnesses;         /* Cached fitness values of curr. generation */
        double _totalFitness;                   /* Cached total fitness of curr. generation */
        std::vector<int> _currentElite;         /* Cached indices of members that are elite in curr. generation */
        int _nrMem;                             /* Nr of members currently in population (during build-up of _members) */
        int _nrElite;                           /* Nr of elite members allowed */
        double _probMutate;                     /* Probability of mutation, for each bit */
        double _probCrossover;                  /* Probability of crossover, for two selected parents */
        int _objmaxindex;                       /* Index of maximum of the objective values */
        int _objminindex;                       /* Index of minimum of the objective values */
        double _objavg;                         /* Average of the objective values */
        double _prevmax;                        /* Maximum in previous step */
        double _overallmax;                     /* Maximum in all previous generations */
        double _nrequalmax;                     /* Number of equal maxima */
    /*
     * Constructors
     */
    public:
        Population(Problem<T>* problem) : _problem(problem), _members(),
                _nrElite(0), _probMutate(0.0), _probCrossover(0.0) {}

        Population(Problem<T>* problem,
                int size, int chromoLength) : _problem(problem), _members(),
                _nrElite(0), _probMutate(0.0), _probCrossover(0.0)
        {
            initialise(size, chromoLength);
        }

        ~Population()
        {
            typename std::vector<Chromosome<T>* >::iterator it;

            for (it = _members.begin(); it != _members.end(); ++it) {
                _problem->deleteChromosome(*it);
            }
        }

    public:
        void addMember(Chromosome<T>* g)
        {
            _members[_nrMem] = g;
            _objvalues[_nrMem] = 0.0;
            _fitnesses[_nrMem] = 0.0;
            _nrMem++;
        }

        int const size()
        {
            return _nrMem;
            // Should always be equal to _members.size(),
            // since only during initialisation, _members is being filled.
        }

        void initialise(int size, int chromoLength)
        {
            Chromosome<T>* tmpChr;

            _members.clear();
            _members.resize(size);
            _objvalues.resize(size);
            _fitnesses.resize(size);
            _nrMem = 0;
            for (int i = 0; i < size; ++i) {
                tmpChr = _problem->constructChromosome(chromoLength);
                addMember(tmpChr);
            }
            _prevmax=-1E+100;
            _overallmax=-1E+100;
            _nrequalmax=0;
            _objmaxindex=0;
            _objvalues[_objmaxindex] = _overallmax;
            evaluateFitness();
            
        }

        void setEliteSize(int nrElite)
        {
            _nrElite = nrElite > 0 ? nrElite : 0;
        }

        void setProbabilities(double probMutate, double probCrossover)
        {
            _probMutate = probMutate;
            _probCrossover = probCrossover;
        }

    public:
        void evaluateFitness()
        {
            /* Scale objective values between nmin and nmax
               before normalising */
            double a, b;
            a = 1.0;
            b = 10.0;


            /*** For all member chromosomes, determine objective value,
                 scale them between a and b.
                 
                 Later, maintain some stats for use in PRINTBEST, etc. printmodes.
            ***/
            /* Directly re-mark the elite members with the updated fitness values */
            markElite();
        }

        void markElite()
        {
            int i, imax;
            double maxfit;
            std::map<int, double> fitnessbackup;
            std::map<int, double>::iterator it;

            /*** After the fitness values have been updated, the old elite
                 has to be discarded and new elite members have to be selected.
                 The nr of elite members is available in the member
                 variable _nrElite, and the indices of elite members can be
                 stored in _currentElite.
            ***/

        }

    public:
        void mutate()
        {
            typename std::vector<Chromosome<T>* >::iterator it;

            /***
            Implement mutation of all member chromosomes yourself.
            ***/
        }

        int selectByRoulette()
        {

            /*** Select a (not yet selected) chromosome in the population
                 using the roulette wheel approach.
                 Hint: selection is based on fitness, but prevent that an
                 already selected chromosome is selected again.
             ***/
            return _members.front(); // dummy
        }

        void selectAndReproduce()
        {
            typename std::vector<Chromosome<T>* >::iterator it;
            int i, isel, nrParents, countElite, countNext;
            double tresh, sumFitness;
            std::vector<Chromosome<T>* > nextgen; // Create the complete new generation in here
            Chromosome<T>* sel;                   // The selected member by roulette wheel
            Chromosome<T>* child1;                // created children by crossover
            Chromosome<T>* child2;
            Chromosome<T>** parents = new Chromosome<T>*[2]; // small array with pointers to the two parents.
            std::vector<int>::iterator eliteAt, tmpAt;        // position of selected elite member in _currentElite array.







            nextgen.resize(size());
            countNext = 0;
            countElite = 0;
            // Start selection, and crossover with selected parents.
            while (countNext < size()) {
                nrParents = 0;
                // Select members until 2 members are allowed to be parents.
                // First select all elite members (if any) as first parent in each couple
                while (nrParents < 2 && countNext < size()) {

                    /*** Use roulette wheel selection to select a member for
                         the next generation and add it to the new population ***/

                    /*** For the just selected member, determine if it's
                         allowed to be a parent ***/
                }

                // If next generation is not yet full, produce two children by crossover
                if (nrParents == 2 && countNext < size()-1) {

                    /*** two parents are known, produce two children
                         and add them to next generation. ***/
                    /*** HINT: Initialise children as literal copies of their parents,
                         (see Propblem::copyChromosome) then determine the crossover
                         points, and finally use Chromosome::crossover
                         (implement that one yourself). ***/
                         
                } else {
#ifdef __GAL_DEBUG
                    std::cout << "Next generation is full, discard children." << std::endl;
#endif /* __GAL_DEBUG */
                }
            }
            delete [] parents;


            /*** Don't forget to free up memory (with delete) of the chromosomes
                 that did not make it into the next generation. ***/

            // The new generation is now ready:
            _members = nextgen;
        }

        void nextGeneration()
        {

            /*** selectAndReproduce(); ***/




            mutate();
            
            evaluateFitness();
        }

    public:
    
    #define PRINTINTERP 1
    #define PRINTBITSTRING 2
    #define PRINTVALUE 4
    #define PRINTOBJECTIVE 8
    #define PRINTFITNESS 16
    
    #define PRINTALL 1
    #define PRINTBEST 2
    #define PRINTWORST 4
    #define PRINTAVG 8
    #define ONLYIFBETTER 16 

        void const print(int generationNr, int printbits, int printmode, std::ostream& outstr)
        {
            typename std::vector<Chromosome<T>* >::iterator it;
            int i = 0;
            int index;

            if (printmode & ONLYIFBETTER) {
                if(_overallmax >= _objvalues[_objmaxindex]) {
                    return;
                }
            }

            outstr.precision(12);
            if(printmode&PRINTALL) {
                for (it = _members.begin(); it != _members.end(); ++it) 
                {
                    if(generationNr>=0)
                        outstr << generationNr+1 << "\t";
                    if(printbits & PRINTINTERP)
                        outstr << (*it)->getInterpretedBitstringText() << "\t";
                    if(printbits & PRINTBITSTRING)
                    {   
                        outstr <<  (*it)->getBitstringText() << "\t";
                        /*if ((*it)->isElite())
                            outstr << "*";*/
                    }
                    if(printbits & PRINTVALUE)  
                        outstr <<(*it)->getValueText() << "\t";
                    if (printbits & PRINTOBJECTIVE) 
                        outstr << _objvalues[i] << "\t";
                    if (printbits & PRINTFITNESS) 
                        outstr << "Fit: " << _fitnesses[i] << "\t";
                    outstr << std::endl;
                    i++;
                }
            }
            else if(printmode&PRINTAVG)
            {
                if(generationNr>=0)
                    outstr << generationNr+1 << "\t";
                if(printbits & PRINTOBJECTIVE)
                    outstr << _objavg << std::endl;
                if(printbits & ( PRINTINTERP | PRINTBITSTRING | PRINTVALUE | PRINTFITNESS))
                    outstr << "Options make no sense voor print-average" << std::endl;

            }
            else 
            {
                if(printmode & PRINTWORST)
                {
                        outstr << "TODO ";
                        index=_objmaxindex; /* Should become objminindex later */
                }
                else if(printmode & PRINTBEST)  
                        index=_objmaxindex;
    
                it = _members.begin();
                it += index;
                
                if(generationNr>=0)
                    outstr << generationNr+1 << "\t";
                if (printbits & PRINTOBJECTIVE) 
                    outstr << _objvalues[index] << "\t";
                if(printbits & PRINTBITSTRING)
                    outstr <<  (*it)->getBitstringText() << "\t";
                outstr << std::endl;
                    
            }   
        }
        
        int testConvergence(int nrequal)
        {
            double objmax = _objvalues[_objmaxindex];
            
            if(objmax==_prevmax)
                _nrequalmax++;
            else
                _nrequalmax=0;

            if(_nrequalmax==nrequal)
                return 1;
            else
                return 0;
                        
        }

        void writePopulation(std::ostream& outstr)
        {
            typename std::vector<Chromosome<T>* >::iterator it;
            int i;

            outstr << "# Bitstring\tElite?\tValue\tObj.value" << std::endl;

            i = 0;
            for (it = _members.begin(); it != _members.end(); ++it) 
            {
                outstr <<  (*it)->getBitstringText();
                outstr << "\t"; // Always delimit potential elite-'*'
                if ((*it)->isElite())
                    outstr << "*";
                outstr << "\t" << (*it)->getValueText();
                outstr << "\t" << _objvalues[i];
                outstr << std::endl;
                i++;
            }
        }





        void readPopulation(std::istream& instr)
        {
            int chromoLength;
            Chromosome<T>* tmpChr;

            if (size() == 0 || (chromoLength = _members[0]->length()) == 0) {
                std::cerr << "** Unexpected population size or bitlength! Is Population unitialised?" << std::endl;
                return;
            }

            char chromoString[5*chromoLength];
            char c;

            int err = 0; // error during reading?
            int i;

            // Ignore first header line
            instr.ignore (1000000, '\n');
            if (instr.peek() == '\r') instr.ignore (1);

            i = 0;
            while (i < size() && !instr.eof()) {
                instr.getline(chromoString, 1000000, '\t');
                std::cout << "just read: \"" << chromoString << "\"" << std::endl;
                tmpChr = _problem->copyChromosome(_members[i]); // Copying is just to get correct bitstring length.
                tmpChr->setBits(chromoString);

                // set elite status to true or false.
                c = instr.peek();
                if (c == '*') {
                    tmpChr->setElite(true);
                } else if (c == '\t') {
                    tmpChr->setElite(false);
                } else {
                    std::cerr << "** Unexpected character '" << c << "' (" << (int)c << ") at line " << (i+2) << ", pos. " << (chromoLength+1) << "." << std::endl;
                    std::cerr << "   Are bitstrings in file longer than current bitstrings?" << std::endl;
                    err = 1;
                    break;
                }

                delete _members[i];   // Clean up memory of current chromosome pointer.
                _members[i] = tmpChr; // Place new chromosome in population

                instr.ignore (1000000, '\n');
                if (instr.peek() == '\r') instr.ignore (1);

                i++;
            }
            
            if (i != size()) {
                std::cerr << "** File was smaller than population." << std::endl;
                err = 1;
            }

            if (!instr.eof()) {
                std::cerr << "** File was larger than population." << std::endl;
            }
            
            if (err) {
                std::cerr << "** Exiting." << std::endl;
                exit(1);



            }
            evaluateFitness();
        }

    };
}
#endif /* __GAL_POPULATION_H */

---