Learn Problem Solving Informed Search Algorithms

Problem Solving - Hill Climbing and Genetic Algorithm

Informed Search Algorithms : Hill-Climbing and Generic

2.3 Hill Climbing Search:

Hill Climbing Search is an informed search algorithm that always chooses the neighbour that appears to be closest to the goal node according to the heuristic function. Here's how Hill Climbing Search works step-by-step:

• Evaluate the current state using the heuristic function h(n).

• If the current state is the goal state, return it.

• Otherwise, generate the neighbour states of the current state.

• Evaluate each neighbour state using the heuristic function h(n).

• If any neighbour state has a lower h-value than the current state, choose the neighbour state with the lowest h-value and repeat from step 2.

• If no neighbour state has a lower h-value than the current state, return failure.

Here's an example of using Hill Climbing Search to find a path from node A to node G in the graph above:

Hill Climbing Search would start at node A and evaluate its heuristic function h(A) = 10. It would choose node B as its neighbour since h(B) = 9, which is lower than h(C) = 8 and h(D) = 7. It would then evaluate h(B) = 9 and choose node C as its neighbour since h(C) = 6, which is lower than h(D) = 7. Furthermore, it would then evaluate h(C) = 6 and choose node E as its neighbour since h(E) = 4, which is lower than h(F) = 5. It would then evaluate h(E) = 4 and choose node G as its neighbour, since h(G) = 0. It would find the goal node G with a cost of 14.

Here's the Python code for Hill Climbing Search:

Python code

def hill_climbing(graph, start, goal, heuristic):
current = start
while current != goal:
neighbors = graph[current]
next_node = None
min_h = float('inf')
for a neighbour in neighbours:
h = heuristic(neighbor, goal)
if h < min_h:
next_node = neighbor
min_h = h
if min_h >= heuristic(current, goal):
return None
current = next_node
return [start, current, goal]

I hope this helps you understand these informed search

4. Local Search (Simulated Annealing, Genetic Algorithm) 

4.1 Simulated Annealing:

Simulated Annealing is a metaheuristic optimization algorithm that can be used to solve optimization problems where the solution space is too large or too complex to be searched exhaustively. It is based on the physical process of annealing, where a metal is heated and then slowly cooled to reduce its defects and improve its strength. The algorithm starts with an initial solution and then iteratively explores the solution space by making random moves. It accepts moves that improve the objective function value and occasionally accepts moves that worsen the objective function value, to avoid getting trapped in local optima.

Here's how Simulated Annealing works step-by-step:

Initialize the current state x and the temperature T.

Repeat until the stopping criterion is met:

Generate a new state x' by making a small random change to x.

If f(x') > f(x), accept x' as the new current state.

Otherwise, calculate the probability of accepting x's as the new current state using the Boltzmann distribution: P = e^(-ΔE/T), where ΔE = f(x') - f(x).

Create a random number, r, in the range of 0 and 1.

If r < P, except x' as the new current state.

Decrease the temperature T according to a cooling schedule.

Here's an example of using Simulated Annealing to find the global minimum of the function f(x) = x^2 - 2x + 1:

Initialize the current state x = 0 and the temperature T = 1.

Repeat until the stopping criterion is met:

Generate a new state x' by adding a random number between -0.1 and 0.1 to x.

If f(x') < f(x), accept x' as the new current state.

Otherwise, calculate the probability of accepting x' using the Boltzmann distribution: P = e^(-(f(x') - f(x))/T).

Create a random number, r, in the range of 0 and 1.

If r < P, except x' as the new current state.

Decrease the temperature T according to a cooling schedule (e.g., T = T * 0.99).

Here's the Python code for Simulated Annealing:

python code

import random

import math

def simulated_annealing(f, x0, T0, cooling_schedule):  

x = x0

T = T0

while T > 0:

x_prime = x + random.uniform(-0.1, 0.1)

delta_E = f(x_prime) - f(x)

if delta_E < 0:

x = x_prime

else:

p = math.exp(-delta_E/T)

r = random.uniform(0, 1)

if r < p:

x = x_prime

T = cooling_schedule(T)

return x

4.2  Genetic Algorithm:

Genetic Algorithm is another metaheuristic optimization algorithm that can be used to solve optimization problems where the solution space is too large or too complex to be searched exhaustively. It is inspired by the process of natural selection and evolution and operates by evolving a population of candidate solutions over multiple generations. Each candidate solution is represented as a string of genes, and the algorithm applies genetic operators such as mutation and crossover to create new candidate solutions. The fitness of each candidate solution is evaluated based on its objective function value, and the best solutions are selected for the next generation.

Here's how Genetic Algorithm works step-by-step:

Initialize a population of candidate solutions randomly.

Evaluate the fitness of each candidate solution based on its objective function value.

Repeat until the stopping criterion is met:

Select a subset of the population to be parents for the next generation, using a selection method, such as roulette wheel selection or tournament selection.

Create a new generation of candidate solutions by applying genetic operators such as mutation and crossover to the selected parents.

Evaluate the fitness of each new candidate solution based on its objective function value.

Replace the old population with the new population, using a replacement method such as elitism or generational replacement.

Here's an example of using a Genetic Algorithm to find the global minimum of the function f(x) = x^2 - 2x + 1:

1. Initialize a population of 100 candidate solutions randomly, represented as binary strings of length 10.

2. Evaluate the fitness of each candidate solution by converting its binary string to a decimal number and evaluating f(x).

3.   Continue until the halting condition is satisfied:

a. Select a subset of the population to be parents for the next generation, using a roulette wheel selection based on fitness.

b. Create a new generation of candidate solutions by applying genetic operators such as mutation and single-point crossover to the selected parents.

c. Evaluate the fitness of each new candidate solution by converting its binary string to a decimal number and evaluating f(x).

d. Replace the old population with the new population, using generational replacement.

e. If a solution with a fitness of 0 is found, stop and return it as the optimal solution.

Another example:

Here's an example of using a Genetic Algorithm to find the global minimum of the function f(x) = x^2 - 2x + 1:

1. Initialize a population of 10 candidate solutions randomly, represented as strings of binary digits: 010010, 101101, 110011, 001100, 111000, 000111, 010101, 101010, 111111, 000000.

2. Evaluate the fitness of each candidate solution by converting its binary string to a decimal number and calculating f(x).

3.  Continue until the halting condition is satisfied:

a. Select the best candidate solutions for the next generation based on their fitness: 010010, 001100, 000111, 000000.

b. Apply genetic operators (mutation and crossover) to create new candidate solutions: 010010 -> 010011 (mutation), 001100 -> 001111 (mutation), 000111 -> 000110 (mutation), 000000 -> 110011 (crossover with 010101).

c. Evaluate the fitness of each new candidate solution.

d. Replace the current population with the new population of candidate solutions.

Here's the Python code for Genetic Algorithm:

python code

import random

def genetic_algorithm(f, n, m, k, p_mut, p_cross):

    # n: population size

    # m: number of genes per candidate solution

    # k: number of selected candidates for reproduction

    # p_mut: the probability of mutation

    # p_cross: the probability of crossover

    # initialize the population randomly

    population = [[random.randint(0, 1) for _ in range(m)] for _ in range(n)]

    # Repeat until the stopping criterion is met

    while True:

        # evaluate the fitness of each candidate's solution

        fitness = [f(candidate) for candidate in population]

        # select the best candidate solutions for reproduction

        selected_indices = sorted(range(n), key=lambda i: fitness[i])[:k]

        selected_population = [population[i] for I in selected_indices]

        # create new candidate solutions by applying genetic operators

        new_population = selected_population[:]

        while len(new_population) < n:

    parent1, parent2 = random.choices(selected_population, k=2)

            if random.random() < p_cross:

                child1 = parent1[:m//2] + parent2[m//2:]

                child2 = parent2[:m//2] + parent1[m//2:]

            else:

                child1, child2 = parent1[:], parent2[:]

            if random.random() < p_mut:

                gene_index = random.randint(0, m-1)

                child1[gene_index] = 1 - child1[gene_index]

                child2[gene_index] = 1 - child2[gene_index]

            new_population.append(child1)

            new_population.append(child2)

        # check the stopping criterion

        if f(selected_population[0]) == f(new_population[0]):

            break

        # update the population

        population = new_population[:n]

    return selected_population[0]

To Problem-Solving Uninformed Search                                

                                                   Continue  (Knowledge Representation)