## Wednesday, 6 September 2017

### Knapsack problem using simulated annealing

The knapsack problem ( Wiki link ) is a problem in combinatorial optimisation. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Let's see how we can solve it using simulated annealing.

### A Basic Understanding

Suppose we are planning a hiking trip; and we are, therefore, interested in filling a knapsack with items that are considered necessary for the trip. There are N different item types that are deemed desirable; these could include bottle of water, apple, orange, sandwich, and so forth. Each item type has a given set of two attributes, namely a weight (or volume) and a value that quantifies the level of importance associated with each unit of that type of item. Since the knapsack has a limited weight (or volume) capacity, the problem of interest is to figure out how to load the knapsack with a combination of units of the specified types of items that yields the greatest total value. What we have just described is called the knapsack problem.

Implementation

knapsack.js
```/**
* Will hold each knapsack item
*/
function Item(w,v,index){
this.weight = w; //Weight of the item
this.value = v;  //Weight of the value
this.index = index; //Index of the value
this.print = function(){
document.write("Item : w : "+this.weight+", v : "+this.value+"<br/>");
}
}

/**
* Knapsack bag
*/
function Bag(size){

this.size = size;
this.itemset = []; //Will hold the overall dataset
this.currentSolution = []; //will hold the current solution

/**
* Populates the itemset with the dataset provided above
*/
this.prepare = function(){
for(var i = 0;i<dataset.length;i++){
var item = new Item(dataset[i],dataset[i],i);
this.itemset.push(item);
}
var temp = getRandomAsInt(0,this.itemset.length);
this.currentSolution.push(this.getItemBasedOnIndex(this.itemset, temp));
}

/**
* Gets the items from the itemset provided as an argument based on the index
*/
this.getItemBasedOnIndex = function(itemset,index){
var item = null;
for(var i=0;i<itemset.length;i++){
if(itemset[i].index==index){
item = itemset[i];
break;
}
}
return item;
}

/**
* Calculates and returns the summation of list of item weights
*/
this.getWeightForList = function(itemset){
var sum = 0;
for(var i=0;i<itemset.length;i++){
sum += itemset[i].weight;
}
return sum;
}

/**
* Calculates and returns the summation of list of item values
*/
this.getValueForList = function(itemset){
var sum = 0;
for(var i=0;i<itemset.length;i++){
sum += itemset[i].value;
}
return sum;
}

/**
* Checks whether current selection is overweight or not
*/
this.checkoverweight = function(itemset){
if(this.getWeightForList(itemset) > this.size){
return true;
}else
return false;
}

/**
* Returns any random item from the itemset which is not in the currentSolution of the bag
*/
this.getRandomItemFromItemSet = function(){
var temp = getRandomAsInt(0,this.itemset.length);
var item  = this.getItemBasedOnIndex(this.itemset,temp);
while(this.getItemBasedOnIndex(this.currentSolution,temp)!=null){
temp = getRandomAsInt(0,this.itemset.length);
item  = this.getItemBasedOnIndex(this.itemset,temp);
}
return item;
}

/**
* Modifies the current selection
*/
this.modifySelection = function(){
var modified = this.currentSolution.clone();
var item = this.getRandomItemFromItemSet();
modified.push(item);
while(this.checkoverweight(modified)){
var dropIndex = getRandomAsInt(0,modified.length);
modified.removeItem(dropIndex);
console.log(dropIndex);
console.log(modified);

}
return modified;
}

/**
* Calculates the remaining space in the bag
*/
this.calculateRemainingSpace = function(itemset){
return (this.size - this.getValueForList(itemset));
}

this.printsolution = function(itemset){
for(var i=0;i<itemset.length;i++){
var item = itemset[i];
item.print();
}
document.write("Total value is : "+this.getValueForList(itemset));
}

this.prepare();
}

/**
* Returns a random number between minimum (inclusive) and maximum (exclusive)
*/
function getRandom(min, max) {
return Math.random() * (max - min) + min;
}

/**
* Returns a random integer between minimum (inclusive) and maximum (exclusive)
*/
function getRandomAsInt(min, max) {
return Math.floor(Math.random() * (max - min)) + min;
}

Array.prototype.clone = function() {
return this.slice(0);
};

Array.prototype.removeItem = function( index){
var i = 0;
while( i < this.length ){
if(i == index ){
this.splice(i,1);
}
i++;
}
};

```

#### index.html

```<script src="knapsack.js"></script>
<script>
/**
* Constants for the program
*/
var MAX_WEIGHT = 15;
var TEMPERATURE = 500;
var COOLING_FACTOR = 0.2;

/**
* The dataset used in the program
* [weight,value]
*/
var dataset = [
[1,2],[4,2],[5,4],[3,6],[9,4],[10,8],[8,5],[6,7],[7,3],[11,8]
];

/** Acceptance function **/
function acceptanceProbability(freespace,newfreespace,temperature){
if(newfreespace < freespace){
return 1.0;
}
return Math.exp((freespace - newfreespace) / temperature);
}

var bag = new Bag(MAX_WEIGHT);
var best = bag.currentSolution;
var temperature = TEMPERATURE;
while(temperature > 0){
var freespaceLeft = bag.calculateRemainingSpace(bag.currentSolution);
var modifiedSolution = bag.modifySelection();
var newfreespaceleft = bag.calculateRemainingSpace(modifiedSolution);
if(acceptanceProbability(freespaceLeft, newfreespaceleft, temperature)>=Math.random()){
bag.currentSolution = modifiedSolution;
}

if(bag.getValueForList(bag.currentSolution) > bag.getValueForList(best)){
best = bag.currentSolution;
}
temperature -= COOLING_FACTOR;
}
bag.printsolution(best);
}
</script>

```

#### 1 comment:

1. How did I find this site? I read a lot of positive reviews about it, of course, there were negative and more positive ones, and I decided to take a chance by clicking on this link modish slot machine games I saw a lot of cool slots and slot machines êàî there so cool I’ve even managed to withdraw my first winnings