Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Traffic flow simulation and optimization using evolutionary strategies, Simulación y optimización del flujo del tráfico usando estrategias evolutivas

De
100 pages

Di erent studies, such as the survey that IBM yearly conducts about commuting to work, verify the importance of a well known problem: traffic congestion in big cities. Solving this problem has concerned professionals from many scienti c and technological disciplines, including physics and arti cial intelligence (AI). AI researchers have contributed to mitigate the problem by adapting their techniques to control traffic, obtaining remarkable results. An important tool in AI is the use of Arti cial Neural Networks (ANN), whose numerous features make them a suitable technique in a wide range of problems. However, we found that the use of ANN to control city lights has never been fully seized by any of the past researches, in our opinion, as a consequence of the learning process adopted in their approaches, that was not adequate due to the nature of the problem. This thesis studies the e ect of di erent neuroevolutionary methods in adapting ANNs to efficiently control traffic semaphores. These methods include biological, cultural and linguistic evolution. Furthermore, the performance of this methods is compared with previous approaches using a microscopic traffic simulator, which was enlarged in order to include di erent realistic scenarios in a square shaped city. The study has been implemented using a combination of Java language, Netlogo social simulation environment and Matlab®. The results of this work illustrate the potential of the adaptation of neuroevolutionary concepts to control systems, which opens the door to further research in the topic and possible expansions to other research areas that includes control systems, such as decision support systems in air traffic control or harbor control. ___________________________________________________________________________________________________
Diferentes estudios, como la encuesta que IBM elabora anualmente acerca de los desplazamientos a los lugares de trabajo, verifican la importancia de un problema bien conocido: la congestión en el tráfico que sufren las grandes ciudades. La solución a este problema ha preocupado a profesionales de muchas disciplinas científicas y tecnológicas, incluyendo físicos y expertos en inteligencia artificial (IA). Los investigadores en el campo de la IA han contribuido a mitigar el problema al adaptar sus técnicas al control del tráfico, obteniendo notables resultados. Una importante herramienta en la IA es el uso de Redes de Neuronas Artificiales (RNA), cuyas múltiples caracter´ısticas las hacen una técnica muy apropiada en una gran extensión de problemas. Sin embargo, encontramos que ninguna de las investigaciones anteriores ha aprovechado en su totalidad el uso de las RNA en el control de semáforos, en nuestra opinión, como consecuencia del proceso de aprendizaje adoptado en sus enfoques, el cual no era el adecuado, dada la naturaleza del problema. Esta tesina estudia el efecto de diferentes métodos neuroevolutivos usados para adaptar las RNA para controlar eficientemente semáforos del tráfico. Estos métodos incluyen evolución biológica, cultural y lingüística. Además, el rendimiento de estos métodos se compara con el obtenido por anteriores propuestas usando un simulador de tráfico microscópico, el cual ha sido ampliado para incluir diferentes escenarios realistas, para una ciudad con forma cuadrada. El estudio ha sido implementado usando una combinación del lenguaje de programación JavaTM, el entorno de simulación social NetLogo y Matlab. Los resultados de este trabajo ilustran el potencial adaptativo de los conceptos neuroevolutivos sobre sistemas de control, abriendo una puerta a posteriores investigaciones acerca del tema, y a la posible ampliación hacia otras áreas de investigación que incluyan sistemas de control, como sistemas de apoyo a las decisiones en el control del tráfico aéreo o portuario.
Ingeniería en Informática
Voir plus Voir moins

Aalto University
School of Science
Master’s Programme in Machine Learning and Data Mining
Alejandro L opez Vidal
Tra c ow simulation and optimiza-
tion using evolutionary strategies
Master’s Thesis
Espoo, June 7, 2011
Supervisors: Doc. Timo Honkela, Ph.D., Chief Research Scientist, Aalto
University
Professor Yago S aez Achaerandio, Universidad Carlos III de
Madrid
Instructor: Doc. Timo Honkela, Ph.D., Chief Research ScientistAalto University
School of Science ABSTRACT OF
Master’s Programme in Machine Learning and Data Mining MASTER’S THESIS
Author: Alejandro L opez Vidal
Title:
Tra c ow simulation and optimization using evolutionary strategies
Date: June 7, 2011 Pages: xii + 88
Professorship: Information and Computer Science Code: T-61
Supervisors: Doc. Timo Honkela, Ph.D., Chief Research Scientist
Professor Yago S aez Achaerandio
Instructor: Doc. Timo Honkela, Ph.D., Chief Research Scientist
Di erent studies, such as the survey that IBM yearly conducts about commuting
to work, verify the importance of a well known problem: tra c congestion in
big cities. Solving this problem has concerned professionals from many scienti c
and technological disciplines, including physics and arti cial intelligence (AI). AI
researchers have contributed to mitigate the problem by adapting their techniques
to control tra c, obtaining remarkable results. An important tool in AI is the
use of Arti cial Neural Networks (ANN), whose numerous features make them
a suitable technique in a wide range of problems. However, we found that the
use of ANN to control city lights has never been fully seized by any of the past
researches, in our opinion, as a consequence of the learning process adopted in
their approaches, that was not adequate due to the nature of the problem.
This thesis studies the e ect of di erent neuroevolutionary methods in adapting
ANNs to e ciently control tra c semaphores. These methods include biological,
cultural and linguistic evolution. Furthermore, the performance of this methods
is compared with previous approaches using a microscopic tra c simulator, which
was enlarged in order to include di erent realistic scenarios in a square shaped
city. The study has been implemented using a combination of Java language,
Netlogo social simulation environment and Matlab .
The results of this work illustrate the potential of the adaptation of neuroevo-
lutionary concepts to control systems, which opens the door to further research
in the topic and possible expansions to other research areas that includes control
systems, such as decision support systems in air tra c control or harbor control.
Keywords: Tra c ow, Tra c light, Social simulation, Evolutionary al-
gorithm, Neuroevolution, Biological Evolution, Cultural Evo-
lution, Language emergence, Cellular Automata, Learning Al-
gorithms, Arti cial Neural Network
Language: English
ii
??Acknowledgments
Writing a thesis is not an easy task, and I would not have been able to do
it if it was not for the support of many people, not just during the process
itself, but also during my whole education. First, I want to dedicate this
work to my family, specially my parents Alejandro and Elida Josefa, and my
sister Gloria, because without their support and guidance during all these
years, I would not be the person I am today. I also want to express my
gratitude to all my teachers, specially those who were excel in their work
and passed me more than just knowledge but also values that make me who
I am. I would like to express a special thanks to my supervisor Dr. Timo
Honkela, who directed this work and always believed in me. I certainly do
not forget my friends and colleagues, specially Alberto L., Alberto S., Andre,
Anonio,t Isabel, Katariina, Oscar and Paloma, who not only have supported
me and been with me both the good and the bad times, but also contributed
to this work with their invaluable comments. As a nal note, I would like to
apologize to all of those who I inadvertently omitted in this acknowledgment,
because I cannot possibly name everyone that contributed signi cantly to this
work.
Espoo, June 7, 2011
Alejandro L opez Vidal
iiiAbbreviations and Acronyms
ANN Arti cial Neural Network
EA Evolutionary Algorithms
GSM Global System for Mobile Communications
MLP Multilayer Perceptron
IL Inductive Loop
ITS Intelligent Transportation Systems
SLD Single Inductive Loop Detector
DLD Double inductive loop detector
CLO camera Linkerover
UML Uni ed Modeling Language
SSH Secure Shell Network Protocol
API Application Programing Interface
VNC Virtual Network Computing
SFTP SSH File Transfer Protocol
GNU GNU’s Not Unix
GPL GNU General Public License
JVM Java Virtual Machine
ECA Elementary Cellular Automata
ivNomenclature
coe cient of drag of vehicle i, depending on vehicle’s cross-section andi
its aero-dynamic shape.
v the free- ow speedff
dimensionless slope of the guideway, considering that sin () tan()
being is the angle of the slope
the occupancy time of vehicle ii
reaction time of the driver from vehicle ii
a the acceleration of vehicle ii
f dimensionless coe cient of friction (about 0.3 for cars and buses)
F braking resistance forceb
F uid resistance forcef
F guideway resistance forceg
f friction coe cient between the wheels and the ground, a suitable ap-n
proximation of this coe cient is shown in Eq. 2.5
F propulsive forcep
m 2g acceleration of gravity (about 9:8 =s )
g the time gap of vehicle iri
g the space gap of vehicle isi
h the space headway of vehicle isi
h the time headway of vehicle iti
vK space region of measurement
k density of the tra c ow
k power to weight ratio of the vehicle ii
k the jam densityj
l length of the vehicle ii
m mass of the vehicle ii
N number of vehicles in the measurement region
o on-time. Time period the i vehicle is above the detector.ti
P Lenght of the population
q capacity owcap
q the out ow from a jam to a queue discharge capacityout
R space region of measurement K during an instant dts
R region of measurements corresponding with a region of the road Kt;s
during a given time Tmp
R region of measurements corresponding with a point in the road dxt
during a given time Tmp
t time instant of the passing of vehicle ii
T time of measurementmp
v velocity of the vehicle ii
v vehicle speed relative to the uidr
w the characteristic/kinematic wave speed
x position of vehicle ii
h hour
Km Kilometer
m meter
vipat patch
s second
tic ticks
viiContents
Abbreviations and Acronyms IV
1. Introduction 1
1.1. De nition of the problem . . . . . . . . . . . . . . . . . . . . . 2
1.2. Scope of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Layout of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Tra c ow theory 4
2.1. History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Microscopic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1. Car-following model . . . . . . . . . . . . . . . . . . . 9
2.3. Macroscopic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1. Density . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.2. Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.3. Mean speed . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4. Occupancy . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.5. Fundamental relation of tra c ow theory . . . . . . . 16
2.3.6. Shock waves . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4. Fundamental diagrams and empirical measurements . . . . . . 17
2.4.1. Space-mean speed versus density . . . . . . . . . . . . 19
2.4.2. Flow versus density . . . . . . . . . . . . . . . . . . . . 19
2.4.3. speed versus ow . . . . . . . . . . . . . . 20
2.5. Tra c ow regimes . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1. single-regime models . . . . . . . . . . . . . . . . . . . 21
2.5.2. multi-regime models . . . . . . . . . . . . . . . . . . . 21
2.5.3. 3 states theory . . . . . . . . . . . . . . . . . . . . . . 22
2.6. State of the art . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.1. Marching . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.2. Green wave . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.3. Self organized algorithm (SOLA) . . . . . . . . . . . . 24
2.6.4. Manual tuned system . . . . . . . . . . . . . . . . . . . 26
viii3. Methods and tools 28
3.1. Arti cial Neural Networks: Multilayer Perceptron . . . . . . . 28
3.1.1. Model and topology . . . . . . . . . . . . . . . . . . . 29
3.1.2. Training . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2. Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . 33
3.2.1. General process . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2. Neuroevolution . . . . . . . . . . . . . . . . . . . . . . 36
3.2.3. Cultural Evolution . . . . . . . . . . . . . . . . . . . . 39
3.2.4. Language Emergence . . . . . . . . . . . . . . . . . . . 40
3.3. Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1. Characteristics . . . . . . . . . . . . . . . . . . . . . . 42
3.4. Software tools . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.1. Java 5.0 . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.2. Neural Network Toolbox in Matlab . . . . . . . . . . 44
3.4.3. NetLogo . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.4. Other software . . . . . . . . . . . . . . . . . . . . . . 45
4. Development 47
4.1. Workbench: Overall architecture . . . . . . . . . . . . . . . . . 47
4.1.1. UML Class Diagram . . . . . . . . . . . . . . . . . . . 47
4.1.2. Example of an experiment . . . . . . . . . . . . . . . . 49
4.2. Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1. Simple city . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.2. City with four directions . . . . . . . . . . . . . . . . . 59
4.2.3. City with four and turns . . . . . . . . . . . 59
4.2.4. Fitness Function . . . . . . . . . . . . . . . . . . . . . 60
4.2.5. Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5. Results 63
5.1. Simple city . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1. Biological evolution . . . . . . . . . . . . . . . . . . . . 63
5.1.2. Cultural ev . . . . . . . . . . . . . . . . . . . . 65
5.1.3. Evolving communication . . . . . . . . . . . . . . . . . 67
5.2. Other scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1. City with four directions . . . . . . . . . . . . . . . . . 69
5.2.2. City with four and turns . . . . . . . . . . . 69
6. Discussion and Conclusions 72
6.1. of the results . . . . . . . . . . . . . . . . . . . . . 72
6.2. Validation of the NetLogo simulator . . . . . . . . . . . . . . . 72
6.3. Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
ix
??

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin