Blog Archives

Function optimization with Genetic Algorithm by using GPdotNET


Content

1. Introduction
2. Analytic function optimization module in GPdotNET
3. Examples of function optimizations
4. C# Implementation behind GPdotNET Optimization module

Introduction

GPdotNET is artificial intelligence tool for applying Genetic Programming and Genetic Algorithm in modeling and optimization of various engineering problems. It is .NET (Mono) application written in C# programming language which can run on both Windows and Linux based OS, or any OS which can run Mono framework. On the other hand GPdotNET is very easy to use. Even if you have no deep knowledge of GP and GA, you can apply those methods in finding solution. The project can be used in modeling any kind of engineering process, which can be described with discrete data. It is also be used in education during teaching students about evolutionary methods, mainly GP and GA. GPdotNET is open source project hosted at http://gpdotnet.codeplex.com

With releasing of  GPdotNET v2 it is also possible to find optimum for any analytic function regardless of independent variables. For example you can find optimum value for an analytically defined function with 2, 5, 10 or 100 independent variables. By using classic methods, function optimization of 3 or more independent variables is very difficult and sometimes impossible. It is also very hard to find optimum value for functions which are relatively complex regardless of number of independent variables.
Because GPdotNET is based on Genetic Algorithm we can find approximated optimum value of any function regardless of the limitation of number of independent variables, or complex definition. This blog post is going to give you a detailed and full description how to use GPdotNET to optimize function. Blog post will also cover C# implementation behind optimization proce by showing representation of Chromosome with real number, as well as Fitness calculation which is based on Genetic Programming tree expression. In this blog post it will also be presented several real world problem of optimization which will be solved with GPdotNET.

Analitic Function Optimization Module in GPdotNET

When GPdotNET is opened you can choose several predefined and calucalted models from various domain problems, as weel as creating New model among other options. By choosing New model new dialog box appears like picture below.

image1

By choosing Optimization of Analytic Function (see pic above) and pressing OK button, GPdotNET prepares model for optimization and opens 3 tab pages:

  1. Analytic function,
  2. Settings and
  3. Optimize Model.

Analytic function

By using “Analytic function” tab you can define expression of a function. More information about how to define mathematics expression of analytic function can be found on this blog post.

image2

By using “Analytic definition tool” at the bottom of the page, it is possible to define analytic expression. Expression tree builder generates function in Genetic Programming Expression tree, because GPdotNET fully implements both methods. Sharing features of Genetic programming  in Optimization based Genetic Algorithm is unique and it is implement only in GPdotNET.

When the process of defining function is finished, press Finish button in order to proceed with further actions. Finish button action apply all changes with Optimization Model Tab. So if you have made some changed in function definition, by pressing Finish button changes will be send to optimization tab.
Defining expression of function is relatively simple, but it is still not natural way for defining function, and will be changed in the future. For example on picture 2, you can see Expression tree which represent:

f(x,y)=y sin{4x}+1.1 x sin{2y} .

Setting GA parameters

The second step in optimization is setting Genetic Algorithm parameter which will be used in optimization process. Open the Setting tab and set the main GA parameters, see pic. 3.

image3

To successfully applied GA in the Optimization, it is necessary to define:

  1.  population size,
  2. probabilities of genetic operators and
  3. selection methods.

These parameters are general for all GA and GP models. More information about parameters you can find at http://bhrnjica.net/gpdotnet.

Optimize model (running optimization)

When GA parameters are defined, we can start with optimization by selecting Optimization model tab. Before run, we have to define constrains for each independent variables. This is only limitation we have to define i  order to start optimization. The picture below shows how to define constrains in 3 steps:

  1.  select row by left mouse click,
  2. enter min and max value in text boxes
  3. Press update button.

Perform these 3 actions for each independent variable defined in the function.

image4

When the process of defining constrains is finished, it is time to run the calculation by pressing Optimize button, from the main toolbar(green button). During optimization process GPdotNET is presenting nice animation of fitness values, as well as showing current best optimal value. The picture above shows the result of optimization process with GPdotNET. It can be seen that the optimal value for this sample is f_{opt}(9.96)=-100.22.

image5

Examples of function optimization

In this topic we are going to calculate optimal value for some functions by using GPdotNET. Zo be prove that the optimal value is correct or very close to correct value we will use Wolfram Alpha or other method.

Function: x sin(4x)+1.1 x sin(2y)

GP Expression tree looks like the following picture (left size):

image6 image7

Optimal value is found (right above picture) for 0.054 min, at 363 generation of total of 500 generation. Optimal value is f(8.66,9.03)=-18.59.

Here is Wolfram Alpha calculation of the same function. http://www.wolframalpha.com/input/?i=min+x*sin%284*x%29%2B+1.1+*y*+sin%282+*y%29%2C+0%3Cx%3C10%2C0%3Cy%3C10

Function:  (x^2+x)cos(x),  -10≤x≤10

GP expression tree looks like the following picture (left size):

image9image10

Optimal value is found for 0.125 min, at 10 generation of total of 500 generation. Optimal value is F(9.62)=-100.22.

Here is Wolfram Alpha calculation of the same function. http://www.wolframalpha.com/input/?i=minimum+%28x%5E2%2Bx%29*cos%28x%29+over+%5B-10%2C10%5D

Easom’s function fEaso(x1,x2)=-cos(x1)•cos(x2)•exp(-((x1-pi)^2+(x2-pi)^2)), -100<=x(i)<=100, i=1:2.

GP expression tree looks like the following picture (left size):

image12image13

Optimal value is found for 0.061 min, at 477 generation of total of 500 generation. Optimal value is F(9.62)=-1, for x=y=3.14.

Function can be seen at this MatLab link.

C# Implementation behind GPdotNET Optimization module

GPdotNET Optimization module is just a part which is incorporated in to GPdotNET Engine. Specific implementation for this module is Chromosome implementation, as well as Fitness function. Chromosome implementation is based on  floating point value instead of classic binary representation. Such a Chromosome contains array of floating point values and each element array represent function independent variable. If the function contains two independent variables (x,y) chromosome implementation will contains array with two floating points. Constrains of chromosome values represent constrains we defined during settings of the optimization process. The following source code listing shows implementation of GANumChrosomome class in GPdotNET:

public class GANumChromosome: IChromosome
 {
 private double[] val = null;
 private float fitness = float.MinValue;
 //... rest of implementation
}

When the chromosome is generated array elements get values randomly generated between min and max value defined by function definition. Here is a source code of Generate method.

///
/// Generate values for each represented variable
///
public void Generate(int param = 0)
{
	if(val==null)
		val = new double[functionSet.GetNumVariables()];
	else if (val.Length != functionSet.GetNumVariables())
		val = new double[functionSet.GetNumVariables()];

	for (int i = 0; i < functionSet.GetNumVariables(); i++)
		val[i] = Globals.radn.NextDouble(functionSet.GetTerminalMinValue(i), functionSet.GetTerminalMaxValue(i));

}

Mutation is accomplish when randomly chosen array element randomly change itc value. Here is a listing:

///
///  Select array element randomly and randomly change itc value
///
public void Mutate()
{
	//randomly select array element
	int crossoverPoint = Globals.radn.Next(functionSet.GetNumVariables());
	//randomly generate value for the selected element
	val[crossoverPoint] = Globals.radn.NextDouble(functionSet.GetTerminalMinValue(crossoverPoint), functionSet.GetTerminalMaxValue(crossoverPoint));
}

Crossover is little bit complicated. It is implemented based on Book Practical Genetic Algoritms see pages 56,57,48,59. Here is an implementation:

///
/// Generate number between 0-1.
/// For each element array of two chromosomes exchange value based on random number.
///
///
public void Crossover(IChromosome ch2)
{
	GANumChromosome p = (GANumChromosome)ch2;
	int crossoverPoint = Globals.radn.Next(functionSet.GetNumVariables());
	double beta;
	for (int i = crossoverPoint; i < functionSet.GetNumVariables(); i++)
	{
		beta = Globals.radn.NextDouble();
		val[i] = val[i] - beta * (val[i] - p.val[i]);
		p.val[i] = p.val[i] + beta * (val[i] - p.val[i]);
	}
}

Fitness function for Optimization is straightforward, it evaluates each chromosome against tree expression. For minimum the better chromosome is lower value. For maximum better chromosome is the chromosome with higher fitness value. Here is a implementation of Optimizatio Fitness function:

///
/// Evaluates function agains terminals
///
///
///
///
public float Evaluate(IChromosome chromosome, IFunctionSet functionSet)
{
	GANumChromosome ch = chromosome as GANumChromosome;
	if (ch == null)
		return 0;
	else
	{
		//prepare terminals
		var term = Globals.gpterminals.SingleTrainingData;
		for (int i = 0; i < ch.val.Length; i++)
			term[i] = ch.val[i];

		var y = functionSet.Evaluate(_funToOptimize, -1);

		if (double.IsNaN(y) || double.IsInfinity(y))
			y = float.NaN;

		//Save output in to output variable
		term[term.Length - 1] = y;

		if (IsMinimize)
			y *= -1;

		return (float)y;
	}
}

Summary

We have seen that Function optimization module within GPdotNET is powerful optimization tool. It can find pretty close solution for very complex functions regardless of number of independent variables. Optimization module use Genetic Algorithm method with floating point value chromosome representation described in several books about GA. It is fast, simple and can be used in education as well as in solving real problems. More info about GPdotNET can be found at http://bhrnjica.net/gpdotnet.

SignalR Online Counter Sample


SignalR is a web technology for building real time ASP.NET web applications. SignalR is an open source project which simplifies the complicated tasks of creating bidirectional communication between clients and server. SignalR is founded on top of WebSockets, as well as other similar technologies.

As you probably know WebSockets introduced a new way to communicate between server and clients, and it is specified by the HTML5 API specification. When it is available SignalR will use this technology, otherwise it will use what is supported by your system. SignalR also provides a high-level API for server communication to client RPC (call JavaScript functions in clients’ browsers from server-side .NET code) in ASP.NET applications, as well as adds useful hooks for connection management, e.g., connect/disconnect events, grouping connections, authorization. More information about SignalR can be found on the official web site for SignalR.

For this post I have implemented a very simple SignalR Web Application which counts how many users are online, so it is called Online Counter. Online Counters are a very popular component for the web.

So let’s start with the implementation.

  1. Open Visual Studio 2012, and create new Empty Web Application called OnlineCounter.

SignalR_image1

The first thing we will do is adding SignalR reference for the clients (JavaScript files) and the Server (.NET Components).

2. So open NuGet Manager console and input the following command: Install-Package Microsoft.AspNet.SignalR –Pre

SignalR_image2

After we added SignalR references, we are implementing Server side of the SignalR HitCounter Web Application.

3. Add a new class named HitCounter.

SignalR_image3

The HitCounter class must be derived from the Hub. More info about Hub and other SignalR components you can find on the official site.

The implementation for the HitCounter class is shown below:

public class HitCounter : Hub
{

 private static int clientCounter = 0;

 public void Send()
 {
 string message = "";
 // Call the recalculateOnlineUsers method to update clients
 if(clientCounter<2)
 message = string.Format("Currently {0} user is online.",clientCounter);
 else
 message = string.Format("Currently {0} users are online.", clientCounter);

 Clients.All.recalculateOnlineUsers(message);
 }

 ///
/// register online user
 ///
 ///
 public override System.Threading.Tasks.Task OnConnected()
 {
 clientCounter++;
 return base.OnConnected();
 }

 ///
/// unregister disconected user
 ///
 ///
 public override System.Threading.Tasks.Task OnDisconnected()
 {
 clientCounter--;
 return base.OnDisconnected();
 }
}

As you can see from the source code, we have override two virtual methods when user is reach the page, and also when the user live the page. The Send method is responsible to send message to all available clients.

We need also to implement Global Application Class to register this hub.

4. Add Global Application Class in to your project, and register MapHubs, as picture shows below.

SignalR_image4

The following code implementation shows how to register Hub in Global App Class.

public class Global : System.Web.HttpApplication
{

    protected void Application_Start(object sender, EventArgs e)
    {
        // Register the default hubs route: ~/signalr/hubs
        RouteTable.Routes.MapHubs();
    }
//rest of the implememtation.....

After we implemented Services side of SignalR, we need to implement client side.

5. Add new html web page in to project.

SignalR_image6

6. Include standard set of JavaScript files necessary for SignalR client to run.

<!--Script references. -->
<!--Reference the jQuery library. -->
<script type="text/javascript" src="Scripts/jquery-1.6.4.min.js"></script><!--Reference the SignalR library. --><script type="text/javascript" src="Scripts/jquery.signalR-1.0.0-rc2.js"></script>
<!--Reference the autogenerated SignalR hub script. -->
<script type="text/javascript" src="/signalr/hubs"></script>

7. Send Notification to Server that the new User is reached the page.
8. Implemet JavaScript code to receive recalculateOnlineUser event sent from server.

    $(function () {

        // Declare a proxy to reference the hub.
        var counter = $.connection.hitCounter;

        // register online user at the very begining of the page
        $.connection.hub.start().done(function () {
            // Call the Send method on the hub.
            counter.server.send();
        });

        // Create a function that the hub can call to recalculate online users.
        counter.client.recalculateOnlineUsers = function (message) {

            // Add the message to the page.
            $('paragraph').text(message);
        };

    });

9. Compile and run the code. Open two Browser Windows. You can see that SignalR has counted two online users.

SignalR_image7

Source code for this blog post demo you can find below.

How to convert your old sequential code in to async


There are plenty of ansyc samples over the internet, and most of them are different and not satisfy your requirements. Actually, async pattern depends of its creator, and can be implement on various ways. It is important to understand the async pattern in order to use it. Only on this way, you can stop searching for exact sample you need, and start coding your own async code.  More that year ago, I wrote simple blog post about async pattern (part 1 and part 2) (Bosnian language), and also wrote how to call Entity Framework with async pattern as well.

Today I am going to show you how old synchronous code block convert in to asynchronous. I think it is interesting because async pattern can improve your existing applications on various ways. First of all async pattern can increase responsiveness of  an application, performance, etc.

First of all, create simple Windows Forms sample and implement synchronous code.This will represent our old application, in which we are going to implement new programming paradigm.

1. Create Windows Forms Project, Name it “WinFormsAsyncSample

2. Design your main form (Form1.cs) exactly as picture shows below, and implement events.

As picture shows we have few labels, one text box, one progress bars, and two buttons.

Note: At the end of the blog you can download both versions (nonasync and async) of this sample.

The sample application calculates how many prime numbers exist in range. You need to enter number, press run button. The program starts counting. The progress bars informs user status of counting.

Lets see the implementation of runBtn_Click event:

private void btnRun_Click(object sender, EventArgs e)
{
    if(!int.TryParse(textBox1.Text,out m_number))
        m_number= 1000000;

    textBox1.Text = m_number.ToString();
    progressBar1.Maximum = m_number;
    progressBar1.Minimum = 0;
    progressBar1.Value = 0;

    //call start calculation
    startCounting();
}

At the beginning of the btnRun_Click we prepare progressBar, and also convert text from textbox in to int type.At the end of the function startConting method is called. Here is the source code of the method:

private void startCounting()
{
    int counter=0;
    for(int i=2;i<m_number; i++)
    {
        bool retVal= IsPrime(i);
        progressBar1.Value++;
        if (retVal)
        {
            counter++;
            label3.Text = "Result is: " + counter.ToString();
        }
    }
}

The method is very simple. It iterates from 2 to specified number by calling helper method IsPrime (see source code of the blog post) to check if certain number is prime. Then the method increased the counter variable and tried to update label about current count value.  If  you run the sample and press run button, you can see that the application is not responsive on user input, and represent classic sequential, synchronous single thread application.

Now I am going to show how this implementation can be converted in to async with minimum code changes.We are going to change only startCounting method, other code will remain the same. Explanation is divided in only 3 steps, which is enough to convert our code in to full async pattern.

  • Put async keyword right after public modifier of startCounting method.

Explanation: Every method which implements async patter needs to be decorated with async.

  • Put sequential implementation in to Task action, and wait.

Explanation: With this, you define a Task object which will run the code without blocking main thread. The simplest implementation is the following:

private async void startCalculation()
{
    var task = new Task(() =>
        {
            int counter = 0;
            for (int i = 2; i < m_number; i++)
            {
                bool retVal = IsPrime(i);

                this.Invoke((Action)(()=>
                {
                    progressBar1.Value++;
                    if (retVal)
                    {
                        counter++;
                        label3.Text = "Result is: " + counter.ToString();
                    }

                }));
            }
        });

    task.Start();
    await task;
}

Now if you run the sample, you have fully asynchronous implementation. Main thread is free and can receive user input. So this is the simplest way how to convert your sync code in to async. This is the case when Task object create another thread in order to execute the code. That’s why we called this.Invoke method in order to set controls properties progressBar.Value and label3.Text. Everything else remain the same as in previous implementation.

  • Create global variable of type CancellationTokenSource and call Cancel method from Cancel Event handler.

Explanation: On this way we can cancel counting at any time.With this case we need to implements extra code in our previous implementation like the following.

private async void RunProces()
{
    if (m_IsRunning)
        return;
    m_IsRunning = true;
    int counter=0;
    if (m_ct != null)
    {
        m_ct.Dispose();
        m_ct = null;
    }
    m_ct = new CancellationTokenSource();

    var task = new Task(() =>
        {
            for (int i = 0; i < m_number; i++)
            {
                bool retVal = IsPrime(i);

                this.Invoke((Action)(()=>
                {
                    progressBar1.Value++;
                    if (retVal)
                    {
                        counter++;
                        label3.Text = "Result is: " + counter.ToString();
                    }

                }));

                if (m_ct.IsCancellationRequested)
                {
                    m_IsRunning = false;
                    return;
                }
            }
        }, m_ct.Token);

    task.Start();
    await task;
}

With the last code implementation you have full of async patter in yur old application.

In this blog post I have tried to explain as simple as possible the way how you can convert you old sync code in to new async programming pattern.

Source code sample used in this blog post:

On this link you can find sequential version of the sample.

On this link you can find the final solution of async pattern.


			

Golden Ratio and GPdotNET v2 User Interface


First of all, I am not a designer. In fact I don’t think I can design anything beautiful. Mostly, if I want to design something first asked some of my friends or people who knows about design, before decided to do. So design implementation of GPdotNET v2 was very frustrated for me. Anything I have implemented, I thought it was not so good. I still think that the current design of GPdotNET v2 is not something which I can say very well. But something interesting happen while I have designed current UX. I knew if something needs to be designed well, it must be based on golden ratio. So I have decided to implement golden ration anywhere where is possible in the app.

This blog post is going to present one approach of implementation of golden ratio in Application, as a good recipe for design. If you don’t know what is golden ratio you can found on this link.

So let’s first see the Start Screen.

Start Screen of GPdotNET

The first implementation of golden Ratio was dimension of the main window. So when you open GPdotNET, the size of initial Window is size=(932:579) which means that the height=579, and width=579*1,61=932, which is depicted on picture below as well.

Then I concentrate on my main toolbar to see if possible to implement golden ratio there. So if you look for example Common group, you can see that the width and height are designed by golden ratio, as well as height = width=H/Φ of tool button.

I have also implement golden ration to parts of group bar. The number a, b, c are implemented based on golden ratio on the following way: c=(a+b)*Φ, b=a*Φ (see picture below).

Other group bars are also implemented with golden ratio by simple adding half width of Common group toolbar for each additional tool button.

Create new Model Dialog

Other full implementation of golden ration was in Create New Dialog
From picture you can see that the size of dialog is based on golden Ration, as well as parts of the dialog. One interesting thing is that the position of Cancel and OK buttons are also based on golden ratio. Length of line a, is the same as length b multiple by Φ.

Export Dialog

Export dialog is pretty simple so golden ratio is implemented in 3 elements height (a) of ListBox, height (b) and width (c) of dialog in relations b=a*Φ , c= b*Φ, which you can see from the picture below.

I don’t know is my design is better than previous but I know you can find some interesting proportions in form of golden ration. :)

Follow

Get every new post delivered to your Inbox.

Join 538 other followers