An example of genetic algorithm (C / C )
Author: newsuppy
Abstract: The M works are allocated to the maximum optimization problem of the M frame machine, and use a genetic algorithm to solve.
First, the Benefits Matrix E
EIJ
M1
M2
M3
M4
M5
J1
5
6
4
8
3
J2
6
4
9
8
5
J3
4
3
2
5
4
Jet
Seduce
2
4
5
3
J5
3
6
4
5
5
JN is a workpiece, Mn is a machine, a matrix, a piece of a workpiece assigned to a machine. Benefits spend time, money, etc., the larger the value, the larger the value. Generate a distribution sequence c = (5, 2, 3, 4, 4) refers to the distribution of the No. 1 installation to No. 1 machine, and the workpiece is allocated to the machine bed, and the currently allocation corresponding to the current distribution is 3 . 4 2 5 3 = 17. The optimization problem is to request a distribution sequence corresponding to the maximum value. Next, a genetic algorithm is used, and the specific algorithm is not repeated here, and [1] or other related books can be referenced. It is important to note that since the workpiece and the machine tool are in one, the algorithm is different from some of the common genetic algorithms, such as chromosome encoding, in place, and variation.
Below is an algorithm implementation. For some reason, C / C mixed coding has to be used, and the C code is mainly in the file input and output section. In addition, let the program run normal to include several support files (with the same path):
Benefit.txt input benefit matrix
Num_of_gen.txt finalized procedure
Numofcolony.txt is the total number of individuals in the group
Numoftm.txt is the number of workpieces and the number of machine tools
The content can be as follows:
Benefit.txt
5 6 4 8 3
6 4 9 8 5
4 3 2 5 4
7 2 4 5 3
3 6 4 5 5
Num_of_ge.txt
50
Numofcolony.txt
10
Numoftm.txt
5
5
Note: Since the program is written comparison, the error handling is not considered, please ensure the correctness of the relevant files.
#include
#include
#include
#include
#include
#include
#include
Using namespace std;
Void generate_colony (int ** colony, int num_of_chromosomes, int num_of_job); // initial group generation
INT compute_benefit (int ** benefit_matrix, int * chromosome, int num_of_machine); // Evaluation of a single chromosome
Void Copy_chromosomes (int ** colony, int num_of_chromosomes, int num_of_job, int * benef_Array); // Copy
INT execute_probable (float probability); // Returns 1 or 0 in accordance with a certain probability
// The above function is implemented in the implementation of random numbers, which is unstrusted, and a uniform distributed random number generator should be used.
Void Exchange_gene (int * chromosome_first, int * chromosome_second, int num_of_job); / / exchange two chromosomes
Void Reverse_gene (int * chromosome, int num_of_job); // Implement a single chromosome in place vid gene_mutate (int * chromosome, int Num_of_job); // Variation for a single chromosome
Void ERV_COLONY (int ** Colony, Float PE, Float PR, Float Pv, Int Num_OF_JOB, INT NUM_OF_CHROMOMES);
/ / Exchange, in place and variation on the group
int main ()
{
INT ** benefit_matrix = null; // efficiency matrix
INT NUM_OF_JOB; // number of workpieces
INT NUM_OF_MACHINE; / / number of machine tools
IFStream InputTM ("NumoftM.txt");
Inputtm >> Num_OF_JOB >> NUM_OF_MACHINE
INPUTTM.CLOSE ();
Benefit_matrix = (int **) malloc (sizeof (int *) * num_of_job);
For (INT i = 0; I { Benefit_matrix [i] = (int *) malloc (sizeof (int) * num_of_machine); } IFStream InputBenefit ("Benefit.txt"); For (INT i = 0; I { For (int J = 0; j { InputBenefit >> Benefit_matrix [i] [j]; } } INPUTBENEFIT.CLOSE (); / *************************************************** // Test for Inital Data's INPUT Cout << Num_of_job << '/ t' << Num_OF_MACHINE << ENDL; For (INT i = 0; I { For (int J = 0; j { COUT << Benefit_matrix [i] [j] << '/ t'; } Cout << '/ n'; } **************************************************** / INT NUM_OF_CHROMOMES; // Group IFStream InputCln ("Numofcolony.txt"); InputCln >> Num_Of_chromosomes; INPUTCLN.CLOSE (); Int ** colony = null; // group Colony = (int **) Malloc (INT *) * NUM_OF_CHROMOMES; For (int i = 0; i { Colony [I] = (int *) Malloc (intend * num_of_job); } SRAND (Time (0)); Generate_colony (colony, num_of_chromosomes, num_of_job); cout << "Origin colonies" << '/ n'; / ****************************************** / // Test for Genetare_colony For (int i = 0; i { For (int J = 0; j { COUT << Colony [i] [j] << '/ t'; } Cout << '/ n'; } / ******************************************** / INT * benefit_Array = NULL; // A number of benefits of each individual in group Benefit_Array = (int *) malloc (sizeof (int) * number_of_chromosomes); For (int i = 0; i { Benefit_Array [i] = compute_benefit (benefony [i], num_of_machine); } COUT << "current benefit" << '/ n' << "" mean: "<< (float) accumulate (benefit_array, benefit_array num_of_chromosomes, 0) / Num_Of_chromosomes << '/ t' << "MAX: << * Max_Element (benefit_ARRAY, Benefit_Array Num_OF_CHROMOMES << '/ t' << "" "" << * min_efit_array, benefit_Array Num_Of_chromosomes << '/ n'; INT NUM_OF_GEN; / / The algebra is generated, that is, the order of the last generation generated. IFSTREAM INPUTNG ("num_of_gen.txt"); Inputng >> Num_OF_Gen; INPUTNG.CLOSE (); Float probability_of_exchange = 0.7F ; FLOAT probability_of_reverse = 0.2F ; Float probability_of_mutate = 0.01F ; For (int i = 0; i { // Call the copy subroutine Copy_chromosomes (colony, num_of_chromosomes, num_of_job, benefit_array); ERV_COLONY (colony, probability_of_exchange, probability_of_reverse, probability_of_mutate, Num_of_job, num_of_chromosomes; // Recalculate the benefits of each individual For (int J = 0; j BENEFIT_ARRAY [J] = compute_benefit (Benefit_Matrix, Colony [J], Num_OF_MACHINE); } // This generation evaluation benefits COUT << "Current Gen:" << i 1 << '/ n' << "" mean: "<< (float) accumulate (benefit_array, benefit_array num_of_chromosomes, 0) / Num_Of_chromosomes << '/ t' << "MAX: << * Max_Element (benefit_ARRAY, Benefit_Array Num_OF_CHROMOMES << '/ t' << "" "" << * min_efit_array, benefit_Array Num_Of_chromosomes << '/ n'; } COUT << "Laster colony" << '/ n'; For (int i = 0; i { For (int J = 0; j { COUT << Colony [i] [j] << '/ t'; } Cout << '/ n'; } // free all resource For (INT i = 0; I { Free (benefit_matrix [i]); } Free (benefit_matrix); For (int i = 0; i { Free (colony [i]); } Free (colony); Free (benefit_Array); System ("pause"); } Void generate_colony (int ** colony, int num_of_chromosomes, int num_of_job) { INT * Initial_Array = (int *) Malloc (intend * num_of_job); For (INT i = 0; I { Initial_Array [i] = i 1; } For (int i = 0; i { Random_shuffle (Initial_Array, Initial_Array Num_OF_JOB); COPY (Initial_Array, Initial_Array Num_OF_JOB, Colony [i]); } Free (Initial_Array); } INT compute_benefit (int ** benefit_matrix, int * chromosome, int num_of_machine) { INT benefit = 0; For (int i = 0; i BENEFIT = Benefit_matrix [chromosome [i] -1] [i]; } Return benefit; } Void Copy_chromosomes (int ** colony, int num_of_chromosomes, int num_of_job, int * benefit_Array) { INT I, J; INT * NEXT_GEN_RESERVE; // Various individuals in future generations INT hascopyed = 0; / / Prevent replication number exceeding the total number of groups INT ** TEMP_COLONY; // Temporary group Float mean, max_benefit, min_benefit; Float big_separator, small_separator; Mean = (float) Accumulate (benefit_array, benefit_array num_of_chromosomes, 0) / (float) Num_of_chromosomes MAX_BENEFIT = * max_efit_array, benefit_array num_of_chromosomes; MIN_BENEFIT = * min_efit_array, benef_array num_of_chromosomes; Big_separator = max_benefit - (MAX_BENEFIT-MEAN) / 2; Small_separator = min_benefit (mean-min_benefit) / 2; Temp_colony = (int **) Malloc (INT *) * NUM_OF_CHROMOMES; For (i = 0; i { Temp_colony [i] = (int *) malloc (sizeof (int) * num_of_job); } // Copy the temporary group For (i = 0; i { For (j = 0; j { Temp_colony [i] [j] = colony [i] [j]; } } NEXT_GEN_RESERVE = (int *) Malloc (sizeof (int) * num_of_chromosomes); / / Calculate the individual contribution and perform parameters round For (i = 0; i { IF (benefit_Array [i]> = big_separator) Next_gen_reserve [i] = 0; Else IF (benefit_Array [i] <= small_separator) NEXT_GEN_RESERVE [I] = 2; Else Next_gen_reserve [i] = 1; } For (i = 0; i { For (j = 0; j { IF (HASCOPYED> = Num_Of_chromosomes) { I = NUM_OF_CHROMOMOMES; Break; } Memcpy (Colony [Hascopyed], Temp_Colony [I], SIZEOF (Colony [0] [0]) * NUM_OF_JOB); Hascopyed; } } For (i = 0; i { Free (temp_colony [i]); } Free (temp_colony); Free (next_gen_reserve); } Int Execute_PROBLY (Float Probability) { IF (probability> 1.0) Return 1; Else IF (probability <= 0.0) Return 0; Else { INT rNDNUM = rand ()% 1000; IF (RNDNUM <(int) (Probability * 1000.0)) Return 1; Else Return 0; } } Void Exchange_gene (int * chromosome_first, int * chromosome_second, int num_of_job) { INT Exchange_pos; // Exchange RAM INT * DERIVED_FIRST, * Derived_second; // Temporary storage of two new children after exchange INT I, J, K; INT is_equal; Exchange_pos = rand ()% Num_OF_JOB; Derived_first = (int *) malloc (intend * num_of_job); Derived_second = (int *) malloc (sizeof (int) * number_of_job); / / Copy the gene before switching Memcpy (Derived_first, chromosome_first, sizeof (int) * (1 exchange_pos)); Memcpy (Derived_second, chromosome_second, sizeof (int) * (1 Exchange_pos)); // Generate the first child by two parents K = Exchange_POS 1; For (i = 0; i { IS_EQUAL = 0; For (j = 0; j <= Exchange_pos; J) { IF (chromosome_second [i] == chromosome_first [j]) { IS_EQUAL = 1; Break; } } IF (IS_EQUAL == 0) { Derived_first [k] = chromosome_second [i]; K; } } // Generate a second child by two parents K = Exchange_POS 1; For (i = 0; i { IS_EQUAL = 0; For (j = 0; j <= Exchange_pos; J) { IF (chromosome_first [i] == chromosome_second [j]) { IS_EQUAL = 1; Break; } } IF (IS_EQUAL == 0) { Derived_second [k] = chromosome_first [i]; K; } } // Cover the original parent Memcpy (chromosome_first, derived_first, sizeof (int) * number_of_job); memcpy (chromosome_second, derived_second, sizeof (int) * num_of_job); Free (derived_first); Free (derived_second); } Void Reverse_gene (int * chromosome, int num_of_job) { INT first_REV_POS; // First retrore point INT Second_rev_pos; // Second Reverse site INT I, DISTANCE; Int temp; First_REV_POS = RAND ()% Num_OF_JOB; Second_rev_pos = rand ()% (NUM_OF_JOB-FIRST_REV_POS) First_REV_POS; Distance = (Second_rev_pos - first_rev_pos) / 2; For (i = 0; i <= distance; i) { Temp = chromosome [first_rev_pos i]; Chromosome [first_rev_pos i] = chromosome [second_rev_pos-i]; Chromosome [Second_REV_POS-I] = TEMP; } } Void gene_mutate (int * chromosome, int num_of_job) { INT MUTATE_POS; // Variation INT mutate_value; // After the change gene value INT EX_POS; / / Switching point with variant point INT I; MUTATE_POS = RAND ()% NUM_OF_JOB; MUTATE_VALUE = RAND ()% NUM_OF_JOB 1; For (i = 0; i { IF (chromosome [i] == mutate_value) { EX_POS = i; Break; } } i = chromosome [ex_pos]; Chromosome [EX_POS] = chromosome [MUTATE_POS]; Chromosome [MUTATE_POS] = i; } Void ERV_COLONY (int ** Colony, Float PE, FLOAT PR, FLOAT PV, INT NUM_OF_JOB, INT NUM_OF_CHROMOMES) { int ** TMP_COLONY; INT I; INT first, second; TMP_COLONY = (int **) Malloc (INT *) * NUM_OF_CHROMOMES; For (i = 0; i { TMP_COLONY [I] = (int *) malloc (sizeof (int) * number_of_job); } // COPY For (i = 0; i { Memcpy (TMP_COLONY [I], Colony [i], sizeof (int) * num_of_job); } For (i = 0; i First = rand ()% Num_Of_chromosomes; While (1) { Second = rand ()% Num_Of_chromosomes; IF (first! = second) Break; } Memcpy (Colony [i], tmp_colony [first], sizeof (int) * num_of_job); Memcpy (Colony [i 1], TMP_COLONY [SECOND], SIZEOF (INT) * NUM_OF_JOB); IF (Execute_PROBABLY (PE)) Exchange_gene (Colony [I], Colony [i 1], NUM_OF_JOB); IF (Execute_Probable (PR)) { Reverse_gene (Colony [i], NUM_OF_JOB); Reverse_gene (Colony [i 1], NUM_OF_JOB); } IF (Execute_PROBABLY (PV)) { Gene_mutate (Colony [i], NUM_OF_JOB); Gene_mutate (Colony [i 1], NUM_OF_JOB); } } // free all resource For (int i = 0; i { Free (TMP_COLONY [I]); } Free (TMP_COLONY); } Below is a result of program compilation operation (already in VC7.1, DEV-C 4.9.8 .0 compiled and test it). Output is the average effectiveness of the initial group, 0 to 50th generation (mean) Worst (Max), best benefits (min). Finally, it is the allocation of the last generation group. Since the initial sequence is randomly generated, and the general genetic algorithm often has difficult to converge to the best solution, this program sometimes cannot converge to the best solution. But as long as you run a few more times, you can get the best solution. Best Distribution Sequence: 5 2 3 4 1, at this time, the benefit is 17 Origin colonies 5 3 2 4 1 5 2 1 4 3 2 5 4 1 3 2 3 5 4 1 1 2 4 5 3 1 3 2 4 5 5 4 3 2 1 3 1 4 2 5 5 3 4 1 2 5 1 3 4 2 Current benefit Mean: 23 Max: 28 min: 18 Current Gen: 1 Mean: 21.8 Max: 29 min: 18 Current Gen: 2 Mean: 19.7 Max: 23 min: 18 CURRENT GEN: 3 Mean: 19.8 Max: 24 min: 17 Current Gen: 4 Mean: 18.4 Max: 21 min: 17 Current Gen: 5 Mean: 18.2 Max: 21 min: 17 Current Gen: 6 Mean: 17.4 Max: 18 min: 17 Current Gen: 7mean: 17.8 Max: 22 min: 17 Current Gen: 8 Mean: 17.2 Max: 18 min: 17 Current Gen: 9 Mean: 17 MAX: 17 min: 17 CURRENT GEN: 10 Mean: 17.3 Max: 20 min: 17 Current Gen: 11 Mean: 17 MAX: 17 min: 17 CURRENT GEN: 12 Mean: 17.3 Max: 20 min: 17 Current Gen: 13 Mean: 18.8 Max: 27 min: 17 Current Gen: 14 Mean: 17.6 Max: 23 min: 17 Current Gen: 15 Mean: 17.5 Max: 20 min: 17 Current Gen: 16 Mean: 18.2 Max: 23 min: 17 Current Gen: 17 Mean: 17.5 Max: 22 min: 17 Current Gen: 18 Mean: 17 MAX: 17 min: 17 Current Gen: 19 Mean: 17 MAX: 17 min: 17 Current Gen: 20 Mean: 17.5 Max: 22 min: 17 Current Gen: 21 Mean: 17.6 Max: 20 min: 17 Current Gen: 22 Mean: 17 MAX: 17 min: 17 Current Gen: 23 Mean: 17.8 Max: 22 min: 17 Current Gen: 24 Mean: 17.6 Max: 23 min: 17 Current Gen: 25 Mean: 17.5 Max: 22 min: 17 Current Gen: 26 Mean: 17 MAX: 17 min: 17 Current Gen: 27 Mean: 17 MAX: 17 min: 17 Current Gen: 28 Mean: 17 MAX: 17 min: 17 Current Gen: 29 Mean: 17 MAX: 17 min: 17 Current Gen: 30 Mean: 18.1 Max: 22 min: 17 Current Gen: 31 Mean: 17.8 Max: 20 min: 17 Current Gen: 32 Mean: 17 MAX: 17 min: 17 Current Gen: 33 Mean: 17.6 Max: 23 min: 17 Current Gen: 34 Mean: 17.3 Max: 20 min: 17 Current Gen: 35 Mean: 17 MAX: 17 min: 17 Current Gen: 36 Mean: 17 MAX: 17 min: 17 Current Gen: 37 Mean: 17 MAX: 17 min: 17 Current Gen: 38 Mean: 17 MAX: 17 min: 17 Current Gen: 39 Mean: 18.1 Max: 23 min: 17 Current Gen: 40 Mean: 17.3 Max: 20 min: 17 Current Gen: 41 Mean: 17 MAX: 17 min: 17 Current Gen: 42 Mean: 17 Max: 17 min: 17 Current Gen: 43 Mean: 17 MAX: 17 min: 17 Current Gen: 44 Mean: 17.5 Max: 22 min: 17 Current Gen: 45 Mean: 17 MAX: 17 min: 17 Current Gen: 46 Mean: 18.3 Max: 27 min: 17 Current Gen: 47 Mean: 17.9 Max: 20 min: 17 Current Gen: 48 Mean: 17 MAX: 17 min: 17 Current Gen: 49 Mean: 17 MAX: 17 min: 17 Current Gen: 50 Mean: 17 MAX: 17 min: 17 Laster colony 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 5 2 3 4 1 references: [1] Computer Integrated Manufacturing System Editor Yan Xinmin Northwestern Practitioner Press P110-P114
