Implementation:Haifengl Smile BitString

Knowledge Sources	Haifengl_Smile
Domains	Genetic Algorithms, Optimization, Evolutionary Computation
Last Updated	2026-02-08 22:00 GMT

Overview

BitString is the standard binary string chromosome representation used within the Smile genetic algorithm package to encode candidate solutions for optimization problems.

Description

The BitString class implements the Chromosome<BitString> interface using a binary (0/1) byte-array encoding. Each chromosome maintains its own crossover strategy, crossover rate, mutation rate, and a reference to a fitness function. The class supports the full genetic algorithm lifecycle: random initialization, fitness evaluation (with lazy caching), crossover with a configurable strategy, and bit-flip mutation.

Key design characteristics:

• Binary encoding -- solutions are represented as arrays of bytes where each byte is 0 or 1.
• Lazy fitness evaluation -- the fitness score is computed on first access and cached (initialized to Double.NaN).
• Configurable crossover -- delegates crossover to the Crossover enum, which supports single-point, two-point, and uniform crossover.
• Bit-flip mutation -- each bit is independently flipped with probability equal to the mutation rate.
• Factory pattern -- newInstance() creates a fresh random chromosome with the same parameters, and newInstance(byte[]) creates a chromosome with specific bits.

Recommended parameter ranges from the literature:

• Crossover rate: 60% to 95% (default 90%)
• Mutation rate: 0.5% to 1% (default 1%)

Usage

Use BitString when you need to represent candidate solutions as binary strings in a genetic algorithm. It is the primary chromosome type supplied with the smile.gap package and is intended for use with the GeneticAlgorithm class.

Code Reference

Source Location

• Repository: Haifengl_Smile
• File: base/src/main/java/smile/gap/BitString.java
• Lines: 1-217

Signature

public class BitString implements Chromosome<BitString> {

    // Constructors
    public BitString(int length, Fitness<BitString> measure);
    public BitString(int length, Fitness<BitString> measure, Crossover crossover,
                     double crossoverRate, double mutationRate);
    public BitString(byte[] bits, Fitness<BitString> measure);
    public BitString(byte[] bits, Fitness<BitString> fitness, Crossover crossover,
                     double crossoverRate, double mutationRate);

    // Accessors
    public int length();
    public byte[] bits();

    // Chromosome interface
    public double fitness();
    public BitString newInstance();
    public BitString newInstance(byte[] bits);
    public BitString[] crossover(BitString mother);
    public void mutate();

    public int compareTo(Chromosome o);
    public String toString();
}

Import

import smile.gap.BitString;

I/O Contract

Inputs

Name	Type	Required	Description
length	int	Yes (constructor variant)	The number of bits in the chromosome. Must be positive.
bits	byte[]	Yes (constructor variant)	Explicit bit values (each 0 or 1) for the chromosome.
measure / fitness	Fitness<BitString>	Yes	The fitness function used to evaluate the chromosome.
crossover	Crossover	No (default TWO_POINT)	The crossover strategy to use (SINGLE_POINT, TWO_POINT, or UNIFORM).
crossoverRate	double	No (default 0.9)	Probability of performing crossover (0.0 to 1.0).
mutationRate	double	No (default 0.01)	Probability of flipping each bit during mutation (0.0 to 1.0).

Outputs

Name	Type	Description
fitness()	double	The fitness score of this chromosome, computed via the fitness function.
bits()	byte[]	The raw binary encoding of the chromosome.
length()	int	The number of bits in the chromosome.
crossover()	BitString[]	An array of two offspring produced by crossover with another parent.
newInstance()	BitString	A new randomly initialized chromosome with the same parameters.

Usage Examples

Basic Usage

import smile.gap.BitString;
import smile.gap.Fitness;
import smile.gap.GeneticAlgorithm;

// Define a fitness function that counts the number of 1-bits
Fitness<BitString> oneMax = chromosome -> {
    byte[] bits = chromosome.bits();
    int count = 0;
    for (byte b : bits) count += b;
    return count;
};

// Create an initial population of 50 bit strings, each 100 bits long
BitString[] population = new BitString[50];
for (int i = 0; i < population.length; i++) {
    population[i] = new BitString(100, oneMax);
}

// Run the genetic algorithm for 200 generations
GeneticAlgorithm<BitString> ga = new GeneticAlgorithm<>(population);
BitString best = ga.evolve(200);
System.out.println("Best fitness: " + best.fitness());
System.out.println("Best solution: " + best);

Custom Crossover and Mutation

import smile.gap.BitString;
import smile.gap.Crossover;
import smile.gap.Fitness;

Fitness<BitString> fitness = chromosome -> {
    // Custom fitness evaluation
    byte[] bits = chromosome.bits();
    double score = 0;
    for (int i = 0; i < bits.length - 1; i++) {
        score += (bits[i] != bits[i + 1]) ? 1 : 0;
    }
    return score;
};

// Use uniform crossover with 80% crossover rate and 0.5% mutation rate
BitString chromosome = new BitString(64, fitness, Crossover.UNIFORM, 0.8, 0.005);

Related Pages

• Implementation:Haifengl_Smile_Chromosome
• Implementation:Haifengl_Smile_Crossover
• Implementation:Haifengl_Smile_GeneticAlgorithm
• Implementation:Haifengl_Smile_GA_Parent_Selection