[galib] Constrainted Optimization

[Bruckmann, Tobias]

Dear Anselmo,

thanks a lot for this helpful explanation. Maybe I should describe my problem more detailed: I'm optimizing robot designs - I want to have an optimized (e.g. small, cheap or fast) design, but it must be guaranteed that a predefined workspace (= all poses the robot can reach) can be covered by the resulting robot, so the robot can handle a certain task for sure. That means that the parts of robot (my genome) can vary in a wide variety. Noteworthy, the optimum design is very close to a design which doesn't have the required workspace. If I just allow parts will never lead to invalid workspaces (which would be hard to determine in advance), I would never get "optimal" results close to the real optimum. Thus, the limited chromosome representation will not help since I can determine invalid designs only during runtime within the objective function (where I check if the individuum has the required workspace)

Mit freundlichen Grüßen aus dem verregneten Duisburg,

Tobias


Tobias Bruckmann 
Universität Duisburg-Essen, Campus Duisburg 
Fachbereich Ingenieurwissenschaften 
Abteilung Maschinenbau 
Lehrstuhl für Mechatronik 
Lotharstraße 1, MD 227
47057 Duisburg
 
Tel.: +49 (0) 203 / 379 - 1908 oder -4065
Mobil: +49 (0) 174 / 186 15 78
Fax: +49 (0) 203 / 379 - 4494 
E-Mail: mailto:bruckmann at mechatronik.uni-duisburg.de  
Internet: http://www.uni-due.de/mechatronik

-----Ursprüngliche Nachricht-----
Von: galib-bounces at mit.edu [mailto:galib-bounces at mit.edu] Im Auftrag von Anselmo Pitombeira
Gesendet: Dienstag, 20. November 2007 15:32
An: galib at mit.edu
Betreff: Re: [galib] Constrainted Optimization

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 efficiency.

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
>
>
>
>
> ------------------------------
>   
_______________________________________________
galib mailing list
galib at mit.edu
http://mailman.mit.edu/mailman/listinfo/galib