ga_problem.c

利用遗传算法实现生产线平衡问题的求解

		for (j = 0; j < station_number; j ++) {
			child_p[i][j] = -1;
		}
	}
	
	//printf("generate child here!\n");
	
	for (i = 0; i < 8; i = i + 2) {
		/* generate new children */
		parents_1 = parent_number_p[i];
		parents_2 = parent_number_p[i+1];
/*		
		if (i == 6) {
			for (x = 0; x < station_number; x ++) {
				printf("i = 6 parents_p 2 is %d \n", parents_p[2][x]);
			}
			for (x = 0; x < station_number; x ++) {
				printf("i = 6 parents_p 1 is %d \n", parents_p[1][x]);
			}
		}
*/
		/* randomly select 5 pos from parents_1, and asign the value to child */
		memset(pos_mark, 0, station_number * sizeof(int));
		memset(exsit_mark, 0, station_number * sizeof(int));
				
		for (k = 0; k < 5; k ++) {
			index_pos = rand() % station_number;
			while (pos_mark[index_pos] == 1) {
				index_pos = (index_pos + 1) % station_number;
			}
			
			pos_mark[index_pos] = 1;
		}
		
		for (k = 0; k < station_number; k ++) {
			if (pos_mark[k] == 1) {
				child_p[i/2][k] = parents_p[parents_1][k];
				exsit_mark[parents_p[parents_1][k]] = 1;
			} else {
				child_p[i/2][k] = -1;
			}		
		}
		
		//printf("generate child here 2!\n");
		/* put the other */
	
		for (k = 0; k < station_number; k ++) { /* number in parents_2 */
			if (exsit_mark[parents_p[parents_2][k]] == 1) {
				continue;
			} else {
				for (j = 0; j < station_number; j ++) {
					if (pos_mark[j] == 1) {
						continue;
					} else {
						child_p[i/2][j] = parents_p[parents_2][k];
						pos_mark[j] = 1;
						exsit_mark[parents_p[parents_2][k]] = 1;
						break;
					}
				}			
			}
		}
		
		//printf("generate child here 3!\n");
		random_flag = judge_validity(station_array , child_p[i/2],station_number);
		
		if (random_flag == -1) {
			int tt = 0;
			int x;
			tt = rand() % 2;
			//printf("random_falg is = -1, tt is %d \n", tt);
			for (x = 0; x < station_number; x ++) {
				if (tt == 0) {
					child_p[i/2][x] = parents_p[parents_1][x];
				} else {
					child_p[i/2][x] = parents_p[parents_2][x];
				}
			}
		}
		
		//printf("generate child here 4!\n");
	}
	
	//printf("generate child here 5!\n");
/*
	for (m = 0; m < 4; m ++) {
		printf("Before change, The %d th child: ", m);
		for (j = 0; j < station_number; j ++) {
			printf(" %d ", child_p[m][j]);
		}
		printf("\n");
	}
*/
	for (i = 0; i < 4; i ++) {
		free(parents_p[i]);
	}
	free(parents_p);
	
	/* Aberrance process */
	
    m = rand() % 4;  /* choose child */

	a_pos_1 = rand() % station_number;
	a_pos_2 = rand() % station_number;
	//printf("m is %d, a_pos_1 is %d, a_pos_2 is %d \n", m, a_pos_1, a_pos_2);
	
	if (a_pos_1 == a_pos_2) {
		a_pos_2 = (a_pos_2 + 1) % station_number;
	}

	/* change the value of a_pos_1 and a_pos_2 */

	do {
		temp = child_p[m][a_pos_2];
		child_p[m][a_pos_2] = child_p[m][a_pos_1];
		child_p[m][a_pos_1] = temp;
		if (judge_validity(station_array , child_p[m], station_number) < 0) {
			temp = child_p[m][a_pos_2];
			child_p[m][a_pos_2] = child_p[m][a_pos_1];
			child_p[m][a_pos_1] = temp;
			a_pos_1 = (a_pos_1 + 1) % station_number;
		} else {
			break;
		}
	} while (1);
/*
	for (m = 0; m < 4; m ++) {
		printf("The %d th child: ", m);
		for (j = 0; j < station_number; j ++) {
			printf(" %d ", child_p[m][j]);
		}
		printf("\n");
	}
*/
	
	return child_p;
}



int main(int argc, char *argv[])
{
	char * ch;  /* int for the control of file end */
	FILE *fp = NULL;   /* pointer to the data file */
	FILE *f_result = NULL;
	char *p = NULL, *mid_number_p = NULL;
	char line_info[6];
	int number;
	
	int line_count = 0;
	int station_number = 0;
	int station_value[100] = {0};
		
	/* 2-d array */
	int **station_array;
	int x,y,i,j, i1, j1;
	int mark_x = 0, mark_y = 0;
	
	/* for topo sort  */ 
	int * sort_result_p = NULL, *first_sort_result_p = NULL, first_node_number;
	int ** topo_order_p = NULL;
	int new_station_number = 0, new_first_node_number = 0;
	int ** new_station_array = NULL;
	
	/*for GA Algrithm */
	int **parents_p = NULL;
	int **time_value = NULL;
	float * range = NULL;
	int *parent_number_p = 0;
	int **child_p = NULL;
	
	/* For the times of GA */
	int times = 0;   /* need to implement scanf func */
	
	printf("Please input the number of GA circulation:");
	scanf("%d", &times);
	
	printf("Please wait the result, and you can find the result in result.txt!\n");
	fp = fopen("data.txt", "r");
	if (fp == NULL) {
		printf("Error during Open data.txt!\n");
		return -1;
	}
	
	f_result = fopen("result.txt", "w");
	fgets(line_info, 20, fp);
	/* while is used for the file-treatment */
	while (ch != NULL) {
		line_count ++;
		if (line_count == 1) {
			station_number = atoi(line_info);
			//printf("Station_number is %d \n", station_number);
			/* malloc spaces for 2-d array */
			x = station_number;
			y = station_number;
			station_array = (int **)malloc(x * sizeof(int));
			for (i = 0; i < x; i ++) {
				station_array[i] = (int *)malloc(y * sizeof(int));
			}
			for (i = 0; i < x; i ++) {
				for (j = 0; j < y; j ++) {
					station_array[i][j] = 0;
				}
			}
		}
		p = line_info;
		number = atoi(line_info);
		//printf("temp_n 1 is %d\n", number);
		if (number == -1) {
			break;
		}
		if (line_count > 1 && line_count <= station_number + 1) {
			station_value[line_count - 2] = number;
		} else if (line_count != 1) {
			mark_x = number - 1;
		}
		while (*p != ',' && *p != '\n') {
			p ++;
		}
		if (*p == ',') {
			mid_number_p = p + 1;
			number = atoi(mid_number_p);
			//printf("temp_n 2 is %d\n", number);
			mark_y = number - 1;
		} 
		//printf("mark_x is %d, mark_y is %d \n", mark_x, mark_y);
		if (line_count > station_number + 1) {
			station_array[mark_x][mark_y] = 1;
		}
		//printf("Character is %s\n", line_info);
		ch = fgets(line_info, 20, fp);
		//printf("one line!\n");
	}
	fclose(fp);
	
	/* sort-func is used to find the first node */
	first_sort_result_p = sort(station_array, station_number, &first_node_number);
	
	if (first_sort_result_p == NULL) {
		printf("sort_restult_p is NULL, error happens in sort func!\n");
	} else {
		/* topo_order_p points to the sort result */
		topo_order_p = (int **)malloc(first_node_number * sizeof(int));
		for (i = 0; i < first_node_number; i ++) {
			topo_order_p[i] = (int *)malloc(station_number * sizeof(int));
		}
		
		
		new_station_number = station_number;
		x = station_number;
		y = station_number;
		/* new_station_array is used to topo-sort */
		/* initializtion of new_station_array, the copy of station_array */
		//printf("Here! new_station_number is %d\n", new_station_number);
		new_station_array = (int **)malloc(x * sizeof(int));
		for (i = 0; i < x; i ++) {
			new_station_array[i] = (int *)malloc(y * sizeof(int));
		}
		
		//printf("For first_node_number is %d, \n", first_node_number);
		for (j = 0; j < first_node_number; j ++) {
			topo_order_p[j][0] = *(first_sort_result_p + j);
			for (i1 = 0; i1 < x; i1 ++) {
				for (j1 = 0; j1 < y; j1 ++) {
					new_station_array[i1][j1] = station_array[i1][j1];
				}
			}
			for (i = 1; i < station_number; i ++) {
				/* description of the algrithm */
				//printf("* sort_result_p is %d \n", *sort_result_p);
				delete_first_node(new_station_array, station_number, topo_order_p[j][i-1]);/* need to be implemented */
				sort_result_p = sort(new_station_array, station_number, &new_first_node_number);
				topo_order_p[j][i] = *sort_result_p;
			}
			
		}
/*
		for (i = 0; i < first_node_number; i ++) {
			for (j = 0; j < station_number; j ++) {
				printf("output is i is %d, j is %d ,value is %d \n", i, j, topo_order_p[i][j]);
			}
		}
*/
	}
	
	for (i = 0; i < x; i ++) {
		free(new_station_array[i]);
	}
	free(new_station_array);
/*
	if (sort_result_p == NULL) {
		printf("sort_result_p is NULL, error happens in sort func!\n");
	} else {
		printf("first_node_number is %d \n", first_node_number);
		for (i = 0; i < first_node_number; i ++) {
			printf("first_node is %d \n", *(sort_result_p + i));
		}
	}		
	printf("After call sort! \n");
*/
	/* generate 4 parents series*/
	parents_p = generate_parents(topo_order_p, first_node_number, station_number);
	/* divide every parent into 4 nodes, and count the time value of every node */
	generation_count ++;
	time_value = divide_nodes(parents_p, station_value, station_number, f_result);
	/* count select genes */
	range = count_genes(time_value);
	/* select parents for the next generation */
	parent_number_p = select_parents(parents_p, range);
	
	/* generate child */
	child_p = generate_child(parent_number_p, parents_p, station_number, station_array);

	/* write the result into a .txt file */
	/* the number of Generation is 1000 */

	for (i = 0; i < times -1; i ++) {
		generation_count ++;
		time_value = divide_nodes(child_p, station_value, station_number, f_result);
		range = count_genes(time_value);
		parent_number_p = select_parents(child_p, range);
		child_p = generate_child(parent_number_p, child_p, station_number, station_array);
	}
	
	for (i = 0; i < station_number; i ++) {
		free(child_p[i]);
	}
	free(child_p);
	
/*
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < station_number; j ++) {
			printf("Parents_p i is %d, j is %d, value is %d \n", i, j, parents_p[i][j]);
		}
	}
*/	
	fclose(f_result);
	return 0;
}