2012
Giancarlo
Agenda
1. Objetivo
2. Presentación de algoritmos
3. Variables de Respuesta
4. Planeación de Experimento
5. Planeación del Trabajo Experimental
6. Ejecución de los Experimentos
7. Análisis de los Resultados
8. Interpretación de los Resultados
9. Conclusiones
10. Referencias
Giancarlo
La experimentación numérica y el sentido de su existencia.
• Definir qué algoritmo es el mejor en términos de:
- Tiempo de ejecución
- Gasto de recursos (menor gastos de memoria)
Permitiendo el balanceo de carga de forma eficiente,
para uso futuro.
Nuestra experimentación numérica tendrá como
base, el uso de un estadístico de prueba.
Giancarlo
Requiere de una solución inicial. En nuestro caso esta
solución dependerá de un algoritmo heurístico - Voraz.
Luego de obtener la solución inicial se precede a una
mejora de esta, por lo que se procede a realizar los
movimientos obteniéndose varias soluciones aspirantes a ser
la mejor solución que proporcione la minimización de la
función objetivo.
Giancarlo
André


Compara todos los posibles caminos a través
del grafo entre cada par de vértices.
Complejidad: O(n3)
André
Pseudocódigo
FloydWarshall(camino,n)
Inicializar (camino)
para k: = 1 hasta n
para todo (i,j) en (1..n )
camino[i][j] = mín ( camino[i][j],
camino[i][k]+camino[k][j])

fin para
fin para
André
André
André
Christian
Es un algoritmo para la determinación del camino más
corto dado un vértice origen al resto de vértices en
un grafo con pesos en cada arista.
La idea subyacente en este algoritmo consiste en ir
explorando todos los caminos más cortos que parten
del vértice origen y que llevan a todos los demás
vértices; cuando se obtiene el camino más corto desde
el vértice origen, al resto de vértices que componen el
grafo, el algoritmo se detiene
Christian
Pseudocódigo
dist[s] ←0
(distance to source vertex is zero)
for all v ∈ V–{s}
do dist[v] ←∞
(set all other distances to infinity)
S←∅
(S, the set of visited vertices is initially empty)
Q←V
(Q, the queue initially contains all vertices)
while Q ≠∅
(while the queue is not empty)
do u ← mindistance(Q,dist)
(select the element of Q with the min. distance)
S←S∪{u}
(add u to list of visited vertices)
for all v ∈ neighbors[u]
do if dist[v] > dist[u] + w(u, v)
(if new shortest path found)
then d[v] ←d[u] + w(u, v) (set new value of shortest path)
return dist
Gustavo
Estos serán los indicadores que nos muestren el performance de los algoritmos
Las variables de respuesta para la comparación de los
algoritmos serán las siguientes:
• T: Tiempo total de procesamiento
de información
• C: Costo total de procesamiento de
información, relacionado al tiempo
de información
Gustavo
•Algoritmo Floyd
Gustavo
Planeación de la Hipótesis
Primera
Hipótesis: Experimento 1
El algoritmo “Tabú” obtiene un menor tiempo de
procesamiento en comparación con el algoritmo
“Dijkstra”.
Segunda Hipótesis: Experimento 2
El algoritmo “Tabú” obtiene un menor costo de
procesamiento en comparación con el algoritmo
“Dijsktra”.
Gustavo
Modelo Estadístico a utilizar
T Student
Se ha escogido el modelo estadístico T-Student, tomando como
suposición que la población tiene distribución normal y que las
varianzas de cada población son iguales pero desconocidas, por lo que
se analizarán las medias de los datos. El modelo T-Student a utilizar
es el siguiente:
Gustavo
Modelo Estadístico a utilizar
El modelo T-Student a utilizar es el siguiente:
X1: tiempo o costo de procesamiento del
algoritmo “Tabú”
X2: tiempo o costo de procesamiento del
algoritmo “Dijkstra”
Si: Varianza de la muestra i;
ni: Tamaño de la muestra i;
Para ambos experimentos trabajaremos con un nivel de riesgo 
igual a 5%, el cual nos indica que se tendrá un 5 % de probabilidad de
rechazar la Hipótesis nula cuando esta es en realidad cierta.
Gustavo
Comparación de Tiempos de Procesamiento y Costos de Procesamiento
Inputs
Los datos de entrada para este experimento serán 3 datos
[Ciudad Origen] [Ciudad Destino] [Numero de Paquetes]
Gustavo
Comparación de Tiempos de Procesamiento y Costos de Procesamiento
Outputs
Para la experimentación numérica como datos de salida, luego de cada
ejecución, se obtendrá:
• Tiempo de procesamiento de toda la información (medido en
milisegundos)
• Costo de procesamiento de toda la información (bytes)
Gustavo
Comparación de Tiempos de Procesamiento y Costos de Procesamiento
Cantidad de la muestra
El resultado de cada ejecución de los algoritmos, será el tiempo y costo de
procesamiento de los 45 grafos equivalentes a las ciudades por las que puedo
utilizar. La muestra constará de 41 experimentaciones de cada
uno de los algoritmos. A partir de las experimentaciones se calculará el
tiempo y costo medio de procesamiento, para luego proceder con los cálculos
estadísticos y así aprobar o rechazar la hipótesis inicial.
Gustavo
Comparación de Tiempos de Procesamiento y Costos de Procesamiento
Consideraciones Importantes:
• Se está utilizando un sola PC con 2GB de RAM, con un procesador de 2.4
GHz, 2 núcleos y con un límite de uso del 40% de la memoria para la
ejecución del algoritmo.
Gustavo
Aquí se plantea cada uno los Experimentos
Experimento 1: Comparación de tiempos
Para este experimento, trabajaremos con algoritmos de procesamiento de
información “Tabú” y “Dijkstra” presentados anteriormente con el objetivo de
comprobar cuál de los dos obtiene un menor tiempo de procesamiento de
información.
Experimento 2: Comparación de costos
Para este experimento, trabajaremos con algoritmos de procesamiento de
información “Tabú” y “Dijkstra” presentados anteriormente con el objetivo de
comprobar cuál de los dos obtiene un menor costo de procesamiento de
información.
Gustavo
Aprovecha el tiempo
Planteamiento de hipótesis
Las hipótesis para este experimento son:
• H0: El algoritmo “Tabú” obtiene el mismo tiempo de procesamiento en
comparación con el algoritmo “Dijkstra”.
H0: μ1 = μ2
• H1: El algoritmo “Tabú” obtiene un menor tiempo de procesamiento en
comparación con el algoritmo “Dijkstra”.
H1: μ1 < μ2
Gustavo
Aprovecha el tiempo
Definición de variables
Las variables a utilizar son:
• X1= tiempo de procesamiento del algoritmo “Tabú”.
• X2= tiempo de procesamiento del algoritmo “Dijkstra”.
Considerando:
• μ1 = tiempo promedio de procesamiento del algoritmo “Encolamiento por
criterio”.
• μ2 = tiempo promedio de procesamiento del algoritmo “Ráfaga”.
Gustavo
Ahorra al máximo
Planteamiento de hipótesis
Las hipótesis para este experimento son:
• H0: El algoritmo “Tabú” obtiene el mismo costo de procesamiento en
comparación con el algoritmo “Dijkstra”.
H0: μ1 = μ2
• H1: El algoritmo “Tabú” obtiene un menor costo de procesamiento en
comparación con el algoritmo “Dijkstra”.
H1: μ1 < μ2
Gustavo
Ahorra al máximo
Definición de variables
Las variables a utilizar son:
• X1= costo de procesamiento del algoritmo “Tabú”.
• X2= costo de procesamiento del algoritmo “Dijkstra”.
Considerando:
• μ1 = costo promedio de procesamiento del algoritmo “Tabú”.
• μ2 = costo promedio de procesamiento del algoritmo “Dijkstra”.
Gustavo
Aprovecha el tiempo y Ahorra al máximo
Criterios de decisión
Considerando un nivel de significación =0.05, y seleccionada el estadístico TStudent para realizar la prueba de hipótesis se puede definir la siguiente
región crítica.
R.C. = { T < t1-α,n1+n2-2} : Prueba unilateral de cola izquierda
Si se obtiene un estadístico a partir de los datos obtenidos de la muestra, que
está dentro de la región crítica, entonces se rechaza H0 y se acepta H1. Caso
contrario, se rechaza H1 y se acepta H0.
Es momento de la ejecutar los algoritmos y recoger datos para su comparación
Gustavo
Aprovecha el tiempo
Luego de ejecutar 41 veces el algoritmo 1 y 2 se han obtenido los siguientes
datos estadísticos en base al tiempo de procesamiento:
Estadístico
Media (u2)
Desviación estándar (S2)
Algoritmo 1 Algoritmo 2
Tiempo (ms) Tiempo (ms)
1
18
0.958911
2.644598
Gustavo
Aprovecha el tiempo
Calculamos el valor del estadístico t, en base a la media y desviación estándar:
t
-3.53
n1
41
n2
41
El valor -1.684 se halla en la tabla t-Student con los grado de libertad 40
una probabilidad de 0.95 de acuerdo al  definido= 5 % que es la
probabilidad de rechazar Ho siendo esta cierta.
"Como t = -1.684 > -3.53128961 se rechaza Ho"
Gustavo
Ahorra al máximo
Luego de ejecutar 41 veces el algoritmo 1 y 2 se han obtenido los siguientes
datos estadísticos en base al costo de procesamiento:
Estadístico
Media (u2)
Desviación estándar (S2)
Algoritmo 1 Algoritmo 2
Costo (MB)
Costo (MB)
93
1522
30.810395
31.630584
Ahorra al máximo
Calculamos el valor del estadístico t, en base a la media y desviación estándar:
t
-207.22
n1
41
n2
41
El valor -1.684 se halla en la tabla t-Student con los grado de libertad 40
una probabilidad de 0.95 de acuerdo al  definido= 5 % que es la
probabilidad de rechazar Ho siendo esta cierta.
"Como t = -1.729 > -207.220146 se rechaza Ho"
Gustavo
Aprovecha el tiempo y Ahorra al máximo
Interpretación de los resultados del experimento 1:
Dado que se rechazó la hipótesis Ho, significa que se acepta la
Hipótesis H1. El algoritmo “Tabú” es el que tiene el menor tiempo
de procesamiento.
Interpretación de los resultados del experimento 2:
Dado que se rechazó la hipótesis Ho, significa que se acepta la Hipótesis
H1. El algoritmo “Tabú” es el que tiene el menor costo de
procesamiento.
Gustavo
Nuestro
veredicto
Primer experimento
Como se plantea desde un inicio en nuestras hipótesis. El algoritmo de “Tabú”
tiene un menor tiempo de procesamiento de información. Eso nos lleva a
concluir que deberíamos elegir este algoritmo para dar solución si es el
tiempo es de mayor importancia en la solución del proyecto.
Segundo experimento
Como se plantea desde un inicio en nuestras hipótesis. El algoritmo de “Tabú”
tiene un menor costo de procesamiento de información. Eso nos lleva a
concluir que deberíamos elegir este algoritmo para dar solución si es que la
cantidad de memoria es vital para el problema identificado.
Elegimos del algoritmo tabú el mejor entre
el resto de algoritmo identificados para la
solución del proyecto del curso
Gustavo
•
Ning Yang; Xuan Ma; Ping Li; "An Improved Angle-Based Crossover Tabu Search for the LargerScale Traveling Salesman Problem,"
May 2009
Intelligent Systems, 2009. GCIS '09. WRI Global Congress on , vol.1,
no., pp.584-587, 19-21
•
Ning Yang; Ping Li; Baisha Mei; , "An Angle-Based Crossover Tabu Search for the Traveling
Salesman Problem,"
Aug. 2007
Natural Computation, 2007. ICNC 2007. Third International Conference on ,
vol.4, no., pp.512-516, 24-27
Gustavo
Computer Science Department at Princeton University
2009
Dijkstra's Shortest Path Algorithm
Consulta: 24 de setiembre de 2012
<http://www.google.com.pe/url?sa=t&rct=j&q=dijkstra%20ppt
&source=web&cd=1&cad=rja&ved=0CCQQFjAA&url=http%3A%2F%2Fw
ww.cs.princeton.edu%2F~wayne%2Fkleinberg-tardos%2F04demodijkstra.ppt&ei=VZiUJvjEIuo8QSV6oHgBQ&usg=AFQjCNFfM_WNyPCxOznFZyAAdVQaliIPs
A>
MASSCHUSETTS INSTITUTE OF TECHNOLOGY
2005
Shortest Paths III: All-pairs Shortest
Paths, Matrix Multiplication, FloydWarshall, Johnson
Consulta: 24 de setiembre de 2012
<http://ocw.mit.edu/courses/electricalengineering-and-computer-science/6-046j-introduction-toalgorithms-sma-5503-fall-2005/video-lectures/lecture-19shortest-paths-iii-all-pairs-shortest-paths-matrix-multiplicationfloyd-warshall-johnson/>
•
•
•
•
•
Estadística Aplicada - Manuel Córdova Zamora
http://www.spss.com/es/
http://www.udc.es/dep/mate/estadistica2/cap2.html
www.cs.utexas.edu
http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
Descargar

Diapositivas-Experimentacion