.. _library_genetic_algorithm:

``genetic_algorithm``
=====================

Genetic algorithms are population-based meta-heuristics inspired by
natural selection. A population of candidate solutions (individuals)
evolves over successive generations through selection, crossover
(recombination), and mutation. They are effective for combinatorial and
continuous optimization problems such as the Traveling Salesman Problem
(TSP), scheduling, and parameter tuning.

The library provides the parametric object
``genetic_algorithm(Problem, RandomAlgorithm)`` where ``Problem`` is an
object implementing the ``genetic_algorithm_problem_protocol`` protocol
and ``RandomAlgorithm`` is one of the algorithms supported by the
``fast_random`` library. The algorithm minimizes the energy (cost)
function defined by the problem by default; maximization is supported
via the ``objective/1`` option.

A convenience object ``genetic_algorithm(Problem)`` is also provided,
using the Xoshiro128++ random number generator (``xoshiro128pp``) as the
default.

API documentation
-----------------

Open the
`../../apis/library_index.html#genetic-algorithm <../../apis/library_index.html#genetic-algorithm>`__
link in a web browser.

Loading
-------

To load all entities in this library, load the ``loader.lgt`` file:

::

   | ?- logtalk_load(genetic_algorithm(loader)).

Testing
-------

To test this library predicates, load the ``tester.lgt`` file:

::

   | ?- logtalk_load(genetic_algorithm(tester)).

Features
--------

- **Configurable random number generator** - the algorithm is
  parameterized by a ``fast_random`` algorithm. Available algorithms
  include ``xoshiro128pp``, ``xoshiro128ss``, ``xoshiro256pp``,
  ``xoshiro256ss``, ``well512a``, ``splitmix64``, and ``as183``. The
  convenience object ``genetic_algorithm(Problem)`` defaults to
  ``xoshiro128pp``.
- **Configurable selection** - parent selection is controlled by the
  ``selection/1`` option. Supported schemes are ``tournament(K)``
  (default ``tournament(3)``), ``roulette`` (fitness-proportionate), and
  ``rank`` (linear rank weights after sorting by objective).
- **Adaptive rates** - crossover and mutation rates can be held constant
  or adapted each generation. Built-in schedules are ``constant``,
  ``linear(Initial, Final)``, and ``geometric(Factor)``. Optional
  problem hooks ``crossover_rate/4`` and ``mutation_rate/4`` override
  the configured schedules when defined.
- **Problem-defined genetic operators** - crossover (``crossover/4``)
  and mutation (``mutate/2``) are supplied by the problem object,
  allowing arbitrary representations (permutations, real vectors,
  bit-strings, trees, etc.).
- **Elitism preservation** - the best ``elite_size(N)`` individuals are
  copied unchanged into the next generation (default N = 1), protecting
  them from crossover and mutation. N is clamped to the population size.
  Set to 0 to disable.
- **Minimization or maximization** - controlled by the ``objective/1``
  option (``minimize`` by default).
- **Best individual tracking** - the algorithm tracks the best
  individual found across all generations, not just the final
  population.
- **Progress reporting** - if the problem object defines ``progress/5``,
  it is called periodically with the current generation, best
  individual, best energy, mean population energy, and diversity. A
  final report is always produced when updates are enabled.
- **Run statistics** - the ``run/4`` predicate returns a list of
  statistics including the number of generations, fitness evaluations,
  improvements, and the final population size.
- **Seed control** - the ``seed(S)`` option initializes the random
  number generator for reproducible runs.
- **Optional initial population** - when the problem defines
  ``initial_population/1`` that list is used (padded or truncated to the
  requested size); otherwise individuals are generated via
  ``random_individual/1``.

Defining a problem
------------------

A problem object must implement the
``genetic_algorithm_problem_protocol`` protocol by defining (at least)
the following predicates:

- ``random_individual(-Individual)`` - generates a random candidate
  solution.
- ``state_energy(+Individual, -Energy)`` - computes the cost/fitness of
  an individual (minimized by default).
- ``crossover(+Parent1, +Parent2, -Offspring1, -Offspring2)`` -
  recombines two parents into two offspring.
- ``mutate(+Individual, -Mutated)`` - produces a mutated individual.

Optionally, the problem object may also define:

- ``initial_population(-Population)`` - returns a non-empty list of
  initial individuals.
- ``stop_condition(+Generation, +BestIndividual, +BestEnergy)`` -
  succeeds when the search should terminate early.
- ``progress(+Generation, +BestIndividual, +BestEnergy, +MeanEnergy, +Diversity)``

  - called periodically to report progress.

- ``diversity(+Population, -Diversity)`` - computes a numeric diversity
  measure for progress reporting.
- ``crossover_rate(+Generation, +MaxGenerations, +CurrentRate, -NewRate)``
  - optional adaptive crossover-rate hook (overrides
  ``crossover_schedule/1``).
- ``mutation_rate(+Generation, +MaxGenerations, +CurrentRate, -NewRate)``
  - optional adaptive mutation-rate hook (overrides
  ``mutation_schedule/1``).

Options
-------

Options for the ``run/3-4`` predicates:

- ``max_generations(N)`` - maximum number of generations (default:
  ``200``).
- ``population_size(N)`` - population size; must be at least 2 (default:
  ``50``).
- ``crossover_rate(P)`` - initial crossover probability (default:
  ``0.8``).
- ``mutation_rate(P)`` - initial mutation probability (default:
  ``0.1``).
- ``crossover_schedule(Schedule)`` - ``constant`` (default),
  ``linear(Initial, Final)``, or ``geometric(Factor)``. Overridden by a
  problem ``crossover_rate/4`` hook when defined.
- ``mutation_schedule(Schedule)`` - ``constant`` (default),
  ``linear(Initial, Final)``, or ``geometric(Factor)``. Overridden by a
  problem ``mutation_rate/4`` hook when defined.
- ``selection(Scheme)`` - parent selection scheme: ``tournament(K)``
  with positive integer K (default: ``tournament(3)``), ``roulette``, or
  ``rank``.
- ``elite_size(N)`` - number of elite individuals preserved each
  generation (default: ``1``). Use ``0`` to disable elitism.
- ``objective(Direction)`` - ``minimize`` (default) or ``maximize``.
- ``updates(N)`` - number of progress reports during the run. Set to
  ``0`` to disable (default: ``0``).
- ``seed(S)`` - positive integer seed for the random number generator,
  enabling reproducible runs (default: none).

Run statistics
--------------

The ``run/4`` predicate returns a list of statistics about the completed
run:

- ``generations(N)`` - number of generations executed.
- ``evaluations(E)`` - total number of fitness evaluations.
- ``improvements(I)`` - number of generations that strictly improved the
  best energy found.
- ``final_population_size(S)`` - size of the final population.

**Limitations**
---------------

- **Single population, generational model** - a classic generational GA
  is implemented. Steady-state replacement, multi-population (island)
  models, and coevolution are not provided.
- **Limited selection schemes** - tournament, roulette-wheel, and linear
  rank selection are implemented. Other schemes (e.g. stochastic
  universal sampling, Boltzmann selection) are not provided.
- **Limited adaptive schedules** - constant, linear, and geometric rate
  schedules are supported, plus optional problem hooks. Other adaptive
  policies (e.g. diversity-triggered rates) require a custom hook.
- **No built-in representation** - chromosomes, real vectors, and other
  encodings must be defined by the problem together with suitable
  crossover and mutation operators.
- **Diversity is optional** - a problem-specific ``diversity/2``
  predicate is required for meaningful diversity reporting; otherwise a
  placeholder value of 0.0 is used.

Usage
-----

Example of a problem definiton
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Define an object implementing the ``genetic_algorithm_problem_protocol``
protocol. For example, a simple quadratic minimization problem on the
real line:

::

   :- object(quadratic,
       implements(genetic_algorithm_problem_protocol)).

       :- uses(fast_random(xoshiro128pp), [
           random/3, randomize/1
       ]).

       :- public(reset_seed/0).
       reset_seed :-
           randomize(12345).

       random_individual(X) :-
           random(-50.0, 50.0, X).

       state_energy(X, E) :-
           E is (X - 3.0) * (X - 3.0).

       crossover(X, Y, C1, C2) :-
           % arithmetic crossover
           Alpha is 0.5,
           C1 is Alpha*X + (1-Alpha)*Y,
           C2 is Alpha*Y + (1-Alpha)*X.

       mutate(X, Y) :-
           random(-2.0, 2.0, Delta),
           Y is X + Delta.

   :- end_object.

Running the algorithm
~~~~~~~~~~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic)::run(State, Energy).
   State = 3.00..., Energy = 0.000...

Running with custom options
~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic)::run(State, Energy, [
            max_generations(100),
            population_size(40),
            crossover_rate(0.9),
            mutation_rate(0.15),
            elite_size(2)
        ]).
   State = 3.00..., Energy = 0.000...

Running with statistics
~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic)::run(State, Energy, Stats, []).
   State = 3.00..., Energy = 0.000...,
   Stats = [generations(200), evaluations(...), improvements(...), final_population_size(50)]

Reproducible runs with seed
~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic)::run(S1, E1, [seed(42)]),
        genetic_algorithm(quadratic)::run(S2, E2, [seed(42)]).
   S1 = S2, E1 = E2.

Maximization
~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic)::run(State, Energy, [objective(maximize)]).
   % (would climb away from the minimum if the landscape allowed)

Using a custom random number generator
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- genetic_algorithm(quadratic, well512a)::run(State, Energy).
   State = 3.00..., Energy = 0.000...
