• Author / Uploaded
• Andres Rodrigues

• Categories
• Algoritmo genético
• Optimización matemática
• Evolución
• Heurístico
• Algoritmos

Citation preview

1. 

Algoritmos Genéticos o Definición El algoritmo genético (AG) imita el proceso de evolución biológica de “sobrevivencia del más apto”. Cada solución factible de un problema se considera como un cromosoma codificado por un conjunto de genes. Los códigos genéticos más comunes son el binario (0,1) y el numérico (0, 1, 2,…, n). Por ejemplo, los cromosomas de una sola variable cuyos valores factibles son 0, 1, 2, 3, 4, 5, 6, 7 y 8 pueden ser representados por los códigos binarios (0000, 1000, 0100, 1100, 0010, 1010, 0110, 1110 y 0001) Estas ideas se transfieren hacia los problemas de optimización en una forma bastante natural. Las soluciones factibles de un problema específico corresponden a los miembros de una especie particular, donde la aptitud de cada miembro ahora se mide por el valor de la función objetivo. En lugar de procesar una sola solución de prueba a la vez (como sucede con las formas básicas de la búsqueda tabú y el templado simulado), ahora se trabaja con una población completa de soluciones de prueba.1 En el caso de cada iteración (generación) de un algoritmo genético, la población actual consiste en el conjunto de soluciones de prueba que en la actualidad están bajo consideración. Estas soluciones de prueba se entienden como los miembros vivos de la especie. Algunos de los miembros más jóvenes de la población (en especial los miembros más aptos) sobreviven en la adultez y se convierten

en padres (aparejados de manera aleatoria) que después tienen hijos (nuevas soluciones de prueba) que tienen algunas de las características (genes) de ambos padres. Como los miembros más aptos de la población tienen una mayor probabilidad de convertirse en padres que los otros, a medida que avanza, un algoritmo genético tiende a generar poblaciones mejoradas de soluciones de prueba. De vez en cuando ocurren mutaciones, de forma que los hijos también pueden adquirir características (algunas veces deseables) que no posee ninguno de los padres. Este fenómeno ayuda a los algoritmos genéticos a explorar una parte de la región factible, quizá mejor que la que se consideró antes. Por último, la supervivencia del más apto tiende a conducir al algoritmo genético hacia una solución de prueba (la mejor de todas las consideradas) que al menos es cercana a la óptima. Aunque la analogía con el proceso de la evolución biológica define la esencia de cualquier algoritmo genético, no es necesario adherirse de manera rígida a esta analogía en cada detalle. Por ejemplo, algunos algoritmos genéticos (incluido el que se describe a continuación) permiten que la misma solución de prueba sea un padre en forma repetida a través de múltiples generaciones. De modo que la analogía debe ser sólo un punto de partida para definir los detalles del algoritmo que se ajuste mejor al problema bajo consideración. o Usos y aplicaciones 

Optimización: Se trata de un campo especialmente abonado para el uso de los Algoritmos Genéticos, por las características intrínsecas

de estos problemas. No en vano fueron la fuente de inspiración para los creadores estos algoritmos. Los Algoritmos Genéticos se han utilizado en numerosas tareas de optimización, incluyendo la optimización numérica, y los problemas de optimización combinatoria. 

Programación automática: Los Algoritmos Genéticos se han empleado para desarrollar programas para tareas específicas, y para diseñar otras estructuras computacionales tales como el autómata celular, y las redes de clasificación.



Aprendizaje máquina: Los algoritmos genéticos se han utilizado también en muchas de estas aplicaciones, tales como la predicción del tiempo o la estructura de una proteína. Han servido asimismo para desarrollar determinados aspectos de sistemas particulares de aprendizaje, como pueda ser el de los pesos en una red neuronal, las reglas para sistemas de clasificación de aprendizaje o sistemas de producción simbólica, y los sensores para robots



Economía: En este caso, se ha hecho uso de estos Algoritmos para modelizar procesos de innovación, el desarrollo estrategias de puja, y la aparición de mercados económicos.



Sistemas inmunes: A la hora de modelizar varios aspectos de los sistemas inmunes naturales, incluyendo la mutación somática durante la vida de un individuo y el descubrimiento de familias de

genes múltiples en tiempo evolutivo, ha resultado útil el empleo de esta técnica. 

Ecología: En la modelización de fenómenos ecológicos tales como las carreras de armamento biológico, la coevolución de parásitohuésped, la simbiosis, y el flujo de recursos.



Genética de poblaciones: En el estudio de preguntas del tipo “¿Bajo qué condiciones será viable evolutivamente un gen para la recombinación?”



Sistemas sociales: En el estudio de aspectos evolutivos de los sistemas sociales, tales como la evolución del comportamiento social en colonias de insectos, y la evolución de la cooperación y la comunicación en sistemas multi-agentes.

Aunque esta lista no es, en modo alguno, exhaustiva, sí transmite la idea de la variedad de aplicaciones que tienen los Algoritmos Genéticos. Gracias al éxito en estas y otras áreas, los Algoritmos Genéticos han llegado a ser un campo puntero en la investigación actual.



Colonia de Hormigas o Definición Se trata de una técnica probabilística para resolver problemas computacionalmente complejos que pueden ser reducidos a la búsqueda de buenos caminos en grafos. ACO se inspira directamente en el comportamiento de las colonias reales de hormigas para solucionar problemas de optimización combinatoria. Se basan en una colonia de hormigas artificiales, esto es, agentes computacionales simples que trabajan de manera cooperativa y se comunican mediante rastros de feromona artificiales.

o Usos y Aplicaciones Los problemas de tipo

2) ¿Cuál es la diferencia entre heurística y meta-heurística? La heurística está diseñada para encontrar buenas soluciones aproximadas de problemas combinatorios difíciles que de lo contrario no pueden resolverse mediante los algoritmos de optimización disponibles. Una heurística es una técnica de búsqueda directa que utiliza reglas favorables prácticas para localizar soluciones mejoradas. La ventaja de la heurística es que en general determina (buenas) soluciones con rapidez, utilizando reglas de solución simples. La desventaja es que la calidad de la solución (con respecto a la óptima) suele desconocerse. La meta-heurística está diseñada principalmente para escapar del entrampamiento en el óptimo local al permitir movimientos inferiores, si es necesario. Se espera que la flexibilidad agregada a la búsqueda conduzca a una mejor solución. La meta-heurística se basa en los siguientes puntos de referencia:

1. La cantidad de iteraciones de búsqueda excede una cantidad especificada.

2. La cantidad de iteraciones desde la última mejor solución excede una cantidad especificada.

3. La vecindad asociada con el punto de búsqueda actual, o está vacía o no puede conducir a un nuevo movimiento de búsqueda viable.

4. La calidad de la mejor solución actual es aceptable.

A pesar de que la Meta-heurística es un método de la Heurística, se diferencia en algunos aspectos, Meta-heurística significa literalmente “encontrar más allá”, es decir su búsqueda es más minuciosa que la que ofrece el método Heurístico. A diferencia de la Heuristica, la Metaheurística se aplican a problemas que no tienen un algoritmo o heurística especificada, además mientras las Heuristica trata de huir de los óptimos locales orientado en la búsqueda de cada momento dependiendo de la evolución del proceso de la búsqueda. Finalmente, en contraste con la Meta-heurística, la Heuristica se caracteriza por su rapidez y facilidad y ofrece respuestas buenas más no óptimas.

3) ¿Para qué se usa una heurística y una meta-heurística en optimización?

o Heurística La Heurística se usa principalmente en problemas de optimización, cuando se encuentran algunas de las características: a. El problema es de una naturaleza tal que no se conoce ningún método exacto para su solución. b. Aunque exista un método exacto para resolver el problema, su uso computacionalmente costoso o inviable. c. El método heurístico es más flexible que un método exacto, permitiendo, por ejemplo, la incorporación de condiciones de difícil modelización. d. El modelo matemático es demasiado grande, demasiado NO lineal o demasiado complejo desde el punto de vista lógico. e. El asumir suposiciones o aproximaciones para simplificar el problema, tienede a destruir estructuras del modelo que son vitales en el contexto del mundo real, haciendo la solución no viable. o Meta-heurística Aunque algunas veces se aplican Meta-heurísticas a problemas difíciles de programación no lineal y entera, un área de aplicación más común es la de los problemas de optimización combinatoria. Un ejemplo clásico de esto es conocido como el problema del agente viajero, recibió este nombre pintoresco porque puede describirse en términos de un agente de ventas que debe visitar cierta cantidad de ciudades en un solo viaje. Si comienza desde su ciudad de residencia, el agente determinará cuál ruta debe seguir para

visitar cada ciudad exactamente una vez antes de regresar a su casa de manera que se minimice la longitud total del viaje.

4) 5) a. Bin packing problem.

b. Problema de Knapsack El modelo de la mochila tiene que ver clásicamente con el hecho de determinar los artículos más valiosos que un combatiente carga en una mochila. El problema representa un modelo de asignación de recursos general en el cual se utilizan recursos limitados por varias actividades económicas. El objetivo es maximizar el rendimiento total.1 La ecuación recursiva (hacia atrás) se desarrolla para el problema general de asignar n artículos a una mochila con capacidad de peso W. Sea mi la cantidad de unidades del artículo i en la mochila, y defina ri y wi como el ingreso unitario y el peso del artículo i. El problema general se representa como

𝑍𝑚𝑎𝑥 = 𝑟1 𝑚1 + 𝑟2 𝑚2 + ⋯ + 𝑟𝑛 𝑚𝑛 𝑆. 𝐴 𝑤1 𝑚1 + 𝑤2 𝑚2 + ⋯ + 𝑤𝑛 𝑚𝑛 𝑚1 + 𝑚2 , … , 𝑚𝑛 𝑒𝑛𝑡𝑒𝑟𝑜𝑠 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑜𝑠 Los tres elementos del modelo son

1. La etapa i está representada por el artículo i, i = 1, 2,…, n. 2. Las alternativas en la etapa i son la cantidad de unidades del articulo i, mi= 0,1,… [W/wi], donde [W/wi] es el mayorentero que es penor o igual W/wi. Esta definición

permite que la solución distribuya algunos, ninguno o todos los recursos W cualquiera de los artículos m artículos. El rendimiento para mi es rimi. 3. El estado en la etapa i, i+1,…, y n. Esta definición reconoce que el límite de peso es la única restricción que liga a todas las n etapas. c. Problema de asignación El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan a la realización de tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas. Para que se ajuste a la definición de un problema de asignación, es necesario que este tipo de aplicaciones se formule de manera tal que se cumplan los siguientes supuestos. 1. El número de asignados es igual al número de tareas. (Este número se denota por n.) 2. A cada asignado se le asigna sólo una tarea. 3. Cada tarea debe realizarla sólo un asignado 4. Existe un costo cij asociado con el asignado i (i 5 1, 2,. . ., n) que realiza la tarea j (j= 1, 2,. . ., n). 5. El objetivo es determinar cómo deben hacerse la n asignaciones para minimizar los costos totales.

d. Problema de transporte Tal como se indica en la figura. Hay m orígenes y n destinos, cada uno representado por un nodo. Los arcos representan las rutas que unen los orígenes con los destinos. El arco (i, j) que une el origen i con el destino j transporta dos piezas de información: el costo de transporte por unidad, cij y la cantidad transportada, xij. La cantidad de la oferta en el origen i es ai y la cantidad de la demanda en el destino j es bj. El objetivo del modelo es minimizar el costo de transporte total al mismo tiempo que se satisfacen las restricciones de la oferta y la demanda.