Todo problema de decisión puede ser considerado como uno de búsqueda particular. Por convención, ?D, el conjunto S?(D) =?, si la respuesta a D es NO y S?(D) ={SI} si la respuesta a D es SI.
Def: los problemas NP-difíciles(duros): un problema ? es NP-difícil si es más difícil que un problema NP-completo, o sea existe un problema NP-completo que se reduce polinomialmente por la reducción de Turing a ?
ILP-optimización son NP-difíciles
Prog. Entera mixta
Prog Lineal
Prog. 0 1 mixta
Prog. Entera pura
Prog. 0-1
Knapsack entero
Localización
Flujos en redes
Pbs lineales de flujos
Set packing
Set covering
0-1 Knapsack
Camino más corto
Trasporte
Matching
Node packing
TSP
Asignación
Algoritmos aproximados
Def: algoritmo aproximado es un algoritmo que construye una solución que no se puede garantizar que sea óptima
Para problemas de gran tamaño se utilizan métodos heurísticos
Problema de métodos heurísticos: no trabajan eficazmente sobre todos los datos. Por esta razón muchas veces se trabaja con muchas soluciones introduciendo, para la construcción de soluciones, sorteos o por ejemplo por métodos de “vecinos”.
Métodos heurísticos: generalmente no validados matemáticamente pero eficientes en la práctica.
Problemas de optimización y algoritmos aproximados
Un problema de optimización es un problema combinatorio comprendiendo:
un conjunto D de datos,
para cada dato d? D un conjunto de soluciones S
una función F:S->R que fija el valor de cada una de las soluciones
Sea s* una solución óptima y F*(d) su valor óptimo
Def: Algoritmo aproximado: es un algoritmo A que construye una solución s’, sea F’(d)=F(s’) el valor de esta solución aproximada
Def: Aproximación absoluta: un algoritmo aproximado A da una aproximación absoluta si existe k tal que para todo dato d, ?F*(d)-F’(d)??k
Def: Aproximación relativa: un algoritmo aproximado A da una aproximación relativa si existen dos números a y b tal que para todo dato d, ?F*(d)-F’(d)?? a F*(d)+b
Def: Esquema de aproximación: Un esquema de aproximación es una familia de algoritmos aproximados A? (??Rn+) tal que para todo dato d, A? genera una solución de valor F’?(d), con: ?F*(d)- F’?(d )?? ?F*(d)
Def: Esquema de aproximación enteramente polinomial: es un esquema de aproximación donde la complejidad del algoritmo A? es una función polinomial del tamaño del problema y de 1/ ?
Construcción de soluciones
Def: Un método heurístico es un algoritmo aproximado o procedimiento inexacto que está bien definido paso a paso y que permite llegar a una solución de buena calidad rápidamente.
Las heurísticas son utilizadas en problemas donde se prioriza el tiempo de cálculo frente a la calidad de las soluciones.
Resultado de heurística: depende de su capacidad de adaptarse a casos particulares, de que evite quedar atrapada en mínimos locales y de su capacidad de exploración de la estructura del problema
Técnicas para mejorar una heurística: preproce-samiento de datos, diseño y utilización de estructuras de datos eficientes, utilización de procedimientos aleatorios en forma controlada (para diversificar el espacio de soluciones obtenidas), búsqueda intensa en regiones ‘promisorias’ según cierto criterio, etc.
Def: Metaheurísticas: clase de métodos aproximados que dan una metodología general, un marco de trabajo que permite la creación de nuevos algoritmos híbridos por combinación de diferentes conceptos derivados de las heurísticas clásicas, etc. Ejemplos de metaheurísticas: tabu search, simulated annealing, algoritmos genéticos, redes neuronales, GRASP, ANT-systems, etc.
Las metaheurísticas utilizan estrategias de aprendizaje de forma de poder estructurar la información para buscar eficientemente soluciones cercanas a la óptima.
Tabu search
Es una técnica de búsqueda local
Basada en noción de “vecindad”: sea S el espacio de búsqueda de un problema de optimización y f, la función objetivo, N(s) es la función de vecindad N:S–> P?S, N depende de la estructura del problema
Es un método de búsqueda local iterativo: partiendo de una solución s0 navega por el espacio de búsqueda pasando de una solución a alguna de sus vecinas
El algoritmo lleva una lista de movimientos de una solución a otra. Para evitar ciclos, el movimiento a realizar no debe estar en esta lista, llamada lista-tabu.
Lista-tabu contiene los últimos P movimientos
Función de aspiración A: es una función / v=f(s) y A(v)=v’ representa el valor de la función objetivo al cual se pretende llegar desde v. La función A permite modificar la lista-tabu
Parámetros del algoritmo: largo de la lista-tabu (P), función A de aspiración, cardinalidad del conjunto V ? N(s) y máxima cantidad de iteraciones sin mejorar el valor de la función objetivo (K)
Algoritmo:
1- s=s0, s-min=s0, i=0
2- calcular V ? N(s) y f(s’)=min f(s) / s?V,
3- i=i+1, si i>K, stop
4- s’ ? lista-tabu?
No: si f(s’)< f(s-mín), s-min=s’, i=0, fin si.
s=s’, actualizar lista-tabu
ir a 2
5-Si f(s’)?A(f(s)), s=s’,i=0, eliminar s’ de la lista-tabu, ir a 2.
6- elegir otro s’ ?V, ir a 3.
Simulated annealing
Método de búsqueda local
Parte de una solución factible s0 , por algún procedimiento se genera una solución vecina:
s’?V? N(s) ,
y se acepta s’ como nueva solución factible con cierta probabilidad aunque esta sea peor que la de partida.
Sea ‘f’ la función objetivo a minimizar y ?=f(s’)-f(s). La probabilidad de aceptar s’ como nueva solución está dada por:
Pr(aceptar s’)= 1 si ?< 0 y
e- ?/t si ??0
t es un parámetro del algoritmo, llamado temperatura
Fijado t se repite el proceso hasta que se llegue a una condición de ‘equilibrio’ que depende del problema (lo más sencillo: número fijo de iteraciones).
Alcanzado el equilibrio para ese t, se decrementa por alguna regla y se inician nuevamente los cálculos
El algoritmo finaliza al llegar a un valor de t mínimo en el que prácticamente s’ se acepta sólo si ?< 0, o sea en este punto el algoritmo funciona como una búsquda local simple.
Conjunto de parámetros (o estrategia de enfriamiento): temperatura inicial, regla para decrementar la temperatura y condición de equilibrio
Algoritmos Genéticos
En este enfoque un problema de optimización= encontrar el individuo mas apto (cromosoma) dentro de una población.
Función objetivo relacionada con la función de aptitud (fitness)
Soluciones=individuos o cromosomas
Población es un conjunto de N individuos
Individuo=secuencia (string) de elementos atómicos (genes)
Un gen puede tomar valores en un conjunto predefinido
Algoritmo genético: actúa sobre cromosomas modificando sus componentes de acuerdo a las reglas de la genética, a través de operadores genéticos
Operadores:
newpop (reproducción): obtiene un nuevo individuo tomando en cuenta el fitness de cada individuo de la población actual.
crossover: toma como entrada la nueva población (newpop) y devuelve otra población crosspop. El operador extrae aleatoriamente dos individuos (padres), elige aleatoriamente, por distribución uniforme, el punto de cruzamiento en los cromosomas e intercambia valores a la derecha de este punto generando dos hijos. El operador crossover es utilizado con probabilidad pc. Sirve para mejorar las características de los nuevos individuos
mutación: toma como entrada newpop y deuelve una nueva población mutpop, en la cual algunos individuos sufrieron mutaciones. Cada individuo puede ser seleccionado con probabilidad pm, siendo los seleccionados los que sufren mutación.
Para usar algoritmos genéticos se deben seleccionar una estructura de cromosomas para codificar en ellos las soluciones.
La función de fitness es función de los valores de los genes y debe estar directamente relacionada con la función objetivo.
Algoritmo genético: consiste en aplicar sucesivamente los tres operadores a cada población hasta que finalmente la población última estará compuesta por individuos idénticos, el tipo más apto, la solución óptima.
NOTA: se debe poder comenzar con un cierto conjunto de soluciones factibles
GRASP
GRASP= Greedy Randomized Adaptive Search Procedure
Algoritmo GRASP:
Inicialización
While (criterio de parada no satisfecho)
construir-solución (s)
búsqueda-local(s)
actualizar-sol (s,s*)
fin while
return(s*)
Método de búsqueda local
Método iterativo, una solución factible es construida en cada iteración
En cada iteración:
elección del próximo elemento: se ordenan, de acuerdo a una función ‘golosa’ , todos los elementos disponibles en una lista de candidatos
se elige aleatoriamente un candidato entre los mejores de la lista de candidatos.
Heurística es adaptativa: beneficios asociados a cada elemento son actualizados, de forma de tomar en cuenta la elección hecha en el paso anterior
Heurística es probabilística
RCL=lista restringida de mejores candidatos
Elección aleatoria en RCL permite generar soluciones diferentes en cada iteración
Limitaciones: pueden estar relacionadas con la cardinalidad de la lista y el valor de los elementos en relación a la elección ‘golosa’
Pasos del algoritmo:
1- armar RCL
2- S=elección aleatoria en RCL
3- adaptar función golosa (S)
EJEMPLO 1
Búsqueda local: casi siempre es beneficioso aplicar una búsqueda local en la vecindad de la solución construida de forma de mejorar la que se tiene.
Es común generar varias soluciones iniciales
EJEMPLO 2
Calidad de las soluciones GRASP: análisis formal es difícil
Existe una justificación si se ve GRASP como una técnica de muestreo: en cada iteración GRASP produce una solución muestra de una distribución desconocida de todas las soluciones posibles. Una medida de la varianza de la distribución es el largo de RCL.
Si ? RCL? =1, todas soluciones iguales, varianza es nula
Algoritmo:
1- i=1
2- while i< K
2.1- armar RCL
2.2- elección aleatoria del próximo elemento
2.3- solución completa? No: Adaptar función golosa,
ir a 2.1
2.4- búsqueda local
2.5- actualizar solución óptima
2.6- i=i+1
3- fin while
ANT systems-Colonias de agentes cooperativos
Se basa en imitar el comportamiento de las colonias de hormigas.
Cada hormiga considerada individualmente tiene capacidades básicas pero la colonia logra en conjunto un comportamiento inteligente, como resultado de la interacción entre las hormigas.
Pese a ser insectos casi ciegos logran encontrar el camino mas corto entre el hormiguero y la fuente de comida.
Comunicación por medio de sustancia química dejada como rastro.
Una hormiga se mueve escencialmente al azar pero si encuentra una huella dejada previamente es muy probable que la siga, reforzándola además con su propio rastro.
Esta idea sirve como base para esta heurística, características:
retroalimentación positiva
cálculo distribuído: evita la convergencia prematura
uso de una heurística greedy constructiva: ayuda a encontrar soluciones aceptables en las primeras etapas del proceso de búsqueda
Agentes cooperativos (hormigas): pueden tener memoria, tener cierta inteligencia, etc.
Redes neuronales (RRNN)
Se basa en imitar el comportamiento y forma de comunicación de las neuronas reales
Elemento básico: una neurona. Recibe estímulos como entrada y como salida una señal que es función de las entradas si la intensidad de las entradas supera cierto umbral (?: threshold)
Red: conjunto de elementos simples interconectados Una neurona puede recibir como entrada las salidas de otras.
Las entradas estan ponderadas por coeficientes wij
Diferentes modelos. Modelos en capas
Características RRNN:
tienen fundamento matemático
información almacenada o representada en patrones formados por los wij. Estos patrones se van alterando a medida que pasa la información.
memoria distribuida, con habilidad a resistir al ruido: la pérdida de una unidad de memoria apenas modifica la representación
Una red neuronal se entrena, no programa
Parámetros: función de transferencia, estructura de conexiones y ley de aprendizaje
Buena habilidad para generalizar: aprender exitosamente las características de una categoría de objetos basados en una muestra de esa categoría
Aplicaciones RRNN:
Predicción
(backpropagation, backpropagation recurrente)
Clasificación
(perceptron, redes probabilísticas, mapas auto-organizativos, etc)
Optimización
(Hopfield,Boltzman, Kohonen
Filtros de datos
(Adaline, madaline, recirculación,etc)
 Página anterior | Volver al principio del trabajo | Página siguiente  |