Dissertação
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
Registro en:
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.
Autor
Santos, Jonatas Cezar Vieira
Institución
Resumen
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. 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. São Cristóvão, SE