Category Archives: GPdotNET
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.
GPdotNET v3 is published with ClickOnce deployment, and can be downloaded at http://gpdotnet.codeplex.com.
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:
Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:
Subject to the constants
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.
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.
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.
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.
3. Genetic Programming article: http://www.answers.com/topic/genetic-programming
4. Scientific paper from Robotics: Use of Learning Methods to Improve Kinematic Models
5. Teaching lessons from Faculty of Informatics, Burapha University, Thailand: Evolutionary Algorithms Applied to Finance
6. Karlsruhe Institute of Technology Paper Work: Evolutionary Algorithms.
7. Scientific paper from Mechanical engineering: Modeling of Discharge Energy in Electrical Discharge Machining by the use of Genetic Programming
8. Thermophysics 2012 Conference Proceedings, Slovak Republic: Evolution algorithms as toolfor optimization of water vapour transport properties of cellular concrete.
9. Scientific paper from Mechanical engineering: Application Of Neuro Fuzzy Systems and Genetic Programming for Modelling Surface Roughness in Electrical Discharge Machining
10. Scientific paper from Mechanical engineering: Aspects regarding the use of Genetic Programming in modelling the cutting process
During summer I found few bugs in GPdotNET, as well as made improvements of existing features.
Before final release of GPdotNET which will be at the end of the year, I have decided to make public release in form of Beta 2 version. This is second pre-release version of GPdotNET v3, which brings a set of new modules and solvers in Linear programming field like, assignment and transportation problems.
In this version you can find some improvements and bug fixes:
1. Implemented improvements IN TFS, Asigment and Transportation problems solver,
2. Improvement in drawing S-Expression in GP model,
3. Bug fix when user defined more that 10 random constants,
4. Bug in background when saving S-expression as png file.
5. Tested compatibility with Visual Studio 2013.
The beta 2 version will be available for download today at http://gpdotnet.codeplex.com . For those who have click one installation of the beta 1 version, they will be get update automatically from codeplex site.