1 unstable release
0.1.0 | Mar 27, 2022 |
---|
#817 in Science
Used in 2 crates
(via memeroute)
105KB
2.5K
SLoC
GA
Just contains my notes about what I'm doing.
TODO
multi-objective optimization - currently just does weird fitness combinations
Selection strategies
- SUS based on fitness
- RWS based on fitness
- Look for maximally different parent (not implemented)
Survival strategies
- Top proportion
- Top proportion from each species
- Age based replacement (not implemented)
- Tournament selection (not implemented)
Crossover strategies
- k-point crossover
- Uniform crossover
- Partially mapped crossover
- Edge crossover
- Order crossover
- Cycle crossover
Mutation strategies
- Single replacement - randomly replace a single gene
- Uniform mutation, non-uniform mutation
- Random resetting - randomly reset a state
- Swap mutation - randomly swap two genes
- Scramble mutation - scramble a substring
- Inversion mutation - invert a substring
- Creep mutation - add a value to gene; small creep, large creep
Niching
- No niching
- Shared fitness with species target
- Crowding (not implemented) - shared fitness generally better
Fitness evaluation
- Stepwise adaption of weights (not implemented)
- As time goes on, add increasing penalties to particular constraints
Constraint handling
- Stepwise Adaption of Weights penalty (not implemented)
- If best solution violates constraint i, it is a hard constraint so increase the penalty factor.
Measures of performance
- Best fitness of last generation
- Mean fitness of last generation
- Number of duplicate states in last generation
- Mean distance between states
- Number of species
- Number of runs to a solution (not implemented)
Tuning / analysis
- Graph of GA progress + mean progress averaged over multiple runs
- Statistical and graph comparison of two GAs (not implemented)
- ANOVA test - statistical analysis of varying multiple parameters (not implemented)
- Two-tailed t-test
Hyper-parameter tuning
- Meta-GA Multi-objective Optimisations: Sharpening, Racing
- Adaptive mutation and crossover rates
- Multiple crossover and mutation methods with adaptively evolved rates
Extra stuff
- Local search (not implemented)
- Choice between minimisation and maximisation
- 1/(1 + f(x))
Multiobjective optimisation (not implemented)
Approaches:
- Assign fitness based on # members dominated + fitness sharing
- Repeatedly take the pareto front and assign fitness based on iteration found
- MOEA-D
Example problems
- Target string evolution
- Knapsack
- Ackley function
- Griewank function
- Rastrigin function
- Travelling salesperson (not implemented)
- Shortest path (not implemented)
Findings
Stochastic Universal Selection vs Roulette Wheel Selection: On 'hello world': RWS:
- worse #runs avg and distribution to convergence
- worse mean fitness
- fewer duplicates
Dependencies
~13MB
~246K SLoC