Solving NP-Hard Problems with Genetic Algorithms in Elixir

Genetic algorithms, inspired by the process of natural selection, are powerful optimization techniques. They can efficiently tackle NP-hard problems like the N-Queens puzzle. This blog post will demonstrate how Elixir, a functional and concurrent language, can be used to implement a genetic algorithm to solve this challenging problem efficiently.

The N-Queens Problem

The N-Queens puzzle involves placing N chess queens on an N×N chessboard in a way that no two queens threaten each other. Solving it requires finding a configuration where no queens are in a position to attack each other. Genetic algorithms provide an elegant approach to this combinatorial problem.

Elixir’s Strengths for Genetic Algorithms

Elixir’s unique features make it an ideal choice for implementing genetic algorithms:

- Functional: Elixir’s functional paradigm aligns well with the mathematical nature of genetic algorithms.
- Concurrent: Elixir’s lightweight processes allow for parallel execution, speeding up the optimization process.

Photo by THAVIS 3D on Unsplash

Genetic Algorithm Components

1. Population Initialization

We begin with a population of random chessboard configurations, each representing a possible solution.

# Population Initialization
defp initialize_population(population_size, board_size) do
 Enum.map(1..population_size, fn _ ->
 Enum.shuffle(1..board_size)
 end)
end

2. Fitness Calculation

A fitness function evaluates the quality of each configuration based on the number of non-attacking queens.

# Fitness Calculation
defp calculate_fitness(state) when is_list(state) do
 queens_attacking = count_attacking_queens(state, 0)
 fitness_score = (board_size * (board_size - 1)) / 2 - queens_attacking
 {state, fitness_score}
end

3. Selection

The best configurations are selected as parents for the next generation. Elixir’s concurrency can be harnessed for efficient selection.

# Selection
defp select_parents(population, num_parents) do
 # Sort the population by fitness score and select the top-performing ones
 sorted_population = Enum.sort_by(population, &elem(&1, 1), :desc)
 top_parents = Enum.take(sorted_population, num_parents)
end

4. Crossover

Crossover combines genetic material from two parents to create offspring. In the N-Queens problem, a one-point crossover is used.

# Crossover
defp crossover(parent1, parent2) when is_list(parent1) and is_list(parent2) do
 {crossover_point, _} = :rand.uniform(board_size)
 child1 = take(parent1, crossover_point) ++ drop(parent2, crossover_point)
 child2 = take(parent2, crossover_point) ++ drop(parent1, crossover_point)
 {child1, child2}
end

5. Mutation

Some offspring undergo random changes (mutations) to introduce diversity.

# Mutation
defp mutate(state) when is_list(state) do
 mutated_state = for {row, col} <- state do
 if should_mutate?(), do: {random_row(), col}, else: {row, col}
 end
 mutated_state
end

6. Evolution

Over successive generations, the population evolves towards an optimal solution. This process continues until a satisfactory solution is found.

# Evolution
defp evolve_population(population, generation, max_generations) when generation >= max_generations do
 Enum.min_by(population, &calculate_fitness/1)
end

Elixir Implementation

In our Elixir implementation, we create multiple modules to handle different aspects of the genetic algorithm. These modules work together harmoniously to evolve solutions over generations efficiently.

Photo by Roman Synkevych on Unsplash

If you further like to explore, check out my repo:

@ b0a04gl/np-hard-solver-elixir (github.com)

Conclusion

Genetic algorithms, when paired with Elixir’s functional and concurrent capabilities, form a potent tool for solving NP-hard problems such as the N-Queens puzzle. Elixir’s concurrency allows for parallel execution, speeding up the optimization process.

The application of genetic algorithms extends beyond chessboard puzzles to real-world optimization challenges. This combination of genetic algorithms and Elixir is a robust approach for tackling complex, computationally intensive problems.

Yep, done for the post… 👋👋