Machine learning, GA, operators, areas

Machine learning

Machine learning is the field of AI in which a system improves its performance on a task from experience (data), without being explicitly programmed for every case. Types: supervised, unsupervised and reinforcement learning.

Genetic algorithm

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

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

Example: maximise f(x) = x² for x in 0..31 (5-bit strings)

Initial population (N = 4):

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).

Areas where GA can be applied

• Optimisation problems: function optimisation, scheduling and timetabling, travelling salesman problem.
• Machine learning: evolving neural-network weights and structure, feature selection, rule learning.
• Engineering design: circuit layout, antenna and structural design.
• Robotics and path planning, game playing.
• Image processing and pattern recognition; data mining.
• Finance (portfolio optimisation) and bioinformatics.