Please use this identifier to cite or link to this item: https://ri.ufs.br/jspui/handle/riufs/10765
Document Type: Dissertação
Title: Utilização de técnicas de redução de dimensionalidade em algoritmos de otimização com muitos objetivos no problema de sincronização de semáforos
Authors: Santos, Jonatas Cezar Vieira
Issue Date: 29-Aug-2018
Advisor: Carvalho, André Britto de
Co-advisor: Matos, Leonardo Nogueira
Resumo : A mobilidade urbana é um problema atual da sociedade moderna e dos grandes centros urbanos. Os Sistemas Inteligentes de Transporte (ITS) utilizam a tecnologia para tentar resolver esses problemas de mobilidade. No contexto de ITS, a gestão de tráfego é uma área que utiliza novos conceitos de organização e manutenção do tráfego, buscando obter um fluxo de tráfego de qualidade. A sincronização de semáforos é um deles e seu principal objetivo é garantir que os veículos tenham uma boa fluidez no trânsito, garantindo percorrer um trajeto em menos tempo possível. Com uma sincronização atingida, as medidas de qualidade tendem a melhorar, como a redução de emissão de poluentes, consumo de combustível, tempo de atraso, velocidade média global e outras. Indicar o melhor tempo semafórico é uma tarefa bastante complexa. É difícil modelar uma situação real, pois existem cadeias de cruzamentos, com características diferentes. A otimização em sincronização de semáforos se classifica como problema NP-Completo, a dificuldade do problema cresce exponencialmente, quando os números de variáveis de decisão e de medidas de qualidades aumentam. Sendo assim, nenhuma técnica clássica seria capaz resolvê-lo em um tempo razoável. Uma solução, é modelar o problema como de otimização, através de um simulador de tráfego. Com o simulador é capaz de construir uma representação computacional semafórica, composta por vias, rotas, veículos, cruzamentos e semáforos. A partir de configurações de condições de fluxo em cenários diferentes, podemos obter essas medidas de qualidades, tratadas como objetivos, extraídas do próprio simulador. O problema é modelado como de otimização multiobjetivo e por trabalhar com mais de 3 funções objetivos, é classificado como de otimização com muitos objetivos. Algoritmos tradicionais enfrentam problemas na otimização com muitos objetivos, uma das técnicas para resolver é a redução de objetivos. O objetivo desse trabalho é utilizar técnicas de aprendizagem de máquina de redução de dimensionalidade, para redução de objetivos no problema de sincronização de semáforos. Foram aplicadas duas técnicas na busca de identificar os objetivos essenciais e descartar os demais para reduzir. As técnicas trabalhadas foram o L-PCA e o K-PCA utilizando os kernels polinomial, RBF e sigmoide. Uma otimização, utilizando os algoritmos NSGA-II e NSGA-III, foi aplicada nos conjuntos contendo todos os objetivos, foram trabalhados 12, e também para os subconjuntos obtidos pela redução. Foram feitas comparações das otimizações entre os conjuntos sem redução e os subconjuntos reduzidos. Além do mais, foram executados testes para identificar se houve diferença estatística entre os algoritmos. Os resultados mostraram que o NSGA-III obteve melhores resultados, e o K-PCA com kernel polinomial foi o melhor algoritmo de redução, conseguindo até superar o NSGA-III sem redução. Concluiu-se também que não houve diferença estatística entre os algoritmos. Portanto, trabalhar com um conjunto menor de objetivos, se tem um desempenho melhor na otimização sem perder a qualidade das informações.
Abstract: Urban mobility is a current problem of modern society and large urban centers. Intelligent Transportation Systems (ITS) use technology to address these mobility issues. In the context of ITS, traffic management is an area that uses new concepts of organization and maintenance of traffic, seeking to achieve a flow of quality traffic. The traffic light synchronization is one of them and its main objective is to ensure that the vehicles have a good fluidity in the traffic, ensuring to cross a route in the shortest possible time. With timing achieved, quality measures tend to improve, such as reducing pollutant emissions, fuel consumption, delay time, overall average speed, and so on. Indicating the best traffic light is a very complex task. It is difficult to model a real situation because there are chains of crosses with different characteristics. The optimization in semaphore synchronization classifies as NP-Complete problem, the difficulty of the problem grows exponentially, when the numbers of decision variables and measures of qualities increase. Therefore, no classical technique would be able to solve it in a reasonable time. One solution is to model the problem as of optimization, through a traffic simulator. With the simulator, it is able to construct a traffic signal representation, composed of roads, routes, vehicles, intersections and traffic lights. From configurations of flow conditions in different scenarios, we can obtain these measures of qualities, treated as objectives, extracted from the simulator itself. The problem is modeled as multiobjective optimization and by working with more than 3 objective functions, it is classified as optimization with many objectives. Traditional algorithms face problems in optimization with many goals, one of the techniques to solve is the reduction of goals. The objective of this work is to use dimensionality reduction machine learning techniques to reduce objectives in the problem of synchronization of traffic lights. Two techniques were applied in the search to identify the essential objectives and discard the others to reduce. The techniques studied were L-PCA and K-PCA using the polynomial, RBF and sigmoid kernels. An optimization, using the NSGA-II and NSGA-III algorithms, was applied in the sets containing all the objectives, were worked 12, and also for the subsets obtained by the reduction. Comparisons of the optimizations between the full sets and the reduced subsets were made. We also performed tests to identify if there was statistical difference between the algorithms. The results showed that the NSGA-III obtained better results, and the K-PCA with polynomial kernel was the best reduction algorithm, even managing to overcome NSGA-III without reduction. It also concluded that there was no statistical difference between the algorithms, thus, to work with a smaller set of objectives, if it has a better performance in the optimization without losing the information quality.
Keywords: Sistemas de transporte inteligente
Sincronização de semáforos
Otimização com muitos objetivos
Redução de objetivos
Intelligent transport systems
Traffic synchronization
Many objective optimization
Goal reduction
Subject CNPQ: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Institution: UFS
Program Affiliation: Pós-Graduação em Ciência da Computação
Citation: SANTOS, Jonatas Cezar Vieira. Utilização de técnicas de redução de dimensionalidade em algoritmos de otimização com muitos objetivos no problema de sincronização de semáforos. 2018. 64 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Sergipe, São Cristóvão, SE, 2018.
URI: http://ri.ufs.br/jspui/handle/riufs/10765
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
JONATAS_CEZAR_VIEIRA_SANTOS.pdf1,59 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.