Day 24: Combining Genetic Algorithms with Hill Climbing: The Hybrid Memetic Approach

• Chris Woodruff
• August 13, 2025
• Genetic Algorithms
• .NET, ai, C#, dotnet, genetic algorithms, programming
• 0 Comments

Traditional genetic algorithms (GAs) excel at global exploration across large search spaces. However, they can struggle to fine-tune solutions with high precision due to their stochastic nature. On the other hand, local search techniques like hill climbing are good at refining individual solutions but easily get trapped in local optima. A memetic algorithm combines both approaches, using GAs for exploration and local search for exploitation. This hybrid strategy has proven effective in complex optimization problems where both breadth and depth of search are required.

In this post, you will learn how to implement a simple memetic algorithm in C# by augmenting a GA with a hill-climbing step applied to each generation’s best individuals.

Why Hybridize?

GAs alone might find “good enough” regions of the solution space, but can leave solutions partially optimized. By adding hill climbing:

• You guide elite individuals to higher precision
• You improve convergence speed
• You reduce the number of generations needed for refinement

This approach is particularly valuable in scheduling, layout optimization, and parameter tuning problems.

Chromosome Design

Let’s define a chromosome as we did in earlier posts. We’ll use a simple binary representation for clarity.

public class Chromosome
{
    public int[] Genes { get; set; }
    public double Fitness { get; set; }

    public static Chromosome Random(int length, Random rand)
    {
        return new Chromosome
        {
            Genes = Enumerable.Range(0, length).Select(_ => rand.Next(2)).ToArray()
        };
    }

    public void Evaluate()
    {
        Fitness = Genes.Sum(); // Simple objective: maximize 1s
    }

    public Chromosome Clone()
    {
        return new Chromosome
        {
            Genes = (int[])Genes.Clone(),
            Fitness = Fitness
        };
    }
}

Hill Climbing Implementation

We now define a simple local search method that flips each gene and keeps the change if it improves fitness.

public static Chromosome HillClimb(Chromosome chromosome)
{
    var current = chromosome.Clone();
    current.Evaluate();

    for (int i = 0; i < current.Genes.Length; i++)
    {
        var neighbor = current.Clone();
        neighbor.Genes[i] = 1 - neighbor.Genes[i]; // Flip the gene
        neighbor.Evaluate();

        if (neighbor.Fitness > current.Fitness)
        {
            current = neighbor;
        }
    }

    return current;
}

Incorporating Hill Climbing in the GA Cycle

The memetic algorithm applies hill climbing to the best individuals in each generation.

public static void RunMemeticGA(int geneLength, int populationSize, int generations, double mutationRate)
{
    var rand = new Random();
    var population = Enumerable.Range(0, populationSize)
        .Select(_ => Chromosome.Random(geneLength, rand))
        .ToList();

    for (int gen = 0; gen < generations; gen++)
    {
        foreach (var individual in population)
            individual.Evaluate();

        population = population.OrderByDescending(c => c.Fitness).ToList();

        // Apply hill climbing to top N individuals
        int eliteCount = Math.Min(5, population.Count);
        for (int i = 0; i < eliteCount; i++)
            population[i] = HillClimb(population[i]);

        var nextGen = new List<Chromosome> { population[0] }; // Elitism

        while (nextGen.Count < populationSize)
        {
            var parent1 = Tournament(population, rand);
            var parent2 = Tournament(population, rand);
            var child = Crossover(parent1, parent2, rand);
            Mutate(child, mutationRate, rand);
            child.Evaluate();
            nextGen.Add(child);
        }

        population = nextGen;
        Console.WriteLine($"Generation {gen + 1}: Best Fitness = {population[0].Fitness}");
    }
}

Helper Methods

public static Chromosome Tournament(List<Chromosome> pop, Random rand, int size = 3)
{
    return pop.OrderBy(_ => rand.Next())
              .Take(size)
              .OrderByDescending(c => c.Fitness)
              .First();
}

public static Chromosome Crossover(Chromosome a, Chromosome b, Random rand)
{
    var genes = new int[a.Genes.Length];
    for (int i = 0; i < genes.Length; i++)
        genes[i] = rand.NextDouble() < 0.5 ? a.Genes[i] : b.Genes[i];

    return new Chromosome { Genes = genes };
}

public static void Mutate(Chromosome c, double rate, Random rand)
{
    for (int i = 0; i < c.Genes.Length; i++)
    {
        if (rand.NextDouble() < rate)
            c.Genes[i] = 1 - c.Genes[i];
    }
}

Conclusion

The memetic algorithm is a powerful hybrid strategy that brings together the global search strength of genetic algorithms with the precision of local search. In problems where refinement is just as important as exploration, this approach offers a clear performance boost.

In the next post, we will examine how to scale GA execution using multithreading and parallel execution strategies in .NET.

You can find the code demos for the GA series at https://github.com/cwoodruff/genetic-algorithms-blog-series

This site uses Akismet to reduce spam. Learn how your comment data is processed.