Monthly Archives: October 2011
Skrgic Selection in GPdotNET
Introduction
This document presents Skrgic Selection Method, the one of several selection methods in GPdotNET. While I was developing GPdotNET I have had several conversation with my friend Fikret Skrgic (master in computer scinence and math) regarding selection in Evolutionary algorithms. He is an incredible man, and in just a few minutes while I was describing to him what I want from a new way of selection, he came out with the basic idea of the new selection method. After that time in just a few mails I had a new selection method ready for implementation in GPdotNET. I gave the name to the new selection method by his surname. It is a little thankfulness to him.
In the flowing text it will be presented the idea behind Skrgic Selection.
Liner Skrgic Selection (LSS)
The Idea behind this selection is based on chromosome fitness. The rule is simple: The bigger chromosome fitness gives bigger chance to select better chromosome. In Population, chromosomes are already sorted from best to worst chromosomes.
The process of selection is the following:
- Find the maximum and minimum fitness value from the population.
- The best chromosome (maximum fitness) has position 0 in the population (zero based index), and the worst chromosome has index
.
- Let’s give them name as
and
respectively.
- Choose random number
between
and
.
- Choose random chromosome from the Population
.
- Compare the values of
and
. If the
is greater than
, select
.
- Repeat steps 3 and 4 until you select one chromosome.
- Repeat steps 2,3,4,5 until you select
chromosomes.
The following picture shows graph of linear Skrgic selection:
Nonlinear Skrgic Selection (NSS)
In LSS we have linear graph of selection probability. This means that if we have chromosome with fitness value, and another chromosome with
fitness value, the probability of selection of two chromosomes is
and
respectively. This means that probability of selection is growing linearly.
If we want to change probability between chromosomes we can define a factor to be like selection pressure on whole chromosomes in the population. So let the k be a real value, and define the fitness of each chromosome as:
,
where:
– fitness value of the chromosome,
– maximum fitness value(fitness of the best chromosome of the population),
– selection pressure,
– nonlinear fitness value of the chromosome.
We can conclude that the maximum nonlinear fitness value of the best chromosome is given by:
.
For various value of parameter we can define graph of probability selection like on the following picture:
On the picture above we can see if we get the standard Linear Skrgic Selection (LSS). We can also conclude that there is a fitness value when the probability of selection is constant and not depends of parameter
. Very interesting graph is when the
. In this case the selection probability of the worst and the best chromosome are equal.
Asynchronous Call of Entity Framework in C# 5.0
Since there is asynchronous pattern in C# 5.0 and .NET 4.5, we can think about how to apply this pattern in to EntityFramework. Natively EntityFramework doesn’t support of asynchronous calls, and you have to use classic DBReader to achieve it. In previous post about WCF and async and await keyword, we saw that asynchronous patter is already implemented when we add service in to client as Service Reference. Entity Framework probably will not have such an option, and you will have to deal with custom implementation.
If we look in to implementation of DBReader and SqlReader in .NET 4.5 we can see that there is also async implementation as well. We don’t need to use begin/end execute reader ayn more. It is a good idea to try to implement similar pattern in Entity Framework.
So, first create a new project in Visual studio 11 DP, and create sample database, so we can test our async solution against EntityFramework.
- Create new WPF project in Visual Studio 11 Developer Preview.
- Give it a name AsyncEntityFrameworkDemo.
- Within VS 11 DP open Server Explorer and create new Database DemoDb.
- Create table Customers, with columns show on picture below
After you create a Table you need to insert a large number of rows that the retrieving data takes at least several seconds.
For that demo I have inserted about 500.000 rows. You can download my database with the Demo sample too.
After you prepare database, let’s create Entity Framework model. After that drag some controls to the MainPage.xaml designer like picture shows. You need to drag one DataGrid, Button and some other controls that we can test unblocking thread while data is retrieving from database.
Define OnLoaded event handle of the MainPage. In the event method we are going to call asynchronous implemented method.
private void OnLoaded(object sender, RoutedEventArgs e)
{
LoadCustomersAsync();
}
The implementation of LoadCustomersAsync(); is showed of the following listing.
///
<summary> /// Retieves data asynchoronous by calling EntityFramework Translate method. It uses the DbCommand and ExecuteReaderAsync
/// for retreiving data from database
/// </summary>
private async void LoadCustomersAsync()
{
using (DemoDbEntities ent = new DemoDbEntities())
{
IDbConnection conn = (ent.Connection as EntityConnection).StoreConnection;
conn.Open();
using (DbCommand cmd = (DbCommand)conn.CreateCommand())
{
var query = from p in ent.Customers
where p.Name.Contains("Name") && p.Surname.Contains("Surname") && (p.Name+p.Surname).Length>3
select p;
//Above linq code convert to SQL statement
string str = ((ObjectQuery)query).ToTraceString();
cmd.CommandText = str;
//New method in C# 5.0 Execute reader async
var task= await cmd.ExecuteReaderAsync();
//translate retieved data to entity customer
var cust1 = await Task.Run(
() => ent.Translate(task).ToList());
//put retrieved data to obesrvable coll
var data = new ObservableCollection(cust1);
//Notify about collection changed
Customer_CollectionChanged(data);
}
}
}
The method is constructed of calling ExecuteReaderAsync: – the new asynchronous implementation of the SqlReader. Further, we have translated the data in to EntitySet and return the list of customers.
The complete data retrieval is implemented with the async pattern.
When we run the demo, we can see that the main UI Thread is not blocked while data is retrieving from the database.
After this implementation it will be nice that we can make an extension method for asynchronous Entity Framework call. So the following list represent extension method for asynchronous call for any Entity Framework query.
///
<summary>/// Asynchronous call of Entity Framework query
/// </summary>public static class AsyncExtensions
{
public static async Task> ExecuteAsync(this IQueryable source,SqlTransaction transaction=null)
where T : EntityObject
{
var query = (ObjectQuery)source;
//Find conncetion from query context
var conn = ((EntityConnection)query.Context.Connection).StoreConnection as SqlConnection;
if (conn == null)
return null;
//parse for sql code from the query
var cmdText = query.ToTraceString();
if (string.IsNullOrEmpty(cmdText))
return null;
//Create SQL Command object
var cmd = new SqlCommand(cmdText);
//if query contains parametres append them
cmd.Parameters.AddRange(query.Parameters.Select(x => new SqlParameter(x.Name, x.Value ?? DBNull.Value)).ToArray());
//Configure connection string
cmd.Connection = conn;
cmd.Connection.ConnectionString = new SqlConnectionStringBuilder(conn.ConnectionString) { AsynchronousProcessing = true }.ToString();
//Now open the connection
if(cmd.Connection.State!= System.Data.ConnectionState.Open)
cmd.Connection.Open();
//New method in C# 5.0 Execute reader async
var reader = await cmd.ExecuteReaderAsync();
var data = await Task.Run(() => { return query.Context.Translate(reader).ToList(); });
return data;
}
}
The use of this method is simple. Include in your project, and call against any Entity Framework query. In our Demo the new method looks like the folowing:
private void LoadCustomersAsyncExtensionMethod()
{
DemoDbEntities ent = new DemoDbEntities();
var query = from p in ent.Customers
where p.Name.Contains("Name") && p.Surname.Contains("Surname") && (p.Name + p.Surname).Length > 3
select p;
//Execute EF query asynchronous
var result = query.ExecuteAsync();
//When the result come from database continue with and assign to datagrid
result.ContinueWith((asyncTask) =>
{
//Fill ItemsSource collection by data from database using Dispatcher, since probably we are not in UI thread
this.Dispatcher.Invoke(
DispatcherPriority.Normal,
(Action)(() => customersDataGrid.ItemsSource = asyncTask.Result)
);
});
}
After we define a query, we call ExecuteAsync extension method. We need to wait the data from database by calling ContinueWith task method.
When the data is come, assign the to ItemSource of DataGrid.
The Demo sample and database you can download here.














