map_elites_strategy (faber_neuroevolution v1.2.4)
View SourceMAP-Elites quality-diversity evolution strategy.
MAP-Elites is a quality-diversity algorithm that maintains a map (grid) of elite solutions. Each cell in the grid corresponds to a region of behavior space, and contains the highest-fitness individual whose behavior maps to that region.
This approach simultaneously optimizes for: - Quality: Each cell contains the best-performing solution for that behavior - Diversity: The grid covers a wide range of behaviors
Behavior Space
The behavior space is divided into discrete bins: - behavior_dimensions: number of dimensions (e.g., 2 for a 2D grid) - bins_per_dimension: discretization resolution (e.g., 10 means 10x10=100 cells) - behavior_bounds: min/max for each dimension (for normalization)
The evaluator must return behavior descriptors in metrics: #{fitness => F, metrics => #{behavior => [float(), ...]}}
Algorithm
1. Initialize: Generate random individuals, evaluate, place in grid 2. Select: Choose parents from existing elites 3. Mutate: Create offspring through mutation 4. Evaluate: Get fitness and behavior for offspring 5. Update: Place offspring in grid if better than current occupant 6. Repeat from step 2
Key Properties
- Grid cells act as niches preventing competition between behaviors - Elites are never deleted, only replaced by better solutions - Coverage metric: fraction of cells with elites - QD-score: sum of all elite fitnesses (quality × diversity)
Summary
Functions
Apply meta-controller parameter adjustments.
Get inputs for the meta-controller.
Get a snapshot of the current population state.
Handle an individual evaluation result.
Initialize the MAP-Elites strategy.
Periodic tick - not heavily used.
Types
-type birth_origin() :: initial | crossover | mutation | migration | insertion.
-type cell_index() :: tuple().
-type death_reason() ::
selection_pressure | stagnation | age_limit | niche_competition | migration |
population_limit | extinction.
-type fitness() :: float() | undefined.
-type generation() :: non_neg_integer().
-type genome() :: #genome{connection_genes :: [#connection_gene{innovation :: pos_integer() | undefined, from_id :: term(), to_id :: term(), weight :: float(), enabled :: boolean()}], input_count :: non_neg_integer(), hidden_count :: non_neg_integer(), output_count :: non_neg_integer()}.
-type individual() :: #individual{id :: individual_id(), network :: network(), genome :: genome() | undefined, parent1_id :: individual_id() | undefined, parent2_id :: individual_id() | undefined, fitness :: fitness(), metrics :: metrics(), generation_born :: generation(), birth_evaluation :: non_neg_integer(), max_age :: pos_integer(), is_survivor :: boolean(), is_offspring :: boolean()}.
-type individual_id() :: term().
-type individual_summary() :: #{id := individual_id(), fitness := fitness(), is_survivor => boolean(), is_offspring => boolean(), species_id => species_id(), age => non_neg_integer()}.
-type island_id() :: pos_integer() | atom().
-type lifecycle_event() :: #individual_born{id :: individual_id(), parent_ids :: [individual_id()], timestamp :: timestamp(), origin :: birth_origin(), metadata :: map()} | #individual_died{id :: individual_id(), reason :: death_reason(), final_fitness :: float() | undefined, timestamp :: timestamp(), metadata :: map()} | #individual_evaluated{id :: individual_id(), fitness :: float(), metrics :: map(), timestamp :: timestamp(), metadata :: map()} | #species_emerged{species_id :: species_id(), founder_id :: individual_id(), parent_species_id :: species_id() | undefined, timestamp :: timestamp(), metadata :: map()} | #species_extinct{species_id :: species_id(), reason :: stagnation | empty | merged | eliminated, final_stats :: map(), timestamp :: timestamp()} | #cohort_evaluated{generation :: pos_integer(), best_fitness :: float(), avg_fitness :: float(), worst_fitness :: float(), population_size :: pos_integer(), timestamp :: timestamp()} | #breeding_complete{generation :: pos_integer(), survivor_count :: non_neg_integer(), eliminated_count :: non_neg_integer(), offspring_count :: non_neg_integer(), timestamp :: timestamp()} | #generation_advanced{generation :: pos_integer(), previous_best_fitness :: float(), previous_avg_fitness :: float(), population_size :: pos_integer(), species_count :: non_neg_integer(), timestamp :: timestamp()} | #steady_state_replacement{replaced_ids :: [individual_id()], offspring_ids :: [individual_id()], best_fitness :: float() | undefined, avg_fitness :: float() | undefined, timestamp :: timestamp()} | #island_migration{individual_id :: individual_id(), from_island :: island_id(), to_island :: island_id(), fitness :: float(), timestamp :: timestamp()} | #island_topology_changed{islands :: [island_id()], connections :: [{island_id(), island_id()}], change_type :: island_added | island_removed | connection_changed, timestamp :: timestamp()} | #niche_discovered{niche_id :: niche_id(), behavior_descriptor :: [float()], individual_id :: individual_id(), fitness :: float(), timestamp :: timestamp()} | #niche_updated{niche_id :: niche_id(), old_individual_id :: individual_id(), new_individual_id :: individual_id(), old_fitness :: float(), new_fitness :: float(), improvement :: float(), timestamp :: timestamp()} | #archive_updated{size :: non_neg_integer(), coverage :: float(), qd_score :: float(), updates_since_last :: non_neg_integer(), timestamp :: timestamp()} | #competitor_updated{competitor_id :: term(), change_type :: generation_advanced | champion_changed | strategy_shift, champion_fitness :: float() | undefined, timestamp :: timestamp()} | #arms_race_event{event_type :: fitness_surge | counter_adaptation | stalemate | breakthrough, populations :: [term()], metrics :: map(), timestamp :: timestamp()} | #competition_result{competitors :: [individual_id()], scores :: [{individual_id(), float()}], winner_id :: individual_id() | draw, competition_type :: tournament | round_robin | elimination | ranked_match | team_vs_team, metadata :: map(), timestamp :: timestamp()} | #capability_emerged{capability_id :: term(), description :: binary(), exhibitors :: [individual_id()], timestamp :: timestamp()} | #complexity_increased{metric :: genome_size | network_depth | behavior_repertoire | term(), old_value :: number(), new_value :: number(), increase_pct :: float(), timestamp :: timestamp()} | #progress_checkpoint{total_evaluations :: non_neg_integer(), evaluations_since_last :: non_neg_integer(), cohort :: non_neg_integer(), best_fitness :: float(), avg_fitness :: float(), worst_fitness :: float(), population_size :: non_neg_integer(), species_count :: pos_integer(), improvement :: float(), elapsed_ms :: non_neg_integer(), evals_per_second :: float(), checkpoint_interval :: non_neg_integer(), timestamp :: timestamp()} | #environment_changed{environment_id :: term(), change_type :: difficulty_increased | difficulty_decreased | task_shifted | condition_changed | curriculum_advanced, description :: binary(), metrics :: map(), timestamp :: timestamp()} | #individual_aged_out{id :: individual_id(), final_age :: pos_integer(), final_fitness :: float(), lifetime_stats :: #{total_evaluations := non_neg_integer(), avg_fitness := float(), best_fitness := float(), offspring_count := non_neg_integer()}, timestamp :: timestamp()}.
-type map_elites_params() :: #map_elites_params{behavior_dimensions :: pos_integer(), bins_per_dimension :: pos_integer(), behavior_bounds :: [{float(), float()}], batch_size :: pos_integer(), random_probability :: float(), mutation_rate :: float(), mutation_strength :: float()}.
-type meta_inputs() :: [float()].
-type metrics() :: map().
-type mutation_config() :: #mutation_config{weight_mutation_rate :: float(), weight_perturb_rate :: float(), weight_perturb_strength :: float(), add_node_rate :: float(), add_connection_rate :: float(), toggle_connection_rate :: float(), add_sensor_rate :: float(), add_actuator_rate :: float(), mutate_neuron_type_rate :: float(), mutate_time_constant_rate :: float()}.
-type network() :: term().
-type neuro_config() :: #neuro_config{population_size :: pos_integer(), evaluations_per_individual :: pos_integer(), selection_ratio :: float(), mutation_rate :: float(), mutation_strength :: float(), reservoir_mutation_rate :: float() | undefined, reservoir_mutation_strength :: float() | undefined, readout_mutation_rate :: float() | undefined, readout_mutation_strength :: float() | undefined, topology_mutation_config :: mutation_config() | undefined, max_evaluations :: pos_integer() | infinity, max_generations :: pos_integer() | infinity, target_fitness :: float() | undefined, network_topology :: {pos_integer(), [pos_integer()], pos_integer()}, evaluator_module :: module(), evaluator_options :: map(), event_handler :: {module(), term()} | undefined, meta_controller_config :: term() | undefined, speciation_config :: speciation_config() | undefined, realm :: binary(), publish_events :: boolean(), evaluation_mode :: direct | distributed | mesh, mesh_config :: map() | undefined, evaluation_timeout :: pos_integer(), max_concurrent_evaluations :: pos_integer() | undefined, strategy_config :: term() | undefined, lc_chain_config :: term() | undefined, checkpoint_interval :: pos_integer() | undefined, checkpoint_config :: map() | undefined, seed_networks :: [term()]}.
-type niche_id() :: term().
-type population_snapshot() :: #{size := non_neg_integer(), individuals := [individual_summary()], best_fitness := fitness(), avg_fitness := fitness(), worst_fitness := fitness(), species_count => non_neg_integer(), generation => pos_integer(), extra => map()}.
-type speciation_config() :: #speciation_config{enabled :: boolean(), compatibility_threshold :: float(), c1_excess :: float(), c2_disjoint :: float(), c3_weight_diff :: float(), target_species :: pos_integer(), threshold_adjustment_rate :: float(), min_species_size :: pos_integer(), max_stagnation :: non_neg_integer(), species_elitism :: float(), interspecies_mating_rate :: float()}.
-type species_id() :: pos_integer().
-type strategy_action() :: {create_individual, ParentIds :: [individual_id()], Metadata :: map()} | {remove_individual, individual_id(), Reason :: death_reason()} | {evaluate_individual, individual_id()} | {evaluate_batch, [individual_id()]} | {update_config, ConfigUpdates :: map()} | {migrate_individual, individual_id(), ToIsland :: island_id()} | {update_archive, ArchiveUpdate :: term()} | {emit_event, lifecycle_event()} | noop.
-type strategy_result() :: {Actions :: [strategy_action()], Events :: [lifecycle_event()], NewState :: strategy_state()}.
-type strategy_state() :: term().
-type timestamp() :: erlang:timestamp().
Functions
-spec apply_meta_params(Params :: meta_params(), State :: #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}) -> #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}.
Apply meta-controller parameter adjustments.
-spec get_meta_inputs(State :: #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}) -> meta_inputs().
Get inputs for the meta-controller.
-spec get_population_snapshot(State :: #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}) -> population_snapshot().
Get a snapshot of the current population state.
-spec handle_evaluation_result(IndividualId :: individual_id(), FitnessResult :: map(), State :: #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}) -> strategy_result().
Handle an individual evaluation result.
When an individual is evaluated: 1. Compute which cell it belongs to 2. If cell is empty or new individual is better, update the grid 3. When batch is complete, generate new batch from elites
-spec init(Config :: map()) -> {ok, #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}, [lifecycle_event()]} | {error, term()}.
Initialize the MAP-Elites strategy.
-spec tick(State :: #me_state{config :: neuro_config(), params :: map_elites_params(), network_factory :: module(), grid :: #{cell_index() => individual()}, dimensions :: pos_integer(), bins :: pos_integer(), total_cells :: pos_integer(), bounds :: [{float(), float()}], batch :: [individual()], batch_map :: #{individual_id() => individual()}, batch_size :: pos_integer(), evaluated_count :: non_neg_integer(), iteration :: pos_integer(), cells_filled :: non_neg_integer(), total_evaluations :: non_neg_integer(), best_fitness :: float(), qd_score :: float()}) -> strategy_result().
Periodic tick - not heavily used.