- Asked 4/12
- 2069 Poush · 10 marks
- 2070 Bhadra · 6 marks
- 2074 Bhadra · 4+4 marks
- 2075 Baisakh · 8 marks
Genetic algorithm and operators
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.
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.
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)
+-------------------------------+
| 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
- Initialisation: generate a random population of N chromosomes.
- Fitness evaluation: compute the fitness of each.
- Selection: choose parents with probability proportional to fitness (roulette wheel, tournament, rank).
- Crossover: combine two parents to make offspring.
- Mutation: randomly flip genes with a small probability.
- 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).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Machine learning, GA, operators, areas · Artificial Intelligence, chapter 6 · asked 2×
- GA vs fuzzy based learning · Artificial Intelligence, chapter 6
- Short note: Genetic algorithm · Data Mining, chapter 3
- Crossover and mutation in GA · Data Mining, chapter 3
- Frequency counter operation with block diagram · Digital Logic, chapter 11 · asked 14×
- Block diagram of digital communication system · Data Communication, chapter 1 · asked 8×