//---------------------------------------------------------------------------//
//                                                                           //
//                           "ALGORYTM GENETYCZNY"                           //
//                                                                           //
//        kurs:                                                              //
//        - ETE7013L Optymalizacja procesow dyskretnych                      //
//                                                                           //
//        termin:                                                            //
//        - CZW/P 09:15                                                      //
//                                                                           //
//        autorzy:                                                           //
//        - Dominik Chalupczynski                                            //
//        - Stanislaw Kozuchowicz                                            //
//        - Lukasz Fajdek                                                    //
//                                                                           //
//                                                                           //
//---------------------------------------------------------------------------//

#pragma hdrstop
#include <iostream.h>
#include <stdlib.h>

using namespace std;

#define IL_CHROM 500                                          //ilosc chromosomow w populacji
#define DL_CHROM 10                                           //dlugosc chromosomu
#define IL_GEN 1000                                           //ilosc generacji
#define INFINITY 2147483647

//---------------------------------------------------------------------------

class Populacja
{
  public:
    int populacja[IL_CHROM][DL_CHROM];                        //tabilca przechowujaca cala populacje
    long int populacja_f_celu[IL_CHROM];                      //tablica przechowujaca wartosci funkcji celu wszystkich cromosomow z bierzacej populacji
    int tymczasowa[IL_CHROM][DL_CHROM];                       //tablica pomocnicza przechowujaca elementy nowej populacji
    int t[DL_CHROM];                                          //tablica przechowujaca czasy wykonania zadan
    int w[DL_CHROM];                                          //tablica przechowujaca wagi zadan
    int d[DL_CHROM];                                          //tablica przechowujaca deadliney zadan

    int maks(int T);
    void f_celu(int ch_n);
    void krzyzowanie(int ch_1, int ch_2);
    void mutacja(int ch_n);
    void populacja_pocz();
};

//---------------------------------------------------------------------------

int Populacja::maks(int T)
{
  if (T > 0)
    return T;
  else
    return 0;
}

//---------------------------------------------------------------------------

void Populacja::f_celu(int ch_n)                              //funkcja obliczajaca i zapisujaca w tablicy wartosci funkcji celu
{
  int marker;                                                 //zmienna pomocnicza sygnalizujaca ze deadline zostal przekroczony
  long int c = 0;                                             //zmienna przechowujaca czas zakonczenia zadania
  long int T;                                                 //zmienna przechowujaca czas opuznienia zadania
  long int F = 0;                                             //zmienna przechowujaca wartosc funkcji celu

  for (int b = 0; b < DL_CHROM; b++)
  {
    c = c + t[populacja[ch_n][b]];
    T = maks(c - d[populacja[ch_n][b]]);
    if (T != 0) {marker = 1;}
    F = c * w[populacja[ch_n][b]];
  }
  if (marker == 1) {populacja_f_celu[ch_n] = INFINITY;}       //przypisanie chromosomowi niespelniajacemu zalozen wartosci funkcji celu "nieskonczonosc"
  else {populacja_f_celu[ch_n] = F;}
  marker = 0;
  c = 0;
  F = 0;
}

//---------------------------------------------------------------------------

void Populacja::populacja_pocz()                              //funkcja generujaca populacje poczatkowa w sposob losowy
{
  int k;
  int tab_pom[DL_CHROM];
  randomize();

  for (int i=0; i < IL_CHROM; i++)
  {
    for (int l=0; l < DL_CHROM; l++)                          //zerowanie tablicy pomocniczej
      tab_pom[l]=0;

    for (int j=0; j < DL_CHROM; j++)
    {
      k=random(DL_CHROM);
      while (tab_pom[k] == 1)
        k = random(DL_CHROM);
      populacja[i][j] = k;
      tab_pom[k] = 1;
    }
  }
}

//---------------------------------------------------------------------------

void Populacja::krzyzowanie(int ch_1, int ch_2)               //operator krzyzowania dwupunktowego PMX
{
  int g1;                                                     //pierwszy punkt rozkroju
  int g2;                                                     //drugi punkt rozkroju
  int d;
  int g;
  int licznik1 = 0;
  int licznik2 = 0;
  int przodek1[DL_CHROM];
  int przodek2[DL_CHROM];
  int potomek1[DL_CHROM];
  int potomek2[DL_CHROM];
  int naturalne[DL_CHROM];

  for (int i = 0; i < DL_CHROM; i++)                          //wypelnienie tablic pomocniczych
  {
      przodek1[i] = populacja[ch_1][i];
      przodek2[i] = populacja[ch_2][i];
      potomek1[i] = -1;
      potomek2[i] = -1;
      naturalne[i] = i;
  }

  ETYKIETA:

  randomize();
  g1 = random(DL_CHROM); cout << "g1: " << g1 << "  ";
  g2 = random(DL_CHROM); cout << "g2: " << g2 << endl;

  if (g1 == g2) {goto ETYKIETA;}
  else if (g1 > g2) {d = g2; g = g1;}
  else {d = g1; g = g2;}

  for (int j = d+1; j < g; j++)                               //wymiana czesci chromosomu zawartej pomiedzy d i g
  {
    potomek1[j] = przodek2[j];
    potomek2[j] = przodek1[j];
  }

  for (int a = 0; a <= d; a++)
  {
    for (int b = 0; b <DL_CHROM; b++)
    {
      if (przodek1[a] == potomek1[b]) {licznik1+=1;}
      if (przodek2[a] == potomek2[b]) {licznik2+=1;}
    }
  if (licznik1 == 0) {potomek1[a] = przodek1[a];}
  if (licznik2 == 0) {potomek2[a] = przodek2[a];}
  licznik1 = 0;
  licznik2 = 0;
  }

  for (int c = g; c < DL_CHROM; c++)
  {
    for (int e = 0; e <DL_CHROM; e++)
    {
      if (przodek1[c] == potomek1[e]) {licznik1+=1;}
      if (przodek2[c] == potomek2[e]) {licznik2+=1;}
    }
  if (licznik1 == 0) {potomek1[c] = przodek1[c];}
  if (licznik2 == 0) {potomek2[c] = przodek2[c];}
  licznik1 = 0;
  licznik2 = 0;
  }

  for (int o = 0; o < DL_CHROM; o++)
  {
    for (int p = 0; p < DL_CHROM; p++)
    {
      if (potomek1[p] == naturalne[o]) {licznik1 += 1;}
      if (potomek2[p] == naturalne[o]) {licznik2 += 1;}
    }

    if (licznik1 == 0)
    {
      for (int r = 0; r < DL_CHROM; r++)
      {
        if(potomek1[r] == -1) {potomek1[r] = naturalne[o]; goto ETYKIETA1;}
      }
    }
    ETYKIETA1:
    licznik1 = 0;

    if (licznik2 == 0)
    {
      for (int s = 0; s < DL_CHROM; s++)
      {
        if(potomek2[s] == -1) {potomek2[s] = naturalne[o]; goto ETYKIETA2;}
      }
    }
    ETYKIETA2:
    licznik2 = 0;
  }

                for (int k = 0; k < DL_CHROM; k++)
                {
                cout << potomek1[k] + 1 << "  ";
                }
                cout << endl;
                for (int n = 0; n < DL_CHROM; n++)
                {
                cout << potomek2[n] + 1 << "  ";
                }
                cout << endl;
}

//---------------------------------------------------------------------------

void Populacja::mutacja(int ch_n)                             //mutacja- operator wymiany wzajemnej
{
  randomize();
  int poz = random(DL_CHROM);
  int temp = populacja[ch_n][poz];
  populacja[ch_n][poz]= random(DL_CHROM);
  for (int p = 0; p < DL_CHROM; p++)
  {
    if(populacja[ch_n][p] == populacja[ch_n][poz] && p != poz)
    {
      populacja[ch_n][p] = temp;
    }
  }
}

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
  Populacja pop;
  pop.populacja_pocz();

  pop.t[0]=32;   pop.w[0]=6;   pop.d[0]=293;                  //przykladowe dane
  pop.t[1]=29;   pop.w[1]=7;   pop.d[1]=203;
  pop.t[2]=44;   pop.w[2]=8;   pop.d[2]=426;
  pop.t[3]=59;   pop.w[3]=7;   pop.d[3]=480;
  pop.t[4]=85;   pop.w[4]=8;   pop.d[4]=585;
  pop.t[5]=87;   pop.w[5]=6;   pop.d[5]=548;
  pop.t[6]=14;   pop.w[6]=10;  pop.d[6]=548;
  pop.t[7]=66;   pop.w[7]=4;   pop.d[7]=585;
  pop.t[8]=46;   pop.w[8]=8;   pop.d[8]=427;
  pop.t[9]=72;   pop.w[9]=6;   pop.d[9]=157;

  for (int i = 0; i < DL_CHROM; i++)
  {
    cout << "Zadanie" << i +1 << ":        t[" << i << "]= " << pop.t[i] << "    " << "w[" << i << "]= " << pop.w[i] << "    " << "d[" << i << "]= " << pop.d[i] << "    " << endl;
  }

                for(int x = 0; x < IL_CHROM; x++)
                {
                  for(int z = 0; z< DL_CHROM; z++)
                  {
                    cout << pop.populacja[x][z] +1  << "  ";
                  }
                  pop.f_celu(x);
                  cout << "wart. f_celu= " << pop.populacja_f_celu[x] << endl;
                  cout << endl;
                }

                pop.krzyzowanie(IL_CHROM - 2, IL_CHROM - 1);

                int dobre=0;
                for (int t = 0; t < IL_CHROM; t++)
                {
                  if (pop.populacja_f_celu[t] < INFINITY) {dobre+=1;}
                }
                cout << dobre << endl;

        system("PAUSE");
        return 0;
}
//---------------------------------------------------------------------------
