New Adventures in Software by Dan Dyer

Late to get involved as ever, I’ve been developing with Android for the last couple of weeks. On the whole it has been a positive experience (thanks to Richard for pointing me in the right direction with my queries).

My first impression is “what the hell were Sun doing for the last decade?” Android shows what J2ME/JavaME could have been. A proper Java environment for mobile devices (the fact that it uses Dalvik is largely inconsequential). J2ME may have first arrived when mobile phones were far less capable than they are today but, like Java in general in the last few years, it never really progressed.  Worse still, with its numerous device profiles and JSRs it betrayed the “Write Once, Run Anywhere” philosophy that is so fundamental to Java. With J2ME it’s more like “right once, wrong somewhere else”. You don’t really write Java at all, you write some horribly restricted, out-dated subset of it. That’s not to say that J2ME was not a success of sorts despite its numerous short-comings. I don’t have the figures to hand but I believe it’s true to say there are vastly more J2ME-enabled devices in circulation than iOS and Android devices combined.

Pain-Free Mobile Development

Android is a complete reboot of Java for mobile devices. No longer do you have to worry about which devices support floating-point arithmetic or how to do anything useful with an anaemic UI toolkit. No more making do with Vectors and without generics, or wondering what happened to half the useful classes and methods that you take for granted with JavaSE.

Of course, nothing’s perfect. The API documentation, while generally pretty good, is not quite up to Sun’s high standard, the UI toolkit is either slightly buggy or slightly unintuitive (probably both), and a couple of things I wanted to achieve were less straightforward than I might have hoped. These however are minor gripes. The resources framework seems to do a pretty good job of dealing with the differences in platform versions and screen sizes. As Sun no doubt learned from J2ME, there is a real risk of fragmentation when different manufacturers want to deliver different capabilities. So far it seems under control.

The documentation favours Eclipse throughout but fortunately it’s pretty painless to develop Android code without it. The Ant tools are fine and, if necessary, it seems flexible enough that I could move things around to employ more sophisticated builds. I’m not sure how easy it is to use TestNG in preference to JUnit when using the Android tools. At the very least it would be possible to just bypass the Android test project stuff and test your Java classes the way you normally would. Given that Cedric was heavily involved in Android it’s mildly surprising that TestNG support is not included out-of-the-box.

Android Market

Yesterday, after paying the $25 registration fee, I pushed my first two (pretty basic) apps to the Android Market. This is an area where Google has room for improvement. It’s all a bit simple at the moment. As I’m in the UK my prices are set in pounds. There is no way to specify different prices for different currencies, nor does the market automatically convert prices for users. That means that, as a user, you are presented with application prices in at least four different currencies (US dollars, Euros, Sterling and Yen) and have to do the necessary conversions yourself. I would like to be able to specify that if my application costs £1.99 in the UK, then it should be $2.99 in the US and €2.49 in the Eurozone.

The other thing you can’t do is respond to user comments. Somebody left a comment that my app did not work properly for them. Unfortunately they provided no details to enable me to track down the problem. Worse, they wrongly assumed that the functionality was simply missing and stated as much. As the only comment on the app so far, that will likely dissuade other people from buying.

The good thing about the Market is that you have the freedom to upload pretty much whatever you want and to have it immediately available to users. Unlike the iPhone, you are not subject to the whims of an inconsistently applied approval process.

My First Apps

So what did I make? My first app is a simple utility for performing a multi-stage fitness test (a.k.a “Beep Test” or “Bleep Test”). It’s a one-button UI that emits the necessary beeps at the appropriate intervals and displays status information such as current speed and cumulative distance.

My second app is an educational game called Flagpole. All you have to do is identify flags. You get one point for each correct answer and it’s game over when you get one wrong. It’s divided into challenges of increasing difficulty, so you might start with South America, for which there are only 14 flags to identify. Eventually you’d progress to “The Whole World”, which would require you to correctly identify 232 flags without making any mistakes.

I intend to release further, more sophisticated applications in the coming weeks. These apps are sold via Rectangular Software, which is the new home for my commercial software development activities (contract/freelance development and now applications).  My open source projects remain here at uncommons.org.

How to move your project from Subversion on Java.net to Git on GitHub without losing the change history.

Cloning the Subversion Repository

The normal way to duplicate a Subversion repository with full history is to use the svnadmin dump and load commands. Unfortunately most SVN hosting services, including Java.net, do not provide access to svnadmin commands or direct access to the file system.

Fortunately there is another way to clone a repository, complete with all its history, that requires only read access to the repository: svnsync.

The first step is to create a local SVN repository into which you will mirror the remote Java.net repository.

svnadmin create myproject

Before cloning the contents it is important that you add a pre-revprop-change hook to your new local repository. This is a script that must complete successfully (exit code 0) before any changes to revision properties are accepted. The easiest way to do this to add an empty script and make it executable.

echo '#!/bin/sh' > myproject/hooks/pre-revprop-change
chmod +x myproject/hooks/pre-revprop/change

Bearing in mind that we want to preserve tags and branches too, not just the trunk, we can then mirror the top-level of the remote repository.

svnsync init file:///pathto/myproject https://myproject.dev.java.net/svn/myproject
svnsync sync file:///pathto/myproject

This may take a while if the repository is large and/or your connection is slow.

Stripping Java.net Web Content from the Repository

Java.net uses the project SVN repository to manage the project website, with the files stored under trunk/www. When migrating from Java.net you probably don’t want to continue with this approach. If that’s the case then you’ll want to remove all traces of the www directory from the repository. The usual way of deleting a file – removing it from the working copy and then committing – will not purge its history so instead we use the svndumpfilter command.

First dump the mirrored repository:

svnadmin dump myproject > dump

We can then remove all traces of the www directory. Any commits that only touched files under www are now empty and are dropped completely. All remaining revisions are renumbered to avoid gaps in the sequence.

svndumpfilter --drop-empty-revs --renumber-revs exclude trunk/www < dump > filtered

The final step is to restore the filtered dump in place of our local repository.

rm -rf myproject
svnadmin create myproject
svnadmin load myproject < filtered

Migrating the Repository from SVN to Git

Now that the local SVN repository contains only what we wish to keep, we are ready to migrate it to Git. To achieve this I follow Paul Dowman’s instructions.

The first step is to import the SVN repository into a new Git repository.

git svn clone file:///pathto/myproject --no-metadata -A authors.txt -t tags -b branches -T trunk myproject-git

The authors.txt file maps SVN users to Git users. Your Java.net repository may have commits attributed to the users root and httpd. You should probably just map these to your own user name. There should be one entry for each committer:

root = Your Name <you@example.com>
httpd = Your Name <you@example.com>
you = Your Name <you@example.com>
other = Someone Else <other@example.com>

Refer to Paul’s full instructions if you have branches and tags to maintain.

Pushing to GitHub

Create a new repository on GitHub and then add this as a remote for your local Git repository.

git remote add origin git@github.com:username/myproject.git

And then push:

git push origin master --tags

Job done.

Over the last 6 weeks or so I seem to have taken an unintentional extended break from programming (and from posting here). It’s time to get back into the swing of things and top of my TODO list was putting the finishing touches to ReportNG 1.1 (ReportNG being an alternative HTML reporting plug-in for TestNG).

This new release fixes a problem people have been having using ReportNG with Gradle. It also adds internationalisation support. So now, as well as the default English text, there is also support for French and Portuguese. The Portuguese translation was contributed by Felipe Knorr Kuhn. The French text is just something I added as a proof of concept. It is likely to be offensively bad to a native French speaker and I welcome any corrections. I’d also appreciate any translations for other languages (just open an issue in the issue tracker and attach your translated version of this file).

The other major change is the addition of the “Chronology” page.  This is something that exists in the default TestNG reports that I originally decided to leave out of ReportNG. I didn’t really have a use for it but several people have asked for something similar so I have added it.

Some time ago, I promised more details about the support for island models that was added to the Watchmaker Framework for Evolutionary Computation in version 0.7.0.  I’ve finally completed a first draft of some documentation for this feature, attempting to cover both the motivation for this approach to evolutionary algorithms and the practicalities of implementing this idea in your own programs that use Watchmaker. If anything is unclear or wrong please leave suggestions for improvements in the comments.

Island Models

In the natural world, populations of organisms might be separated by geography. Left to evolve in isolation over millions of years, vastly different species will occur in different locations. Consider Australia, an island continent protected by its seas. With little opportunity for outside organisms to interfere, and few opportunities for its land-based organisms to migrate to other land masses, Australian wildlife evolved to be distinctly different from that of other continents and countries. The majority of Australia’s plant and animal species, including 84% of its mammals, are endemic. They occur nowhere else in the world.

Australia is not the only island to exhibit such levels of endemism. It was a visit to the Galápagos Islands in 1835 that started Charles Darwin on the path to formulating his theory of evolution. Darwin noticed the pronounced differences between the species of mocking birds and tortoises present on the different islands of the archipelago and began to speculate on how such variations might have occurred.

In the world of evolutionary computation we can mimic this idea of having multiple isolated populations evolving in parallel. Having additional populations would increase the likelihood of finding a solution that is close to the global optimum. However, it is not just a question of having a larger global population. A system of 10 islands each with a population of 50 individuals is not equivalent to a single island with a population of 500. The reason for this is that the island system partitions the search. If one island prematurely converges on a sub-optimal solution it does not affect the evolution happening on the other islands; they are following their own paths. A single large population does not have this in-built resilience.

Migration

There is of course no real difference between evolving 10 completely separate islands in parallel and running the same single-population evolution 10 times in a row, other than how the computing resources are utilised. In practice the populations are not kept permanently isolated from each other and there are occasional opportunities for individuals to migrate between islands.

In nature external species have been introduced to foreign ecosystems in several ways. In an ice age the waters that previously separated two land masses might freeze providing a route for land animals to migrate to previously unreachable places. Microorganisms and insects have often strayed beyond their usual environment by hitching a ride with larger species.

The effect of introducing a foreign species to a new environment can vary. The new species might be ill-adapted to its new surroundings and quickly perish. Alternatively, a lack of natural predators may cause it to flourish, often to the detriment of indigenous species. One such example is the introduction of rabbits to Australia. Australia was a land without rabbits until the arrival of European settlers. An Englishman named Thomas Austin released 24 rabbits into the wild of Victoria in October 1859 with the intention of hunting them. If rabbits are famous for one thing it is for reproducing prodigiously. The mild winters allowed year-round breeding and the absence of any natural rabbit predators, such as foxes, allowed the Australian rabbit population to explode unchecked. Within 10 years an annual cull of two million rabbits was having no noticeable effect on rabbit numbers and the habitats of some native animals were being destroyed by the floppy-eared pests. Today there are hundreds of millions of rabbits in Australia, despite efforts to reduce the population, and the name of Thomas Austin is widely cursed for his catastrophic lack of foresight.

While such invasions of separate species provide a useful analogy for what can happen when we introduce migration into island model evolutionary algorithms, we are specifically interested in the effects of migration involving genetically different members of the same species. This is because, in our simplified model of evolution, all individuals are compatible and can reproduce. The island model of evolution provides the isolation necessary for diversity to thrive while still providing opportunities for diverse individuals to be combined to produce potentially fitter offspring.

In an island model, the isolation of the separate populations often leads to different traits originating on different islands. Migration brings these diverse individuals together occasionally to see what happens when they are combined. Remember that, even if the immigrants are weak, cross-over can result in offspring that are fitter than either of their parents. In this way, the introduction to the population of new genetic building blocks may result in evolutionary progress even if the immigrants themselves are not viable in the new population.

Islands in the Watchmaker Framework

The Watchmaker Framework for Evolutionary Computation supports islands models via the IslandEvolution class. Each island is a self-contained EvolutionEngine just like those we have been using previously for single-population evolutionary algorithms. The evolution is divided into epochs. Each epoch consists of a fixed number of generations that each island completes in isolation. At the end of an epoch migration occurs. Then, if the termination conditions are not yet satisfied, a new epoch begins.

The IslandEvolution supports pluggable migration strategies via different implementations of the Migration interface. An island version of the string evolution example from this previous article might look something like this:

IslandEvolution engine  = new IslandEvolution(5, // Number of islands.
                                              new RingMigration(),
                                              candidateFactory,
                                              evolutionaryOperator,
                                              fitnessEvaluator,
                                              selectionStrategy,
                                              rng);
 
engine.evolve(100, // Population size per island.
              5, // Elitism for each island.
              50, // Epoch length (no. generations).
              3, // Migrations from each island at each epoch.
              new TargetFitness(0, false));

We can add listeners to an IslandEvolution object, just as we can with individual EvolutionEngines. We use a different interface for this though, IslandEvolutionObserver, which provides two call-backs. The populationUpdate method reports the global state of the combined population of all islands at the end of each epoch. The islandPopulationUpdate method reports the state of individual island populations at the end of each generation.

Advanced Usage

In the example code above we specified how many islands we wanted to use and the IslandEvolution class created one GenerationalEvolutionEngine for each island. Using this approach all of the islands have the same configuration; they use the same candidate factory, evolutionary operator(s) and selection strategy. This is the easiest way to create an island system but it is also possible to construct each island individually for ultimate flexibility.

List> islands = new ArrayList>();
 
// Create individual islands here and add them to the list.
// ...
 
IslandEvolution engine  = new IslandEvolution(islands,
                                              new RingMigration(),
                                              false, // Natural fitness?
                                              rng);

One reason you might choose to construct the islands explicitly is that it makes it possible to configure individual islands differently. You may choose to have different islands use different parameters for evolutionary operators, or even to use different evolutionary operators all together. Alternatively, you could use the same evolutionary operators and parameters but have different selection strategies so that some islands have stronger selection pressure than others. You should generally use the same fitness function for all islands though, otherwise you might get some strange results.

Another possible reason for creating the islands explicitly is so you don’t have to use the standard GenerationalEvolutionEngine for the islands. You can choose to use any implementation of the EvolutionEngine interface, such as the SteadyStateEvolutionEngine class or the EvolutionStrategyEngine class. You can even use a mixture of different island types with the same IslandEvolution object.

This is the fourth entry in a short and increasingly infrequent series of articles on practical Evolutionary Computation, based on the work-in-progress documentation for the Watchmaker Framework for Evolutionary Computation.  The first article provided an introduction to the field of evolutionary computation, the second article showed how to implement a simple evolutionary algorithm using the Watchmaker Framework, and the third article briefly discussed the concept of elitism in evolutionary algorithms.

Further Reading

The Watchmaker Framework for Evolutionary Computation has reached version 0.7.1.  This is an incremental release that refines a couple of the changes made in the substantial 0.7.0 update.  It also adds support for Evolution Strategies to complement the existing support for generational and steady-state evolutionary/genetic algorithms.

In addition, the (still incomplete) user manual has a new section on the different selection strategies that are available.

• Downloads
• Full Changelog
• API Documentation
• User Manual

The Watchmaker Framework for Evolutionary Computation has reached version 0.7.0. If you’re new here, Watchmaker is a Java library for implementing evolutionary/genetic algorithms. This release is the most substantial update for some time.

Backwards-Incompatibilities

Firstly, I’ve refactored the evolution engine so that it is not as tightly tied to the standard generational model of evolution. What this means in practice is that the class formerly known as ConcurrentEvolutionEngine is now called GenerationalEvolutionEngine. For most users this should be the only backwards-incompatibility in this release. The constructor arguments are the same and all the old methods are still there so it should just be a case of updating your code to use the new name. If you were using SequentialEvolutionEngine, and I think this mostly affects the Mahout guys, this class no longer exists. Concurrency is no longer managed via different sub-classes. Instead you should also use GenerationalEvolutionEngine and call the new setSingleThreaded method to force all work to be done synchronously on the request thread.

If you use Watchmaker to evolve BitString objects, this release improves the performance of the provided mutation and cross-over operators. One side-effect of this is that the semantics of the BitStringMutation class have been modified, so you may need to adjust your parameters.

Steady-State Evolution

OK, on to the good stuff. The reason for the evolution engine changes was to make it easier for the framework to support different types of evolutionary algorithm. The benefits of these changes will become more apparent in subsequent releases but there is one example in this release. The framework now has first-class support for steady-state evolution via the new SteadyStateEvolutionEngine. In steady-state evolution the population is evolved one member at a time rather than all members in parallel. This was possible in previous versions of the Watchmaker Framework but only via a nasty hack.

Island Model Evolution

The major new feature in 0.7.0 is support for island model evolution. Instead of evolving a single population, you evolve multiple populations in parallel. The idea is that the different populations will randomly proceed in different directions making it less likely that the evolution will get stuck at a local optimum. What makes this different from simply evolving a single population multiple times is that there is periodic migration of individuals between islands. The motivation behind the migration is that combining independently evolved individuals with different traits will hopefully result in even fitter offspring. There’s a lot more detail that I’m glossing over that I intend to cover in a later post, but if you want to get started right away the IslandEvolution class is the place to start.

Sigma-Scaling Selection

0.7.0 also includes a new selection strategy. SigmaScaling uses the population’s fitness standard deviation to regulate the selection pressure, making premature convergence less likely.

More Information

• Full Changelog
• API Documentation
• (Incomplete) User Manual
• Download

Demo Applets

• Sudoku Solver
• Evolution of the Mona Lisa
• Travelling Salesman
• Biomorphs

Tomek Kaczanowski has written a blog post showing how to use ReportNG with Gradle (an alternative build system for Java/Groovy/Scala). I’ve never used Gradle but it seems to have two things in its favour.  Firstly, it uses Groovy syntax rather than the cumbersome XML employed by Ant. Secondly, it’s not Maven. Maybe I should try it out some day?

I recently signed-up for GitHub. Compared to Java.net or Sourceforge, it provides a much lower barrier of entry for code hosting.  There’s no need to wait an indeterminate period of time for somebody to approve your project, you just upload it. And because it’s a DVCS, it’s easy for other people to fork your projects and submit patches. Open Source project hosting has become so straightforward, thanks to sites like GitHub and the Bazaar-based Launchpad, that it encourages developers to open up code that they might otherwise have kept to themselves. After all, why bother with local repositories and back-ups when you can get somebody else to do it for you and get free web-hosting and issue-tracking too?

I have a number of trivial and incomplete projects hosted in local Subversion repositories. I am slowly adding to GitHub those that have any worthwhile substance to them. I’m making no promises about the quality of this code, and I don’t intend to spend much time supporting it, but I’m putting it out there in case somebody might have a use for it.

First up is Zeitgeist. This is a small Java library/application for identifying common topics among a set of news articles downloaded from RSS feeds. It’s sort of like what Google News does. There is a basic HTML publisher included that generates a web page for displaying the current top news stories, including relevant pictures.

You give the program a list of RSS feeds that cover a certain topic (maybe world news, or music news, or a particular sport) and it uses non-negative matrix factorisation to detect similarities in the article contents and to group the articles by topic. The original idea comes from Programming Collective Intelligence.

The default HTML output looks a bit like the image below, but you could customise it with CSS or by hacking the default templates to modify what information is included (for example, you could add an excerpt instead of just displaying headlines).

The algorithm is not infallible and how well it works depends a lot on the feeds that you select. It’s also non-deterministic, so if you run it multiple times with the same input you will get variations in the output.  Perhaps Zeitgeist is not that useful in it’s current form but it could be used for adding on-topic news headlines to a website or as the basis for something more advanced.

When I released version 0.9.9 of ReportNG last week, I didn’t call it version 1.0 because I thought I’d probably have to fix some problem caused by the changes I’d made. I was right. It turns out that I broke the one tiny piece of JavaScript that the HTML reports use. Well that’s fixed now and, because none of the three people who downloaded 0.9.9 have complained about anything else, and because I’m not keen on double-figure components in version numbers (as in 0.9.10), I’ve decided that this can be version 1.0.  You can get it here (or from the Java.net Maven repository if that’s how you roll).

I’ve just released version 0.9.9 of ReportNG, the HTML/XML reporting plug-in for TestNG. This version incorporates several minor changes, mostly improvements to the HTML/CSS.

If you want to see what ReportNG does, it generates HTML test reports that look something like this. You can customise the appearance with your own stylesheets. ReportNG also generates XML reports for compatibility with tools that support JUnit XML files.

For those of you afflicted by Maven, you should be able to get ReportNG from the Java.net Maven 2 repository. Not being a Maven user, I haven’t actually tested that this works, but it should be less wrong than it was last time.