[galib] Constrainted Optimization

Anselmo Pitombeira anselmop at sc.usp.br
Tue Nov 20 09:32:24 EST 2007

You have many ways of avoiding infeasible solutions, but I suggest one 
of the following:

 1. Using a chromosome representation which doesn't allow an infeasible 
solution to be generated;
 2. developing a feasibility correction procedure;
 3. applying penalties on infeasible individuals so that they can't 
propagate over the generations.

Alternative 1 is preferable, since you don't have to set any parameter, 
i.e., the penalty value, but it may be difficult for you to arrive at a 
suitable representation which bounds within your feasible solution 
space. Moreover, if you use an obscure representation, you must develop 
all genetic operators and experiment with them in order to assess their 

You can also check for the feasibility of the solution as soon as it is 
generated, as in alternative 2, and modify it so that it complies with 
your feasible space definition. You have to develop a correction 
procedure to accomplish this.

My third suggestion is the use of penalties. You check for the 
feasibility of the solution and in case it is infeasible, you just 
assigns a high fitness value to it. This is the simplest method, but it 
has the drawback of requiring the penalty value, which is highly 
dependent on your data set.

There is no immediate way of doing this in GALib. You may use, as an 
aid, allele sets in order to develop a representation which doesn't 
generate infeasible solutions.

Mit freundlichen Grüssen aus Brasilien

Anselmo Pitombeira

galib-request at mit.edu escreveu:
> ----------------------------------------------------------------------
> Message: 1
> Date: Mon, 19 Nov 2007 11:38:01 +0100
> From: "Bruckmann, Tobias" <bruckmann at mechatronik.uni-duisburg.de>
> Subject: [galib] Constrainted Optimization
> To: <galib at mit.edu>
> Message-ID:
> 	<27EC885DCEA1A44AB6BAE5C934D3D9BB1B8834 at horch.mechatronik.uni-duisburg.de>
> Content-Type: text/plain;	charset="us-ascii"
> Hallo,
> I'm starting my experience with GAlib to solve a constrainted
> optimization problem. That means, I have absolutely strict boundaries
> for the optimization. The evolution will generate individuals which are
> invalid and thus have to be removed from the population before the next
> generation is created. Now I could just set a very bad cost function for
> these individuals, but in this case, the population would sometimes
> contain individuals which are no solution. So I would prefer to "kill"
> these individuals - is there already a way within GAlib to do this, or
> do I have to implement it by myself?
> Thanks a lot for your help and 
> Best Regards,
> Tobias
> ------------------------------

More information about the galib mailing list