Week 5 - Genetic Algorithm

Answer:

Understanding Genetic Algorithm (GA):

            Genetic Algorithm is a heuristic optimization technique inspired by the process of natural selection and genetics. It is used to find the optimal solution to a problem by mimicking the process of evolution. The algorithm starts with a population of candidate solutions (chromosomes) and repeatedly applies selection, crossover (recombination), and mutation operations to produce new generations of solutions. The selection process favors better-performing solutions, and crossover and mutation introduce variations and diversity in the population. Over generations, the algorithm converges towards better solutions, ideally reaching the global optimum.

The steps involved in the Genetic Algorithm are as follows:

1. Initialization: Create an initial population of random candidate solutions.
2. Fitness Evaluation: Evaluate the fitness of each solution in the population based on the objective function.
3. Selection: Choose individuals from the population to create the next generation, giving preference to higher fitness solutions.
4. Crossover (Recombination): Perform crossover (breeding) between selected individuals to create new offspring.
5. Mutation: Introduce random changes (mutation) in the offspring to maintain diversity.
6. Replacement: Replace the old generation with the new generation of offspring.
7. Termination: Repeat steps 2 to 6 until a termination condition is met (e.g., a maximum number of iterations or convergence to an acceptable solution).

MATLAB Syntax for ga: In MATLAB, the ga function is used to implement the Genetic Algorithm. Its basic syntax is as follows:

[x, fval, exitFlag, output, population, scores] = ga(fun, nvars, A, b, Aeq, beq, lb, ub, nonlcon, options);

where:

• fun: The objective function to be minimized or maximized.
• nvars: The number of variables in the objective function.
• A, b, Aeq, beq: Linear inequality and equality constraints (optional).
• lb, ub: Lower and upper bounds on the variables.
• nonlcon: Nonlinear constraint function (optional).
• options: Options structure specifying various algorithm parameters and termination conditions (optional).

Code to Optimize Stalagmite Function using Genetic Algorithm in MATLAB:

% Stalagmite function: f(x) = x * sin(10 * pi * x) + 1
fun = @(x) x .* sin(10 * pi * x) + 1;

% Define bounds and options
lb = 0;
ub = 2;
options = optimoptions('ga', 'MaxGenerations', 100, 'Display', 'off');

% Run Genetic Algorithm
[x, fval] = ga(fun, 1, [], [], [], [], lb, ub, [], options);

% Plot the function and the optimal point
x_values = linspace(0, 2, 1000);
y_values = fun(x_values);

figure;
plot(x_values, y_values, 'b', 'LineWidth', 2);
hold on;
scatter(x, fval, 100, 'r', 'filled');
title('Stalagmite Function Optimization');
xlabel('x');
ylabel('f(x)');
legend('Stalagmite Function', 'Optimal Point');

% Plot F maximum vs no. of iterations
max_iterations = 100;
f_max = zeros(max_iterations, 1);

for iter = 1:max_iterations
    [x, fval] = ga(fun, 1, [], [], [], [], lb, ub, [], options);
    f_max(iter) = fval;
end

figure;
plot(1:max_iterations, f_max, 'b', 'LineWidth', 2);
title('F Maximum vs. Number of Iterations');
xlabel('Iterations');
ylabel('F Maximum');

Explanation: 

• We define the Stalagmite function fun as per the provided formula.
• The bounds for x are set between 0 and 2.
• We set the options for the GA algorithm, including the maximum number of generations as 100, and disable displaying the progress with 'Display', 'off'.
• We use the ga function to optimize the Stalagmite function with the specified options. The output x gives the optimal point, and fval gives the maximum value of the function achieved.
• We plot the Stalagmite function and mark the optimal point found by the GA.
• We then run the GA multiple times to record the maximum value of the function achieved at each iteration and plot F maximum vs. Number of Iterations.

Please note that the GA algorithm is a stochastic optimization method, meaning the results might vary between different runs due to the random nature of the algorithm. However, the general trend of convergence should be consistent.

Ensure you have the Optimization Toolbox installed in MATLAB to use the ga function. The code provided here optimizes the Stalagmite function using GA and plots the function, the optimal point, and the F maximum vs. Number of Iterations graph.

Output :