Inhalte zur Vorlesungswoche #10, Informatik 1 im Wintersemester 2024/25
(EN google-translate)
(PL google-translate)
Thema: Implementierung einer genetischen Optimierung am Beispiel der Generierung von Rorschach-Bilder
https://de.wikipedia.org/wiki/Rorschachtest
|
Sollte noch Zeit bleiben: Kleine Beispiele zu allem, was bisher an Sprachmitteln in C/C++ durchgenommen wurde.
Zusammenstellung wichtiger besonderer für das Rorschachprojekt nützlicher Funktionen
//Grundgerüst:
#include <iostream> //nötig für cin cout
#include <cstring> // nötig für strcpy()
#include <unistd.h> // nötig für usleep
#include <math.h> // nötig für sqrt()
#include <ctime> // nötig für Initialisierung der Pseudozufallsfolge
using namespace std;
int main(void)
{
return 0;
}
//Nützliche Funktionen:
srand(static_cast<unsigned int>(time(0))); //Initialisierung Zufallsprozess
srand(2); //Immer die gleichen "Zufallsgewichte"
//Zufallszahl erzeugen
double zufall()
{
return (double)(rand()%10000)*0.02-100.0; // Wertebereich: +/-99.99
}
cout<<"\033c"; //Reset Terminal
usleep(300000);// 300000 Mikrosekunden "schlafen"
//Mehrere Texte bereitstellen:
char feld[][22] = {
//..........x..........
//012345678901234567890
"* * * * ",
" ",
"* * * * *",
" * ",
" ",
" * * ",
" ",
" * * *",
"* * * *",
" ",
" * *",
" ",
" ",
" * * "
};
Code 0-1: Programmentwurf zur Erzeugung von Rorschachbildern
Problem 1: Bild erzeugen und darstellen:
#include <iostream> //nötig für cin cout
#include <cstring> // nötig für strcpy()
#include <unistd.h> // nötig für usleep
#include <math.h> // nötig für sqrt()
#include <ctime> // nötig für Initialisierung der Pseudozufallsfolge
using namespace std;
int main(void)
{
char feld[][11] = {
//0123456789
" ",
" * ",
" ",
" * ",
" ",
" ",
" * ",
" ",
" * ",
" "
};
for(int i=0;i<10;i++)
cout<<feld[i]<<endl;
return 0;
}
Code 0-2: Problem 1: Bild erzeugen und darstellen.
Problem 2: Definition der Fehlerfunktion
|
Problem 3: Implementierung des Genetischen Algorithmus
Teillösung: Gespiegelte Zufallsbilder und DNA:
#include <iostream> //nötig für cin cout
#include <cstring> // nötig für strcpy()
#include <unistd.h> // nötig für usleep
#include <math.h> // nötig für sqrt()
#include <ctime> // nötig für Initialisierung der Pseudozufallsfolge
#define SPALTEN 10
#define DNAANZAHL 100
#define PIXELZAHL (SPALTEN*SPALTEN)
using namespace std;
void zeigeBild(int bild[])
{
int inx = 0;
cout<<"c"; //Reset Terminal
for(int i=0;i<SPALTEN;i++) //Zeilen des Bildes
{
for(int k=0;k<SPALTEN;k++) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx++; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
//Spiegelung der Zeile
//inx-=SPALTEN;
inx--;
for(int k=SPALTEN-1;k>=0;k--) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx--; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
inx+=SPALTEN;
cout<<endl;
}
}
int main(void)
{
srand(static_cast<unsigned int>(time(0))); //Initialisierung Zufallsprozess
int dna[DNAANZAHL][PIXELZAHL];
//100 Zufallsbilder erzeugen:
for(int i=0;i<DNAANZAHL;i++)
{
for(int k=0;k<PIXELZAHL;k++)
{
dna[i][k]=rand()%2;
}
}
for(int i=0;i<DNAANZAHL;i++)
{
zeigeBild(dna[i]);
usleep(3000000);// 300000 Mikrosekunden "schlafen"
}
return 0;
}
Code 0-3: Teillösung: Gespiegelte Zufallsbilder und DNA.
Bild 0-1: Screenshot.
Teillösung 2: Berechnung der Fehlerfunktion
#include <iostream> //nötig für cin cout
#include <cstring> // nötig für strcpy()
#include <unistd.h> // nötig für usleep
#include <math.h> // nötig für sqrt()
#include <ctime> // nötig für Initialisierung der Pseudozufallsfolge
#define SPALTEN 10
#define DNAANZAHL 100
#define PIXELZAHL (SPALTEN*SPALTEN)
using namespace std;
double fehlerfunktion(int bild[])
{
double err=0.0;
//1. Eine gewissen Mindest- und Maximalanzahl der Pixel (z.B. 30...60%)
int anzahlPixel30Prozent = (PIXELZAHL*30)/100;
int anzahlPixel60Prozent = (PIXELZAHL*60)/100;
int anzahl = 0;
for(int i=0;i<PIXELZAHL;i++)
if(bild[i]==1)
anzahl++;
if(anzahl<anzahlPixel30Prozent)
err+=(double)(anzahlPixel30Prozent-anzahl);
//identisch zu err=err+(double)(anzahlPixel30Prozent-anzahl);
if(anzahl>anzahlPixel60Prozent)
err+=(double)(anzahl-anzahlPixel60Prozent);
//2. Zusammenhang mit der Symmetrieachse (also rechte Spalte bei Bildhälfte)
anzahlPixel30Prozent = (SPALTEN*30)/100;
anzahlPixel60Prozent = (SPALTEN*60)/100;
anzahl = 0;
for(int i=0;i<SPALTEN;i++)
if(bild[SPALTEN-1 + SPALTEN*i]==1)
anzahl++;
if(anzahl<anzahlPixel30Prozent)
err+=(double)(anzahlPixel30Prozent-anzahl);
//identisch zu err=err+(double)(anzahlPixel30Prozent-anzahl);
if(anzahl>anzahlPixel60Prozent)
err+=(double)(anzahl-anzahlPixel60Prozent);
//3. Zusammenhang der Pixel
// Wie komme ich eine Spalte weiter?: index+1
// Wie komme ich eine Zeile weiter?: index+SPALTEN
int inx=0;
for(int i=0;i<SPALTEN;i++)
{
for(int k=0;k<SPALTEN;k++)
{
//wenn nicht Rand, wenn Pixel gesetzt und linker Nachbar nicht, dann Fehler
if(k>0 && bild[inx]>0 && bild[inx-1]==0)
err+=10.0;
//wenn nicht Rand, wenn Pixel gesetzt und rechter Nachbar nicht, dann Fehler
if(k<SPALTEN-1 && bild[inx]>0 && bild[inx+1]==0)
err+=10.0;
//kein Nachbar oben
if(i>0 && bild[inx]>0 && bild[inx-SPALTEN]==0)
err+=5.0;
//kein Nachbar unten
if(i<((SPALTEN-1)*SPALTEN) && bild[inx]>0 && bild[inx+SPALTEN]==0)
err+=5.0;
inx++;
}
}
return err;
}
void zeigeBild(int bild[])
{
int inx = 0;
cout<<"c"; //Reset Terminal
for(int i=0;i<SPALTEN;i++) //Zeilen des Bildes
{
for(int k=0;k<SPALTEN;k++) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx++; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
//Spiegelung der Zeile
//inx-=SPALTEN;
inx--;
for(int k=SPALTEN-1;k>=0;k--) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx--; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
inx+=SPALTEN;
cout<<endl;
}
}
int main(void)
{
srand(static_cast<unsigned int>(time(0))); //Initialisierung Zufallsprozess
int dna[DNAANZAHL][PIXELZAHL];
//100 Zufallsbilder erzeugen:
for(int i=0;i<DNAANZAHL;i++)
{
for(int k=0;k<PIXELZAHL;k++)
{
dna[i][k]=rand()%2;
}
}
for(int i=0;i<DNAANZAHL;i++)
{
zeigeBild(dna[i]);
double err = fehlerfunktion(dna[i]);
cout<<"err="<<err<<endl;
usleep(300000);// 300000 Mikrosekunden "schlafen"
}
return 0;
}
Code 0-4: Teillösung 2: Berechnung der Fehlerfunktion.
Vollständige Lösung nach einigen Verbesserungen an den Optimierungsparametern
#include <iostream> //nötig für cin cout
#include <cstring> // nötig für strcpy()
#include <unistd.h> // nötig für usleep
#include <math.h> // nötig für sqrt()
#include <ctime> // nötig für Initialisierung der Pseudozufallsfolge
#define SPALTEN 15
#define DNAANZAHL 150
#define PIXELZAHL (SPALTEN*SPALTEN)
using namespace std;
double fehlerfunktion(int bild[])
{
double err=0.0;
//1. Eine gewissen Mindest- und Maximalanzahl der Pixel (z.B. 30...60%)
int anzahlPixel30Prozent = (PIXELZAHL*30)/100;
int anzahlPixel60Prozent = (PIXELZAHL*60)/100;
int anzahl = 0;
for(int i=0;i<PIXELZAHL;i++)
if(bild[i]==1)
anzahl++;
if(anzahl<anzahlPixel30Prozent)
err+=(double)(anzahlPixel30Prozent-anzahl);
//identisch zu err=err+(double)(anzahlPixel30Prozent-anzahl);
if(anzahl>anzahlPixel60Prozent)
err+=(double)(anzahl-anzahlPixel60Prozent);
//2. Zusammenhang mit der Symmetrieachse (also rechte Spalte bei Bildhälfte)
anzahlPixel30Prozent = (SPALTEN*30)/100;
anzahlPixel60Prozent = (SPALTEN*60)/100;
anzahl = 0;
for(int i=0;i<SPALTEN;i++)
if(bild[SPALTEN-1 + SPALTEN*i]==1)
anzahl++;
if(anzahl<anzahlPixel30Prozent)
err+=(double)(anzahlPixel30Prozent-anzahl);
//identisch zu err=err+(double)(anzahlPixel30Prozent-anzahl);
if(anzahl>anzahlPixel60Prozent)
err+=(double)(anzahl-anzahlPixel60Prozent);
//3. Zusammenhang der Pixel
// Wie komme ich eine Spalte weiter?: index+1
// Wie komme ich eine Zeile weiter?: index+SPALTEN
int inx=0;
for(int i=0;i<SPALTEN;i++)
{
for(int k=0;k<SPALTEN;k++)
{
//wenn nicht Rand, wenn Pixel gesetzt und linker Nachbar nicht, dann Fehler
if(k>0 && bild[inx]>0 && bild[inx-1]==0)
err+=1.0;
//wenn nicht Rand, wenn Pixel gesetzt und rechter Nachbar nicht, dann Fehler
if(k<SPALTEN-1 && bild[inx]>0 && bild[inx+1]==0)
err+=1.0;
//kein Nachbar oben
if(i>0 && bild[inx]>0 && bild[inx-SPALTEN]==0)
err+=1.0;
//kein Nachbar unten
if(i<((SPALTEN-1)*SPALTEN) && bild[inx]>0 && bild[inx+SPALTEN]==0)
err+=1.0;
inx++;
}
}
//4. Neue Idee: Abstand zum rechten Rand minimieren und zur Mitte
inx=0;
for(int i=0;i<SPALTEN;i++)
{
for(int k=0;k<SPALTEN;k++)
{
if(bild[inx]>0)
{
err+=(double)(SPALTEN-1-k)*0.03;
if(i<SPALTEN/2)
err+=(double)(SPALTEN/2-i)*0.015;
else
err+=(double)(i-SPALTEN/2)*0.015;
}
inx++;
}
}
return err;
}
void zeigeBild(int bild[])
{
int inx = 0;
cout<<"c"; //Reset Terminal
for(int i=0;i<SPALTEN;i++) //Zeilen des Bildes
{
for(int k=0;k<SPALTEN;k++) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx++; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
//Spiegelung der Zeile
//inx-=SPALTEN;
inx--;
for(int k=SPALTEN-1;k>=0;k--) //Spalten des Bilden
{
if(bild[inx]==1)
cout<<'*';
else
cout<<' ';
inx--; //zählt 0..99 durch das eindimensional repräsentierte Bild (alle Pixel hintereinander)
}
inx+=SPALTEN;
cout<<endl;
}
}
int main(void)
{
srand(static_cast<unsigned int>(time(0))); //Initialisierung Zufallsprozess
int dna[DNAANZAHL][PIXELZAHL];
//100 Zufallsbilder erzeugen:
for(int i=0;i<DNAANZAHL;i++)
{
for(int k=0;k<PIXELZAHL;k++)
{
dna[i][k]=rand()%2;
}
}
cout<<"Genetische Optimierung"<<endl;
double alle_fehler[DNAANZAHL];
double ERR_BEST = 99999999999.99;
for(int DURCHLAUF = 0; DURCHLAUF<500;DURCHLAUF++)
{
//Alle Fehler der i. Generation berechnen:
for(int i=0;i<DNAANZAHL;i++)
alle_fehler[i] = fehlerfunktion(dna[i]);
//Das beste 10tel finden
//Bubblesort:
int hilfsarray[PIXELZAHL];
for(int i=0;i<DNAANZAHL*2;i++)
{
for(int k=1;k<DNAANZAHL;k++)
{
if(alle_fehler[k]<=alle_fehler[k-1])
{
double hilf = alle_fehler[k];
alle_fehler[k] = alle_fehler[k-1];
alle_fehler[k-1] = hilf;
//Arraytausch
for(int p=0;p<PIXELZAHL;p++)
hilfsarray[p]=dna[k][p];
for(int p=0;p<PIXELZAHL;p++)
dna[k][p]=dna[k-1][p];
for(int p=0;p<PIXELZAHL;p++)
dna[k-1][p]=hilfsarray[p];
}
}
}
if(alle_fehler[0]<ERR_BEST)
{
cout<<"Durchlauf Nr."<<DURCHLAUF<<" Kleinster Fehler: "<<alle_fehler[0]<<endl;
ERR_BEST = alle_fehler[0];
}
// 1/10 behalten und den Rest rekombinieren:
int inx_einzehntel = DNAANZAHL/10;
for(int i=inx_einzehntel;i<DNAANZAHL;i++)
{
//Auswahl zweier der besten:
int i1 = rand()%inx_einzehntel;
int i2 = (i1 + 1 + rand()%(inx_einzehntel-1))%inx_einzehntel;
for(int k=0;k<PIXELZAHL;k++)
if(rand()%2==0)
dna[i][k] = dna[i1][k];
else
dna[i][k] = dna[i2][k];
}
// Mutationen
for(int i=0;i<DNAANZAHL*5;i++)
{
int inx = inx_einzehntel + 1 + rand()%(DNAANZAHL-inx_einzehntel-1);
int pix = rand()%PIXELZAHL;
dna[inx][pix] = 1 - dna[inx][pix]; // 1=>0 0=>1
}
}
cout<<"In 4 Sekunden erfolgt die Ausgabe aller optimierten Bilder:"<<endl;
usleep(4000000);
for(int i=DNAANZAHL-1;i>=0;i--)
{
zeigeBild(dna[i]);
double err = fehlerfunktion(dna[i]);
cout<<"err="<<err<<endl;
usleep(30000);// 300000 Mikrosekunden "schlafen"
}
return 0;
}
Code 0-5: Vollständige Lösung nach einigen Verbesserungen an den Optimierungsparametern.
|
Bild 0-2: Generierte Rorschachfigur 1.
Bild 0-3: Generierte Rorschachfigur 2.
Bild 0-4: Generierte Rorschachfigur 3.
Bild 0-5: Generierte Rorschachfigur 4.
Bild 0-6: Generierte Rorschachfigur 5.
Bild 0-7: Generierte Rorschachfigur 6.