Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
Zusammenfassung
Für diesen Bericht lag nur ein Auszug oder keine vollständige Fassung vor. Die Zusammenfassung sagt das selbst.
Kurz
Der Auszug beschreibt einen Vergleich von AlphaZero und Tabu-Suche zur Suche nach kantenreichen Graphen ohne Dreier- oder Viererzyklen. Laut Abstract verbesserte ein Curriculum mit Lösungen kleinerer Graphen die bekannten unteren Schranken für mehrere Größen; konkrete Resultate und Studiendetails fehlen im Auszug.
Mittel
Der vorliegende Bericht ist ein Auszug mit Abstract und bibliografischen Angaben, nicht der vollständige Artikel. Er behandelt die Suche nach Graphen mit möglichst vielen Kanten, die keine Dreier- oder Viererzyklen enthalten; das Problem geht laut Abstract auf eine Vermutung von Erdős aus dem Jahr 1975 zurück.
Die Autoren stellen die Aufgabe als sequenzielle Entscheidungsfindung dar und vergleichen AlphaZero, eine Kombination aus neuronaler Netzsteuerung und Baumsuche, mit der heuristischen Tabu-Suche. Beide Verfahren werden durch ein Curriculum unterstützt: Gute Graphen kleinerer Größe dienen als Ausgangspunkt für die Suche nach größeren. Laut Abstract verbessert dieser Ansatz die bekannten unteren Schranken für mehrere Größen. Zudem schlagen die Autoren eine flexible Graphenerzeugungsumgebung und eine permutationsinvariante Netzwerkarchitektur vor. Konkrete Größen, Zahlenwerte, Versuchsdetails und Einschränkungen sind im Auszug nicht enthalten; als Veröffentlichungsort wird arXiv angegeben.
Ausführlich lesen
Der vorliegende Bericht ist ein Auszug: Er enthält ein Abstract sowie Angaben zu Autoren und Veröffentlichungsort, aber keine vollständige Darstellung der Studie. Im Abstract wird ein Problem der extremalen Graphentheorie behandelt, das auf eine Vermutung von Erdős aus dem Jahr 1975 zurückgeht. Gesucht werden Graphen einer vorgegebenen Größe, die möglichst viele Kanten haben und zugleich keine Zyklen der Länge drei oder vier enthalten.
Die Autoren formulieren die Suche nach solchen Graphen als sequenzielles Entscheidungsproblem und vergleichen zwei Verfahren: AlphaZero, das neuronale Netze mit Baumsuche verbindet, und Tabu-Suche, ein heuristisches lokales Suchverfahren. Als zentrale Strategie beschreiben sie ein Curriculum: Die Suche nach größeren Graphen wird mit guten Graphen begonnen, die bei kleineren Größen gefunden wurden.
Laut Abstract verbesserte dieser Ansatz mit beiden Verfahren die bis dahin bekannten unteren Schranken für mehrere Graphengrößen. Der Auszug nennt jedoch weder die konkreten Größen und Schranken noch die Höhe der Verbesserungen oder einen detaillierten Vergleich der Verfahren. Er erwähnt außerdem eine flexible Umgebung zur Graphenerzeugung und eine permutationsinvariante Netzwerkarchitektur, die das Lernen bei der Suche im Graphenraum unterstützen soll.
Als Veröffentlichungsort nennt der Auszug arXiv. Da nur der Abstract und knappe bibliografische Angaben vorliegen, lassen sich aus dem bereitgestellten Text weder die Versuchsanordnung und Resultate im Detail noch Einschränkungen der Studie beurteilen.
Wie die Modelle den Bericht einordnen
Ansicht
Filter
Tempo und Grenzen
- SF-T3 Woran erkennt man, dass KI beginnt, ihre eigene Weiterentwicklung voranzutreiben, und wer darf das erlauben?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV
- amos 43 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 62 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Vertrauen in Modelle
- SF-V5 Was soll heute für das Verhalten und den Betrieb von Modellen gelten?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 50 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug