GPdotNET v4.0- Introduction


This is the first post in series of posts that describe upcomming version of GPdotNET v4.0. Besides lot of improvements of the current version, the main part isimplementation of neural networks and set of other optimization methods of machine learning.

1. Modelling with GPdotNET v4.0

GPdotNET Logo

GPdotNET Logo

GPdotNET is C#, open source artificial intelligence tool for applying Genetic Algorithm and Artificial Neural Networks in modeling, prediction, optimization and pattern recognitions. With GPdotNET you can solve various engineering problems from classic regression and approximation to linear programming transportation and location problems and other machine learning based problems. By providing the learning algorithms GPdotNET uses a data of the research or experimental measures to learn about the problem. The results of learning algorithms are analytical models which can describe or predict the state of the problem, or can recognize the pattern. GPdotNET is very easy to use, even if you have no deep knowledge of GA, GP or ANN, you can apply those methods in finding solutions. The project can be used in modeling any kind of engineering process, which can be described with discrete data, as well as in education during teaching students about evolutionary methods, mainly GP and GA, as well as machine learning mainly Artificial Neural Networks.
The typical process of modelling with GPdotNET can be described in 5 steps.

  1. Choosing the type of the Solver: The first step is choosing the type of the solver. Which solver you will use depends on your intention what you want to do. For example if you want to make model for your experimental measurement you have several options which depend of your experimental data and the method you want to use. In GPdotNET you can use Genetic Programming or Neural Nets for modelling and prediction experimental data. But this is not strictly separate as may look on the flowchart below. That means that you can user Neural Networks for prediction, but training algorithm can be based on  Genetic Algorithm or Particle Swarm Optimization or Back Propagation algorithm.
  2. Loading your experimental data: GPdotNET uses powerful tool for importing your experimental data regardless of the type of data. You can import your numerical, binary or classification data. GPdotNET can automatically define classes, or format numerical data with floating or comma separated decimal values. More info can be find in Section 2.
  3. Setting Learning Parameters. After data is loaded and prepared successfully, you have to set parameters for the selected method. GPdotNET providers various parameters for each method, so you can set parameters which can provides and generates best output model.
  4. Searching for the solution: GPdotNET provides visualization of the searching solution so you can visually monitor how GPdotNET finds better solution as increasing the iteration number. If you provide data for testing calculated model, you can also see simulation of prediction.
  5. Saving and exporting the results: GPdotNET provides several options you can choose while exporting your solution. You can export your solution in Excel or text file, as well as in Wolfram Mathematica or R programming languages.

As would be seen, working in GPdotNET follows the same procedures regardless of the problem type. That means you have the same set of steps when modelling with Genetic Programming or Neural Networks. In fact GPdotNET contains the same set of input dialogs when you try to solve Traveling Salesman Problem with Genetic Algorithm or if you try to solve handwriting recognition by using Backpropagation Neural Networks. All learning algorithms within GPdotNET share the same UI.

The picture below shows the flowchart of the modelling in GPdotNET. The five steps described previously are depicted in the graphical forms surrounded with Start and Stop elements.

Modeling in GPdotNET v4.0

Modeling in GPdotNET v4.0

Besides parameters specific to learning algorithm, GPdotNET provides set of parameters which control the way of how iteration process should terminates as well as how iteration process should be processed by means of parallelization to use the multicore processors. During the problem searching GPdotNET records the history, so you can see when the best solution is found, how much time pass since last iteration process started, or how much time is remain to finish currently running iteration process.
Due to the fact that GP is the method which requires lot of processing time, GPdotNET provides parallelization, which speed up the process of searching. Enabling or disabling the parallelization processing is just a click of the button.

1.1 GPdotNET Open source project

From developer point of view GPdotNET is .NET (Mono) application written in C# programming language which can run both on Windows and Linux based OS, or any OS which supports Mono framework. Project started in 2006 within postgraduate study for modeling and optimization with evolutionary algorithms. As open source project, GPdotNET is first published on November 5 2009 on codeplex.com. The project is licensed under GNU Library General Public License (LGPL). For information about license and other kind of copyright please see http://gpdotnet.codeplex.com/license. The project is hosted at http://gpdotnet.codeplex.com. Main place for all news, documentation and code changes is my blog site at https://bhrnjica.wordpress.com/gpdotnet.

1.2 How to citate GPdotNET

GPdotNET is used from all around the world, in scientific papers, journals, books, for diploma works, master thesis or Dissertations. It is free to use GPdotNET with proper citation. So if you want to use the GPdotNET you need the right way to citate the tool.

Use this citation example in your paper, book etc.:

[1] B. I. Hrnjica, GPdotNET V4.0- artificial intelligence tool [Computer program], http://gpdotnet.codeplex.com, accessed {date}.

Or

[1] Bahrudin I. Hrnjica, GPdotNET V4.0 – artificial intelligence tool [Computer program], http://gpdotnet.codeplex.com, accessed {date}.

Advertisements

Announcing Neural Networks in GPdotNET


gpdotnet_ann1

Last few months I was playing with Artificial Neural Network (ANN) and how to implement it in to the GPdotNET. ANN is one of the most popular methods in Machine Learning, specially Back Propagation algorithm. First of all, the Artificial Neural Network is more complex than Genetic Algorithm, and you need to dive deeper in to math and other related fields in order to understand some of the core concept of the ANN. But likely there are tons of fantastic learning sources about ANN. Here is my recommendation of ANN learning sources:

First of all there are several MSDN Magazine articles about ANN and how to implement it in C#.

1. Dive into Neural Networks

2. Classification and Prediction Using Neural Networks

3. Neural Network Back-Propagation for Programmers

If you want to know what’s behind the scene of ANN, read this fantastic online book with great animations of how neuron and neural networks work.

1. Neural Networks and Deep Learning,  by Michael Nielsen.

There is a series you tube video about ANN.

1. Neural Networks Demystified [Part 1: Data and Architecture]

Open source libraries about ANN in C#:

1.  AForge.NET. – Computer Vision, Artificial Intelligence, Robotics.

2. numl – Common Machine Learning Algorithms by Seth Juarez

The first GPdotNET v4.0 beta will be out very soon.

Citations of GPdotNET


This is updated blog post about GPdotNET citation

Bahrudin Hrnjica Blog

gpdotnetv3beta2

Recently I have googled about GPdotNET to find out how people use GPdotNET. I was surprised that there are plenty of sites which are published GPdotNET as freeware software. I have also found several scientific papers which citated GPdotNT as well. Some other people used it as elegant example in their  lessons. Some students used GPdotNET in seminars and diploma works, master and phd thesis.

All in all I was very excited about it. So lets list some interested web sites and scientific paper which mentioned GPdotNET.

1.  Softpedia http://www.softpedia.com/get/Science-CAD/GPdotNET.shtml

2. StackOverflow : http://stackoverflow.com/questions/14761910/genetic-evolution-of-source-code/14762077#14762077

3.  Genetic Programming article:  http://www.answers.com/topic/genetic-programming

4.  Teaching lessons from  Faculty of Informatics, Burapha University, Thailand:  Evolutionary Algorithms Applied to Finance

5.  Karlsruhe Institute of Technology Paper Work: Evolutionary Algorithms.

6. Scientific paper, ACS Vol.14:  Use of Learning Methods to Improve Kinematic Models

7. Scientific paper, JPE Vol.15: Modeling of Discharge Energy in Electrical Discharge…

View original post 103 more words

Brood Recombination new feature in GPdotNET


As currently implemented GPdotNET has classic crossover implementation without any intelligent way to exchange genetic materials. In most time classic crossover operation is destructive operation wasting lot of good genetic materials. By including brood recombination crossover can be slightly improved.

Brood recombination simple repeats crossover operation several time on the same parents, with different crossover points. After fitness evaluation of offspring, the best two child are kept and others are discarded. On that way there is a better chance to get better child than with classic crossover. The picture below graphically describes brood recombination.

brood_recombination

Brood Size – new GPdotNET parameter

The first feature which will be implemented is manually setting the Brood Size of crossover. By adding Brood Recombination, we will increase possibility that two chromosomes will exchange the best genetic material they have.

brood_recombination_parameter

The next feature will be brood size which will be generating dynamically and will be dependent of the generation number.

GPdotNET v3 released


releasegpdotnetv3_sl2

I am proud to announce after almost full year of working on GPdotNET v3 is finally released today. The first post about GPdotNET v3 was on February this year when the TSP problem announced. The next direction was solving assignment problem because is similar to TSP. At the finally stage of developing solver for version 3 was transportation problem which represent the most complex implementation in GPdotNET regarding representation of chromosome.

Beside introduction to the new solvers GPdotNET v3 contains new exported format which is implemented when I was working my PhD thesis.

GPdotNET User manual is also completed with all new functionalities introduced in version 3.

releasegpdotnetv3_sl1

GPdotNET v3 is published with ClickOnce deployment, and can be downloaded at http://gpdotnet.codeplex.com.

Solving Assignment Problems (AP) in GPdotNET


8.1. Introduction to AP

AP deal with the question how to assign n objects to m other objects in the best possible way. Best possible way can be represent optimal (with minimum or maximum) value of the objective function. Most of the APs have m>n which means that assignment operation deals with not equally numbers of objects. All such a problems can be transformed to m=n, by adding fake assignment operations.

One example of AP can be formulate as follow: Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the “cost” of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth dummy task can be invented, perhaps called “sitting still doing nothing”, with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.

Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

The formal definition of the assignment problem (or linear assignment problem) is

Given two sets, A and T, of equal size, together with a weight function C: A × T → R. Find a bijection f: A → T such that the cost function:

equation-01

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

equation-02

Subject to the constants

 equation-03

The variable represents the assignment of agent to task, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.

8.2 AP in GPdotNET

Solving AP with GPdotNET begins by clicking “New” button from Application Bar, and selecting AP Solver from New GPModel dialog (see pic. below).

Figure 14 Creating new AP Model in GPdotNET

After clicking OK button, GPdotNET shows several tab pages similar on the following picture.

The first step in defining AP in GPdotNET is loading data of the problem.

8.2.1 Preparing and loading data in AP

As we can see from introduction data for AP problem must be in matrix form, so the following picture can represent proper format of AP data.

In GPdotNET v3 and late you can put comments in data file. The picture above contains three lines of comments which will not be loaded. Then we have 5 lines represent rows in AP. Columns are divided by semicolon. From the picture above it can be seen “M” letter in the middle of the data. “M” represent maximum number (infinity number). Other symbol which can be seen in data is “L” which represents the minimum value (negative infinity). Decision when to put M or L letter depends of the solution.

  1. If we want to find minimum cost of AP and want to put fake row in order to define closed solution, we can put M letter.
  2. If we want to find maximum cost of AP and want to put fake row in order to define closed solution, we can put L letter.

8.3. Running AP problem with GPdotNET

When the data is loaded we can start by defining GP parameters and start with finding solution. The process is identical like other, so this step we will not be describe. After we start finding solution by clicking START button, we can see that GPdotNET find solution very quickly. The picture below show solution for problem we have described above.

As we can see from the picture above, result is shown as array of number. Actually, result is presented as vector, which position of number represent column, and the value represent the row of started problem. From the picture above result is [2 5 1 4 3]
which means the following results:

Vector number represent the row index, and position means column index.