[122] | 1 | #include "Evaluator.h" |
---|
| 2 | #include "Genetic.h" |
---|
| 3 | #include <math.h> |
---|
| 4 | #include <vector> |
---|
| 5 | #include <omp.h> |
---|
| 6 | |
---|
| 7 | #define DEBUG 0 |
---|
| 8 | |
---|
| 9 | using namespace std; |
---|
| 10 | |
---|
| 11 | /** |
---|
| 12 | * the default constructor |
---|
| 13 | */ |
---|
| 14 | TaskInfo::TaskInfo(){ |
---|
| 15 | start = 0; |
---|
| 16 | end = 0; |
---|
| 17 | proc_index = -1; |
---|
| 18 | } |
---|
| 19 | |
---|
| 20 | /** |
---|
| 21 | * the default constructor |
---|
| 22 | */ |
---|
| 23 | Evaluator::Evaluator(){} |
---|
| 24 | |
---|
| 25 | /** |
---|
| 26 | * the constructor |
---|
| 27 | * |
---|
| 28 | * @param TG the input graph of tasks |
---|
| 29 | * @param PG the input graph of processors |
---|
| 30 | */ |
---|
| 31 | Evaluator::Evaluator(TaskGraf &TG, ProcesorGraf &PG){ |
---|
| 32 | tasks = TG; |
---|
| 33 | procs = PG; |
---|
| 34 | |
---|
| 35 | proc_time = (int*)calloc(procs.nr_noduri , sizeof(int)); |
---|
| 36 | task_info = (TaskInfo*)calloc(tasks.nr_noduri , sizeof(TaskInfo));; |
---|
| 37 | |
---|
| 38 | } |
---|
| 39 | |
---|
| 40 | /** |
---|
| 41 | * Method that evaluates one chromosome, computing its makespan, fitness, etc |
---|
| 42 | * |
---|
| 43 | * @param ch the chromosome we want to evaluate |
---|
| 44 | */ |
---|
| 45 | void Evaluator::evaluateIndividual(Chromosome &ch){ |
---|
| 46 | int i,j; |
---|
| 47 | Gene g; |
---|
| 48 | int time,start,end; |
---|
| 49 | int cost_com, id_proc, id_task; |
---|
| 50 | tasks.init(); |
---|
| 51 | procs.init(); |
---|
| 52 | |
---|
| 53 | if (DEBUG == 1) |
---|
| 54 | ch.print(); |
---|
| 55 | |
---|
| 56 | |
---|
| 57 | //initializes the task information |
---|
| 58 | for (i=0;i<tasks.nr_noduri;i++){ |
---|
| 59 | task_info[i].start = 0; |
---|
| 60 | task_info[i].end = 0; |
---|
| 61 | task_info[i].proc_index = -1; |
---|
| 62 | } |
---|
| 63 | //initializes procesor times |
---|
| 64 | for (i=0;i<procs.nr_noduri;i++) |
---|
| 65 | proc_time[i]=0; |
---|
| 66 | |
---|
| 67 | |
---|
| 68 | for (i=0;i<tasks.nr_noduri;i++){ |
---|
| 69 | g = ch[i]; |
---|
| 70 | time = proc_time[g.proc_index]; |
---|
| 71 | |
---|
| 72 | if (DEBUG == 1) printf("P%d : time = %d\n",g.proc_index, time); |
---|
| 73 | |
---|
| 74 | if (DEBUG == 1) printf("Predecesori:\n"); |
---|
| 75 | |
---|
| 76 | for (j=0;j<tasks.noduri[g.task_index].nr_pred;j++){ |
---|
| 77 | cost_com = ((Muchie *)(tasks.noduri[g.task_index].predecesori[j]))->cost; |
---|
| 78 | id_task = ((Muchie *)(tasks.noduri[g.task_index].predecesori[j]))->predecesor->id; |
---|
| 79 | id_proc = task_info[id_task].proc_index; |
---|
| 80 | |
---|
| 81 | if (DEBUG == 1) printf("T%d pe P%d - cost=%d\n",id_task,id_proc,cost_com); |
---|
| 82 | |
---|
| 83 | if (id_proc == g.proc_index) |
---|
| 84 | cost_com = 0; |
---|
| 85 | else cost_com *= procs.noduri[g.proc_index].cost_comm[id_proc]; |
---|
| 86 | |
---|
| 87 | if (DEBUG == 1) printf("Cost comm : %d\n",cost_com); |
---|
| 88 | |
---|
| 89 | if (time < cost_com + task_info[id_task].end) |
---|
| 90 | time = cost_com + task_info[id_task].end; |
---|
| 91 | |
---|
| 92 | if (DEBUG == 1) printf("Time : %d\n",time); |
---|
| 93 | |
---|
| 94 | } |
---|
| 95 | start = time; |
---|
| 96 | time += tasks.noduri[g.task_index].cost * procs.noduri[g.proc_index].cost; |
---|
| 97 | end = time; |
---|
| 98 | |
---|
| 99 | //tasks.noduri[g.task_index].setProcesor(g.proc_index,start,end); |
---|
| 100 | //procs.noduri[g.proc_index].time = time; |
---|
| 101 | //procs.noduri[g.proc_index].addTask(g.task_index); |
---|
| 102 | |
---|
| 103 | task_info[g.task_index].start = start; |
---|
| 104 | task_info[g.task_index].end = end; |
---|
| 105 | task_info[g.task_index].proc_index = g.proc_index; |
---|
| 106 | proc_time[g.proc_index] = time; |
---|
| 107 | if (DEBUG == 1) printf("Time update on P%d : %d\n\n",g.proc_index,time); |
---|
| 108 | } |
---|
| 109 | |
---|
| 110 | int makespan = proc_time[0]; |
---|
| 111 | for (i=1;i<procs.nr_noduri;i++) |
---|
| 112 | if (proc_time[i] > makespan) |
---|
| 113 | makespan = proc_time[i]; |
---|
| 114 | |
---|
| 115 | if (DEBUG == 2) printf("makespan = %d\n",makespan); |
---|
| 116 | |
---|
| 117 | ch.makespan = makespan; |
---|
| 118 | |
---|
| 119 | double av = 0; |
---|
| 120 | double min = 30000; |
---|
| 121 | |
---|
| 122 | for (i=0;i<procs.nr_noduri;i++){ |
---|
| 123 | av+=proc_time[i]; |
---|
| 124 | if (proc_time[i] < min ) |
---|
| 125 | min = proc_time[i]; |
---|
| 126 | } |
---|
| 127 | |
---|
| 128 | av = av / procs.nr_noduri; |
---|
| 129 | |
---|
| 130 | ch.evalT1 = min / makespan; |
---|
| 131 | ch.evalT2 = av / makespan ; |
---|
| 132 | |
---|
| 133 | double delta = 0; |
---|
| 134 | for (i=0;i<procs.nr_noduri;i++){ |
---|
| 135 | delta+= (av - proc_time[i])*(av - proc_time[i]); |
---|
| 136 | } |
---|
| 137 | delta = delta / procs.nr_noduri; |
---|
| 138 | ch.loadBalance = 1 - 1/av * sqrt(delta); |
---|
| 139 | |
---|
| 140 | if (DEBUG == 2) printf("T1 = %f T2 = %f LB = %f\n",ch.evalT1, ch.evalT2, ch.loadBalance); |
---|
| 141 | } |
---|
| 142 | |
---|
| 143 | /** |
---|
| 144 | * Method that evaluates one population's performance |
---|
| 145 | * |
---|
| 146 | * @param ch the list of chromosomes |
---|
| 147 | */ |
---|
| 148 | void Evaluator::evaluatePopulation(vector<Chromosome> &chs){ |
---|
| 149 | int i; |
---|
| 150 | for (i=0;i<(int)chs.size();i++){ |
---|
| 151 | if (chs[i].fitness == 0) |
---|
| 152 | evaluateIndividual(chs[i]); |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | double best = chs[0].makespan; |
---|
| 156 | |
---|
| 157 | for (i=0;i<(int)chs.size();i++){ |
---|
| 158 | if (chs[i].makespan < best) |
---|
| 159 | best = chs[i].makespan; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | for (i=0;i<(int)chs.size();i++){ |
---|
| 163 | chs[i].evalT3 = best / chs[i].makespan; |
---|
| 164 | chs[i].fitness = chs[i].evalT1 * chs[i].evalT2 * chs[i].evalT3 * chs[i].evalT3 * chs[i].evalT3 ; |
---|
| 165 | if (DEBUG == 1) printf("Fit = %f\n",chs[i].fitness); |
---|
| 166 | } |
---|
| 167 | |
---|
| 168 | |
---|
| 169 | } |
---|