/ 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. x: _gtime _t y: ((x[1]) ! 1003) _draw 300 / 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] x: * 1 _draw 0 if[x > crossoverprob :(c1;c2) ] 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 fitness 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 if[(#choices) > sqchromos choices@: !sqchromos ] / now do crossover crosses: ,/(!#choices) ,/:\: (!#choices) crosses@: & ~ crosses[;0] = crosses[;1] crossindexes: !#crosses / let there be replacment ceil:{[x] :[x = _ x; :x; 1 + _ x]} crossindexes@: ! _ ceil[numchromos % 2] x: ,/crossover'choices[crosses[crossindexes]] / now do mutations x: mutation[;mutationprob]'x newchromos,: x if[(1 + (#chromos)) < #newchromos newchromos@: ! 1 + (#chromos) ] :newchromos } spit:{[list] (-1) _ ,/(\$list) ,\: (" ")} / DATA / knapsack parameters numitems: 1000 maxweight: 50 maxval: 300 knapcap: _ (numitems * maxweight) % 4 values: numitems _draw maxval weights: 1 + numitems _draw maxweight "tmp" 0: spit' weights,'values knapcap