Solving Integer Programming Problems Using Genetic Algorithms
Fabrício Olivetti de França
Fabrício Olivetti de França
The first thing to concern about when coding an GA is the codification, or chromosome, of each individual. If we are dealing with integers, the most efficient way to code it is using an array of bits, making the crossover operation more "active” (this way we can generate new numbers each time we use it, if we had an array of integers we would just swap the numbers among parents, not building new ones), we will get on that later.For now let’s face a bigger problem: "how long should my array be?”. Remember that we must be sure to fit the values to reach the global maximum. To solve this question, let’s take a look at the constraints:
T1A + T2A + T3A <= 550 T1B + T2B + T3B <= 700 T1A + T1B <= 390 T2A + T2B <= 460 T3A + T3B <= 370
If we take a variable and "zero” the others we can take a maximum allowed value for this. Let’s take the T1A variable as an example:
T1A + 0 + 0 <= 550 T1A + 0 <= 390
From this we can see that T1A can be no more than 390, now, as we’re going to treat it like a binary number, let’s see how many digits we must use for it:390 in binary is 110000110 which has 9 bits, so our first variable will occupy the first 9 indexes of the array.
| Random Tip:Like good mathematicians that we are, we can deduce a simple formula to calculate how much bits we must use. Let x be the number of bits used to represent ‘y’. So we have 2^x = y, logging both sides, we have x*log2 = logy and then x = logy/log2, since we can won't have an exact solution most of the time, we must always round up x (we better play with a larger search space than lacking some possible good points). |
Calculating the bits for the others variables we get:
T1A = T1B = T2A = T2B = T3A = T3B = 9 bits
So we need an array of 9*6 bits = 54 bits total.An individual can be represented only by its chromosome, but to avoid some wasteful calculations we put together two other information: fitness, which gives each individual a "score”, and prob, which represents the probability to be chosen for breeding or to live. So our first code starts here:
------- galib.h --------- /* BITS used by each variable */ #define T1A_BITS 9 #define T1B_BITS 9 #define T2A_BITS 9 #define T2B_BITS 9 #define T3A_BITS 9 #define T3B_BITS 9 /* Total bits */ #define BITS T1A_BITS + T1B_BITS + T2A_BITS + T2B_BITS + T3A_BITS + T3B_BITS /* How we represent each individual, with its chromossome, its fitness, and its probability */ typedef struct crom{ char cromo[BITS]; long int fitness; int prob; } crom; --------- cut here -----------
Here we define the bits used for each variable, the total bits of an individual, and the structure in which we’ll hold all the info about it.
Well, having defined how each individual is represented we must create a function that will show us what does this representation means (i.e. transform a bit array into an array of 6 integers numbers). This function will have the chromosome and a pointer to an array of size n (number of variables) passed as parameters, so we can decode the bits as decimal numbers. We will have something like this:
--------- galib.c ----------- void decode(crom indv, int vars[]){ int i,j; /* initialize the variables */ vars[0] = 0; vars[1] = 0; vars[2] = 0; vars[3] = 0; vars[4] = 0; vars[5] = 0; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Let's walk the first 9 bits (T1A) from left to right: * * 2^8 + 2^7 + ... + 2^0 * * so, for i = 0 to 9 we use the formula: bit*2^(BITS-1-i) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ for(i=0;i<T1A_BITS;i++){ vars[0] += indv.cromo[i]*(int)pow(2, T1A_BITS -1-i); } /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Here 'i' already starts as 9 from the above loop, * * let's make different this time, let's initialize * * j to BITS-1 (8) and decrement it until it's less than 0, * * and keep incrementing i to keep going all variables * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ for(j=T1B_BITS-1;j>=0;i++,--j){ vars[1] += indv.cromo[i]*(int)pow(2,j); } /* and so on ... */ for(j=T2A_BITS-1;j>=0;i++,--j){ vars[2] += indv.cromo[i]*(int)pow(2,j); } for(j=T2B_BITS-1;j>=0;i++,--j){ vars[3] += indv.cromo[i]*(int)pow(2,j); } for(j=T3A_BITS-1;j>=0;i++,--j){ vars[4] += indv.cromo[i]*(int)pow(2,j); } for(j=T3B_BITS-1;j>=0;i++,--j){ vars[5] += indv.cromo[i]*(int)pow(2,j); } } -------- cut here ------
Now we have the binary representation and its decoded values for an individual, we must now calculate its fitness so we can eval one by one in a population. First of all, let's calculate the function we want to maximize, the objective function:
----- insert into galib.c ------- long int object(int vals[]){ long int objt; int D_30, T, TA, TB, T1,T2,T3; /* Let's calculate some intermediate values */ TA = vals[0] + vals[1] + vals[2]; TB = vals[3] + vals[4] + vals[5]; T1 = vals[0] + vals[3]; T2 = vals[1] + vals[4]; T3 = vals[2] + vals[5]; T = TA + TB; /* D*300 = (T/10)*300 = 30*T so now we don't need to deal with float point numbers */ D_30 = 30*T; /* Now let's apply the objective function to it */ objt = D_30; objt -= (8*T1 + 3*T2 + 5*T3); objt -= (5*vals[0] + 9*vals[1] + 6*vals[2] + 6*vals[3] + 8*vals[4] + 7*vals[5]); objt -= (9*TA + 7*TB); return objt; } ------- cut here -------------
Wait a moment, you must be thinking, if we eval each individual through just the objective function, how we can guarantee that it will respect the constraints? Well, you’re right, we must avoid the solutions that break the constraints so we don’t get a wrong answer. To control it we have four options:
For this tutorial let’s focus on the penalty function, for it preserves those individuals who aren’t satisfactory but can generate a child that is. Just like we have a chance to preserve the worst individual in roulette selection to add diversity. There should be some experiments to decide which one is more effective, and even that can vary from problem to problem.The penalty function will be defined as "how much the value has passed from the constraint” multiplied by a constant rate to make the individual worse. So the more you get above the constraint less will be your fitness.Once we have 5 constraints, we will have 5 penalty functions, defined as:
----- insert into galib.c ------- long int penalty(int vals[]){ long int TA, TB, T1,T2,T3,P1,P2,P3,P4,P5,P; TA = vals[0] + vals[1] + vals[2]; TB = vals[3] + vals[4] + vals[5]; T1 = vals[0] + vals[3]; T2 = vals[1] + vals[4]; T3 = vals[2] + vals[5]; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * if (TA - 550) > 0 (the amount passed from constraint) * * the value returned will be: penalty rate * this diference * * else it will be 0, for it respected the constraints * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ P1 = ((TA - 550) > 0)?(RATE1*(TA-550)):0; P2 = ((TB - 700) > 0)?(RATE2*(TB-700)):0; P3 = ((T1 - 390) > 0)?(RATE3*(T1-390)):0; P4 = ((T2 - 460) > 0)?(RATE4*(T2-460)):0; P5 = ((T3 - 370) > 0)?(RATE5*(T3-370)):0; P = P1 + P2 + P3 + P4 + P5; return P; } ------- cut here -------------
the RATEn constants are defined in galib.h:
------insert into galib.h------- /* the rate for penalizing for each constraint unsatisfied */ #define RATE1 20 #define RATE2 20 #define RATE3 20 #define RATE4 20 #define RATE5 20 ------------cut here----------
Now that we have the objective function value and the penalties for not respecting the constraints we can say how good an individual is, or in GA, its fitness:
----- insert into galib.c ------- void evaluate(crom *cromo){ int vals[6]; long int objt; int P; /* let's get the real values of all variables */ decode((*cromo),vals); /* Now let's apply the objective function to it */ objt = object(vals); /* its penalty for not respecting our constraints */ P = penalty(vals); /* * * * * * * * * * * * * * * * * * * * * * * * * * * * Let's guarantee that the fitness will be always * * positive, because we don't want the objective * * function to give us negative results * * (or it wouldn't be profit, it'd be outlay). * * So if its penalty is too much much, let's zero * * the result and taking it out of further selection * * (it will have a probability of 0% to be chosen) * * * * * * * * * * * * * * * * * * * * * * * * * * * */ cromo->fitness = (objt - P > 0)?(objt-P):0; } ------- cut here -------------
Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?