Population.h 6.54 KB
Newer Older
adelmann's avatar
adelmann committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#ifndef __POPULATION_H__
#define __POPULATION_H__

#include <map>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <cmath>
#include <sstream>
#include <fstream>

#include "boost/smart_ptr.hpp"

#include "extlib/wfgHypervolume/hypervolume.h"


/**
 *  \class Population
 *
 *  Managing a population of individuals. We maintain two sets: a set of all
 *  (evaluated) individuals in the population and a set of new potential
 *  individuals (the selector decides which individuals join the population),
 *  called 'stagingArea'.
 *  Most operations work on the 'stagingArea', population is kept for
 *  visualization purposes.
 */
template< class Individual_t >
class Population {

public:
    Population() {
        last_identity = 0;
    }

36
    ~Population() {}
adelmann's avatar
adelmann committed
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

    typedef typename Individual_t::genes_t          genes_t;
    typedef boost::shared_ptr<Individual_t>         individual;
    typedef std::pair< unsigned int, individual >   ind_t;

    /// population iterator type
    typedef typename std::map<unsigned int, individual>::iterator indItr_t;

    /**
     *  Adds an individual to the population
     *  @param ind an individual that will be added to the population
     *  @return individual id if successful, -1 otherwise
     */
    unsigned int add_individual(individual ind) {

        unsigned int id = getFreeID();
        stagingArea.insert(ind_t(id, ind));
        ind->id = id;
        //std::cout << "+++ staging    id = " << id << "\xd";
        return id;
    }


    void remove_individual(individual ind) {

        indItr_t it = stagingArea.begin();
        while(it != stagingArea.end()) {
            if(it->second == ind) {
                if(it->first == last_identity-1)
                    last_identity--;
                else
                    freeids.push(it->first);

                //std::cout << "--- removing   id = " << it->first << "\xd";
                stagingArea.erase(it);
                break;
            }
            it++;
        }
    }


    /**
     *  Get an individual of the current population with a specific ID
     *  @param identity an ID of the individual in the population
     *  @return the individual with the specified ID in the population, -1 if
     *  none found
     */
    individual get_individual(int identity) {

        indItr_t it;
        if(identity == -1)
            it = individuals.begin();
        else {
            it = individuals.find(identity);
            if( it == individuals.end() )
                return individual();
        }

        return it->second;
    }


    individual get_staging(int identity) {

        indItr_t it;
        if(identity == -1)
            it = stagingArea.begin();
        else {
            it = stagingArea.find(identity);
            if( it == stagingArea.end() )
                return individual();
        }

        return it->second;
    }


    void commit_individuals(std::set<unsigned int> ids) {

117
        for (unsigned int id : ids) {
adelmann's avatar
adelmann committed
118 119 120 121 122 123 124 125
            //std::cout << "--+ committing id = " << id << "\xd";
            individual ind = get_staging(id);
            individuals.insert(ind_t(id, ind));
            stagingArea.erase(id);
        }
    }

    /**
126 127 128
     *  Remove all non-surviving individuals from the population and put IDs
     *  back in pool of free IDs.
     *  @param survivors to keep for next generation
adelmann's avatar
adelmann committed
129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
     */
    void keepSurvivors(std::set<unsigned int> survivors) {

        indItr_t it = individuals.begin();
        while(it != individuals.end()) {
            if( survivors.count(it->first) == 0 ) {
                if(it->first == last_identity-1)
                    last_identity--;
                else
                    freeids.push(it->first);

                individuals.erase(it++);
            } else
                it++;
        }
    }


    /// check if a gene set is already represented in the population
    //XXX: currently O(n): add a fast look-up table?
    bool isRepresentedInPopulation(genes_t ind_genes) {

151
        for(ind_t ind : individuals) {
adelmann's avatar
adelmann committed
152 153 154 155 156 157 158 159
            if( ind_genes == ind.second->genes )
                return true;
        }

        return false;
    }


160 161 162
    double computeHypervolume(size_t island_id, const std::vector<double>& referencePoint) {
        // protection check
        if (individuals.empty() == true) return -1;
adelmann's avatar
adelmann committed
163 164 165 166 167 168 169 170 171 172 173 174 175 176

        std::ofstream file;
        std::ostringstream filename;
        filename << "hypervol.dat_" << island_id;
        file.open(filename.str().c_str(), std::ios::out);

        file << "#" << std::endl;

        indItr_t it;
        for(it = individuals.begin(); it != individuals.end(); it++) {

            individual temp = it->second;
            for(size_t i=0; i<temp->objectives.size(); i++)
                file << temp->objectives[i] << " ";
177 178
            if (temp->objectives.size() > 0)
                file << std::endl;
adelmann's avatar
adelmann committed
179 180 181 182 183 184 185
        }

        file << "#" << std::endl;

        file.flush();
        file.close();

186
        return Hypervolume::FromFile(filename.str(), referencePoint);
adelmann's avatar
adelmann committed
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
    }


    void commit_individuals() {
        individuals.insert(stagingArea.begin(), stagingArea.end());
        stagingArea.clear();
    }


    /// iterator begin on staging area
    indItr_t stagingBegin() { return stagingArea.begin(); }
    /// iterator end on staging area
    indItr_t stagingEnd()   { return stagingArea.end(); }


    /**
     *  Size of population
     *  @return total number of individuals in population
     */
    unsigned int size() const { return individuals.size(); }

    /// iterator begin on population container
    indItr_t begin() { return individuals.begin(); }
    /// iterator end on population container
    indItr_t end()   { return individuals.end(); }

213 214
    /* /// Remove (and cleanup) all individuals in the population */
    /* void clean_population() { */
adelmann's avatar
adelmann committed
215

216 217 218
    /*     stagingArea.clear(); */
    /*     individuals.clear(); */
    /* } */
adelmann's avatar
adelmann committed
219 220 221 222 223 224 225 226 227

private:

    /// population container holding all individuals
    std::map<unsigned int, individual > individuals;

    /// staging area for individuals probably joining population
    std::map<unsigned int, individual > stagingArea;

228
    /// queue to handle free individual IDs
adelmann's avatar
adelmann committed
229 230 231 232 233 234
    std::queue<unsigned int> freeids;

    /// last used (= next free) ID
    unsigned int last_identity;

    /**
235
     *  Manages free individual IDs
adelmann's avatar
adelmann committed
236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
     *  @return lowest free ID
     */
    unsigned int getFreeID() {

        unsigned int id = 0;
        if(freeids.empty()) {
            id = last_identity;
            last_identity++;
        } else {
            id = freeids.front();
            freeids.pop();
        }

        return id;
    }
};

253
#endif