Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Estudo e desenvolvimento de algoritmos criptográficos para redes de sensores sem fio, utilizando técnicas de programação genética

Cryptography is the main form to obtain security in any network. Even in networks with great energy consumption restrictions, processing and memory limitations, as the Wireless Sensors Networks (WSN), this is no different. Aiming to improve the cryptography performance, security and the lifetime of these networks, we propose a new cryptographic algorithm developed through the Genetic Programming (GP) techniques. For the development of the cryptographic algorithm’s fitness criteria, established by the genetic GP, nine new cryptographic algorithms were tested: AES, Blowfish, DES, RC6, Skipjack, Twofish, T-DES, XTEA and XXTEA. Starting from these tests, fitness functions was build taking into account the execution time, occupied memory space, maximum deviation, irregular deviation and correlation coefficient. After obtaining the genetic GP, the CRYSEED and CRYSEED2 was created, algorithms for the 8-bits devices, optimized for WSNs, i.e., with low complexity, few memory consumption and good security for sensing and instrumentation applications.

Estudo e desenvolvimento de algoritmos criptográficos para redes de sensores sem fio, utilizando técnicas de programação genética

Cryptography is the main form to obtain security in any network. Even in networks with great energy consumption restrictions, processing and memory limitations, as the Wireless Sensors Networks (WSN), this is no different. Aiming to improve the cryptography performance, security and the lifetime of these networks, we propose a new cryptographic algorithm developed through the Genetic Programming (GP) techniques. For the development of the cryptographic algorithm’s fitness criteria, established by the genetic GP, nine new cryptographic algorithms were tested: AES, Blowfish, DES, RC6, Skipjack, Twofish, T-DES, XTEA and XXTEA. Starting from these tests, fitness functions was build taking into account the execution time, occupied memory space, maximum deviation, irregular deviation and correlation coefficient. After obtaining the genetic GP, the CRYSEED and CRYSEED2 was created, algorithms for the 8-bits devices, optimized for WSNs, i.e., with low complexity, few memory consumption and good security for sensing and instrumentation applications.

Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Verificación de algoritmos y estructuras de datos en Dafny

La verificación formal de un programa es la demostración de que este funciona de acuerdo a una descripción del comportamiento esperado en toda posible ejecución. La especificación de lo deseado puede utilizar técnicas diversas y entrar en mayor o menor detalle, pero para ganarse el título de formal esta ha de ser matemáticamente rigurosa. El estudio y ejercicio manual de alguna de esas técnicas forma parte del currículo común a los estudios de grado de la Facultad de Informática y del itinerario de Ciencias de la Computación de la Facultad de Ciencias Matemáticas de la Universidad Complutense de Madrid, como es el caso de la verificación con pre- y postcondiciones o lógica de Hoare. En el presente trabajo se explora la automatización de estos métodos mediante el lenguaje y verificador Dafny, con el que se especifican y verifican algoritmos y estructuras de datos de diversa complejidad. Dafny es un lenguaje de programación diseñado para integrar la especificación y permitir la verificación automática de sus programas, con la ayuda del programador y de un demostrador de teoremas en la sombra. Dafny es un proyecto en desarrollo activo aunque suficientemente maduro, que genera programas ejecutables.

Aceleración de algoritmos de estimación de movimiento mediante OpenCL

El flujo óptico y la estimación de movimiento es área de conocimiento muy importante usado en otros campos del conocimiento como el de la seguridad o el de la bioinformática. En estos sectores, se demandan aplicaciones de flujo óptico que realicen actividades muy importantes con tiempos de ejecución lo más bajos posibles, llegando a tiempo real si es posible. Debido a la gran complejidad de cálculos que siguen a este tipo de algoritmos como se observará en la sección de resultados, la aceleración de estos es una parte vital para dar soporte y conseguir ese tiempo real tan buscado. Por lo que planteamos como objetivo para este TFG la aceleración de este tipo de algoritmos mediante diversos tipos de aceleradores usando OpenCL y de paso demostrar que OpenCL es una buena herramienta que permite códigos paralelizados con un gran Speedup a la par que funcionar en toda una diversa gama de dispositivos tan distintos como un GPU y una FPGA. Para lo anteriormente mencionado trataremos de desarrollar un código para cada algoritmo y optimizarlo de forma no especifica a una plataforma para posteriormente ejecutarlo sobre las diversas plataformas y medir tiempos y error para cada algoritmo. Para el desarrollo de este proyecto partimos de la teoría de dos algoritmos ya existentes: Lucas&Kanade monoescala y el Horn&Schunck. Además, usaremos estímulos para estos algoritmos muy aceptados por la comunidad como pueden ser el RubberWhale o los Grove, los cuales nos ayudarán a establecer la corrección de estos algoritmos y analizar su precisión, dando así un estudio referencia para saber cual escoger.

PREDIÇÃO DE LINKS EM REDES SOCIAIS ACADÊMICAS: UMA ANÁLISE DA INFLUÊNCIA DAS CARACTERÍSTICAS DA REDE NA EFICÁCIA DOS ALGORITMOS BASEADOS NA TOPOLOGIA

A predição de links em redes sociais tem sido objeto de estudo em um crescente número de artigos científicos e comerciais devido à grande oferta de bases de dados com representações das relações entre pessoas e também devido à facilidade de acesso a recursos computacionais para análise dessas redes. Prever conexões em redes sociais acadêmicas contribui para o crescimento científico, facilitando a colaboração entre pesquisadores com potencial de contribuição mútua. Este trabalho busca identificar as características das redes levam a uma maior eficiência na predição de links feita por algoritmos baseados na topologia. As características serão isoladas conjuntos de dados e alguns experimentos serão repetidos com diferentes algoritmos para buscar identificar tendências. As análises feitas neste trabalho poderão ajudar a compreender melhor a dinâmica das redes sociais acadêmicas e também contribuir na escolha dos melhores algoritmos de predição de link para cada tipo de rede social.

Plataforma de simulación de aberraciones ópticas vía implementación de las características de un SLM y reconstrucción de fase usando algoritmos basados en los sensores de Hartmann-Shack

Dada la importancia que hoy día presenta dentro del ámbito de la óptica, la implementación y conocimiento de dispositivos capaces tanto de generar aberraciones ópticas bien caracterizadas como de censarlas, se presenta a lo largo de este trabajo el desarrollo de una interfaz gráfica en MATLAB, que permita simular el funcionamiento tanto de un sensor de frente de onda de Hartamnn-Shack (HS), así como la simulación de dispositivos capaces de modificar frentes de onda como los SLM, adicionando algoritmos de propagación y cálculo de centroides -- Para ello, se implementarán en primer lugar máscaras de fase que generen frentes de onda aberrados a partir de la modulación en fase de moduladores espaciales de luz o SLM, tanto a través de funciones lente de primer orden en representación de las aberraciones constantes, como de fase cuadrática en representación de las aberraciones de bajo orden y adicionalmente como combinaciones lineales de polinomios de Zernike -- Todo lo anterior se simulará teniendo en cuenta las características técnicas de los SLM, como lo son el número de pixeles en x y en y, el tamaño de estos y la curva de calibración de los moduladores espaciales, tanto para una relación lineal como para una relación no lineal -- Posteriormente se simularán las dos propagaciones sufridas por los haces de luz desde el SLM hasta el CCD (dispositivo de carga acoplada), pasando a través de la matriz de multilentes del HS (MLA), a partir de la implementación de algoritmos de propagación de un solo paso, que nos permitirán observar sobre el plano del CDD el mapa de spots necesario para el censado de las superficies -- Continuaremos con la construcción de algoritmos para determinar los centroides de dicho mapa y sus respectivas coordenadas, seguiremos con la implementación de algoritmos de reconstrucción modal empleados por sensores de frente de onda de Hartmann-Shack, y finalmente compararemos el grado de error existente entre las superficies generadas y las superficies censadas a través del cálculo de su error cuadrático medio

Algoritmos de planificación en redes de paquetes

En este artículo se presentan los mecanismos y procesos necesarios que realizan los enrutadores para ofrecer calidad de servicio en redes de paquetes y se hace especial énfasis en el estudio del estado del arte en lo referente a los algoritmos de planificación utilizados en este tipo de redes.

Simulador gráfico de algoritmos matemáticos

O objetivo principal do trabalho de investigação foi desenvolver uma ferramenta computacional que possa ser usada por professores e alunos no ensino dos Métodos Numéricos. A ferramenta, designada por GraSMA (Graphical Simulator of Mathematical Algorithms), permite visualizar no ecrã a execução dos correspondentes algoritmos. Esta ferramenta integra vários softwares open source e baseia-se na anotação automática de código Octave com funções de inspeção que permitem captar a sucessão de valores e produzir uma animação do funcionamento do método. A validação do GraSMA como ferramenta de apoio à lecionação destes métodos foi feita através de uma experiência feita em contexto de sala de aula que obteve resultados muito positivos conforme será descrito neste artigo.

Algoritmos genéticos

En el presente artículo se presenta el resultado final del proyecto de Investigación sobre Algoritmos Genéticos que se desarrolló con la asesoría del profesional Luis Eduardo Múnera. A medida que los computadores evolucionan, aumenta su capacidad para resolver problemas cada vez más complejos, En muchos campos han superado a los seres humanos, por ejemplo, la rapidez con la que realizan cálculos matemáticos.

Otimização de controle de tráfego em grupo de elevadores com algoritmos bioinspirados

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Mecânica, 2015.

Modelo origen destino para estimar el flujo de tráfico usando algoritmos genéticos

En este trabajo se ha desarrollado un nuevo método basado en Inteligencia Artificial para resolver un problema del matriz origen-destino (O-D) aplicado al caso de una red de tráfico vehicular en la ciudad de Ambato. El método implementado, basado en algoritmos genéticos (AG), resuelve el problema de minimización asociado al problema de matriz O-D. Para validar la técnica, se ha utilizado una red vial correspondiente a la zona del Mercado Modelo en la ciudad de Ambato, que es una zona de alta congestión vehicular.