[CR] Waptia - genetic optimization algorithm

[vugie]

Name: Waptia - genetic optimization algorithm

Submitter: vugie

Submitted: 10 Sep 2009

File Updated: 23 Jan 2011

Category: General

LabVIEW Version: 8.2

License Type: BSD (Most common)

Waptia - genetic optimization algorithm

Copyright © 2009, Wojciech Golebiowski

All rights reserved.

Author: Wojciech Golebiowski (w_golebiowski (at) tlen.pl)

Name: Waptia - genetic optimization algorithm

Type: library

LabVIEW version: 8.2

Distribution:

This code was downloaded from:

http://www.lavag.org

Description:

Waptia is general genetic optimization algorithm - it tries to maximize user supplied function of N variables (so called "Fitness Function"). Function is given as strictly typed VI reference. So the optimization goal may be described as: find such set of N numbers for which Fitness Function value is highest.

Waptia is LabVIEW implementation of quite well known genetic optimization algorithm Pikaia by Paul Charbonneau & Barry Knapp developed in Fortran-77. For more information on Pikaia and some background informatio on genetic algorithms visit: http://www.hao.ucar....kaia/pikaia.php

Pikaia name comes from lancelet-like creature which lived ages ago in Cambrian sea and waptia was another Cambrian being. Original Pikaia was developed for educational purposes, but it grew up and became widely used routine. Waptia is almost 1:1 conversion of Pikaia code (which is public domain) to LabVIEW - parts of original Fortran code are placed in related VIs - with some cosmetic modifications and improvements. Although Waptia already does real job I treat this code as starting point for further development to create sophisticated, but still easy to use genetic algorithm.

Here are Waptia's core features:

- decimal genotype encoding

- two-point crossover operator

- optional dynamically adjustable mutation rate

- optional "creep" (smoothly changing) mutation mode

- three possible reproduction plans

- elitism

- optionally stops optimization when fitness criterion is satisfied

- optimization progress may be traced on-line with notifiers

Usage is very simple - just put Waptia.vi on block diagram and provide number of independent variables and fitness function VI reference (which may be created using included template). There is of course a lot of parameters to tune, but default set usually does good job.

Installation

Preferably install VIP package with VI Package Manager

Alternatively extract ZIP to User.lib.

There are no external dependencies.

Documentation

Documentation is provided in "Waptia docs.rtf" file. It's just a description of all controls of Waptia.vi with some background information. Same information may be found in context help. Information on how to write your own fitness function is provided as comments in "Fitness Function Template.vit"

If you want to understand how Waptia works, whole code is extensively commented.

Examples

There is one quite complex example (but I hope that still understandable) located in _examples folder - "multimodal optimise.vi"

If you want any support on general or specifically genetic optimization problems, just contact me.

License (BSD):

Copyright © 2009 Wojciech Golebiowski

All rights reserved.

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions

are met:

1. Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright

notice, this list of conditions and the following disclaimer in the

documentation and/or other materials provided with the distribution.

3. The name of the author may not be used to endorse or promote products

derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Click here to download this file

[vugie]

I uploaded a VIPM package of Waptia library.

[Interstellar]

Hey,

I want to use genetic algorithm to optimize the gain of a PID controller.. Can this be done with help of waptia?

I have created model , control algorithm (PID) and a VI which calculates control quality factors out of such response (such as overshoot, settlement time or oscilations parameters) .

What should i do next to optimize the gains?

Thank you,,

[vugie]

Short explanation first - this is continuation of ours private discussion, so I repeat some things already said.

Thanks for asking it - PID optimization is a very good use case for genetic algorithm. But you have to remember that it is only good for off-line optimization as it base on huge number of trials. So you have to have prepared a numerical model of your object of control - a program (VI in case of LabVIEW) which respond on control signal exactly the same way as real object would respond. To prepare it you have to know what phenomena drives your object, what are their equations and you have to implement them with proper coefficients (measured i.e.). To be more specific I have to know what exactly do you want to control with PID.

Once you have the model you have to insert it into simulated PID loop, so you have a model of whole control system with Kp, Kd and Ki coefficients as parameters (gains of proportional, differentiating and integrating blocks respectively). Than you have to determine what will be the measure of quality of regulation. Typically parameters of response on step-like excitation are used for this purpose:

You have to decide which of these parameters are more important, which are less important, which are not important at all and combine them into one number which is the higher, the better regulation is. It may be for example weighted sum: a*(1/rise_time)+b*(1/overshoot)+c*(1/settling_time), where a,b,c are the weights. In genetic algorithm such a number is called a fitness function and PID optimization process may be now described as: find such Kp, Kd, Ki which maximizes previously defined fitness function. You have to implement a fitness function as a VI which takes certain Kp, Kd and Ki parameters, makes a simulation of control system's response on step-like excitation, calculates quality parameters out of the response and combines them into final quality measure.

In Waptia you have to implement fitness function as a strictly typed VI. There is a special template in main Waptia directory (Fitness Function Template.vit):

Phenotype input (1D array of doubles) in terms of genetic algorithm is a set of parameters describing the system, which are the subject of optimization. In our case size of this array will be always 3 and Kp, Kd and Ki will be coded in it. Coded, because optimizer requires all parameters to be scaled to 0..1 range. So you have to know the expected ranges for optimized gains (you could determine them using i.e. Ziegler–Nichols method and some manual checking). Your fitness function VI could look like this:

Data and Init? inputs are not required in simplest approach, but they may not be deleted as VI must be strictly typed. You could use these inputs to control other parameters of the models which are not to be optimized (i.e. coefficients of equations of the model).

Code for actual optimization of PID gains is now as simple as:

Values from final solution have to be scaled, because optimizer works on 0..1 range and it doesn't know anything about scaling you use. Most significant parameters for optimizer are population size , number of generations (both affect computation time) and number of significant digits. All parameters are described in documentation, but if you need more detailed explanation, don't hesitate to ask.

It was quite general introduction for PID optimization using genetic algorithm. To help in anything more specific, I have to know more details on what do you want to control. But if you already have a model as you said, you are very close to make an optimization of PID gains.

[Interstellar]

Hey thank you so much for your effort and helping me.. I've just made PID controller and i m using very basic transfer function.. I'll try to make this and will let you know my status..

Thank you again for your help...

Short explanation first - this is continuation of ours private discussion, so I repeat some things already said.

Thanks for asking it - PID optimization is a very good use case for genetic algorithm. But you have to remember that it is only good for off-line optimization as it base on huge number of trials. So you have to have prepared a numerical model of your object of control - a program (VI in case of LabVIEW) which respond on control signal exactly the same way as real object would respond. To prepare it you have to know what phenomena drives your object, what are their equations and you have to implement them with proper coefficients (measured i.e.). To be more specific I have to know what exactly do you want to control with PID.

Once you have the model you have to insert it into simulated PID loop, so you have a model of whole control system with Kp, Kd and Ki coefficients as parameters (gains of proportional, differentiating and integrating blocks respectively). Than you have to determine what will be the measure of quality of regulation. Typically parameters of response on step-like excitation are used for this purpose:

You have to decide which of these parameters are more important, which are less important, which are not important at all and combine them into one number which is the higher, the better regulation is. It may be for example weighted sum: a*(1/rise_time)+b*(1/overshoot)+c*(1/settling_time), where a,b,c are the weights. In genetic algorithm such a number is called a fitness function and PID optimization process may be now described as: find such Kp, Kd, Ki which maximizes previously defined fitness function. You have to implement a fitness function as a VI which takes certain Kp, Kd and Ki parameters, makes a simulation of control system's response on step-like excitation, calculates quality parameters out of the response and combines them into final quality measure.

In Waptia you have to implement fitness function as a strictly typed VI. There is a special template in main Waptia directory (Fitness Function Template.vit):

Phenotype input (1D array of doubles) in terms of genetic algorithm is a set of parameters describing the system, which are the subject of optimization. In our case size of this array will be always 3 and Kp, Kd and Ki will be coded in it. Coded, because optimizer requires all parameters to be scaled to 0..1 range. So you have to know the expected ranges for optimized gains (you could determine them using i.e. Ziegler–Nichols method and some manual checking). Your fitness function VI could look like this:

Data and Init? inputs are not required in simplest approach, but they may not be deleted as VI must be strictly typed. You could use these inputs to control other parameters of the models which are not to be optimized (i.e. coefficients of equations of the model).

Code for actual optimization of PID gains is now as simple as:

Values from final solution have to be scaled, because optimizer works on 0..1 range and it doesn't know anything about scaling you use. Most significant parameters for optimizer are population size , number of generations (both affect computation time) and number of significant digits. All parameters are described in documentation, but if you need more detailed explanation, don't hesitate to ask.

It was quite general introduction for PID optimization using genetic algorithm. To help in anything more specific, I have to know more details on what do you want to control. But if you already have a model as you said, you are very close to make an optimization of PID gains.

[Interstellar]

Sir, what must be the output of the Fitness Function? Or what must be connected to the terminal Fitness Function of waptia.vi?

[vugie]

Sir, what must be the output of the Fitness Function? Or what must be connected to the terminal Fitness Function of waptia.vi?

This input is a reference to a strictly typed VI which realizes calculation of fitness. It's output is just a number which doesn't have any particular interpretation. It is a measure of how good is system described by DBL array on its input (the better system, the higher fitness).

[Interstellar]

Hey, This is the error i get after making it.. i cant figure out what the problem is...

[vugie]

You have to wire reference to fitness function VI, not its output.

The simplest way (but not too flexible) is: on block diagram, palette Application Control --> Static VI Reference - put it somewhere, then right-click on it and select "browse for path". In dialog find your fitness VI and confirm. Right-click on reference icon again and check "Strictly Typed VI Reference". Now you may wire it to Waptia.vi

Providing a reference means that Waptia knows what is your fitness VI and it is able to launch it by itself when it wants to and with any parameters. Strictly typed reference means that VI with specific connector pane is expected. BTW, fitness function VI is launched by Waptia (Generations_number * Population_size) times.

[Edit]

I saw that you use 0.001..0.1 range for one of parameters. It is a difference of two rows of order. In such case it is better to use logarithmic scaling to scale to 0..1 range.

[Interstellar]

I am new to labview.. And I have not familiar with strictly typed VI.. so can please help me on that too?

[vugie]

Almost everything you need to know about VI references is here:

http://labviewwiki.org/VI_Reference

http://labviewwiki.o...ll_By_Reference

Waptia internally uses Call by Reference mechanism

[Interstellar]

I am still not sure how to implement it.. this is what i get after implementing it..

[vugie]

I am still not sure how to implement it.. this is what i get after implementing it..

You dindn't make this:

Right-click on reference icon again and check "Strictly Typed VI Reference"

Little star will appear on the reference icon

[Interstellar]

Little star appeared but there is still some error!!

Little star appeared but there is still some error!!

Little star appeared but there is still some error!!

[vugie]

Upload your fitness VI then. I guess that you changed the connector pane (It must be exactly the same as in template)

[Interstellar]

Thank you so much for your help...

Yes, i changed the connector pane .. now its working fine.. but the problem is the result (the optimized value) by manual tuning is better than the GA method..

BTW what did you mean when you wrote "I saw that you use 0.001..0.1 range for one of parameters. It is a difference of two rows of order. In such case it is better to use logarithmic scaling to scale to 0..1 range."??

[vugie]

Thank you so much for your help...

Yes, i changed the connector pane .. now its working fine.. but the problem is the result (the optimized value) by manual tuning is better than the GA method..

BTW what did you mean when you wrote "I saw that you use 0.001..0.1 range for one of parameters. It is a difference of two rows of order. In such case it is better to use logarithmic scaling to scale to 0..1 range."??

What do you mean by "better"? Better by means of quality factor you defined (is the fitness function of manually tuned PID params higher than for optimized ones?) or just visually - response from manually tuned PID looks better on a chart?

Each optimizer (genetic or not) is at most as good as quality factor it optimizes. So if you feel that your parameters are better that optimized ones it could mean that quality factor you implemented in fitness VI reflects other criteria of "goodness" than you actually expect.

As for scaling. Your parameter changes from 0.001 to 0.1. Lets assume that you use single digit precision, so optimizer will choose from following values 0..0.9 with 0.1 step. Linear scaling to your range gives following actual values: 0.001, 0.011, 0.021, 0.031, 0.041, 0.051, 0.06, 0.07, 0.08, 0.09 (I just applied formula out = in * (0.1-0.001) + 0.001). I guess that for parameter that uses such a range difference between 0.001 and 0.011 (10 times) is much more significant than between 0.08 and 0.09 (1.1 times). If you would use logarithmic scaling (with formula out = 10 ^ (-2 * in - 1)) you get following actual values: 0.002, 0.003, 0.004, 0.006, 0.01, 0.016, 0.025, 0.04, 0.063, 0.1 which seem to be much better distributed.

[Interstellar]

By better i mean the rise time, overshoot and settling time is less in manual tunning than when it is GA optimized.. so i just want to ask is there some flaw in my coding or is the nature of GA?

or may be should i change the value of fitness weights?

[vugie]

By better i mean the rise time, overshoot and settling time is less in manual tunning than when it is GA optimized.. so i just want to ask is there some flaw in my coding or is the nature of GA?

or may be should i change the value of fitness weights?

Compare value of fitness for both solutions (you have to scale them to 0..1 using the same ranges as in optimization process and pass them directly to your fitness VI). If solution you consider as better has lower fitness, it means that quality function you implemented doesn't reflect your intentions (it may be caused by weights or by some error in calculation of rise time, overshoot, etc.).

If better solution has higher fitness (test it for several cases), maybe the evolution was too short or populations were too small. You may use Progress Notifier to observe how fitness grows with time. Typically there are long periods of stagnation interrupted with short periods of rapid grow. Try to play also with mutation rates.

But first of all make sure that your fitness VI reflects your feeling of "goodness".

There are also some tricks which could improve evolution process (such as using too high precision or introducing few genes with no specific function) but give significant effects for really high degree of freedom systems.

[Interstellar]

ok. I am changing the weights value.. can you tell me whats the criterion? I mean do the sum of all three weights be a constant. for example in GA i made i fixed the criterion that sum of all weights should be 1..

[vugie]

The only criterion is: the better system should have higher fitness. Weights not necessarily has to sum to 1. Even weighted sum is only one of possible approaches for calculating global quality factor. You give formula for the number, GA (and any other kind of optimizer) tries to find conditions which maximize it. Other possible approaches are i.e. weights with thresholds or introducing penalties for parameters outside expected range. Read about multi criteria optimization to have a broader look on possible strategies.

[Interstellar]

thanks a lot!!

[MrDigg]

Hi

Can i use GA to solve a simple maxima problem? Like i have a function f(x)=4x₁+3x₂ constrained by the following conditions

2x₁ + 3x₂ <=6

-3x₁ + 2x₂ <=3

2x₁ + x₂ <=4

0 <= x₁ <=2

[vugie]

Hi

Can i use GA to solve a simple maxima problem? Like i have a function f(x)=4x₁+3x₂ constrained by the following conditions

2x₁ + 3x₂ <=6

-3x₁ + 2x₂ <=3

2x₁ + x₂ <=4

0 <= x₁ <=2

Much more adequate method is to use Linear Programming Simplex Method.vi which is designed for solving exactly this kind of problems. Some background is here.

If you for some strange reason still want to use genetic algorithm - yes, it is possible. In fitness function you have to define some kind of penalty for each not satisfied inequality. But there is no general recipe for it. And it is not mathematically guaranteed that solution found will satisfy all inequalities (even if real solution exists). Waptia implementation of GA has also additional limitation: it doesn't handle not ranged variables (like x2 in your case).

[ariahs]

Hi

Can I use this GA in face recognition?