Solving Integer Programming Problems Using Genetic Algorithms
By ai-depot | May 25, 2003
Starting the Fun
Starting the fun
How does it look like?
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.
Our Objective
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
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 ————-
Constraints
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:
- Correcting the individuals that do not satisfy the constraints
- Eliminating the individuals that do not satisfy the constraints
- Adding a penalty function to diminish the individuals that do not satisfy the constraints
- Make the crossover, mutation and encoding take care of this.
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———-
How Good Am I?
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 ————-
Tags: none
Category: tutorial |
April 15th, 2007 at 8:40 am
nicely written article
August 30th, 2007 at 11:45 pm
I liked to know about the Integer Programming using GA and different between about the LP and Ip.
September 13th, 2007 at 3:39 am
pls explain the following as regarding integer programming problem. Sepration,fathoming,branching,bounding.
October 25th, 2007 at 10:21 am
Very nice!
Your tut help me a lot in my course.
Thank you very much.
February 2nd, 2008 at 12:32 pm
You should add a list of problems for moms to use for home schooling. It would definitely help! :-)
February 2nd, 2008 at 12:33 pm
It would sure help if you had a list of math problems for us moms. Thx. ;-)
February 8th, 2008 at 5:57 am
very good