Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

main.cpp @ 122

Last change on this file since 122 was 122, checked in by (none), 14 years ago

File size: 27.2 KB

Line
1	#include <time.h>
2	#include <unistd.h>
3	#include <stdlib.h>
4	#include <stdio.h>
5	#include <omp.h>
6	#include "main.h"
7	#include "mpi.h"
8
9	/** the number of chromosomes contained into a population */
10	#define POP_SIZE 128
11
12	/** the number of generation after which the populations exchange their bests chromosomes */
13	#define EXCHANGE 10
14
15	/** the number of generation all populations evolve - in the genetic algorithm */
16	#define NR_GEN 50
17
18	/** the number of generation all populations evolve - in the immune algorithm */
19	#define IMMUNE_GEN 10
20
21	/** the maximum number of clones for each chromosome - for the immune algorithm */
22	#define MAX_CLONES 3
23
24	/** the maximum number of mutations a chromosome can suffer - for the immune algorithm */
25	#define MAX_MUTATIONS 7
26
27	/** the simple mutation probability */
28	#define SIMPLE_MUT_PROB 50
29
30	/** the swap gene mutation probability */
31	#define SWAP_MUT_PROB 25
32
33	/** the hyper-mutation probability */
34	#define HYPER_MUT_PROB 25
35
36	/** the tour's size - in the tournament selection */
37	#define TOUR_SIZE 4
38
39	#define debug 0
40
41	using namespace std;
42
43	/**
44	* structure used in the MPI communication to send the configuration of the best individual
45	*/
46	struct chromompi
47	{
48	double dbs[6];
49	int ints[2500];
50	};
51
52	/**
53	* function that executes the serial quicksort
54	*
55	* @param chs the list of chromosomes
56	* @param index the list containing the chromosomes' id - the list specifies the order according to the fitness
57	* @param left the left limit of the interval
58	* @param right the right limit of the interval
59	*/
60	void quickSort(Chromosome chs[], int index[], int left, int right) {
61
62	int i = left, j = right;
63	int tmp;
64	double pivot = chs[index[(left + right) / 2]].fitness;
65
66	/**
67	* partition
68	*/
69
70	while (i <= j) {
71
72	while (chs[index[i]].fitness > pivot)
73	i++;
74
75	while (chs[index[j]].fitness < pivot)
76	j--;
77	// printf("i=%d j=%d ::\n",i,j);
78
79	if (i <= j) {
80	tmp = index[i];
81	index[i] = index[j];
82	index[j] = tmp;
83	i++;
84	j--;
85	}
86	};
87
88	/**
89	* recursion
90	*/
91
92	if (left < j)
93	quickSort(chs,index, left, j);
94
95	if (i < right)
96	quickSort(chs,index , i, right);
97
98	}
99
100	/**
101	* function that merges the results
102	*
103	* @param chs the list of chromosomes
104	* @param index the index list - specifies the order according to the fitness
105	* @param start the start index
106	* @param middle - the first range=from "start" to "middle"
107	* @param end the end start - the second range=from "middle+1" to "end"
108	*/
109	void merge(Chromosome chs[], int index[], int start, int middle, int end, int *aux_index, int aux_start){
110	int p = start;
111	int q = middle + 1;
112	int r = aux_start;
113
114	//printf(" interclass (%d %d)-(%d %d) \n",start,middle,middle+1,end);
115	int total = end - start + 1;
116	while(r <= aux_start + total){
117	//printf("R=%d\n P(%d)= %lf Q(%d)=%lf\n",r, p, chs[index[p]].fitness , q, chs[index[q]].fitness);
118	if (chs[index[p]].fitness >= chs[index[q]].fitness ){
119	aux_index[r] = index[p];
120	p++;
121	r++;
122	// printf(" P++ => p=%d q=%d r=%d aux = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness );
123	}else if (q <= end ){
124	aux_index[r] = index[q];
125	q++;
126	r++;
127	// printf(" Q++ => p=%d q=%d r=%d aux = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness);
128	}
129
130	if (q > end){
131	while ( p <= middle ) {
132	aux_index[r] = index[p];
133	p++;
134	r++;
135	// printf(" P++ NO Q => p=%d q=%d r=%d aux = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness);
136	}
137	break;
138	}else if (p > middle){
139	while ( q <= end ) {
140	aux_index[r] = index[q];
141	q++;
142	r++;
143	// printf(" Q++ NO P => p=%d q=%d r=%d aux = %d val=%lf\n", p,q,r,aux_index[r-1],chs[aux_index[r-1]].fitness);
144	}
145	break;
146	}
147	}
148	}
149
150	/**
151	* function that realizes the parallel sort
152	*
153	* @param chs the list of chromosomes
154	* @param num_chs the number of chromosomes
155	* @param index simulates a shared memory
156	* @param aux_index simulates a shared memory
157	*/
158	void inline parallel_sort(Chromosome chs[], int num_chs , int index[], int *aux_index){
159	int j,k;
160	int num_th = omp_get_num_threads();
161	int th_id = omp_get_thread_num();
162	int chunk_size = num_chs / num_th ;
163	int start = th_id * chunk_size;
164
165	int chunk;
166
167	//int *res = index ;
168	//int *aux_ptr;
169	int end;
170
171	chunk = chunk_size;
172
173	if (num_chs % num_th > 0){
174	if (th_id < (num_chs % num_th)){
175	start+=th_id;
176	end = start + chunk;
177	}else{
178	start += (num_chs % num_th);
179	end = start + chunk - 1;
180	}
181
182	}else{
183	end = start + chunk -1 ;
184
185	}
186
187	//printf("Th[%d] (%d->%d)\n",th_id,start,end);
188
189	#pragma omp barrier
190
191	#pragma omp for private(j) nowait
192	for (j = 0 ; j < num_chs ; j++){
193	index[j]=j;
194	}
195
196	#pragma omp barrier
197
198	//printf("Th[%d] QSort %d %d \n",th_id,start , end);
199
200	quickSort(chs,index, start, end) ;
201
202	//printf("Th[%d] QSort Done!!!\n",th_id);
203	#pragma omp barrier
204
205
206
207	int n = num_th ;
208	int merge_st, merge_mid, merge_end;
209	int extra_chunks = num_chs % num_th;
210	for (j = 2 ; j <= n ; j = j * 2 ){
211	//printf("Active th %d [%d] j= %d chunk = %d\n",n,th_id, j, chunk);
212	if (th_id % j == 0) {
213	merge_st = start;
214
215	merge_mid = start + j/2 * chunk - 1 ;
216
217	merge_end = end + (j-1) * chunk;
218	if (th_id < extra_chunks && th_id + j - 1 <= extra_chunks){
219	merge_end += j - 1;
220	} else if (th_id < extra_chunks && th_id + j - 1 > extra_chunks){
221	merge_end += extra_chunks - th_id - 1;
222	}
223
224	if (th_id < extra_chunks && th_id + j/2 <= extra_chunks){
225	merge_mid += j/2;
226	} else if (th_id < extra_chunks && th_id + j/2 > extra_chunks){
227	merge_mid += extra_chunks - th_id ;
228	}
229
230
231	// printf("Th[%id] :: Merge (%d,%d)->(%d,%d)\n", th_id, merge_st, merge_mid,merge_mid+1,merge_end);
232	merge(chs, index , merge_st, merge_mid, merge_end, aux_index, merge_st);
233	}
234
235	#pragma omp barrier
236
237	#pragma omp for private(k) schedule(static)
238	for (k=0;k<num_chs;k++){
239	// printf("Th[%d] copying %d => %d -- val=%lf\n",th_id,k, aux_index[k] , chs[aux_index[k]].fitness);
240	index[k] = aux_index[k];
241
242	}
243	#pragma omp barrier
244	//printf("COPY DONE\n");
245	}
246	}
247
248	/**
249	* function that performes the evaluation of one population
250	*
251	* @param chs the list of chromosomes
252	* @param num_chs the number of chromosomes
253	* @param ev the chromosomes evaluator
254	* @param best simulates a shared memory
255	*/
256	void inline evaluatePopulation(Chromosome *chs, int num_chs , Evaluator &ev, double best[]){
257	int th_id = omp_get_thread_num();
258	int j;
259	int num_th = omp_get_num_threads();
260
261	#pragma omp for schedule(static) nowait
262	for (j=0; j < num_chs ; j++){
263	ev.evaluateIndividual(chs[j]);
264	}
265
266	#pragma omp barrier
267
268	best[th_id] = 30000;
269
270
271
272	#pragma omp for schedule(static) nowait
273	for (j=0; j < num_chs ; j++){
274	if (best[th_id] > chs[j].makespan){
275	best[th_id] = chs[j].makespan;
276	}
277	}
278	#pragma omp barrier
279
280	#pragma omp master
281	{
282
283	for (j=0;j<num_th;j++)
284	if (best[0] > best[j])
285	best[0] = best[j];
286	for (j=1;j<num_th;j++)
287	best[j] = best[0];
288
289	}
290
291	#pragma omp barrier
292
293
294	#pragma omp for schedule(static) nowait
295	for (j = 0 ; j < num_chs ; j++){
296	chs[j].evalT3 = best[th_id]/chs[j].makespan;
297	chs[j].fitness = chs[j].evalT1 * chs[j].evalT2 * chs[j].evalT3 * chs[j].evalT3 * chs[j].evalT3 ;
298	}
299
300
301	}
302
303	/**
304	* function that computes the prefix sums
305	*
306	* @param input the input series
307	* @param n the number of input elements
308	* @param sum the prefix sums
309	*/
310	void inline computePrefixSum(int input[], int n, int sum[]){
311	int *aux_sum;
312	//int *aux_ptr;
313	int k,j;
314	int num_th = omp_get_num_threads();
315	int th_id = omp_get_thread_num();
316
317	aux_sum = (int *)calloc(n,sizeof(int));
318
319	#pragma omp for private(j)
320	for (j = 0 ; j < n ; j++){
321	aux_sum[j] = sum[j] = input [j];
322	}
323
324	#pragma omp barrier
325
326	int start,end;
327	int step, num_tasks;
328
329
330	for (step = 1 ; step < n ; step*=2) {
331
332	num_tasks = (n - step) / num_th ;
333	if (th_id < ((n - step) % num_th)){
334	num_tasks ++;
335	start = step + num_tasks * th_id ;
336	end = start + num_tasks;
337	}else{
338	start = step + num_tasks * th_id + ((POP_SIZE - step) % num_th) ;
339	end = start + num_tasks;
340	}
341	for (k = start ; k < end ; k++){
342	aux_sum[k] = sum[k] + sum[k - step];
343	}
344
345	#pragma omp barrier
346
347	for (k = start ; k < end ; k++){
348	sum[k] = aux_sum[k];
349	}
350
351	#pragma omp barrier
352	//printf("Th[%d] #tasks = %d st = %d stop = %d \n",th_id, num_tasks, start, end);
353
354
355	}
356	free(aux_sum);
357	}
358
359	/**
360	* function that converts a chromompi structure to a Chromosome
361	*
362	* @param c the chromompi structure
363	* @return the Chromosome
364	*/
365	Chromosome to_chromosome(chromompi c)
366	{
367	Chromosome chr = Chromosome();
368	chr.makespan = c.dbs[0];
369	chr.fitness = c.dbs[1];
370	chr.evalT1 = c.dbs[2];
371	chr.evalT2 = c.dbs[3];
372	chr.evalT3 = c.dbs[4];
373	chr.loadBalance = c.dbs[5];
374
375	for(int i = 0 ; i < c.ints[0]*3 ; i += 3)
376	{
377	Gene g = Gene(c.ints[i+1], c.ints[i+2], c.ints[i+3]);
378	chr.genes.push_back(g);
379	}
380	int start = c.ints[0]*3+1;
381	for(int i = 0 ; i < c.ints[start] ; i ++)
382	chr.f_nodes.push_back(c.ints[start+i+1]);
383	return chr;
384	}
385
386	/**
387	* function that converts a Chromosome structure to a chromompi
388	*
389	* @param chrom the Chromosome
390	* @return the chromompi
391	*/
392	chromompi to_chromompi(Chromosome chrom)
393	{
394	chromompi c;
395	c.dbs[0] = chrom.makespan;
396	c.dbs[1] = chrom.fitness;
397	c.dbs[2] = chrom.evalT1;
398	c.dbs[3] = chrom.evalT2;
399	c.dbs[4] = chrom.evalT3;
400	c.dbs[5] = chrom.loadBalance;
401
402	c.ints[0] = chrom.genes.size();
403	int i;
404	for(i = 1 ; i < c.ints[0]*3 ; i += 3)
405	{
406	c.ints[i] = chrom.genes[(i-1)/3].task_index;
407	c.ints[i+1] = chrom.genes[(i-1)/3].proc_index;
408	c.ints[i+2] = chrom.genes[(i-1)/3].level;
409	}
410	c.ints[i++] = chrom.f_nodes.size();
411	for(int k = 0 ; k < (int)chrom.f_nodes.size(); k++)
412	c.ints[i++] = chrom.f_nodes[k];
413	//for(int i = 0 ; i < chrom.genes.size()*3 + chrom.f_nodes.size() +2 ; i ++)
414	// printf("%i ", c.ints[i]);
415	//printf("\n");
416	return c;
417	}
418
419	/**
420	* function that prints the chromosome's information
421	*
422	* @param chrom the chromosome
423	*/
424	void print(chromompi chrom)
425	{
426	printf("%lf %lf %lf %lf %lf %lf\n", chrom.dbs[0], chrom.dbs[1], chrom.dbs[2], chrom.dbs[3],chrom.dbs[4], chrom.dbs[5]);
427	printf("[%i]:", chrom.ints[0]);
428	for(int i = 0 ; i < chrom.ints[0]*3 ; i+=3)
429	printf("(%i %i %i) ", chrom.ints[1 + i], chrom.ints[1 + i+ 1], chrom.ints[1 + i+ 2]);
430	int count = chrom.ints[0]*3+1;
431	printf("\n[%i]:", chrom.ints[count]);
432	for(int i = 0 ; i < chrom.ints[count] ; i ++)
433	printf("%i ", chrom.ints[count+1+i]);
434	printf("\n");
435	}
436
437	/**
438	* entry point for the GAIIA project
439	*
440	* @param argc ignored
441	* @param args ignored
442	*/
443	int main(int argc, char ** args)
444	{
445	int numprocs, rank;//number of populations
446	srand(time(NULL) + getpid());
447
448	/**
449	* MPI initialization
450	*/
451
452	MPI_Init(&argc, &args);
453	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
454	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
455
456	int i, master=rank;
457	MPI_Request request;
458	MPI_Status status;
459
460	/**
461	* MPI datatype construction
462	*/
463
464	chromompi sent;
465	MPI_Datatype Chromotype;
466	MPI_Datatype type[2] = {MPI_DOUBLE, MPI_INT};
467	int blocklen[2] = {6, 2500};
468	MPI_Aint disp[2];
469	int base;
470	MPI_Address( &sent, disp);
471	MPI_Address( &sent.ints, disp+1);
472	base = disp[0];
473	for (i=0; i <2; i++) disp[i] -= base;
474	MPI_Type_struct( 2, blocklen, disp, type, &Chromotype);
475	MPI_Type_commit( &Chromotype);
476
477	printf("hello mpi from %i\n", rank);
478	master =0;
479
480	/**
481	* the tasks graph we want to schedule
482	*/
483
484	TaskGraf tasks = TaskGraf();
485	tasks.init((char*)"test500.in");//in.txt
486
487	/**
488	* the processors graph we can se
489	*/
490
491	ProcesorGraf procs = ProcesorGraf();
492	procs.init((char *)"proc.txt");
493
494	/**
495	* the random population generator
496	*/
497
498	Generator gen = Generator(POP_SIZE, tasks, procs.nr_noduri);
499	gen.setFloatingNodes(tasks.f_nodes);
500	gen.generate();
501
502
503	/**
504	* we need two populations and three pointers in order to use double buffering
505	*/
506
507	Chromosome *chs;
508	Chromosome *new_pop;
509	Chromosome *aux;
510
511	chs = (Chromosome *)calloc(POP_SIZE,sizeof(Chromosome));
512	new_pop = (Chromosome *)calloc(POP_SIZE,sizeof(Chromosome));
513
514
515
516
517	for(i = 0 ; i < POP_SIZE ; i ++)
518	{
519	chs[i] = gen.getNext();
520	new_pop[i] = Chromosome();
521	}
522
523
524	int j,k,th_id;
525	int num_th;
526
527	#pragma omp parallel shared(num_th)
528	{
529	num_th = omp_get_num_threads();
530
531	}
532
533	int selected[128];//[POP_SIZE];
534	int used[128];//[POP_SIZE];
535
536	int free_ch[128];//[num_th];
537
538	Evaluator ev[128];//[num_th];
539	Crossover cross[128];//[num_th];
540
541	SimpleMutation simple_mut[128];//[num_th];
542	SwapMutation swap_mut[128];//[num_th];
543	HyperMutation hyper_mut[128];//[num_th];
544	double best[128];//[num_th];
545
546	time_t ltime;
547	time(&ltime);
548	printf("The start time is %s\n", ctime(&ltime));
549
550
551
552	#pragma omp parallel private(j,k,th_id) shared(i,num_th,chs,ev,new_pop, aux, used, selected)
553	{
554
555	th_id = omp_get_thread_num();
556	cross[th_id] = Crossover();
557	ev[th_id] = Evaluator(tasks, procs);
558	simple_mut[th_id] = SimpleMutation(procs.nr_noduri, tasks.max_level, 0.4);
559	swap_mut[th_id] = SwapMutation(procs.nr_noduri, tasks.max_level, 0.4);
560	hyper_mut[th_id] = HyperMutation(tasks, 0.3);
561	printf("Th[%d/%d]: Init\n",th_id,num_th);
562
563	#pragma omp for private(i) schedule(static)
564	for (i = 0; i < POP_SIZE ; i++){
565	selected[i] = 0;
566	used [i] = 0 ;
567	}
568
569	evaluatePopulation(chs, POP_SIZE ,ev[th_id], best);
570	#pragma omp barrier
571	}
572
573
574
575
576	/**
577	* prefix sums computation
578	*/
579
580	int *clones;
581	int *sum ;
582	sum = (int *)calloc(POP_SIZE,sizeof(int));
583	clones = (int )calloc(MAX_CLONES POP_SIZE,sizeof(int));
584
585	Chromosome clone_pop[POP_SIZE * MAX_CLONES];
586
587	double fit_med[num_th];
588
589	int num_clones;
590
591	int *index;
592	int *aux_index;
593	int *clones_index;
594	int * clones_aux;
595
596	index = (int *)calloc(POP_SIZE,sizeof(int));
597	aux_index = (int *)calloc(POP_SIZE,sizeof(int));
598	clones_index = (int )calloc(MAX_CLONES POP_SIZE,sizeof(int));
599	clones_aux = (int )calloc(MAX_CLONES POP_SIZE,sizeof(int));
600
601	/**
602	* start of the immune algorithm
603	*/
604
605	for(i=0;i<IMMUNE_GEN;i++){
606
607
608	#pragma omp parallel private(j,k,th_id) shared(num_clones, clone_pop,i,num_th,chs,ev,new_pop, aux, used, selected, sum,clones)
609	{
610	th_id = omp_get_thread_num();
611	fit_med[th_id] = 0 ;
612	best[th_id] = 0 ;
613	#pragma omp for private(j) nowait
614	for (j = 0 ; j < POP_SIZE ; j++){
615	fit_med[th_id]+= chs[j].fitness;
616	if (chs[j].fitness > best[th_id] )
617	best[th_id] = chs[j].fitness;
618	}
619	#pragma omp barrier
620
621	#pragma omp master
622	{
623	double mean = 0;
624	for (j = 0 ; j < num_th ; j++ ){
625	mean += fit_med[j];
626	}
627	mean = mean / POP_SIZE ;
628	for (j = 0 ; j < num_th ; j++ ){
629	fit_med[j] = mean;
630	}
631	for (j=0 ; j < num_th ; j++){
632	if (best[j] > best[th_id])
633	best[th_id] = best[j];
634	}
635	for (j=0 ; j < num_th ; j++){
636	best[j] = best[th_id];
637	}
638
639	}
640	#pragma omp barrier
641
642	#pragma omp for private(j)
643	for (j=0 ; j < POP_SIZE ; j++) { //TODO not all - first selection
644	clones[j] = 1 + (MAX_CLONES - 1) * (chs[j].fitness - fit_med[th_id]) / (best[th_id] - fit_med[th_id]);
645	if ( clones[j] < 0)
646	clones[j] = 0 ;
647	//printf("Th[%d] For Ch[%d] -- %d clones\n",th_id, j, clones[j]);
648	}
649
650	#pragma omp barrier
651
652	computePrefixSum(clones,POP_SIZE,sum);
653
654	#pragma omp barrier
655
656	#pragma omp master
657	{
658	num_clones = sum[POP_SIZE - 1];
659
660	//printf("Th[%d] :: Nr clone = %d\n",th_id, sum[POP_SIZE-1]);
661
662	}
663
664	#pragma omp barrier
665
666	int base;
667	#pragma omp for private(j,k) schedule(static) nowait
668	for (j = 0 ; j < POP_SIZE; j ++){
669	if (clones[j] > 0) {
670	base = 0;
671	if (j > 0)
672	base = sum[j-1];
673	for (k = 0 ; k < clones[j] ; k++) {
674	clone_pop[base + k] = chs[j];
675	}
676
677	}
678
679	}
680
681	#pragma omp barrier
682
683	#pragma omp barrier
684
685	int num_mut ;
686	double rnd ;
687	//aplicarea operatorilor de mutatie asupra clonelor
688
689	simple_mut[th_id].mutation_pb = 1;
690	swap_mut[th_id].mutation_pb = 1;
691	hyper_mut[th_id].mutation_pb = 1;
692
693	#pragma omp for private(j,k) schedule(static) nowait
694	for (j = 0 ; j < num_clones; j ++){
695
696	//printf("b=%lf f=%lf mk=%lf fmed=%lf\n",best[th_id], clone_pop[j].fitness, clone_pop[j].makespan, fit_med[th_id]);
697	num_mut = 3 + (MAX_MUTATIONS - 1) * (best[th_id] - clone_pop[j].fitness) / (best[th_id] - fit_med[th_id]);
698
699	//printf("Th[%d] Clone = %d Mut# = %d\n",th_id, j , num_mut);
700	for (k = 0 ; k < num_mut ; k++) {
701	rnd = (double)(rand() % 10000) / 100;
702	if (rnd < SIMPLE_MUT_PROB){
703	simple_mut[th_id].mutateIndividual(clone_pop[j]);
704	// printf("Simple\n");
705	}else if (rnd < SIMPLE_MUT_PROB + SWAP_MUT_PROB){
706	// printf("Swap\n");
707	swap_mut[th_id].mutateIndividual(clone_pop[j]);
708	}else {
709	// printf("Hyper\n");
710	hyper_mut[th_id].mutateIndividual(clone_pop[j]);
711	}
712
713	}
714	}
715
716	/**
717	* clone population evaluation
718	*/
719
720	#pragma omp barrier
721
722	evaluatePopulation(clone_pop, num_clones ,ev[th_id], best);
723
724	#pragma omp barrier
725
726
727	#pragma omp for private(j) nowait
728	for (j=0; j < POP_SIZE; j++)
729	index[j]=j;
730
731	#pragma omp barrier
732	parallel_sort(chs, POP_SIZE, index,aux_index);
733
734	#pragma omp barrier
735
736	#pragma omp for private(j) nowait
737	for (j=0; j < num_clones; j++)
738	clones_index[j]=j;
739
740	#pragma omp barrier
741	parallel_sort(clone_pop, num_clones, clones_index, clones_aux);
742
743	#pragma omp barrier
744
745	int clone_base = 2* POP_SIZE / 3 + 1;
746
747	#pragma omp for private(j)
748	for (j=0 ; j < clone_base ; j++){
749	new_pop[j] = chs[index[j]];
750	}
751
752	#pragma omp barrier
753
754	#pragma omp for private(j)
755	for (j=0 ; j < POP_SIZE - clone_base ; j++){
756	new_pop[clone_base + j] = clone_pop[clones_index[j]];
757	}
758
759	#pragma omp barrier
760
761	#pragma omp master
762	{
763
764	aux = new_pop;
765	new_pop = chs;
766	chs = aux;
767
768
769	}
770	}
771	}
772
773	/**
774	* end of the immune algorithm
775	*/
776
777	time(&ltime);
778	printf("IA The end time is %s\n", ctime(&ltime));
779
780	/**
781	* start of the genetic algorithm
782	*/
783
784	printf("GA\n");
785
786	for (i = 0 ; i < NR_GEN ; i++) {
787
788	#pragma omp parallel private(j,k,th_id) shared(i,num_th,chs,ev,new_pop, aux, used, selected)
789	{
790
791	th_id = omp_get_thread_num();
792
793	/**
794	* choosing of the mutations' probabilities
795	*/
796
797	simple_mut[th_id].mutation_pb = 0.4;
798	swap_mut[th_id].mutation_pb = 0.3;
799	hyper_mut[th_id].mutation_pb = 0.3;
800
801
802	/**
803	* selection
804	*/
805
806	/**
807	* first step -> reset used vector
808	*/
809
810	#pragma omp for schedule(static)
811	for (j = 0 ; j < POP_SIZE ; j++){
812	used[j] = 0;
813	selected[j] = 0;
814	}
815
816	#pragma omp barrier
817	double best_makespan;
818	int best_poz ;
819	int base;
820	int offset;
821	int chunk_size = POP_SIZE / num_th ;
822	int crt_chunk;
823	int new_poz;
824
825	/**
826	* compute the number of unselected nodes for each chunck
827	*/
828
829	int tours = POP_SIZE / ( 2 * num_th ) ;
830	int l ;
831	for (l = 0 ; l < tours ; l++){
832
833	best_makespan = 30000;
834	best_poz = -1;
835	free_ch[th_id] = chunk_size;
836
837	/**
838	* update unselected chromosomes
839	*/
840
841	for (j=0; j < chunk_size ; j++){
842	if (selected[th_id * chunk_size + j] == 1)
843	free_ch[th_id]--;
844	used[th_id * chunk_size + j] = 0;
845	}
846
847	#pragma omp barrier
848
849	/**
850	* start new tour
851	*/
852
853	for (j=0; j < TOUR_SIZE ; j++){
854	crt_chunk = (th_id + j) % num_th;
855	base = crt_chunk * chunk_size;
856	if (free_ch[crt_chunk] - j > 0 )
857	offset = rand() % (free_ch[crt_chunk] - j);
858	else {
859	//printf("Th[%d] :: No selection possible\n",th_id);
860	}
861	//printf("Th[%d] - step=%d base=%d offset=%d\n",th_id, j, base, offset);
862
863	for (k = 0 ; k < chunk_size ; k++){
864	if (used[base + k] == 0 && selected[base + k] == 0){
865	if (offset == 0){ //this one is selected in this step
866	//printf("Th[%d] - selected in tour -> %d\n", th_id , (base+k));
867	used[base + k] = 1;
868	if (best_makespan > chs[base + k].makespan){
869	best_makespan = chs[base + k].makespan;
870	best_poz = base + k ;
871	}
872	break;
873	}else
874	offset--;
875	}else {
876	//printf("Th[%d] - %d DROP uz:%d sel:%d\n", th_id , (base+k), used[base+k], selected[base + k]);
877	}
878	}
879	#pragma omp barrier
880	}
881	//printf("Th[%d] - Winner = %d Makespan = %lf \n",th_id, best_poz, best_makespan);
882
883
884	selected[best_poz] = 1;
885	new_poz = l * num_th + th_id;
886	new_pop[new_poz] = chs[best_poz];
887
888	#pragma omp barrier
889
890	}
891
892
893	/**
894	* crossover phase
895	*/
896
897	offset = POP_SIZE / 2;
898
899	#pragma omp for private(j) schedule(static) nowait
900	for(j = 0 ; j < POP_SIZE / 2 ; j+=2 ){
901	//printf("T[%d] :: Cross (%d %d) -> (%d %d)\n" , th_id , j, j+1 , offset + j , offset+j+1);
902	cross[th_id].crossover(new_pop[j], new_pop[j+1], new_pop[offset + j], new_pop[offset + j + 1]);
903	}
904
905	#pragma omp barrier
906
907
908	/**
909	* simple mutation phase
910	*/
911
912	#pragma omp for private(j) schedule(static) nowait
913	for(j = 0 ; j < POP_SIZE ; j++ ){
914	simple_mut[th_id].mutateIndividual(new_pop[j]);
915	}
916	#pragma omp barrier
917
918	/**
919	* swap gene mutation phase
920	*/
921
922	#pragma omp for private(j) schedule(static) nowait
923	for(j = 0 ; j < POP_SIZE ; j++ ){
924	swap_mut[th_id].mutateIndividual(new_pop[j]);
925	}
926	#pragma omp barrier
927
928
929	/**
930	* topo hyper-mutation phase
931	*/
932
933	#pragma omp for private(j) schedule(static) nowait
934	for(j = 0 ; j < POP_SIZE ; j++ ){
935	hyper_mut[th_id].mutateIndividual(new_pop[j]);
936	}
937	#pragma omp barrier
938
939
940
941	/**
942	* evaluation
943	*/
944
945	#pragma omp for schedule(static) nowait
946	for (j=0; j < POP_SIZE ; j++){
947	ev[th_id].evaluateIndividual(new_pop[j]);
948	}
949
950	#pragma omp barrier
951
952	best[th_id] = 30000;
953
954
955
956	#pragma omp for schedule(static) nowait
957	for (j=0; j < POP_SIZE ; j++){
958	if (best[th_id] > new_pop[j].makespan){
959	best[th_id] = new_pop[j].makespan;
960	}
961	}
962
963	#pragma omp barrier
964
965	#pragma omp master
966	{
967
968	for (j=0;j<num_th;j++)
969	if (best[0] > best[j])
970	best[0] = best[j];
971	for (j=1;j<num_th;j++)
972	best[j] = best[0];
973
974	//printf("Th[%d] - Best = %lf\n",th_id, best[0]);
975	}
976
977	#pragma omp for schedule(static) nowait
978	for (j = 0 ; j < POP_SIZE ; j++){
979	new_pop[j].evalT3 = best[th_id]/new_pop[j].makespan;
980	new_pop[j].fitness = new_pop[j].evalT1 * new_pop[j].evalT2 * new_pop[j].evalT3 * new_pop[j].evalT3 * new_pop[j].evalT3 ;
981
982	}
983
984
985	}
986	aux = chs ;
987	chs = new_pop;
988	new_pop = aux;
989
990	//for(j = 0 ; j < POP_SIZE ; j++ ){
991	// chs[j].print();
992	//}
993
994
995	/**
996	* each population will exchange its worsts individuals with the others bests
997	*/
998
999	if(i % EXCHANGE == 0 && i != NR_GEN - 1)
1000	{
1001	int best = 0;
1002	for(j = 1 ; j < POP_SIZE ; j++ )
1003	if (chs[best].makespan > chs[j].makespan)
1004	best = j;
1005
1006	int worst[numprocs];
1007	int used[128];//[POP_SIZE];
1008
1009	for(j = 0 ; j < POP_SIZE ; j++)
1010	used[j] = 1;
1011
1012	for(j = 0; j < numprocs - 1; j ++)
1013	worst[j] = -1;
1014
1015	for(int k = 0 ; k < numprocs - 1; k ++)
1016	{
1017
1018	for(j = 1 ; j < POP_SIZE ; j++ )
1019	if ((worst[k] == -1 \|\| chs[worst[k]].makespan < chs[j].makespan) && used[j] != 2)
1020	worst[k] = j;
1021
1022	used[worst[k]] = 2;
1023	}
1024	/* printf("[%i] best %i, worst ",rank, best);
1025	for(int k = 0 ; k < numprocs - 1; k ++)
1026	printf("%i ", worst[k]);
1027	printf("\n");
1028	*/
1029
1030	int ready = 1;
1031
1032
1033	printf("[%i] exchange \n", rank);
1034	chromompi b = to_chromompi(chs[best]);
1035
1036	/**
1037	* each population broadcasts its best chromosome
1038	*/
1039
1040	for(int jj = 0 ; jj < numprocs ; jj ++)
1041	{
1042	if(jj != rank)
1043	{
1044	MPI_Isend(&b, 1, Chromotype, jj, i, MPI_COMM_WORLD, &request);
1045	//if (debug) printf("[%i] j(%i)->k(%i) %lf\n", rank, sursa, jj, to_chromosome(b).makespan);
1046
1047	}
1048	}
1049
1050	int recv = 0;
1051
1052	/**
1053	* each population receives other bests
1054	*/
1055
1056	for(int i = 0 ; i < numprocs - 1 ; i ++)
1057	{
1058	MPI_Irecv(&b, 1, Chromotype, MPI_ANY_SOURCE, i, MPI_COMM_WORLD, &request);
1059	int flag = 0, step = 100000;
1060	MPI_Test(&request, &flag, &status);
1061
1062	while (!flag && step > 0)
1063	{
1064	MPI_Test(&request, &flag, &status);
1065	step --;
1066	}
1067
1068	if(step > 0)
1069	{
1070	/**
1071	* exchange the worst with the best
1072	*/
1073
1074	chs[worst[recv++]] = to_chromosome(b);
1075	//if (debug) printf("[%i] received best %lf %lf\n", rank, to_chromosome(b).makespan, to_chromosome(b).fitness);
1076	}
1077
1078	}
1079
1080	printf("[%i] exchange done\n", rank);
1081
1082	}
1083
1084	/**
1085	* the end of the algorithm -> we have to compute the general best
1086	*/
1087
1088	if(i == NR_GEN - 1)
1089	{
1090
1091	/**
1092	* leader selection
1093	*/
1094
1095	/**
1096	* broadcast of the rank
1097	*/
1098
1099	for(int j = 0 ; j < numprocs ; j ++)
1100	if(j != rank)
1101	MPI_Isend(&rank, 1, MPI_INT, j, 0, MPI_COMM_WORLD, &request);
1102
1103	/**
1104	* wait for other ranks
1105	*/
1106
1107	int candidat = -1, max = rank;
1108	for(int j = 0 ; j < numprocs - 1 ; j ++)
1109	{
1110
1111	MPI_Irecv(&candidat, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &request);
1112	int flag = 0, step = 500000;
1113	MPI_Test(&request, &flag, &status);
1114
1115	while (!flag && step > 0)
1116	{
1117	MPI_Test(&request, &flag, &status);
1118	step --;
1119	}
1120
1121	/**
1122	* new message received
1123	*/
1124	if(step > 0)
1125	{
1126	//printf("IRECV[%i]: sursa = %i, candidat = %i\n", rank, sursa, candidat);
1127	if(max < candidat)
1128	max = candidat;
1129
1130	}
1131	}
1132
1133
1134	/**
1135	* broadcast of the candidate master
1136	*/
1137
1138	for(int j = 0 ; j < numprocs ; j ++)
1139	if(j != rank)
1140	MPI_Isend(&master, 1, MPI_INT, j, 0, MPI_COMM_WORLD, &request);
1141
1142	for(int ii = 0 ; ii < numprocs - 1 ; ii ++)
1143	{
1144	MPI_Irecv(&candidat, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &request);
1145	int flag = 0, step = 500000;
1146	MPI_Test(&request, &flag, &status);
1147
1148	while (!flag && step > 0)
1149	{
1150	MPI_Test(&request, &flag, &status);
1151	step --;
1152	}
1153
1154	if(step > 0)
1155	{
1156	// int sursa = status.MPI_SOURCE;
1157	//printf("IRECV[%i]: sursa = %i, candidat = %i\n", rank, sursa, candidat);
1158	if(master > candidat)
1159	master = candidat;
1160	}
1161
1162	}
1163
1164	printf("END\n");
1165	int best = 0;
1166	chromompi b;
1167	for(int j = 1 ; j < POP_SIZE ; j++ )
1168	if (chs[best].makespan > chs[j].makespan)
1169	best = j;
1170
1171	if(rank != master)
1172	{
1173	/**
1174	* sends the best chromosome to the master
1175	*/
1176
1177	b = to_chromompi(chs[best]);
1178	MPI_Isend(&b, 1, Chromotype, master, 1, MPI_COMM_WORLD, &request);
1179	//printf("[%i] => trimit best %lf -> master\n", rank, chs[best].makespan);
1180	}
1181	else if(rank == master)
1182	{
1183	/**
1184	* receives the others' bests
1185	*/
1186	printf("[%i] leader\n", rank);
1187
1188	Chromosome crtbest = chs[best];//the best is the master's best
1189
1190	for(int ii = 0 ; ii < numprocs - 1 ; ii ++)
1191	{
1192	MPI_Irecv(&b, 1, Chromotype, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &request);
1193	int flag = 0, step = 100000;
1194	MPI_Test(&request, &flag, &status);
1195
1196	while (!flag && step > 0)
1197	{
1198	MPI_Test(&request, &flag, &status);
1199	step --;
1200	}
1201
1202	if(step > 0)
1203	{
1204	Chromosome ch = to_chromosome(b);//the received chromosome
1205
1206	/**
1207	* computes the general best
1208	*/
1209
1210	if(ch.makespan < crtbest.makespan )
1211	crtbest = ch;
1212	}
1213	}
1214
1215	/**
1216	* the final result
1217	*/
1218	printf("[%i]BEST: %lf", rank, crtbest.makespan);//crtbest.print();
1219	time(&ltime);
1220	printf("GA The end time is %s\n", ctime(&ltime));
1221	}
1222
1223	}
1224
1225	}
1226
1227	MPI_Finalize();
1228
1229	return 0;
1230	}
1231
1232

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: proiecte/GAIIA/main.cpp @ 122

Download in other formats: