Chapter 7: Genetic Algorithms to Constraint Satisfaction Problems presents about What is a Genetic Algorithm? Components of GA; How does GA work? Constraint Handling in Gas; GA for 8-Queens Problems; GA for Exam Timetabling Problem; Memetic Algorithms. | Chapter 7 Genetic Algorithms to Constraint Satisfaction Problems Outline What is a Genetic Algorithm? Components of GA How does GA work? Constraint Handling in Gas GA for 8-Queens Problems GA for Exam Timetabling Problem Memetic Algorithms Genetic algorithm is a population-based search method. Genetic algorithms are acknowledged as good solvers for tough problems. However, no standard GA takes constraints into account. This chapter describes how genetic algorithms can be used for solving constraint satisfaction problems. What is a Genetic Algorithm? The general scheme of a GA: begin INITIALIZE population with random candidate solutions; EVALUATE each candidate; repeat SELECT parents; RECOMBINE pairs of parents; MUTATE the resulting children; EVALUATE children; SELECT individuals for the next generation until TERMINATION-CONDITION is satisfied end The general scheme of Genetic Algorithm Parents Children Population Initialization Termination Recombination Mutation . | Chapter 7 Genetic Algorithms to Constraint Satisfaction Problems Outline What is a Genetic Algorithm? Components of GA How does GA work? Constraint Handling in Gas GA for 8-Queens Problems GA for Exam Timetabling Problem Memetic Algorithms Genetic algorithm is a population-based search method. Genetic algorithms are acknowledged as good solvers for tough problems. However, no standard GA takes constraints into account. This chapter describes how genetic algorithms can be used for solving constraint satisfaction problems. What is a Genetic Algorithm? The general scheme of a GA: begin INITIALIZE population with random candidate solutions; EVALUATE each candidate; repeat SELECT parents; RECOMBINE pairs of parents; MUTATE the resulting children; EVALUATE children; SELECT individuals for the next generation until TERMINATION-CONDITION is satisfied end The general scheme of Genetic Algorithm Parents Children Population Initialization Termination Recombination Mutation Parent selection Survivor selection The general scheme of Genetic Algorithm (cont.) It’s clear that this scheme falls in the category of generate-and-test algorithms. The evaluation function represents a heuristic estimation of solution quality and the search process is driven by the variation and the selection operator. GA has a number of features: GA is population-based GA uses recombination to mix information of candidate solutions into a new one. GA is stochastic. COMPONENTS OF GENETIC ALGORITHMS The most important components in a GA consist of: representation (definition of individuals) evaluation function (or fitness function) population parent selection mechanism variation operators (crossover and mutation) survivor selection mechanism (replacement) Representation Objects forming possible solutions within original problem context are called phenotypes, their encoding, the individuals within the GA, are called genotypes. The representation step specifies the mapping .
