Autor Tema: Problema De Algoritmos Genéticos (Leído 5224 veces)

Geneticos · « **en:** Lunes 24 de Mayo de 2004, 12:33 »

Tenemos un problema de algoritmos genéticos en el que debemos ubicar un número de piezas de 2 dimensiones en un área mínima. Podría ser el ejemplo de una placa electrónica en la que posicionar elementos electrónicos, como una placa base, por ejemplo. Teniendo en cuenta que el usuario introduce las dimensiones de todas las piezas que desea, debemos obtener el resultado mediante algoritmos genéticos.

Cada individuo lo hemos representado indicando la posición y las dimensiones de cada una de las piezas. La población inicial la creamos de forma aleatoria, pudiendo girar 90º las piezas. La función de evaluación escogida ha sido: area + grado de solapamiento de piezas (cuanto mayor, peor). El cruce lo hemos realizado con un solo punto, escogiendo padres de forma aleatoria, pero teniendo en cuenta que el mejor evaluado tiene mayor probabilidad. Y la mutación la realizamos arrinconando las piezas en la esquina, para reducir el área.

La función de evaluación y los operadores de cruce y mutación que hemos elegido no nos han dado muy buenos resultados, por lo que agradecería si alguien nos pudiera ayudar en elegir esta función y estos operadores.

Muchas gracias.

AURED

Mmmmm...creo que entiendo al menos la idea de tu programa. Veo que estás aplicando una función de aptitud sumando dos objetivos. O sea que realmente lo que tienes entre manos es una optimización multiobjetivo, podrías plantearte la posibilidad de hacer una búsqueda del pareto óptimo de las soluciones. Por otro lado si lo que no quieres de ningún modo es que haya solapamiento de las piezas, puedes plantarte eso como una restricción y penalizar a aquellas soluciones que presenten algún grado de solpamiento. En cuanto a la elección de los padres, ¿sólo el mejor evaluado tiene mayor probabilidad de ser escogido?¿la probabilidad de escoger unos u otros no se basa en sus mejores o peores aptitudes, de modo que uno tendrá más probabilidades de ser padre cuanto mejor solución sea? (o sea como una ruleta clásica....).Me temo que el asunto de la mutación no lo entiendo.

Actualmente me encuentro pegándome con un SPEA para aplicar una optimzación multiobjetivo.

emax

Hola ! estoy intersado en resolver un problema similar a este planteado y queria saber si habian arribado a un buen planteo y a una buena solucion. Gracias por su tiempo. Agradeceria me contestara.
Saludos.

Geneticos

emax, si me das tu correo electrónico te enviaré lo que al final hicimos (está programado en Matlab).

emax

hola! gracias por interesarte, te cuento que estoy programando en delphi, pero igual me sirve lo de matlab pues se programar en matlab, mi email es emax_ii@latinmail.com, desde ya gracias.-

Amilius

Cita de: "AURED"

Me temo que el asunto de la mutación no lo entiendo.

La mutación es muy importante para evitar el estancamiento en máximos locales.

----

Creo que esos puntos deberían ser configurables, por ejemplo lo del elitismo:

1.- Elitismo o sólo ruleta.(Un porcentaje de 1 a n% de la población tendrá como padre al "macho alfa"

, con cruce con el resto de la población, el resto según la ruleta.)

2.- Opción para incluir un "clon" del mejor evaluado en la siguiente generación para asegurar que evites perder el mejor "espécimen"

3.- Nivel de mutación. (Tal vez automático: aumentando si se llega al estancamiento y disminuyendo si la población ya es bastante diversa)

Y un detalle más: ¿Las piezas sólo pueden girarse 90º en 2 dimensiones? Por que también es necesario considerar que se las puede girar 180º usando una tercera dimensión siendo el resultado la pieza "reflejada" en vertical u horizontal. Por ejemplo en lugar de girar una pieza de 3 dimensiones por una cuarta y que todo quede denuevo en 3dimensiones es más sencillo reflejarla en algún eje.

Finalmente siempre hecha una ojeada entre varios a todo el algoritmo, no vaya a ser que por un detalle "casi invisible" las cosas no funcionen como deben.

AURED

Je je je, no me as entendido, si que entiendo en que consiste la mutación, de hecho la he implementado en varios algoritmos. Lo que me refería es que no entendía el método en el que Geneticos había empleado la mutación.

AURED

En cuanto a la mutación puedes plantearte una mutación no uniforme, de modo que conforme avancen las generaciones el rango en el que puede mutar el gen seleccionado se ciña cada vez más en el el entorno del gen original.
El problema que veo es como vas a agregar ambos objetivos, puedes tener soluciones de muy baja área con elevado grado de solapamiento y también lo contrario. Deberás seleccionar los pesosde un modo muy cuidadoso.

Tengo una pregunta, ¿permites que haya solapamiento en las piezas?¿o por el contrario no lo deseas? en este caso te comentaba lo de emplear el grado de solapamiento como una penalización, mejor que como un objetivo adicional, si por el contrario puedes asumir cierto grado de solapamiento te sugiero que te plantees una optimización de dos objetivos, en la red hay muchos artículos donde buenos algoritmos multiobjetivo son descritos, busca SPEA,SPEA2, MOGA,NPGA,NSGA....

Imagino que todas estas palabras llegan tarde.....lo siento.

cad666

Por favor si puedes enviame el codigo que tienes en Matlab de la resolucion de tu problema ya que estoy intentado resolver un problema similar en Matlab pero recien lo instale hace poco asi que no termino de enteder bien como funciona el GA Toolbox, gracias.
Mi email es cad666@hotmail.com

SoloCodigo

Autor Tema: Problema De Algoritmos Genéticos (Leído 5224 veces)

Geneticos

Problema De Algoritmos Genéticos

AURED

Re: Problema De Algoritmos Genéticos

emax

Re: Problema De Algoritmos Genéticos

Geneticos

Re: Problema De Algoritmos Genéticos

emax

Re: Problema De Algoritmos Genéticos

Amilius

Re: Problema De Algoritmos Genéticos

AURED

Re: Problema De Algoritmos Genéticos

AURED

Re: Problema De Algoritmos Genéticos

cad666

Re: Problema De Algoritmos Genéticos