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