Genetic Algorithms Explained: Solving the TSP with AForge.NET

Evolutionary Background

Genetic Algorithm (GA) is a heuristic search method inspired by Darwinian evolution. It models a population of candidate solutions that evolve through selection, crossover, and mutation.

Population : a set of individuals that evolve together.

Individual : a single candidate solution.

Gene : the smallest unit of information.

Chromosome : an ordered collection of genes representing a solution.

Survival of the fittest : individuals with higher fitness have a greater chance to reproduce.

Genetic variation : offspring inherit genes from both parents and may undergo random mutations.

Genetic Algorithm Concept

GA treats problem solving as an evolutionary process. In each generation the population is evaluated, the fittest individuals are selected, and genetic operators generate a new set of offspring. After a predefined number of generations the remaining individuals are expected to have high fitness.

Example – 0‑1 Knapsack : encode a solution as a binary string, generate a random initial population, evaluate fitness (total value subject to weight limit), select parents proportionally, apply crossover and mutation, and repeat for G generations to obtain an approximate optimal solution.

Core GA Operators

Selection – Roulette‑Wheel (proportionate) selection

int RouletteWheelSelect(double[] P) {
    double r = Random(0, 1); // random number in [0,1]
    double cumulative = 0;
    for (int i = 0; i < P.Length; i++) {
        cumulative += P[i];
        if (r <= cumulative) return i;
    }
    return -1; // should never reach here
}

Crossover : with probability Pc exchange a segment between two parent chromosomes.

Before Crossover:
00000|011100000000|10000
11100|000001111110|00101

After Crossover (single‑point at the vertical bar):
00000|000001111110|10000
11100|011100000000|00101

Mutation : with probability Pm flip a randomly chosen gene.

Before Mutation:
0000011100000<strong>0</strong>0010000

After Mutation:
0000011100000<strong>1</strong>0010000

Fitness Function : evaluates each chromosome; typically derived from the problem’s objective function but may be transformed to improve guidance.

Basic GA Pseudocode

Initialize parameters: Pc (crossover prob), Pm (mutation prob), M (population size), G (max generations), Tf (fitness threshold)
Generate initial population Pop
repeat
    Compute fitness F(i) for each individual in Pop
    newPop = empty
    while newPop.Size < M
        parent1 = RouletteWheelSelect(Pop)
        parent2 = RouletteWheelSelect(Pop)
        if Random(0,1) < Pc then
            offspring1, offspring2 = Crossover(parent1, parent2)
        else
            offspring1 = parent1; offspring2 = parent2
        end if
        if Random(0,1) < Pm then
            offspring1 = Mutate(offspring1)
            offspring2 = Mutate(offspring2)
        end if
        Add offspring1 and offspring2 to newPop
    end while
    Pop = newPop
until (any chromosome fitness > Tf) or (generation >= G)

GA Optimizations

Elitist strategy : copy the best individual unchanged to the next generation to avoid losing the current optimum.

Insertion operator : move a random chromosome segment to another position, providing a fourth variation operator beyond selection, crossover, and mutation.

Solving the Traveling Salesman Problem with AForge.Genetic

AForge.NET is an open‑source C# framework that includes a genetic‑algorithm library ( AForge.Genetic.dll). The following steps show how to build a TSP solver for a dataset of 31 Chinese provincial capitals.

Download the AForge.NET binaries (e.g., from http://code.google.com/p/aforge/downloads/list) and reference AForge.dll and AForge.Genetic.dll in a C# project.

Place the city coordinate file Data.txt (one line per city) in the project’s bin/Debug folder.

Implement a fitness‑function class that implements IFitnessFunction. The function computes the total tour length of a chromosome (a permutation of city indices) and returns the inverse (or a scaled value) so that shorter tours have higher fitness.

Create a main program that:

Instantiates a PermutationChromosome with the number of cities.

Creates a Population object, sets PopulationSize, CrossoverProbability (Pc), and MutationProbability (Pm).

Assigns the custom fitness function to the population.

Runs the evolution loop using population.RunEpoch() for a fixed number of generations or until a fitness threshold is reached.

Outputs the best tour and its total length.

Running the program on the 31‑city dataset yields a best tour length of approximately 15402 , close to the known optimum of 15404 . Increasing the population size to 1000 and iterating 5000 generations improves the result to about 15408.5 .

Full source code (C#) is available at:

http://files.cnblogs.com/heaad/GenticTSPcode.rar

Typical workflow with AForge.Genetic

Define a class that implements IFitnessFunction and computes the TSP tour length.

Choose GA parameters (population size, selection method, crossover and mutation probabilities) and create a Population instance.

Execute the evolutionary loop with RunEpoch until a stopping condition (max generations or fitness threshold) is met.