Algorithm Examples in K


Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html




Genetic Algorithm for Knapsack


/ Knapsack problem done with a genetic algorithm
/ Given (i) a knapsack with a certain weight capacity
/ (ii) a collection of items having a weight and a value, 
/ find the  items to put  into the knapsack so that you don't
/ exceed its capacity and you get the maximum possible value.

/ Note that the order does not matter, so can encode as a 
/ string in which we indicate whether the item is in or out.

/ It appears that the simulating annealing trick of making mutation
/ probabilities higher at the beginning than later is a good one. 

/ APPLICATION


/ see how fit a chromosome is
/ negative if impossible because too heavy and otherwise get the value.
/ Application dependent
fit:{[c]
	w: +/weights*c	
	if[w > knapcap; :knapcap - w] / more negative if too weighty
	:+/values*c
}

/ crossover two chromosomes and return them
/ Generic crossover for binary encoding, pair is a pair of chromosomes.
crossover:{[pair]
	c1: pair[0]
	c2: pair[1]
	size: #c1
	i: 2 + *1 _draw (size-2)
	newc1: c1[!i],i _ c2
	newc2: c2[!i],i _ c1
	:(newc1; newc2)
}

/ cause a mutation in c with probability prob
/ Generic crossover for binary encoding
mutation:{[c;prob]
	numpos: _ (prob * #c)+0.5
	i: numpos _draw -#c
	c[i]: ~ c[i]
	:c
}

/ generic genetic algorithm
/ mutationprob: 0.1
/ crossoverprob: 0.2
evolve:{[]
  fitvals: fit'chromos
  max: |/fitvals
  imax: fitvals ? max
  bestchromo:: chromos[imax] 
  bestvalue:: fitvals[imax] / assuming the fitness is the value
  newchromos: ,bestchromo / keep this for the future
  choices: chromos _di imax
  fitvals: fitvals _di imax
  / now do selection
  ii: < fitvals
  choices@: ii / order based on fitnesso
  size: #choices
  x1: choices[ ! _ size % 2]
  x2: (_ size % 2) _ choices
  x: x1, x2, x2
  choices: x[size _draw -#x] / twice the prob of getting fitter chromos
  / now do crossover
  crosses: ,/(!#choices) ,/:\: (!#choices)
  crosses@: & ~ crosses[;0] = crosses[;1]
  num: _ (crossoverprob * #crosses) + 0.5
  if[num > (1 + (_ (#choices) % 2)); num: (1 + (_ (#choices) % 2))]
  crossindexes: num _draw -#crosses / let there be replacment
  x: ,/crossover'choices[crosses[crossindexes]]
  / now do mutations
  x: mutation[;mutationprob]'x
  newchromos,: x
  if[1 + (#chromos) < #newchromos
	newchromos@: ! 1 + (#chromos)
  ]
  :newchromos
}


/ DATA

/ knapsack parameters
numitems: 40
maxweight: 50
maxval: 300
knapcap: _ (numitems * maxweight) % 4
values: numitems _draw maxval
weights: 1 + numitems _draw maxweight


/ genetic algorithm parameters
numchromos: 30
bestchromo: numitems # 0
bestvalue: 0
mutationprob: 0.3 / higher seems better. Maybe it should get lower over time.
crossoverprob: 0.2
numgen: 300 / how many generations to try


/ initialize chromos generically
chromos: ()
do[numchromos
  chromos,: ,numitems _draw 2
]



/ EXECUTION

i: 0
origmut: mutationprob
do[numgen+1
  i+: 1
  mutationprob: (((numgen+1) - i) % (numgen+1)) * origmut
  chromos: evolve[chromos]
  / ` 0: ,$bestvalue
]

("Best chromosome: "), ,/$bestchromo
("Best value: "), $bestvalue
("Weight of best: "),$+/weights * bestchromo
("Knapsack capacity: "),$knapcap
("Number of generations: "), $numgen