Hill Climbing

Hill Climbing is the most simple implementation of a Genetic Algorithm. It completely gets rid of the concepts like population and crossover, instead focusing on the ease of implementation. It has faster iterations compared to more traditional genetic algorithms, but in return it is less thorough.

How does Hill Climbing work?

Hill Climbing works in a very simple way. We can actually show it in a step-by-step list.

1. Start with an empty or random solution. This is called our best solution.
2. Make a copy of the solution and mutate it slightly.
3. Evaluate the new solution. If it’s better than the best solution, we replace the best solution with this one.
4. Go to step two and repeat.

So basically to evolve a solution to a problem, you need to write three functions.

1. Create a random solution
2. Evaluate a solution and return a score
3. Mutate a solution in a random way

What are the pitfalls of the Hill Climbing algorithm?

Unless you modify the algorithm, a Hill Climber can only move to better solutions. While this sounds good, it means that the algorithm is prone to getting stuck in local minima.

A simple solution that tends to works well for this problem is the Simulated Annealing algorithm.

Example Project (Hello World)

Even though it is not a challenging problem, hello world is still a good introduction. First of all, let’s write the basic outline of the hill climbing algorithm.

best = generate_random_solution()
best_score = evaluate_solution(best)

while True:
    print('Best score so far', best_score, 'Solution', best)
    new_solution = copy_solution(best)
    mutate_solution(new_solution)

    score = evaluate(new_solution)
    if evaluate(new_solution) < best_score:
        best = new_solution
        best_score = score

Let’s implement the functions to make this skeleton work.

Generate Random Solution

This function needs to return a random solution. In a hill climbing algorithm making this a seperate function might be too much abstraction, but if you want to change the structure of your code to a population-based genetic algorithm it will be helpful.

def generate_random_solution(length=11):
    return [random.choice(string.printable) for _ in range(length)]

Evaluating a Solution

The target of our algorithm is producing the string “Hello, World!”. So our evaluation function is going to return a distance metric between two strings. Here is a simple way to do it. The function below will return the absolute difference of our solution to the target.

def evaluate(solution):
    target = "Hello, World!".split("")
    diff = 0
    for i in range(len(target)):
        s = solution[i]
        t = target[i]
        diff += abs(ord(s) - ord(t))
    return diff

Mutating a Solution

In genetic algorithms, mutating a solution means randomly changing it in a small way. In the context of our project, this means changing one of the letters randomly.

def mutate_solution(solution):
    index = random.randint(0, len(solution) - 1)
    solution[index] = random.choice(string.printable)

Tying it all together

One last thing we need before our code is ready is the copy function, but our solution is just a list of characters which is easily copied in Python. Let’s get the code in a state that is ready to run.

import random
import string

def generate_random_solution(length=13):
    return [random.choice(string.printable) for _ in range(length)]

def evaluate(solution):
    target = list("Hello, World!")
    diff = 0
    for i in range(len(target)):
        s = solution[i]
        t = target[i]
        diff += abs(ord(s) - ord(t))
    return diff

def mutate_solution(solution):
    index = random.randint(0, len(solution) - 1)
    solution[index] = random.choice(string.printable)

best = generate_random_solution()
best_score = evaluate(best)

while True:
    print('Best score so far', best_score, 'Solution', "".join(best))

    if best_score == 0:
        break

    new_solution = list(best)
    mutate_solution(new_solution)

    score = evaluate(new_solution)
    if evaluate(new_solution) < best_score:
        best = new_solution
        best_score = score

Testing the code

If you run the code above, you should be greeted with the following output.

Best score so far 392 Solution #KAKZ'yjrJo/5
Best score so far 392 Solution #KAKZ'yjrJo/5
Best score so far 390 Solution #KAKZ/yjrJo/5
Best score so far 347 Solution #KAKZ/yjrJon5
...
Best score so far 27 Solution Jojon,"\osld
...
Best score so far 12 Solution H_mmn, Vosld
...
Best score so far 4 Solution Hemmo, Vorld
...
Best score so far 0 Solution Hello, World!