7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois

Share this publication

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
??