Die Mathe-Redaktion - 23.11.2019 03:43 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 115 Gäste und 4 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » Aktuelles und Interessantes » der nächste Al Zimmermann Contest ab 27.07.2019
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich der nächste Al Zimmermann Contest ab 27.07.2019
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26866
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-21


Siehe azspcs.com/



-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1050
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-23


Hallo viertel,

ja, ich bin mal gespannt, was Al Zimmermann dieses mal wieder ausgebrütet hat. Fifth Avenue klingt irgendwie nach einer optimalen Unterbringung bestimmter Gebäudeumrisse in einer vorgegebenen Grundfläche, aber lassen wir uns mal überraschen, was sich dahinter wirklich verbirgt.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-08-06


Das Problem sieht recht spannend aus. Die Lösung haben Struktur, aber anscheinend nicht soviel, dass man die Struktur nur finden und reproduzieren muss.
Ich habe es mal mit lokalen Suchverfahren versucht und habe damit die ersten 5 Probleme gelöst(*).
Da die besten Werte jetzt auch wieder auf der Seite mit aufgeführt werden, werde ich in den nächsten Tagen mal nach und nach für alle n einen Durchlauf machen und schauen, wo ich damit lande.

(*) "optimale Lösung" / "gelöst" -- bedeutet hier immer "den besten bekannten(!) Wert (gefunden)"



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1050
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-08-06


Hallo Kitaktus,

ich finde die Programmieraufgabe auch sehr interessant.

Habe auch schon gerätselt, ob die optimale Lösung eine bestimmte Struktur bzw. ein bestimmtes Muster aufweisen muss, aber hatte diesbezüglich noch keine passende Programmieridee, weil ich noch keine ausgereifte Idee habe, welches Muster es sein könnte.

Bin erstmal mit einem rudimentäreren Ansatz rangegangen, der zwar auch schon recht passable Ergebnisse erzielt, aber diesmal gibt es wie beim letzten Mal auch wieder sehr viele Teilnehmer mit sehr guten Ergebnissen, so dass es schon eines besonderen Kniffes bedarf, um an die optimalen Lösungen heranzukommen.

Leider hab ich bislang für kein gefordertes $n$ die bisherige Optimallösung, nicht mal für $n=6$.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-08-07


Es ist (leider?!) mal wieder so ein typisches "Simulated-Annealing"-Problem(*). Es bilden sich Strukturen, die lokal betrachtet sehr wenig Energie haben, aber wenn man den Betrachtungsfokus vergrößert, dann treffen die lokalen Cluster irgendwo aufeinander und dort passt es dann nicht so richtig. Jetzt braucht man einen Effekt, die die Cluster wieder aufbricht und eine Neuanordnung der Elemente zulässt.
Ich schätze, dass im Bereich Score 24-25 etliche Leute mit Simulated-Annealing-Ansätzen unterwegs sind.
Das schlägt sich auch in den Zielfunktionswerten wieder. Nach dem ersten Durchlauf waren vier meiner Scores im Bereich 0.93-0.94, während alle anderen im Bereich 0.98-1.00 lagen. Bei den vier Werten habe ich offenbar irgendeine "Barriere" nicht durchbrochen.
Man müsste sich jetzt eigentlich intensiver mit den Strukturen befassen. Aber das kostet halt Zeit...

(*) Siehe hier.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1050
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-08-07


Hallo Kitaktus,

klingt vielversprechend dieser Ansatz "Simulated Annealing". Muss ich mal die nächste Zeit gucken, ob es mir gelingt, daraus einen tauglichen Algorithmus zu basteln.

Letztlich denke ich schon, dass gewisse Strukturen oder Muster erfüllt sein müssen, weil totales Chaos führt ja normalerweise nicht zu einem besten Resultat. Aber gut möglich, dass es mehrere solcher "Cluster" sein müssen, die auf bestimmte Weise verzahnt werden müssen.

Erst dachte ich ja schon, ob man vielleicht solche Muster wie bei den Verknüpfungstafeln symmetrischer oder alternierender Permutationsgruppen verwenden kann, aber das passt nicht, da in der Gruppentafel ja nur $n$ statt $n^{2}$ verschiedene Elemente vorkommen und dann auch nicht klar ist, wie bzw. gemäß welcher Abbildung man $n$ verschiedene Fälle (d. h. Tokenfelder) nutzbringend auf $n^{2}$ verschiedene aufblähen kann. Außerdem gibt es nicht zu jedem $n$ von 6 bis 30 eine symmetrische oder alternierende Permutationsgruppe mit passender Mächtigkeit.

Bisher hab ich lediglich einen Algorithmus, der auf Zufallsfunden kombiniert mit Greedy-Strategie beruht, wobei mein Greedy-Verfahren sehr simpel gehalten ist. Ich verwerfe dort im Gegensatz zu Simulated Annealing sofort solche Lösungen, die eine temporäre Verschlechterung bringen. Aber es leuchtet mir ein, dass man kleinere vorübergehende Verschlechterungen wohl zulassen muss, um zu einer besseren Gesamtlösung zu kommen.

Mal sehen, ob ich meine Ergebnisse noch irgendwie verbessern kann in nächster Zeit.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1342
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-08-07


Ich habe ebenfalls mit einer lokalen Suche (jedoch nicht SA) die ersten 5 Probleme lösen können. Die geraden n scheinen dabei leichter zu sein als die (um 1 kleineren) ungeraden Werte.

Ich gehe davon aus, dass man - wie in den vorherigen Contests eigentlich auch - problemspezifische Eigenschaften ausnutzen muss, um vorne mitzuspielen.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-08-09


So, ich habe meine persönlichen Ziele erreicht: Scores über 99% in allen Probleminstanzen, Durchschnittsscore über 99,5%. Der Rest ist Zugabe.

So richtig Bewegung scheint in den Bestwerten auch nicht mehr zu sein. Seit ich die Scores mitschreibe gab es nur drei Verbesserungen, jeweils im Bereich der letzten angezeigten Nachkommastelle.



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 854
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-08-11


2019-08-07 11:44 - Kitaktus in Beitrag No. 4 schreibt:
Es ist (leider?!) mal wieder so ein typisches "Simulated-Annealing"-Problem(*).

Hallo Kitakus,

ich habe mich auch mal an dem Problem mit diesem Ansatz versucht.
Sehe ich das richtig, dass man dabei nicht auf die Idee verfallen sollte, zwischendurch wieder auf reine Abstiegsverfahren zu wechseln, weil man damit nur wieder „in die lokalen Minima zurückrollt“?





  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-08-12


Für solche Probleme gibt es prinzipiell zwei Strategien:
a) Simulated-Annealing: Verbesserungen werden immer zugelassen. Verschlechterung nur mit einer bestimmten Wahrscheinlichkeit, wobei typischerweise die Wahrscheinlichkeit kleiner gewählt wird, wenn die Verschlechterung groß ist und mit der Zeit sinken sollte, damit man in Richtung Optimum driftet.(*)
(*) Eng verwandt: Threshold-Accepting - Verschlechterungen werden zugelassen, wenn sie nicht zu schlecht sind (über dem Threshold liegen). Der Threshold wird mit der Zeit angehoben.

Im "Endstadium" tritt dann der von dir beschriebene Effekt auf. Sind Verschlechterungen zu selten, so werden die meisten von ihnen in der nächsten Runde der lokalen Suche direkt wieder zurückgenommen. Man "rollt" ins lokale Optimum zurück.
Es gibt hier - unter dem Namen Tabu-Suche - Ansätze, genau das zu verhindern. Es gibt dann eine Liste von Suchschritten, die eine zeitlang nicht direkt zurückgenommen werden dürfen (also tabu sind).

b) Lokale Suche mit Störung: Es werden im Suchlauf nur Verbesserungen zugelassen. Ist ein lokales Optimum erreicht, stört man die Lösung (z.B. durch Permutation einiger Einträge) und startet dann die lokale Suche neu.

Man kann auch beide Strategien verknüpfen:
Man macht Simulated-Annealing, aber ein "Schritt" ist nicht der Übergang zu einem Nachbarn, sondern ein Schritt ist "Lösung stören und bis zum lokalen Optimum suchen". Dann entscheidet man nach dem Simulated-Anealing-Ansatz, ob man die Änderung behält, oder nicht.
Das ist so in etwa mein bisheriger Ansatz.

Übers Wochenende habe ich bei den meisten n (bei 14 von 20) damit noch (kleinere) Verbesserungen erreicht (ca. 15% der verbleibenden Abweichung zum Optimum). Ein bischen Potential gibt es noch, aber ganz große Sprünge werde ich damit wohl nicht machen (zumal mein Rechner so langsam sein Lebensende erreicht hat).



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 854
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-08-13


Danke für die Anregungen. Ich werde auch noch versuchen einen Ansatz der Form „Zufall + Optimierungen mit Tabus“ als Simulated-Annealing-Schritt einzubauen.
Derzeit bewege ich mich im Bereich >95% für große N und >98% für kleine N.
Da hat mein Raspberry Pi 3 also noch etwas zu rechnen für gute Resultate :)

Das du in der öffentlichen Liste keine Bewegung siehst kann auch daran liegen, dass Verbesserungen erst kurz vor Ablauf des Wettbewerbes eingereicht werden. Mir ist nicht bekannt, wie die Community diesbezüglich bei diesem Wettbewerb tickt, aber Zimmermans Seite/Kommentare läd/laden ja quasi dazu ein, nicht jede kleine Verbesserung zu posten.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-08-14


Ich möchte mich etwas korrigieren. Ein bisschen Bewegung ist in den besten Lösungen noch drin, aber es sind hauptsächlich Veränderungen in der letzten Nachkommastelle und da bei den Standings eine Stelle weniger angezeigt wird, sieht man dort fast nichts.

Hinsichtlich der erreichbaren Güte mit meinen Verfahren spielt die Problemgröße keine große Rolle.
Bei allen Problemen der Größe 18-30 liege ich im Bereich 99.35-99.55%. Bei den kleineren Problemen ist die Spreizung etwas größer 99.15-100%.
Mit lokaler Suche allein sollte man mit ein paar Versuchen so im Bereich 93-97% landen.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-08-28


Ein kleines Update:
Mit Nachoptimieren (zusätzliche Betrachtung von 3-, 4- und 5-Austauschen) ließen sich die Ergebnisse etwas verbessern. Insbesondere eine optimale Lösung für N=11 ist dabei mit abgefallen.
Einen größeren Schritt bin ich weitergekommen, als ich am letzten Wochenende mal eine (eingeschränkte) Tabusuche programmiert habe. Die Idee ist, gezielt nach längeren Austausch-Zyklen zu suchen. Gegenüber einer normalen Tabusuche beschränke ich mich auf Austausch-Schritte, die einen vorhandenen Austauschzyklus verlängern: A rückt auf die Position von B, B auf die Position von C, C auf die Position von D usw.



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2016
Mitteilungen: 32
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-10-10


Den aktuellen Wettbewerb finde ich sehr faszinierend, da sich auch nach über zwei Monaten immer noch neue Dinge ausprobieren lassen und manchmal noch zu einer kleinen Verbesserung führen. Über meinen aktuellen 14. Platz will ich mich auch nicht beschweren ;-)

Mein Vorgehen ist ähnlich wie bei Kitaktus - zufällige Ausgangsanordnungen optimieren, dann leicht "stören", wieder optimieren usw.

@Kitaktus: 3er-Austauschungen kann ich auch für n=30 komplett untersuchen (läuft dann aber ein paar Stunden), aber 4er- oder gar 5er-Austauschungen muß man auf geschickt gewählte beschränken - ist bei dir auch so, oder?

Letzte Woche habe ich mich mit Visualisierungen der Lösungen beschäftigt (via matplotlib unter Python), was sehr schöne Muster erkennen lässt (Bilder kann ich hier nicht direkt zeigen, oder?)

@Yggdrasil: ich denke, die meisten Teilnehmer reichen gefundene Lösungen gleich ein. Da seit Ende August keine neue beste Lösung mehr eingereicht wurde, wäre es natürlich auch eine Strategie, diese bis zum Schluss geheim zu halten, um so noch Tomas und Martin vom ersten Platz zu verdrängen.

Sehr neugierig bin ich auf die Methoden, welche Tomas verwendet hat, um so schnell so ausgezeichnete Lösungen zu finden - er hatte sie ja im Prinzip nach einer oder zwei Wochen, bis auf ein paar kleine Verbesserungen.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1050
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-10-12


Also ich bin zwischenzeitlich nicht mehr zu nennenswerten weiteren Verbesserungen gekommen, obwohl ich noch versucht habe, nach dem Simulated Annealing Prinzip vorzugehen. Mal gucken, zwei Wochen läuft der Wettbewerb noch, mal sehen, wer dann am Ende die Nase vorn hat.

Ist das nur bei mir so, dass die Al Zimmermann Webseite nicht erreichbar ist (gestern auch schon nicht)?

LG Primentus

Edit:
Ach ja, hab mich grad dran erinnert, dass es ja vor paar Wochen eine Benachrichtigung gab, dass man auf einen Alternativlink ausweichen soll.



  Profil  Quote  Link auf diesen Beitrag Link
Wally
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.11.2004
Mitteilungen: 8579
Aus: Dortmund, Old Europe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-10-12


Wie ist denn der Alternativlink?

Wally



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1050
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-10-12


Hallo Wally,

das ist dieser hier: Programming Contest
Reversing Nearness ist der aktuelle.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1342
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-10-12


Ich arbeite mich momentan bzgl. der Werte \(n\) von unten nach oben.
Mit meinem jetzigen Algo bin ich für \(n \leq 23\) sehr zufrieden, die Qualität der Ergebnisse für \(n = 24\) lässt aber zu wünschen übrig. Einige Probleme scheinen deutlich schwieriger zu sein als andere (auch kleinere).



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-10-12


2019-10-10 19:36 - woodstock68 in Beitrag No. 13 schreibt:
@Kitaktus: 3er-Austauschungen kann ich auch für n=30 komplett untersuchen (läuft dann aber ein paar Stunden), aber 4er- oder gar 5er-Austauschungen muß man auf geschickt gewählte beschränken - ist bei dir auch so, oder?
Ja, natürlich. Die Positionen der Token, oder die Werte auf den Token müssen nahe beieinander liegen. Wobei man dann "nah" je nach Problemgröße und Zahl der auszutauschenden Token wählen kann.


Letzte Woche habe ich mich mit Visualisierungen der Lösungen beschäftigt (via matplotlib unter Python), was sehr schöne Muster erkennen lässt
(Bilder kann ich hier nicht direkt zeigen, oder?)
Man darf halt keine Lösung daraus erkennen können.
Das es diverse Muster gibt, ist mir klar, aber ich habe den Aufwand der "händischen" Analyse gescheut. Ist halt ein Unterschied, ob ich Rechenzeit verbrauche, oder meine eigene Zeit.


@Yggdrasil: ich denke, die meisten Teilnehmer reichen gefundene Lösungen gleich ein. Da seit Ende August keine neue beste Lösung mehr eingereicht wurde, wäre es natürlich auch eine Strategie, diese bis zum Schluss geheim zu halten, um so noch Tomas und Martin vom ersten Platz zu verdrängen.
Da die Roh-Scores veröffentlicht werden, ist das Geheimhalten von neuen Bestwerten schon attraktiv, wenn man selbst nicht in Führung liegt. Andernfalls stürzen sich die weiter vorn platzierten genau auf diese eine Instanz und finden die richtige Lösung, bevor man selbst zur Spitze aufschließen konnte.
Andererseits, wenn ich eine Verbesserung hätte, würde ich sie sofort einreichen. Die Ehre, sie als erster gefunden zu haben, wäre mir wichtiger als die eher hypothetische Chance am Ende noch zu gewinnen.


Sehr neugierig bin ich auf die Methoden, welche Tomas verwendet hat, um so schnell so ausgezeichnete Lösungen zu finden - er hatte sie ja im Prinzip nach einer oder zwei Wochen, bis auf ein paar kleine Verbesserungen.
Na ja. Tomas kann ziemlich schnell ziemlich schnellen Code erzeugen und hat vermutlich auch einiges an Rechenkapazität zur Verfügung.
Ich hoffe, dass auch ein paar wirklich originelle Ideen eine Rolle spielen, denn den Aspekt "wer kann den gleichen Algorithmus einfach schneller machen", finde ich persönlich nicht so spannend(*).
Der Wettbewerb "Sums and Products II" war so ein Beispiel, bei dem wahrscheinlich alle 30-Punkte-Teilnehmer genau das gleiche programmiert haben.

(*) Das dürfen andere gerne anders sehen. Es ist ja schließlich ein "_Programmier_wettbewerb".

[Die Antwort wurde nach Beitrag No.16 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2016
Mitteilungen: 32
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-10-14


@Kay_S: ja, deine glatten 16 Punkte sind mir vor ein paar Tagen in der Rangliste aufgefallen. Inzwischen hast du ja noch für ein 17. n etwas eingereicht. Ich komme "nur" auf 13 n mit einem vollen Punkt, die 18 ist sehr sehr nahe dran. Da du wahrscheinlich auch Lösungen für die restlichen n im Vorrat hast, rechne ich Ende nächster Woche mit dir relativ weit oben.

@Kitaktus: genau diese Beobachtungen habe ich auch gemacht - wenn ich z.B. vier Tokens erfolgreich vertausche, liegen diese meist ganz nahe beieinander und lagen auch im Ausgangstorus ganz nahe beieinander.
Mit dem neuen Rekord veröffentlichen sehe ich es wie du - falls ich etwas finde, wird es sehr zeitnah eingereicht. Auf einen neuen Rekord für ein n mache ich mir allerdings aktuell keine Hoffnungen mehr.
Ich hoffe auch, dass Tomas mit einer Idee um die Ecke kommt, welche uns an die Stirn schlagen lässt und Sätze wie "ja klar, warum bin ich da nicht selber drauf gekommen" ausrufen lässt ;-)
Bei "Sums and Products II" war es so, dass wenn du wusstest, dass die Lösung durch ein Golomb-Lineal realisiert werden kann, nur noch reine Fleißarbeit übrig blieb ( de.wikipedia.org/wiki/Golomb-Lineal ). So mancher hat dann auch das Fortran-Programm von 1986 im Netz entdeckt...



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2019-10-15


@ Sums and Products II

Mathematisch gesehen ist nicht klar, dass man mit dem algebraischen Ansatz zu optimalen(!) Lösungen kommt.
Wenn man aber sieht, dass nach ein paar Tagen x Teilnehmer die gleiche Punktzahl haben, liegt ja nahe, dass es da einen allgemeingültigen Ansatz geben muss. Den sucht man dann, programmiert ihn nach und findet - wie erwartet - die gleichen Ergebnisse.
Ich befürchte, dass kaum einer ersthaft etwas anderes versucht hat. Daher hat der Wettbewerb praktisch keine neuen Erkenntnisse gebracht.



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2016
Mitteilungen: 32
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-10-15


@ Sums and Products II

Da die Aufgabe des Wettbewerbs nicht identisch mit der Definition eines Golomb-Lineals ist, hast du natürlich recht: ob damit die optimalen Lösungen gefunden wurden ist nicht sicher. Meine damaligen Ansätze VOR der Umsetzung mit Golomb-Linealen waren allerdings um Welten schlechter als die dann gefundenen Lösungen.

Allerdings hat der Wettbewerb Tomas und Gil zu weiteren Forschungen an Golomb-Linealen inspiriert, was auch nicht schlecht ist: cube20.org/golomb/

@ Reversing Nearness

Durch die Visualisierung ist mir folgendes aufgefallen: Ausgehend von meiner besten Lösung eines Grids "schüttele" ich diese ein wenig durch, realisiert durch 1-3 züfällige Vertauschungen von 2 Tokens. Danach laufen dann die Optimierungsschritte. Wenn dabei ein neuer Rekord gefunden wird, bestehen die Unterschiede zur vorherigen Lösung immer in EINER langen Kette von Verschiebungen (und evtl. zusätzlich gefundenen 3er- und 4er-Ketten durch separate Optimierungsschritte). Sowohl die Kette im aktuellen Grid wie auch die Position der zugehörigen Tokens im Initialgrid sind fast immer räumlich sehr nahe.



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2016
Mitteilungen: 32
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2019-10-26 20:56


Gratulation an @Kay_S zum 11. Platz :-)

Mein Ansatz ist weit weniger strukturiert als das Vorgehen von Tomas R. und Martin P.:
- als erstes gilt es, "gute" Ausgangs-Grids dür den zweiten Schritt zu finden. Dazu nehme ich zufällige Grids und führe solange Austauschungen von 2 Tokens durch welche den raw-Score verbessern bis es keinen solchen Austausch mehr gibt. Die Reihenfolge in welcher alle 2er-Vertauschungen untersucht werden ist dabei zufällig gewählt, da sie eine Rolle auf das Endergebnis hat. Ist ein Grid "2er-Tausch-optimiert", werden zufällig zwei Tokens vertauscht und dann wieder eine komplette 2er-Tausch-Optimierung durchgeführt (welche allerdings NICHT exakt die beiden zuvor vertauschten Tokens zurücktauschen darf). Diese beiden Schritte werden ein paar Mal wiederholt. Als Ergebnis erhält man ein Grid mit einem bestimmten raw-Score. Dann wiederholt man das ganze für viele weitere zufällige Grids. Am Ende ist das Grid mit dem kleinsten raw-Score der Kandidat für den zweiten Schritt, der durchaus mal einen Tag oder auch zwei auf dem PC laufen kann.
- der zweite Schritt besteht aus einer kleinen Störung des Grids (z.B. zwei beliebige Tokens vertauschen, oder auch den Token mit dem höchsten raw-Score-Anteil mit einem beliebigen anderen Token oder eine Kettenverschiebung von x Tokens oder zwei- oder dreimal zwei Tokens vertauschen - ich habe da vieles versucht) und anschliessender 2er-Tausch-Optimierung. Falls dabei eine Verbesserung erzielt wird, werden zusätzlich 3er- und 4er-Ketten-Vertauschungen untersucht (immer nur von 3 bzw. 4 Tokens in direkter Nachbarschaft). Diese ergeben oft noch zusätzliche Verbesserungen. Der zweite Schritt kann beliebig lange laufen.

Ein weiterer Ansatz bei der Bestimmung des Startgrids für den zweiten Schritt war, ausgehend von einem zufälligen Grid in jedem Schritt zufällig zwei Tokens auszuwählen und diese zu vertauschen, wenn die raw-Score-Änderung dadurch kleiner einer Schranke war. Diese Schranke wird zu Beginn auf 0 gesetzt, sprich, es sind erst mal nur Verbesserungen des raw-Scores erlaubt. Wenn der zufällig ausgewählte Tausch von 2 Tokens in seiner raw-Score-Änderung über der Schranke liegt, wird er nicht durchgeführt, dafür aber die Schranke erhöht. Am Ende war ich hier bei n^3 / 100 als sinnvollem Wert. Erfüllt ein 2er-Tausch die Schrankenbedingung, wird die Schranke nach dem Austausch wieder auf 0 zurückgesetzt. Das Ganze versucht man für viele zufällig gewählte Vertauschungen (z.B. 500 * n^3) und führt danach noch eine 2er-Tausch-Optimierung durch.

@Kay_S: magst du noch ein paar Worte zu deinem Vorgehen schreiben?



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1342
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2019-10-27 21:41


Hi Helge und Mitstreiter,

Über Platz 11 habe ich mich angesichts der Konkurrenz schon gefreut smile  (aber haarscharf an 10 vorbei - die Zeit hat nicht mehr gereicht).

Im Kern habe ich denselben Ansatz verfolgt, d.h. der Algorithmus realisiert 'Iterated Local Search'. Es werden solange verbessernde Täusche von (einer bestimmten Anzahl) Token durchgeführt, bis ein lokales Optimum erreicht ist. Um aus diesem zu entkommen, wird eine Perturbation mit anschließender lokaler Suche durchgeführt. Falls dieses Nachbaroptimum besser ist, wird zu diesem gewechselt (es werden nur Verbesserungen akzeptiert).

Ich hatte zunächst eine einfache Version, die beliebige Täusche mit 2 oder 3 Token ausprobierte. Nachdem ich mir damit gefundene Verbesserungen angeschaut hatte, ist mir aufgefallen, dass
- die meisten verbessernden Täusche sehr nah beieinander liegende Token betreffen
- es sich fast immer um eine Art Ringtausch handelt, d.h. Token 1 wechselt auf die Position von Token 2, dieses auf 3 usw., Token k wiederum auf 1; die Wechselposition ist meist ein direkter Nachbar
Besonders häufig war ein 4er Tausch in einem 2x2-Rechteck. Ich habe dann eine spezielle Suche programmiert, die sich ausschließlich auf diese Muster beschränkte:
- alle 2er und 4er Täusche in einem 2x2-Rechteck
- alle 3er Täusche in einem 2x3- bzw. 3x2-Rechteck

In einem lokalen Optimum wurden folgende Perturbationen verwendet:
- Tausch dreier zufälliger Token (für kleine n)
- Tausch zweier zufälliger entfernter Token (Mindestabstand) (für große n)

Eine nennenswerte Verbesserung ergab sich weiterhin durch Wechsel zu einer zweiten, deutlich komplexeren Nachbarschaft, falls die Suche in einem 'Elite-Optimum' stecken blieb (d.h. zig Versuche mit Perturbation + lokaler Suche führten zu keinem besseren lokalen Optimum):
- alle 4er Täusche in einem 3x3-Rechteck
- alle 3er Täusche in einem 4x4-Rechteck
Hiermit wurden häufig weitere unentdeckte Verbesserungen gefunden. Danach wird zur schnellen Standardsuche zurückgekehrt, die infolge der vorgenommenen Änderungen häufig wiederum weitere Verbesserungen produzierte.

Als eine weitere gute Strategie stellte sich eine Art von Backtracking heraus: In der Suche wird eine Folge lokaler Optima \(t_0 \rightarrow t_1 \rightarrow \cdots \rightarrow t_k\) erzeugt (mit \(t_k\) als Lösung des aktuellen Durchlaufs). Man kann versuchen, in dieser Sequenz zurückzugehen und eine andere Verzweigung zu nehmen, die in vielen Fällen zu einem besseren Endwert \(t_l\) führt. Das ist möglich, da in einem lokalen Optimum häufig mehr als eine Perturbation+Suche zu einer Verbesserung führt (aus Gründen der Performance war first improvement die Standardstrategie).

Dieses Backtracking fand allerdings teilweise manuell statt, was sehr viel Zeit fraß und auch ermüdend war, so dass ich froh bin, dass der Contest nun zu Ende ist (obwohl der nächste bereits für März angekündigt ist eek ).

Kay





  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6087
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2019-10-28 10:24


Ich bin mit meinen Ergebnissen relativ unzufrieden.
Meine Ansätze waren sehr ähnlich zu denen von Kay:
- wiederholte lokale Suche
- wiederholte lokale Suche + Störung lokal optimaler Lösugen
- Erweiterung der Nachbarschaft (3-Austausche, ...)
- 4er- 5er-Austausche in lokaler Nähe
- Übergang zur "dualen" Lösung(*)
- Spezieller Algorithmus zum Finden von Verbesserungsketten

Ich habe im Prinzip immer eine neue Idee ausprobiert, wenn es mit den vorherigen Ansätzen nicht weiter ging. Im Prinzip brachte jede Idee auch Verbesserungen mit sich, die Ideen waren also im Prinzip gut.
eine Woche vor Schluss habe ich dann nach dem Lesen eines Beitrages hier im Forum eine winzige Änderung(**) im Störungsmodus vorgenommen und schlagartig wurden die Ergebnisse dann nochmal deutlich besser. Leider war dann nicht mehr viel Zeit, um das Auszureizen und um die Nachoptimierung drüber laufen zu lassen.
Fazit: Eine taktische Fehleinschätzung ziemlich am Anfang hat mich zu viel Zeit gekostet.

(*) Duale Lösung: Man vertauscht die Bedeutung von "Position" eines Token und "Beschriftung" eines Tokens. Ein Token, der auf Position (A,A) liegt und die Beschriftung (X,X) hat, wird ersetzt durch einen Token, der auf (X,X) liegt und die Beschriftung (A,A) hat. Macht man nur lokale Suche, so ändert sich dadurch gar nichts. Schränkt man sich aber auf Austausche eine, die "nahe beieinanderliegen", so erhält man durch die Dualisierung eine ganz neue Bedeutung von "nahe beieinander".

(**) Damit 2-Austausche die Störung nicht sofort wieder rückgängig machen können, habe ich als Störung 3-, 4- oder 5-Austausche verwendet. Anscheinend werden Lösungen daurch aber zu sehr gestört.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
woodstock68
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 23.03.2016
Mitteilungen: 32
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2019-10-31 15:48


Hallo Kay,

die Beobachtungen, was sich zwischen zwei Lösungen verändert habe ich auch gemacht und darauf meine Optimierungsschritte abgestimmt.
Dein "Backtracking" war bei mir auch in gewisser Weise vorhanden: Wenn ein Grid nach einer Perturbation mit der anschliessender Optimierung zu einem neuen Rekord geführt hat, hat mein Algorithmus ausgehend vom Grid nach der Perturbation weitere Optimierungen versucht. Damit sich diese von den vorherigen unterschieden, durchläuft der Algorithmus die zu untersuchenden 2er- (oder auch 3er- und 4er-Ketten-) Vertauschungen in zufälliger Reihenfolge. Dadurch konnte besonders zu Beginn der Optimierung oft ein noch besserer lokaler Rekord gefunden werden.

Keinen Ansatz habe ich bei der Frage gefunden, ob es eine "geschickte" bzw. "ungeschickte" Reihenfolge im Untersuchen und Durchführen von z.B. 2er-Vertauschungen gibt. Klar ist, dass jeder Austausch die Menge der danach möglichen 2er-Austauschungen welche den raw-Score weiter verbessern verändert.

Das Schreiben eines Programms zur Bestimmung einer canonical representation eines Grids nach dem Wettbewerb war noch einmal ein wenig fordernd, aber sehr interessant, gerade wegen der nicht kleinen Menge von 128n^4 theoretisch zu untersuchenden Möglichkeiten.

viele Grüße
Helge



  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]