SMILE — Genetic Algorithm User Guide

This guide explains how to use the smile.gap package for genetic algorithms in SMILE.

Overview

smile.gap provides:

• Chromosome<T>: the contract for candidate solutions.
• LamarckianChromosome<T>: chromosome with optional local-search steps.
• GeneticAlgorithm<T>: the evolution engine.
• BitString: built-in binary chromosome implementation.
• Selection: parent-selection strategies.
• Crossover: crossover strategies for BitString.
• Fitness<T>: fitness scoring contract (used by BitString).

The framework assumes higher fitness is better.

Core Concepts

Chromosome

A chromosome must implement:

• fitness(): returns quality score.
• newInstance(): creates a random chromosome.
• crossover(T other): creates two children.
• mutate(): applies mutation.
• compareTo(...): orders by fitness (ascending for internal sorting).

Fitness

For BitString, fitness is typically provided via Fitness<BitString>:

• double score(BitString chromosome)

Selection

Available selection strategies:

• Selection.RouletteWheel()
• Selection.ScaledRouletteWheel()
• Selection.Rank()
• Selection.Tournament(size, probability) (default choice in many scenarios)

Crossover (BitString only)

Available crossover types:

• Crossover.SINGLE_POINT
• Crossover.TWO_POINT
• Crossover.UNIFORM

Quick Start (BitString)

import smile.gap.*;

public class GapQuickStart {
    static class OnesFitness implements Fitness<BitString> {
        @Override
        public double score(BitString chromosome) {
            int sum = 0;
            for (byte bit : chromosome.bits()) {
                sum += bit;
            }
            return sum;
        }
    }

    public static void main(String[] args) {
        int populationSize = 100;
        int chromosomeLength = 64;

        BitString[] seeds = new BitString[populationSize];
        Fitness<BitString> fitness = new OnesFitness();
        for (int i = 0; i < populationSize; i++) {
            seeds[i] = new BitString(
                    chromosomeLength,
                    fitness,
                    Crossover.TWO_POINT,
                    0.9,   // crossover rate
                    0.01   // mutation rate
            );
        }

        GeneticAlgorithm<BitString> ga = new GeneticAlgorithm<>(
                seeds,
                Selection.Tournament(3, 0.95),
                1 // elitism
        );

        BitString best = ga.evolve(200, chromosomeLength);
        System.out.println("Best fitness: " + best.fitness());
        System.out.println("Best chromosome: " + best);
    }
}

Using Your Own Chromosome Type

If BitString is not suitable, implement Chromosome<T> directly.

Checklist:

• Make fitness() deterministic for a fixed chromosome state.
• Ensure crossover() returns new child objects.
• Keep mutation and crossover valid for your domain constraints.
• Implement compareTo so better chromosomes compare larger.

Lamarckian Search

If your chromosome supports local improvement, implement LamarckianChromosome<T>.

GeneticAlgorithm can apply local search steps during evaluation:

GeneticAlgorithm<MyChromosome> ga = new GeneticAlgorithm<>(seeds);
ga.setLocalSearchSteps(5);  // 0 disables local search
MyChromosome best = ga.evolve(500);

Constructor and Runtime Constraints

• Population size must be greater than 1. In general, larger populations provide better diversity but increase runtime. We recommend starting with 50 to 200 individuals. A common rule is to set the population size to 1.5 to 2 times the number of genes (variables) in a chromosome.
• elitism must satisfy: 0 <= elitism < population.length.
• generation in evolve(...) must be greater than 0.
• setLocalSearchSteps(t) requires t >= 0.
• BitString requires valid rates in [0, 1].

Choosing Parameters

Reasonable defaults to start with:

• Selection: Tournament(3, 0.95)
• Crossover rate: 0.8 - 0.95
• Mutation rate: 0.005 - 0.02
• Elitism: 1 - 2
• Population size: 50 - 200 (problem dependent)

Tune these based on convergence speed and solution quality.

Stopping Criteria

Use one or both:

• Fixed generations: evolve(maxGenerations)
• Fitness threshold: evolve(maxGenerations, threshold)

The second form stops early if the threshold is reached.

Logging

GeneticAlgorithm logs per-generation fitness statistics (best and average). This is useful for tracking convergence and diagnosing stagnation.

Common Pitfalls

• Returning shared parent instances from custom crossover() instead of new children.
• Mutating chromosomes without invalidating cached fitness in custom implementations.
• Using fitness values with poor scaling (can reduce selection pressure).
• Very low mutation leading to premature convergence.
• Very high mutation turning search into near-random walk.

Testing Recommendations

When adding a custom chromosome, test:

• Constructor preconditions.
• crossover() shape and invariants.
• mutate() behavior under fixed RNG seeds.
• fitness() consistency/caching behavior.
• End-to-end convergence on a small synthetic objective.

SMILE — © 2010-2026 Haifeng Li. GNU GPL licensed.