Wie man Ameisen zur Lösung eines Problems Schach (Op-Ed)

Dieser Artikel erschien ursprünglich in The Conversation. Die Publikation beigetragen zu LiveScience des Artikels Experten stimmen: Op-Ed & Einblicke.

Nehmen Sie eine Reihe von Schachfiguren und alles werfen Sie außer für einen Ritter Weg. Legen Sie die Ritter auf einem der 64 Plätze ein Schachbrett.

Machen Sie 63 legale Züge, so dass Sie jedes Feld auf dem Schachbrett genau einmal besuchen? Zur Erinnerung: kann ein Ritter zwei Quadrate in einer geraden Linie, gefolgt von ein neunzig-Grad-Drehung und eine Abkehr von einem weiteren Platz bewegen. Es mag wie eine schwierige Aufgabe, aber dieser Satz von Bewegungen, rief der Ritter Tour in zu viele Möglichkeiten, zählen erreicht werden kann.

Wenn Sie in der Lage sind, die 63 Züge machen und am Ende auf einem Platz, von dem Sie zurück auf den ursprünglichen Platz mit der 64. legalen Zug bewegen können, wird dies als eine geschlossene Tour bezeichnet. Andere Touren sind offene Touren genannt.

Mathematiker haben darüber nachgedacht, wie viele geschlossene Touren vorhanden, und sie haben eine erstaunliche Anzahl sich einfallen: mehr als 26 Billionen. Es gibt so viele offenere Touren, die wir nicht wissen, die genaue Zahl.

Philip Hingston und ich waren so fasziniert von der Ritter-Tour-Problem, die wollten wir eine andere Art und Weise, es zu lösen. Wir fanden, dass die Motivation in der Natur – speziell bei Ameisen.

Ameisen nutzen ein bestimmtes Muster oder Algorithmus, um nach Nahrung zu suchen. Dieser Algorithmus kann verwendet werden, um viele Arten von Problemen einschließlich Reisen Salesman Problem und Vehicle Routing Probleme anzugehen. Philip und Graham fragte sich, ob sie die Ameise Kolonie Optimierung Algorithmus verwenden, um den Ritter-Tour-Problem zu lösen.

Dieser Algorithmus funktioniert folgendermaßen: ein Computerprogramm wird verwendet, um eine Bevölkerung von Ameisen zu simulieren. Diese Ameisen sind beauftragt, eine Lösung für ein Problem finden. Wie jede Ameise über ihre Aufgabe geht, legen sie ein Pheromon-Trail – eine stinkende Substanz, die Ameisen zu verwenden, um miteinander zu kommunizieren. Die erfolgreichsten Ameisen (diejenigen, die das Problem besser lösen), lag in der simulierten Algorithmus mehr Pheromon als jene, die schlecht abschneiden.

Wir wiederholen Sie diesen Vorgang viele Male (vielleicht Millionen Mal). Durch Wiederholungen die Pheromone Wanderwege auf gute Lösungen erhöhen und verringern sie auf die ärmeren Lösungen durch Verdunstung, die auch in der Simulationsalgorithmus programmiert ist.

In der Simulation des Ritters Tour Problem zu lösen konnte die Ameisen nur rechtliche Ritter bewegt und beschränkten sich auf innerhalb der Grenzen des dem Schachbrett zu bleiben. Wenn eine Ameise eine Tour erfolgreich abgeschlossen wurde dann stärken wir die Tour durch Hinterlegung mehr Pheromone auf dieser Tour im Vergleich zu einer Tour, die keine volle Tour war.

Ameisen, die versuchen, spätere Touren zu finden sind eher zu höhere Ebenen der Pheromone zu folgen. Dies bedeutet, dass sie eher die gleichen Bewegungen wie zuvor erfolgreich Ameisen zu machen sind.

Es ist ein Mittelweg gefunden werden. Wenn die Ameisen die erfolgreiche Ameisen zu starr befolgen, wird der Algorithmus schnell zu einer einzigen Tour konvergieren. Wenn wir die Ameisen zu viel fördern, nicht auf die Pheromone der vorherigen Ameisen folgen dann als sie wird nur nach dem Zufallsprinzip handeln. So ist es ein Fall von Einstellungsparameter der Algorithmus um zu versuchen und eine gute Balance zu finden.

Mit diesem Algorithmus, waren wir in der Lage, fast eine halbe million Touren zu finden. Dies war eine deutliche Verbesserung in früheren Arbeiten, die auf einem genetischen Algorithmus beruht. Diese Algorithmen emulieren Darwins Prinzip der natürlichen Evolution – der stärkste. Fitter Mitglieder (diejenigen, die gut für das vorliegende Problem ausführen) einer simulierten Bevölkerung überleben und schwächeren Mitglieder sterben ab.

Es ist nicht leicht zu sagen, warum die Ameise-Algorithmus so gut ausgeführt, wenn im Vergleich zu den genetischen Algorithmus. Vielleicht war es bis auf die algorithmische Einstellungsparameter, oder vielleicht Ameisen wirklich gerne Schach spielen!

Der Ritter Tour Problem wurde bereits 840 n. Chr. gearbeitet. Diese Problemlöser ahnte, dass Ameisen, wenn auch, simuliert das gleiche Puzzle mehr als 1.000 Jahre in der Zukunft anpacken würde.

Graham Kendall funktioniert nicht für, zu konsultieren, eigene Anteile an oder von einem Unternehmen oder einer Organisation, würde profitieren von diesem Artikel, und hat keine relevanten Zugehörigkeiten, finanziert.

Dieser Artikel erschien ursprünglich in The Conversation. Lesen Sie die