Witam
Chcę napisać prosty program C++ implementujący algorytmy genetyczne. Na razie to co robię, rozprzestrzenia mi w populacji dość dobre - najlepsze w populacji ale nie optymalne, rozwiązanie.
Robię funkcję x^2, więc dla 6 bitów, rozwiązanie to 63. Prawdopodobieństwo bycia rodzicem jest proporcjonalne do x^2, więc między 57 a 59 mała różnica, to prawdopodobieństwo nie może być funkcją (celu jak x^2, powinno od czegoś innego zależeć), bo jeśli zechcę znaleźć minimalny błąd, to co wtedy? Więc czym powinno być prawdopodobieństwo ?
Czy wprowadzenie płci to dobry pomysł? Osobniki męskie miałyby bardzo dużo dzieci lub wcale, żeńskie po trochu.
Poza tym - może uzależnić w cross-over, to która cześć wyższa lub niższa bitów zostanie wzięta , od płci? Część większa - dobra na początek - szybkie dojście w pobliże, część dolna - dokładniejsze szukanie.
Powoli, powoli - co chcesz za pomocą tego algorytmu genetycznego rozwiązać?
Najpierw chcę zrobić najprostszy genetyczny, rozwiązujący x^2, potem rozwiązujący parabolę z maksimum czy minimum ewentualnie większego stopnia z dwoma ekstremami. Potem odwrotnie - Szukanie A,B,C dla paraboli metodą minimalnych kwadratów dla zadanych x i y.
A potem może dało by radę zastosować do detektora UTF. Detekcja na rozpoznawać UTF16BE, UTF16LE, UTF32BE, UTF33LE, czy binarny/UTF8. NA razie ręcznie dostrajam detektor a chcę go wyuczyć.
Ad x^2: algorytm genetyczny się do tego całkowicie nie nadaje, wystarczy rozwiązać zwyczajne równanie kwadratowe ;-p
Tym niemniej, jeśli tak bardzo z jakiegoś powodu chcesz to zastosować, jako funkcję przystosowania (fitness) spróbuj np. różnicę między oryginalnym wynikiem a tym aktualnym - powinno coś sensownego zwrócić. Tym niemniej jest to straszne marnowanie czasu - już lepiej byś napisał aplikację do rozwiązywania problemu plecakowego w oparciu o algorytmy genetyczne niż to, co robisz teraz.
Ad detekcji UTF: do tego również algorytm genetyczny się nie nadaje (ani sieci neuronowe, ani blockchain, ani nic z tego gatunku, FWIW) - bardziej pasowałyby jakieś metody wykorzystujące właściwości UTF (np. skanujące byte order mark) czy oparte na analizie tekstu w poszukiwaniu np. słów z języka angielskiego.
szukanie maksimum paraboli jest tylko do testów algorytmu genetycznego.
Celem będzie automatyczne dostrajanie detektora UTF. Działa on w ten sposób że zliczam 4 histogramy: te pozycje bajtowe, które dają w wyniku modulo 4 resztę 0,1,2 czy 3.
I teraz jeśli histogram 0 jest podobny do histogramu 2 daję punkty, podobnie daję punkty gdy podobne są 1 i 3. Ale wielokrotnie musiałem modyfikować procedury dodające punkty. Chcę aby tego się wyuczył.
CrossOver niezbyt działa, bo zamiast generować nowe geny, wybiera jednego z rodziców, np:
pozycje 0,1 czy 4
CO: 0 55,37->55
CO: 1 55,54->54
CO: 4 55,37->37
CO: 0 55,37->55
W pierwszym pokoleniu najwyżej oceniany jest ten o bitach=55, potem wszystkie przybierają tylko takie bity. nie robiłem mutacji, ale crossOver, powinien dawać kwadratową ilość możliwości?
Na szybko napisałem:
#include <cstdint>
#include <vector>
#include <algorithm>
#include <random>
#include <assert.h>
const int nBits = 6;
const int halfPopulSize = 5;
double ThrM = 0.4,ThrF = 0.6;
class Individual {
public:
bool bits[nBits];
double fitness;
void compFitness()
{
int x = decode();
fitness = x*x;
}
void initRandom()
{
for (int i=0; i<nBits; i++)
if (rand() % 2==0)
bits[i] = 0;
else
bits[i] = 1;
}
void crossOver(Individual &a, Individual &b)
{
int pos = rand() % (nBits-1);
for (int i=0; i<=pos; i++)
bits[i] = b.bits[i];
for (int i = pos+1; i < nBits; i++)
bits[i] = a.bits[i];
printf("CO: %d %d,%d->%d\n",pos, a.decode(), b.decode(), decode());
}
int decode()
{
//Decode string as unsigned binary integer - true = 1, false = 0
int accum = 0; int powerof2 = 1;
for (int j = 0; j < nBits; j++)
{
if (bits[j])accum += powerof2;
powerof2 *= 2;
}
return accum;
}
};
std::vector<Individual> males;
std::vector<Individual> females;
std::vector<Individual> newMales;
std::vector<Individual> newFemales;
void initialize()
{
for (int i=0; i<halfPopulSize; i++)
{
Individual ind;
ind.initRandom();
males.push_back(ind);
ind.initRandom();
females.push_back(ind);
}
}
bool compare(const Individual &a, const Individual &b)
{
return a.fitness > b.fitness;
}
void generate()
{
for (int i = 0; i<halfPopulSize; i++)
males[i].compFitness();
sort(males.begin(), males.end(), compare);
for (int i = 0; i<halfPopulSize; i++)
females[i].compFitness();
sort(females.begin(), females.end(), compare);
int hM = (int)(halfPopulSize * ThrM);
int hF = (int)(halfPopulSize * ThrF);
for (int i = 0; i<halfPopulSize; i++)
{
int indexM = rand() % hM;
int indexF = rand() % hF;
Individual ind;
ind.crossOver(males[indexM], females[indexF]);
newMales.push_back(ind);
indexM = rand() % hM;
indexF = rand() % hF;
ind.crossOver(males[indexM], females[indexF]);
newFemales.push_back(ind);
}
males = move(newMales);
females = move(newFemales);
}
void print()
{
for (int i = 0; i<halfPopulSize; i++)
printf("%d ",males[i].decode());
printf("|");
for (int i = 0; i<halfPopulSize; i++)
printf("%d ", females[i].decode());
printf("\n");
}
int main()
{
initialize();
for (int i=0; i<10; i++)
{
generate();
print();
}
return 0;
}
Zrobiłem crossover, by przełamywał między pierwszym a ostatnim punktem różnicy, a nie poza nimi, poza tym zrobiłem by nie było kojarzenia z jednakowymi ani różniącymi się tylko jednymi bitem. Na nic - zawsze wypełnia jednym wybranym. Co robię nie tak?
Pomogła mutacja, robię ją gdy crossOver z klonem lub różniącym się tylko o 1 bit. Oraz dużo pomógł kod Graya.
Poniżej zamieszczam dobrze działający kod. Prawidłowo wyszukuje wyższe z dwóch maksimów.
Teraz chcę zrobić coś takiego: mam zadane 16 punktów X i Y i mam znaleźć A,B,C,D,E dla Ax^4+Bx^3+Cx^2+Dx+E.
Mam 6 liczb rzeczywistych, kod Graya się już nie przyda, nie będzie przełamywania chromosomu na połowę. Może nowymi genami będą te liczby?
Przedtem miałem 8 razy 1 bit teraz 5 razy float?, czyżbym też robił podobnie?
Czyli dla A0B0C0D0E0 i A1B1C1D1E1 otrzymałbym A0B0C1D1E1 ?
a może A2B2C2D2E2 gdzie A2 to coś pośredniego między A0 a A1?
Dla binarnych chromosomów działa, teraz czas na geny rzeczywiste.
#include <cstdint>
#include <vector>
#include <algorithm>
#include <random>
#include <assert.h>
const int nBits = 8;
const int populSize = 100;
double Thr = 0.5;
unsigned int GrayToBinary(unsigned int num)
{
unsigned int mask = num >> 1;
while (mask != 0)
{
num = num ^ mask;
mask = mask >> 1;
}
return num;
}
double fitfun(int x)
{
x = GrayToBinary(x);
return -2.18678 + 0.139089 * x - 0.00210957 * x*x
+ 1.24172e-05 * x*x*x - 2.46726e-08 * x*x*x*x;
}
class Individual {
public:
int x;
double fitness;
void compFitness()
{
fitness = fitfun(x);
}
void initRandom()
{
x = rand() % (1 << nBits);
}
/* void crossOver(Individual &a, Individual &b)
{
int pos = rand() % (nBits-1);
for (int i=0; i<=pos; i++)
bits[i] = b.bits[i];
for (int i = pos+1; i < nBits; i++)
bits[i] = a.bits[i];
printf("CO: %d %d,%d->%d\n",pos, a.decode(), b.decode(), decode());
}*/
static int mutate(int x, int maxBit)
{
if (rand() % 2 > 0)
return x;
else
{
int newx = x ^ (1 << (rand() % maxBit));
return newx;
}
}
void crossOver(Individual &a, Individual &b)
{
int ax = a.x;
int bx = b.x;
if (rand() % 2 == 0)
{
int tmp = ax;
ax = bx;
bx = tmp;
}
int first = -1, last = -1;
for (int i = 0; i<nBits; i++)
{
if ((ax & (1 << i)) != (bx & (1 << i)))
{
if (first == -1) first = i;
last = i;
}
}
if (first<0)
{
x = mutate(ax, nBits);
return;
}
if (first == last)
{
//printf("ax=%d, bx=%d\n",ax,bx);
x = mutate(ax, first + 1);
return;
}
int pos = rand() % (last - first) + first + 1;
x = 0;
//for (int pos = first+1; pos<last+1; pos++)
for (int i = 0; i<pos; i++)
{
if (ax & (1 << i))
x |= (1 << i);
}
for (int i = pos; i<nBits; i++)
{
if (bx & (1 << i))
x |= (1 << i);
}
}
};
std::vector<Individual> popul;
std::vector<Individual> newPopul;
bool compare(const Individual &a, const Individual &b)
{
return a.fitness > b.fitness;
}
void initialize()
{
for (int i = 0; i<populSize; i++)
{
Individual ind;
ind.initRandom();
popul.push_back(ind);
}
for (int i = 0; i<populSize; i++)
popul[i].compFitness();
sort(popul.begin(), popul.end(), compare);
}
/**
return true if is only 1 or 0 set bits
(for 0 retuns true)
if is severeal set bits return false
*/
#define isAlone(x) ((x & (x - 1))==0)
void generate()
{
int goodCount = (int)(populSize * Thr);
for (int i = 0; i<populSize; i++)
{
int indexA = rand() % goodCount;
int indexB = rand() % goodCount;
//int xor = males[indexM].x ^ females[indexF].x;
//if (males[indexM].x !=females[indexF].x && newMales.size()<halfPopulSize && !isAlone(xor))
{
Individual ind;
ind.crossOver(popul[indexA], popul[indexB]);
newPopul.push_back(ind);
}
}
popul = move(newPopul);
for (int i = 0; i<populSize; i++)
popul[i].compFitness();
sort(popul.begin(), popul.end(), compare);
}
void print(int nGen)
{
/*for (int i = 0; i<std::min(10, populSize); i++)
printf("%d ", GrayToBinary(popul[i].x), popul[i].fitness);
printf("\n");*/
if (GrayToBinary(popul[0].x)!=196) printf("%d\n",nGen);
}
int main()
{
double maxf = fitfun(0);
int idxmax = 0;
for (int i = 1; i<256; i++)
{
double f = fitfun(i);
if (f>maxf)
{
maxf = f;
idxmax = i;
}
}
printf("max for %d = %f\n", idxmax, maxf);
initialize();
print(0);
for (int i = 1; i<100; i++)
{
generate();
print(i);
}
return 0;
}