So, it works.

After another little while pottering away this afternoon, I've managed to get the code for the big GA into some kind of shape. All the essentials are there, as it were:

- chromosomes and genes

- a basic fitness function

- a basic parent-selection method

- a basic crossover system

- a basic mutation system

I've knocked together a rough initial dataset, and it's generating the sort of results that I'd expect; trending from worse to better. This is good :-)

Now we move onto the actual tricky part, which is working in the various other bits of the requirements, like the quality of service restrictions and so on. First up will be fixing the fitness function to be a bit more standardised.

Step 1: types of QoS attributes

First thing to consider is whether we should have different methods of combining attributes over the service. My initial reaction is "yes", and here's why:

For something like "cost", all we need to do to work out the total cost of a particular set of services is to add up the cost of each of them. Easy. But for something like "Availability", expressed in a percentage, we can't really just add up all the availability scores, can we? That'd produce an oddly skewed result at the end.

eg: we have three services, each of which has a 90% chance of being available. If we add those up, we get an availability score of 270 for the operation. We could divide that by the number of services to get back to the average availability, but that still only takes us to 90% -- in fact, the aggregate availability (the chance that all three services will be available during the invocation) is only 73%.

So, which will serve the algorithm better - the average availability of the services, or the actual computed aggregate availability for the whole set? I'm not sure. Possibly I should test both :-)

Step 2: weighting factors

Also, we should take into account a couple of other factors when calculating the fitness of a chromosome: partly a user-defined weighting (eg: if they would rather the algorithm brought the cost of the service composition down, rather than the execution time), and partly a dynamic weighting to try and meet any particular requirements (eg: if the maximum cost of the service composition is set to £10, and none of the current solutions match that, then the weighting factor assigned to the cost of the service composition should be increased).

What this means is that I'll have to take the fitness calculation of a chromosome out of the chromosome itself, and into the main population object; that way I can store a series of weighting factors that can be changed quickly and easily throughout the execution time.

Fitness

No, it's not a New Year's Resolution that I'm talking about today. It's a set of thoughts that I'm having about how to measure the fitness of a solution to a difficult problem.

Let's imagine that we have a set of four tasks to do, and ten workers who can do them. Each worker has a skill rating at each of those four tasks, a cost to employ them to do the task, a reliability rating to see if they actually show up for the task, and maybe a few other attributes as well.

We're going to start by randomly assigning workers to tasks, and see how good those solutions are. So how do you measure the fitness of a given solution to the task at hand?

Well, we'll start by assigning positive or negative qualifiers to the different attributes of the workers:
Skill rating; reliability rating: these should clearly be maximised for any given task.
Cost: this should clearly be minimised for any given task.

Then we'll let the manager decide which of attributes is the most important, either by simply ranking them in order, or by assigning percentages to each one. (eg: they could decide that the priority should be 50% based on cost, 40% based on reliability, and 10% based on skill rating)

And now comes the hard part: normalisation! Let's say that we measure the time taken to complete the task in hours, the cost to complete the task in pounds, and the reliability of the worker as a percentage. How do we unite those completely different measurements?

Well, I've a few ideas, and they start with some kind of normalisation.

1) Normalise each value and then multiply by prioritisation:
- let's look over all of the values for a particular attribute (say skill), and then divide all of those attributes by the highest one. We'll end up with the highest skilled worker being rated with a skill of 1, and everyone else rated between 0 and 1.
- Repeat that for all of the other attributes available.
- multiply each of the attributes by the ranking factor, or the priority percentage.

2) Distance from average:
- again, we'll pick a particular attribute, and then calculate the average (mean) value of that attribute.
- Now, we'll calculate the distance from that average for every worker.
- Then, we'll normalise those distances to lie in the range -1 -- +1
- Finally, we can apply the priority factors.

Which of these would give a better set of results? Any gut feeling answers on a postcard?! In the meanwhile, I'm going to have a poke around in the literature to see if there are any recommendations there...

News at last

Finally there's a little bit of forward movement on the Masters course - we've got the dates for the seminars sorted. Of course, the first one is scheduled for one of the few days in the next few weeks where I have something on that cannot be cancelled or moved at all, but I guess that's life...

But at least there's stuff going on. In other news there, the collection of papers to do with SOA and the application of genetic algorithms thereto continues. There's been a bit more work done on this field than I'd anticipated, which was a little surprising, and it falls into two general streams.

One takes a composed service, made up of lots of interchangeable component services, and tries to work out the best combination of services given a specific set of requirements. This is pretty similar to work that I've done already in this area, so that's encouraging.

The second uses the genetic approach to try and combine services efficiently into a single component service. This looks fantastically interesting and useful, but it would mean learning a whole new mathematical language of combinatorial algebra, and then trying to code it into Java. Which is unlikely to take place over the course of a single, part-time year.

But hey - I'm meeting up with my supervisor soon enough, and we'll have a look through the papers to see if he thinks that the gaps I've spotted are (a) actually gaps at all and (b) big enough gaps for a research project.

Service composition

Electronic journals are both big and clever, it seems. It's also very useful to be working from within the library, and thus gaining instant access to said journals from my own laptop: technology is a marvellous thing!

I've started looking into service composition techniques now, and they're looking to be really quite a complex beastie, particularly when you begin to factor in dynamic service composition which, for my sins, is what I'm attempting to research. Obviously, when you have a group of x services that can e combined in a variety of orders to achieve a variety of results, searches to try and combine them are going to need to be heuristic to some degree: the mind-boggling number of combinations rapidly rules out a brute-force search for all but the smallest number of systems. However, the number of combinations and techniques available for a heuristic search is also beginning to hurt my brain ever so slightly.

Fortunately, it appears that not many people have looked into the method that I'd like to look at (genetic algorithms). Unfortunately, this means that I'll have to start this all from scratch!

Propositions

This morning I had a very quick chat with one of my lecturers about the prospects of continuing study to take an MSc. There were a few things that I would have been very interested in looking at, and - by some amazing fortune - two of them can be combined into a mega-research project that should be both (a) useful and (b) fascinating.

I'd get to carry on developing the genetic algorithm that I worked quite hard on during the diploma (one of the highlights of the course, to be honest) and try to integrate it into the wider context of Web Services and a more useful application than the rather abstract "workers and tasks" scenario that I'd been testing previously.

So, all in all, a rather productive morning! Now I actually have to do a bit more background reading and sort it all out as a full on research proposition. All very exciting!

Kicking off

Yet another development blog! What is it that makes this one different to any other coding blog out there?
Not much.
Apart from the fact that I'm still very much learning how all this stuff works.
My current big projects are:
- Work Schedule: a variant on the classical "Worker Allocation Problem" and a genetic algorithm to solve it.
- RandomRolly: a dice-rolling robot for Google Wave
There'll be more to come, I'm sure. Like learning perl, like all good little coders should!