Búsqueda Tabú

Búsqueda Tabú

Parte 1

Set de datos 1

Matlab:

[pic 1] 

Número de iteraciones: 15

Resolución:

 [pic 2]

Gráfico de la ruta:

[pic 3]

Ruta: 8-14-19-11-3-16-6-17-20-7-21-1-15-13-2-12-10-4-9-18-5  

Distancia total: 432.10

NEOS:

[pic 4]

[pic 5]

Ruta: 0-14-18-12-1-11-9-3-8-17-4-7-13-2-15-10-5-16-19-6-20

Distancia total: 4+38+22+15+15+13+13+15+21+23+14+21+46+14+4+11+32+24+29+

38+21= 433

Comparación de resultados: (porcentaje de desvío)

Comparando, obtenemos que al usar NEOS el cálculo es más rápido, además de que este programa tiende a redondear los resultados. Comparando obtenemos una variación del 0.20%, (que puede ocurrir debido al redondeo de decimales) obteniendo una eficacia en el método de Matlab del 99.79% en cuanto al óptimo obtenido en NEOS.

Set de datos 2:

Matlab: [pic 6]

Número de iteraciones: 6000

Resolución:

[pic 7]

Gráfico de la ruta:

[pic 8]

Ruta: 53-28-46-30-49-31-5-76-1-68-27-13-41-18-52-7-69-3-75-29-63 -74 -2-34-64-17-4 -45-33-10-40-73-59-11-32-26 -56-51 -19- 25- 50-24-57-42-44-43-65-23-62-22-48-37-70-72 -61-71-21-38-6-16-58 -14-55-20-15-60-67-66-39-12-54-8-36-9-47-35

Distancia total: 548.60

NEOS:

[pic 9]

[pic 10]

 Ruta: 0-75-4-68-6-51-17-40-12-58-72-39-9-32-44-3-16-63-33-73-1-62-22-64-42-43-41-56-23-49-24-18-50-25-55-31-10-38-65-11-66-59-14-53-7-35-8-19-54-13-57-15-5-37-20-70-60-71-69-36-47-21-61-28-74-2-30-48-29-45-27-52-46-34-67-26

Distancia total: 3+5+7+5+6+6+7+5+10+5+5+4+7+5+3+9+6+6+5+5+8+8+14+9+5+4+10+6+10+7+13+6+8+9+22+13+7+5+7+7+15+11+7+9+5+5+8+9+8+9+4+8+7+6+6+4+5+9+7+6+6+11+10+6+7+7+7+6+4+6+4+5+2+5+6+6= 538

Comparación de resultados: (porcentaje de desvío)

Comparando, obtenemos que al usar NEOS el cálculo es más rápido, además de que este programa tiende a redondear los resultados. En este caso es probable que la variación haya ocurrido debido a la cantidad de nodos a evaluar. Comparando el método de Matlab con el de NEOS obtenemos una variación del 1.97%, lo cual quiere decir que es probable que a mayor número de datos, es probable que exista un mayor porcentaje de variación.

Parte 2

1. ¿Cuáles son algunos posibles movimientos que se utilizan?

Dentro de la busqueda tabú cada vez que se realiza un movimiento dentro de algun conjunto, se introduce su inverso en una lista circular, de tal forma que los elementos de dicha lista están penalizados durante un cierto tiempo. Por tanto, si un movimiento está en la lista tabú no será aceptado, aunque pueda parecer que sea mejor solución que la solución actual. Algunos otros movimientos de la búsqueda tabu podrían ser dentro de un árbol en un grafo, el añadir o. el retirar aristas según sea el caso.

1. ¿Qué es el criterio de aspiración? y ¿para qué se usa?

Se puede definir al criterio de aspiración como una forma de “olvido estratégico”, la cual permite que un movimiento sea admisible aunque esté clasificado como tabú. El criterio de aspiracion, se compone de dos clases: aspiración de movimiento que cuando se cumple, quita la condición tabú de un movimiento y la aspiración de atributo, que cuando se cumple quita el status tabú del atributo.

Se usa para los siguientes casos:

- Si todos los movimientos posibles son clasificados como tabú, entonces se selecciona el movimiento “menos tabú”.

...