//---------------------Include Header Libraries-------------------------- #include #include #include #include //---------------------#define marco------------------------------------- #define file_name_length 30 #define pattern_type_num 2 #define chromosome_num 100 #define default_similarity_method 1 // 1:by阿寬法 2:by直覺法 #define default_selection_manner 1 // 1:只與一個媽媽交配就生所有的pre-child 2:每一個pre-child都是與不同之媽媽所生 #define default_KNN_manner 2 // 1:p即表示"第p"的鄰居 2:p表示"第1~第p"的鄰居 #define default_least_square_line_manner 1 // 1:from puppy學姐的書 2:from網路 #define default_fitness_calculation 1 // 1:不除以1 bits的個數 2:除以1 bits的個數 #define default_random_manner 1 // 1:先random 1 bits共有的個數,然後再random決定放那裡 // 2:先random產生一個1~32767的整數，然後再轉成0與1的string #define with_frequency 1 // 1:without frequency 2:with frequency #define with_correlation_concept 1 // 1:with correlation concept 2:without correlation concept #define pre_child_num 5 #define cutting_num 1 #define be_pre_child_segment_probability 0.8 //probability of the segment which its BW value higher will to be a pre_child_segment #define be_pre_child_segment_probability_when_segment_BW_value_equal 0.5 #define lower_bound_of_mutation_probability 0.7 #define upper_bound_of_mutation_probability 0.9 #define range_of_nearest_neighbor_num 30 #define stop_threshold_value 0.05 #define stop_generation_value 1 #define replace_threshold 0.00001 #define MAX_Size 1000 // Filtering後所要留下的genes總數 #define gene_size 1000 #define sample_size 62 #define gene_size_original 2000 #define z_score_value 2.0 // 用frequency概念時,最後要留下來的gene的z_score threshold #define correlation_location 1 // 1:fitness calue = fitness + correlation 2:fitness calue = fitness / correlation //---------------------Declare Global Variables-------------------------- char file_name_of_raw_data[file_name_length],file_name_of_pattern_type[file_name_length]; FILE *input_file_of_raw_data,*input_file_of_pattern_type; //double **raw_data_array; double raw_data_array[gene_size][sample_size]; //double **raw_data_array_temp; double raw_data_array_temp[gene_size_original][sample_size]; //int *pattern_type_array; int pattern_type_array[sample_size]; //double **pearson_matrix; double pearson_matrix[gene_size][gene_size]; //double *BW_value; double BW_value[gene_size]; //double *BW_value_temp; double BW_value_temp[gene_size_original]; //double *BW_value_sorted; double BW_value_sorted[gene_size]; //double *BW_value_sorted_temp; double BW_value_sorted_temp[gene_size_original]; //int *rank_index_of_BW_value_for_every_gene; int rank_index_of_BW_value_for_every_gene[gene_size]; //int *rank_index_of_BW_value_for_every_gene_temp; int rank_index_of_BW_value_for_every_gene_temp[gene_size_original]; //int gene_size_original; //int *chromosome[chromosome_num]; int chromosome[chromosome_num][gene_size]; //int gene_size,sample_size; double average_similarity[chromosome_num]; int spouse[chromosome_num][pre_child_num]; int cutting_index[chromosome_num][pre_child_num][cutting_num]; //int *pre_child_array[chromosome_num][pre_child_num]; int pre_child_array[chromosome_num][pre_child_num][gene_size]; int generation = 2; //Initialized chromosomes are 1st generation int count_array_for_the_total_amount_of_1_bits_of_every_pre_child[chromosome_num][pre_child_num]; int count_array_for_the_total_amount_of_1_bits_of_every_chromosome[chromosome_num]; int selected_genes; //double **change_dim_base_on_pre_child[pre_child_num]; double change_dim_base_on_pre_child[pre_child_num][sample_size][gene_size]; //double **change_dim_base_on_1st_generation[chromosome_num]; double change_dim_base_on_1st_generation[chromosome_num][sample_size][gene_size]; //double **original_euclidean_distance_for_every_sample_in_every_pre_child[pre_child_num]; double original_euclidean_distance_for_every_sample_in_every_pre_child[pre_child_num][sample_size][sample_size]; //double **original_euclidean_distance_for_every_sample_in_every_chromosome[chromosome_num]; double original_euclidean_distance_for_every_sample_in_every_chromosome[chromosome_num][sample_size][gene_size]; //double **sorted_euclidean_distance_for_every_sample_in_every_pre_child[pre_child_num]; double sorted_euclidean_distance_for_every_sample_in_every_pre_child[pre_child_num][sample_size][sample_size]; //double **sorted_euclidean_distance_for_every_sample_in_every_chromosome[chromosome_num]; double sorted_euclidean_distance_for_every_sample_in_every_chromosome[chromosome_num][sample_size][sample_size]; double average_euclidean_distance_value_for_different_nearest_neighbor_value[pre_child_num][range_of_nearest_neighbor_num]; double average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[chromosome_num][range_of_nearest_neighbor_num]; double average_pattern_type_value_for_different_nearest_neighbor_value[pre_child_num][range_of_nearest_neighbor_num]; double average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[chromosome_num][range_of_nearest_neighbor_num]; double coefficients_of_least_square_line[pre_child_num][2]; double coefficients_of_least_square_line_base_on_1st_generation[chromosome_num][2]; double fitness_value_of_pre_child[pre_child_num]; double fitness_value_of_chromosome[chromosome_num]; int index_of_best_pre_child; double best_fitness_value_of_pre_child; int stop_generation = 0; double stop_threshold; double average_fitness_value_in_some_generation; //int **sol_generation; int sol_generation[gene_size][200]; int *temp_count_ary_1,*temp_count_ary_2; FILE *debug_file = fopen("debug_file.txt","w"); //FILE *debug_file2 = fopen("debug_file2.txt","w"); //FILE *debug_file3 = fopen("debug_file3.txt","w"); //FILE *debug_file4 = fopen("debug_file4.txt","w"); //FILE *line = fopen("Least_Square_Line.txt","w"); FILE *average_fitness_value = fopen("Average_Best_Fitness_Value_In_Every_Generation.xls","w"); FILE *threshold_file = fopen("Threshold_Value_In_Every_Generation.xls","w"); FILE *average_sim_in_every_generation = fopen("Average_Similarity_In_Every_Generation.xls","w"); FILE *information = fopen("information.txt","w"); //---------------------Declare Procedure Protype------------------------- void Print_CopyRight_Declaration(void); void Ask_For_Input_File_Name(void); void Read_File_Contents_Into_Array(void); void Filtering(void); void Calculate_Correlation_Matrix(void); void Normalization_Of_Input_Data(void); void Calculate_BW_Value_For_All_Gene_Index_And_Output_Into_File(void); void Sort_BW_Value_For_All_Gene_Index_And_Output_Into_File(void); void Random_Create_Chromosome_And_Output_Into_File(void); void Calculate_The_Total_Amount_Of_1_Bits_For_Every_Chromosome(void); void Change_Dimension_Base_On_1st_Generation(void); void Calculate_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(void); void Sort_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(void); void Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(void); void Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(void); void Calculate_The_Coefficients_Of_Least_Square_Line_Base_On_1st_Generation(void); void Calculate_The_Best_Fitness_Value_Of_Chromosome_And_Output_Into_File(void); void Initialization_For_All_Dynamic_Declaration_Arrays_Which_Used_In_Recursion(void); void Calculate_Values_of_Average_Similarity_For_Corresponding_Chromosome_And_Output_Into_File(int); void Random_Select_Spouse_And_Output_Into_File(void); void Random_Select_Cutting_Index_And_Output_Into_File(void); void Create_Pre_Child_And_Output_Into_File(void); void Create_Pre_Child_After_Mutation_And_Output_Into_File(void); void Calculate_The_Total_Amount_Of_1_Bits_For_Every_Pre_Child(void); void Generate_New_Generation_And_Output_Into_File(void); void Change_Dimension_Base_On_Pre_Child(int); void Calculate_All_Euclidean_Distance_For_Every_Sample(int); void Sort_All_Euclidean_Distance_For_Every_Sample(int); //=>int for debug void Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor(int);//=>int for debug void Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor(int);//=>int for debug void Calculate_The_Coefficients_Of_Least_Square_Line(int); //=>int for debug void Calculate_The_Best_Fitness_Value_Of_Pre_Child_And_Output_Into_File(int); //=>int for debug void Replace_Or_Not(int); void Write_Information_File(void); void Write_Solution_File(void); void Swap(double [],int,int); int Partition(double [],int,int); void QuickSort(double [],int,int); double Similarity(int,int); void Pre_Condition_Statment_In_File(FILE *,char *); //---------------------Begin of Main Function---------------------------- int main(void) { Print_CopyRight_Declaration(); Ask_For_Input_File_Name(); //--------------------------------Initialization begin----------------------- Read_File_Contents_Into_Array(); Filtering(); Normalization_Of_Input_Data(); Calculate_Correlation_Matrix(); Random_Create_Chromosome_And_Output_Into_File(); Calculate_BW_Value_For_All_Gene_Index_And_Output_Into_File(); Sort_BW_Value_For_All_Gene_Index_And_Output_Into_File(); Calculate_The_Total_Amount_Of_1_Bits_For_Every_Chromosome(); Change_Dimension_Base_On_1st_Generation(); Calculate_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(); Sort_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(); Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(); Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(); Calculate_The_Coefficients_Of_Least_Square_Line_Base_On_1st_Generation(); Calculate_The_Best_Fitness_Value_Of_Chromosome_And_Output_Into_File(); Initialization_For_All_Dynamic_Declaration_Arrays_Which_Used_In_Recursion(); //--------------------------------Initialization end------------------------- //----------------------feature selection by GA method begin----------------- while(stop_generation < stop_generation_value) { //--------------------------------selection begin---------------------------- Calculate_Values_of_Average_Similarity_For_Corresponding_Chromosome_And_Output_Into_File(default_similarity_method); Random_Select_Spouse_And_Output_Into_File(); //---------------------selection over and cross-over begin------------------- Random_Select_Cutting_Index_And_Output_Into_File(); //Create_Pre_Child_And_Output_Into_File(); //---------------------cross-over over and mutation begin-------------------- Create_Pre_Child_After_Mutation_And_Output_Into_File(); //---------------------mutation over and replace begin----------------------- Calculate_The_Total_Amount_Of_1_Bits_For_Every_Pre_Child(); Generate_New_Generation_And_Output_Into_File(); //---------------------replace over and recursive begin---------------------- //-----------recursive over and feature selection by GA method over---------- } Write_Solution_File(); Write_Information_File(); return 0; } //----------------------End of Main Function------------------------------ //----------------------Procedures Definition----------------------------- void Print_CopyRight_Declaration(void) //copyright declaration { printf(" ┌────────────────────────────────┐\n"); printf(" │ § 2003 NTU CSIE BioInformatics Lab. All Rights Reserved. § │\n"); printf(" └────────────────────────────────┘\n"); printf(" 【Paper Topic】Microarray Feature Selection by Genetic Algorithm\n"); printf(" 【Designed By】蔡懷寬(博士班)；莊涵宇(研究生)；邱樺聲(研究生)\n"); } //------------------------------------------------------------------------ void Ask_For_Input_File_Name(void) //read raw data & pattern type file name { printf("------------------------------------------------------------------------------\n"); do //input raw data file name { printf("Please input file name(raw data) : "); scanf("%s",file_name_of_raw_data); input_file_of_raw_data = fopen(file_name_of_raw_data,"r"); if(input_file_of_raw_data == NULL) { printf("File doesn't exist.\n"); } }while(input_file_of_raw_data == NULL); do //input pattern type file name { printf("Please input file name(pattern type) : "); scanf("%s",file_name_of_pattern_type); input_file_of_pattern_type = fopen(file_name_of_pattern_type,"r"); if(input_file_of_pattern_type == NULL) { printf("File doesn't exist.\n"); } }while(input_file_of_pattern_type == NULL); printf(" ┌────────────────────────────────┐\n"); printf("-----│ Initialization │-----\n"); printf(" └────────────────────────────────┘\n"); } //------------------------------------------------------------------------------- void Read_File_Contents_Into_Array(void) //read raw data and pattern type into array { printf("Read %s(raw data) and %s(pattern_type) into arrays......",file_name_of_raw_data,file_name_of_pattern_type); char temp[200],*stop_at,ch; double value; int row = 0,col = 0,i = 0,val; //------------------------read pattern type into 1-D int array--------------- //pattern_type_array = new int[sample_size]; i = 0; do { fscanf(input_file_of_pattern_type,"%s",temp); fscanf(input_file_of_pattern_type,"%c",&ch); fscanf(input_file_of_pattern_type,"%s",temp); fscanf(input_file_of_pattern_type,"%c",&ch); if(feof(input_file_of_pattern_type) != 0) break; val = atoi(temp); *(pattern_type_array + i) = val; //printf("%d ",*(pattern_type_array+i)); i++; }while(feof(input_file_of_pattern_type) == 0); //sample_size = i; //------------------------read raw data into 2-D double array----------------- //calculate gene size for dynamic declaration of raw_data_array in the future i = 0; while(feof(input_file_of_raw_data) == 0) { fscanf(input_file_of_raw_data,"%c",&ch); if(ch == (char)10) i++; } fclose(input_file_of_raw_data); //gene_size= i-2; //???? //printf("%d\n\n",gene_size); //read raw data into 2-D double raw_data_array by dynamic declaration i = 0; input_file_of_raw_data = fopen(file_name_of_raw_data,"r"); /*raw_data_array_temp = new double*[gene_size_original]; //dynamic declaration for 2-D double raw_data_array for(int num = 0 ; num < gene_size_original ; num++) { raw_data_array_temp[num] = new double[sample_size]; }*/ do //ignore first line { fscanf(input_file_of_raw_data,"%c",&ch); }while(ch!=(char)10); do { while(feof(input_file_of_raw_data) == 0) //ignore first two columns { fscanf(input_file_of_raw_data,"%c",&ch); if(ch == (char)9) i++; if(i == 2) break; } while(feof(input_file_of_raw_data) == 0) { fscanf(input_file_of_raw_data,"%s",temp); fscanf(input_file_of_raw_data,"%c",&ch); value = strtod(temp,&stop_at); raw_data_array_temp[row][col] = value; col++; if(ch == (char)10) { row++; col = 0; break; } } i = 0; }while(feof(input_file_of_raw_data) == 0); printf("ok.\n"); fclose(input_file_of_raw_data); fclose(input_file_of_pattern_type); } //------------------------------------------------------------------------------- void Filtering(void) { double BSS,WSS; int i,j; //BW_value_temp = new double[gene_size_original]; double temp_all; double temp_one[pattern_type_num]; int pattern_type_count[pattern_type_num]; double item_average_value_for_all_pattern_type_in_one_gene_index; double item_average_value_for_one_pattern_type_in_one_gene_index[pattern_type_num]; printf("Filtering to %d genes....",MAX_Size); for(i = 0 ; i < gene_size_original ; i++) { //----------------------------------------------------- temp_all = 0.; for(j = 0 ; j < pattern_type_num ; j++) { temp_one[j] = 0.; pattern_type_count[j] = 0; } BSS = WSS = 0.; //----------------------------------------------------- for(j = 0 ; j < sample_size ; j++) { temp_all = temp_all + raw_data_array_temp[i][j]; } item_average_value_for_all_pattern_type_in_one_gene_index = temp_all / sample_size; //------------------------------------------------------ for(j = 0 ; j < sample_size ; j++) { if(pattern_type_array[j] == 0) { temp_one[0] = temp_one[0] + raw_data_array_temp[i][j]; pattern_type_count[0] = pattern_type_count[0] + 1; } else if(pattern_type_array[j] == 1) { temp_one[1] = temp_one[1] + raw_data_array_temp[i][j]; pattern_type_count[1] = pattern_type_count[1] + 1; } } for(j = 0 ;j < pattern_type_num ; j++) { item_average_value_for_one_pattern_type_in_one_gene_index[j] = temp_one[j] / pattern_type_count[j]; } //------------------------------------------------------- for(j = 0 ; j < pattern_type_num; j++) { BSS = BSS + ( pattern_type_count[j] * ((item_average_value_for_one_pattern_type_in_one_gene_index[j] -item_average_value_for_all_pattern_type_in_one_gene_index)* (item_average_value_for_one_pattern_type_in_one_gene_index[j] -item_average_value_for_all_pattern_type_in_one_gene_index)) ); } //------------------------------------------------------- for(j = 0 ; j < sample_size ; j++) { if(pattern_type_array[j] == 0) { WSS = WSS + ((raw_data_array_temp[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[0]) * (raw_data_array_temp[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[0])); } else if(pattern_type_array[j] == 1) { WSS = WSS + ((raw_data_array_temp[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[1]) * (raw_data_array_temp[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[1])); } } //------------------------------------------------------- BW_value_temp[i] = BSS / WSS; } //------------------------------------------ //BW_value_sorted_temp = new double[gene_size_original]; //rank_index_of_BW_value_for_every_gene_temp = new int[gene_size_original]; for(i = 0 ; i < gene_size_original ; i++) { BW_value_sorted_temp[i] = BW_value_temp[i]; } QuickSort(BW_value_sorted_temp,0,gene_size_original-1); for(i = 0 ; i < gene_size_original ; i++) { for(j = 0 ; j < gene_size_original ; j++) { if(BW_value_temp[i] == BW_value_sorted_temp[j]) { rank_index_of_BW_value_for_every_gene_temp[i] = j; break; } } } /*for(i = 0 ; i < gene_size ; i++) { fprintf(debug_file,"%d \n",rank_index_of_BW_value_for_every_gene_temp[i]+1); }*/ //----------------------------------------- //gene_size_original = gene_size; int counter = 0; //gene_size = MAX_Size; /*raw_data_array = new double*[gene_size]; for(int num = 0 ; num < gene_size ; num++) { raw_data_array[num] = new double[sample_size]; }*/ for(i = 0 ; i < gene_size_original ; i++) { if((rank_index_of_BW_value_for_every_gene_temp[i]+1) > (gene_size_original - MAX_Size)) { for(j = 0 ; j < sample_size ; j++) { raw_data_array[counter][j] = raw_data_array_temp[i][j]; //fprintf(debug_file,"%lf\t",raw_data_array[counter][j]); } //fprintf(debug_file,"%d\n",rank_index_of_BW_value_for_every_gene_temp[i]+1); counter++; } } /*FILE *ddd = fopen("solution.txt","r"); int po = 0; int de = 0; int ccc = 0; do { fscanf(ddd,"%d",&de); if(de == 1) { for(j = 0 ; j < sample_size ; j++) { raw_data_array[ccc][j] = raw_data_array_temp[po][j]; } ccc++; } po++; }while(feof(ddd) == 0); for(i = 0 ; i < gene_size ; i++) { for(j = 0 ; j < sample_size ; j++) { printf("%lf\t",raw_data_array[i][j]); } printf("\n"); }*/ printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_Correlation_Matrix(void) { //FILE *pearson = fopen("pearson_matrix.xls","w"); int num,i,j,ptr; double temp = 0 , temp1 = 0 , temp2 = 0 , temp3 = 0 , temp4 = 0; double XY = 0 , X = 0 , Y = 0 , X_square = 0 , Y_square = 0; /*pearson_matrix = new double*[gene_size]; for(num = 0 ; num < gene_size ; num++) { pearson_matrix[num] = new double[gene_size]; }*/ printf("Calculate the Pearson correlation matrix......"); for(i = 0 ; i < gene_size ; i++) { for(j = 0 ; j < gene_size ; j++) { temp = 0 , temp1 = 0 , temp2 = 0 , temp3 = 0 , temp4 = 0; XY = 0 , X = 0 , Y = 0 , X_square = 0 , Y_square = 0; if((i!=j)&&(ij) { pearson_matrix[i][j] = pearson_matrix[j][i]; } else if(i==j) { pearson_matrix[i][j] = 0; } //fprintf(pearson,"%lf\t",pearson_matrix[i][j]); } //fprintf(pearson,"\n"); } //fclose(pearson); printf("ok.\n"); } //------------------------------------------------------------------------------- void Normalization_Of_Input_Data(void) { printf("Normalize the input data and store into arrays again......"); //FILE *normalization = fopen("input_data_Normalized.xls","w"); int i,j; double mean,STD; for(i = 0 ; i < gene_size ; i++) { mean = 0; STD = 0; //----------------------------------------- for(j = 0 ; j < sample_size ; j++) { mean = mean + raw_data_array[i][j]; } mean = mean / sample_size; //----------------------------------------- for(j = 0 ; j < sample_size ; j++) { STD = STD + (raw_data_array[i][j] - mean)*(raw_data_array[i][j] - mean); } STD = STD / (sample_size-1); STD = sqrt(STD); //----------------------------------------- for(j = 0 ; j < sample_size ; j++) { raw_data_array[i][j] = (raw_data_array[i][j] - mean) / STD; //fprintf(normalization,"%lf\t",raw_data_array[i][j]); } //fprintf(normalization,"%lf\t%lf",mean,STD); //fprintf(normalization,"\n"); } printf("ok.\n"); //fclose(normalization); } //------------------------------------------------------------------------------- void Calculate_BW_Value_For_All_Gene_Index_And_Output_Into_File(void) //calculate BW value for all gene index by BSS/WSS { double BSS,WSS; int i,j; //BW_value = new double[gene_size]; double temp_all; double temp_one[pattern_type_num]; int pattern_type_count[pattern_type_num]; double item_average_value_for_all_pattern_type_in_one_gene_index; double item_average_value_for_one_pattern_type_in_one_gene_index[pattern_type_num]; printf("Calculate BW value of all gene from %d sample and %d pattern(0:無病,1:有病)..",sample_size,pattern_type_num); for(i = 0 ; i < gene_size ; i++) { //----------------------------------------------------- temp_all = 0.; for(j = 0 ; j < pattern_type_num ; j++) { temp_one[j] = 0.; pattern_type_count[j] = 0; } BSS = WSS = 0.; //----------------------------------------------------- for(j = 0 ; j < sample_size ; j++) { temp_all = temp_all + raw_data_array[i][j]; } item_average_value_for_all_pattern_type_in_one_gene_index = temp_all / sample_size; //------------------------------------------------------ for(j = 0 ; j < sample_size ; j++) { if(pattern_type_array[j] == 0) { temp_one[0] = temp_one[0] + raw_data_array[i][j]; pattern_type_count[0] = pattern_type_count[0] + 1; } else if(pattern_type_array[j] == 1) { temp_one[1] = temp_one[1] + raw_data_array[i][j]; pattern_type_count[1] = pattern_type_count[1] + 1; } } for(j = 0 ;j < pattern_type_num ; j++) { item_average_value_for_one_pattern_type_in_one_gene_index[j] = temp_one[j] / pattern_type_count[j]; } //------------------------------------------------------- for(j = 0 ; j < pattern_type_num; j++) { BSS = BSS + ( pattern_type_count[j] * ((item_average_value_for_one_pattern_type_in_one_gene_index[j] -item_average_value_for_all_pattern_type_in_one_gene_index)* (item_average_value_for_one_pattern_type_in_one_gene_index[j] -item_average_value_for_all_pattern_type_in_one_gene_index)) ); } //------------------------------------------------------- for(j = 0 ; j < sample_size ; j++) { if(pattern_type_array[j] == 0) { WSS = WSS + ((raw_data_array[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[0]) * (raw_data_array[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[0])); } else if(pattern_type_array[j] == 1) { WSS = WSS + ((raw_data_array[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[1]) * (raw_data_array[i][j] - item_average_value_for_one_pattern_type_in_one_gene_index[1])); } } //------------------------------------------------------- BW_value[i] = BSS / WSS; } printf("ok.\n"); } //------------------------------------------------------------------------------- void Sort_BW_Value_For_All_Gene_Index_And_Output_Into_File(void) { //BW_value_sorted = new double[gene_size]; //rank_index_of_BW_value_for_every_gene = new int[gene_size]; int i,j; printf("Sort the BW value of all gene index by QuickSort in ascending manner......"); for(i = 0 ; i < gene_size ; i++) { BW_value_sorted[i] = BW_value[i]; } QuickSort(BW_value_sorted,0,gene_size-1); for(i = 0 ; i < gene_size ; i++) { for(j = 0 ; j < gene_size ; j++) { if(BW_value[i] == BW_value_sorted[j]) { rank_index_of_BW_value_for_every_gene[i] = j; break; } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_The_Total_Amount_Of_1_Bits_For_Every_Chromosome(void) { printf("Calculate the total amount of 1 bits for every chromosome......"); for(int i = 0 ; i < chromosome_num ; i++) { count_array_for_the_total_amount_of_1_bits_of_every_chromosome[i] = 0; for(int j = 0 ; j < gene_size ; j++) { if(chromosome[i][j] == 1) count_array_for_the_total_amount_of_1_bits_of_every_chromosome[i]++; } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Change_Dimension_Base_On_1st_Generation(void) { int i,j,k,temp; /*for(i = 0 ; i < chromosome_num ; i++) { change_dim_base_on_1st_generation[i] = new double*[sample_size]; } for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { change_dim_base_on_1st_generation[i][j] = new double[gene_size]; } }*/ printf("Change dimension base on 1st generation......"); for(i = 0 ; i < chromosome_num ; i++) { temp = 0; for(j = 0 ; j < gene_size ; j++) { if(chromosome[i][j] == 1) { for(k = 0 ; k < sample_size ; k++) { change_dim_base_on_1st_generation[i][k][temp] = raw_data_array[j][k]; } temp++; } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(void) { int i,j,k,m; double euclidean_distance,temp; /*for(i = 0 ; i < chromosome_num ; i++) { original_euclidean_distance_for_every_sample_in_every_chromosome[i] = new double*[sample_size]; } for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { original_euclidean_distance_for_every_sample_in_every_chromosome[i][j] = new double[sample_size]; } }*/ printf("Calculate all euclidean distance for every sample base on 1st generation..."); for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { for(k = 0 ; k < sample_size ; k++) { if(j < k) { euclidean_distance = 0.; for(m = 0 ; m < count_array_for_the_total_amount_of_1_bits_of_every_chromosome[i] ; m++) { temp = ((change_dim_base_on_1st_generation[i][j][m] - change_dim_base_on_1st_generation[i][k][m])*(change_dim_base_on_1st_generation[i][j][m] - change_dim_base_on_1st_generation[i][k][m])); euclidean_distance = euclidean_distance + temp; } euclidean_distance = sqrt(euclidean_distance); original_euclidean_distance_for_every_sample_in_every_chromosome[i][j][k] = euclidean_distance; } else if(j > k) { original_euclidean_distance_for_every_sample_in_every_chromosome[i][j][k] = original_euclidean_distance_for_every_sample_in_every_chromosome[i][k][j]; } else { original_euclidean_distance_for_every_sample_in_every_chromosome[i][j][k] = 0.; } } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Sort_All_Euclidean_Distance_For_Every_Sample_Base_On_1st_Generation(void) { int i,j,k; printf("Sort all euclidean distance for every sample base on 1st generation......"); /*for(i = 0 ; i < chromosome_num ; i++) { sorted_euclidean_distance_for_every_sample_in_every_chromosome[i] = new double*[sample_size]; } for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][j] = new double[sample_size]; } }*/ for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { for(k = 0 ; k < sample_size ; k++) { sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][j][k] = original_euclidean_distance_for_every_sample_in_every_chromosome[i][j][k]; } } } for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < sample_size ; j++) { QuickSort(sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][j],0,sample_size-1); } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(void) { double temp; int i,j,k,m; printf("Calculate the average euclidean distance value base on 1st generation....."); if(range_of_nearest_neighbor_num < sample_size) { for(i = 0 ; i < chromosome_num ; i++) { for(j = 1 ; j <= range_of_nearest_neighbor_num ; j++) { if(default_KNN_manner == 2) { temp = 0.; for(k = 1 ; k <= j ; k++) { for(m = 0 ; m < sample_size ; m++) { temp = temp + (sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][k]*sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][k]); } } average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j-1] = temp / (sample_size * j); } else if(default_KNN_manner == 1) { temp = 0.; for(m = 0 ; m < sample_size ; m++) { temp = temp + (sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][j]*sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][j]); } average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j-1] = temp / sample_size; } } } } else if(range_of_nearest_neighbor_num >= sample_size) { printf("ERROR：No enough neighbor.\n"); } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor_Base_On_1st_Generation(void) { double temp; int i,j,k,m,n; printf("Calculate the average pattern type value base on 1st generation....."); if(range_of_nearest_neighbor_num < sample_size) { for(i = 0 ; i < chromosome_num ; i++) { for(j = 1 ; j <= range_of_nearest_neighbor_num ; j++) { if(default_KNN_manner == 2) { temp = 0.; for(k = 1 ; k <= j ; k++) { for(m = 0 ; m < sample_size ; m++) { for(n = 0 ; n < sample_size ; n++) { if(original_euclidean_distance_for_every_sample_in_every_chromosome[i][m][n] == sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][k]) break; } temp = temp + ((pattern_type_array[n] - pattern_type_array[m]) * (pattern_type_array[n] - pattern_type_array[m])); } } average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j-1] = temp / ((sample_size * 2) * j); } else if(default_KNN_manner == 1) { temp = 0.; for(m = 0 ; m < sample_size ; m++) { for(n = 0 ; n < sample_size ; n++) { if(original_euclidean_distance_for_every_sample_in_every_chromosome[i][m][n] == sorted_euclidean_distance_for_every_sample_in_every_chromosome[i][m][j]) break; } temp = temp + ((pattern_type_array[n] - pattern_type_array[m]) * (pattern_type_array[n] - pattern_type_array[m])); } average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j-1] = temp / (sample_size * 2); } } } } else if(range_of_nearest_neighbor_num >= sample_size) { printf("ERROR：No enough neighbor.\n"); } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_The_Coefficients_Of_Least_Square_Line_Base_On_1st_Generation(void) { int i,j,n = range_of_nearest_neighbor_num; double sigma_x,sigma_y,sigma_x_pow_two,sigma_xy,average_x,average_y; printf("Calculate the coefficients of least square line base on 1st generation...."); for(i =0 ; i < chromosome_num ; i++) { if(default_least_square_line_manner == 1) { sigma_x = sigma_y = sigma_x_pow_two = sigma_xy = average_x = average_y =0.; for(j = 0 ; j < range_of_nearest_neighbor_num ; j++) { sigma_x = sigma_x + average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]; sigma_y = sigma_y + average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]; sigma_x_pow_two = sigma_x_pow_two + (average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]*average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]); sigma_xy = sigma_xy + (average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]*average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]); } average_y = sigma_y / n; average_x = sigma_x / n; //m coefficients_of_least_square_line_base_on_1st_generation[i][0] = ( sigma_xy - (average_y*sigma_x) - (average_x*sigma_y) + ( n * average_x * average_y) ) / (sigma_x_pow_two - ( 2 * average_x * sigma_x ) + (n * (average_x*average_x) ) ); //b coefficients_of_least_square_line_base_on_1st_generation[i][1] = average_y - (coefficients_of_least_square_line_base_on_1st_generation[i][0]*average_x); } else if(default_least_square_line_manner == 2) { sigma_x = sigma_y = sigma_x_pow_two = sigma_xy = 0.; for(j = 0 ; j < range_of_nearest_neighbor_num ; j++) { sigma_x = sigma_x + average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]; sigma_y = sigma_y + average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]; sigma_x_pow_two = sigma_x_pow_two + (average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]*average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]); sigma_xy = sigma_xy + (average_euclidean_distance_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]*average_pattern_type_value_for_different_nearest_neighbor_value_base_on_1st_generation[i][j]); } // y = mx + b //m coefficients_of_least_square_line_base_on_1st_generation[i][0] = ((n*sigma_xy)-(sigma_x*sigma_y))/((n*sigma_x_pow_two)-(sigma_x*sigma_x)); //b coefficients_of_least_square_line_base_on_1st_generation[i][1] = ((sigma_y*sigma_x_pow_two)-(sigma_x*sigma_xy))/((n*sigma_x_pow_two)-(sigma_x*sigma_x)); } if(coefficients_of_least_square_line_base_on_1st_generation[i][1] < 0) coefficients_of_least_square_line_base_on_1st_generation[i][1] = -(coefficients_of_least_square_line_base_on_1st_generation[i][1]); } printf("ok.\n"); } //----------------------------------------------------------------------------------------------------// void Calculate_The_Best_Fitness_Value_Of_Chromosome_And_Output_Into_File(void) { temp_count_ary_1 = new int[gene_size]; int i,j,k,count; double pearson_sum = 0; for(i = 0 ; i < chromosome_num ; i++) { fitness_value_of_chromosome[i] = 1 / (1 + exp(coefficients_of_least_square_line_base_on_1st_generation[i][1])); if(default_fitness_calculation == 1) { if(with_correlation_concept == 1) { count = 0; pearson_sum = 0; for(j = 0 ; j < gene_size ; j++) { temp_count_ary_1[j] = -1; if(chromosome[i][j] == 1) { temp_count_ary_1[count] = j; count++; } } for(j = 0 ; j < count ; j++) { for(k = j+1 ; k < count ; k++) { pearson_sum = pearson_sum + pearson_matrix[temp_count_ary_1[j]][temp_count_ary_1[k]]; } } if(correlation_location == 1) { fitness_value_of_chromosome[i] = fitness_value_of_chromosome[i] + (pearson_sum / (0.5*((count*count)-count))); } else if(correlation_location == 2) { fitness_value_of_chromosome[i] = (fitness_value_of_chromosome[i] / (pearson_sum / (0.5*((count*count)-count)))); } } } else if(default_fitness_calculation == 2) { fitness_value_of_chromosome[i] = (fitness_value_of_chromosome[i]/count_array_for_the_total_amount_of_1_bits_of_every_chromosome[i]); } } } //------------------------------------------------------------------------------- void Initialization_For_All_Dynamic_Declaration_Arrays_Which_Used_In_Recursion(void) { int i,j; /*for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < pre_child_num ; j ++) { pre_child_array[i][j] = new int[gene_size]; } }*/ /*for(i = 0 ; i < pre_child_num ; i++) { change_dim_base_on_pre_child[i] = new double*[sample_size]; original_euclidean_distance_for_every_sample_in_every_pre_child[i] = new double*[sample_size]; sorted_euclidean_distance_for_every_sample_in_every_pre_child[i] = new double*[sample_size]; } for(i = 0 ; i < pre_child_num ; i++) { for(j = 0 ; j < sample_size ; j++) { change_dim_base_on_pre_child[i][j] = new double[gene_size]; original_euclidean_distance_for_every_sample_in_every_pre_child[i][j] = new double[sample_size]; sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][j] = new double[sample_size]; } }*/ /*sol_generation = new int*[gene_size]; for(i = 0 ; i < gene_size ; i++) { sol_generation[i] = new int[200]; }*/ temp_count_ary_2 = new int[gene_size]; printf(" ┌────────────────────────────────┐\n"); printf("-----│Beginning of Microarray Feature Selection by Genetic Alogorithm │-----\n"); printf(" └────────────────────────────────┘\n"); } //------------------------------------------------------------------------------- void Random_Create_Chromosome_And_Output_Into_File(void) //random create chromosomes(that's,solutions) and put into file { printf("Create %d chromosomes which gene size is %d randomly......",chromosome_num,gene_size); int i,j,k,m; int temp_count,temp,index,temp_index; int temp_ary[15]; /*for(int num=0;num=gene_size);// || temp>=MAX_Size); //printf("%d\n",temp); do { temp_index = rand()%gene_size; if(chromosome[i][temp_index] != 1) { chromosome[i][temp_index] = 1; temp--; } }while(temp>=1); for(j = 0 ; j = 15) { temp = rand()%32768; //fprintf(debug_file2,"\n\nchromosome : %d , index = %d , temp = %d\n\n",i+1,index+1,temp); for(k = 14 ; k >= 0 ; k--) { if(temp >= (int)pow(2,k)) break; } //fprintf(debug_file2,"k = %d\n",k+1); for(m = k+1 ; m < 15 ; m++) { temp_ary[m] = 0; } for(m = k ; m >= 0 ; m--) { if( (temp-(int)pow(2,m)) >= 0) { temp = temp - ((int)pow(2,m)); temp_ary[m] = 1; } else { temp_ary[m] = 0; } } for(j = 0 ; j < 15 ; j++) { chromosome[i][index] = temp_ary[j]; //fprintf(debug_file2,"%d ",chromosome[i][index]); index++; } } for( j = index ; j < gene_size ; j++) { chromosome[i][j] = rand()%2; //fprintf(debug_file2,"\nindex = %d , bit = %d\n",j+1,chromosome[i][j]); } } for(j=0;j 0)) { break; } } for(j=0;j=50) { fprintf(chromosome_file,"\n "); }*/ } //fprintf(chromosome_file,"\n\n"); } printf("ok.\n"); //fclose(chromosome_file); /*int inc = 100; for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < (i+1)*inc ; j++) { if(j < gene_size) { chromosome[i][j] = 1; } } for(j = (i+1)*inc ; j < gene_size ; j++) { if(j < gene_size) { chromosome[i][j] = 0; } } }*/ } //------------------------------------------------------------------------------- void Calculate_Values_of_Average_Similarity_For_Corresponding_Chromosome_And_Output_Into_File(int method_select) //Calculate the value of average similarity { double temp,temp_bit,average; //FILE *average_sim; //average_sim = fopen("Average Similarity.txt","w"); //Pre_Condition_Statment_In_File(average_sim,"Average Similarity.txt"); printf("Calculate average similarity "); if(method_select == 1) printf("by 阿寬法 for corresponding chromosome......"); else if(method_select == 2) printf("by 直覺法 for corresponding chromosome......"); if(method_select == 1) //by阿寬法 { for(int i=0;iaverage_similarity[i]) { mark_spouse_for_not_fit[spouse_index] = 1; continue; } else { break; } }while(temp>average_similarity[i]); } if(j != 0) { if(default_selection_manner == 1) spouse[i][j] = spouse[i][0]; else if(default_selection_manner == 2) spouse[i][j] = spouse_index; } else if(j == 0) { spouse[i][j] = spouse_index; } /*if(j == 0) fprintf(spouse_file,"chromosome %4d's 1st spouse is chromosome %4d. It's Similarity(%4d,%4d) = %lf <= average similarity( = %lf) of chromosome %4d.\n",(i+1),(spouse[i][j]+1),(i+1),(spouse[i][j]+1),temp,average_similarity[i],(i+1)); if(j == 1) fprintf(spouse_file,"chromosome %4d's 2nd spouse is chromosome %4d. It's Similarity(%4d,%4d) = %lf <= average similarity( = %lf) of chromosome %4d.\n",(i+1),(spouse[i][j]+1),(i+1),(spouse[i][j]+1),temp,average_similarity[i],(i+1)); if(j == 2) fprintf(spouse_file,"chromosome %4d's 3rd spouse is chromosome %4d. It's Similarity(%4d,%4d) = %lf <= average similarity( = %lf) of chromosome %4d.\n",(i+1),(spouse[i][j]+1),(i+1),(spouse[i][j]+1),temp,average_similarity[i],(i+1)); if(j >= 3) fprintf(spouse_file,"chromosome %4d's %dth spouse is chromosome %4d. It's Similarity(%4d,%4d) = %lf <= average similarity( = %lf) of chromosome %4d.\n",(i+1),(j+1),(spouse[i][j]+1),(i+1),(spouse[i][j]+1),temp,average_similarity[i],(i+1)); */ } //fprintf(spouse_file,"\n\n"); } printf("ok.\n"); //fclose(spouse_file); } //------------------------------------------------------------------------------- void Random_Select_Cutting_Index_And_Output_Into_File(void) //select cutting index randomly for every chromosome and it's spouse { //FILE *cutting_index_file; int index,i,j,k; printf("Select %d cutting index randomly for every chromosome and it's spouse......",cutting_num); if(gene_size>cutting_num) { //cutting_index_file = fopen("Cutting Index.txt","w"); //Pre_Condition_Statment_In_File(cutting_index_file,"Cutting Index.txt"); time_t t; srand((unsigned) time(&t)); for(i=0;i0) { do { index = rand()%gene_size; }while(((index>cutting_index[i][k][j-1]) && (index<((gene_size-1-1)-(cutting_num-(j+1))))) == false); cutting_index[i][k][j] = index; } /*if(j= 3) fprintf(cutting_index_file," for their %dth pre-child.",(k+1)); fprintf(cutting_index_file,"\n");*/ } //fprintf(cutting_index_file,"\n\n"); } printf("ok.\n"); //fclose(cutting_index_file); } else if(gene_size<=cutting_num) { printf("error!\nGene size <= Cutting number , cutting is failed.\n"); exit(1); } } //------------------------------------------------------------------------------- void Create_Pre_Child_And_Output_Into_File(void) { int i,j,k,l,m,char_num_in_one_line = 0; double chromosome_segment_BW_value , spouse_segment_BW_value; int chromosome_1_bit_count,spouse_1_bit_count; double probability; time_t t; srand((unsigned) time(&t)); printf("Create %d pre-child of cross-over probability %g(nonequal) and %g(equal)...",pre_child_num,be_pre_child_segment_probability,be_pre_child_segment_probability_when_segment_BW_value_equal); for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ;j < pre_child_num ; j++) { l = 0; for(k = 0 ; k <= cutting_num ;k ++) { chromosome_segment_BW_value = spouse_segment_BW_value = 0.; chromosome_1_bit_count = spouse_1_bit_count = 0; int flag = l; probability = (double)((rand()%10000)+1) / 10000; if(probability <= 0.5) { if(k < cutting_num) { for(m = flag ;m <= cutting_index[i][j][k];m++) { pre_child_array[i][j][m] = chromosome[i][m]; } } else if(k == cutting_num) { for(m = flag ;m < gene_size;m++) { pre_child_array[i][j][m] = chromosome[i][m]; } } } else if(probability > 0.5) { if(k < cutting_num) { for(m = flag ;m <= cutting_index[i][j][k];m++) { pre_child_array[i][j][m] = chromosome[spouse[i][j]][m]; } } else if(k == cutting_num) { for(m = flag ;m < gene_size;m++) { pre_child_array[i][j][m] = chromosome[spouse[i][j]][m]; } } } } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Create_Pre_Child_After_Mutation_And_Output_Into_File(void) { double temp; double temp1 = lower_bound_of_mutation_probability , temp2 = upper_bound_of_mutation_probability; int char_num = 0; int i,j,k; int temp_count; printf("Bits of every pre-child will mutate as 1 of probability %g∼%g......",temp1,temp2); time_t t; srand((unsigned) time(&t)); for(i = 0 ; i < chromosome_num ; i++) { for(j = 0 ; j < pre_child_num ; j++) { temp_count = 0; while(true) { for(k = 0 ; k < gene_size ; k++) { temp = (double)(rand()%10000+1) / 10000; if(temp > 0.05) { pre_child_array[i][j][k] = pre_child_array[i][j][k]; } else { if(pre_child_array[i][j][k] == 0) { pre_child_array[i][j][k] = 1; } else if(pre_child_array[i][j][k] == 1) { pre_child_array[i][j][k] = 0; } } } for(k = 0 ; k < gene_size ; k++) { temp_count = temp_count + pre_child_array[i][j][k]; } if(( temp_count < gene_size) && (temp_count != 0 )) { break; } } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Calculate_The_Total_Amount_Of_1_Bits_For_Every_Pre_Child(void) { printf("Calculate the total amount of 1 bits for every pre_child......"); for(int i = 0 ; i < chromosome_num ; i++) { for(int j = 0 ; j < pre_child_num ; j++) { count_array_for_the_total_amount_of_1_bits_of_every_pre_child[i][j] = 0; for(int k = 0 ; k < gene_size ; k++) { if(pre_child_array[i][j][k] == 1) count_array_for_the_total_amount_of_1_bits_of_every_pre_child[i][j]++; } } } printf("ok.\n"); } //------------------------------------------------------------------------------- void Generate_New_Generation_And_Output_Into_File(void) { if(generation > 3) printf("Generate the %dth new generation and output into files......",generation); else if(generation == 2) printf("Generate the %dnd new generation and output into files......",generation); else if(generation == 3) printf("Generate the %drd new generation and output into files......",generation); stop_threshold = 0.; average_fitness_value_in_some_generation = 0; for(int chromosome_index = 0 ; chromosome_index < chromosome_num ; chromosome_index++) { Change_Dimension_Base_On_Pre_Child(chromosome_index); //ok Calculate_All_Euclidean_Distance_For_Every_Sample(chromosome_index); //ok Sort_All_Euclidean_Distance_For_Every_Sample(chromosome_index); //ok Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor(chromosome_index); //ok Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor(chromosome_index); //ok Calculate_The_Coefficients_Of_Least_Square_Line(chromosome_index); //ok Calculate_The_Best_Fitness_Value_Of_Pre_Child_And_Output_Into_File(chromosome_index); //ok Replace_Or_Not(chromosome_index); } int max_fitness = 0; int i; for(i = 0 ; i < chromosome_num-1 ; i++ ) { if(fitness_value_of_chromosome[i+1] > fitness_value_of_chromosome[i]) { max_fitness = i+1; } } for(i = 0 ; i < gene_size ; i++) { sol_generation[i][generation-2] = chromosome[max_fitness][i]; } fprintf(average_fitness_value,"%lf\n",average_fitness_value_in_some_generation/chromosome_num); printf("\naverage fitness value : %lf\n",average_fitness_value_in_some_generation/chromosome_num); if(stop_threshold <= stop_threshold_value) { stop_generation++; } else { stop_generation = 0; } generation++; printf("ok.\n"); fprintf(threshold_file,"%lf\n",stop_threshold); printf("threshold value current=%lf , generation連續 = %d",stop_threshold,stop_generation); printf("\n-------------------------------------------------------------------------------\n"); exit(0); } //------------------------------------------------------------------------------- void Change_Dimension_Base_On_Pre_Child(int chromosome_index) { int i,j,k,temp; double t = 0.; for(i = 0 ; i < pre_child_num ; i++) { temp = 0; for(j = 0 ; j < gene_size ; j++) { if(pre_child_array[chromosome_index][i][j] == 1) { for(k = 0 ; k < sample_size ; k++) { change_dim_base_on_pre_child[i][k][temp] = raw_data_array[j][k]; /*if((chromosome_index+1) == 3 && (i+1) == 3 && (k+1) == 3) { fprintf(debug_file,"chromosome=%d pre_child=%d sample=%d gene=%d value=%lf \n",(chromosome_index+1),(i+1),(k+1),(j+1),change_dim_base_on_pre_child[i][k][temp]); fprintf(debug_file,"chromosome=%d pre_child=%d sample=%d gene=%d value=%lf \n",(chromosome_index+1),(i+1),(k),(j+1),change_dim_base_on_pre_child[i][k-1][temp]); t = t + (change_dim_base_on_pre_child[i][k-1][temp]-change_dim_base_on_pre_child[i][k][temp])*(change_dim_base_on_pre_child[i][k-1][temp]-change_dim_base_on_pre_child[i][k][temp]); }*/ } temp++; //if((chromosome_index+1) == 3 && (i+1) == 3 && (k+1) == 3) // fprintf(debug_file,"----------------------------------------------------------------\n"); } } } //fprintf(debug_file,"%lf\n",sqrt(t)); } //------------------------------------------------------------------------------- void Calculate_All_Euclidean_Distance_For_Every_Sample(int chromosome_index) { int i,j,k,m; double euclidean_distance,temp; for(i = 0 ; i < pre_child_num ; i++) { for(j = 0 ; j < sample_size ; j++) { for(k = 0 ; k < sample_size ; k++) { if(j < k) { euclidean_distance = 0.; for(m = 0 ; m < count_array_for_the_total_amount_of_1_bits_of_every_pre_child[chromosome_index][i] ; m++) { temp = ((change_dim_base_on_pre_child[i][j][m] - change_dim_base_on_pre_child[i][k][m])*(change_dim_base_on_pre_child[i][j][m] - change_dim_base_on_pre_child[i][k][m])); euclidean_distance = euclidean_distance + temp; } euclidean_distance = sqrt(euclidean_distance); original_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k] = euclidean_distance; } else if(j > k) { original_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k] = original_euclidean_distance_for_every_sample_in_every_pre_child[i][k][j]; } else { original_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k] = 0.; } //if((chromosome_index+1) == 3 && (i+1) == 3) // fprintf(debug_file2,"%15lf ",original_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k]); } //if((chromosome_index+1) == 3 && (i+1) == 3) // fprintf(debug_file2,"\n"); } } } //------------------------------------------------------------------------------- void Sort_All_Euclidean_Distance_For_Every_Sample(int chromosome_index) { //double temp; int i,j,k; for(i = 0 ; i < pre_child_num ; i++) { for(j = 0 ; j < sample_size ; j++) { for(k = 0 ; k < sample_size ; k++) { sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k] = original_euclidean_distance_for_every_sample_in_every_pre_child[i][j][k]; } } } for(i = 0 ; i < pre_child_num ; i++) { for(j = 0 ; j < sample_size ; j++) { QuickSort(sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][j],0,sample_size-1); } } /*if((chromosome_index+1) ==3) { for(i = 0 ; i < sample_size ; i++) { temp = 0.; for(j = 0 ; j < sample_size ; j++) { temp = temp + (sorted_euclidean_distance_for_every_sample_in_every_pre_child[2][j][i]*sorted_euclidean_distance_for_every_sample_in_every_pre_child[2][j][i]); } fprintf(debug_file3,"%15lf ",temp); } }*/ } //------------------------------------------------------------------------------- void Calculate_The_Average_Euclidean_Distance_Value_For_Different_Nearest_Neighbor(int chromosome_index) { double temp; if(range_of_nearest_neighbor_num < sample_size) { for(int i = 0 ; i < pre_child_num ; i++) { for(int j = 1 ; j <= range_of_nearest_neighbor_num ; j++) { if(default_KNN_manner == 2) { temp = 0.; for(int k = 1 ; k <= j ; k++) { for(int m = 0 ; m < sample_size ; m++) { temp = temp + (sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][k]*sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][k]); } } average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j-1] = temp / (sample_size * j); } else if(default_KNN_manner == 1) { temp = 0.; for(int m = 0 ; m < sample_size ; m++) { temp = temp + (sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][j]*sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][j]); } average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j-1] = temp / sample_size; } } } } else if(range_of_nearest_neighbor_num >= sample_size) { printf("ERROR：No enough neighbor.\n"); } } //------------------------------------------------------------------------------- void Calculate_The_Average_Pattern_Type_Value_For_Different_Nearest_Neighbor(int chromosome_index) { double temp; int i,j,k,m,n; if(range_of_nearest_neighbor_num < sample_size) { for(i = 0 ; i < pre_child_num ; i++) { for(j = 1 ; j <= range_of_nearest_neighbor_num ; j++) { if(default_KNN_manner == 1) { temp = 0.; for(m = 0 ; m < sample_size ; m++) { for(n = 0 ; n < sample_size ; n++) { if(original_euclidean_distance_for_every_sample_in_every_pre_child[i][m][n] == sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][j]) break; } temp = temp + ((pattern_type_array[n] - pattern_type_array[m]) * (pattern_type_array[n] - pattern_type_array[m])); } average_pattern_type_value_for_different_nearest_neighbor_value[i][j-1] = temp / (sample_size * 2); } else if(default_KNN_manner == 2) { temp = 0.; for(k = 1 ; k <= j ; k++) { for(m = 0 ; m < sample_size ; m++) { for(n = 0 ; n < sample_size ; n++) { if(original_euclidean_distance_for_every_sample_in_every_pre_child[i][m][n] == sorted_euclidean_distance_for_every_sample_in_every_pre_child[i][m][k]) break; } temp = temp + ((pattern_type_array[n] - pattern_type_array[m]) * (pattern_type_array[n] - pattern_type_array[m])); } } average_pattern_type_value_for_different_nearest_neighbor_value[i][j-1] = temp / ((sample_size * 2) * j); } } } } else if(range_of_nearest_neighbor_num >= sample_size) { printf("ERROR：No enough neighbor.\n"); } } //------------------------------------------------------------------------------- void Calculate_The_Coefficients_Of_Least_Square_Line(int chromosome_index) { int i,j,n = range_of_nearest_neighbor_num; double sigma_x,sigma_y,sigma_x_pow_two,sigma_xy,average_x,average_y; for(i =0 ; i < pre_child_num ; i++) { if(default_least_square_line_manner == 1) { sigma_x = sigma_y = sigma_x_pow_two = sigma_xy = average_x = average_y =0.; for(j = 0 ; j < range_of_nearest_neighbor_num ; j++) { sigma_x = sigma_x + average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]; sigma_y = sigma_y + average_pattern_type_value_for_different_nearest_neighbor_value[i][j]; sigma_x_pow_two = sigma_x_pow_two + (average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]*average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]); sigma_xy = sigma_xy + (average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]*average_pattern_type_value_for_different_nearest_neighbor_value[i][j]); } average_y = sigma_y / n; average_x = sigma_x / n; //m coefficients_of_least_square_line[i][0] = ( sigma_xy - (average_y*sigma_x) - (average_x*sigma_y) + ( n * average_x * average_y) ) / (sigma_x_pow_two - ( 2 * average_x * sigma_x ) + (n * (average_x*average_x) ) ); //b coefficients_of_least_square_line[i][1] = average_y - (coefficients_of_least_square_line[i][0]*average_x); } else if(default_least_square_line_manner == 2) { sigma_x = sigma_y = sigma_x_pow_two = sigma_xy = 0.; for(j = 0 ; j < range_of_nearest_neighbor_num ; j++) { sigma_x = sigma_x + average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]; sigma_y = sigma_y + average_pattern_type_value_for_different_nearest_neighbor_value[i][j]; sigma_x_pow_two = sigma_x_pow_two + (average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]*average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]); sigma_xy = sigma_xy + (average_euclidean_distance_value_for_different_nearest_neighbor_value[i][j]*average_pattern_type_value_for_different_nearest_neighbor_value[i][j]); } // y = mx + b //m coefficients_of_least_square_line[i][0] = ((n*sigma_xy)-(sigma_x*sigma_y))/((n*sigma_x_pow_two)-(sigma_x*sigma_x)); //b coefficients_of_least_square_line[i][1] = ((sigma_y*sigma_x_pow_two)-(sigma_x*sigma_xy))/((n*sigma_x_pow_two)-(sigma_x*sigma_x)); } /*if(generation == 2) fprintf(line,"chromosome : %d pre_child : %d => m = %lf , b = %lf\n",chromosome_index+1,i+1,coefficients_of_least_square_line[i][0],coefficients_of_least_square_line[i][1]); */ if(coefficients_of_least_square_line[i][1] < 0) coefficients_of_least_square_line[i][1] = -(coefficients_of_least_square_line[i][1]); } //if(generation == 2) // fprintf(line,"\n=================================================\n"); } //------------------------------------------------------------------------------- void Calculate_The_Best_Fitness_Value_Of_Pre_Child_And_Output_Into_File(int chromosome_index) { int i,j,k,count; double pearson_sum = 0; for(i = 0 ; i < pre_child_num ; i++) { fitness_value_of_pre_child[i] = 1 / (1 + exp(coefficients_of_least_square_line[i][1])); if(default_fitness_calculation == 1) { if(with_correlation_concept == 1) { count = 0; pearson_sum = 0; for(j = 0 ; j < gene_size ; j++) { temp_count_ary_2[j] = -1; if(pre_child_array[chromosome_index][i][j] == 1) { temp_count_ary_2[count] = j; count++; } } for(j = 0 ; j < count ; j++) { for(k = j+1 ; k < count ; k++) { pearson_sum = pearson_sum + pearson_matrix[temp_count_ary_2[j]][temp_count_ary_2[k]]; } } if(correlation_location == 1) { fitness_value_of_pre_child[i] = fitness_value_of_pre_child[i] + (pearson_sum / (0.5*((count*count)-count))); } else if(correlation_location == 2) { fitness_value_of_pre_child[i] = (fitness_value_of_pre_child[i] / (pearson_sum / (0.5*((count*count)-count)))); } } } else if(default_fitness_calculation == 2) { fitness_value_of_pre_child[i] = (fitness_value_of_pre_child[i] / count_array_for_the_total_amount_of_1_bits_of_every_pre_child[chromosome_index][i]); } } index_of_best_pre_child = 0; best_fitness_value_of_pre_child = fitness_value_of_pre_child[0]; for(i = 0 ; i < pre_child_num ; i++) { if(fitness_value_of_pre_child[i] >= best_fitness_value_of_pre_child) { index_of_best_pre_child = i; best_fitness_value_of_pre_child = fitness_value_of_pre_child[i]; } } } //------------------------------------------------------------------------------- void Replace_Or_Not(int chromosome_index) { int chromosome_count = 0,pre_child_count = 0; int i; for(i = 0 ; i < gene_size ; i++) { if(chromosome[chromosome_index][i] == 1) chromosome_count++; if(pre_child_array[chromosome_index][index_of_best_pre_child][i] == 1) pre_child_count++; } printf("\n\ndad's 1 bits:%d\tbest_sun's 1 bits:%d\ndad's fitness:%lf\tbest_sun's fitness:%lf\n",chromosome_count,pre_child_count,fitness_value_of_chromosome[chromosome_index],best_fitness_value_of_pre_child); /*if(generation == 2) { fprintf(debug_file,"%d\t%lf\n",chromosome_count,fitness_value_of_chromosome[chromosome_index]); } else if(generation == 3) { fclose(debug_file); }*/ if(fitness_value_of_chromosome[chromosome_index] < best_fitness_value_of_pre_child) { if( (pre_child_count <= chromosome_count) || ((best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / (pre_child_count-chromosome_count)) >= replace_threshold) { if( (pre_child_count <= chromosome_count) && ((best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / (pre_child_count-chromosome_count)) >= replace_threshold) { printf("Replaced!!! Because replace_value = %lf >= replace_threshold:%lf\n",(best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / (pre_child_count-chromosome_count),replace_threshold); printf(" and best_sun's size %d <= dad's size %d\n\n",pre_child_count,chromosome_count); } else if( (best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / (pre_child_count-chromosome_count) >= replace_threshold ) { printf("Replaced!!! Because replace_value = %lf >= replace_threshold:%lf\n\n",(best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / (pre_child_count-chromosome_count),replace_threshold); } else if(pre_child_count <= chromosome_count) { printf("Replaced!!! Because best_sun's size %d <= dad's size %d\n\n",pre_child_count,chromosome_count); } stop_threshold = stop_threshold + ((best_fitness_value_of_pre_child - fitness_value_of_chromosome[chromosome_index]) / fitness_value_of_chromosome[chromosome_index]); fitness_value_of_chromosome[chromosome_index] = best_fitness_value_of_pre_child; for(i = 0 ; i < gene_size ; i++) { chromosome[chromosome_index][i] = pre_child_array[chromosome_index][index_of_best_pre_child][i]; } } } else { printf("No Replacement!!!\n\n"); } average_fitness_value_in_some_generation = average_fitness_value_in_some_generation + fitness_value_of_chromosome[chromosome_index]; exit(0); } //------------------------------------------------------------------------------- void Swap ( double data[] , int i , int j ) { double temp; temp = data[i]; data[i] = data[j]; data[j] = temp; } //------------------------------------------------------------------------------- int Partition ( double data[] , int left , int right ) { int i,j; double pivot; pivot = data[left]; i = left; j = right+1; for( ; ; ) { while((data[++i] < pivot) && (i <= right)); while((data[--j] > pivot) && (j >= left)); if(i >= j) { break; } Swap(data,i,j); } Swap(data,j,left); return j; } //------------------------------------------------------------------------------- void QuickSort ( double data[] , int left , int right ) { int i; if(right > left) { i = Partition(data,left,right); QuickSort(data,left,i-1); QuickSort(data,i+1,right); } } //------------------------------------------------------------------------------- double Similarity(int _chromosome,int spouse) //calculate the value of similarity of two chromosome { double temp = 0.; for(int i=0;i fitness_value_of_chromosome[i-1]) && (i>0)) best_chromosome = i; } counter = 0; for(i = 0 ; i < gene_size_original ; i++) { if((rank_index_of_BW_value_for_every_gene_temp[i]+1) > (gene_size_original - MAX_Size)) { fprintf(solution_file,"%d\n",chromosome[best_chromosome][counter]); counter++; } else { fprintf(solution_file,"0\n"); } } for(i = 0 ; i < gene_size ; i++) { if(chromosome[best_chromosome][i] == 1) { selected_genes++; } } } else if(with_frequency == 2) //with frequencies concept { int *frequency; frequency = new int[gene_size]; for(i = 0 ; i < gene_size ; i++) { frequency[i] = 0; } for(i = 0 ; i < gene_size ; i++) { for(int j = 0 ; j < chromosome_num ; j++) { if(chromosome[j][i] == 1) { frequency[i]++; } } } int sum_freq = 0; double average_freq = 0; double std_freq = 0; double *z_score; z_score = new double[gene_size]; for(i = 0 ; i < gene_size ; i++) { z_score[i] = 0.; } for(i = 0 ; i < gene_size ; i++) { sum_freq = sum_freq + frequency[i]; } average_freq = sum_freq / gene_size; for(i = 0 ; i < gene_size ; i++) { std_freq = std_freq + ((frequency[i] - average_freq) * (frequency[i] - average_freq)); } std_freq = std_freq / (gene_size-1); std_freq = sqrt(std_freq); for(i = 0 ; i < gene_size ; i++) { z_score[i] = (frequency[i] - average_freq) / std_freq; } fprintf(debug_file,"average_freq = %lf , std_freq = %lf\n\n\n",average_freq,std_freq); for(i = 0 ; i < gene_size ; i++) { fprintf(debug_file,"gene %d => frequency : %d z_score : %lf\n",i+1,frequency[i],z_score[i]); } fclose(debug_file); for(i = 0 ; i < gene_size ; i++) { if(z_score[i] > z_score_value) { frequency[i] = 1; } else { frequency[i] = 0; } } counter = 0; for(i = 0 ; i < gene_size_original ; i++) { if((rank_index_of_BW_value_for_every_gene_temp[i]+1) > (gene_size_original - MAX_Size)) { fprintf(solution_file,"%d\n",frequency[counter]); counter++; } else { fprintf(solution_file,"0\n"); } } for(i = 0 ; i < gene_size ; i++) { if(frequency[i] == 1) { selected_genes++; } } } fclose(solution_file); } //------------------------------------------------------------------------------- void Write_Information_File(void) { fprintf(information,"Generation : %d\n",generation-1); fprintf(information,"Selected genes : %d (total:%d)\n",selected_genes,gene_size_original); fprintf(information,"file_name_length : %d\n",file_name_length); fprintf(information,"pattern_type_num : %d\n",pattern_type_num); fprintf(information,"chromosome_num : %d\n",chromosome_num); fprintf(information,"default_similarity_method(1:by阿寬法,2:by直覺法) : %d\n",default_similarity_method); fprintf(information,"default_selection_manner(1:只與一個媽媽交配就生所有的pre-child,2:每一個pre-child都是與不同之媽媽所生) : %d\n",default_selection_manner); fprintf(information,"default_KNN_manner(1:p即表示「第p」的鄰居,2:p表示「第1到第p」的鄰居) : %d\n",default_KNN_manner); fprintf(information,"default_least_square_line_manner(1:from puppy學姐的書,2:from網路) : %d\n",default_least_square_line_manner); fprintf(information,"default_fitness_calculation(1:不除以1 bits的個數,2:除以1 bits的個數) : %d\n",default_fitness_calculation); fprintf(information,"default_random_manner(1:先random 1 bits共有的個數,然後再random決定放那裡,2:先random產生一個1~32767的整數，然後再轉成0與1的string) : %d\n",default_random_manner); fprintf(information,"with_frequency(1:without frequency,2:with frequency) : %d\n",with_frequency); fprintf(information,"with_correlation_concept : %d\n",with_correlation_concept); fprintf(information,"pre_child_num : %d\n",pre_child_num); fprintf(information,"cutting_num : %d\n",cutting_num); fprintf(information,"be_pre_child_segment_probability : %f\n",be_pre_child_segment_probability); fprintf(information,"be_pre_child_segment_probability_when_segment_BW_value_equal : %f\n",be_pre_child_segment_probability_when_segment_BW_value_equal); fprintf(information,"lower_bound_of_mutation_probability : %f\n",lower_bound_of_mutation_probability); fprintf(information,"upper_bound_of_mutation_probability : %f\n",upper_bound_of_mutation_probability); fprintf(information,"range_of_nearest_neighbor_num : %d\n",range_of_nearest_neighbor_num); fprintf(information,"stop_threshold_value : %f\n",stop_threshold_value); fprintf(information,"stop_generation_value : %f\n",stop_generation_value); fprintf(information,"replace_threshold : %lf\n",replace_threshold); fprintf(information,"MAX_Size : %d\n",MAX_Size); fprintf(information,"z_score_value : %f\n",z_score_value); fprintf(information,"correlation_location : %d\n",correlation_location); fclose(information); }