EA1

numberOfCities = 10;
populationSize = 250;
n = 0.8;
parentsSize = populationSize * n;
t_max = 1000;
mutationRate = 0.3;
x = [0 2 6 7 15 12 14 9.5 7.5 0.5];
y = [1 3 5 2.5 -0.5 3.5 10 7.5 9 10];

points = zeros(2, numberOfCities);
points(1, :) = x;
points(2, :) = y;
population = zeros(populationSize,numberOfCities);
selected_parents = zeros(parentsSize, numberOfCities);
costs = zeros(populationSize, 3);

the_best_val = 1000000; %initial value
the_best_path = zeros(numberOfCities, 1);
the_best_iteration = 0;

% generate n paths where n=population_size
for k = 1:populationSize
population(k,:) = randperm(numberOfCities);
end
for z = 1:t_max
    % calculate costs for each path combination in population
    % Evaluate the cost (the total distance to be traveled) of each individual.
    for k = 1:populationSize
        normalization = points(: ,population(k, numberOfCities)) - points(: ,population(k, 1));
        single_cost = norm(points(: ,population(k, numberOfCities)) - points(: ,population(k, 1)));
        for j=2:numberOfCities
            single_cost = single_cost + norm(points(: ,population(k, j-1)) - points(:, population(k,j)));
        end
        costs(k, 1) = single_cost;
        costs(k, 2) = k;
        costs(k, 3) = true;
    end
    % proportional selection - roulette wheel
    % Choose n·P parents from the current population via proportional selection, where n ∈ (0, 1].
    costs = sortrows(costs);
    max_val = max(costs(:,1));
    ti = zeros(populationSize, 1);
    for i = 1: populationSize
        costs(i, 1);
        ti(i) = max_val - costs(i,1);
    end
    ts = sum(ti);
    for i = 1: parentsSize
        r = ts.*rand();
        chosen_index = 1;
        ti_sum = 0;
        for index = 1 : populationSize
            ti_sum = ti_sum + ti(i);
            if(ti_sum >= r)
                index;
                chosen_index = costs(index, 2);
                break
            end
        end
        selected_parents(i, :) = population(chosen_index, :);
    end
    %parents_costs = zeros(parentsSize,3);
    %for k = 1:parentsSize
    %    single_cost = norm(points(: ,selected_parents(k, numberOfCities)) - points(: ,selected_parents(k, 1)));
    %    for j=2:numberOfCities
    %        single_cost = single_cost + norm(points(: ,selected_parents(k, j-1)) - points(:, selected_parents(k,j)));
    %    end
    %    parents_costs(k,1) = single_cost;
    %    parents_costs(k,2) = k;
    %    parents_costs(k,3) = true;
    %end

    %crossover
    % Select randomly two parents to create offspring using crossover operator
    child_popul = zeros(parentsSize, numberOfCities);
    for i = 1:parentsSize
        random2parents = datasample(selected_parents, 2);    %random 2 parents
        parent1 = random2parents(1, :);
        parent2 = random2parents(2, :);
        child = zeros(1, numberOfCities);
        child(1) = parent1(1);
        search = parent1(1);
        while(true)
            found = false;
            for j = 1:numberOfCities
                if(parent2(j) == search)
                    if(child(j) ~= 0)
                        break;
                    end
                    child(j)=parent1(j);
                    search=parent1(j);
                    found=true;
                end
            end
            if(~found)
                break;
            end
        end
        for j = 1:numberOfCities
            if(child(j)==0)
                child(j)=parent1(j);
            end
        end
        child_popul(i, :) = child;
    end
    %mutation
    % Apply mutation operators for changes in randomly selected offspring.

    for i = 1:child_popul
        if rand() <= mutationRate
            mut_child = child_popul(i, :);
            mut_points = randi([1 numberOfCities],2,1);
            temp = mut_child(mut_points(1));
            mut_child(mut_points(1))=mut_child(mut_points(2));
            mut_child(mut_points(2))=temp;
            child_popul(i, :) = mut_child;
        end
    end
    %calc children costs
    children_costs = zeros(parentsSize,2);
    for k = 1:parentsSize
        single_cost = norm(points(: ,child_popul(k, numberOfCities)) - points(: ,child_popul(k, 1)));
        for j=2:numberOfCities
            single_cost = single_cost + norm(points(: ,child_popul(k, j-1)) - points(:, child_popul(k,j)));
        end
        children_costs(k,1) = single_cost;
        children_costs(k,2) = k;
        children_costs(k,3) = false;
    end
    [a, b] = size(children_costs);
    family = costs;
    for i = 1 : a
        family(i+populationSize, :) = children_costs(i, :);
    end
    family_sorted = sortrows(family);
    if(family_sorted(1, 1) < the_best_val)
        the_best_val = family_sorted(1,1)
        the_best_iteration = z
        if family_sorted(1, 3)
            the_best_path = population(family_sorted(1,2), :);
        else
            the_best_path = child_popul(family_sorted(1, 2), :);
        end
    end
    new_population = zeros(populationSize, numberOfCities);
    for i = 1: populationSize
        if family_sorted(i, 3)
            new_population(i, :) = population(i, :);
        else
            new_population(i, :) = child_popul(family_sorted(i, 2), :);
        end
    end
population = new_population;
the_best_val
end
hold on scatter(x,y,'X')
plot([x(the_best_path(numberOfCities)), x(the_best_path(1))], [y(the_best_path(numberOfCities)), y(the_best_path(1))])
for i=2:numberOfCities
    plot([x(the_best_path(i-1)), x(the_best_path(i))], [y(the_best_path(i-1)), y(the_best_path(i))])
end