Tabu Search

In a year old comment on a three year old post relating to vocabulary ordering using simulated annealing, Chris Huntley suggests tabu search might be a better approach.

Unfortunately, I only noticed the post now (sorry Chris). I hadn't come across tabu search before but started to do some investigation and wrote the beginnings of a Python implementation. My limited understanding so far is that you essentially do a local search amongst all possible swaps but keep a list of recent swaps that are "taboo" (hence the name) so you aren't always picking the local optimum.

I started off just writing a local search version (without the tabu) and found that on my programming competition, I could get the global optimum in Category I and a pretty good score for Category II (almost as good as I could get using SA). The problem is that the local search is damn slow.

Unlike the travelling salesman problem where a swap doesn't require full recalculation of the score, in my vocabulary ordering problem, I haven't yet worked out a way to avoid having to run the entire scorer for every swap. In local search, that's O(n²) in the number of verses (Category III hasn't finished running yet after 12 hours).

I need to work out a way of improving that before I finish implementing the rest of the tabu search.

I'm also thinking ant colony optimization might be another approach.

Of course, people with more experience in these algorithms than me are more than welcome to submit an entry in the programming competition using them.