Skip to main content

Genetic Algorithm

use when need sth stochastic (randomn) alt text alt text

Knapsack problem using GA​

Facts​

  • Each fact is a full solution to the problem alt text → each fact represents as a tuple, each bit in this tuple indicates whether that item is picked or not such that total weight < Capacity

example​

alt text

Extension rules​

Extension rules create new solutions from some subset of solutions alt text

Mutation​

single point mutation alt text

  • critic: only one bit changes each time → slow alt text

Crossover​

for each bit choose either from A or B alt text

  • critic: can end up with the same one or go over Capacity alt text

Search Control​

alt text

Search Instance​

alt text