![Page 1: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/1.jpg)
Investigación AlgorítmicaInvestigación Algorítmica
ChasquiSoftChasquiSoft
![Page 2: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/2.jpg)
IntegrantesIntegrantes
Contreras Ames, Roy CarlosContreras Ames, Roy Carlos 2003703820037038Gaspar Calle, RonaldGaspar Calle, Ronald 2004038520040385Urlich Ames, RafaelUrlich Ames, Rafael 2005027220050272Paredes Anicama, FernandoParedes Anicama, Fernando 2005043820050438Castro Toribio, JorgeCastro Toribio, Jorge 2005203620052036Ruiz Vergara, César AugustoRuiz Vergara, César Augusto 2005723820057238
![Page 3: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/3.jpg)
1.1. IntroducciónIntroducción2.2. Algoritmos Algoritmos
• Heurístico: Primero el mejor.Heurístico: Primero el mejor.• Meta-heurístico: GRASP.Meta-heurístico: GRASP.• Meta-heurístico: Genético. Meta-heurístico: Genético.
3.3. ConclusionesConclusiones4.4. ReferenciasReferencias
AgendaAgenda
![Page 4: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/4.jpg)
• Descripción del problema:Descripción del problema:
El problema consiste en encontrar la distribución El problema consiste en encontrar la distribución de red optima entre un grupo de clientes de una de red optima entre un grupo de clientes de una zona rural y su antena correspondiente para zona rural y su antena correspondiente para poder brindarles los servicios de comunicaciones poder brindarles los servicios de comunicaciones que han solicitado. Se necesita encontrar una que han solicitado. Se necesita encontrar una distribución de red optima mediante el uso de distribución de red optima mediante el uso de algoritmos especializados para disminuir los algoritmos especializados para disminuir los costos del cableado.costos del cableado.
IntroducciónIntroducción
![Page 5: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/5.jpg)
Gráfico de red de un grupo de clientes con su Gráfico de red de un grupo de clientes con su antena correspondiente:antena correspondiente:
IntroducciónIntroducción
![Page 6: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/6.jpg)
AlgoritmosAlgoritmos
![Page 7: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/7.jpg)
Algoritmo HeurísticoAlgoritmo Heurístico
Voraz – El Primero, el mejorVoraz – El Primero, el mejor
![Page 8: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/8.jpg)
Algoritmo Voraz - DefiniciónAlgoritmo Voraz - Definición
Algoritmo HeurísticoAlgoritmo Heurístico
Escoger siempre el mejor elemento en cada paso, Escoger siempre el mejor elemento en cada paso, conocido como el candidato más prometedor, a fin conocido como el candidato más prometedor, a fin de llegar a una solución óptima.de llegar a una solución óptima.
El avance es paso a paso, empezando con un El avance es paso a paso, empezando con un conjunto solución vacío.conjunto solución vacío.
![Page 9: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/9.jpg)
•Conjunto C de candidatos: conjunto de clientes
•Función de selección: determina el cliente más cercano al último cliente seleccionado (candidato prometedor)
•Función de factibilidad: Comprueba que el conjunto de candidatos seleccionados junto al nuevo candidato prometedor permitan llegar a una solución.
Algoritmo Heurístico - ElementosAlgoritmo Heurístico - Elementos
![Page 10: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/10.jpg)
Función objetivo: minimizar el costo del cableado. Se aplica a todo el conjunto solución y está dada por la siguiente fórmula:
f(x) = ∑ ( d * costo_cable ) * factor
Donde:
d = distancia entre cada clientecosto_cable = costo del cable por metroFactor = indica un factor de coste adicional dependiendo del
tipo de terreno donde habita cada cliente.
Algoritmo Heurístico - ElementosAlgoritmo Heurístico - Elementos
![Page 11: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/11.jpg)
Función voraz(C:conjunto):conjunto { C es el conjunto de todos los clientes }
S = {Ø} { S es el conjunto en el que se construye la solución }
mientras C <> vacío hacer x = el elemento de C que maximiza seleccionar(x) C = C - {x} si completable(S U {x}) entonces S = S U {x}
si solucion(S) entonces devolver S
si no devolver no hay solucionfin
Algoritmo Voraz – PseudocódigoAlgoritmo Voraz – Pseudocódigo
![Page 12: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/12.jpg)
•Problema del cambio de dinero
•El problema de la mochila
•El problema de la programación de tareas
•El problema de cortes de una dimensión
•El problema de la selección de proyectos de inversión
Algoritmo Heurístico - AplicaciónAlgoritmo Heurístico - Aplicación
![Page 13: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/13.jpg)
Desventajas
• Miopía.
Ventajas
• Fácil de diseñar e implementar.
• Fácil de comprobar la optimización.
Algoritmo HeurísticoAlgoritmo Heurístico
![Page 14: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/14.jpg)
GraspGrasp
Algoritmo Meta-HeurísticoAlgoritmo Meta-Heurístico
![Page 15: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/15.jpg)
Algoritmo Meta-HeurísticoAlgoritmo Meta-Heurístico
Se basa en métodos probabilísticos.Se basa en métodos probabilísticos.
Usado para problemas de optimización Usado para problemas de optimización combinatoriacombinatoria
Es un algoritmo iterativo.Es un algoritmo iterativo.
Algoritmo GRASP - DefiniciónAlgoritmo GRASP - Definición
![Page 16: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/16.jpg)
Cada iteración presenta 2 fases:Cada iteración presenta 2 fases:
Fase de Fase de Construcción. Considerando una lista Construcción. Considerando una lista restringida de elementos candidatos se restringida de elementos candidatos se selecciona aleatoriamente uno para añadirlo en selecciona aleatoriamente uno para añadirlo en la construcción de la solución.la construcción de la solución.
Fase de Mejora. Realiza una búsqueda local en el Fase de Mejora. Realiza una búsqueda local en el vecindario de la solución construida con el fin de vecindario de la solución construida con el fin de mejorar esta solución.mejorar esta solución.
Algoritmo GRASP - AplicaciónAlgoritmo GRASP - Aplicación
![Page 17: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/17.jpg)
Procedimiento GRASP (numIteraciones, instancia)
Leer (instancia)Mientras <no se cumple con número de iteraciones> hacer
Fase de ConstrucciónFase de MejoraActualizar la mejor solución
Regresar la mejor solución
Fin
Algoritmo GRASP – PseudocódigoAlgoritmo GRASP – Pseudocódigo
![Page 18: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/18.jpg)
VentajasVentajasFacilidad de Facilidad de
implementaciónimplementación
Buena solución con costo Buena solución con costo de procesamiento de procesamiento
razonablerazonable
Puede servir como paso Puede servir como paso previo en la aplicación previo en la aplicación
de otros algoritmosde otros algoritmos
DesventajasDesventajas
No se escoge No se escoge necesariamente la necesariamente la
mejor soluciónmejor solución
Algoritmo GRASPAlgoritmo GRASP
![Page 19: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/19.jpg)
GenéticoGenético
Algoritmo Meta-HeurísticoAlgoritmo Meta-Heurístico
![Page 20: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/20.jpg)
Algoritmo Genético - DefiniciónAlgoritmo Genético - Definición
Son métodos de optimización y búsqueda de Son métodos de optimización y búsqueda de soluciones basados en los postulados de la soluciones basados en los postulados de la evolución biológica y su base genético-evolución biológica y su base genético-molecular.molecular.
![Page 21: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/21.jpg)
Algoritmo Genético - DefiniciónAlgoritmo Genético - Definición• Individuo o cromosoma:Individuo o cromosoma:
Entidad que representan una posible solución.Entidad que representan una posible solución.
• Población:Población:Conjunto de individuos.Conjunto de individuos.
• Función Fitness:Función Fitness:Función evaluadora de la calidad Función evaluadora de la calidad de un individuo como solución a nuestro problema.de un individuo como solución a nuestro problema.
• Cruce:Cruce:Mezcla de la información de dos individuos.Mezcla de la información de dos individuos.
• Mutación:Mutación:Cambio aleatorio en los genes de un individuo.Cambio aleatorio en los genes de un individuo.
• Selección:Selección:Operación donde tienen mayor probabilidadOperación donde tienen mayor probabilidad de ser elegidos de ser elegidos los individuos con mayor valor de función fitness.los individuos con mayor valor de función fitness.
![Page 22: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/22.jpg)
IndividuoIndividuo PoblaciónPoblación Función FitnessFunción Fitness CruceCruce MutaciónMutación SelecciónSelección
Algoritmo Genético - AplicaciónAlgoritmo Genético - Aplicación
![Page 23: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/23.jpg)
Algoritmo Genético – Algoritmo Genético – PseudocódigoPseudocódigo
Procedimiento GENETICO ()
GenerarPoblacionInicial()Mientras <No hay mejora en muchas generaciones> hacer
SeleccionarPadres()Cruce()MutarHijos()EvaluarMutaciones()
Regresar la mejor soluciónFin
![Page 24: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/24.jpg)
VentajasVentajas
Paralelismo Ideal para conjuntos
grandes Adaptativos Sin conocimiento
previo
DesventajasDesventajas
• Complicado de implementar
• Definición de función objetivo correcta
• Convergencia prematura
Algoritmo GenéticoAlgoritmo Genético
![Page 25: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/25.jpg)
Luego del análisis realizado de las ventajas y Luego del análisis realizado de las ventajas y desventajas de cada algoritmo, el equipo desventajas de cada algoritmo, el equipo Chasquisoft ha decidido experimentar con una Chasquisoft ha decidido experimentar con una fusión de dos algoritmos: Grasp-Genético.fusión de dos algoritmos: Grasp-Genético.
ConclusionesConclusiones
![Page 26: Investigación Algorítmica ChasquiSoft. Integrantes Contreras Ames, Roy Carlos 20037038 Gaspar Calle, Ronald20040385 Urlich Ames, Rafael20050272 Paredes](https://reader035.vdocumento.com/reader035/viewer/2022062323/5665b4a71a28abb57c92ef22/html5/thumbnails/26.jpg)
http://www.research.att.com/~mgcr/doc/http://www.research.att.com/~mgcr/doc/gannbib.pdfgannbib.pdf
catarina.udlap.mx/u_dl_a/tales/documentos/catarina.udlap.mx/u_dl_a/tales/documentos/lii/martinez_g_ag/capitulo3.pdflii/martinez_g_ag/capitulo3.pdf
ReferenciasReferencias