====== AI Lab 2 ======

<WRAP column 30%>
The following script produces the plot:

{{ :ai:plot.jpg|}}

X axis: Generations, Y Axis: Fitness
</WRAP>

<file matlab main.m>
population_size = 100;
chromosome_length = 500;
generations = 500;
mutation_rate = 0.001;

best_fitness_hist = [];

%create inital population
population = initialization(population_size, chromosome_length);

for g = 1:generations
    %eval fitness
    fitness = sum(population, 2);
    %select individuals for tournament selection
    selected = tournament_selection(population,fitness,population_size);
    %crossover the individuals
    offspring = crossover(selected);
    %mutation
    mutated_offspring = mutate(offspring, mutation_rate);

    %create new population
    population = mutated_offspring;

    %display best fitness of this generation
    best_fitness = max(fitness);

    if best_fitness == chromosome_length
        break
    end

    best_fitness_hist = [best_fitness_hist;best_fitness];
    fprintf('Generation %d: Bestfitness = %d\n', g, best_fitness);
end

plot(best_fitness_hist)
</file>
</WRAP>

<file matlab initialization.m>
function population = initialization(size,string_length)
    population = randi([0,1], size, string_length);
end
</file>

<file matlab tournament_selection.m>
function selected_parents = tournament_selection(population, fitness, n)
    selected_parents = zeros(n, size(population, 2));
    for i = 1:n
        %randomly select 2 indiviuals
        idx = randi([1, size(population, 1)], 2, 1);
        if fitness(idx(1)) > fitness(idx(2))
            selected_parents(i, :) = population(idx(1), :);
        else
            selected_parents(i, :) = population(idx(2), :);
        end
    end
end
</file>

<file matlab crossover.m>
function offspring = crossover(parents)
    [num_parents, string_length] = size(parents);
    offspring = zeros(num_parents, string_length);
    
    %pick every 2, use -1 so you can select the next one i.e. i+1 without
    %running out of hte index bounds
    for i = 1:2:num_parents-1
        crossover_point = randi([1, string_length-1]);
        offspring(i, :) = [
            parents(i, 1:crossover_point) ...
            parents(i+1, crossover_point+1:end)
        ];
        offspring(i+1, :) = [
            parents(i+1, 1:crossover_point) ...
            parents(i, crossover_point+1:end)
        ];
    end

    if mod(num_parents, 2) == 1
        %Carry over last parent if odd
        offspring(end, :) = parents(end, :);
    end
end
</file>

<file matlab mutate.m>
function mutated_offspring = mutate(offspring, mutation_rate)
    mutated_offspring = offspring;

    for i = 1:size(offspring, 1)
        for j = 1:size(offspring, 2)
            if rand < mutation_rate
                % flip the bits
                mutated_offspring(i, j) = ~mutated_offspring(i,j);
            end
        end
    end
end
</file>