daily pastebin goal
38%
SHARE
TWEET

Untitled

a guest Jan 22nd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdafx.h>
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <locale.h>
  5. #include <fstream>
  6. #include <stdio.h>
  7. #include <string>
  8. #include <time.h>
  9.  
  10. using namespace std;
  11.  
  12. void showData(int **exeTimeTable, int *tasksQuantity, int* machinesQuantity, int *path) //wydruk danych
  13. {
  14.     cout << "Ilosc maszyn wynosi: " << *machinesQuantity << ", " << endl;    //maszyny
  15.     cout << "Nalezy na nich wykonac: " << *tasksQuantity << " zadan." << endl;      //zadania
  16.     for (int j = 0; j < *tasksQuantity + 1; j++)
  17.     {
  18.         for (int g = 0; g < *machinesQuantity + 1; g++) cout << " " << exeTimeTable[j][g];
  19.         cout << endl;
  20.     }
  21.     //for (int j = 0; j < *tasksQuantity; j++) cout << path[j] << " ";
  22. }
  23.  
  24. int countPathValue(int *pathValue, int *path, int **exeTimeTable, int tasksQuantity, int machinesQuantity)
  25. {
  26.     int maxTime = 0;
  27.     int **taskEnd;
  28.     *pathValue = 0;
  29.  
  30.     taskEnd = new int*[tasksQuantity + 1];      //??
  31.     for (int i = 0; i < tasksQuantity + 1; i++) taskEnd[i] = new int[machinesQuantity + 1]; //matrix with all time values
  32.  
  33.     for (int j = 0; j < tasksQuantity + 1; j++)
  34.         for (int k = 0; k < machinesQuantity + 1; k++) taskEnd[j][k] = 0;
  35.  
  36.  
  37.     for (int j = 1; j < tasksQuantity + 1; j++)
  38.         for (int k = 1; k < machinesQuantity + 1; k++)
  39.         {
  40.             if (taskEnd[j][k - 1] >= taskEnd[j - 1][k]) maxTime = taskEnd[j][k - 1];
  41.             if (taskEnd[j][k - 1] <= taskEnd[j - 1][k]) maxTime = taskEnd[j - 1][k];
  42.             taskEnd[j][k] = maxTime + exeTimeTable[path[j]][k];     //??
  43.         }
  44.  
  45.     //for (int nr = 0; nr < tasksQuantity; nr++) *pathValue = *pathValue + taskEnd[nr][machinesQuantity];
  46.     *pathValue = taskEnd[tasksQuantity][machinesQuantity];
  47.     return *pathValue;
  48. }
  49.  
  50. void comparePathsValues(int primPathValue, int *bestPathValue, int *pathBest, int *pathPrim, int tasksQuantity)
  51. {
  52.     if (*bestPathValue > primPathValue)
  53.     {
  54.         *bestPathValue = primPathValue;
  55.         for (int nr = 0; nr < tasksQuantity; nr++) pathBest[nr] = pathPrim[nr];     //?
  56.     }
  57. }
  58.  
  59. int generatePermutationNumber(int tasksQuantity) // Liczba z zakresu 0-tasksQuantity
  60. {
  61.     return (rand() % (tasksQuantity)+1);
  62. }
  63.  
  64. float generateProbability() // Liczba z zakresu 0-1
  65. {
  66.     return (1 - (float)(rand() % 100) / 100);
  67. }
  68.  
  69. void generateNewPath(int *path, int tasksQuantity, int machinesQuantity)
  70. {
  71.     int permutationNum1 = generatePermutationNumber(tasksQuantity);
  72.     int permutationNum2 = generatePermutationNumber(tasksQuantity);
  73.     int temp = 0;
  74.     //for (int nr = 1; nr < distNumber + 1; nr++) pathActual[nr] = pathBest[nr];
  75.     cout << endl << "sciezka przed zmiana: ";
  76.     for (int z = 0; z <= tasksQuantity; z++)
  77.     {
  78.         cout << path[z] << "  ";
  79.     }
  80.     cout << "dla permutacji NUM1 =" << permutationNum1 << "I NUM2 =" << permutationNum2 << endl;
  81.     if (permutationNum1 > permutationNum2)
  82.     {
  83.         temp = path[permutationNum2];
  84.         for (int i = permutationNum2; i < permutationNum1; i++) path[i] = path[i + 1];
  85.         path[permutationNum1] = temp;
  86.     }
  87.     if (permutationNum2 > permutationNum1)
  88.     {
  89.         temp = path[permutationNum2];
  90.         for (int j = permutationNum2; j > permutationNum1; j--) path[j] = path[j - 1];
  91.         path[permutationNum1] = temp;
  92.     }
  93.     cout << "sciezka po zmianie:   ";
  94.     for (int q = 0; q <= tasksQuantity; q++) cout << path[q] << "  ";
  95. }
  96.  
  97. int countOptimalPath()
  98. {
  99.     int tasksQuantity = 0;              //number of tasks (n)
  100.     int machinesQuantity = 0;           //number of machines (m)
  101.     int **exeTimeTable;                 //n linii zawiera m liczb, gdzie i-ta liczba w wierszu k oznacza czas wykonania zadania k na maszynie i.
  102.     int *pathActual;
  103.     int *pathBest;
  104.     int *pathStart;
  105.     int *pathPrim;
  106.  
  107.     //---------------------------DATA----------------------------------
  108.     ifstream plik;
  109.     plik.open("E:\\_STUDIA\\2018MGR_5R_9SEM\\Optymalizacja\\NEH1.dat", std::ios::in | std::ios::out);
  110.  
  111.     plik >> tasksQuantity;              //download how many tasks are specified for one machine from file
  112.     plik >> machinesQuantity;           //download how many machines are used from file
  113.  
  114.     exeTimeTable = new int*[tasksQuantity + 1];                                     //matrix with all time values
  115.     for (int i = 0; i < tasksQuantity + 1; i++) exeTimeTable[i] = new int[machinesQuantity + 1];        //memory allocation
  116.  
  117.     pathStart = new int[tasksQuantity + 1];                                             //path memory allocation
  118.     pathActual = new int[tasksQuantity + 1];
  119.     pathBest = new int[tasksQuantity + 1];
  120.     pathPrim = new int[tasksQuantity + 1];
  121.  
  122.     for (int w = 0; w < tasksQuantity + 1; w++)
  123.         for (int k = 0; k < machinesQuantity + 1; k++) exeTimeTable[w][k] = 0;      //zerowanie całej macierzy
  124.  
  125.     for (int w = 1; w < tasksQuantity + 1; w++)
  126.         for (int k = 1; k < machinesQuantity + 1; k++) plik >> exeTimeTable[w][k];  //wypełnianie macierzy danymi czasami
  127.  
  128.     for (int nr = 0; nr < tasksQuantity; nr++)
  129.         pathStart[nr] = nr;
  130.  
  131.     showData(exeTimeTable, &tasksQuantity, &machinesQuantity, pathActual);
  132.  
  133.     //--------------------VARIABLES--------------------------
  134.  
  135.     int actualPathValue = 0;                        //aktualna długość harmonogramu
  136.     int primPathValue = 0;                          //ostatnia długość harmonogramu
  137.     int bestPathValue = 100000;                     //najkrótsza wartość harmonogramu
  138.     int lastPathValue1 = 0, lastPathValue2 = 0;     //wartośći ostatnich harmonogramów
  139.     int delta = 0;                                  //różnica ostatniego i aktualnego harmonogramu
  140.     float temperatureEnd = 0.1;                     //temperatura końcowa
  141.     float temperatureActual = 1000;                 //temperatura aktualna
  142.     float lambda = 0.995;                           //współczynnik temperatury
  143.     float mutationProbability = 0;                  //prawdopodobieństwo "sublimacji"
  144.     float randProbability = 0;                      //wygenerowana wartość prawdopodobieństwa
  145.     int counter = 0;
  146.     int temp = 0;
  147.  
  148.     //--------WPŁYW KOLEJNOŚCI NA WYNIK KOŃCOWY----------
  149.     //---DOPISANIE 0 NA KOŃCU TRASY----
  150.     for (int a = 0; a < tasksQuantity + 1; a++)
  151.     {
  152.         pathStart[a] = a;
  153.     }
  154.     /*pathStart[0] = 0;
  155.     pathStart[1] = 2;
  156.     pathStart[2] = 5;
  157.     pathStart[3] = 4;
  158.     pathStart[4] = 6;
  159.     pathStart[5] = 3;
  160.     pathStart[6] = 1;
  161.     pathStart[7] = 3;
  162.     pathStart[8] = 4;
  163.     pathStart[9] = 0;
  164.     pathStart[10] = 0;*/
  165.  
  166.     //for (int yh = 0; yh < distNumber + 2; yh++) cout << pathStart[yh] << " ";
  167.     //---------------------WYŻARZANIE----------------------
  168.     for (int nr = 0; nr < tasksQuantity + 1; nr++)
  169.     {
  170.         pathActual[nr] = pathStart[nr];
  171.         pathBest[nr] = pathStart[nr];
  172.         pathPrim[nr] = pathStart[nr];
  173.     }
  174.     actualPathValue = countPathValue(&actualPathValue, pathActual, exeTimeTable, tasksQuantity, machinesQuantity);
  175.     primPathValue = countPathValue(&primPathValue, pathPrim, exeTimeTable, tasksQuantity, machinesQuantity);
  176.     bestPathValue = countPathValue(&bestPathValue, pathBest, exeTimeTable, tasksQuantity, machinesQuantity);
  177.  
  178.     do {
  179.         for (int k = 0; k < tasksQuantity + 1; k++) pathPrim[k] = pathActual[k];
  180.         primPathValue = 0;
  181.  
  182.         generateNewPath(pathPrim, tasksQuantity, machinesQuantity);
  183.  
  184.         actualPathValue = countPathValue(&actualPathValue, pathActual, exeTimeTable, tasksQuantity, machinesQuantity);
  185.         primPathValue = countPathValue(&primPathValue, pathPrim, exeTimeTable, tasksQuantity, machinesQuantity);
  186.  
  187.         comparePathsValues(primPathValue, &bestPathValue, pathBest, pathPrim, tasksQuantity);
  188.  
  189.         delta = primPathValue - actualPathValue;
  190.         if (delta <= 0)
  191.         {
  192.             for (int k = 0; k < tasksQuantity + 1; k++) pathActual[k] = pathPrim[k];
  193.             actualPathValue = countPathValue(&actualPathValue, pathActual, exeTimeTable, tasksQuantity, machinesQuantity);
  194.         }
  195.         else
  196.         {
  197.             mutationProbability = exp(-1 * (float)delta / temperatureActual);
  198.             randProbability = generateProbability();
  199.             if (randProbability < mutationProbability) //rzadki warunek mutacji
  200.             {
  201.                 for (int k = 0; k < tasksQuantity + 1; k++)
  202.                 {
  203.                     pathActual[k] = pathPrim[k];
  204.                 }
  205.             }
  206.         }
  207.         //  showData(distancesTable, &distNumber, pathActual);
  208.         temperatureActual = lambda * temperatureActual;
  209.         cout << counter << " temperaturka:" << temperatureActual << "aktualny best: " << bestPathValue << endl;
  210.         counter++;
  211.     } while (temperatureActual > temperatureEnd);
  212.  
  213.     return bestPathValue;
  214. }
  215.  
  216.  
  217. int main()
  218. {
  219.     srand(time(0));
  220.  
  221.     cout << "Najlepszy wynik to: " << endl << countOptimalPath() << endl;
  222.  
  223.     system("pause");
  224.     return 0;
  225. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top