1.- Imagina una secuencia de puntos en el espacio, supongamos de momento un espacio bidimensional, osea una superficie.
2.- Iniciemos la tarea con 2 puntos. Encontrar el camino mas corto entre ellos es obvio, no?
3.- Aumentemos la cantidad de puntos, digamos 4, distribuídos aleatoriamente. Para encontrar el camino mas corto basta con ser un buen observador y de ser necesario una regla para medir el largo total de la linea dibujada. Algunas opciones:
Al ser solo cuatro puntos resulta relativamente facil estimar las opciones, basta con partir de 1 y experimentar, (y que la hipotenusa es mas corta que la suma de los catetos..). Pero si quisieramos estar seguros de que el camino elegido es el mas corto, deberiamos medir todas las opciones. ¿Cuantas son?.Si partimos desde cada punto, tendremos cuatro inicios, siendo en todos los casos las siguientes opciones solo tres, ya que el primer punto está seleccionado, y luego dos, y por último sólo el punto que queda. Por lo tanto: Si tenemos 4 puntos, el total de opciones correponde a 4 x 3 x 2 x 1 , o 4! (factorial), y las opciones de circuito corresponderán a n-1! (siendo n = el número de puntos por los cuales se debe pasar), es decir 3! = 6.
Es decir 24 alternativas de recorrido por estos cuatro puntos, algunas de las cuales se enmarcan en un mismo ciclo partiendo desde otro de los tres puntos disponibles. Y ya que cada ciclo se compone de 4 lineas, y que el total de lineas posibles de utilizar al realizar un circuito corresponde a 6, tenemos solo 3 ciclos posibles no redundantes, (nos olvidaremos de esto por el momento).
http://www.tsp.gatech.edu/methods/opt/subtour.htm
4.- Aumentemos los puntos a 10!!, que hacemos? Una opcion es comenzar por cualquiera y elegir el mas cercano cada vez y luego unirlo. Pero como saber que es la mejor opcion? Para estar seguros deberíamos partir de todos los puntos repitiendo el proceso antes nombrado y obtener un largo total para cada uno...lo cual puede ser un poco lento. Las opciones de recorridos corresponderían a 10!, es decir 3.628.800 posibles recorridos! Aún es posible calcularlo pero se deberá optar por un sistema diferente: identificar lo circuitos redundantes para así limitar la cantidad de mediciones. Sin embargo si demoráramos 1 segundo en medir la distancia entre cada punto al revisar el recorrido, nos tomaría 60.480 minutos, es decir 1008 horas, es decir 42 días.
http://www.tsp.gatech.edu/methods/opt/subtour.htm
Este es un buen problema,
Obtener una solucion, no necesariamente la mejor, solo una posible y válida, es muy facil. Pero obtener la mejor solucion puede requerir de un tiempo gigantesco. Esto es lo que se llama el problema del vendedor viajero (TSP, Traveling Salesman Problem), y es un problema que requiere de soluciones no convencionales en cuanto a matemáticas.
Es lo que se llamaría: "problema NP hard"
A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem. NP-hard therefore means "at least as hard as any NP-problem," although it might, in fact, be harder.
DATO !!! : revise
http://fbim.fh-regensburg.de/~saj39122/jfroehl/diplom/e-index.html
(redes neuronales aprendiendo plano de union minimo)
OPCION:
Optimización mediante procesos Heurísticos, esto es, mediante procesos de aproximación iterativa (es decir mediante intentos sucesivos). Esto nos permite buscar en el universo de soluciones posibles una buena (no necesariamente la mejor)
conceptos:
(voy a completar esto...)
a.- Optimo local / Optimo Global
b.- Convergencia en la optimización
c.- Algoritmos de búsqueda Heurística
d.- Algoritmos Genéticos
e.- Algoritmos de Tabú Search
f.- Algoritmos de Simulated Annealing
g.- Metodos de optimización y las metaforas del pensamiento diseñador en la Arquitectura
desarrollo....
a.- Optimo local / Optimo Global
Imagina que todas las medidas de distancia entre todas las posibles combinatorias de los puntos se grafican en un plano, en el que la altura (eje z) representa el largo total, esto correspondería al universo de soluciones en el que buscaremos. Un detalle es que obtener la representacion del universo de soluciones para un problema dado corresponde a obtener todas las soluciones posibles, y en el caso de los problemas NP el tiempo requerido para esto es demasiado. Por lo tanto solo podemos especular sobre las posibilidades de conformacion de este plano.
El optimo global corresponderá al punto mas bajo de este plano (idealmente solo uno), y será este el principal objetivo de busqueda. Las opciones de conformacion de este plano:
- Un valle unico y continuo desde los bordes: esto implica una solucion que puede obtenerse buscando en las cercanías de cualquier solucion y seleccionandola mejor vecina repetidas veces, y cuando no se encuentre una mejor, ya se estará en el fondo (optimo global). Atencion que se deberá cuidar el umbral de busqueda ya que se podrñia generar un salto muy grande en la seleccion del vecino y así oscilar en torno al optimo sin seleccionarlo nunca.
- Una secuencia de valles de diferentes tamaños, distribuidos aleatoriamente entre los cuales uno es el mayor. Esta corresponde a la situación clasica de este tipo de problemas, y cada uno de los valles es lo que se identifica por optimos locales, a los que se llega mediante el proceso de comparación con vecinos, pero de los que es imposible salir ya que esto requeriría seleccionar una solucion peor que la que se tiene durante una secuencia de iteraciones para lograr superar los bordes del valle.
- Una "caja de huevos", la pesadilla de la optimización. Todos los valles son equivalentes, todos son optimos locales y globales al mismo tiempo. Y será imposible saber si hemos llegado a un optimo global por comparación ya que todo sera igual...!!
b.- Convergencia en la optimización
Algo de matemáticas...
...para evaluar un resultado necesitamos sumar el total de lineas que definen el camino a recorrer, para esto debemos obtener la diferencia entre un punto y el siguiente, descompuesto en lso componentes X e Y (las coordenadas cartesianas de cada punto y el cálculo de la distancia euclidiana),
D, corresponde a la distancia total
n, es el número de puntos por los cuales se debe pasar
X e Y, son las coordenadas de cada punto
Esto es lo que se considera la función de evaluación del resultado, es decir la medida de "optimización" conseguida, y el objetivo será que el valor obtenido sea el mínimo.
El grafico anterior correponde a la minimización del resultado en un proceso de optimización, realizado para el curso "Optimizacion en Ingeniería" del magister de informática del DIINF USACH, dictado por el profesor Victor Parada. En este proceso se utilizó la heurística de tabú search, y podemos ver que al inicio el valor disminuye rápidamente, para luego estabilizarse en un valor aproximadoa 190.000, luego de 6300 iteraciones. Luego de esto, el valor baja muy lentamente y se puede detener la búsqueda. Es importante hacer notar que 6300 iteraciones, es probablemente "infinitamente" menor al número total de combinatoria de soluciones al problema, y por lo tanto el tiempo empleado en obtener la solucion fue relativamente poco (menos que la edad del universo entodo caso).
No hay comentarios:
Publicar un comentario