In einem früheren Artikel habe ich einen Algorithmus beschrieben, mit dem Sie interessantere (im Gegensatz zu kürzeren, wie bei allen von Yandex-Google hergestellten) Wanderrouten zwischen zwei Punkten erstellen können. Der Algorithmus lud Sehenswürdigkeiten, Parks und andere angenehme und interessante Objekte für Fußgänger von der Open Street Map und legte eine Route durch diese. Infolgedessen könnte der Weg 10-20% länger sein, aber viel malerischer und interessanter.
Stadtfotos - Alex 'Florstein' Fedorov
In den Kommentaren schrieben viele, dass sie zusätzlich zu den Routen zwischen zwei Punkten daran interessiert wären, Kreisrouten zu konstruieren, die am selben Punkt beginnen und enden und in ein bestimmtes Zeitlimit passen. Wenn Sie beispielsweise zwei Stunden zum Zug haben oder Freunde treffen, haben Sie in dieser Zeit keine Zeit, irgendwohin zu gehen, aber es ist durchaus möglich, einen Spaziergang zu machen und die Schönheit in der Nähe zu sehen.
Nach einer Reihe von Experimenten habe ich einen genetischen Algorithmus erstellt, der in dieser Situation (für mich) recht gute Routen erstellt. Unter Katzenbeschreibung des Funktionsprinzips und einigen Beispielen.
Benutzer möchten also in der Lage sein, eine kurze Tour durch die Umgebung zu machen und in der angegebenen Zeit (normalerweise 1-2 Stunden) zum Startpunkt zurückzukehren. Wie sich herausstellte, ist diese Art des Spaziergangs sehr gefragt. Zum Beispiel beschreibt der Artikel "Bewegungsmuster von Touristen innerhalb eines Ziels" die Untersuchung von Spuren von 250 Touristen in Hongkong, während 40% der Touristen die Stadt auf einer Rundstrecke in einem Umkreis von 500 Metern um das Hotel erkundeten. Oft hängen die Leute nur herum und wissen nicht, was interessant ist.
Die Aufgabe ist kompliziert, wenn sie sich nicht im Touristenzentrum befindet (wohin Sie auch gehen - Sie werden überall etwas Interessantes finden), sondern irgendwo am Stadtrand, wo Sie nach Sehenswürdigkeiten suchen müssen.
Radius und Auswahl der Sehenswürdigkeiten
Um eine Route zu erstellen, müssen wir zuerst die Sehenswürdigkeiten auswählen, die wir besuchen möchten. Und dafür müssen Sie den Bereich ihrer Suche um den Startpunkt bestimmen. Wenn der Benutzer die maximale Gehzeit in M Minuten festlegt, ist der am weitesten entfernte Punkt, zu dem Sie gelangen und Zeit haben, um zurückzukehren, der Punkt in einer Entfernung (V * M / 2), wobei V die Geschwindigkeit des Fußgängers ist.
Die durchschnittliche bevorzugte Geschwindigkeit eines Fußgängers kann als 1,4 Meter pro Sekunde angesehen werden. Beim Sightseeing geht eine Person jedoch etwas langsamer, da sie zusätzliche Zeit auf einer Tour verbringt. Ich baute einige Routen in der Stadt und ging sie entlang, wobei ich den Zeitpunkt des Spaziergangs mit den Vorhersagen der Anwendung verglich. Als Ergebnis stellte sich heraus, dass meine durchschnittliche Gehgeschwindigkeit etwa 20% geringer war, d.h. ungefähr 1,1 m / s. Da ich regelmäßig anhielt, um Fotos zu machen, überprüfen Sie die Karte, überquerte ich manchmal noch einmal die Straße, um den besten Winkel zu wählen oder Eis zu kaufen.
Ich habe Experimente in unbekannten Gegenden der Stadt durchgeführt. Mit meinem Algorithmus finden Sie dort alle möglichen interessanten Dinge, von denen ich vorher noch nichts gehört hatte. Zum Beispiel ein Denkmal für die erste Broschüre.
Die Auswahl eines Sonderziels in maximaler Entfernung führt zum Bau einer entarteten Kreisroute. Da der Fußgänger keine Zeit mehr hat, den kürzesten Weg in einer geraden Linie zu verlassen, kann er nur diese Attraktion besuchen, dorthin gehen und auf derselben Straße zurückkehren, wie der rote Pfeil zeigt.
Hier können wir entweder weiter weg in den Park gehen oder mehrere Punkte gleichzeitig näher besuchen
Diese Situation widerspricht jedoch der Vorstellung von interessanten Rundwegen, denn tatsächlich haben wir nur eine Straße und ein Objekt gesehen, aber ich möchte am meisten sehen. Daher wurde gemäß den Ergebnissen der Experimente ein Radius gewählt, der einem Drittel des maximalen Abstands entspricht. Mit diesem Suchradius hat der Fußgänger genügend Zeit, um den entferntesten Punkt des Interesses entlang des Radius zu erreichen. Gehen Sie dann bei Bedarf dieselbe Strecke entlang des Akkords, um nach anderen interessanten Objekten zu suchen, und kehren Sie dann rechtzeitig zurück.
Probleme mit dem frontalen Ansatz
Okay, wir haben eine Liste mit Kandidatenattraktionen zusammengestellt. Es bleibt nun zu entscheiden, welche von ihnen und in welcher Reihenfolge wir überprüfen möchten. Höchstwahrscheinlich werden wir keine Zeit haben, sie zu besuchen, daher müssen wir die interessanteste Untergruppe von ihnen auswählen.
Zuerst habe ich versucht, einen einfachen sequentiellen Algorithmus zu formulieren und zu erstellen. Ich stieß jedoch schnell auf eine Reihe von Problemen.
Wenn wir die Situation aus der obigen Abbildung betrachten, ist nicht klar, wo mit dem Bau der Route begonnen werden soll. Wenn der Park die wichtigste, aber am weitesten entfernte Attraktion ist, erhalten wir zunächst eine entartete Version, über die wir zuvor geschrieben haben.
Die nächste naheliegende Lösung besteht darin, die Sehenswürdigkeiten irgendwie zu gruppieren und zu versuchen, nach dem Weg zum profitabelsten Cluster zu suchen und dann hineinzugehen. Aber auch hier ist nicht alles klar: Von welchem Cluster aus soll man starten, welchen Weg soll man gehen. Sie können immer in die Falle tappen, wenn wir den falschen Weg eingeschlagen haben und in die „Wüste“ gerannt sind - ein Gebiet ohne Sehenswürdigkeiten, für das wir nicht genug Zeit haben, um zum Ausgangspunkt zurückzukehren.
Irgendwann wurde mir klar, dass ich praktisch die Arbeit des genetischen Algorithmus erledigte: Ich zeichne verschiedene Routen auf die Karte und versuche festzustellen, wie sehr ich sie persönlich möchte.
Genetischer Algorithmus
Nachdem der Algorithmus eine nummerierte Liste von Attraktionen erhalten hat, sollte er eine geordnete Teilmenge auswählen, die die Grundlage für die Rundstrecke bildet. Die endgültige Route ist in diesem Fall einer der Orte vieler Hauptattraktionen (wir möchten keine Wiederholungen und müssen nicht alle möglichen Objekte verwenden).
Wenn wir die Formel für die Anzahl der Platzierungen von n bis k kennen, können wir die mögliche Anzahl von Optionen schätzen. Wenn wir die einstündige Route um den Palastplatz in St. Petersburg betrachten, gibt es 54 Kandidaten für Hauptattraktionen nach dem Filtern und Clustering in einem Radius von 1320 Metern (wie oben beschrieben definiert).
Höllenbrei aus einem Haufen von Sehenswürdigkeiten in der Mitte, eine Debug-Ausgabe von Sichtbarkeitsbereichen, berechnet nach dem Algorithmus aus dem vorherigen Artikel
Das Prinzip der Auswahl und Sortierung wurde in einem früheren Artikel beschrieben. Außerdem löschen wir zusätzlich Objekte mit einem Interesse von weniger als 3 (wegen derart unbedeutender Objekte ist es unwahrscheinlich, dass eine Person bereit ist, weit zu gehen, es sei denn, es befindet sich nichts anderes in der Nähe). Somit kann die mögliche Anzahl von Routen nach der Formel der Anzahl von Platzierungen von 54 bis 5 berechnet werden. Sie beträgt 379501200. Für eine 2-stündige Route, in deren Radius bereits 151 Sonderziele liegen, entspricht diese Anzahl 73423236600. Nun, das ist zu viel für eine einfache Suche.
Chromosomen und genetische Operatoren
Chromosomen sind in diesem Fall eine Linie, in der jedes Element die Nummer der entsprechenden Hauptattraktion ist. Für solche Aufgaben, bei denen Chromosomen Permutationen oder Anordnungen sind, gibt es speziell optimierte Varianten genetischer Operatoren. Solche Operatoren behalten die Eigenschaft des Chromosoms bei, eine Permutation oder Platzierung des anfänglichen Satzes von Elementen zu bleiben.
- Partial-Mapped Crossover (PMX) wird zum Überqueren verwendet.
- Für die Mutation wird der Austausch von Orten zweier zufälliger Gene (Swap Mutator) verwendet.
Eine Beschreibung der Funktionsweise dieser Operatoren mit Beispielen findet sich beispielsweise in der Arbeit "Genetische Algorithmen für das Problem des Handlungsreisenden: Eine Überprüfung der Darstellungen und Operatoren".
Fitnessfunktion
Die Fitnessfunktion sollte die folgenden Faktoren berücksichtigen, um eine interessante Rundstrecke zu erstellen:
- Das Gesamtinteresse aller besuchten Hauptattraktionen sollte so groß wie möglich sein.
- Die Gesamtreisezeit sollte so nah wie möglich an der vom Benutzer angegebenen Zeit liegen. Die Route sollte weder viel länger noch viel kürzer sein. Kurze Strecken sind nur zulässig, wenn nicht genügend Sehenswürdigkeiten in der Nähe sind.
- Die Route sollte sich nicht kreuzen. Für jede Selbstüberschneidung addieren wir Strafprozentsätze zum Gesamtwert der Funktion.
- Die Form der Route sollte nahe am Kreis liegen, die größtmögliche Fläche der Stadt erfassen und entartete Fälle vermeiden. Dazu geben wir in die Funktion das Verhältnis der Fläche der durch die Route beschriebenen Figur zur Fläche des Kreises ein, in dem die Sehenswürdigkeiten gesucht wurden.
Hier ist ein Beispiel für eine gute Rundreise. Es geht durch zwei Parks und besucht nie zweimal denselben Ort
Hier ist ein Beispiel für eine eindeutig erfolglose Route. Es enthält Sackgassen, in denen der Fußgänger auf dem untersuchten Weg zurückkehren muss, und Selbstkreuzungen. An Kreuzungen wird normalerweise vergeblich Zeit verschwendet, um bereits gesehene Teile der Stadt erneut zu untersuchen.
Der schlechte Weg wurde tatsächlich durch die Genetik erreicht, bei der die Punkte 3 und 4 für die Fitnessfunktion deaktiviert wurden (Geldstrafen für die Selbstüberquerung und für einen kleinen Bereich).
Nuancen
Während des Testens tauchten einige weitere Nuancen auf.
Frist überschritten
Während der Arbeit der Genetik zählen wir die Länge der Route entlang gerader Linien zwischen Punkten. Nachdem wir Objekte für die Kommunikation mithilfe des genetischen Algorithmus ausgewählt haben, suchen wir mithilfe des Algorithmus aus dem vorherigen Artikel nach dem Pfad zwischen ihnen. In diesem Fall kann der Pfad länger werden und nicht mehr genügend Zeit haben. Schließlich kann in der Stadt der kürzeste Weg entlang der Straße oft um ein Vielfaches länger sein als eine gerade Linie.
Im Durchschnitt beträgt der Unterschied normalerweise etwa 10 bis 20%, und wir setzen ihn in die Fitnessfunktion ein (d. H. Die Genetik sucht nach einer Route mit einem Zeitrahmen, der dann beim Erstellen einer detaillierten Route verzehrt wird). Manchmal reicht es nicht aus - Sie müssen die Route neu berechnen. Wir haben solche Orte in Städten, an denen der Unterschied zwischen den Routen „wie ein Vogel“ und „wie ein Fußgänger“ Kilometer beträgt.
Zwischen den Punkten von 50 Metern in einer geraden Linie, aber eineinhalb Kilometer entlang der Bürgersteige und Passagen, die umgangen werden.
Trotzdem überschreitet der Algorithmus manchmal die vom Benutzer festgelegte Zeit, aber dann kann jeder selbst entscheiden, ob er 10-15 zusätzliche Minuten hat oder ob er den Spaziergang vorzeitig beenden muss.
Venedig
Als der Algorithmus fertig war, beschloss ich, zum Spaß Top-Touristenstädte in Europa hinzuzufügen. Es stellte sich als interessant heraus: Die Städte sind überall unterschiedlich, die Merkmale der Kartierung auch in OSM, weshalb ich ständig etwas fertigstellen musste.
Insbesondere die Suche nach Rundstrecken brach in Venedig zusammen. Da dies ein einzigartiges Beispiel für eine Stadt mit nicht verwandten Gebieten ist - die Inseln sind durch den Canal Grande getrennt, durch den es keine Brücken gibt, ist eine Überquerung nur mit der Fähre möglich.
Infolgedessen wählte der Algorithmus einen Teil der Objekte auf einer Seite der Meerenge und einen Teil auf der anderen Seite aus und konnte dann keinen Landweg zwischen ihnen finden und fiel. Ich musste die Erreichbarkeit aller Attraktionen vom Startpunkt aus überprüfen.
Manchmal muss man immer noch auf dem gleichen Weg zurückkommen
Im Beispiel mit dem Park oben gibt es einen Teil der Route, auf dem Sie den gleichen Weg zurücklegen müssen - dies ist eine kleine Halbinsel, auf der ein Denkmal mit einem Flugzeug steht. Der einzige Weg führt zu dieser Halbinsel, und es wird notwendig sein, darauf zurückzukehren. Daher können solche Rückerstattungen nicht vollständig verboten werden. Der Algorithmus hierfür erhöht das Gewicht aller bereits zurückgelegten Kanten, verringert die Wahrscheinlichkeit einer Rückkehr entlang dieser Kanten, macht dies jedoch weiterhin möglich.
Obwohl es manchmal immer noch schlecht funktioniert. Zum Beispiel beschweren sie sich über die Hauptkathedrale in Kaliningrad. Es befindet sich auf einer Insel in der Mitte des Flusses, durch den die Brücke führt. Von dieser Brücke gibt es einen Abstieg und einen Weg zur Kathedrale. Anscheinend erhöht der Algorithmus das Gewicht dieses einzigen Weges zu sehr, was eine Rückkehr unrentabel macht. Infolgedessen führt er fast nie in die Kathedrale, obwohl dies eine der Hauptattraktionen der Stadt ist. Es bedarf noch einer Verfeinerung.
Ergebnisse
Der genetische Algorithmus ist etwas unvorhersehbar, daher ist er manchmal fehlerhaft und zeichnet seltsame Zickzacke. Aber im Allgemeinen bin ich mit dem Ergebnis zufrieden. Was besonders schön ist, der Algorithmus funktioniert nicht nur im Touristenzentrum (wo es kein Problem ist, Spaß zu haben), sondern auch am Rande der Stadt. Wo es oft ohne Hinweise sehr schwierig ist, etwas Interessantes zu finden.
Selbst in den Schlafsäcken im Südwesten von St. Petersburg finden Sie genügend Denkmäler für einen zweistündigen Spaziergang
Sie können den Algorithmus selbst in einer der 77 unterstützten Städte auf unserer Sight Safari-Website oder in unserer Android-Anwendung ausprobieren (ja, wir haben ihn endlich fertiggestellt).
Es ist besonders interessant, wie der Algorithmus in Städten mit komplexem Gelände und Höhen funktioniert. Wir haben der Graphopper Pathfinder-Bibliothek Unterstützung für die Höhenanalyse hinzugefügt, können jedoch nicht überprüfen, wie es sein soll - Peter ist eine zu flache Stadt.
Versuchen Sie im Allgemeinen, Bewertungen zu schreiben, da die Routen korrekt erstellt werden. Sie können sofort die Hinzufügung neuer Städte beantragen.