Solving Knapsack Problem with JAYA Algorithm

JAYA algorithm was invented by RV Rao (2016) for solving continuous problems. In this blog we try to apply JAYA to knapsack problem which is a standard combinatorial problem.

Problem formulation

max value sum : sum(v_i*x_i)

s.t.

Total weight < max weight = w_i*x_i

MATLAB CODE

% Simple Knapsack solved by Binary JAYA

clc; clear; rng(1);



% Problem data

values  = [60 100 120 80 30];   % item values

weights = [10 20 30 40 15];     % item weights

Wmax    = 50;                   % capacity

n = length(values);



% JAYA parameters

pop_size = 20; 

max_iter = 100;



% Initialize population (binary solutions)

pop = randi([0 1], pop_size, n);



% Fitness function with penalty

fitness = @(x) sum(values.*x) - 1e3*max(0, sum(weights.*x)-Wmax);



% Evaluate initial fitness

fit_vals = arrayfun(@(i) fitness(pop(i,:)), 1:pop_size);



for iter = 1:max_iter

    [best_val, ibest] = max(fit_vals);

    [worst_val, iworst] = min(fit_vals);

    Xbest = pop(ibest,:);

    Xworst = pop(iworst,:);

    

    for i = 1:pop_size

        Xi = pop(i,:);

        Xnew = zeros(1,n);

        for j = 1:n

            % JAYA update in continuous space

            r1 = rand; r2 = rand;

            cont = Xi(j) + r1*(Xbest(j)-abs(Xi(j))) - r2*(Xworst(j)-abs(Xi(j)));

            

            % Map to binary with sigmoid

            p = 1/(1+exp(-cont));

            Xnew(j) = rand < p;

        end

        

        % Evaluate new solution

        fnew = fitness(Xnew);

        

        % Accept if improved

        if fnew > fit_vals(i)

            pop(i,:) = Xnew;

            fit_vals(i) = fnew;

        end

    end

end



% Final result

[best_val, ibest] = max(fit_vals);

best_sol = pop(ibest,:);



fprintf('Best value = %d\n', best_val);

fprintf('Selected items = '); disp(find(best_sol));