Genetic Algorithms MATLAB

Da Bioingegneria Elettronica e Informatica.

Slides

Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it

Nicola Altini nicola.altini@poliba.it

Mono-objective Function Optimization

Optimization Function

  1. %%% Optimization Function 
  2. % Define and plot the function to optimize
  3. xi = linspace(-6,6,300);
  4. yi = linspace(-6,6,300);
  5. [X,Y] = meshgrid(xi,yi);
  6. Z = ps_example([X(:),Y(:)]);
  7. % Note that ps_example is a non-smooth function
  8. Z = reshape(Z,size(X));
  9. surf(X,Y,Z,'MeshStyle','none')
  10. colormap 'jet'
  11. view(-26,43)
  12. xlabel('x(1)')
  13. ylabel('x(2)')
  14. title('Teaching Example')
  15. hold on 
  16. dim_area = 200;

Unconstrained Optimization

  1. %% Optimization with Genetic Algorithm
  2. rng default % For reproducibility
  3. x = ga(@ps_example,2);
  4. fprintf('The minimum found using GA is: ');
  5. disp(x);
  6. fprintf('f(x) = %.4f\n', ps_example(x));
  7. scatter3(x(1), x(2), ps_example(x),dim_area,'g','filled');

Optimization with Linear Inequality Constraints

  1. %% Nonsmooth Function with Linear Constraints
  2. % Linear Constraints
  3. % Inequalities to the matrix form A*x <= b
  4. % -x(1) -x(2) <= -1
  5. % -x(1) +x(2) <= 5
  6. A = [-1, -1;
  7.      -1,  1];
  8. b = [-1; 5];
  9.  
  10. rng default % For reproducibility
  11. fun = @ps_example;
  12. x = ga(fun,2,A,b);
  13. fprintf('The minimum found using GA (with Linear Constraints) is: ');
  14. disp(x);
  15. fprintf('f(x) = %.4f\n', ps_example(x));
  16. fprintf('Check constraint:\n');
  17. fprintf('A * x - b = ');
  18. disp(A*x' - b);
  19. scatter3(x(1), x(2), ps_example(x),dim_area,'r','filled');

Optimization with Linear Equality and Inequality Constraints

  1. %% Linear Equality and Inequality Constraints
  2. % Inequalities to the matrix form A*x <= b
  3. % Equalities to the matrix form   Aeq*x = beq
  4. A = [-1 -1];
  5. b = -1;
  6. Aeq = [-1 1];
  7. beq = 5;
  8.  
  9. % Optimization
  10. rng default % For reproducibility
  11. fun = @ps_example;
  12. x = ga(fun,2,A,b,Aeq,beq);
  13. fprintf('The minimum found using GA (with Linear Equality and Inequality Constraints) is: ');
  14. disp(x);
  15. fprintf('f(x) = %.4f\n', ps_example(x));
  16. fprintf('Check constraints:\n');
  17. fprintf('A * x - b = ');
  18. disp(A*x' - b);
  19. fprintf('Aeq * x - beq = ');
  20. disp(Aeq*x' - beq);
  21. scatter3(x(1), x(2), ps_example(x),dim_area,'b','filled');

Excercise 3

  1. %% Linear Equality and Inequality Constraints - Excercise 3
  2. % Constraints
  3. A = [-2 -4; 3 -1; -1 -1];
  4. b = [-1; -2; 0];
  5. Aeq = [2 1];
  6. beq = 5;
  7.  
  8. % Optimization
  9. rng default % For reproducibility
  10. fun = @ps_example;
  11. x = ga(fun,2,A,b,Aeq,beq);
  12. fprintf('The minimum found using GA (with Linear Equality and Inequality Constraints) is: ');
  13. disp(x);
  14. fprintf('f(x) = %.4f\n', ps_example(x));
  15. fprintf('Check constraints:\n');
  16. fprintf('A * x - b = ');
  17. disp(A*x' - b);
  18. fprintf('Aeq * x - beq = ');
  19. disp(Aeq*x' - beq);
  20. scatter3(x(1), x(2), ps_example(x),dim_area,'b','filled');

Optimization with Linear Constraints and Bounds

  1. %% Linear Constraints and Bounds
  2. % -x(1) -x(2) <= -1
  3. % -x(1) +x(2) == 5
  4. A = [-1 -1];
  5. b = -1;
  6. Aeq = [-1 1];
  7. beq = 5;
  8. %  1 <= x(1) <= 6
  9. % -3 <= x(2) <= 8
  10. lb = [1 -3];
  11. ub = [6  8];
  12.  
  13. % Optimization
  14. rng default % For reproducibility
  15. fun = @ps_example;
  16. x = ga(fun,2,A,b,Aeq,beq,lb,ub);
  17. fprintf('The minimum found using GA (with Linear Constraints and Bounds) is: ');
  18. disp(x);
  19. fprintf('f(x) = %.4f\n', ps_example(x));
  20. fprintf('Check constraints:\n');
  21. fprintf('A * x - b = ');
  22. disp(A*x' - b);
  23. fprintf('Aeq * x - beq = ');
  24. disp(Aeq*x' - beq);
  25. scatter3(x(1), x(2), ps_example(x),dim_area,'p','filled');

Optimization with Nonlinear Constraints

Example 1

  1. %% Nonlinear Constraints 
  2. % minimize ps_example function on the region
  3. % 2x(1).^2 + x(2).^2 <= 3 
  4. % (x(1) + 1).^2 = (x(2) / 2).^4
  5. nonlcon = @ellipsecons;
  6.  
  7. % Optimization
  8. fun = @ps_example;
  9. rng default % For reproducibility
  10. x = ga(fun,2,[],[],[],[],[],[],nonlcon);
  11. disp(x);
  12. fprintf('f(x) = %.4f\n', ps_example(x));
  13. [c,ceq] = nonlcon(x);
  14. fprintf('Check constraints:\n');
  15. fprintf('nonlcon(x) -> c = %.3f, ceq = %.3f\n', c, ceq); 
  16. % Constraints satisfied when
  17. % c   <= 0
  18. % ceq == 0
  19. scatter3(x(1), x(2), ps_example(x),dim_area,'y','filled');

Example 2

  1. %% Genetic Algorithm with Non-Linear constraints
  2. use_circle_equality_constraint = 1;
  3. if use_circle_equality_constraint
  4.     nonlcon = @circlecons_eq;
  5. else
  6.     nonlcon = @circlecons_lt;
  7. end
  8.  
  9. rng default % For reproducibility
  10. fun = @squarednorm;
  11. A = [];
  12. b = [];
  13. Aeq = [];
  14. beq = [];
  15. lb = [2, 2];
  16. ub = [7, 8];
  17. IntCon = [];
  18. [x,fval,exitflag,output,population,scores] = ga(fun,2,A,b,Aeq,beq,lb,ub,nonlcon,IntCon);

Optimization with Integer Constraints

  1. %% Integer Constraints
  2. IntCon = 1;
  3. rng default % For reproducibility
  4. fun = @ps_example;
  5. A = [];
  6. b = [];
  7. Aeq = [];
  8. beq = [];
  9. lb = [];
  10. ub = [];
  11. nonlcon = [];
  12. x = ga(fun,2,A,b,Aeq,beq,lb,ub,nonlcon,IntCon);
  13. disp(x);
  14. fprintf('f(x) = %.4f\n', ps_example(x));
  15. scatter3(x(1), x(2), ps_example(x),dim_area,'c','filled');

Obtaining Diagnostic Information

Example 1

  1. %%% Example 1
  2. rng default % For reproducibility
  3. fun = @ps_example;
  4. A = [];
  5. b = [];
  6. Aeq = [];
  7. beq = [];
  8. lb = [];
  9. ub = [];
  10. nonlcon = [];
  11. IntCon = 1;
  12. % options = optimoptions(SolverName,Name,Value)
  13. options = optimoptions('ga','PlotFcn', @gaplotbestf);
  14. [x,fval,exitflag,output,population,scores] = ga(fun,2,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options);
  15. % Final Population and Scores
  16. disp(population(1:10,:));
  17. disp(scores(1:10));

Example 2

  1. %%% Example 2
  2. options = optimoptions('ga','ConstraintTolerance',1e-6,'PlotFcn', @gaplotbestf);
  3. [x,fval,exitflag,output,population,scores] = ga(fun,2,A,b,Aeq,beq,lb,ub,nonlcon,options);
  4. % Final Population and Scores
  5. disp(population(1:10,:));
  6. disp(scores(1:10));

Helper Functions

  1. %% Helper Functions
  2. function [c,ceq] = circlecons_eq(x)
  3. c = [];
  4. ceq = (x(1)-8)^2 +(x(2)-6)^2 -9;
  5. end
  6.  
  7. function [c,ceq] = circlecons_lt(x)
  8. c = (x(1)-8)^2 +(x(2)-6)^2 -9;
  9. ceq = [];
  10. end
  11.  
  12. function [c, ceq] = ellipsecons(x)
  13. c = 2*x(1)^2 + x(2)^2 - 3;
  14. ceq = (x(1)+1)^2 - (x(2)/2)^4;
  15. end
  16.  
  17. function f = squarednorm(x)
  18. f = x(1)^2 + x(2)^2;
  19. end

Multi-objective Function Optimization

Unconstrained Optimization

  1. %%  Multi-objective Optimization Example
  2. %%% No Constraints
  3. % Defining fitness function
  4. % Find the Pareto front for a simple multiobjective problem. There are two objectives and two decision variables x.
  5. fitnessfcn = @(x)[norm(x)^2  ,  0.5*norm(x(:)-[2;-1])^2+2];
  6. % Find the Pareto front for this objective function.
  7. % Optimization
  8. rng default % For reproducibility
  9. x = gamultiobj(fitnessfcn,2);
  10. % Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.
  11. % Plot the solution points.
  12. plot(x(:,1),x(:,2),'ko')
  13. xlabel('x(1)')
  14. ylabel('x(2)')
  15. title('Pareto Points in Parameter Space')

Optimization with Linear Constraints

  1. %% Linear Inequality Constraint
  2. A = [1,1];
  3. b = 1/2;
  4. % Find the Pareto front.
  5.  
  6. rng default % For reproducibility
  7. [x, fval] = gamultiobj(fitnessfcn,2,A,b);
  8. % Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.
  9. % Plot the constrained solution and the linear constraint.
  10.  
  11. plot(x(:,1),x(:,2),'ko')
  12. t = linspace(-1/2,2);
  13. y = 1/2 - t;
  14. hold on
  15. plot(t,y,'b--')
  16. xlabel('x(1)')
  17. ylabel('x(2)')
  18. title('Pareto Points in Parameter Space')
  19. hold off

Optimization with Bound Constraints

Example 1

  1. %% Bound Constraints
  2. fitnessfcn = @(x)[sin(x),cos(x)];
  3. nvars = 1;
  4. lb = 0;
  5. ub = 2*pi;
  6. rng default % for reproducibility
  7. [x, fval] = gamultiobj(fitnessfcn,nvars,[],[],[],[],lb,ub);
  8.  
  9. plot(sin(x),cos(x),'r*')
  10. xlabel('sin(x)')
  11. ylabel('cos(x)')
  12. title('Pareto Front')
  13. legend('Pareto front')

Example 2

  1. %% Multi-objective Optimization Example 2
  2. % Defining and plotting function to optimize
  3. x = -1:0.1:8;
  4. y = schaffer2(x);
  5. plot(x,y(:,1),'r',x,y(:,2),'b');
  6. xlabel x
  7. ylabel 'schaffer2(x)'
  8. legend('Objective 1','Objective 2')
  9.  
  10. % Bounds
  11. lb = -5;
  12. ub = 10;
  13.  
  14. % Set options to view the Pareto front as gamultiobj runs.
  15. options = optimoptions('gamultiobj','PlotFcn',@gaplotpareto);
  16.  
  17. % Optimization - call gamultiobj.
  18. rng default % For reproducibility
  19. [x,fval,exitflag,output] = gamultiobj(@schaffer2,1,[],[],[],[],lb,ub,options);

Helper Functions

  1. %% Helper Functions
  2. function f = my_multi(x)
  3. f(1) = x(1)^4 - 10*x(1)^2+x(1)*x(2) + x(2)^4 -(x(1)^2)*(x(2)^2);
  4. f(2) = x(2)^4 - (x(1)^2)*(x(2)^2) + x(1)^4 + x(1)*x(2);
  5. end
  6.  
  7. function f = pareto_example(x)
  8. f = [norm(x)^2  ,  0.5*norm(x(:)-[2;-1])^2+2];
  9. end
  10.  
  11. function y = schaffer2(x) % y has two columns
  12.  
  13. % Initialize y for two objectives and for all x
  14. y = zeros(length(x),2);
  15.  
  16. % Evaluate first objective. 
  17. % This objective is piecewise continuous.
  18. for i = 1:length(x)
  19.     if x(i) <= 1
  20.         y(i,1) = -x(i);
  21.     elseif x(i) <= 3 
  22.         y(i,1) = x(i) -2; 
  23.     elseif x(i) <= 4 
  24.         y(i,1) = 4 - x(i);
  25.     else 
  26.         y(i,1) = x(i) - 4;
  27.     end
  28. end
  29.  
  30. % Evaluate second objective
  31. y(:,2) = (x -5).^2;
  32. end
Estratto da "http://www.vitoantoniobevilacqua.it/wiki/index.php?title=Genetic_Algorithms_MATLAB&oldid=1124"