Informe de Experimentación Numérica




descargar 83.05 Kb.
títuloInforme de Experimentación Numérica
fecha de publicación28.02.2016
tamaño83.05 Kb.
tipoInforme
b.se-todo.com > Documentos > Informe


Sistema RutaSoft

Informe de Experimentación Numérica

Versión 1.0



Integrante

Código

Carlos Velez Correa

20047227

Jonathan Pumapillo Gutarra

20052159

Jaime Díaz Riofrío

20060390

Tania Gonzales Villa

20060578

Miguel Benites Regalado

20064934


Historia de Revisión


Fecha

Versión

Descripción

Autor

30/09/10

1.0

Versión inicial

Miguel Benites

Carlos Velez

Jonathan Pumapillo

Jaime Diaz

Tania Gonzales


Tabla de Contenidos


Introducción 4

Definición del problema 4

Presentación de Algoritmos 4

Algoritmo Genético 4

Algoritmo Grasp 5

Variables de respuesta 5

Planeación del experimento 5

Planeamiento de Hipótesis 5

Factores Experimentales 5

Selección del Diseño Experimental 6

Planeación del trabajo experimental 6

Ejecución y análisis 7

Interpretación 9

Conclusiones 9

Informe de Avance

Introducción


El presente documento describe la experimentación numérica realizada con dos algoritmos de resolución de problemas de ruteo de vehículos.

En el documento se describirá el problema planteado, se presentarán los algoritmos a utilizar, la planificación del experimento, la ejecución de experimento, resultados y conclusiones.

Mediante la experimentación numérica se pretende saber que algoritmo es el más adecuado de acuerdo al problema planteado, las hipótesis planteadas, los factores de evaluaciones y pruebas estadísticas.

Definición del problema


El problema planteado (el cual se quiere resolver mediante la experimentación numérica) consiste en determinar la mejor ruta de asignación de clientes sobre una ciudad en particular dado una flota de vehículos cisterna.

Este problema se presenta en una empresa encargada de comercializar y distribuir gas licuado de petróleo a toda una ciudad. La solución que se intenta conseguir es encontrar la ruta óptima de viajes priorizando el menor consumo de combustible para llegar a un cliente.

Presentación de Algoritmos


Los algoritmos seleccionados para la experimentación numérica son el Algoritmos Genético y el Algoritmo Grasp.

Algoritmo Genético



Algoritmo inspirado en la evolución biológica. Consiste en un método de búsqueda dirigida basada en probabilidad. Se empieza con una población de individuos a los cuales se les hace evolucionar al someterlos a acciones aleatorias como mutación y cruzamiento. También existe el proceso de selección que de acuerdo a un criterio se decide cuáles son los individuos más óptimos que sobrevivirán y cuáles son los menos óptimos que serán descartados.
El algoritmo bajo condiciones probabilísticas débiles mantiene un cierto elitismo, es decir siempre guarda las mejores soluciones sin hacerles ningún cambio.
Consideraciones del algoritmo:

  • Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán más iteraciones del algoritmo para "asegurar" el máximo/mínimo global.

  • Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente podemos "asegurar" que encontraremos uno de ellos (no necesariamente el óptimo).



Algoritmo Grasp


Algoritmos que utiliza métodos de construcción y mejora. Es decir se encuentra una solución factible inicial y se mejora mediante un procedimiento de búsqueda local.
Para las soluciones factibles iniciales se usa la lista de candidatos restringidos (RCL) en la que se incluyen a los mejores aspirantes para ser parte de la solución. Una constante de relajación es necesaria para establecer el tamaño de esta lista. Esta constante varia de 0 a 1.

La estructura del algoritmo es la siguiente:
Mientras no se satisfaga el criterio de parada

  1. Construir una solución greedy aleatoria

  2. Aplicar una técnica de búsqueda local a la solución greedy aleatoria obtenida en el paso anterior (para mejorarla)

  3. Actualizar la mejor solución encontrada

Este algoritmo se basa en un criterio del algoritmo voraz, sin embargo es mas eficiente ya que agrega a la solución final los mejores elementos de cada iteración. Dichos elementos se obtienen de forma aleatoria. Las consideraciones y variables que presenta este algoritmo son las siguientes:


Parámetros

Consideraciones

Alfa=0.5

Hallada de manera empirica.

Número de Iteraciones por vehículo=1000

Hallada de manera empirica.


Variables de respuesta


Las variables de respuesta que se usarán para la comparación de los algoritmos son las siguientes:
Variable 1: Cantidad de combustible consumido.

Variable 2: Tiempo de ejecución.

Planeación del experimento




Planeamiento de Hipótesis


La hipótesis con la que se trabajará en la experimentación es la siguiente:
El Algoritmo Genético genera una mejor solución en comparación con la solución del algoritmo Grasp.

Factores Experimentales



Los factores experimentales que se aplicaran según el planteamiento de hipótesis son:


  • La distancia de cada cliente a la planta central.

  • La cantidad de pedidos realizados.

  • El tiempo requerido para obtener la solución.

  • La cantidad mínima de combustible empleado para llegar a un punto dado.



Selección del Diseño Experimental



El experimento planteado se basa en la aceptación o rechazo de pruebas de hipótesis estadísticas. Las conclusiones sobre las hipótesis estarán basadas en la muestra aleatoria de la población.
Se escoge emplear el estadístico T-Student debido a que se analiza muestras de una población normal y se requiere analizar medias utilizando una desviación estándar conocida.
El valor del nivel de riesgo será = 5%. Esto nos indica que se tendrá un 5 % de probabilidad de rechazar la Ho (Hipotesis nula) siendo esta cierta..
Distribución del estadístico t para dos muestras:


Sean:

Si: Varianza muestral del algoritmo i

Ni: Tamaño de las muestras

Planeación del trabajo experimental



Para la ejecución de la experimentación de los algoritmos se contará con el siguiente tipo de información:
Un archivo xml con la información relativa a los pedidos de los clientes que maneja la empresa.
Un método que crea los diferentes tipos de vehículos cisterna con los que cuenta la empresa.
La empresa brindó la siguiente información:
Vehículos: flota de 4 tipos de vehículos cuyo volumen de gas varia entre 8 y 30 toneladas de glp.
Clientes: cartera de 40 clientes con una cantidad promedio de 40 toneladas de glp.
Para cada algoritmo se aplican dichos tipos de datos en sus distintas iteraciones.
Los resultados obtenidos de cada algoritmo son el tiempo de ejecución y uso de combustible diesel total necesario para cada planificación de rutas. A partir de estos datos obtenidos se calcularán el promedio gasto de combustible diesel y del tiempo de ejecución. Luego se calcularán los estadísticos necesarios para aprobar o rechazar las hipótesis planteadas en cada uno de los experimentos.

Ejecución y análisis



Se define la ejecución de la experimentación.

Experimentos

Se describen las variables y las hipótesis utilizadas en el experimento.


  1. Experimento 1

Este experimento permite comprobar cuál de los dos algoritmos, Genetico o Grasp, nos da un menor consumo de combustible en el planeamiento de rutas.
Definición de variables

Se definen las variables aleatorias que definen el gasto de combustible diesel necesario para realizar un plan de rutas.

X1= gasto de combustible del Algoritmo Genético.

X2= gasto de combustible del Algoritmo Grasp.
Las medias de estas variables.

μ1= gasto promedio de combustible del Algoritmo Genético.

μ2= gasto promedio de combustible del Algoritmo Grasp.
Las muestras tomadas de ambas poblaciones de de igual característica y número debido a que se trabaja sobre los mismos datos de entrada.

Planteamiento de hipótesis

Las hipótesis nula y alternativa planteadas para este experimento se describen a continuación.
H0: Mediante el algoritmo Genético se obtiene igual gasto de combustible promedio que con el algoritmo Grasp.

H0: μ1 = μ2

H1: Mediante el algoritmo Grasp se obtiene mayor gasto de combustible que con el algoritmo Genético.

H0: μ2 > μ1
Criterios de decisión

Considerando un nivel de significación =0.05, y seleccionada el estadístico T-Stundet 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 derecha
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.

5.2 Interpretación de resultados

A continuación se describirán los resultados obtenidos.


  1. Experimento 1

Se obtiene el siguiente cuadro con los cálculos más importantes de esta prueba.

Muestra:

Grasp




Genético

118.6855




124.6353

136.298




129.6056

170.274




186.3743

144.7964




136.2349

131.2571




126.1219

151.9261




128.8951

110.2853




112.0712

125.4893




124.6459

107.2508




119.8287

129.5583




149.7476

127.7226




108.4187

128.02




86.0088

124.8651




163.6597

140.1212




148.3029

153.8178




114.1722

164.4529




91.44022

139.131




171.8301

145.3523




118.3443

119.2865




121.7459

142.9583




145.1455



Resultado para una muestra de n=20:


Media

135.5774




130.3614

Desviación

16.68516




25.01842


t = 0.77595

Se rechaza Ho Si t > 1.9845
El valor 1.9845 se halla en la tabla t-Student con los grado de libertad n1+n2 -2 una probabilidad de 0.975 de acuerdo al  definido= 5 % que es la probabilidad de rechazar Ho siendo esta cierta.
Entonces existe un 95 % de grado de confianza aceptar Ho siendo esto válido.
"Como t = 0.77595< 1.9845 se acepta Ho"

Interpretación



Conclusiones


  • El algoritmo Genético es más rápido que el algoritmo Grasp.

  • El algoritmo Grasp en promedio y conforme aumenta la muestra brinda mejores soluciones en promedio que el genético.

  • Las muestras utilizadas para el ejemplo tienen distribución normal

  • El algoritmo genético no es tan preciso conforme aumenta la cantidad de información de entrada, es decir mayor número de pedidos.

  • Para el Sistema se busca un algoritmo que de resultados estables a medida aumenten los pedidos de glp. Estos resultados deben ser eficientes en su uso de combustible diesel para los vehículos cisterna, además la generación de dicho plan de rutas debe ser en el menor tiempo posible. Entonces decidimos que pese a que el Algoritmo GRASP tiene un mayor tiempo de repuesta, es el que se implementara en la solución.





similar:

Informe de Experimentación Numérica iconSumario: Observación preliminar.— Noción, alcance y situaciones más...

Informe de Experimentación Numérica iconPrograma del curso de formación profesional ecologia numerica

Informe de Experimentación Numérica iconProyecto de investigación y experimentacióN

Informe de Experimentación Numérica icon“ Manual de experimentación para docentes y alumnos de primaria”

Informe de Experimentación Numérica iconComprensión verbal (V), fluidez verbal (W), razonamiento (R), espacial...

Informe de Experimentación Numérica iconInstrucciones para cumplimentar el formulario para la introducción...

Informe de Experimentación Numérica iconInforme Avance: 1 Período de Informe

Informe de Experimentación Numérica iconInforme de

Informe de Experimentación Numérica iconInforme no. 51/13

Informe de Experimentación Numérica iconInforme de




Todos los derechos reservados. Copyright © 2015
contactos
b.se-todo.com