Tuesday, July 21, 2009

Generic selection in CIlib

So, you are busy with a an algorithm and you need to apply a selection to a group of objects.

Generally, you would write some code that implements a selection strategy. Class names such as TournamentSelection, RouletteWheelSelection and RandomSelection seem to be the norm. I've seen these classes many, many times. Feels like a waste doesn't it? I mean how many TournamentSelection classes should a person write in a lifetime? There has to be a better way!

Well, that's what we thought as we thought about the notion of "selection" in CIlib. You may want to select a variety of things, not just specific object such as Individuals. Java generics and a nifty fluent interface come to the rescue.

Fluent interfaces are interfaces that read like natural language. Martin Fowler and Eric Evans first described this kind of API structure. The JMock guys, for example, have developed a very good API for mocking using fluent interfaces. So, how can we use this in CIlib? It's quite simple, actually.

There are a few key concepts that we need to take note of regarding selection:
  • Orderings: This is related to how a list of entries can be arranged.
  • Weighing: Entries may or may not have different levels of importance.
  • Randomness: There may be a need to have a collection of entries and a set of x random entries need to be returned.
  • Number of returned elements: One entry? Two? Twelve?
  • Should the selection be such that only unique entries are returned?
That's a bit to keep track of. Thankfully, most of the hard work has been done.

Keeping the points above in mind, a TournamentSelection is actually a multi-part process. Firstly, a random sub-group of elements needs to be selected. Then from this sub-group, the elements are ordered based on some criteria and the element which is the "best" is then the winner of the tournament and should be returned as the final result for the selection. I'll be honest, it's easy to implement but what about if you want to use a different random number generator? These type of options need to be simple to define.

How about a tournament selection in a one-liner:
Selection.from(elements)
.orderBy(new RandomOrdering<E>(this.random))
.last(tournamentSize)
.orderBy(new SortedOrdering<E>(this.comparator))
.last().singleSelect();

Mixing the Ordering, Weighing and type of selection means that we can do some very interesting selections with what ever the selection type E might be.

For more information regarding all the combinations, please have a look at the CIlib JavaDoc and documentation, or drop us an email on the mailing lists.

1 comment:

  1. I recently came accross your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.


    Susan

    http://dclottery.info

    ReplyDelete