Jonathan Swift's Blog

Pathfinder using DirectX and Genetic Algorithms

jon_l_Swifg]t — Fri, 23 Jan 2009 16:13:00 GMT

Well, I've been threatening it for long enough, now it's time for some action : ) Over the course of the next few weeks I'll aim to build a simple 2D application that demonstrates how a Pathfinder application can be developed using genetic algorithm's. I'm going to use DirectX to render the 2D display because I've been messing about with it on and off for a while now and happen to think it's really cool. I'll aim to walk you through the code (of which there will be quite a bit) and so this example will be comprised of multiple parts, each covering a logical step in the example build.

This first step then will take you through creating the initial C++ application, registering and creating the standard window's bits (entry point, window, message loop, callback proc etc etc) and setting up and initialising DirectX, ready for use. I guess I'm hoping that even if you've never used C++ or DirectX before you'll find these instructions easy enough to at least follow, if not fully understand.

And with that, let's begin. The first thing to do is to make sure you have the latest DirectX SDK installed (currently DirectX 10), you can find this by browsing here. I'm assuming you have Visual Studio installed also. Kick off by creating a new C++ project using the 'empty project' template. As its name implies, this does nothing more than create a base project with nothing in it, a blank canvas if you will.

Next, you need to add a .cpp to the Source Files directory to enable you to write your code, call it whatever you want - entry_point.cpp will do nicely and hey presto, you're ready to rock and roll. At this point I should add a bit of a disclaimer regarding the code I write - please don't consider it a shining example of best practice in any areas, it's simply sample code that demonstrates a number of concepts, nothing more. It's not layed out nicely or anything either, you've been warned.

Strap yourselves in, it's time to code. In this first step, we need to define an entry point for our application, from which everything else will follow. When writing a Windows application in C++, there are a number of different entry point methods that can be used. In our case, we're going to write a Windows application that may cater for Unicode support, and so we're going to use the _tWinMain entry point method. Under the covers, this generic entry point method will actually call either WinMain (non unicode support) or wWinMain (Unicode support) depending on whether the _UNICODE compiler flag has been defined.

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{}

As you can see, this function returns data of type integer and has four parameters that are set for you when the application is loaded and started. The first parameter, hInstance is the instance handle for the current application. The next parameter, hPrevInstance will always be set to NULL in a Win32 application, and was used to identify an instance of the application already running in a 16-bit Windows application. Next up is lpCmdLine, which is a pointer to a null-terminated string containing the command line used to fire up the application. Finally you have nCmdShow, which can be one of a number of values that determines how the window itself will be shown.

Let's take a look at the contents of this function.

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
    if (!InitialiseWindow(hInstance))
    {
        return FALSE;
    }

    MSG msg = {0};

    while (WM_QUIT != msg.message)
    {
        while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }
    }

return (int) msg.wParam;
}

The first thing to note is that a function called InitialiseWindow is called. This is a function you're going to write that you'll see shortly, and its job will be to define, register and show the application window. Next comes the important part, the message loop. This is the top level controller for your application, and its task is a simple one, to retrieve and send messages that are on the thread message queue. To do this, the PeekMessage function is used to check the queue and extract the message information (if any). Five parameters are required. The first is the address of the MSG structure to populate. The second is a handle to a window whose messages you're checking, NULL signifies the current window. The third and fourth parameters are min and max values that allow you to specify a range of messages that should be checked. Finally, you specify whether or not messages should be removed after being processed.

If you look at some examples online, you'll often see GetMessage used in place of PeekMessage. GetMessage is a blocking call however and won't return until a message is received, no good for a game or suchlike.

Within the message loop are two function calls, TranslateMessage and DispatchMessage. TranslateMessage translates virtual-key codes into character messages and DispatchMessage sends the message to a windows procedure (which you'll see soon). That's pretty much it for this method for the time being, let's turn our attention now to the business of actually creating and showing our application window via the InitialiseWindow function.

bool InitialiseWindow(HINSTANCE hInstance)
{
    WNDCLASSEX wcex;
    ZeroMemory(&wcex, sizeof(WNDCLASSEX));

    wcex.cbSize = sizeof(WNDCLASSEX);
    wcex.style = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc = (WNDPROC)WndProc;
    wcex.cbClsExtra = 0;
    wcex.cbWndExtra = 0;
    wcex.hInstance = hInstance;
    wcex.hIcon = 0;
    wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
    wcex.lpszMenuName = NULL;
    wcex.lpszClassName = TEXT("DirectXAITutorialClass");
    wcex.hIconSm = 0;

    RegisterClassEx(&wcex);

    RECT rect = { 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT };
    AdjustWindowRect(&rect, WS_OVERLAPPEDWINDOW, FALSE);

    g_hWnd = CreateWindowEx(NULL,
            TEXT("DirectXAITutorialClass"),
            TEXT("DirectXAITutorial"),
            WS_OVERLAPPEDWINDOW,
            300,
            300,
            rect.right - rect.left,
            rect.bottom - rect.top,
            NULL,
            NULL,
            hInstance,
            NULL);

    if(!g_hWnd)
    {
        return FALSE;
    }

ShowWindow(g_hWnd, SW_SHOW);
UpdateWindow(g_hWnd);

return TRUE;
}

Yes I know, looks like a lot of work to show a window, there's really nothing to it though (please check the msdn documentation for a breakdown of all the parameters). There are a few basic steps that need to be followed in order to show a window. First, a window class needs to be defined and information such as cursor type, background color, icon and style provided. The WNDCLASSEX structure is used to hold this information. One of the key parameters in this definition is lpfnWndProc, which expects a function pointer to a procedure that will handle messages, you'll see this in a little while. Once this definition is complete, it needs to be registered with the system so it can then be used. The RegisterClassEx function is used to perform this task.

Next, the CreateWindowEx function is called and its job is to actually create an instance of the window that we defined earlier and return a handle to this instance. Again, please check the documentation for a listing of all the parameters, but the starting position, size, window class and text are all specified here.

All that remains at this point is to actually show the window via a call to ShowWindow. You can see also that UpdateWindow is called after this, which sends a WM_PAINT message to the window, effectively getting it to redraw itself.

Voila.

Almost there. We now need to implement a function whose job it is to actually do something with messages for our window, this is the function we specified in the WNDCLASSEX function.

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    switch(message)
    {
    case WM_DESTROY:
        {
        PostQuitMessage(0);
        return 0;
        }
        break;
    }
    return DefWindowProc(hWnd, message, wParam, lParam);
}

This function contains a switch construct that is used to define what should happen for different messages. At the moment only one type of message is checked for - WM_DESTROY - which is sent to the window when it is being destroyed. When this message is received, PostQuitMessage is called which places a WM_QUIT message in the thread message queue, indicating to the system that the thread has made a request to terminate.

Finally, DefWindowProc should always be called as this function provides default message processing for any messages that the application does not specifically process.

In terms of putting together a blank Windows application, we're done. The full code listing is now shown, try copying it into your source file and compile and run it. A blank window should appear. There's a few lines of code I've added that allows you to exit the application by hitting the escape key, and of course the standard header gubbins and prototyping.

#include <windows.h>
#include <tchar.h>

HWND hWnd;

#define KEY_DOWN(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 1 : 0)
#define KEY_UP(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 0 : 1)

const int SCREEN_WIDTH = 640;
const int SCREEN_HEIGHT = 480;

bool InitialiseWindow(HINSTANCE hInstance);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
    if (!InitialiseWindow(hInstance))
    {
        return false;
    }

MSG msg = {0};

    while (WM_QUIT != msg.message)
    {
        while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }

        if(KEY_DOWN(VK_ESCAPE))
            PostMessage(hWnd, WM_DESTROY, 0, 0);
    }

return (int) msg.wParam;
}

bool InitialiseWindow(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
ZeroMemory(&wcex, sizeof(WNDCLASSEX));

    wcex.cbSize = sizeof(WNDCLASSEX);
    wcex.style = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc = (WNDPROC)WndProc;
    wcex.cbClsExtra = 0;
    wcex.cbWndExtra = 0;
    wcex.hInstance = hInstance;
    wcex.hIcon = 0;
    wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
    wcex.lpszMenuName = NULL;
    wcex.lpszClassName = TEXT("DirectXAITutorialClass");
    wcex.hIconSm = 0;

RegisterClassEx(&wcex);

RECT rect = { 0, 0, SCREEN_WIDTH, SCREEN_HEIGHT };
AdjustWindowRect(&rect, WS_OVERLAPPEDWINDOW, FALSE);

    hWnd = CreateWindowEx(NULL,
            TEXT("DirectXAITutorialClass"),
            TEXT("DirectXAITutorial"),
            WS_OVERLAPPEDWINDOW,
            300,
            300,
            rect.right - rect.left,
            rect.bottom - rect.top,
            NULL,
            NULL,
            hInstance,
            NULL);

    if(!hWnd)
    {
        return false;
    }

ShowWindow(hWnd, SW_SHOW);
UpdateWindow(hWnd);

return true;
}

Now we've got that bit out of the way it's time to turn our attention to something more interesting, DirectX. DirectX is a high performance API for rendering graphics to screen, utilising the video card directly. It's based on COM and you can program against it in the managed environment now also. This is the technology we're going to use to render our 2D graphics, so let's get cracking. First off, there's a couple of extra include directives needed to use DirectX 10.

#include <d3d10.h>
#include <d3dx10.h>

And you also need to make sure you link to the DirectX .lib file, you can do this from the Project Properties pane accessed by right-clicking the project name in Solution Explorer.

There's a few global variables we're going to set up for ease of use also.

ID3D10Device*                   g_pD3DDevice = NULL;
IDXGISwapChain*               g_pSwapChain = NULL;
ID3D10RenderTargetView*   g_pRenderTargetView = NULL;

The first one, ID3D10Device is a device interface used to perform rendering and to create a number of different resources such as Textures. Consider it a virtual adapter for Direct3D 10. IDXGISwapChain represents a collection of 'surfaces' that can be drawn to before being displayed on screen, usually 2 but sometimes more. The Swap Chain is used to implement buffering, allowing rendering to occur on the buffer that is not currently being displayed and, once rendering is complete the buffers are swapped around and the finished rendering is drawn on the monitor display. Without buffering, flickering and image tearing will occur as the monitor refreshes partway through drawing to the currently active buffer (surface). Finally, ID3D10RenderTargetView allows us to bind the back buffer in our Swap Chain as the render target.

Next, we're going to write a function called InitialiseDirectX10 that will, you guessed it, perform the initialisation and setup of the DirectX 10 components.

bool InitialiseDirectX10()
{
DXGI_SWAP_CHAIN_DESC sd;
ZeroMemory(&sd, sizeof(sd));

    sd.BufferCount = 1;
    sd.BufferDesc.Width = SCREEN_WIDTH;
    sd.BufferDesc.Height = SCREEN_HEIGHT;
    sd.BufferDesc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
    sd.BufferDesc.RefreshRate.Numerator = 60;
    sd.BufferDesc.RefreshRate.Denominator = 1;
    sd.BufferUsage = DXGI_USAGE_RENDER_TARGET_OUTPUT;
    sd.OutputWindow = g_hWnd;
    sd.SampleDesc.Count = 1;
    sd.SampleDesc.Quality = 0;
    sd.Windowed = TRUE;

    HRESULT hr = D3D10CreateDeviceAndSwapChain(NULL,
            D3D10_DRIVER_TYPE_HARDWARE,
            NULL,
            0,
            D3D10_SDK_VERSION,
            &sd,
            &g_pSwapChain,
            &g_pD3DDevice);

    if (FAILED(hr))
    {
        MessageBox(g_hWnd, TEXT("Error Message Here"), TEXT("ERROR"), MB_OK);
        return FALSE;
    }

ID3D10Texture2D* pBackBuffer;
hr = g_pSwapChain->GetBuffer(0, __uuidof(ID3D10Texture2D), (LPVOID*)&pBackBuffer);

    if (FAILED(hr))
    {
        return FALSE;
    }

hr = g_pD3DDevice->CreateRenderTargetView(pBackBuffer, NULL, &g_pRenderTargetView);
pBackBuffer->Release();

    if (FAILED(hr))
    {
        return FALSE;
    }

g_pD3DDevice->OMSetRenderTargets(1, &g_pRenderTargetView, NULL);

    D3D10_VIEWPORT viewPort;
    viewPort.Width = SCREEN_WIDTH;
    viewPort.Height = SCREEN_HEIGHT;
    viewPort.MinDepth = 0.0f;
    viewPort.MaxDepth = 1.0f;
    viewPort.TopLeftX = 0;
    viewPort.TopLeftY = 0;

g_pD3DDevice->RSSetViewports(1, &viewPort);

return true;
}

Again, looks like an awful lot is going on here but it's really rather simple. The first thing we need to do is to create both our DirectX device and our swap chain. To do this, we make a call to the D3D10CreateDeviceAndSwapChain function, passing in a DXGI_SWAP_CHAIN_DESC structure that describes in detail what type of Swap Chain we want to create. We also pass in the address of our device and swap chain pointers to populate and that's it. For a full explanation of all the parameters please consult the documentation here.

Next, we need to get a handle to the buffer that we're going to render to and then set this as our render target, before setting up a default view port to view the entire render scene from. Again, there isn't much point in me duplicating in depth information about method calls and parameters that are readily available in the documentation shipped with the SDK.

Finally for this first part of the tutorial, you need to add a function which will be responsible for cleaning up the DirectX objects that you've created and a function responsible for actually rendering the scene, these are listed below.

void RenderFrame()
{
    if (g_pD3DDevice != NULL)
    {
        g_pD3DDevice->ClearRenderTargetView(g_pRenderTargetView, D3DXCOLOR(0.0f, 0.0f, 0.0f, 0.0f));
        g_pSwapChain->Present(0, 0);
    }
}

void ClearUpD3D10()
{
    if (g_pRenderTargetView)
        g_pRenderTargetView->Release();

    if (g_pSwapChain)
        g_pSwapChain->Release();

    if (g_pD3DDevice)
        g_pD3DDevice->Release();
}

The clean up function doesn't require any explanation, we just release the COM objects that have been created so far. For the render function, it's about the simplest render that can be performed, painting the screen a single colour using the ClearRenderTargetView command. Following this Present is called, which takes care of taking the back buffer that's been rendered to and displaying it on screen.

The entry point method will of course need altering to make use of these new functions.

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
    if (!InitialiseWindow(hInstance))
    {
        return FALSE;
    }

    if (!InitialiseDirectX10())
    {
        return FALSE;
    }

    MSG msg = {0};

    while (WM_QUIT != msg.message)
    {
        while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE) == TRUE)
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }

        if(KEY_DOWN(VK_ESCAPE))
            PostMessage(g_hWnd, WM_DESTROY, 0, 0);

        RenderFrame();
    }

    ClearUpD3D10();

    return (int) msg.wParam;
}

If you compile and run your program you should be presented with a window painted with a single colour.

In Part 2, we'll look at drawing the scene we're going to use for this example as well as start looking at the genetic algorithm implementation.

Silverlight 2 Book - Go Buy It!

jon_l_Swifg]t — Wed, 21 Jan 2009 14:38:00 GMT

OK, so it's finally finished. It's been a long time in the making and has consumed all of my spare time, so please go out and buy a copy. Judging by its dimensions it will make an excellent door stop, table leg prop, paper weight or of course Silverlight 2 guide.

http://www.amazon.co.uk/s/ref=nb_ss_b?url=search-alias%3Dstripbooks&field-keywords=silverlight+2+for+asp.net+developers

Get ready for some more blog posts!

Silverlight 2.0 For ASP.NET Developers

jon_l_Swifg]t — Wed, 28 May 2008 11:56:00 GMT

The more astute of you may have noticed that my blog has been a little 'sparse' over the past year or so. In fact, I still have a couple of half finished articles that I promised some time ago (Path Finder example using Genetic Algorithms springs to mind). The good news is I have a very good excuse for this - for about a year now I've been working on a book with some colleagues. The book is titled 'Silverlight 2.0 for ASP.NET Developers' and I think this title speaks for itself.

I'll post the link to the book as soon as I have it. It's not quite finished yet... still a lot of finishing off to do over the next couple of months, but once this is done I will finally get round to finishing the articles I started and replying to some of the queries posted (that I haven't already replied to).

Thanks for your patience : )

Composite WPF/Prism

jon_l_Swifg]t — Wed, 16 Jan 2008 20:13:00 GMT

So this week I've been involved in a workshop with the P & P team in Redmond evaluating and discussing ideas around Composite WPF and what deliverables might look like in this area. It's been very useful indeed, with some great feedback from the other delegates around what people liked/disliked about the CAB and SCSF and what was needed moving forward when building a composite application in WPF.

Key themes echo'd by all in the room were the need for a framework that was more flexible, simpler and easier to pick up and run with than the CAB and SCSF were. So a more pluggable architecture with better documentation and learning material would be great.

With this in mind, at the end of day 2 we got to look at three early spikes demonstrating the ability to swap in and out a DI Container of your choice (good work guys), an implementation of the replacement for Workspaces, called Regions, and a look at the possible replacement for the EventBroker, which provides type safety and is driven by interfaces rather than simple string topic names.

All in all I like what I've seen so far and the direction we're moving in is a good one. When the workshop is over I'll provide a full report, possibly including code samples if I can get them.

P & P Visit - Overview

jon_l_Swifg]t — Mon, 25 Jun 2007 15:26:00 GMT

During April 2007 I attended a week long workshop with the Patterns and Practices (P&P) team at Microsoft’s Corporate Headquarters in Redmond. The primary goals of the engagement were:

· Better understand the P&P offerings and future direction

· Ascertain the best approach to building and reusing application frameworks across an Enterprise.

· Develop a more coherent UI strategy, considering the multiple recent offerings in this space

· Learn from the experience of the P&P team, particularly with respect to Governance and Process

In addition to meeting the P&P team, sessions with key representatives from other groups were delivered, including:

· Windows CardSpace with Richard Turner

· WPF & SilverLight with Ian Ellison Taylor

· CCF with Ming Chao

· Project Acropolis with David Hill

During the course of the visit we discussed the origins of the P&P team, their Vision and Mission, their product offerings and how everything they engineer is ultimately customer driven.

We also discussed the problems they aim to address through the guidance they deliver and how this guidance can be delivered in many forms, from whitepapers to complete code packages and software factories. Primarily, they are targeting the common issues that face all development functions, for example:

· Application Development takes too long

· Mistakes are repeated and lessons relearned

· Knowledge sharing is hard

· Developers spend time on repetitive tasks

· Best practices are not captured

�� There’s a lack of reuse and inconsistent approach

We also discussed how P&P specifically aim to address these issues by filling the ‘content gap’ in Microsoft’s offerings. That is, the space between the Microsoft Platform, Products and Technologies and a functionally rich, fully integrated and tested solution.

Vision and Strategy

“The world’s best guided development experience, delivered to teams building apps on the Microsoft application platform” is P&P’s vision statement. They also have a Charter: “The Microsoft source of guided development experiences for teams building app on the Microsoft Platform”.

Their strategy for delivering these is as follows:

· Guided experiences spanning software engineering practices, development of applications and project execution patterns

· Optimize for discoverability, evaluation and integration into the Visual Studio development environment

· Make guidance customisable and extensible by the development teams

· Create vibrant community of integrated guided experience developers

Portfolio

The delivery itself takes one of four forms:

Guides consist of written guidance, either online or printed, covering topics that include patterns, application architecture, integration, performance, and security.

Application Blocks are actual deliverables that streamline development and currently include Caching, Cryptography, Data Access, Exception Handling, Logging, Policy Injection, Security, and Validation.

Process includes two Visual Studio Team System templates: MSF for Agile Software Development and MSF for CMMI Process Improvement. These process templates includes set of software development processes, practices, template documents, and associated queries, reports and project portal settings.

Software Factories are installable packages that extend Visual Studio Team System with a custom process for a specific type of deliverable supported by a set of integrated software assets.

Applications and Frameworks

During the visit we hosted an open discussion with Edward Jezierski and Wojtek Kozaczynski on the best approach to building frameworks within the enterprise. The key questions to address were:

· How can an Enterprise make the most of their assets through reuse?

· Is a one-size fits all framework the best approach to take?

In order to achieve reuse across the group it is clear that teams need to collaborate in order to identify opportunities for reuse. Further to this it also critical that a common vocabulary exists across the group.

The P&P approach to developing shared assets is to choose the most mature offering that entirely or most closely satisfies a given requirement, and to then incentivise one of the teams to deliver the full functionality required.

However, Ed And Wojtek both felt strongly that it is a mistake to start a greenfield ‘Framework’ project with the aim of satisfying all present and future requirements. It is best that these items evolve and follow an ‘Enable not Constrain’ ideology with regard to developers.

Genetic Algorithms Basics

jon_l_Swifg]t — Tue, 01 May 2007 20:58:00 GMT

So.. I've finally got around to blogging about Genetic Algorithms, apologies it's taken me so long. I'll kick off with a very brief tutorial around the theory behind genetic algorithms, before moving on to a concrete example showing how to solve the Path Finder problem in my next post. It's not an easy topic, but bear with me and I'll do the best I can to make sense of it for you.

So, first things first, we need to refresh our Biology knowledge regarding the theory of evolution and natural selection, as this forms the basis of Genetic Algorithms.

Evolution and Natural Selection

OK, Evolution is the term used to describe changes in a populations traits from generation to generation. These traits are encoded in segments of nucleic acid called genes, which connect together to form chromosomes. When species reproduce, their encoded traits, genes, are copied and passed on to their offspring in a process called Recombination, so for instance half of an offspring’s genes could come from one parent and half from another, the exact combination though is determined by the crossover rate. This is one way in which the traits of the next generation are determined.

Natural selection simply states that favourable traits in one population are more likely to survive and be passed onto subsequent generations. For example, a gene directly related to a predator have excellent sight would be more likely to be passed on to future generations as that predator would in theory be able to catch more prey and have a greater chance of survival (thereby living longer and reproducing more), passing it’s genes on (think ‘survival of the fittest’). As you’ll see further on in this tutorial, the concept of ‘fitness’ for an organism is absolutely critical and one of the most difficult things about Genetic Algorithms is defining and calculating the fitness for your conceptual organism.

As well as natural selection and recombination affecting the genes of subsequent generations, on occasion mutation can occur. Mutation could result in no change to the organism with regard to its fitness, it could affect it’s fitness negatively or it could have a positive effect on the fitness. Clearly a mutation that resulted in a usually four legged creature being born with three legs wouldn’t ‘stand it’ in good stead ; )

So how do we take advantage of this evolutionary process to solve problems?

One of the first things we need to do is decide upon a convention for representing possible solutions (guesses) to the problem in hand. You can represent these guesses in any way you choose, in this tutorial we will be encoding them as a binary string. These guesses will be our version of a chromosome (chain of genes). In very basic terms, here is how we will attempt to solve a problem:

1) First off, we will need to create a starting population of random chromosomes to work with

2) Following on from this we will take each one in turn and work out how good it is at solving our particular problem. The better the chromosome is at solving our problem, the higher a ‘fitness score’ we will give it

3) We can then implement our version of recombination by selecting two chromosomes from the population. The fitness score directly relates to the chance of a chromosome being selected and effectively being allowed to reproduce in our program. There are different methods of selection that can be used in Genetic Algorithms (Roulette Wheel, Tournament and Elitism), we will use Roulette Wheel selection

4) We then need to work out how the offspring chromosome will be made up from both parent chromosomes. This process is called crossover

5) Evaluate the chromosome genes for mutation

6) Repeat as necessary to create a population of the right size

Making any sense? I tend to find that the entire process only really starts to make some sense when the scheme used to encode a potential solution as a chromosome has been explained, as well as how to evaluate a chromosomes ‘fitness’ rating. So hang on in there for a short while yet J

In the process listed above, step 3 mentions the selection process for deciding which two chromosomes (remember these are our guesses) will get the chance to create offspring. The selection methodology we are going to use is Roulette wheel selection. The easiest way to imagine this method is to picture a pie chart in your head. Now... with that in mind, assign each chromosome a slice of the chart..... BUT.... the chromosomes with the higher fitness score will receive a larger slice of the pie chart than those with a lower fitness score. This will result in the higher scoring chromosomes having an increased, but not definite chance of being able to ‘reproduce’.

Now comes the interesting part.... how do the genes within each parent chromosome make up the genes in the offspring chromosome? Two things in our simulation will affect how this is made up, the Crossover and Mutation rate. More imagery will help illustrate this point. Consider the following two chromosomes in a hypothetical population that have been ‘selected’ to reproduce.

0011010001001100

0100101010101001

First off, we need to decide if the two chromosomes will ‘swap’ their bits. We use a constant factor to decide this, a good starting point being 0.6 or 0.7. If the decision is to swap, we select a random point within the string of bits, let’s say 12, and then swap all the bits that follow. So, the chromosomes above will become:

0011010001001001

0100101010101100

We then evaluate the chromosomes to see if mutation needs to be applied to each bit in the chromosomes, the chance of this happening should be set to something very low as mutation should be a rare event.

And... that's the bones of it. I'll put together some source code that illustrates this in action and publish it asap. If anyone has any idea for applying this let me know and we can put something together if it's interesting.

P & P Workshop, Redmond

jon_l_Swifg]t — Mon, 30 Apr 2007 19:24:00 GMT

Hi all, I write this blog post from the comforts of the SAS lounge in Copenhagen airport, whilst I wait for my connecting flight to Seattle. The joys of a long haul flight await, let’s hope Alastair Reynolds book “Absolution Gap” keeps me occupied.

So... this post is just to set the scene for the workshop I’m running with the Patterns & Practices team in Redmond this coming week. Four days looking at the entire P & P estate in detail with a client, as well as in depth talks regarding CCF, WPF/e, CardSpace and Acropolis.

Throughout the four days I’ll keep this post updated with any points of interest, and perhaps a few photo’s also to break up the monotony of text. I’m particularly looking forward to some good debate around enterprise frameworks, the pros and cons of, if you have any thoughts you’d like to share please do so via the comments section. In particular, any experiences of putting together a framework for an Enterprise would be of interest. Was it successful? Was it overkill? Has it been reused by many applications?

Below is an example of some of the material we’ll be covering in the next four days. Specific updates will be provided asap after the event.

· Web/Smart Client Software Factories, including Vision and Roadmap

· AJAX within the Application Blocks

· Enterprise Frameworks – General Discussion

· Web Service Factory

· Identity Platform

· Workflow

· CCF

· WPF

Genetic Algorithms

jon_l_Swifg]t — Wed, 20 Dec 2006 17:40:00 GMT

I have seen a great example of solving the path finder problem with a genetic algorithm.... I'll modify it, write about it and put it on here by mid january.... promise!

Merry Xmas by the way

Customer Care Framework

jon_l_Swifg]t — Thu, 26 Oct 2006 18:30:00 GMT

I've been in Redmond all week checking out CCF with the product group. Some of my clients are looking at utilising its features and so I'm busy getting the lowdown on the CCF roadmap etc.

Not many people tend to have heard about it and its capabilities and so expect a blog post imminently with more information and perhaps some technical samples.

Oh and I won't forget to write a quick post about interop performance, honest! In point of fact, I'm still trying to get round to writing some game dev content for you. The best things come to those who wait right?!

.NET Interop - Freeing unmanaged memory

jon_l_Swifg]t — Mon, 16 Oct 2006 14:38:00 GMT

OK. Imagine you need to call an unmanaged function. Now imagine this function returns you a pointer to a block of unmanaged memory that it's allocated. The runtime will clear this up for you right? Wrong. Well, wrong a lot of the time anyway.

The runtime always attempts to free unmanaged memory using the COM method - CoTaskMemAlloc. So let's say we have a function that returns a pointer to unmanaged memory that we're going to marshal directly as a .NET type - System.String. Once the System.String object has been created (the runtime uses a copy of the unmanaged data to build this), the runtime will attempt to clean up the unmanaged data with a call to CoTaskMemFree. This is all well and good providing the memory was allocated with CoTaskMemAlloc. If it wasn't though, you'll end up with a memory leak.

Luckily, the solution is simple. The only tricky item is finding out which method the function used to allocated the memory. If you find out the C runtime was used, you can pass the data back as an IntPtr and then pass this IntPtr to an unmanaged function you've written to be cleaned up properly. (You could of course re write the original unmanaged function to use CoTaskMemAlloc, but I'm assuming in most cases this isn't possible). Let's take a look at a very simple example.

Our unmanaged function allocates memory for a Unicode string and returns a pointer to this memory to us:

extern "C" __declspec(dllexport) wchar_t* GetString(const wchar_t* inString);

wchar_t* GetString(const wchar_t* inString)
{
    wchar_t* retValue = new wchar_t[wcslen(inString) + 1];
    wcscpy(retValue, inString);
    return retValue;
}

Now, when we write our DllImport statement to expose this function to our managed code, we might be tempted to simply cast the return value directly as System.String. However, this will leave us unable to clean up the unmanaged memory allocated above. Instead, we need to cast it as an IntPtr, which we can then pass to an unmanaged function written specifically to clean memory for us.

[DllImport("YourDLL", CharSet=CharSet.Unicode)]
public static extern IntPtr GetString(string inString);

Our unmanaged helper function for freeing memory might look like this:

extern "C" __declspec(dllexport) void FreeMemory(void* memToFree);

Leaving us with the small job of adding a DllImport statement for it (I'm sure you can manage this part yourselves - email me if you can't!) and then using it in code:

IntPtr pUnmanagedMemory = NativeMethods.GetString("123456789");
string theString = Marshal.PtrToStringUni(pUnmanagedMemory);
Console.WriteLine(theString);
NativeMethods.FreeMemory(pUnmanagedMemory);

Note the Marshal.PtrToStringUni method. There are a variety of these PtrTo* methods for just such occasions as this. Of course (as in all my examples) you'd probably want to wrap the interop calls in try/catch blocks and place your cleanup code in the finally.

Enjoy!