An Introduction to Non-Traditional Optimization Algorithms: Part 1

I have decided to make some lecture videos on non traditional optimization. I have just made an introductiory lecture on conventional optimization algorithms.

The drawbacks of  conventional algorithms gives the motivation for non traditional algorithms like Genetic algorithms and its variants.
Part 1

Part 2

I will add more videos on this topic.
Thanks for reading.

Solving Optimization Problems Using PSO algorithm.

Introduction

As we have discussed the difference between the conventional optimization algorithms and the unconventional algorithms are summarized below.

1.The conventional algorithms start from a single  initial feasible  solution where as the unconventional algorithms start with a set of initial(feasibility not a prerequisite)  solutions. 

2.The conventional algorithms need the function to be continuously differentiable through out the range of search.

3.The accuracy of the conventional algorithms depending on the selection of initial solution.Always a local solution is assured. The performance of the unconventional algorithms will  vary for every run. A solution is assured.It may be local or global.Very rarely diverges.

Particle Swarm Optimization(PSO)

This  PSO algorithm also one of the important unconventional optimization algorithms.PSO optimizes a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae. The movements of the particles are guided by the best found positions in the search-space which are updated as better positions are found by the particles.

PSO is originally attributed to Kennedy, Eberhart and Shi  and was first intended for simulating social behaviour. The algorithm was simplified and it was observed to be performing optimization. The book by Kennedy and Eberhart  describes many philosophical aspects of PSO and swarm intelligence.

As I am more interested in the implementation of this algorithm interested readers can get more details in the web regrading this algorithm.To implement PSO you neeed not know anything about the algorithm,you should know how to use the code to solve your modelled problem.

http://en.wikipedia.org/wiki/Particle_swarm_optimization

PSO Code in MATLAB

There are so many variants of this PSO the code  which  I found simple and powerful is the vectorised PSO  Toolbox by Mr Brian Birge.I thank him for the excellent toolbox.It can be downloaded from the link.

http://www.mathworks.com/matlabcentral/fileexchange/7506

Just download it and unzip it as a folder.You can either add it to MATLAB path or make it as  the default folder.

Solving an Optimization problem by PSO

For implementing  most of  the unconventional algorithms(including the PSO)   follow the steps.

1. Model the problem as unconstrained minimization problem( you can refer my earlier post on MATLAB GA toolbox ).

2. Write it as a function file.There are two types of functiones (i) scalar function(ii)vector function

In the scalar function for for every value of X the corresponding function value is returned.

X1-----------F(X1)

In the vector function for for every set of X values the corresponding function values are returned.

[X1 X2 X3 X4...Xn]-------------[F(X1),F(X2),F(X3),F(X4)...F(Xn)]

The code by Mr Brian Birge requires a vector function file .

3.After writing the function file save it in the same PSO folder and change it as default.

The toolbox has lot of details regarding the setting..

4.Run it .You get the solution as well the progressive graphs( iteration vs best solution and movement of particles in two dimension) .

Implementation

The same problem discussed in GA tool box is considered. Same way two files have to be written the first one is  the pso setting file(test1.m) .This calls the subroutine vector function file ex2.m.

program 1 test1.m

clear;
clc
% lower limir
l=[0 0];
% upper limit
u=[ 10 10];
ran=[l' u'];
% number of variables
n=2;
% settings for pso
%1. population,2. no of iterations,3 refresh on screen 4&5 type of PSO 06&7
%are final and initial swarm velocity 8. final iteration to reach final
%velocity 9. expected function value
Pdef = [20 200 10 2 2 0.9 0.4 200 50 5000 NaN 0 0];
[OUT]=pso_Trelea_vectorized('ex2',n,1,ran,0,Pdef);
out=abs(OUT)
P=out(1:n)

[F x]=ex2(P')

Program 2 vector function file ex2.m

function [F x]=ex2(x);

F=sum((x.*x).').'+1000*((sum(x')-10))^2;

Results

PSO: 1/200 iterations, GBest =                  100.

PSO: 20/200 iterations, GBest =   52.210493585432118.

PSO: 40/200 iterations, GBest =   50.166913798388642.

PSO: 60/200 iterations, GBest =   49.997052264769565.

PSO: 80/200 iterations, GBest =   49.978589042793075.

PSO: 100/200 iterations, GBest =   49.978455656591841.

PSO: 120/200 iterations, GBest =   49.975851601760063.

PSO: 140/200 iterations, GBest =   49.975342456412399.

PSO: 160/200 iterations, GBest =   49.975036994685418.

PSO: 180/200 iterations, GBest =    49.97501323855063.

PSO: 200/200 iterations, GBest =   49.975012959884864.

out =

   4.99798359369474

   4.99701881234046

  49.97501295916326

P =

   4.99798359369474

   4.99701881234046

F =

  49.97501295916326

x =

   4.99798359369474   4.99701881234046

You are welcome to make some suggestions .All the best.

Solving Linear and Quadratic Programming Problems by MATLAB

Introduction

Optimization is defined as Minimizing (or Maximizing) an objective function subject to some constraints .If the objective function and the all the constrains are linear it is called linear programming. If the objective function is quadratic and the all the constraints are linear, it is known as quadratic programming. Let us learn how to use the linear and quadratic programming routines of the MATLAB.

Linear programming

The command for implementing the matlab linear programming routine is ‘linprog’.

Let us consider a linear programming problem with ‘n’ variables, ‘m’ inequality constraints, ‘k’ equality constraints, and the lower ,upper bounds LB and UB.

The linear programming is defined in matlab like this

min f'*x    subject to:   A*x <= b, Aeq*x = beq ,LB≤ x ≤ UB

x-=[x₁ x₂ x₃ ….x_n]^T x is a column matrix of 1 X n) to be determined.  

f=[c₁ c₂ c₃ ….c_n]  f is a vector(row matrix of n X 1)

A is the matrix of inequalities having a size of m X n

Aeq is the matrix of equalities having a size of k X n

LB-=[l₁ l₂ l₃ ….l_n]^T x is a column matrix of 1 X n)

UB= [u₁ u₂, u₃ ….u_n]^T x is a column matrix of 1 X n)

Example

f=[10 5 12 13 20];

A= [10     6     1     0     8

     2     8     4     7     0

     6     9     8     4     7

     5     7     0     9     4

     9     2     1     5     8

     8     4     2     4     5

     5     9     2     8     7

     0     9     6     5     4

     8     4     3     2     3

     4     9     2     7     2];

b=[70    63   104    80    81    68   101    81    53    71]';

Aeq=[1 1 1 1 1]

beq=15;

LB=[0 0 0 0 0]'

UB=[20 20 20 20 20]'

X=linprog(f,A,b,Aeq,beq,LB,UB)

Solution

Optimization terminated.

X =

    2.1683

    0.0000

    9.6931

    2.8416

    0.2970

Quadratic programming

The command for implementing the matlab quadratic programming routine is ‘quadprog’.Let us consider a quadratic programming problem with ‘n’ variables, ‘m’ inequality constraints, ‘k’ equality constraints, and the lower, upper bounds LB and UB.

The quadratic programming is defined in matlab like this

   min 0.5*x'*H*x + f'*x    subject to:   A*x <= b, Aeq*x = beq ,LB≤ x ≤ UB

x-=[x₁ x₂ x₃ ….x_n]^T x is a column matrix of 1 X n) to be determined.  

H= is a square matrix of n X n

f=[c₁ c₂ c₃ ….c_n]  f is a vector(row matrix of n X 1)

A is the matrix of inequalities having a size of m X n

Aeq is the matrix of equalities having a size of k X n

LB-=[l₁ l₂ l₃ ….l_n]^T x is a column matrix of 1 X n)

UB= [u₁ u₂, u₃ ….u_n]^T x is a column matrix of 1 X n)

Example

Minimize x₁^2+x₁x₂+x₂₂+3x₁+5x₂

Subject to the constraints

x₁+x₂=20;

2x₁+3x₂≤100

[0 0]^T≤x₁,x₂≤[50 50]^T

H=[2 1;1 2];

f=[3 5];

A= [2 3];

b=[100];

Aeq=[1 1]

beq=20;

LB=[0 0 0 0 0]';

UB=[50 50]';

[X ff]=quadprog(H,f,A,b,Aeq,beq,LB,UB)

Solution

X =

   11.0000

    9.0000

ff is the objective function value

ff =  379.0000

Solving Economic Dispatch and Optimal Power Flow by GA

The economic dispatch problem is described as an act of minimizing the total fuel cost of the committed generators while satisfying the demand, network constraints. and plant.

Follow these steps.

Step II Solution Methodology

1. Choose a reference plant .For economic dispatch choose the plant with large capacity (range). In case of optimal power flow the slack bus is the reference bus.
2. For  both problems the number of  control(independent) variables to be determined in n-1.The reference plant  allocation is determined from the  constraint equations A2.

While solving the quadratic equation consider the positive solution. Check for the plant limits. If it is violating the limits allocate that particular limit.
3. Write a function file of n-1 control variables which return the total fuel cost fuel cost and the allocation. In case optimal power flow you have to use a power flow routine to determine the reference plant(slack bus) allocation.
4.The data file (fuel cost equations ,demand,loss coefficients,bus data,line data) and the gaoptions is put in a file  and the function file is run by the GA with options.


The program can be downloaded from the matlab cetral file excange

http://www.mathworks.de/matlabcentral/fileexchange/20825

Solving Optimization Problems Using MATLAB GA toolbox-Part 2

Now let us learn how to use the GA in command line mode.
the basic syntax to run the GA in command mode is
x = ga(@fitnessfunction,nvar,options)

fitnessfunction:Function file relating the control variables(x) with function value(F).

nvar: no of  control variables

options: Genetic algorithm parameters setting.


GA Options



PopulationType: [ 'bitstring'      | 'custom'    | {'doubleVector'} ]:-Type of the population 'custom' :  :binary,'double vector': real values

PopInitRange: [ matrix           | {[0;1]} ]: Initial value range default is [0 to 1] you can change this by giving two column vectors .For the example problem discussed for the GUI mode the limits can be like this
l=[0 0]'; u=[10 10]';

        
PopulationSize: [ positive scalar  | {20} ]-Size of the population

            
EliteCount: [ positive scalar  | {2} ]:The number best solution in each generation to be saved.

    
CrossoverFraction: [ positive scalar  | {0.8} ]: cross over value between 0 to 1

    
MigrationDirection: [ 'both'           | {'forward'} ]  The solution vector is moved in both direction.(increase or decrease)
    
MigrationInterval: [ positive scalar  | {20} ]
    
MigrationFraction: [ positive scalar  | {0.2} ]

          
Generations: [ positive scalar  | {100} ]: no of iterations
            
TimeLimit: [ positive scalar  | {Inf} ]: Time Limit for the algorithm

          
FitnessLimit: [ scalar           | {-Inf} ]:;Set value or a typical known fitness value

        
 StallGenLimit: [ positive scalar  | {50} ]: If Solution is not changing for certain number of generation stop the algorithm
        
StallTimeLimit: [ positive scalar  | {20} ]: If Solution is not changing for certain time, stop the algorithm
    
 InitialPopulation: [ matrix           | {[]} ]:You can specify initial feasible solution if already known.

  InitialScores: [ column vector    | {[]} ]: Known function values

 CreationFcn: [ function_handle  | {@gacreationuniform} ]; random function for creating initial population

 FitnessScalingFcn: [ function_handle  | @fitscalingshiftlinear  | @fitscalingprop  | :testing the fitness
                             @fitscalingtop   | {@fitscalingrank} ]
SelectionFcn: [ function_handle  | @selectionremainder    | @selectionrandom |
                            @selectionroulette | @selectiontournament   | {@selectionstochunif} ]
          
CrossoverFcn: [ function_handle  | @crossoverheuristic  | @crossoverintermediate |
@crossoversinglepoint | @crossovertwopoint | {@crossoverscattered} ]:Different crossovers
          
MutationFcn: [ function_handle  | @mutationuniform | {@mutationgaussian} ]:  Mutation function
            
HybridFcn: [ @fminsearch | @patternsearch | @fminunc | {[]} ]: After GA run another local minimizing function is run

Display: [ off | iter | diagnose | {final} ]: the results are displayed
            
OutputFcns: [ function_handle  | @gaoutputgen | {[]} ]:the output producing function
            
 PlotFcns: [ function_handle  | @gaplotbestf | @gaplotbestindiv | @gaplotdistance | @gaplotexpectation | @gaplotgeneology | @gaplotselection | @gaplotrange | @gaplotscorediversity  | @gaplotscores | @gaplotstopping  | {[]} ]: Choose the graphs you want
          
PlotInterval: [ positive scalar  | {1} ]: The plotting interval

            
Vectorized: [ 'on'  | {'off'} ]

Program in command mode.


This file  and the function file should be in the same folder which should be default.

the options can be set by the following commands

% setting the genetic algorithm parameters.
options = gaoptimset;
options = gaoptimset('PopulationSize', 50,'Generations', 500,'TimeLimit', 200,'StallTimeLimit',100,
'PlotFcns',  {@gaplotbestf,@gaplotbestindiv});
  [x ff]=ga(@ex1,2,options)

.

Solving Optimization Problems Using MATLAB GA toolbox-Part 1

The GA tool box of MATLAB is good in solving hard optimization problems. It can be run form (i) GUI (Graphical  User Interface) mode or(ii) Command line Mode.


GA A Different Introduction

Genetic Algorithm or GA is one of th basic and powerful heuristic optimization algorithms.If you read any material on this algorithm you can observe the following points.

• 1.It is working on the population dynamics.
• 2.It is searching form a set of solutions(population) .
• 3.It does not need the derivative or continuous solution search space.
• 4.It doing some probabilistic operations like Reproduction,Cross Over,Mutation on the old  population to produce a new population.

MATLAB GA Toolbox

This toolbox contains some matlab files which can do the above described actions.This can be run in two modes.The GA toolbox is written as a minimization tool. Maximization problems also can be done by converting the Maximization problem as minimization problem.

1.GUI Mode

2.Command line Mode

Steps For Solving Optimization Problem 


To use the GA toolbox you need not know anything about Ga and its dynamics. All you should know is some fundamentals about optimization or operation research and basic matlab commands.


1. Model the optimization problem as a unconstrained  minimization problem.

2. Write the unconstrained minimization problem  as matlab function file.
3. Run the matalb ga tool box in a command line mode or GUI mode.




I am giving one example in GUI .It s problem of minimizing a  two variable quadratic function subject to a linear equality constraint..Just click on the figure to enlarge the figure.

 . 

Improvement of Maximum Load-ability of Power system by FACTS devices:Part 2

In the last part some fundamentals of this problem was discussed.In this part the modelling of the the problem is to be completed.

λ: The load-ability parameter

P_li- Scheduled real power load of ‘i’th bus

Q_li- Scheduled reactive power load of ‘i’th bus

P_gi- Generated real power of ‘i’th bus

Q_li- Generated real power of ‘i’th bus

V_i-Voltage of ‘i’th bus

LF_ij-Line Flow (MVA)of transmission line connecting buses ‘i’ and ‘j’

If a power system has 'm' generator buses, 'n' load buses and 'k' transmission lines.

The number of parameters to be determined is 'm+1'

The number of equality constraints are 2*(n+m-1)

The number of inequality constraints are 2*m+n+k

In the figure the equations are clearly written. It can be solved by any conventional or unconventional optimization algorithm.

Improvement of Maximum Load-ability of Power system by FACTS devices:Part 1

Now days lot of research is going on FACTS and its application on power system performance enhancement.

In this post let us try to understand the problem of Maximizing the loadability of the power system with and without incorporating the FACTS devices.

i) Maximum loadability without FACTS devices

If a problem is to be understood the title should be understood in the realistic way.

A Power System comprises of generators,loads , transmission lines and other devices ( circuit breakers ,capacitors. and lightning arrestors).

1.The generators have real and reactive power limits and a better voltage voltage profile is to be maintained.

2.The loads have to receive the scheduled power at a better voltage. The load voltage voltage should be within the allowable range . Normally it is between 90% to 110% of the base(rated) voltage.

3.The transmission lines have the MVA power flow rating .

It is known that the load on a power system is not certain and subject to change with time. The variation of demand with time is called the Load duration curve.

All the Load centers are having Maximum demand indicators which record the maximum demand on a day/week and year. From this the importance of the maximum load-ability can be understood.

The term Maximum load-ability can be defined as the maximum load that can be served by the power network without violating the voltage,power and line flow constraints.

This is an offline study done on the power system data to determine the maximum load supplied by the power system without violating the constraints.

A) what is the data is required to carry out this analysis.?

busdata,generator and linedata ( same like matpower data format)

MATPOWER is a package of MATLAB® M-files for solving power flow and optimal power flow problems. It is intended as a simulation tool for researchers and educators that is easy to use and modify. MATPOWER is designed to give the best performance possible while keeping the code simple to understand and modify. It was initially developed as part of the PowerWeb project.

This can be downloaded in the following link.

http://www.pserc.cornell.edu/matpower/

B) Problem Formulation

Let us put the points in the following way.

• The loads are to be increased.In the literature the method followed is to increase the loads by the same amount .
• The generators are optimally allocated to meet the new demand and losses .
• The load voltage limits ,power limits of generators and the line flow limits are checked.
• The maximum amount of load that can be supplied by the power system is maximum load-ability.

C) Mathematical Modelling

In this problem the control variables are the loadability parameter and the real power of the generation.

The problem is modeled as a optimization(Maximization or Minimization) an problem.

The objective function

The load-ability parameter.

The constraints are

equality constraints: Power flow equations

In equality constraints : real and reactive power limits of generators and line flow limits. of the transmission line.

In the next part let us see how to model this problem with FACTS devices.