Die Mathe-Redaktion - 23.08.2019 11:36 - 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!
ListenpunktAnmeldung MPCT Sept.
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 463 Gäste und 21 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: 26822
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: 983
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: 5985
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-08-06 13:09


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: 983
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-08-06 22:19


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: 5985
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-08-07 11:44


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: 983
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-08-07 18:24


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: 1331
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-08-07 21:57


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: 5985
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-08-09 16:27


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
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 839
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-08-11 11: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: 5985
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-08-12 13:57


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: 839
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-08-13 23:18


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: 5985
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-08-14 09:51


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
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]