namespace BRKGA

Overview

This namespace contains all facilities related to BRKGA Multi Parent with Implicit Path Relinking. More…

namespace BRKGA {

// namespaces

namespace BRKGA::PathRelinking;

// typedefs

typedef std::vector<double> Chromosome;
typedef double fitness_t;

// enums

enum BiasFunctionType;
enum Sense;
enum ShakingType;

// classes

class AlgorithmStatus;

template <class Decoder>
class BRKGA_MP_IPR;

class BrkgaParams;
class ControlParams;
class DistanceFunctionBase;
class HammingDistance;
class KendallTauDistance;
class Population;

// global variables

static constexpr fitness_t FITNESS_T_MIN = FITNESS_T_MIN_TEMPLATE<fitness_t>;
static constexpr fitness_t FITNESS_T_MAX = FITNESS_T_MAX_TEMPLATE<fitness_t>;
constexpr double EQUALITY_THRESHOLD = 1e-6;

// global functions

template <class T>
constexpr bool close_enough(
    T a,
    T b
);

template <
    size_t I = 0,
    typename T,
    typename... Ts
>
constexpr bool close_enough(
    std::tuple<T, Ts...> a,
    std::tuple<T, Ts...> b
);

INLINE std::pair<BrkgaParams, ControlParams> readConfiguration(
    std::istream& input,
    std::ostream& logger = std::cout
);

INLINE std::pair<BrkgaParams, ControlParams> readConfiguration(
    const std::string& filename,
    std::ostream& logger = std::cout
);

INLINE std::ostream& operator << (
    std::ostream& os,
    const BrkgaParams& brkga_params
);

INLINE std::ostream& operator << (
    std::ostream& os,
    const ControlParams& control_params
);

INLINE void writeConfiguration(
    std::ostream& output,
    const BrkgaParams& brkga_params,
    const ControlParams& control_params = ControlParams{}
);

INLINE void writeConfiguration(
    const std::string& filename,
    const BrkgaParams& brkga_params,
    const ControlParams& control_params = ControlParams{}
);

std::ostream& operator << (
    std::ostream& output,
    const AlgorithmStatus& status
);

} // namespace BRKGA

Detailed Documentation

This namespace contains all facilities related to BRKGA Multi Parent with Implicit Path Relinking.

Typedefs

typedef std::vector<double> Chromosome

Chromosone representation.

The chromosome is represented using a vector in the unitary hypercube, i.e., \(v \in [0,1]^n\) where \(n\) is the size of the array (dimensions of the hypercube). We use double precision because float precision maybe not be enough for some applications.

We could use std::vector<double> directly. However, using an alias, we can add additional capabilities to the Chromosome class in the future, such as parenting track. For example, we may want to do this:

class Chromosome: public std::vector<double> {
    public:
        Chromosome() :
            std::vector<double>(), my_personal_data(0.0)
            {}
    public:
        double my_personal_data;
};

to keep track of some data within a specifc chromosome.

In general, most people do not recommend to inherit publicly from std::vector because it has no virtual destructor. However, we may do that as long as:

1. We remember that every operation provided by std::vector must be a semantically valid operation on an object of the derived class;

2. We avoid creating derived class objects with dynamic storage duration;

3. We DO AVOID polymorphism:

std::vector<double>* pt = new Chromosome();     // Bad idea
delete pt;      // Delete does not call the Chromosome destructor

typedef double fitness_t

Fitness type representation.

In general, fitness_t is a single number for single-objective problems. For instance:

using fitness_t = double;

For multi-objective problems (with dominance/lexicographical sorting), we need to use multiple values. We can either use a class, structure, or std::tuple. Using a custom class or structure, we must provide copy assignment (operator=), comparison operators (operator<, operator>, and operator==), and the streaming operator std::ostream& operator<<(std::ostream& os, const CustomFitness& fitness) where CustomFitness is your fitness structure. We have all these perks using std:tuple. For example, assume we have three minimization objective functions. Then we may have:

using fitness_t = std::tuple<double, double, double>;

Note

We do recommend use std::tuple.

Internally, BRKGA-MP-IPR doesn’t use operator== directly. BRKGA implements the custom function close_enough(). For fundamental numerical types, it compares the absolute difference with a given EQUALITY_THRESHOLD, i.e., two numbers \(a\) and \(b\) equal if \(|a - b| < EQUALITY\_THRESHOLD\). For all other types (except std::tuple), we use operator==. For std::tuple, we have a specialized function close_enough() that iterates over each element of the tuples calling the base close_enough().

Warning

If you are using custom class other than fundamental types or tuples with fundamental types, you must also provide two const template expressions FITNESS_T_MIN and FITNESS_T_MAX.

Global Variables

static constexpr fitness_t FITNESS_T_MIN = FITNESS_T_MIN_TEMPLATE<fitness_t>

The actual minimal value to fitness_t.

static constexpr fitness_t FITNESS_T_MAX = FITNESS_T_MAX_TEMPLATE<fitness_t>

The actual Maximum value to fitness_t.

constexpr double EQUALITY_THRESHOLD = 1e-6

This constant is used to compare floating-point numbers to equality. Therefore, we consider two numbers \(a\) and \(b\) equal if \(|a - b| < EQUALITY\_THRESHOLD\).

Currently, this constant is only used during IPR procedures to compare fitness with fundamental types (int, flot, char, etc), either single type or embedded in a tuple. If your fitness_t has a custom type, this is not applied, as explained in fitness_t.