Discrete Optimisation (N-Queens Problem)

How does ARIEL EC module work?

The ARIEL EC (Evolutionary Computing) module works a bit different than other EAs (Evolutionary Algorithms). While other EAs represent the population as a simple list of individuals, here they the population is made as its own class, with a population being type of list[Individuals].

Similarly, in traditional EA architecture an individual is chosen for certain operators (for example parent selection) according to some criteria, put into a separate list and then given to the operator function. ARIEL works by giving individuals what we call tags. An individual has tags that can be toggled, which qualify it for any and all operations. The tag can be whether an individual can crossover or mutate in the future, but it can also show if it can enter the learning cycle.

The tags can be changed at all times, and default values for each tag can be given to more closely represent a traditional EA structure.

Additionally, ARIEL utilizes an SQL database to handle the variables and outputs of the code. This makes the code run faster, but it adds an extra step to the process.

This file demonstrates the process of initializing an EA class and running it for a simple problem, in our case, the Sphere function.

# Standard library
import random
from typing import Literal, cast

import matplotlib.pyplot as plt

# Third-party libraries
import numpy as np

# Local libraries
from ariel.ec.a001 import Individual
from ariel.ec.a004 import EA, EASettings, EAStep, Population

# Function to show fitness landscape
from fitness_plot import plot_fit_per_gen

# Pretty little errors and progress bars
from rich.console import Console
from rich.traceback import install

Visualisation for N-Queens board

def visualize_solution(solution, fitness) -> None:
    """Visualize the N-Queens solution using matplotlib.

    - Attacking queens are red
    - non-attacking queens are green.
    """
    n = len(solution)

    # --- build checkered background ---
    board = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if (i + j) % 2 == 1:
                board[i, j] = 0.7

    _fig, ax = plt.subplots(figsize=(8, 8))
    ax.imshow(board, cmap="Greys", origin="upper")

    # --- detect which queens are in conflict ---
    attacking = [False] * n
    for r1 in range(n):
        c1 = solution[r1]
        for r2 in range(r1 + 1, n):
            c2 = solution[r2]
            same_col = (c1 == c2)
            same_diag = (abs(r1 - r2) == abs(c1 - c2))
            if same_col or same_diag:
                attacking[r1] = True
                attacking[r2] = True

    # --- draw queens with per-queen color ---
    for row, col in enumerate(solution):
        color = "red" if attacking[row] else "green"
        ax.text(col, row, "♛", fontsize=300 / n, ha="center", va="center", color=color)

    # --- grid / labels ---
    ax.set_xticks(np.arange(n))
    ax.set_yticks(np.arange(n))
    ax.set_xticklabels([""] * n)
    ax.set_yticklabels([""] * n)

    ax.set_xticks(np.arange(-0.5, n, 1), minor=True)
    ax.set_yticks(np.arange(-0.5, n, 1), minor=True)
    ax.grid(which="minor", color="black", linestyle="-", linewidth=2)

    plt.title(f"{n}-Queens Solution - Fitness = {fitness}", fontsize=16, pad=20)
    plt.show()


# Example: A valid 8-Queens solution
example_solution = [4, 2, 0, 6, 1, 7, 5, 2]
visualize_solution(example_solution, "?")

Define fitness function

# Define the fitness function
def evaluate_solution_n_queens(solution):
    """Calculate the fitness of an solution."""
    attacks = 0
    n = len(solution)
    for i in range(n):
        for j in range(i + 1, n):
            if solution[i] == solution[j] or abs(solution[i] - solution[j]) == abs(i - j):
                attacks += 1
                break  # Break out of the loop once an attack is found for the current queen

    # Fitness is equal to number of attacks
    return float(attacks)


def evaluate_ind(ind: Individual) -> float:
    """Evaluate an individual by calculating its fitness using the Ackley function."""
    return evaluate_solution_n_queens(cast("list[float]", ind.genotype))


def evaluate_pop(population: Population) -> Population:
    """Evaluate a population by calculating the fitness of each individual."""
    for ind in population:
        if ind.requires_eval:
            ind.fitness = evaluate_ind(ind)
    return population

Initialize the global constants

# A seed is optional, but it helps with reproducibility
SEED = None  # e.g., 42

# The database has a few handling modes
    # "delete" will delete the existing database
    # "halt" will stop the execution if a database already exists
DB_HANDLING_MODES = Literal["delete", "halt"]

# Initialize RNG
RNG = np.random.default_rng(SEED)

# Initialize rich console and traceback handler
install()
console = Console()

Initialize the EASettings class.

The EASettings class acts as the handles the database and other parameters

# Set config
config = EASettings(
    is_maximisation=False,
    db_handling="delete",
    target_population_size=100,
)

And just like that we have everything we need to get started. Now all we need to do define our evolutionary operators

Keep in mind that all operators in ARIEL have to work with the Individual and Population classes. You could define your own operators from scratch, but using the built in ones is easier.

def create_individual(num_dims) -> Individual:
    ind = Individual()
    ind.genotype = np.random.permutation(num_dims).tolist()
    return ind


def parent_selection(population: Population) -> Population:
    """Tournament Selection."""
    tournament_size: int = 5

    # Ensure all individuals have a tags dict and reset parent-selection tag
    for ind in population:
        if ind.tags is None:
            ind.tags = {}
        ind.tags["ps"] = False

    # Decide how many parents we want (even number)
    num_parents = (len(population) // 2) * 2
    if num_parents == 0 and len(population) >= 2:
        num_parents = 2

    winners = []
    for _ in range(num_parents):
        # sample competitors with replacement
        competitors = [random.choice(population) for _ in range(tournament_size)]

        # pick best competitor depending on maximisation/minimisation
        if config.is_maximisation:
            winner = max(competitors, key=lambda ind: ind.fitness)
        else:
            winner = min(competitors, key=lambda ind: ind.fitness)

        winners.append(winner)

    # mark winners as parents
    for w in winners:
        w.tags["ps"] = True

    return population


def _ox_crossover(p1: list[int], p2: list[int]) -> tuple[list[int], list[int]]:
    """Order Crossover (OX) for permutations."""
    n = len(p1)

    a, b = sorted(np.random.choice(n, size=2, replace=False))
    # ensure non-empty segment; if a==b could never happen due to replace=False
    # but if adjacent is fine (segment length 1)

    def make_child(seg_from, fill_from):
        child = [-1] * n
        # copy segment
        child[a:b] = seg_from[a:b]
        used = set(child[a:b])

        # fill positions starting from b (wrap around), taking genes from fill_from in order
        fill_positions = list(range(b, n)) + list(range(a))
        fill_genes = [g for g in fill_from if g not in used]

        for pos, gene in zip(fill_positions, fill_genes, strict=False):
            child[pos] = gene

        return child

    c1 = make_child(p1, p2)
    c2 = make_child(p2, p1)

    return (c1, c2)


def crossover(population: Population) -> Population:
    """OX (Order) crossover for permutation genotypes."""
    parents = [ind for ind in population if ind.tags.get("ps", False)]
    np.random.default_rng()

    for idx in range(0, len(parents), 2):
        if idx + 1 >= len(parents):
            break  # odd parent out

        parent_i = parents[idx]
        parent_j = parents[idx + 1]

        genotype_i, genotype_j = _ox_crossover(
            cast("list[int]", parent_i.genotype),
            cast("list[int]", parent_j.genotype),
        )
        # First child
        child_i = Individual()
        child_i.genotype = genotype_i
        child_i.tags = {"mut": True}
        child_i.requires_eval = True

        # Second child
        child_j = Individual()
        child_j.genotype = genotype_j
        child_j.tags = {"mut": True}
        child_j.requires_eval = True

        population.extend([child_i, child_j])

    return population


def mutation(population: Population) -> Population:
    for ind in population:
        if ind.tags.get("mut", False):
            genes = cast("list[int]", ind.genotype)
            i, j = np.random.choice(len(genes), size=2, replace=False)
            genes[i], genes[j] = genes[j], genes[i]
            ind.genotype = genes.copy()
    return population


def survivor_selection(population: Population) -> Population:
    tournament_size: int = 5

    # Decide how many parents we want (even number)
    pop_len = len(population)

    for _ in range(config.target_population_size):
        # Sample competitors with replacement
        pop_alive = [ind for ind in population if ind.alive is True]
        death_candidates = [random.choice(pop_alive) for _ in range(tournament_size)]

        # Pick best competitor depending on maximisation/minimisation
        if config.is_maximisation:
            about_to_be_killed_lol = min(death_candidates, key=lambda ind: ind.fitness)
        else:
            about_to_be_killed_lol = max(death_candidates, key=lambda ind: ind.fitness)

        about_to_be_killed_lol.alive = False

        pop_len -= 1
        if pop_len <= config.target_population_size:
            break

    return population

Define evolutionary loop

Now that all our operators are done, we can define the evolutionary loop and run the algorithm

def main(pop_size, num_queens) -> EA:
    """Entry point."""
    # Create initial population
    population_list = [create_individual(num_dims=num_queens) for _ in range(pop_size - 1)]
    population_list = evaluate_pop(population_list)

    # Create EA steps
    ops = [
        EAStep("parent_selection", parent_selection),
        EAStep("crossover", crossover),
        EAStep("mutation", mutation),
        EAStep("evaluation", evaluate_pop),
        EAStep("survivor_selection", survivor_selection),
    ]

    # Initialize EA
    ea = EA(
        population_list,
        operations=ops,
        num_of_generations=100,
    )

    ea.run()

    best = ea.get_solution("best", only_alive=False)
    console.log(f"Best fitness: {best.fitness}")
    visualize_solution(best.genotype, best.fitness)

    return ea

ea = main(pop_size=100,
          num_queens=16)

[22:40:43] Database file exists at d:\University\EC TA\ariel\docs\source\EA_intro\__data__\database.db! a004.py:105
           Behaviour is set to: 'delete' --> ⚠️  Deleting file!                                                     

───────────────────────────────────────────────── EA Initialised ──────────────────────────────────────────────────

─────────────────────────────────────────────── EA Finished Running ───────────────────────────────────────────────

[22:41:02] Best fitness: 1.0                                                                         85475682.py:26

plot_fit_per_gen()