Sample Genetic Algorithm Rule Generator

This is a basic genetic algorithm based rule generator. The main idea is to begin with an initialized population of rulesets, perform fitness tests on them, then generate a new population using the strongest fitnesses. Of particular note, this generator uses an FI2-population format, meaning that there are two populations: an infeasible population and a feasible population. A chromosome will be assigned to one of the two populations based off the outcome of its feasibility test.

Get First Population: The generator begins by initializing a population of Chromosomes, a type which contains an interaction ruleset, a termination ruleset, and a fitness. The first population is made of a hybrid of 40% randomly generated rulesets, 40% constructively generated rulesets, and 20% constructively generated rulesets that underwent several rounds of random mutation. The fitness of the chromosome is calculated upon initialization.

Rank Selection: The population then undergoes traditional rank selection by fitness.

Evolutionary Loop: Beginning here, the process will continue indefinitely until competition parameter timeout. The current population is subdivided into two populations based on their feasibility, which is calculated inside of the Chromosome Calculate Fitness function. After sorting populations based off fitness, Rank Selection occurs to populate the new generation. Two chromosomes will be selected to parent two child chromosomes, using crossover and mutation. This process repeats until a fully new generation has been created. Then the best chromosome from the last generation is forwarded into the new one. At timeout, the highest ranked chromosome of the last completed generation is returned as the generated ruleset.

Calculate Fitness: Each chromosome has its fitness calculated every generation. Three agents play the game, and fitness is calculated from a combination of their score, win-rate, unique interaction rules triggered, and game length.

Feasibility Test: Each chromosome must be tested for feasibility. A chromosome is feasible if it passes three tests:

1. The ruleset does not generate any errors within the GVGAI engine. Errors are classified as anything that prevents the engine from simulating correctly.
2. A do-nothing agent which makes no moves will survive the first 40 steps (1.6 seconds) of playtime.
3. A random agent, a baseline agent, and a smart agent play the game. The number of bad-frames is totaled throughout the playthroughs. Bad Frames are defined as frames in which game sprites are drawn outside the boundaries of the screen. If > 30% of the frames are bad, this chromosome is infeasible.

Mutation: There are 3 types of mutation, and 2-subtypes for each type. Insertion is subdivided into new parameter insertion and new rule insertion. Deletion is subdivided into parameter deletion and rule deletion. Modification is subdivided into modification of a parameter and modification of a rule. Each chromosome has a 10% chance to mutate.

Crossover: All crossovers are done using simple one-point crossover, ie at a random point in one parent's ruleset, a part will be swapped with a part of the other parent's ruleset.