--- title: "Genetic algorithm and operators" subject: "Artificial Intelligence" chapter: 6 key: "semester_6/artificial_intelligence:genetic-algorithm-operators" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/genetic-algorithm-operators site: BCT Engineering --- # Genetic algorithm and operators Artificial Intelligence · Chapter 6: Machine Learning - Asked in: 2069 Poush, 10 marks; 2070 Bhadra, 6 marks; 2074 Bhadra, 4+4 marks; 2075 Baisakh, 8 marks (asked 4 times) - Video: [Genetic Algorithms Explained By Example](https://www.youtube.com/watch?v=uQj5UNhCPuo) — Kie Codes - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/genetic-algorithm-operators - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-6 ## Question What is a genetic algorithm (GA)? Explain all the steps in the genetic algorithm with block diagram and its operators (with importance), with an example. ## Short answer A genetic algorithm (GA) evolves a population of encoded solutions via selection (fitter chosen), crossover (swap parts), and mutation (random flip). Steps: initial random population, evaluate fitness, then iterate selection, crossover, mutation to form new generation. For f(x)=x², initial average fitness 292.5 improved to 438.5 after one generation. ## Answer A **genetic algorithm (GA)** is a search and optimisation technique based on natural selection and genetics (John Holland). It evolves a population of candidate solutions (chromosomes) over generations; fitter individuals are more likely to survive and reproduce, so the population improves towards an optimum. #### Terms - **Chromosome / individual:** one encoded solution (e.g. a bit string 01101). - **Gene:** one position in the chromosome. - **Population:** the set of chromosomes. - **Fitness function:** measures how good a solution is. #### Steps (block diagram) ```text +-------------------------------+ | 1. Initial random population | +---------------+---------------+ | v +-------------------------------+ | 2. Evaluate fitness |<-------------+ +---------------+---------------+ | | | v | < Stop condition? >--No--+ | | | | Yes v | | +--------------------+ | | | 3. Selection | | | | 4. Crossover | | | | 5. Mutation | | | | 6. New generation |--+ | +--------------------+ v Best solution ``` 1. **Initialisation:** generate a random population of N chromosomes. 2. **Fitness evaluation:** compute the fitness of each. 3. **Selection:** choose parents with probability proportional to fitness (roulette wheel, tournament, rank). 4. **Crossover:** combine two parents to make offspring. 5. **Mutation:** randomly flip genes with a small probability. 6. **Replacement:** form the new generation; repeat from step 2 until the stop condition (fixed number of generations, target fitness, or no improvement). #### Genetic operators and their importance | Operator | Action | Importance | |---|---|---| | Selection (reproduction) | Copies fitter strings more often | Pushes the population towards better solutions | | Crossover | Swaps parts of two parents at a crossover point, e.g. 01/101 x 11/000 (cut at /) gives 01000 and 11101 | Mixes good building blocks; explores new combinations | | Mutation | Flips a bit with probability about 0.001-0.01, e.g. 11000 gives 11010 | Maintains diversity; prevents premature convergence and recovers lost genes | #### Example: maximise f(x) = x² for x in 0..31 (5-bit strings) Initial population (N = 4): | String | x | f(x) | Probability | Expected copies | |---|---|---|---|---| | 01101 | 13 | 169 | 0.144 | 0.58 | | 11000 | 24 | 576 | 0.492 | 1.97 | | 01000 | 8 | 64 | 0.055 | 0.22 | | 10011 | 19 | 361 | 0.309 | 1.23 | | Sum / average | | 1170 / 292.5 | | | Selection gives 01101, 11000, 11000, 10011. Crossover of 01101 x 11000 after bit 4 gives 01100 (12) and 11001 (25); crossover of 11000 x 10011 after bit 2 gives 11011 (27) and 10000 (16). New fitness: 144, 625, 729, 256; sum 1754, average **438.5** (up from 292.5), best 729 (up from 576). Repeating the cycle moves the population towards 11111 (x = 31, f = 961). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the basic idea of a genetic algorithm? A. Search one solution by repeatedly moving downhill B. Derive facts by firing rules C. Evolve a population of solutions where fitter ones are more likely to survive and reproduce D. Fit a straight line to data Answer: C. GA (Holland) applies natural selection to a population of chromosomes. (Key point: GA basis) 2. Which is the correct order of GA steps? A. Initialise, evaluate fitness, select, crossover, mutate, replace, repeat B. Initialise, crossover, select, evaluate, mutate C. Select, initialise, mutate, evaluate, crossover D. Evaluate, mutate, initialise, crossover, select Answer: A. After creating a random population, each generation is evaluated, then selection, crossover and mutation produce the next one. (Key point: Step order) 3. Why is mutation used? A. It copies the fittest strings more often B. It maintains diversity, prevents premature convergence and recovers lost genes C. It swaps parts of two parents to mix building blocks D. It evaluates fitness of strings Answer: B. Mutation flips bits with a small probability; selection and crossover are different operators. (Key point: Mutation importance) 4. In the x^2 example, how does the population change after selection and crossover? A. Average fitness falls from 438.5 to 292.5 B. Average rises to 961 C. Best stays at 576 D. Average fitness rises from 292.5 to 438.5 and best from 576 to 729 Answer: D. New strings give fitness 144, 625, 729, 256 (sum 1754, average 438.5), moving towards 11111 = 31. (Key point: Example result) ## Related in Artificial Intelligence - [Machine learning, GA, operators, areas](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aml-genetic-algorithm-operators-areas) — Artificial Intelligence, chapter 6, asked 2× - [GA vs fuzzy based learning](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aga-vs-fuzzy-learning) — Artificial Intelligence, chapter 6 ## Related in other subjects - [Short note: Genetic algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Agenetic-algorithm-note) — Data Mining, chapter 3 - [Crossover and mutation in GA](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Acrossover-mutation-ga) — Data Mining, chapter 3 - [Frequency counter operation with block diagram](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Afrequency-counter) — Digital Logic, chapter 11, asked 14× - [Block diagram of digital communication system](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ablock-diagram-digital-comm) — Data Communication, chapter 1, asked 8×