ga_problem.c

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

/* Name:   GA_ALP problem */
/* Date: 2008.06.04*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int generation_count = 0;
/* topology sort, return value is number of first node */
int * sort(int ** station_array, int station_number, int * first_node_number)  
{
	int x,y,i,j, flag = 0, node_number = 0;
	int first_node[4] = {0};
	int * first_node_p = NULL;
	
	x = station_number;
	y = station_number;
	
	for (j = 0; j < y; j ++) {
		flag = 0;
		for (i = 0; i < x; i ++) {
			if (station_array[i][j] == 1) {
				flag = 1;
				break;
			}
		}
		if (flag == 0 && node_number < 4) {
			first_node[node_number] = j;
			node_number ++;
		}
	}
/*	
	for (i = 0; i < 4; i++)
		printf("first_node is %d \n", first_node[i]);
	printf("node_number is %d\n", node_number);
*/
	//printf("In sort node_number is %d\n", node_number);
	if (node_number == 0) {
		printf("Error, there is no station which could be selected as the first node! \n");
		return NULL;
	}
	*first_node_number = node_number;
	first_node_p = (int *)malloc(node_number * sizeof(int));
	for (i = 0; i < node_number; i ++) {
		*(first_node_p + i) = first_node[i];
	}
	
	return first_node_p;
}

int delete_first_node(int **new_station_array, int station_number, int node)
{
	int x, y, i, j;

	x = station_number;
	y = station_number;
	
	for (j = 0; j < y; j ++) {
		for (i = 0; i < x; i ++) {
			if (i == node) {
				new_station_array[i][j] = 0;
			}
			if (j == node) {
				new_station_array[i][j] = 1; 
			}
		} 
	}

	return 0;
}

int ** generate_parents(int **topo_order_p, int number, int station_number)
{
	int i, j;
	int ** parents_p = NULL;
	
	parents_p = (int **)malloc(4 * sizeof(int *));
	for (i = 0; i < 4; i ++) {
		parents_p[i] = (int *)malloc(station_number * sizeof(int));
	}
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < station_number; j ++) {
			parents_p[i][j] = 0;
		}
	}
	
	if (number >= 4) {
		for (i = 0; i < 4; i ++) {
			for (j = 0; j < station_number; j ++) {
				parents_p[i][j] = topo_order_p[i][j];
			}
		}
	} else {
		for (i = 0; i < number; i ++) {
			for (j = 0; j < station_number; j ++) {
				parents_p[i][j] = topo_order_p[i][j];
			}
		}
		for (i = number; i < 4; i ++) {
			for (j = 0; j < station_number; j ++) {
				parents_p[i][j] = topo_order_p[0][j];
			}
		}
	}
	
	for (i = 0; i < station_number; i ++) {
		free(topo_order_p[i]);
	}
	free(topo_order_p);
	
	
	return parents_p;
}

int** divide_nodes(int ** parents_p, int *node_time_value, int station_number, FILE * fp)
{
	int i, j, k, total_node_number = 0;
	int **time_value;
	int total_time_value = 0;
	int average_time_value;
	int node_remember[4][4];
	int max_time_value = 0;
	
	
	time_value = (int **)malloc(4 * sizeof(int *));
	for (i = 0; i < 4; i ++) {
		time_value[i] = (int *)malloc(4 * sizeof(int));
	}
	
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < 4; j ++) {
			time_value[i][j] = 0;
			node_remember[i][j] = 0;
		}
	}
	
	for (i = 0; i < station_number; i ++) {
		total_time_value = total_time_value + *(node_time_value + i);
	}
	
	average_time_value = total_time_value / 4;
	
	
	for (i = 0; i < 4; i ++) {
		k = 0;
		total_node_number = 0;
		for (j = 0; j < station_number; j ++) {
			if ((time_value[i][k] + node_time_value[parents_p[i][j]]/2) < average_time_value || k == 3) {
				time_value[i][k] = time_value[i][k] + node_time_value[parents_p[i][j]];
			} else {
				k ++;
				if (k == 1) {
					node_remember[i][0] = j;
					total_node_number = j;
				} else if (k == 3) {
					//node_remember[i][2] = j - node_remember[i][0] - node_remember[i][1];
					node_remember[i][2] = j; 
				} else if (k == 2) {
					//node_remember[i][1] = j - node_remember[i][0];
					node_remember[i][1] = j;
				}
				time_value[i][k] = time_value[i][k] + node_time_value[parents_p[i][j]]; 
			}
		}
		//node_remember[i][3] = station_number - node_remember[i][0] - node_remember[i][1] - node_remember[i][2];
		node_remember[i][3] = station_number;
	}
/*	
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < 4; j ++) {
			printf("node_remember[%d][%d] is %d \n", i, j, node_remember[i][j]);
		}
	}

	for (i = 0; i < 4; i ++) {
		for (j = 0; j < 4; j ++) {
			printf("the %d th, %d node time value is %d \n", i, j, time_value[i][j]);
		}
	}
*/	
	fprintf(fp, "The %d th generation's workstation allocation is as follow:\n", generation_count);
	for (i = 0; i < 4; i ++) {
		fprintf(fp, "The %d th unit's workstation allocation:\n", i + 1);
		for (j = 0; j < 4; j ++) {
			//fprintf(fp, "node[%d]", node_remember[i][j]);
			fprintf(fp, "   station%d include:", j);
			if (j == 0) {
				for (k = 0; k < node_remember[i][j]; k ++) {
					fprintf(fp, " %d", parents_p[i][k] );
				}
				fprintf(fp,"\n");
			} else if (j == 1) {
				for (k = node_remember[i][0]; k < node_remember[i][1]; k ++) {
					fprintf(fp, " %d", parents_p[i][k] );
				}
				fprintf(fp,"\n");
			} else if (j == 2) {
				for (k = node_remember[i][1]; k < node_remember[i][2]; k ++) {
					fprintf(fp, " %d", parents_p[i][k] );
				}
				fprintf(fp,"\n");
			} else if (j == 3) {
				for (k = node_remember[i][2]; k < node_remember[i][3]; k ++) {
					fprintf(fp, " %d", parents_p[i][k] );
				}
				//fprintf(fp,"");
			}
		}
		fprintf(fp, "\n");
		for(k = 0; k < 4; k ++) {
			if (time_value[i][k] > max_time_value) {
				max_time_value = time_value[i][k];
			}
		}
		fprintf(fp, "   max_time_value in this uint is %d\n", max_time_value);
	}
		
	return time_value;
}

float * count_genes(int ** time_value)
{
	int i, j;
	float max_time[4] = {0};
	float genes[4] = {0};
	float total_genes;
	float *range;
		
	
	range = (float *)malloc(4 * sizeof(float));
	memset(range, 0, 4 * sizeof(float));
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < 4; j ++) {
			if (max_time[i] < time_value[i][j]) {
				max_time[i] = time_value[i][j];
			}
		}
	}
	
	for (i = 0; i < 4; i ++) {
		max_time[i] = 1 / max_time[i];
		total_genes = total_genes + max_time[i];
	}
	
	for (i = 0; i < 4; i ++) {
		genes[i] = max_time[i] / total_genes;
	}
	
	range[0] = genes[0];
	for (i = 1; i < 4; i ++) {
		range[i] = genes[i] + range[i-1];
	}
	
	for (i = 0; i < 4; i ++) {
		free(time_value[i]);
	}
	free(time_value);
/*
	for (i = 0; i < 4; i ++) {
		printf("max_time [%d] is %f \n ", i, max_time[i]);
		printf("Genes %d, is %f \n", i, genes[i]);
		printf("range %d, is %f \n", i, range[i]);
	}
*/
	
	return range;
}


int * select_parents(int ** parents_p, float * range)/* need 8 rand() */
{
	int i,j, flag = 0;
	float number;
	float select_index[8] = {0};
	int *parent_number_p = NULL;
	
	parent_number_p = (int *)malloc(8 * sizeof(int));
	memset(parent_number_p, 0, 8 * sizeof(int));
	
	for (j = 0; j < 8; j ++) {
		number = rand() % 100;
		select_index[j] = number / 99;
		flag = 0;
		for (i = 0; i < 3; i ++) {
			if (select_index[j] > range[i] && select_index[j] < range[i+1]) {
				flag = 1;
				parent_number_p[j] = i;
			}
		}
		if (flag == 0) {
			parent_number_p[j] = 0;
		}
	}
/*
	for (i = 0; i < 8; i ++) {
		printf("select parents parent_number is %d \n", parent_number_p[i]);
	}
*/
	return parent_number_p;	
}

int judge_validity(int ** station_array, int *parents_seq, int station_number)
{
	int i, j;
	
	for (i = 0; i < station_number - 1; i ++) {
		for (j = i + 1; j < station_number; j ++) {
			if (station_array[parents_seq[j]][parents_seq[i]] == 1) {
				return -1; /* invalid */
			}
		}
	}		
		
	return 0;
}

int ** generate_child(int * parent_number_p, int ** parents_p, int station_number, int ** station_array) 
{
	int i, j, k, m;
	int parents_1 = 0, parents_2 = 0;
	int ** child_p = NULL;
	int *pos_mark = NULL;
	int index_pos = 0;
	int *exsit_mark = NULL;
	int random_flag = 0;
	int a_pos_1 = 0, a_pos_2 = 0, temp; /* the pos of aberrance */
	
	pos_mark = (int *)malloc(station_number * sizeof(int));
	memset(pos_mark, 0, station_number * sizeof(int));
	
	
	exsit_mark = (int *)malloc(station_number * sizeof(int));
	memset(exsit_mark, 0, station_number * sizeof(int));

	child_p = (int **)malloc(4 * sizeof(int *));
	for (i = 0; i < 4; i ++) {
		child_p[i] = (int *)malloc(station_number * sizeof(int)); 
	}
	
	for (i = 0; i <4; i ++) {