Write code to solve the following 0-1 Knapsack problem

Given a knapsack of items N and capacity W. The volume and value of the item is c(i) and w(i) respectively. Find the maximum total value in the knapsack. Suppose that N=10, and V=300. The volume of each item is 95, 75, 23, 73, 50, 22, 6, 57, 89 and 98. The values of each item are 89, 59, 19, 43, 100, 72, 44, 16, 7 and 64.

[Jiri Hajek]

Hi, hint: c(i)/w(i) is the volumetric value density of an item.

[Chihiro Ogino]

Can you check this code? I was having problem while renaming c(i) and w(i) , something like array issue. so I kept it as value and volume

clear all;
 
clc;
 
value = [95, 75, 23, 73, 50, 22, 6, 57, 89, 98];
 
volume = [89, 59, 19, 43, 100, 72, 44, 16, 7, 64];
 
V = 300; % given volume capacity
 
N = 10; % given items
 
value2volume = value./volume; % finding the value-to-volume ratio
 
v2v_descend = sort(value2volume,2,"descend");% descending order of value to volume ratio
 
 
 
indi = zeros(1,N);
 
 
 
% finding the indices locations (as per descending order of value-to-volume ratio)
 
 
for i=1:1:N
    indi(i) = find(value2volume == v2v_descend(i));
 
 
end
 
% Re-arranging the volume array(as per descending order of value-to-volume ratio)
volume_order = volume(indi);
 
% Re-arranging the value array(as per descending order of value-to-volume ratio)
value_order = value(indi);
 
 
vol=0;
val=0;
count=1;
 
while(vol<=V && count <=N)
 
     vol=vol+volume_order(count);
     val=val +value_order(count);
     count=count +1;
end
 
val %Optimal value

val = 560

items = count-1 %number of items

items = 8

 
figure
plot(value2volume,v2v_descend)
xlabel('volume');
ylabel('value');
title('fitness evolution')

[Jiri Hajek]

Seems almost ok, with the exception of the figure, which does not make sense, if your labels should be valid. Also the indexing can be done directly using output of sort:

clear all;
clc;
 
value = [95, 75, 23, 73, 50, 22, 6, 57, 89, 98];
 
volume = [89, 59, 19, 43, 100, 72, 44, 16, 7, 64];
 
V = 300; % given volume capacity
 
N = 10; % given items
 
value2volume = value./volume; % finding the value-to-volume ratio
 
[v2v_descend,sortOrder] = sort(value2volume,2,"descend");% descending order of value to volume ratio
 
% Re-arranging the volume array(as per descending order of value-to-volume ratio)
volume_order = volume(sortOrder);
 
% Re-arranging the value array(as per descending order of value-to-volume ratio)
value_order = value(sortOrder);
  
vol=0;
val=0;
count=1;

while(vol<=V && count <=N)
 
     vol=vol+volume_order(count);
     val=val +value_order(count);
     count=count +1;
end
 
val %Optimal value

val = 560

items = count-1 %number of items

items = 8

 
cumValues = cumsum(value_order);
cumVolumess = cumsum(volume_order);

figure
plot(cumVolumess,cumValues)
xlabel('volume');
ylabel('value');
title('fitness evolution')

[Chihiro Ogino]

Copy that, much thanks

[Torsten]

@Chihiro Ogino

I think you interchanged volume and value in your code. Further, your result does not seem correct according to "intlinprog".

f = -[89, 59, 19, 43, 100, 72, 44, 16, 7, 64];
A = [95, 75, 23, 73, 50, 22, 6, 57, 89, 98];
b = 300;
lb = zeros(1,10);
ub = ones(1,10);
intcon = 1:10;
x = intlinprog(f,intcon,A,b,[],[],lb,ub)

LP:                Optimal objective value is -401.938776.                                          

Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is -383.000000.                                                      
                   Relative gap is 1.30%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

x = 10×1

1 0 1 0 1 1 1 0 0 1

value = -f*x

value = 388

volume = A*x

volume = 294

[Chihiro Ogino]

I just noticed the mismatch that I did. Bless you

[Chihiro Ogino]

Any suggestion on how do I apply BPSO algorithm in this same code?

Answer 1

[Amith]

Hi Chihiro,

Below is a basic implementation of Binary Particle Swarm Optimization (BPSO) algorithm to solve the 0-1 knapsack problem in MATLAB.

function bpso_knapsack
    % Parameters
    num_particles = 30;
    num_iterations = 100;
    num_items = 10;
    w = 0.5; % Inertia weight
    c1 = 2; % Cognitive (particle) weight
    c2 = 2; % Social (swarm) weight
    max_weight = 50;
    
    % Generate random weights and values for the items
    weights = randi([1, 15], 1, num_items);
    values = randi([10, 100], 1, num_items);
    
    % Initialize particles
    particles = randi([0, 1], num_particles, num_items);
    velocities = rand(num_particles, num_items);
    personal_best_positions = particles;
    personal_best_values = zeros(num_particles, 1);
    
    for i = 1:num_particles
        personal_best_values(i) = fitness(particles(i, :), weights, values, max_weight);
    end
    
    [global_best_value, idx] = max(personal_best_values);
    global_best_position = personal_best_positions(idx, :);
    
    % Store best values for plotting
    best_values = zeros(num_iterations, 1);
    
    % Main loop
    for iter = 1:num_iterations
        for i = 1:num_particles
            % Update velocity
            velocities(i, :) = w * velocities(i, :) + ...
                               c1 * rand * (personal_best_positions(i, :) - particles(i, :)) + ...
                               c2 * rand * (global_best_position - particles(i, :));
                           
            % Update position
            particles(i, :) = sigmoid(velocities(i, :)) > rand(1, num_items);
            
            % Calculate fitness
            current_value = fitness(particles(i, :), weights, values, max_weight);
            
            % Update personal best
            if current_value > personal_best_values(i)
                personal_best_positions(i, :) = particles(i, :);
                personal_best_values(i) = current_value;
            end
        end
        
        % Update global best
        [current_best_value, idx] = max(personal_best_values);
        if current_best_value > global_best_value
            global_best_value = current_best_value;
            global_best_position = personal_best_positions(idx, :);
        end
        
        % Store best value for plotting
        best_values(iter) = global_best_value;
        
        % Display iteration and best value
        fprintf('Iteration %d: Best Value = %d\n', iter, global_best_value);
    end
    
    % Final result
    fprintf('Optimal solution found: \n');
    disp(global_best_position);
    fprintf('Maximum value: %d\n', global_best_value);
    
    % Plot the best values over iterations
    figure;
    plot(1:num_iterations, best_values, 'LineWidth', 2);
    xlabel('Iteration');
    ylabel('Best Value');
    title('BPSO Optimization Progress');
    grid on;
end

function value = fitness(particle, weights, values, max_weight)
    total_weight = sum(particle .* weights);
    if total_weight > max_weight
        value = 0;
    else
        value = sum(particle .* values);
    end
end

function s = sigmoid(x)
    s = 1 ./ (1 + exp(-x));
end

Explanation:

1. Parameters:

• num_particles: Number of particles in the swarm.
• num_iterations: Number of iterations to run the algorithm.
• num_items: Number of items in the knapsack problem.
• w, c1, c2: Parameters for the PSO algorithm (inertia weight, cognitive weight, social weight).
• max_weight: Maximum weight capacity of the knapsack.

1. Initialization:

• Randomly generate weights and values for the items.
• Initialize particles and velocities.
• Determine the personal best positions and values for each particle.
• Determine the global best position and value.

1. Main Loop:

• Update velocities and positions of particles.
• Calculate the fitness of each particle.
• Update personal and global bests based on fitness values.

1. Fitness Function:

• Calculates the total value of the items in the knapsack if the total weight does not exceed the maximum weight.

1. Sigmoid Function:

• Used to map velocities to probabilities for binary decision making.

This code provides a basic framework for BPSO applied to the 0-1 Knapsack problem. You can further optimize the parameters and enhance the algorithm based on specific needs and problem constraints.

And the plot generated from the above code looks something like this:

Hope this helps!