Genetic learning Algorithms

Genetic and Paralising Algorithms

Genetic Algorithms: 

Genetic algorithms are a type of machine learning that uses a population-based search algorithm inspired by the process of natural selection to solve optimization problems. 

Topics in Genetic Algorithm

• Motivation

• Genetic algorithms 

• hypothesis space search

• genetic programming

• models of evolution and learning

• parallelizing genetic algorithms 

Motivation

Natural selection and genetics serve as the inspiration for the family of optimization algorithms known as genetic algorithms (GAs). They are used to find the optimal solution to a given optimization problem, which can be a global or local optimum.

The motivation behind using GAs is that they can handle a large search space and non-linear optimization problems. They are also useful when the objective function is expensive to evaluate or when there is no known mathematical expression for the objective function.

Genetic algorithms

Algorithm:

• Initialization: Provide a random beginning population of potential solutions.

• Evaluation: Evaluate each candidate solution in the population using the objective function.

• Selection: Select the best-performing candidate solutions (parents) from the population based on their fitness scores.

• Crossover: Create new candidate solutions (offspring) by combining the genetic material of the selected parents using the crossover. 

• Mutation: Introduce random changes in the genetic material of the offspring to maintain diversity in the population.

• Evaluation: Evaluate the fitness of the offspring. 

• Selection: Select the best-performing candidate solutions from the population, including the parents and offspring

• Repeat steps 4-7 for a fixed number of iterations or until a stopping criterion is met (e.g., the solution quality converges).

Python code example that implements a genetic algorithm for optimizing a simple function:

import random 

# Define the objective function to be optimized

def objective_function(x):

    return x ** 2

# Define the size of the population and the number of iterations

population_size = 10

num_iterations = 100

# Generate an initial population of candidate solutions

population = [random.uniform(-10, 10) for i in range(population_size)]

# Main loop of the genetic algorithm

for i in range(num_iterations):

    # Evaluate the fitness of each candidate's solution

    fitness_scores = [objective_function(x) for x in population]

    # Select the best-performing candidate solutions (parents)

    parents = sorted(zip(population, fitness_scores), key=lambda x: x[1])[:int(population_size/2)]

    # Create new candidate solutions (offspring) by combining the genetic material of the parents using crossover

    offspring = []

    for j in range(int(population_size/2)):

        parent1, _ = random.choice(parents)

        parent2, _ = random.choice(parents)

        offspring.append((parent1 + parent2) / 2)

    # Introduce random changes in the genetic material of the offspring to maintain diversity

    offspring = [x + random.gauss(0, 1) for x in offspring]

    # Evaluate the fitness of the offspring

    offspring_fitness_scores = [objective_function(x) for x in offspring]

    # Select the best-performing candidate solutions from the parents and offspring

    population = [x for x, _ in sorted(parents + list(zip(offspring, offspring_fitness_scores)), key=lambda x: x[1])[:population_size]]

# Print the best solution found by the genetic algorithm

best_solution = sorted(zip(population, fitness_scores), key=lambda x: x[1])[0][0]

print(f"The best solution found is x = {best_solution}, with a fitness of {objective_function(best_solution)}")

In this example, the genetic algorithm optimizes the function f(x) = x^2 over the range [-10, 10]. The algorithm generates an initial population of 10 candidate solutions randomly and iteratively evolves the population by selecting the best-performing candidates, creating new candidate solutions using crossover and mutation, and evaluating the fitness of the offspring. The algorithm stops after 100 iterations or when the solution quality converges. In the end, the best solution found by the genetic algorithm is printed.

One illustrative example of using genetic algorithms is the travelling salesman problem. Finding the quickest route that makes exactly one stop at each of a specified set of cities before returning to the beginning city is the task at hand. This problem is NP-hard, which means that it is computationally intractable for large problem sizes.

Genetic algorithms can be used to find a good solution to this problem. In this case, each candidate solution (also known as an individual) in the population represents a possible tour of the cities. The genetic material of the individual is the order in which the cities are visited. The fitness of the individual is the length of the tour.

The steps of the genetic algorithm for the travelling salesman problem are similar to the general algorithm described earlier. The main difference is that the crossover and mutation operators need to be modified to ensure that the offspring are valid tours of the cities.

Bayesian belief networks (BBNs) are a type of probabilistic graphical model that represents the joint probability distribution over a set of random variables using a directed acyclic graph. BBNs are useful for modelling complex systems with uncertain relationships between variables.

The EM algorithm is a widely used algorithm for learning the parameters of a BBN from data. The algorithm iteratively estimates the hidden variables of the model using the observed data and the current estimates of the parameters. The algorithm stops when the estimates converge to a stable value.

In conclusion, genetic algorithms are a powerful optimization technique that can be used to find the optimal solution to a wide range of problems. BBNs and the EM algorithm are useful for modelling complex systems with uncertain relationships between variables and for learning the parameters of the model from data.

Hypothesis space search

In genetic algorithms, the search for the optimal solution is done by exploring a hypothesis space, which is the set of all possible solutions to the problem at hand. The algorithm maintains a population of candidate solutions, each represented as a string of genetic material or "chromosome". The fitness of each candidate solution is evaluated using an objective function, which measures how well the solution solves the problem.

Genetic Programming

Genetic programming is a variant of genetic algorithms that uses a population of computer programs instead of fixed-length strings of genetic material. The programs are represented as trees, where the leaves are variables and the internal nodes are operators or functions. The fitness of each program is evaluated by running it on a set of inputs and comparing its output to the expected output.

Models of Evolution and Learning,

Several models of evolution and learning can be used in genetic algorithms, such as the Darwinian model, the Lamarckian model, and the Baldwinian model. In the Darwinian model, individuals with higher fitness are more likely to survive and reproduce, leading to the evolution of fitter individuals over time. In the Lamarckian model, individuals can pass on acquired traits to their offspring, leading to faster evolution. In the Baldwinian model, learning occurs during an individual's lifetime, which can influence the evolution of the species over generations.

Parallelizing genetic algorithms

Parallelizing genetic algorithms can improve their performance by running multiple populations in parallel and exchanging genetic material between them. This can help explore the hypothesis space more efficiently and overcome local optima. However, parallelization introduces additional challenges, such as communication overhead and load balancing. Different parallelization strategies can be used, such as island models, cellular models, and distributed models.

Overall, genetic algorithms are a powerful optimization technique that can be used to search through large and complex hypothesis spaces. Genetic programming extends this approach to evolve computer programs. Different models of evolution and learning can be used, and parallelization can improve the performance of the algorithm.

Previous (Computational learning)

                                                            Continue to (Learning Set of Rules)