[E-Book Release] Einführung in die Programmierung von Künstlicher Intelligenz

[Shadow992]

Ich hatte darüber ja bereits vor einiger Zeit geschrieben und hatte indirekt versprochen ein Buch über Künstliche Intelligenz zu schreiben und jetzt ist es vorerst fertig.

Das Werk besteht aus 136 (mittlerweile 169) DIN A4 Seiten mit 74 farbigen Abbildungen (keine Ahnung wen das interessiert, aber bei großen Sachbüchern steht das auch oft da ). Damit ist es nicht ganz so groß geworden wie erwartet, was wohl auch daran lag, dass ich 4 Abbildungen weggelassen habe und 2 Kapitel (Schwarmintelligenz (seit dem 11.10.14 ist auch das Thema dabei) und Künstliche Immunsysteme) komplett außen gelassen habe.

Ich freue mich über jegliche Art von Kritik und hoffe vorallem auf Feedback.
Das E-Book soll später auch in diversen E-Book-Sammlungen (also auf Seiten, die kostenlose E-Books anbieten) landen, sobald ich es für bereit halte.

Ich würde mich freuen, wenn ihr Fehler, egal welcher Art, melden könntet, damit meine ich insbesondere Sach-Fehler, aber auch Rechtschreibfehler.

Die neueste Version vom E-Book gibt es auf meiner Seite, die erste Version werde ich jedoch auch hier hochladen, damit sie (vielleicht) länger im Internet verfügbar bleibt als auf meiner Seite.

Download-Link:

Edit:
Inhaltsverzeichnis (05.04.2015):

 Spoiler

Inhaltsverzeichnis
1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1 Vorwort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Programmiererfahrung in Java/AutoIt . . . . . . . . . . . . . . . . . . . . 5
1.3 Sonstige Voraussetzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Verwendungszweck für Künstliche Intelligenz . . . . . . . . . . . . . . . . 6
2 Darstellung von Problemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Grundlegendes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Zweck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Gerichtete Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Zyklische Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.5 Zusammenhängende Graphen . . . . . . . . . . . . . . . . . . . . . 17
2.1.6 Adjazenzmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.7 Adjazenzliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.8 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Simple Suchverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Breiten/Tiefen Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Breitensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Tiefensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Implementierung der Tiefensuche . . . . . . . . . . . . . . . . . . . . . . . 32
3.5.1 AutoIt-Implementierung . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.2 Java-Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Greedy Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.1 Definition und Verwendungszweck . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Bestimmung des kürzesten Weges im Graphen mit Hilfe von Dijkstra . . . 40
4.3 Implementierung des Dijkstra Algorithmus in Java . . . . . . . . . . . . . 44
5 Heuristik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Grundprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.1 Problem des Handlungsreisenden . . . . . . . . . . . . . . . . . . . 51
5.3.2 Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6 Boolesche Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2 Zeichenklärung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Rechenregeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7 Fuzzy Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.2 Fuzzy Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.3 Fuzzyfizierung und Defuzzyfizierung . . . . . . . . . . . . . . . . . . . . . 77
7.4 Fuzzy Zahlen und Arimethrik . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.5 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8 Evolutionäre Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.2 Fitness-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.3 Rekombination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.3.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.3.2 n-Point Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.3.3 Dominant Recombination . . . . . . . . . . . . . . . . . . . . . . . 92
8.3.4 Intermediaries Recombination . . . . . . . . . . . . . . . . . . . . . 92
8.3.5 Partially Mapped Crossover . . . . . . . . . . . . . . . . . . . . . . 92
8.4 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.4.1 Swap Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.4.2 Random Resetting . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.4.3 Inversion Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.4.4 Scramble Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.5 Selektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.5.1 Bestenselektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.5.2 Fitnessproportionale Selektion . . . . . . . . . . . . . . . . . . . . . 96
8.5.3 Turnierselektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.5.4 Rangselektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.6 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
9 Künstliche Neuronale Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
9.1 Einstieg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
9.2 Ein Neuron unter der Lupe (vgl. Biologie) . . . . . . . . . . . . . . . . . . 110
9.3 Verwendungszwecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.4 Vernetzungsstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.4.1 Ebenenweise verbundene Feedforward-Netze . . . . . . . . . . . . . 114
9.4.2 Allgemeine Feedforward-Netze . . . . . . . . . . . . . . . . . . . . . 115
9.4.3 Direkte Rückkopplung (direct feedback) . . . . . . . . . . . . . . . 115
9.4.4 Indirekte Rückkopplung (indirect feedback) . . . . . . . . . . . . . 116
9.4.5 Netze mit Rückkopplung innerhalb der Schicht . . . . . . . . . . . 117
9.4.6 Vollständig verbundene Netze . . . . . . . . . . . . . . . . . . . . . 117
9.5 Arten des Lernens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.5.1 Überwachtes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.5.2 Bestärkendes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.5.3 Unüberwachtes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.6 Aktivierungsfunktion und Bias . . . . . . . . . . . . . . . . . . . . . . . . 120
9.6.1 Logistische Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.6.2 Tangenshyperbolicus . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.7 Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
9.8 Weitere Probleme des Backpropagation Algorithmus . . . . . . . . . . . . 126
9.9 Backpropagation Algorithmus am Beispiel . . . . . . . . . . . . . . . . . . 127
9.10 Lösung der Backpropagation-Probleme . . . . . . . . . . . . . . . . . . . . 136
10 Expertensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
10.1 Grundprinzip und Verwendungszweck . . . . . . . . . . . . . . . . . . . . 137
10.2 Notruftelefon als Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
11 Schwarmintelligenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.1 Allgemein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.2 Ameisensystem-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.2.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.2.2 Ameisensystem in Java . . . . . . . . . . . . . . . . . . . . . . . . . 150
11.3 Partikel Schwarm Optimierung . . . . . . . . . . . . . . . . . . . . . . . . 161
11.3.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
11.3.2 Weitere Ideen für das Partikel Schwarm System . . . . . . . . . . . 165

[c0w]

du machst keine halben sachen was =)

[Shadow992]

Originally Posted by c0w

du machst keine halben sachen was =)

Halbe Sachen leider oft genug.
Fange oft genug Projekte an, mache 2-3 Tage dran und legs dann wieder hin. Aber ich sags mal anders:
Wenn ich etwas vorschlage, dann setz ich mich auch definitiv hin und schau, dass ich was hinkriege, die Frage ist halt nur immer wie lange ich es durchhalte.

[Epvp User]

Also der erste Blick sieht sehr gut aus. Müsste noch ein bisschen Bunter werden denn ich hasse schwarz auf weiß.

[Al Kappaccino]

Hab es eben direkt heruntergeladen und kurz überflogen. Macht auf jeden Fall einen guten Eindruck, werde mich die nächsten Tage mal durchlesen

Danke für deine Mühe!

[.StarSplash]

Danke, Knecht Rup(p)recht!



Habe mal fix überflogen und es in meine EBook-Sammlung aufgenommen, das ist dir auf den ersten Blick wirklich gut gelungen Ich werds mir die Tage mal gründlicher durchlesen, wenn ich Fehler oder Ergänzungen habe, lasse ich sie dir zukommen

PS: Hast du was dagegen, wenn ich ein .epub draus mache? Möchtest du das dann eventuell auch haben?

[Shadow992]

Originally Posted by .StarSplash

Danke, Knecht Rup(p)recht!



Habe mal fix überflogen und es in meine EBook-Sammlung aufgenommen, das ist dir auf den ersten Blick wirklich gut gelungen Ich werds mir die Tage mal gründlicher durchlesen, wenn ich Fehler oder Ergänzungen habe, lasse ich sie dir zukommen

PS: Hast du was dagegen, wenn ich ein .epub draus mache? Möchtest du das dann eventuell auch haben?

Darfst du sehr gerne machen. Schicken brauchst du es mir nicht, werd die Tage ne Art daily-build einbauen, damit man sich immer die neueste Version mit weniger Fehlern runterladen kann. Sobald es neue Kapitel/Andere Erklärungen gibt, werde ich es in einen extra Ordner schieben und das Datum dazu angeben.

Edit: Wenn jemand eine Erklärung nicht versteht, darf ers mir auch gerne sagen, dann versuche ich es anders/besser zu erklären.

[Mostey]

Sehr interessant, habe mal die ersten 25 Seiten gelesen. Leider sprichst du dort (bei den Graphen) nicht sehr viel vom eigentlichen Ziel. Die Verbindung wurde mir zwar relativ schnell klar, allerdings wären Beispiele und vermehrte Integrierung super gewesen.

[Shadow992]

Originally Posted by Mostey

Sehr interessant, habe mal die ersten 25 Seiten gelesen. Leider sprichst du dort (bei den Graphen) nicht sehr viel vom eigentlichen Ziel. Die Verbindung wurde mir zwar relativ schnell klar, allerdings wären Beispiele und vermehrte Integrierung super gewesen.

Wie meinst du das?
Welche Art von Beispiele haben dir gefehlt?
Was das Ziel von Graphen ist, wird man im Buch über merken. Strenggenommen kann man nicht einmal sagen, dass Graphen immer ein bestimmtes Ziel haben, da sie einfach für so viele Sachen benutzt werden können.

Ab Seite 27 gibt es mehr Beispiele mit Code.
Allgemein baut das ganze Buch auf Graphen auf, also wirst du noch etliche Beispiele finden, wobei die Mitte des Buches wieder weniger mit Graphen zu tun hat, gegen Ende wirds dann aber nur noch "graphisch".

[Mostey]

Originally Posted by Shadow992

Wie meinst du das?
Welche Art von Beispiele haben dir gefehlt?
Was das Ziel von Graphen ist, wird man im Buch über merken. Strenggenommen kann man nicht einmal sagen, dass Graphen immer ein bestimmtes Ziel haben, da sie einfach für so viele Sachen benutzt werden können.

Ab Seite 27 gibt es mehr Beispiele mit Code.
Allgemein baut das ganze Buch auf Graphen auf, also wirst du noch etliche Beispiele finden, wobei die Mitte des Buches wieder weniger mit Graphen zu tun hat, gegen Ende wirds dann aber nur noch "graphisch".

Sagtest du ja schon selbst, das Ziel der Graphen und ab und zu eben mal etwas vorausgreifen sofern möglich. Macht es etwas abwechslungsreicher.

[Shadow992]

Originally Posted by Mostey

Sagtest du ja schon selbst, das Ziel der Graphen und ab und zu eben mal etwas vorausgreifen sofern möglich. Macht es etwas abwechslungsreicher.

Alles klar, werde ich versuche in der nächsten Version zu verbessern.

#Die tägliche automatische Akutalisierung ist nun bereit.
Das Ebook wird stündlich geupdated, auch wenn es keinerlei Änderungen gab.

[Eleeya]

Habe es auch eben runtergeladen und flott überflogen, macht einen guten Eindruck. Die Tage habe ich mehr Zeit und ich fuchse mich etwas in das Thema rein
Danke für dieses kleine aber feine Werk

[maxmax37]

Habe mir auch mal das E-Book runtergeladen und die ersten 30 Seiten gelesen. Bei der Programmierung muss ich mir nochmal ein bisschen mehr Zeit nehmen um da durchzublicken, da ich noch Anfänger bin.
Die Graphen hast du auf jeden Fall gut mit dem Flughafenbeispiel erklärt und da ich das zufälligerweise demnächst gebrauchen kann, bin ich schonmal froh, dass ich das jetzt schon verstanden hab
So ganz klar ist mir noch nicht weshalb Graphen so wichtig bei KIs sind, aber du hast ja geschrieben, das sollte sich im Laufe des Buchs klären.

Auf jeden Fall schonmal danke dafür, dass du es kostenlos zur Verfügung stellst

[HardCore.1337]

Hast du das EBook mit Latex gemacht?
Wenn ja, dann kannst du für den Code Listings und für die Graphen automata aus dem Tikz package nehmen. Sieht dann besser aus

Aber ansonsten schön erklärt

[greenryder]

Ich will jetzt nicht unhöflich sein, aber kann es sein, das in deinem AutoIT code "deapthsearch" ein kleiner Fehler ist ?

Folgende Funktion steht ab zeile 41:

Func depthsearch($current_node,$goal_node) ; Unsere Tiefensuche-Funktion
	; Überprüfe, ob der momentane Knoten mit unserem Zielknoten verbunden ist bzw. ob der Zielknoten unser aktueller Knoten ist
	if $graph[$current_node][$goal_node]>0 Then
		return $name[$goal_node]
	EndIf

Das Problem dabei ist, dass die Variable $name nicht deklariert ist. Deshalb gehe ich davon aus, dass die Variable $names an dieser stelle gemeint ist.