macula_tweann

%% @doc Selection algorithms for evolutionary processes.
%%
%% This module provides various selection strategies for choosing
%% surviving agents from a population based on fitness. Each strategy
%% implements a different approach to balancing exploration vs exploitation:
%%
%% - Competition: Top performers survive (pure exploitation)
%% - Tournament: Random tournaments with best winner (balanced)
%% - Steady State: Incremental replacement (conservative)
%%
%% == Selection Strategies ==
%%
%% Competition Selection:
%% - Sort population by fitness (descending)
%% - Select top N agents based on survival rate
%% - Guarantees best performers survive
%% - Fast convergence but risks premature convergence
%% - Best for well-understood fitness landscapes
%%
%% Tournament Selection:
%% - Run K tournaments of size TournamentSize
%% - Each tournament selects best from random subset
%% - Provides diversity through randomness
%% - Tournament size controls selection pressure
%% - Good balance of exploration and exploitation
%%
%% Steady State Selection:
%% - Replace worst N agents with offspring
%% - Keep majority of population unchanged
%% - Very conservative, slow convergence
%% - Good for maintaining diversity
%% - Useful when fitness landscape is deceptive
%%
%% == Fitness Comparison ==
%%
%% All strategies use multi-objective fitness vectors [F1, F2, ...].
%% Comparison is by sum of components (weighted sum aggregation).
%% For more sophisticated multi-objective optimization, use
%% fitness_postprocessor module to apply Pareto dominance first.
%%
%% @author Macula.io
%% @copyright 2025 Macula.io, Apache-2.0
-module(selection_algorithm).

-export([
    competition/2,
    tournament/3,
    steady_state/2
]).

%% ============================================================================
%% API
%% ============================================================================

%% @doc Competition selection - select top performers.
%%
%% Sorts agents by fitness (descending) and selects the top N performers
%% based on survival rate. This is the most aggressive selection strategy,
%% providing strong selection pressure toward the best solutions.
%%
%% Example:
%%   AgentFitnesses = [{agent1, [5.0]}, {agent2, [3.0]}, {agent3, [7.0]}]
%%   SurvivalRate = 0.5
%%   Result = competition(AgentFitnesses, SurvivalRate)
%%   Result = [agent3, agent1]  % Top 50% by fitness
%%
%% @param AgentFitnesses list of {AgentId, Fitness} tuples where Fitness
%%        is a vector [F1, F2, ...] of floats
%% @param SurvivalRate fraction of population to keep (0.0-1.0)
%% @returns list of surviving AgentIds sorted by fitness (best first)
-spec competition([{term(), [float()]}], float()) -> [term()].
competition([], _SurvivalRate) ->
    [];
competition(AgentFitnesses, SurvivalRate) ->
    %% Sort by fitness (descending - best first)
    Sorted = lists:sort(
        fun({_, F1}, {_, F2}) -> compare_fitness(F1, F2) end,
        AgentFitnesses
    ),

    %% Calculate number of survivors (at least 1)
    NumSurvivors = max(1, round(length(AgentFitnesses) * SurvivalRate)),

    %% Take top N agents
    Survivors = lists:sublist(Sorted, NumSurvivors),
    [AgentId || {AgentId, _Fitness} <- Survivors].

%% @doc Tournament selection - run tournaments to select survivors.
%%
%% Runs K tournaments where each tournament randomly selects TournamentSize
%% agents and picks the best. This provides a good balance between selection
%% pressure (controlled by tournament size) and diversity (through randomness).
%%
%% Larger tournament sizes increase selection pressure (more elitist).
%% Smaller tournament sizes increase diversity (more exploratory).
%%
%% Example:
%%   AgentFitnesses = [{agent1, [5.0]}, {agent2, [3.0]}, {agent3, [7.0]},
%%                     {agent4, [4.0]}, {agent5, [6.0]}]
%%   SurvivalRate = 0.4
%%   TournamentSize = 2
%%   Result = tournament(AgentFitnesses, SurvivalRate, TournamentSize)
%%   Result might be [agent3, agent5] (winners of 2 tournaments)
%%
%% @param AgentFitnesses list of {AgentId, Fitness} tuples
%% @param SurvivalRate fraction of population to keep (0.0-1.0)
%% @param TournamentSize number of agents per tournament (typically 2-5)
%% @returns list of surviving AgentIds (tournament winners)
-spec tournament([{term(), [float()]}], float(), pos_integer()) -> [term()].
tournament([], _SurvivalRate, _TournamentSize) ->
    [];
tournament(AgentFitnesses, SurvivalRate, TournamentSize) ->
    %% Calculate number of tournaments to run
    NumSurvivors = max(1, round(length(AgentFitnesses) * SurvivalRate)),

    %% Run tournaments
    Survivors = lists:map(
        fun(_) ->
            %% Select random contestants
            Contestants = select_random_contestants(AgentFitnesses, TournamentSize),

            %% Find winner (best fitness)
            {WinnerId, _WinnerFitness} = find_best_agent(Contestants),
            WinnerId
        end,
        lists:seq(1, NumSurvivors)
    ),

    %% Remove duplicates (same agent can win multiple tournaments)
    lists:usort(Survivors).

%% @doc Steady state selection - replace worst performers with new agents.
%%
%% This is the most conservative selection strategy. It keeps the majority
%% of the population unchanged and only replaces the worst performers.
%% Good for maintaining diversity and avoiding premature convergence.
%%
%% The survival rate determines what fraction of the worst agents to replace.
%% For example, SurvivalRate=0.8 means keep top 80% and replace bottom 20%.
%%
%% Example:
%%   AgentFitnesses = [{agent1, [5.0]}, {agent2, [3.0]}, {agent3, [7.0]},
%%                     {agent4, [1.0]}, {agent5, [6.0]}]
%%   SurvivalRate = 0.6
%%   Result = steady_state(AgentFitnesses, SurvivalRate)
%%   Result = [agent3, agent5, agent1]  % Top 60% survive
%%
%% @param AgentFitnesses list of {AgentId, Fitness} tuples
%% @param SurvivalRate fraction of population to keep (0.0-1.0)
%% @returns list of surviving AgentIds
-spec steady_state([{term(), [float()]}], float()) -> [term()].
steady_state(AgentFitnesses, SurvivalRate) ->
    %% Steady state is essentially the same as competition selection
    %% The difference is in how offspring are generated (not in this module)
    %% For selection purposes, we keep the top N performers
    competition(AgentFitnesses, SurvivalRate).

%% ============================================================================
%% Internal Functions
%% ============================================================================

%% @private Compare two fitness vectors (higher is better).
-spec compare_fitness([float()], [float()]) -> boolean().
compare_fitness(F1, F2) ->
    sum_fitness(F1) >= sum_fitness(F2).

%% @private Sum fitness vector components.
-spec sum_fitness([float()]) -> float().
sum_fitness(Fitness) ->
    lists:sum(Fitness).

%% @private Select N random agents from population.
-spec select_random_contestants([{term(), [float()]}], pos_integer()) ->
    [{term(), [float()]}].
select_random_contestants(AgentFitnesses, N) ->
    %% Don't select more than available
    ActualN = min(N, length(AgentFitnesses)),

    %% Shuffle and take first N
    Shuffled = shuffle(AgentFitnesses),
    lists:sublist(Shuffled, ActualN).

%% @private Shuffle a list using Fisher-Yates algorithm.
-spec shuffle([T]) -> [T].
shuffle(List) ->
    %% Convert to array for efficient random access
    Array = array:from_list(List),
    Size = array:size(Array),

    %% Shuffle array indices
    ShuffledArray = shuffle_array(Array, Size - 1),

    %% Convert back to list
    array:to_list(ShuffledArray).

%% @private Shuffle array in place (Fisher-Yates).
-spec shuffle_array(array:array(T), integer()) -> array:array(T).
shuffle_array(Array, -1) ->
    Array;
shuffle_array(Array, I) ->
    %% Select random index from 0 to I
    J = rand:uniform(I + 1) - 1,

    %% Swap elements at I and J
    ElemI = array:get(I, Array),
    ElemJ = array:get(J, Array),
    Array1 = array:set(I, ElemJ, Array),
    Array2 = array:set(J, ElemI, Array1),

    %% Continue with next index
    shuffle_array(Array2, I - 1).

%% @private Find agent with best fitness in a list.
-spec find_best_agent([{term(), [float()]}]) -> {term(), [float()]}.
find_best_agent([First | Rest]) ->
    lists:foldl(
        fun({_Id, Fitness} = Agent, {_BestId, BestFitness} = BestSoFar) ->
            case compare_fitness(Fitness, BestFitness) of
                true -> Agent;
                false -> BestSoFar
            end
        end,
        First,
        Rest
    ).