novelty_strategy (faber_neuroevolution v1.2.4)
View SourceNovelty Search evolution strategy.
Novelty Search replaces fitness-based selection with novelty-based selection. Instead of selecting for the fittest individuals, it selects for those with the most novel behaviors - behaviors that are different from both the current population and an archive of previously seen behaviors.
This approach is particularly effective for: - Deceptive fitness landscapes where fitness gradients lead to local optima - Open-ended exploration where diverse solutions are valuable - Problems where the path to the solution is not clear
Behavior Descriptors
The evaluator must return a behavior descriptor in the metrics map: #{fitness => F, metrics => #{behavior => [float(), ...]}}
The behavior descriptor is a vector characterizing the individual's behavior. For example: - For a maze robot: final (x, y) position - For a game AI: action frequencies, states visited - For neural networks: activation patterns
Novelty Calculation
Novelty is the average distance to the k-nearest neighbors in behavior space. Neighbors come from both the current population and the archive.
novelty(ind) = avg(distance(ind, neighbor_i)) for i in 1..k
Hybrid Mode
When include_fitness=true and fitness_weight > 0, selection is based on: score = (1 - fitness_weight) * novelty + fitness_weight * fitness
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 novelty search strategy.
Periodic tick - not heavily used in novelty strategy.
Types
-type behavior_descriptor() :: {individual_id(), [float()]}.
-type birth_origin() :: initial | crossover | mutation | migration | insertion.
-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 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 novelty_params() :: #novelty_params{archive_size :: pos_integer(), archive_probability :: float(), k_nearest :: pos_integer(), include_fitness :: boolean(), fitness_weight :: float(), novelty_threshold :: float(), behavior_dimensions :: pos_integer() | undefined}.
-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 :: #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}) -> #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}.
Apply meta-controller parameter adjustments.
-spec get_meta_inputs(State :: #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}) -> meta_inputs().
Get inputs for the meta-controller.
-spec get_population_snapshot(State :: #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}) -> population_snapshot().
Get a snapshot of the current population state.
-spec handle_evaluation_result(IndividualId :: individual_id(), FitnessResult :: map(), State :: #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}) -> strategy_result().
Handle an individual evaluation result.
Accumulates behavior descriptors, computes novelty scores when all are evaluated, then performs novelty-based selection and breeding.
-spec init(Config :: map()) -> {ok, #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}, [lifecycle_event()]} | {error, term()}.
Initialize the novelty search strategy.
Expects config map with: - neuro_config - the full neuroevolution config - strategy_params - optional novelty_params record or map - network_factory - optional module for network creation
-spec tick(State :: #novelty_state{config :: neuro_config(), params :: novelty_params(), network_factory :: module(), population :: [individual()], population_map :: #{individual_id() => individual()}, population_size :: pos_integer(), generation :: pos_integer(), evaluated_count :: non_neg_integer(), archive :: [behavior_descriptor()], best_novelty :: float(), avg_novelty :: float(), best_fitness :: float(), archive_adds :: non_neg_integer()}) -> strategy_result().
Periodic tick - not heavily used in novelty strategy.