Habt ihr schonmal mit genetischen Algorithmen professionell gearbeitet?

[Thilo87]

Und wenn man genetische Algorithmen und KNNs einsetzt (einsetzen könnte), um bessere Algorithmen für spezielle Probleme zu generieren? Das wär doch eine Aufgabe der künstlichen Intelligenz. Gibts in dieser Richtung Algorithmen, die soetwas können?

[Mechanics]

Finde ich jetzt wenig erfolgversprechend. Ein Algorithmus ist eine Abstraktion, so etwas wird ein KNN (in der heutigen Form) oder GA nie finden.

[Thilo87]

Ein Programm, das zufällige Zeichenfolgen erzeugt wird auch irgendwann den optimalen Algorithmus für jedes Problem finden
Genetische Algorithmen arbeiten da effizienter, also dass sie einen optimalen Algorithmus "nie" finden würden, ist nicht richtig. Die Frage ist blos, wie man sie dazu kriegt, dass sie intelligenter arbeiten, so dass man keine 1000 Jahre warten muss.

[Bashar]

Die Zielfunktion stelle ich mir schwierig vor, Woran erkennst du denn einen guten Algorithmus? Mal einen Gang runtergeschaltet, woran erkennt man einen korrekten Algorithmus? Richtig, gar nicht.

[Thilo87]

Warum sollte man einen korrekten Algorithmus nicht erkennen können? Man kann beweisen, dass er funktioniert Natürlich müsste dafür ein KNN oder etwas Ähnliches erst einmal die Prädikatenlogik beherrschen, aber das ist ja ein Klacks (Ironie).

[Bashar]

Thilo87 schrieb:

Warum sollte man einen korrekten Algorithmus nicht erkennen können? Man kann beweisen, dass er funktioniert

Halteproblem, Satz von Rice?

Natürlich müsste dafür ein KNN oder etwas Ähnliches erst einmal die Prädikatenlogik beherrschen, aber das ist ja ein Klacks (Ironie).

Vergleichsweise ja, ohne Ironie.

[Columbo]

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.
(Dafür ist natürlich ein Referenzalgorithmus nötig)

[loll]

Arcoth schrieb:

(Dafür ist natürlich ein Referenzalgorithmus nötig)

lol

[volkard]

Thilo87 schrieb:

Und wenn man genetische Algorithmen und KNNs einsetzt (einsetzen könnte), um bessere Algorithmen für spezielle Probleme zu generieren?

Also der da hat geschnallt, was ihm passierte und schaltete einen Schritt zurück:
http://www.acooke.org/malbolge.html

[Gregor]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Im Allgemeinen geht das so nicht. Bashar hat ja schon das Halteproblem erwähnt. Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird? Du kannst das Ergebnis des Algorithmus also nicht mit einer Referenz vergleichen, weil Du unter Umständen kein Ergebnis vom Algorithmus kriegst. Jenseits davon ist der Ansatz nicht praktikabel, da es wohl meistens in Abhängigkeit der Problemgröße exponentiell viele Instanzen einer Problemstellung geben kann. Wenn man also so an die Sache herangeht, dann wird man nie fertig.

Was allerdings teilweise funktioniert ist eine formelle Übersetzung von "Code" in andere Darstellungen bzw. Semantiken, so dass man den Code auf eine Form zurückführt, die der formellen Spezifikation des Algorithmus entspricht. Allerdings geht das nur bei stark eingeschränkten Sprachen.

...siehe zum Beispiel da: https://de.wikipedia.org/wiki/Formale_Semantik#Formale_Semantik_in_der_Informatik

[volkard]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Schon bei sowas einfachem wie sort() kann ich nicht glauben, daß man mit Rumprobieren und Vergleichen weit kommt.

Alle vector<int> aufzuzählen stelle ich mir ein wenig mühsam vor. Wieviele gibt es davon nochmal?

Vielleicht tut das zu testende Programm gar nicht bei allen Eingaben anhalten? Das macht das Testen recht mühsam. Man bräuchte schon eine sagenumwobene Cray⁽¹⁾.

⁽¹⁾ https://www.google.de/#q=cray+endlosschleifen

[Bashar]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Wieso zitierst du etwas, um es dann vollkommen zu ignorieren?

(Dafür ist natürlich ein Referenzalgorithmus nötig)

Auch Unsinn

[Columbo]

Wieviele gibt es davon nochmal?

\sum^{vector::max\\_size()}\_{i = 0} 2^{i\times sizeof(int) \times CHAR\\_BIT} ~=~ \frac{2^{(vector::max\\_size()+1)\times sizeof(int) \times CHAR\\_BIT} - 1}{2^{sizeof(int) \times CHAR\\_BIT}-1}
(Bitte um Bestätigung, ich kenne keine Formel für das Aufsummieren von Zweierpotenzen mit Faktor im Exponenten, das hier kam nur durch ausprobieren heraus)

Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird?

Ich verwette meinen Daumen, dass es in C++ - wo alles endlich ist, auch der Speicher(?) - immer eine absolute Höchstzahl von Operationen gibt, die >= aller Anzahlen von Operationen endlicher Funktionsdurchläufe ist. Das gilt dann als obere Schranke.

Auch Unsinn

Das musst du mir mal erklären. Wie soll ich wissen, ob das Ergebnis das ich von meiner Funktion erhalte richtig ist?
(Edit: ... aber wie überprüfe ich die Korrektheit dieses Referenzalgorithmus? )

[Bashar]

Arcoth schrieb:

Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird?

Ich verwette meinen Daumen, dass es in C++ - wo alles endlich ist, auch der Speicher(?) - immer eine absolute Höchstzahl von Operationen gibt, die >= aller Anzahlen von Operationen endlicher Funktionsdurchläufe ist. Das gilt dann als obere Schranke.

Endlosschleifen existieren bei dir nicht? Außerdem geht es hier nicht um C++.

Auch Unsinn

Das musst du mir mal erklären. Wie soll ich wissen, ob das Ergebnis das ich von meiner Funktion erhalte richtig ist?

Indem du die Spezifikation anwendest. Beispielsweise ist es für einen Sortieralgorithmus absolut nicht nötig, nochmals zu sortieren. Man muss nur prüfen, ob alle Elemente da sind und ob die Ergebnissequenz richtig angeordnet ist.

Edit: ... aber wie überprüfe ich die Korrektheit dieses Referenzalgorithmus?

Indem du sie beweist.

[Columbo]

Man muss nur prüfen, ob alle Elemente da sind und ob die Ergebnissequenz richtig angeordnet ist.

Ah, ich dachte da eher an berechnende Algos. Sowie accumulate oder so.

Endlosschleifen existieren bei dir nicht?

Sind Endlosschleifen auf einmal endlich? Sie werden weiterlaufen und weiterlaufen, und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.
(Ich meinte hier mit Operationen die die der Prozessor ausführt, nicht die die im Code stehen. Vielleicht sollte man eher Taktzyklen nehmen.)

Außerdem geht es hier nicht um C++.

Achso, danke. Volkard hat da nur so Anspielungen gemacht, auf vector<int>, std::sort und so.

[Bashar]

Arcoth schrieb:

Endlosschleifen existieren bei dir nicht?

Sind Endlosschleifen auf einmal endlich? Sie werden weiterlaufen und weiterlaufen, und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

OK, ich verstehe dein Argument. Du sagst, dass Computer effektiv endliche Automaten sind, so dass all die theoretischen Ergebnisse für turingäquivalente Berechenbarkeitsmodelle irrelevant sind. Das ist leider aufgrund der gigantischen Anzahl von Zuständen ein extrem unpraktischer Standpunkt, insbesondere hilft er dir absolut nicht dabei, praktisch die Korrektheit eines beliebigen Algorithmus (besser: Programms) nachzuweisen. Und wenn du mal zurückblätterst, ging es hier genau darum.

[volkard]

Arcoth schrieb:

Wieviele gibt es davon nochmal?

\sum^{vector::max\\_size()}\_{i = 0} 2^{i\times sizeof(int) \times CHAR\\_BIT} ~=~ \frac{2^{(vector::max\\_size()+1)\times sizeof(int) \times CHAR\\_BIT} - 1}{2^{sizeof(int) \times CHAR\\_BIT}-1}

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

[volkard]

Arcoth schrieb:

und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

Oh, das erinnert mich an http://de.wikipedia.org/wiki/Fleißiger_Biber#Die_Funktion_S

[Columbo]

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

Ja, aber immer wenn ich mit dir diskutiere werde ich total mathegeil. Kannst du das erklären?

volkard schrieb:

Arcoth schrieb:

und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

Oh, das erinnert mich an http://de.wikipedia.org/wiki/Fleißiger_Biber

Danke! Das schaue ich mir gleich an.

@Bashar: Ja, ist genau was ich meine.

[Columbo]

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

Ja, aber laut meiner Kalkulation ist es deutlich größer als $10^{10^9}$:

\frac{2^{(4611686018427387903+1)\*4\*8} - 1}{2^{32}-1} = \frac{2^{147573952589676412928} - 1}{2^{32}-1} \approx 2^{147573952589676412898} \approx 10^{147573952589676412898 * log_{10}2} \approx 10^{4.4424*10^{19}}