| Técnicas Completas | Técnicas Incompletas |
|---|---|
| Encuentra el óptimo global si existe | Busca el óptimo local |
| Permite saber si no existe solución | Necesita una condición de termino |
| Recorre todo el espacio de búsqueda | Encuentra soluciones factibles rápidamente |
| En todas las ejecuciones entregan el mismo resultado | En cada ejecución entrega resultados diferentes |
| Método determinista | Método estocastico |
- Problema: Una persona debe visitar un conjunto de n ciudades comenzando en una ciudad específica, debiendo regresar a esa misma ciudad, luego de haber visitado todas las ciudades y sin haberse devuelto a ninguna.
- Objetivo: Encontrar la secuencia óptima de visita, medida a través de un criterio como: minimizando costo, minimizando tiempo o maximizando velocidad....
- Problema: Se tiene una pieza (un plano, una planta de un edificio, una placa) en donde se desean posicionar objetos sin que se superpongan. El problema puede tener objetivos de al menos dos clases:
- Optimización: Buscando introducir la mayor cantidad de objetos posibles en la pieza o buscar la menor dimensión de la pieza que permita que todos los objetos sean ubicados dentro de la pieza.
- Satisfacción: Buscando la ubicación de los objetos que se sabe caben en la pieza.
- Problema: Una tabla horaria es la localización de un conjunto de reuniones en el tiempo. Una reunión es una combinación de recursos (salas, personas, equipos..) algunos de los cuales están especificados en el problema y otros se asignan como parte de la resolución del problema
Puede tener básicamente 2 objetivos distintos:
- Optimización: Minimizar el tiempo ocioso
- Satisfacción: Alcanzar a realizar todas las actividades en el tiempo dado
- Problema: Colorear un grafo con k colores de tal forma que los nodos adyacentes no tengan el mismo color.
Puede también tener 2 prismas en cuanto a objetivos:
- Optimización: Encontrar el valor mínimo de k que permita cumplir con las restricciones
- Satisfacción: Dado un cierto valor k, por ejemplo k=3, colorear el grafo con esos tres colores sin que los nodos adyacentes tengan el mismo color.
Las metahurísticas son estrategias inteligentes para diseñar o mejorar procedimientos heurísticos muy generales con un alto rendimiento.
- Relajación: resuelven problemas relajando el modelo original, haciendolo más fácil de resolver, cuya solución hace más fácil resolver el problema original.
- Constructivas: obtienen la solución a partir del analisis y selección paulatina de los elementos que forman dicha solución.
- Búsqueda: usan procedimientos que transforman o mueven la solución inicial para explorar y luego explotar la solución.
- Evolutiva: procedimientos basados en los conjuntos de soluciones que evolucionan sobre el espacio de las mismas soluciones.
- Descomposición: determinan subproblemas a partir de los cuales se construye una solución del problema origina. Intermedio entre relajación y contrucción. La idea es que los subproblemas sean mucho más faciles de resolver y que las soluciones puedan ser usadas como base.
- Memoria a largo plazo: metaheuristica de aprendizaje. Están entre las de población inicial y búsqueda tabú. Son capaces de emplear la información obtenida en la aplicación del procedimiento.
- Algoritmos de estimación de distribución (EDA): algoritmos evolutivos que usan soluciones candidatas para realizar trayectorias que eviten óptimos locales.
- Simple: basada en un principio sencillo y claro, facíl de entender.
- Precisa: pasos y faces concretas.
- Coherente: elementos deben deducirse naturalmente.
- Efectiva: proporcionar soluciones de muy alta calidad o cercanos a los óptimos.
- Eficaz: probabilidad de silución en situaciones realistas es alta.
- Eficiente: aprovechar bien los recursos del PC, memoria y tiempo de ejecución.
- General: buen rendimiento en diversos problemas.
- Adaptable: debe adaptarse a cambios en el modelo.
- Robusta: poco sensible a pequeñas alteraciones del modelo o contexto.
- Interactiva: el usuario puede aplicar sus conocimientos para mejorar el rendimiento.
- Múltiple: dar varias soluciones de alta calidad para poder elegir.
- Autónoma: debe funcionar libre de parámetros o que estos se pongan solos.
Son algoritmos que buscan encontrar soluciones aceptables. Se usan porque ellas son, en general, eficientes computacionalmente y/o fáciles de implementar. Ellas no son muy precisas ni predecibes. El mejor resultado se obtiene al mezclar heurísticas con técnicas o algortimos de optimización.
Los algoritmos basados en construcción encuentran soluciones de manera incremental empezando con una solución vaciá, añadiendo componentes de forma incremental hasta completar una solución. Los algoritmos de construcción glotones o greedy añaden a la solución el componente que, de acuerdo a cierta heurística, produce el máximo beneficio local (Función miope que toma en consideración solo la información local). No crean vecindarios.
- En el TSP añadir siempre la ciudad más cercana.
- En el problema de optimización de coloreo de grafos asignar como primera opción los colores ya utilizados.
Generalmente los algoritmos que construyen soluciones son más rápidos, pero sus resultados no siempre son buenos.
- Representación
- Función de aptitud/evaluación (objetivos)
- Punto de partida
- Función miope
Los algoritmos basados en búsqueda local se mueven en el espacio de soluciones. Se puede ver como un proceso iterativo que empieza en una solución y a través de modificaciones locales la va mejorando.
- Representación
- Movimiento (Generar el vecindario)
- Reparar una solución (Buscar en el vecindario)
- Función de aptitud (objetivos)
Busca ir mejorando el valor de la función objetivo de una solución candidata, realizando reparaciones.
- Solo acepta movimientos que mejoran la calidad de la solución actual.
- Queda atrapado en soluciones locales.
- PArtiendo desde distintas semillas llega a resultados distintos.
- No asegura un óptimo global
- Selección según alguna mejora: la primera instancia que mejora la calidad de la solución es aceptada inmediatamente.
- Selección según mejor mejora: se construye un vecindario según el movimiento, y luego, de ese vecindario se elije la instancia que proporcione mejor calidad.
Re-comienza el algoritmo con una solución nueva cuando se ha quedado atrapado en un óptimo local. Explora, pero se puerde información valiosa. Reiniciar en otro punto cualquiera cambia completamente el vecindario, pudiendo haber estado cerca de un óptimo global. Para solucionar esto, se puede:
- Almacenar óptimos locales.
- Aceptar solo soluciones de peor calidad.
- Prohibir ciclos de búsqueda.
Si la solución actual es la mejor del vecindario el algoritmo aplica Restart.
Restringe la búsqueda al calsificar ciertos movimientos como prohibidos, para evitar caer en soluciones recientes. Para escapar de óptimos locales se eceptan soluciones de peor calidad. La lista tabú generalmente se llena en forma FIFO.
- Lista tabú: para impedir ciclos.
- Al comienzo es recomendable tener una lista tabú larga, para diversidicar y explorar.
- Al final, se recomienda tener una lista tabú corta, para explotar o intensificar.
- Puede llegar a restringuir el tamaño de los vecindarios, y por lo tanto, la búsqueda y las posibilidades de encontrar el óptimo.
- Criterio de aspiración: esto es tabú, pero si con X movimientos consigo calidad Y, acepto de todas formas.
Una lista tabu almacena movimientos prohibidos y en cada iteración elige el mejor movimiento factible no-tabu. Después de cada iteración, una colección de movimientos que podría hacer volver inmediatamente al punto anterior es agregado a la lista tabu. Ya que a cada paso se puede mejorar o empeorar el valor de la función objetivo, se guarda la información de la mejor solución encontrada hasta el momento. Cuando la búsqueda termina luego de un máximo número de iteraciones se informa la mejor solución obtenida.
Simula el enfriamento de ciertos materiales. Permite soluciones que empeoran la calidad en base a una probalidad que depende de la temperatura del sistema. Al comienzo es recomendable tener una temperatura alta para diversificar, puesto que esto se traduce en alta probabilidad de aceptación. Al final, se usa una temperatura baja puesto que disminuye la probabilidad de aceptación y con esto se intensifica.
- Inicializar T en un valor alto.
- Inicializar solución inicial, aletoria.
- Generar vecindario.
- Chequear cuales vecinos son factibles
- Estratificar(dividir en porcentajes equivalentes) los vecinos.
- Elegir al vecino correspondiente al numero aleatorio definido previo a la busqueda.
- Si el vecino tiene mejor calidad, se acepta de inmediato.
- Si el vecino es peor, se calcula la probabilidad.
- Actualizar T si el problema lo considera.
Se utilizan enfriamientos sucesivos cada cieto número de iteraciones y recalientatmientos períodicos para escapar de óptimos locales.
- El más apto sobrevive y tiene más posibilidades de tener descendencia.
- Se trabaja con poblaciones de individuos.
- Función de evaluación determina que tan apto es el individuo.
- Tamaño pequeño de población: pocos puntos donde buscar, se explota.
- Tamaño grande de población: diferentes puntos y pasos largos donde buscar, se explora.
- Genotipo: es lo que se transmite. Caracteres hereditarios definidos por un conjunto de genes. No cambian. Por ejemplo, la representación.
- Fenotiopo: No se transmite. Apariencia fisica, caracteristicas observables y medibles. Pueden cambiar en el tiempo. Por ejemplo, la calidad en la función evaluación.
- Representación: forma en que se representaran las variables. Las 2 principales representaciones son binarias o código gray.
- Iniciaización: Aleatoriamente, sembrando con cromosomas buenos para conseguir una evuloción más rápida.
- Proceso de selección: seleccionar individuos más aptos para ser transformados, pero no solo los mejores, ya que de esa forma solo se intensificaria. Esto se regula con el término Presión de selección. Cuando la presión es alta, se eligen los mejores candidatos, favoreciendo explotación. Si la presión es baja, se admiten candidatos no tan buenos, explorando.
* __Ruleta__: selección propocional a la función de desempeño. Ponderación respecto a su calidad o fitness. La ruleta tiene alta presión de selección. El problema con este método, es que si una fraccion de la población pose una media de desempeño excesivamente alta, tendrán mucha más probabilidades de ser elegido y por ende perjudica la exploración.
* __Torneo__: se define un grupo y se escoge al con mejor desempeño.
* __Ranking__: es un poco más equilibrado y equitativo. Los individuos se ordenan según su medida de desempeño.
-
Cruzamiento (Explota y explora):
- Maneja la explotación y la exploración según el tipo de corte que se realicé.
- Existe una probabilidad de cruzamiento [0.6 - 1]
-
Mutación (Explora): operación para escapar de optimos locales y entregarle variabilidad al algoritmo. Es una probabilidad de un pequeño cambio aleatorio en un individuo. Generalmente el operador de mutación que se utiliza es Bit-flip, que cambia el valor de un bit. La probabilidad de mutación es pequeña, en un rango que va desde [0.001 - 0.1]
-
Reemplazo: reemplazar individuos de la población inicial con los nuevos individuos generadosal terminar el proceso. Una técnica llamada elitismo permite dejar siempre en la población al mejor individuo de la población anterior, haciendo que se salte el proceso de selección. Esto es con el fin de mejorar la generación.
-
Condición de parada: puede ser un total de individuos, como el tamaño maximo de la población o numero de x de generaciones.
Para evitar convergencia prematura en un algoritmo genético, se puede:
- No tener una presión de selección muy elevada.
- No tener una probabilidad de mutación muy baja.
- No tener un tamaño de población ineficiente o muy pequeña para el problema.
incompletas*