Population.h 6.69 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 36 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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
#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 "boost/foreach.hpp"
#define foreach BOOST_FOREACH

#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;
        hypervolume_  = 0.0;
    }

    ~Population() {
        clean_population();
    }

    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) {

        foreach(unsigned int id, ids) {
            //std::cout << "--+ committing id = " << id << "\xd";
            individual ind = get_staging(id);
            individuals.insert(ind_t(id, ind));
            stagingArea.erase(id);
        }
    }

    /**
     *  Remove all non-surviving individuals from the population and put ID's
     *  back in pool of free ID's.
     *  @param surviors to keep for next generation
     */
    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) {

        foreach(ind_t ind, individuals) {
            if( ind_genes == ind.second->genes )
                return true;
        }

        return false;
    }


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

        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] << " ";
182 183
            if (temp->objectives.size() > 0)
                file << std::endl;
adelmann's avatar
adelmann committed
184 185 186 187 188 189 190
        }

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

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

191
        hypervolume_ = Hypervolume::FromFile(filename.str(), referencePoint);
adelmann's avatar
adelmann committed
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
        return hypervolume_;
    }


    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(); }

    /// Remove (and cleanup) all individuals in the population
    void clean_population() {

        stagingArea.clear();
        individuals.clear();
    }

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;

    /// queue to handle free individual ID's
    std::queue<unsigned int> freeids;

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

    double hypervolume_;

    /**
     *  Manages free individual ID's
     *  @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;
    }
};

261
#endif