The Martlesham Heath Laboratory of British Telecommunications Plc has developed what it claims to be the world’s fastest Travelling Salesman algorithm, based on the concept of Charles Darwin’s Theory of Evolution. It is designed to keep the time spent searching for information to a minimum, while also trying to keep an element of serendipity in […]
The Martlesham Heath Laboratory of British Telecommunications Plc has developed what it claims to be the world’s fastest Travelling Salesman algorithm, based on the concept of Charles Darwin’s Theory of Evolution. It is designed to keep the time spent searching for information to a minimum, while also trying to keep an element of serendipity in the search. The algorithm is based on the concept of looking at the Travelling Salesman Problem from a social rather than global perspective, and part of the study was based on the behaviour of ants. The search algorithm is set in motion on a problem to find the shortest travelling distance between several cities, for example. In effect a whole series of ants are thrown on a map of the area and if the system doesn’t find a destination city, it dies, whereas if it does find a chosen destination city it gives birth and grows. Once this has happened, a path develops between the various cities. It runs on a RISC workstation, and British Telecom says the algorithm can solve a 100-point problem in less than two seconds and a 1,000-point problem in under two and a half minutes. Potential applications include video on demand where the algorithm can be used to offer you a shortlist of what you might like to watch from a huge list of options. British Telecom has written the algorithm in C++ and it will be publishing it in Neural Computing Applications in the July issue.