Algoritmo Genetico como método de resolución de problemas de búsquedas y optimización

[pic 1][pic 2]

UNIVERSIDAD TÉCNICA DE AMBATO

FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL

“INVESTIGACION OPERATIVA”

TÍTULO:

ALGORITMO GENÉTICO

CARRERA:

INGENIERÍA INDUSTRIAL EN PROCESOS DE AUTOMATIZACIÓN

ÁREA ACADÉMICA:

INDUSTRIAL

CICLO ACADÉMICO Y PARALELO:

CUARTO “A”

ALUMNOS PARTICIPANTES:

CASTRO CÓRDOVA DIEGO ISRAEL

CONRADO MESTANZA BRYAN SEBASTIAN

MÓDULO Y DOCENTE:

INVESTIGACION OPERATIVA ING. ROSA GALLEGUILLOS

RESUMEN:

La presente investigación consiste en el estudio y análisis del Algoritmo Genético como método de resolución de problemas de búsquedas y optimización, tomando en cuenta que este tipo de técnica tiene la facultad de reducir significativamente los procedimientos para la resolución de ciertos problemas en cuanto a optimización o a la mejora de algún proceso se refiere, se han tomado en cuenta 3 publicaciones que han sido puestas  directamente para apreciación y  estudio y de esa forma verificar la eficacia de este tipo de algoritmo además de enunciar si es este puede llegar a ser factible o no además se podrá notar que en cada publicación  a pesar de que se sigue la temática del algoritmo genético se ocuparan procesos distintos debido a que el modelo debe irse adaptándose según los variables o restricciones expuestas cabe recalcar que  este algoritmo en cada uno de los artículos la solución más óptima no siempre  será la que sobresalga primero sino que,  será aquella que después de varias combinaciones  cumpla con las requerimientos del problema.

Se describe en detalle un algoritmo genético simple con aplicación a la optimización de parámetros continuos, incluyendo diversos métodos de selección los mismos que son elegidos de acuerdo a las especificaciones del problema. La investigación por sí misma es capaz de promocionar la enseñanza, entrenamiento, desarrollo de destrezas y otras oportunidades de aprendizaje. Se puede discutir como  el estudio de estos apartados enriquecerán  de gran manera nuestros conocimiento y a su vez  se puede evaluar cuan útil puede llegar a ser este método  en referencia a cuan efectivo fue este algoritmo en la solución a los problemas estudiados.

Palabras clave: Algoritmo genético, problemas, optimización, decisiones, modelo, artículos.

OBJETIVOS:

Objetivo General

Estudiar el método conocido como Algoritmo genético a través de  investigación bibliográfica y ejemplos, con la finalidad de que al concluir con  esta investigación, este algoritmo pueda ser aplicado a problemas de optimización o cualquier otra cuestión verificando su factibilidad revisando si pudo dar solución a los problemas tratados en los apartados.

Objetivos Específicos

• Analizar tres publicaciones referentes al Algoritmo Genético con la finalidad de poder evaluar sus procedimientos y resultados y así notar si este método es adecuado o no.
• Aprender la adecuada aplicación del Algoritmo genético en el desarrollo de soluciones adecuadas para ciertos problemas que requieran una mejora en una industria, empresa o cualquier ámbito.

• Determinar la relación del algoritmo con los problemas de optimización en u una industria para obtener una solución factible para realizar un trabajo de calidad.

DESARROLLO:

PAPER 1: ALGORITMO GENETICO MODIFICADO APLICADO AL PROBLEMA DE SECUENCIAMIENTO DE TAREAS EN SISTEMAS DE PRODUCCION LINEAL – FLOW SHOP

Resumen

En este trabajo se aborda el problema de producción de Flow Shop que radica en el secuenciamiento de tareas con el objetivo de minimizar el tiempo total de producción.

Planteamiento del Problema

El principal problema radica en establecer una secuencia de tareas entre las n! sucesiones posibles atravesando por todas las máquinas procurando mejorar una determinada medida de trabajo.

Las consideraciones usuales de un problema de programación de tareas Flow Shop son:

1) Cada máquina está disponible continuamente y sin interrupciones.

2) Cada máquina puede procesar una tarea por vez.

3) Cada tarea sólo puede ser procesada por una máquina cada vez.

Modelamiento matemático

El objetivo es encontrar la secuencia óptima de las distintas actividades a programar la cual debe minimizar el Makespan que corresponde al tiempo en el cual el último trabajo es culminado en la máquina m.

Metodología de solución

Representación del Cromosoma: la codificación utilizada para representar cada una de las alternativas de solución del problema de flow shop consiste en construir un vector de tamaño m (que corresponde al número de trabajos a ejecutar). Por lo tanto, la k-ésima posición del vector representa el trabajo que se hará en el k-ésimo lugar.

[pic 3]

Figura 1. Representación del cromosoma

Selección: En el proceso de selección se definen un determinado número de opciones que serán seleccionadas de la población de forma aleatoria a fin de definir los alternativos padres.

[pic 4]

Figura 2. Diagrama de flujo de selección de padres

Recombinación: con los dos padres elegidos, el siguiente proceso es cruzarlos de tal manera que se conciban dos nuevos descendientes con nuevas características. [pic 5]

Figura 3. Cruzamiento de padres para así obtener un nuevo hijo

Mutación: En este trabajo, el cromosoma hijo obtenido en el proceso de recombinación es sometido al proceso de mutación, que consiste en escoger, de manera aleatoria, dos trabajos e intercambiarlos.

Modificar la población actual: La estrategia de modificación de la población actual se realiza cambiando sólo una alternativa por iteración y teniendo en cuenta que no se admiten alternativas repetidas. Adicionalmente se pueden obtener múltiples soluciones de un mismo problema.

...