Metaheurísticas

Cap´tulo 5 ı

T´ cnicas Incompletas e
´ 5.1. Busqueda Alternativa
Heur´stica: Son criterios, principios o m´ todos que permite determinar entre un conı e junto de posibilidades, aquella que promete ser la m´ s eficaz para cumplir un a objetivo. Las heur´sticas representan el compromiso entre dos exigencias: la neı cesidad de tener criterios simples y al mismo tiempo la necesidad de distinguirentre una buena y una mala elecci´ n. Un m´ todo heur´stico puede ser un m´ todo o e ı e emp´rico utilizado para guiar acciones. Son algoritmos que buscan encontrar soı luciones aceptables. Se usan porque ellas son, en general, eficientes computacionalmente y/o f´ ciles de implementar. Ellas nos son muy precisas ni predecibles. a e El mejor resultado se obtiene al mezclar heur´sticas con t´ cnicaso algoritmos de ı optimizaci´ n. o Reparar una soluci´ n: Buscar una nueva soluci´ n a partir de una soluci´ n existente o o o cambiando el valor que tiene asignado una sola variable. Es decir, se est´ busa cando una nueva soluci´ n en el ”vecindario”de la soluci´ n actual. o o Funci´ n Objetivo: Es la funci´ n clave dentro de la b´ squeda. Debe reflejar el Objetio o u vo que se est´ buscando ydebe ser capaz de medir que tan buena (o mala) es una a soluci´ n en t´ rminos del mismo. Una funci´ n objetivo es capaz de representar o e o uno o varios objetivos, esto se logra a trav´ s de una ponderaci´ n de los ”sube o objetivos”, la que es directamente proporcional al grado de importancia de ellos en la b´ squeda. u Caracter´stica principal: Problemas NP-Completos, Explosi´ n Combinatoria. ı o5.1.1. TSP (Travel Salesman Problem- Problema del Vendedor Viajero)
Problema: 41

42

´ ´ CAPITULO 5. TECNICAS INCOMPLETAS

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 optima de visita, medida atrav´ s de un criterio como: mini´ e mizando costo, minimizando tiempo o maximizando velocidad....

5.1.2. SPP (Space Planning problem - Problema de distribuci´ n eso pacial)
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: Buscandointroducir la mayor cantidad de objetos posibles en la pieza o o buscar la menor dimensi´ n de la pieza que permita que todos los objetos sean o ubicados dentro de la pieza. Satisfacci´ n: Buscando la ubicaci´ n de los objetos que se sabe caben en la pieza. o o

5.1.3. TT (TimeTabling problem - Problema de distribuci´ n horao ria)
Problema: Una tabla horaria es la localizaci´ n de un conjunto dereuniones en el tiempo. Una o reuni´ n es una combinaci´ n de recursos (salas, personas, equipos..) algunos de los o o cuales est´ n especificados en el problema y otros se asignan como parte de la resoluci´ n a o del problema. Puede tener b´ sicamente 2 objetivos distintos: a Optimizaci´ n: Minimizar el tiempo ocioso. o Satisfacci´ n: Alcanzar a realizar todas las actividades en el tiempo dado. o5.1.4. k-Colouring Problem (Colorear grafos con k colores)
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: e ı Optimizaci´ n: Encontrar el valor m´nimo de k que permita cumplir con las restrico ciones. Satisfacci´ n: Dado un cierto valor k, por ejemplo k = 3, colorear el grafo conesos o tres colores sin que los nodos adyacentes tengan el mismo color.

´ ´ 5.2. TECNICAS QUE USAN HEURISTICAS

43

Podemos ver que estamos trabajando, en general, con problemas denominados ”Problemas de Satisfacci´ n de Restricciones”(CSP) y ”Problemas de Optimizaci´ n con o o Satisfacci´ n de Restricciones”(CSOP) que pertenecen a la clase NP-completos debido o a su complejidad.

5.2....