Population.h

Go to the documentation of this file.

//
// 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.
//
// Copyright (c) 2010 - 2013, Yves Ineichen, ETH Zürich
// All rights reserved
//
// Implemented as part of the PhD thesis
// "Toward massively parallel multi-objective optimization with application to
// particle accelerators" (https://doi.org/10.3929/ethz-a-009792359)
//
// This file is part of OPAL.
//
// OPAL 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
// (at your option) any later version.
//
// You should have received a copy of the GNU General Public License
// along with OPAL. If not, see <https://www.gnu.org/licenses/>.
//
#ifndef __POPULATION_H__
#define __POPULATION_H__

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

#include "extlib/wfgHypervolume/hypervolume.h"


template< class Individual_t >
class Population {

public:
    Population() {
        last_identity = 0;
    }

    ~Population() {}

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

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

    unsigned int add_individual(individual ind) {

        unsigned int id = getFreeID();
        stagingArea.insert(ind_t(id, ind));
        ind->id_m = 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++;
        }
    }

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

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

    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++;
        }
    }


    //XXX: currently O(n): add a fast look-up table?
    bool isRepresentedInPopulation(genes_t ind_genes) {

        for(ind_t ind : individuals) {
            if( ind_genes == ind.second->genes_m )
                return true;
        }

        return false;
    }


    double computeHypervolume(size_t island_id, const std::vector<double>& referencePoint) {
        // protection check
        if (individuals.empty() == true) return -1;

        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_m.size(); i++)
                file << temp->objectives_m[i] << " ";
            if (!temp->objectives_m.empty())
                file << std::endl;
        }

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

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

        return Hypervolume::FromFile(filename.str(), referencePoint);
    }


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


    indItr_t stagingBegin() { return stagingArea.begin(); }
    indItr_t stagingEnd()   { return stagingArea.end(); }


    unsigned int size() const { return individuals.size(); }

    indItr_t begin() { return individuals.begin(); }
    indItr_t end()   { return individuals.end(); }
    indItr_t erase(indItr_t it) { return individuals.erase(it); }

private:

    std::map<unsigned int, individual > individuals;

    std::map<unsigned int, individual > stagingArea;

    std::queue<unsigned int> freeids;

    unsigned int last_identity;

    unsigned int getFreeID() {

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

        return id;
    }
};

#endif