Improved Harmony Search (IHS)

class pagmo::ihs

Improved Harmony Search.

../../../_images/ihs.gif

Harmony search (HS) is a metaheuristic algorithm said to mimick the improvisation process of musicians. In the metaphor, each musician (i.e., each variable) plays (i.e., generates) a note (i.e., a value) for finding a best harmony (i.e., the global optimum) all together.

This code implements the so-called improved harmony search algorithm (IHS), in which the probability of picking the variables from the decision vector and the amount of mutation to which they are subject vary (respectively linearly and exponentially) at each call of the evolve() method.

In this algorithm the number of fitness function evaluations is equal to the number of iterations. All the individuals in the input population participate in the evolution. A new individual is generated at every iteration, substituting the current worst individual of the population if better.

Warning

The HS algorithm can and has been criticized, not for its performances, but for the use of a metaphor that does not add anything to existing ones. The HS algorithm essentially applies mutation and crossover operators to a background population and as such should have been developed in the context of Evolutionary Strategies or Genetic Algorithms and studied in that context. The use of the musicians metaphor only obscures its internal functioning making theoretical results from ES and GA erroneously seem as unapplicable to HS.

Note

The original IHS algorithm was designed to solve unconstrained, deterministic single objective problems. In pagmo, the algorithm was modified to tackle also multi-objective (unconstrained), constrained (single-objective), mixed-integer and stochastic problems. Such extension is original with pagmo.

See also

https://en.wikipedia.org/wiki/Harmony_search for an introduction on harmony search.

See also

https://linkinghub.elsevier.com/retrieve/pii/S0096300306015098 for the paper that introduces and explains improved harmony search.

Public Types

typedef std::tuple<unsigned long long, double, double, double, double, vector_double::size_type, double, vector_double> log_line_type

Single data line for the algorithm’s log.

A log data line is a tuple consisting of:

  • the number of objective function evaluations made so far,

  • the pitch adjustment rate,

  • the distance bandwidth

  • the population flatness evaluated as the distance between the decisions vector of the best and of the worst individual (or -1 in a multiobjective case),

  • the population flatness evaluated as the distance between the fitness of the best and of the worst individual (or -1 in a multiobjective case),

  • the number of constraints violated by the current decision vector,

  • the constraints violation norm for the current decision vector,

  • the objective value of the best solution or, in the multiobjective case, the ideal point

typedef std::vector<log_line_type> log_type

Log type.

The algorithm log is a collection of ihs::log_line_type data lines, stored in chronological order during the optimisation if the verbosity of the algorithm is set to a nonzero value (see ihs::set_verbosity()).

Public Functions

ihs(unsigned gen = 1u, double phmcr = 0.85, double ppar_min = 0.35, double ppar_max = 0.99, double bw_min = 1E-5, double bw_max = 1., unsigned seed = pagmo::random_device::next())

Constructor.

Constructs ihs

Parameters
  • gen – Number of generations to consider. Each generation will compute the objective function once.

  • phmcr – probability of choosing from memory (similar to a crossover probability)

  • ppar_min – minimum pitch adjustment rate. (similar to a mutation rate)

  • ppar_max – maximum pitch adjustment rate. (similar to a mutation rate)

  • bw_min – minimum distance bandwidth. (similar to a mutation width)

  • bw_max – maximum distance bandwidth. (similar to a mutation width)

  • seed – seed used by the internal random number generator

Throws

value_error – if phmcr is not in the ]0,1[ interval, ppar min/max are not in the ]0,1[ interval, min/max quantities are less than/greater than max/min quantities, bw_min is negative.

population evolve(population) const

Algorithm evolve method.

Parameters

pop – population to be evolved

Throws

std::invalid_argument – if the problem is multi-objective or constrained

Returns

evolved population

inline void set_verbosity(unsigned n)

Set verbosity.

This method will set the algorithm’s verbosity. If n is zero, no output is produced during the optimisation and no logging is performed. If n is nonzero, then every n objective function evaluations the status of the optimisation will be both printed to screen and recorded internally. See ihs::log_line_type and ihs::log_type for information on the logging format. The internal log can be fetched via get_log().

Example (verbosity 100, a constrained problem):

Fevals:          ppar:            bw:            dx:            df:      Violated:    Viol. Norm:        ideal1:
      1        0.35064       0.988553        5.17002        68.4027              1      0.0495288        85.1946
    101        0.41464       0.312608        4.21626         46.248              1      0.0495288        85.1946
    201        0.47864      0.0988553        2.27851        8.00679              1      0.0495288        85.1946
    301        0.54264      0.0312608        3.94453        31.9834              1      0.0495288        85.1946
    401        0.60664     0.00988553        4.74834         40.188              1      0.0495288        85.1946
    501        0.67064     0.00312608        2.91583        6.53575              1     0.00904482        90.3601
    601        0.73464    0.000988553        2.98691        10.6425              1    0.000760728        110.121
    701        0.79864    0.000312608        2.27775        39.7507              1    0.000760728        110.121
    801        0.86264    9.88553e-05       0.265908         4.5488              1    0.000760728        110.121
    901        0.92664    3.12608e-05       0.566348       0.354253              1    0.000760728        110.121
Feasibility is checked against the problem’s tolerance.

By default, the verbosity level is zero.

Parameters

n – the desired verbosity level.

inline unsigned get_verbosity() const

Gets the verbosity level.

Returns

the verbosity level

void set_seed(unsigned)

Sets the seed.

Parameters

seed – the seed controlling the algorithm stochastic behaviour

inline unsigned get_seed() const

Gets the seed.

Returns

the seed controlling the algorithm stochastic behaviour

inline std::string get_name() const

Algorithm name.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing the algorithm name

std::string get_extra_info() const

Extra info.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing extra info on the algorithm

inline const log_type &get_log() const

Get the optimisation log.

See ihs::log_type for a description of the optimisation log. Logging is turned on/off via set_verbosity().

Returns

a const reference to the log.