Solving the knapsack problem with genetic algorithms.

geneticknapsack.js

let items = [
  {
    name: "laptop",
    weight: 1.5,
    price: 1000,
  },
  {
    name: "speakers",
    weight: 0.5,
    price: 200,
  },
  {
    name: "IPhone",
    weight: 0.7,
    price: 700,
  },
  {
    name: "suit",
    weight: 0.7,
    price: 300,
  },
  {
    name: "watr bottle",
    weight: 0.3,
    price: 50,
  },
  {
    name: "SDR Radio",
    weight: 1.2,
    price: 150,
  },
  {
    name: "textbook",
    weight: 1.1,
    price: 30,
  },
  {
    name: "hard drive",
    weight: 0.75,
    price: 400,
  },
  {
    name: "usb stick",
    weight: 0.2,
    price: 20,
  },
  {
    name: "toothbrush",
    weight: 0.3,
    price: 10,
  },
  {
    name: "gold ring",
    weight: 0.2,
    price: 700,
  },
  {
    name: "Fancy boots",
    weight: 0.8,
    price: 120,
  },
  {
    name: "100$ bill",
    weight: 0.1,
    price: 100,
  },
  {
    name: "lunchbox",
    weight: 0.4,
    price: 40,
  },
  {
    name: "Mechanical keyboard",
    weight: 1.4,
    price: 110,
  },
  {
    name: "lockpicking kit",
    weight: 2,
    price: 600,
  },
];

function generateRandomChromosome() {
  let chromosome = [];
  for (let j = 0; j < 16; j++) {
    chromosome.push(Math.round(Math.random()));
  }

  return chromosome;
}

let population = [];

for (let i = 0; i < 60; i++) {
  population.push(generateRandomChromosome());
}

function shuffleArray(original) {
  let array = [...original];
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  return array;
}

function calculateChromosomeMetadata(chromosome) {
  let totalWeight = 0;
  let totalPrice = 0;
  for (let i = 0; i < chromosome.length; i++) {
    if (chromosome[i] === 1) {
      totalWeight += items[i].weight;
      totalPrice += items[i].price;
    }
  }

  if (totalWeight > 7) {
    totalPrice = 0;
  }

  return {
    weight: totalWeight,
    price: totalPrice,
    chromosome: chromosome,
  };
}

function evaluate(population) {
  population = population.map((chromosome) => {
    return calculateChromosomeMetadata(chromosome);
  });

  // sort chromosomes based on price
  population = population.sort((a, b) => b.price - a.price);

  // get rid of meta data
  return population.map((chromosome) => chromosome.chromosome);
}

function crossover(population) {
  population.length = population.length / 2;
  maxPopulationSize = population.length;
  for (let i = 0; i < maxPopulationSize; i = i + 2) {
    let splitPoint = Math.round(Math.random() * 16);
    let base1 = Array.from(population[i]);
    let base2 = Array.from(population[i + 1]);
    let head1 = base1.slice(0, splitPoint);
    let tail1 = base1.slice(splitPoint, base1.length);
    let head2 = base2.slice(0, splitPoint);
    let tail2 = base2.slice(splitPoint, base1.length);

    population.push([...head1, ...tail2]);
    population.push([...head2, ...tail1]);
  }

  return population;
}

function mutate(chromosome) {
  if (Math.random() < 0.075) {
    return shuffleArray(chromosome);
  } else {
    return chromosome;
  }
}

for (let i = 0; i < 1000; i++) {
  let evaluatedPopulation = evaluate(population);
  let newPopulation = crossover(evaluatedPopulation);
  let mutatedPopulation = newPopulation.map((chromosome) => mutate(chromosome));

  population = evaluate(mutatedPopulation);
}

let bestOfGeneration = calculateChromosomeMetadata(population[0]);

console.log("best possible price: " + bestOfGeneration.price);

test message