// (c) 2003. Dinko Korunic 'kreator'
// cetvrta laboratorijska vjezba iz APR
//
// Genetski algoritam: Naciniti programsku implementaciju genetskog
// algoritma koja ce traziti optimum zadanog optimizacijskog problema

#include <stl.h>
#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
#include <time.h>
#include <math.h>

// makroi za skipanje razlicitih delimitera..
#define SkipDelimiterNL(ifs) SkipChar(ifs, " \n")
#define SkipDelimiters(ifs) SkipChar(ifs, " \t")

typedef vector<double> Double1D;  // jednodimenzionalni STL vektor
typedef vector<Double1D> Double2D;  // dvodimenzionalni STL vektor

// osnovna klasa
class Matrica
{
  public:
    Matrica(); // osnovni konstruktor
    ~Matrica(); // osnovni destruktor
    Matrica(const int, const int); // konstruktor sa dimenzijama
    Matrica(const Matrica &); // konstruktor sa kopiranjem
    double Dohvati(int, int); // dohvati element
    double Postavi(int, int, const double); // postavi element
    Matrica& operator= (const Matrica &); // nadogr. pridruzivanje
    Matrica operator+ (const Matrica &); // nadogr. zbrajanje
    Matrica operator- (const Matrica &); // nadogr. oduzimanje
    Matrica operator* (const Matrica &); // nadogr. mnozenje
    Matrica operator* (double); // nadogr. mnozenje skalarom
    Matrica& operator+= (const Matrica &); // nadogr. +=
    Matrica& operator-= (const Matrica &); // nadogr. -=
    Matrica& Transponiraj(); // nadogradjeno transponiranje
    int redaka, stupaca; // podaci o podacima :-)
    Double2D podaci; // 2D STL vektor sa elementima
    friend ostream& operator<< (ostream &, Matrica &); // nadogr. <<
    friend istream& operator>> (istream &, Matrica &); // nadogr. >>
}; // class Matrica

// prazni konstruktor - treba nam samo za retke/stupce
Matrica::Matrica()
{
  redaka = stupaca = 0;
} // Matrica::Matrica()

// konstruktor za matricu iz matrice
//      ulaz: referenca na izvornu matricu
//      izlaz: nista
Matrica::Matrica(const Matrica &izvor)
{
  *this = izvor;
} // Matrica::Matrica(const Matrica)

// konstruktor za stvaranje nove matrice proizvoljnih dimenzija
//      ulaz: retci, stupci
//      izlaz: nista
Matrica::Matrica(const int _redaka, const int _stupaca) :
  redaka(_redaka), stupaca(_stupaca)
{
  Double2D tmp(redaka, stupaca);
  podaci = tmp;
} // Matrica::Matrica(int, int)

// standardni destruktor - prazan jer se vektori automatski ciste
//      ulaz: nista
//      izlaz: nista
Matrica::~Matrica()
{
} // Matrica::~Matrica()

// dohvacanje proizvoljnog elementa iz matrice
//      ulaz: stupac, redak
//      izlaz: dohvaceni element
double Matrica::Dohvati(int stupac, int redak)
{
  if (!(--stupac < stupaca))
    throw "Dohvati: stupac izvan matrice";
  if (!(--redak < redaka))
    throw "Dohvati: redak izvan matrice";

  return podaci[redak][stupac];
} // Matrica::Dohvati(int, int)

// postavljanje proizvoljnog elementa u matrici
//      ulaz: stupac, redak, podatak
//      izlaz: postavljeni element
double Matrica::Postavi(int stupac, int redak, const double podatak)
{
  if (!(--stupac < stupaca))
    throw "Postavi: stupac izvan matrice";
  if (!(--redak < redaka))
    throw "Postavi: redak izvan matrice";

  return (podaci[redak][stupac] = podatak);
} // Matrica::Postavi(int, int, double)

// operator pridruzivanja
//      ulaz: referenca na matricu
//      izlaz: referenca na vlastiti objekt
Matrica& Matrica::operator= (const Matrica &izvor)
{
  stupaca = izvor.stupaca;
  redaka = izvor.redaka; // izjednacimo stupce/retke
  podaci = izvor.podaci; // i onda same podatke (nadogr. =)

  return *this;
} // Matrica& operator= (const Matrica &)

// operator zbrajanja
//      ulaz: referenca na matricu
//      izlaz: matrica (novi objekt)
Matrica Matrica::operator+ (const Matrica &izvor)
{
  if ((izvor.stupaca != stupaca)
      || (izvor.redaka != redaka))
    throw "operator+: matrice nemaju iste dimenzije";

  Matrica rezultat(*this); // koristimo nadogradjeno instanciranje
 
  int i, j;
  
  for (i = 0; i < redaka; ++i)
    for (j = 0; j < stupaca; ++j)
      rezultat.podaci[i][j] += izvor.podaci[i][j]; // i za sve elem.
  
  return rezultat;
} // Matrica Matrica::operator+ (const Matrica &)

// operator oduzimanja
//      ulaz: referenca na matricu
//      izlaz: matrica (novi objekt)
Matrica Matrica::operator- (const Matrica &izvor)
{
  if ((izvor.stupaca != stupaca)
      || (izvor.redaka != redaka))
    throw "operator+: matrice nemaju iste dimenzije";

  Matrica rezultat(*this);
 
  int i, j;
  
  for (i = 0; i < redaka; ++i)
    for (j = 0; j < stupaca; ++j)
      rezultat.podaci[i][j] -= izvor.podaci[i][j]; // za sve..
  
  return rezultat;
} // Matrica Matrica::operator- (const Matrica &)

// operator mnozenja skalarom
//      ulaz: skalar
//      izlaz: matrica (novi objekt)
Matrica Matrica::operator* (const double izvor)
{
  Matrica rezultat(*this);
 
  int i, j;
  
  for (i = 0; i < redaka; ++i)
    for (j = 0; j < stupaca; ++j)
      rezultat.podaci[i][j] *= izvor; // za sve elemente
  
  return rezultat;
} // Matrica Matrica::operator* (double)

// operator mnozenja matricom
//      ulaz: referenca na matricu
//      izlaz: matrica (novi objekt)
Matrica Matrica::operator* (const Matrica &izvor)
{
  if (stupaca != izvor.redaka)
    throw "operator*: matrice nisu ulancane";

  Matrica rezultat(redaka, izvor.stupaca);

  int i, j, k;
  
  for (i = 0; i < redaka; ++i)
    for (j = 0; j < izvor.stupaca; ++j)
      for (k = 0; k < stupaca; ++k)
        rezultat.podaci[i][j] += podaci[i][k] * izvor.podaci[k][j];
        // prema formuli A[i][j] = Sum a[i][j]b[k][j], k=1..n

  return rezultat;
} // Matrica Matrica::operator* (const Matrica &)

// operator zbrajanja i izjednacenja
//      ulaz: referenca na matricu
//      izlaz: referenca na matricu
Matrica& Matrica::operator+= (const Matrica &izvor)
{
  return (*this = *this + izvor); // najjednostavnije
} // Matrica& Matrica::operator+= (const Matrica &)

// operator oduzimanja i izjednacenja
//      ulaz: referenca na matricu
//      izlaz: referenca na matricu
Matrica& Matrica::operator-= (const Matrica &izvor)
{
  return (*this = *this - izvor); // najjednostavnije
} // Matrica& Matrica::operator-= (const Matrica &)

// transponiranje matrice
//      ulaz: nista
//      izlaz: referenca na matricu
Matrica& Matrica::Transponiraj()
{
  Matrica rezultat(stupaca, redaka);

  int i, j;
  for (i = 0; i < redaka; ++i)
    for (j = 0; j < stupaca; ++j)
      rezultat.podaci[j][i] = podaci[i][j];
      // napravimo novi objekt tocnih dimenzija
      // i napunimo ga podacima
  
  return (*this = rezultat);
} // Matrica& Matrica::Transponiraj()

// preskacemo zeljene znakove, ma koliko ih god bilo
//      ulaz: input stream, znak za ignoriranje
//      izlaz: nista
void SkipChar(istream &ifs, char *igme)
{
  for (; index(igme, ifs.peek()) != NULL; ifs.ignore());
} // SkipChar(ifstream &, char *)

// operator >>
//      ulaz: input stream, referenca na matricu
//      izlaz: referenca na input stream
istream& operator>> (istream &ifs, Matrica &MOb)
{
  while (ifs.peek() != EOF) // dok mozes citaj
  {
    double tmp;

    MOb.stupaca = 0; // najjednostavnije resetirati svaki put
    Double1D tmpRedak; // privremeni redak

    while (ifs && ifs.peek() != '\n')
    {
      ifs >> tmp; // ucitaj jedan znak
      tmpRedak.push_back(tmp); // i jedan po jedan u vektor
      MOb.stupaca++;
      SkipDelimiters(ifs); // preskoci " " ili "\t"
    }
    MOb.podaci.push_back(tmpRedak); // redak u kompletnu tablicu
    SkipDelimiterNL(ifs); // preskoci "\n" i sl.
    MOb.redaka++;
  }

  return ifs;
} // istream& operator>> (istream &, Matrica &)

// operator <<
//      ulaz: output stream, referenca na matricu
//      izlaz: referenca na output stream
ostream& operator<< (ostream &ofs, Matrica &MOb)
{
  Double2D::iterator it;

  for (it = MOb.podaci.begin(); it != MOb.podaci.end(); ++it)
  {
    ostream_iterator<double> out(ofs, "\t");
    copy(it->begin(), it->end(), out); // iteriraj sve elemente
    ofs << endl;
  }

  return ofs;
} // ostream& operator<< (ostream &, Matrica &)

class Kromosom
{
  public:
    Kromosom(double); // vjerojatnost mutacije
    Kromosom(const Kromosom &); // copy constructor
    double Dobrota(Matrica &); // vraca ocjenu dobrote nekog rjesenja
                                  // za zadani ulazni niz
    Kromosom operator!(); // operator mutacije
    Kromosom operator*(const Kromosom &); // operator krizanja
    void Ispisi(); // ispis parametara
  private:
    unsigned short a[17]; // koeficijenti
    double bUV(unsigned short, int);
    double g(double);
    double VjerojatnostMutacije;
};

// inicijalizacija Kromosoma
Kromosom::Kromosom(double VjerojatnostMutacijeArg)
{
  srandom(time(NULL));

  for (int i = 0; i < 17; ++i)
    a[i] = random();
  VjerojatnostMutacije = VjerojatnostMutacijeArg;
}

// copy constructor Kromosoma
Kromosom::Kromosom(const Kromosom &izvor)
{
  for (int i = 0; i < 17; ++i)
    a[i] = izvor.a[i];
  VjerojatnostMutacije = izvor.VjerojatnostMutacije;
}

// izracun dobrote
double Kromosom::Dobrota(Matrica &niz)
{
  double x, y, suma = 0.;
  
  for (int i = 0; i < niz.redaka; ++i)
  {
    x = niz.podaci[i][0];
    y = niz.podaci[i][1];
    suma += pow((g(x) - y), 2);
  }
  return suma;
}

// mutacija Kromosoma
Kromosom Kromosom::operator!()
{
  double r, tmp = 1 - pow(1 - VjerojatnostMutacije, 16);
  Kromosom mutirani(VjerojatnostMutacije);
  int pos;
  unsigned short mask;

  srandom(time(NULL));

  for (int i = 0; i < 17; ++i)
  {
    r = random() / RAND_MAX;
    if (r < tmp) // mijenja li se doticni poddio?
    {
      pos = random() % 16;
      mask = (unsigned short)pow(2, pos);
      mutirani.a[i] = a[i] ^ mask; // mutiraj ga!
    }
    else
      mutirani.a[i] = a[i]; // ne mutira..
  }
  return mutirani;
}

// binarno krizanje Kromosoma
Kromosom Kromosom::operator*(const Kromosom &desni)
{
  unsigned short r;
  Kromosom krizani(VjerojatnostMutacije);

  srandom(time(NULL));

  for (int i = 0; i < 17; ++i)
  {
    r = random();
    // krizaj!
    krizani.a[i] = (a[i] & desni.a[i]) | (r & (a[i] ^ desni.a[i]));
  }
  return krizani;
}

// ispis Kromosoma
void Kromosom::Ispisi()
{
  for (int i = 0; i < 17; ++i)
    cout << "A[" << i << "]=" << bUV(a[i], i) << endl;
}

// izracunaj vrijednost poddijela Kromosoma
double Kromosom::bUV(unsigned short b, int i)
{
  double dg, gg;
  switch (i)
  {
    // granice varijabli..
    case 0: case 1: case 2: case 5: case 8: case 11: case 14:
      dg = -10; gg = 10; break;
    case 3: case 6: case 9: case 12: case 15:
      dg = 0; gg = 2; break;
    case 4: case 7: case 10: case 13: case 16:
      dg = -5; gg = 5; break;
  }
  return dg + b*(gg - dg) / (pow(2, 16) - 1.);   
}
 
double Kromosom::g(double t)
{
  double rez;

  // aproksimacijska funkcija, 5 clanova
  rez = bUV(a[0], 0) + bUV(a[1], 1) * t +
        bUV(a[2], 2) * sin(bUV(a[3], 3) * t + bUV(a[4], 4)) +
        bUV(a[5], 5) * sin(bUV(a[6], 6) * t + bUV(a[7], 7)) +
        bUV(a[8], 8) * sin(bUV(a[9], 9) * t + bUV(a[10], 10)) +
        bUV(a[11], 11) * sin(bUV(a[12], 12) * t + bUV(a[13], 13)) +
        bUV(a[14], 14) * sin(bUV(a[15], 15) * t + bUV(a[16], 16));
  return rez;
}

class GA
{
  public:
    GA(int, int, double, Matrica &);
    ~GA();
    void Radi();
  private:
    int VelicinaPopulacije,BrojIteracija;
    double VjerojatnostMutiranja;
    Matrica UlazniPodaci;
    Kromosom **Populacija;
    void Ispisi();
};

GA::GA(int VelicinaPopulacijeArg, int BrojIteracijaArg,
    double VjerojatnostMutiranjaArg, Matrica &UlazniPodaciArg)
{
  VelicinaPopulacije = VelicinaPopulacijeArg;
  BrojIteracija = BrojIteracijaArg;
  VjerojatnostMutiranja = VjerojatnostMutiranjaArg;
  UlazniPodaci = UlazniPodaciArg;

  Populacija = new (Kromosom *)[VelicinaPopulacije];
  for (int i = 0; i < VelicinaPopulacije; ++i)
    Populacija[i] = new Kromosom(VjerojatnostMutiranja);
}

GA::~GA()
{
  for (int i = 0; i < VelicinaPopulacije; ++i)
    delete Populacija[i];
  delete Populacija;
}

void GA::Radi()
{
  srandom(time(NULL));
  
  for (int i = 0; i < BrojIteracija; ++i)
  {
    // odabiremo slucajno 3 razlicite jedinke
    int a, b, c;
    a = random() % VelicinaPopulacije;
    do
      b = random() % VelicinaPopulacije;
    while (b == a);
    do
      c = random() % VelicinaPopulacije;
    while ((c == a) || (c == b));

    // okej, pogledaj dobrote
    double DobrotaA = Populacija[a]->Dobrota(UlazniPodaci);
    double DobrotaB = Populacija[b]->Dobrota(UlazniPodaci);
    double DobrotaC = Populacija[c]->Dobrota(UlazniPodaci);

    int tmp;

    // eliminiraj najlosiju i spremi je u c
    if (DobrotaB > DobrotaC)
    {
      tmp = b;
      b = c;
      c = tmp;
    }
    if (DobrotaA > DobrotaC)
    {
      tmp = a;
      a = c;
      c = tmp;
    }

    // nova populacije je krizanje preostale dvije
    Kromosom *novi = new Kromosom(VjerojatnostMutiranja);
    *novi = *Populacija[a] * *Populacija[b];

    // mutiraj novu populaciju
    *novi = !*novi;

    delete Populacija[c];
    Populacija[c] = novi;

    // i ispisi
    cout << "iteracija " << i << endl;
    Ispisi();
  }
}

void GA::Ispisi()
{
  int najbolji = 0;

  for (int i = 0; i < VelicinaPopulacije; ++i)
    if (Populacija[i]->Dobrota(UlazniPodaci)
        < Populacija[najbolji]->Dobrota(UlazniPodaci))
      najbolji = i;

  cout << "Dobrota najbolje populacije " <<
    Populacija[najbolji]->Dobrota(UlazniPodaci) << endl;
}

// glavna funkcija
int main()
{
  int VelicinaPopulacije;
  int BrojIteracija;
  double VjerojatnostMutiranja;
  Matrica UlazniPodaci;

  cout << "Unesite velicinu populacije: ";
  cin >> VelicinaPopulacije;
  cout << "Unesite broj iteracija: ";
  cin >> BrojIteracija;
  cout << "Unesite vjerojatnost mutiranja: ";
  cin >> VjerojatnostMutiranja;

  ifstream datoteka("podaci.ga");
  datoteka >> UlazniPodaci;
  datoteka.close();

  GA ga(VelicinaPopulacije, BrojIteracija, VjerojatnostMutiranja,
      UlazniPodaci);

  try
  {
    ga.Radi();
  } // try

  catch (const char *msg)
  {
    cout << "Greska: " << msg << endl;
    return EXIT_FAILURE;
  } // catch

  return EXIT_SUCCESS;
} // main