The 0/1 Knapsack problem is a classic combinatorial optimization challenge. Given a set of items, each with a specific weight $w_i$ and value $v_i$, the goal is to determine wich items to include in a collection so that the total weight does not exceed a predefined limit $W$, while the total value is maximized. This is mathematically expressed as:

$$\text{Maximize } \sum_{i=1}^{n} v_i x_i$$ $$\text{Subject to } \sum_{i=1}^{n} w_i x_i \le W, \text{ where } x_i \in {0, 1}$$

Genetic Algorithms (GA) provide an effective heuristic approach to finding near-optimal solutions by simulating natural selection processses. This involves maintaining a population of potential solutions (chromosomes), evaluating their fitness, and applying evolutionary operators like selection, crossover, and mutation over multiple generations.

Problem Configuration and Parameters

To implement the solution in MATLAB, we first define the item properties and the GA hyperparameters. In this example, we use a dataset of 50 items and a maximum weight capacity of 1000 units.

% Problem Dataset
itemWeights = [80, 82, 85, 70, 72, 70, 82, 75, 78, 45, 49, 76, 45, 35, 94, 49, 76, 79, 84, 74, 76, 63, ...
               35, 26, 52, 12, 56, 78, 16, 52, 16, 42, 18, 46, 39, 80, 41, 41, 16, 35, 70, 72, 70, 66, ...
               50, 55, 25, 50, 55, 40];
itemValues = [200, 208, 198, 192, 180, 180, 168, 176, 182, 168, 187, 138, 184, 154, 168, 175, 198, ...
              184, 158, 148, 174, 135, 126, 156, 123, 145, 164, 145, 134, 164, 134, 174, 102, 149, 134, ...
              156, 172, 164, 101, 154, 192, 180, 180, 165, 162, 160, 158, 155, 130, 125];
capacityLimit = 1000;

% GA Parameters
numItems = length(itemWeights);
popSize = 200;
maxGen = 500;
crossProb = 0.95;
mutProb = 0.15;

% Initialize Population (Binary Matrix)
population = round(rand(popSize, numItems));
bestFitnessHistory = zeros(maxGen, 1);

Main Evolutionary Loop

The algorithm iterates through generations, performing selection based on fitnesss, generating offspring through crossover, and introducing diversity via mutation.

for gen = 1:maxGen
    % Fitness Evaluation
    fitness = zeros(popSize, 1);
    for i = 1:popSize
        currentWeight = sum(population(i, :) .* itemWeights);
        currentValue = sum(population(i, :) .* itemValues);
        
        % Penalty for exceeding weight capacity
        if currentWeight > capacityLimit
            fitness(i) = 0;
        else
            fitness(i) = currentValue;
        end
    end
    
    % Identify Best Individual
    [maxVal, bestIdx] = max(fitness);
    bestIndividual = population(bestIdx, :);
    bestFitnessHistory(gen) = maxVal;
    
    % Selection (Roulette Wheel)
    probDist = fitness / sum(fitness);
    cumProb = cumsum(probDist);
    selectedPop = zeros(size(population));
    for i = 1:popSize
        r = rand();
        idx = find(cumProb >= r, 1, 'first');
        selectedPop(i, :) = population(idx, :);
    end
    
    % Single-Point Crossover
    offspringPop = selectedPop;
    for i = 1:2:popSize-1
        if rand < crossProb
            cp = randi([1, numItems-1]);
            offspringPop(i, :) = [selectedPop(i, 1:cp), selectedPop(i+1, cp+1:end)];
            offspringPop(i+1, :) = [selectedPop(i+1, 1:cp), selectedPop(i, cp+1:end)];
        end
    end
    
    % Mutation
    for i = 1:popSize
        if rand < mutProb
            mp = randi([1, numItems]);
            offspringPop(i, mp) = 1 - offspringPop(i, mp); % Flip bit
        end
    end
    
    % Elitism: Carry forward the best individual
    population = offspringPop;
    population(1, :) = bestIndividual;
end

Results and Performance Tracking

After completing the iterations, the best solution can be extracted and the convergence of the fitness function can be visualized.

% Display Results
fprintf('Maximum Value Found: %.2f\n', bestFitnessHistory(end));
includedItems = find(bestIndividual == 1);
fprintf('Items selected (Indices): %s\n', mat2str(includedItems));

% Plot convergence curve
figure;
plot(1:maxGen, bestFitnessHistory, 'LineWidth', 1.5);
grid on;
title('Fitness Evolution over Generations');
xlabel('Generation');
ylabel('Total Value');

The optimization process identifies a combination of items that maximizes value while respecting the weight constraint. Due to the stochastic nature of Genetic Algorithms, results may vary slightly between runs, though it consistently converges toward an optimal region of the search space.