Define chromosome, selection, fitness function, cross over and mutation as used in Genetic Algorithm.

A genetic algorithm (GA) is a search/optimisation method based on natural evolution: a population of candidate solutions (chromosomes) is improved over generations by selection, crossover and mutation, guided by a fitness function.

Definitions

• Chromosome: an encoded candidate solution, usually a string of bits, numbers or characters; each position is a gene. Example: \(x = 13\) encoded as 01101.
• Fitness function: a function that measures how good a chromosome is. Example: to maximise \(f(x) = x^2\), the chromosome 01101 (\(x = 13\)) has fitness 169.
• Selection: choosing parents for reproduction, with fitter chromosomes more likely to be chosen. Methods: roulette-wheel (probability \(= f_i/\sum f\)), tournament, rank selection; elitism copies the best directly to the next generation.
• Crossover: combining two parents to create offspring by exchanging parts. Single-point example, cut after bit 4:
  01101 × 11000 → 01100 and 11001.
  Other types: two-point, uniform crossover. Applied with crossover probability \(p_c\) (often 0.6–0.9).
• Mutation: randomly changing a gene with small probability \(p_m\) (e.g. 0.01), e.g. 01100 → 01110 by flipping bit 4. It keeps diversity and helps escape local optima.

Working of a genetic algorithm

1. Encode the problem and initialise a random population of \(N\) chromosomes.
2. Evaluate the fitness of each chromosome.
3. Select parents according to fitness.
4. Apply crossover to produce offspring.
5. Apply mutation to the offspring.
6. Replace the old population with the new one (possibly keeping the best by elitism).
7. Repeat steps 2–6 until a stopping condition: a fixed number of generations, a satisfactory fitness, or no improvement.

Applications: scheduling and timetabling, travelling salesman problem, neural network weight/hyperparameter tuning, feature selection, design optimisation.