Genetic Algorithm Engine

knapsack.py

from __future__ import division

import numpy as np
import sys
from operator import methodcaller
from Engine import Engine

# data from https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html
capacity = 6404180
weights = [382745, 799601, 909247, 729069, 467902, 44328, 34610, 698150, 823460,\
            903959, 853665, 551830, 610856, 670702, 488960, 951111, 323046, 446298, \
            931161, 31385, 496951, 264724, 224916, 169684]
values = [825594, 1677009, 1676628, 1523970, 943972, 97426, 69666, 1296457, 1679693, \
        1902996, 1844992, 1049289, 1252836, 1319836, 953277, 2067538, 675367, \
         853655, 1826027, 65731, 901489, 577243, 466257, 369261]
optimal_solution = ['1','1','0','1','1','1','0','0','0','1','1','0','1','0','0','1','0','0','0','0','0','1','1','1']
optimal_value = np.sum(np.asarray(map(int, optimal_solution)) * np.asarray(values))
item_count = len(optimal_solution)

def encode_genes(genes):
    return np.asarray(map(float, genes))

def fitness(encoded_genes):
    total_value = np.dot(encoded_genes, values)
    total_weight = np.dot(encoded_genes, weights)
    if capacity < total_weight:
        return capacity - total_weight
    return total_value

def main():
    genes_alphabet = ['0', '1']
    mutation_probability = 0.075
    population_size = item_count*10
    num_genes = item_count
    iterations = 2000
    checkpoints = 100

    engine = Engine(genes_alphabet,
                encode_genes,
                population_size,
                num_genes,
                fitness,
                mutation_probability,
                iterations,
                checkpoints)

    solution, best_fitness = engine.run()
    answer = (solution == optimal_solution)
    print('Optimal value: {}'.format(optimal_value))
    print('Found optimal solution? {}'.format(answer))
    print('Difference between optimal value and best fitness: {}'.format(optimal_value - best_fitness))
    print('Saving best solution found...')
    np.savetxt('best_fitness.txt', encode_genes(solution), fmt='%d')

if __name__ == '__main__':
    main()