 Open Access
 Total Downloads : 423
 Authors : Nabil. Benkheris, Rachida. Ghoul
 Paper ID : IJERTV2IS110176
 Volume & Issue : Volume 02, Issue 11 (November 2013)
 Published (First Online): 08112013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Simulation and optimization of an isolated intersection with genetic algorithms
Nabil. Benkheris 1 ,
(1) Laboratoire d'Automatique et Informatique de Guelma, LAIG
DÃ©partement d'ElectromÃ©canique, Annaba University
Rachida. Ghoul 2
(2) Laboratoire d'Automatique et Informatique de Guelma, LAIG
DÃ©partement d'automatique, USTO University
Abstract
In recent decades, cities have continued to expand with the development of the world economy. It followed a difficult circulation that comes even to traffic congestion during rush hours. The design, the study and the management of Urban Traffic Systems have become increasingly difficult and expensive because of the big number of vehicles and the frequent apparition of congestion which cause a loss of time and difficulties in movement. Our goal is to develop a methodology for modeling static and dynamic components of an elementary cell of urban traffic, a twolane isolated intersection.
We propose hybrid Petri Nets as a modelling tool and we develop a simulator that allows studying the random behaviour of the main actors such as the traffic flow of vehicles in both lanes of the intersection, the inflows and outflows of vehicles to the intersection, the sequences of switching traffic lights… The simulated model enables us to design intelligent control strategies that aim to minimize the lengths of queues, as well as the time lost in the intersection. In a first step we are working on the design of an optimization procedure based on genetic algorithms and Hybrid Petri Nets.
Key words: simulator, system of urban traffic, Hybrid Petri nets, macroscopic modelling, simulation, genetic algorithms.

Introduction
This paper focuses on optimizing the vehicles waiting time in the lanes of the isolated intersection to ensure a smooth flow throughout the road network. Indeed, because of the increasing number of vehicles leading to the emergence of frequent congestions which causes a loss of time and movement difficulty. Regarding the lack of space and the big investments that it necessitates, the only viable solution to deal with this problem is to propose a control methodology and simulation tools to optimize the use of the existing infrastructure.
The issue of urban traffic control appeared with the exponential growth in the number of vehicles on the roads. Therefore, optimizing the waiting time in an intersection has many advantages: first, allow the drivers to save some time, but it is also about reducing pollution and fuel usage, reducing congestion and improving road safety. It turns out that we are all confronted with this situation every day: looking forward to a red crossroads light to turn green … This is also the argument that motivates us to choose the subject. [P. Villard] Crossroads are crucial in the management of urban traffic. Considering that the flow of vehicles can be approximated by a continuous pattern characterized by the flow rates of the vehicles. The switching sequences of the signal (road) lights are composed of discrete events which determine the changes in the traffic situation. The entire system can then be considered as a Hybrid Dynamic System HDS.
In the context of this article, we present the Hybrid Petri Net model that we have developed for modelling the flow of vehicles sequences
interrupted by switching traffic lights at the crossroads in two cases; the first in the case of normal hours and the second in the case of rush hours. Then we describe the simulator that we designed to study the hybrid dynamic behaviour of the traffic. The simulator outputs provide the input vector of the genetic algorithm, which is the optimization procedure, whose role is to calculate the switching times of the intersection traffic lights, which guarantee a smooth flow without congestion or blockage by minimizing the number of vehicles on the lanes of the studied intersection.

Overview of work on the urban traffic
The increase of the traffic flow in urban zones engenders congestion that exceeds the capacity of intersections lights, which are sources of time waste for users and energy consumption, etc.. To face these problems, many methods of urban traffic regulations have been developed primarily to minimize delays and queue lengths. However, most of the developed methods have shown some limitations and are only valid for unsaturated traffic. Henceforth, this field of study has been opened and new approaches have been proposed to deal with the saturation crossroads [C. tolba].
The first studies related to the modelling of traffic are from 1930 [GREE35], the science of traffic has, in fact, been established when the first flow patterns have emerged in the United States in the early 1950s. Since that date, several theories have been built to model the traffic.
The work carried out over the last few decades, have permitted defining solutions for controlling traffic in order to optimize the waiting time of the vehicle in an intersection lane. Works on urban traffic are directed into the following three main areas of research: modelling, control and optimization. Among the most recent works in this area, the thesis of AurÃ©lien CORRÃˆA [A. CORRÃˆA] which provides the resolution of intersection conflicts by Algebra dioÃ¯des and RdP Ptimed and traffic regulation with optimal control. The thesis of EL Hmam Mohamed Said [M. S. EL HMAM]proposes a hybrid modelling approach (between microscopic and macroscopic model) and regulating the flow of traffic through the multi agent systems. Nadir Farhi [N. Farhi] in his thesis proposes a microscopic traffic modelling by Petri nets and an approach to optimize the dynamic flow of vehicles by algebra (min, plus).

Purpose of work
The optimization problem in the intersections is to calculate the moments and the switching times of the traffic lights, which allow avoiding intensive filling and timeouts at the intersections lanes. For this we first modelled the traffics dynamics by Hybrid Petri nets, and then we built a simulator model which provides us the necessary variables in the optimization algorithm based on genetic algorithm. These values are the number of vehicles and lanes output rates.

Modelling urban traffic
Modelling is an essential step in a process of decision support, to which special importance must be given. In fact, before any steps to resolve the studied problem, we first must formulate it well by translating it into a mathematical or graphical model well designed, and should be as complete and accurate as possible, without making it unusable.
Modelling and simulation of urban traffic began in the 1950s. Three approaches have emerged.
Macroscopic modelling considers the traffic as a continuous phenomenon. This model has been widely used because it allows the use of proven physical principles and models. Thus, models derived from fluid dynamics [GREE35] are used. Density (or concentration) K (vehicles / meter), the flow of traffic Q (vehicles / second) and the flow velocity V (meter / second) used verify the fundamental relation Q = KV. Continuous models such as continuous kinetic models can also be used. Macroscopic models are used when the study can be carried out using volumetric data traffic, and when the results of this type are sufficient. However, this type of model does not pemit the analysis of individual movements. They propose a coarse traffic modelling and provide fast results (which makes models suitable for shortterm operational goals). However, their lack of precision can be problematic.
The microscopic modelling allows us to study individual interactions. These models called based entities describe accurately the interactions between vehicles. Among these models, cellular automata, the pursuit model describes the reactions of a vehicle compared to its perception of its environment, particularly, how it reacts with the movements of other vehicles. These models are usually dedicated to a particular purpose (such as the study of lane changes on a highway), and can be used for any type of study since macroscopic valuescan be calculated through microscopic results. Their use in a study of macroscopic objectives must be carried out with caution; they require a large collection of data (and therefore expensive) and are complicated to implement. For example, the study of the highway coating wear does not require an accurate modelling for changing lanes.
A less common approach is mesoscopic. It uses the vehicle but considers them as packet forms. Their movements (lane changes …) are controlled by macroscopic models. It is very well applied in economic research or in the study of movement patterns.[ M. Chabrol]
Modeling is an essential step in a process of decision support, to which a special importance must be given. In fact, before any steps to resolve the problem studied, it must first make it well by translating it into a well designed mathematical model, and should be as complete and accurate as possible, without making it unusable. In this section, we will first give a description of the macroscopic model by Petri nets. Macroscopic models of urban traffic describe the overall behaviour of the vehicles flow by analogy to the movement of a liquid in a tube, where we consider the section of track as the driver of the liquid, which allows us to apply the laws of hydrodynamics).
Inflow Outpu
t flow
For safety reasons at the end of each phase, all lights in the crossroad are
Maintained in red for a certain period. [S. Cohen] In this paper we will make a description of the macroscopic model of an isolated crossroads by Petri nets.

Description of the system
The studied systems are networks of urban roads composed of one or more crossroads. The basic component is a crossroad with two lanes (d1, d2) and two traffic lights (f1, f2) located at the end of the intersection (Figure 1). Free running speed is the maximum speed attainable by a vehicle using the intersection. Traffic flows into two directions: eastwest (EW) and NorthSouth (NS). For simplicity, the lanes are supposed to be oneway and exclude movements turned left and right. Moreover, the traffic light has two states "green" and "red". The duration of the orange light is added to the light red. Several isolated crossroads can be interconnected to form a network of intersections.
Figure 2. Isolated intersection
Infl
ow
section of
Outpu t flow
Table 1. characteristic of lane 1 and lane 2 of the crossroads
Characteristic
lane 1
lane 2
Lane length
375m
375m
lane capacity
50vÃ©h.
50vÃ©h.
Inflow
1650uvp/h/voie
1300uvp/h/voie
Time of the green light
40s
40s
Time of the red light
variable
variable
Cycle time
variable
variable
Characteristic
lane 1
lane 2
Lane length
375m
375m
lane capacity
50vÃ©h.
50vÃ©h.
Inflow
1650uvp/h/voie
1300uvp/h/voie
Time of the green light
40s
40s
Time of the red light
variable
variable
Cycle time
variable
variable
driver of the
Figure 1. Macroscopic model of a road stretch

Relationships and macroscopic parameters:

The average rate of

q (t ,t
, x) n(t1,t2 , x)
(1)
t
t
1 2
2

t1


Modelling isolated crossroad by

The total cycle time of lights:
C = FV + FR (2)

The input rate is measured by suitable sensors installed at the entrance of the track such as the electromagnetic loops.

The outflow ds = Vfree / S (3) With Vfree the speed of entry into the lane and the S the gap between vehicles.

FV: duration of the green light.

FR: duration of red light.
hybrid Petri net
In a controlled intersection, the evolution of the flow of vehicles is determined by the sequences of the red and green lights. Event sequences of traffic lights are modelled by a timed Petri Net . During the switching to the phase of the green light, the maximum duration is 40s in the normal case in the lane two, and 25s in the case of rush hours, the
vehicles flow runs continuously with a medium outflow rate ds2 considered constant in the stationary state. When the light switches to red, the flow of the car is stopped, and the length of the corresponding lane is filled continuously during the red light maximum duration in the normal case 50s and 40s in the rush hours with a medium inflow rate de2 considered constant over a given time interval. The continuous evolution of the cars flow through a complete cycle can be modelled by a continuous Petri net with a constant speed.
For lane 1, the outflow rate is equal to ds1 during the green light: 40s and 30s in case of the rush hours and the inflow rate is equal to de1 during the red light: 50s and 40s in the case of rush hours. The continuing evolution of vehicles flow conditioned by the discrete states of lights gives birth to a hybrid system. The addition of the two models a timed Petri Net and P.N. continued at a constant speed led to the construction of a particular Hybrid P.N called Delementary , where only the discrete model influences the evolution of the continuous model (continuous transition crossing is controlled by marking discrete place). The continuous model has no influence on the discrete one.

Definition of a hybrid P.N [R. David]
H.P.N is a structure HPN = (P, T, h, E, , Pre, Post, Tempo, V, M0), such as:
P = {P1, P2, …, Pn} n is a number of times, P = PC PD with:
PC = {P1, P2, , PnC} is a finite set of continuous places (or Cpluses);
PD = {PnC+1,, PnD} is the finite set of discrete places (or Dplaces);
T = {T1, T2, , Tm} m is a number of transitions,
T= TC TD with:
TC = {T1, T2, , TmC} is a finite set of continuous transitions (or Ctransitions);
TD = {TmC+1,, Tm} is a finite set of continuous transitions (or transitionsC);
V : TC R+ is an application that associates to each Ctransition maximum speed of crossing: M0 is the initial marking, Dspaces contain a positive integer marking and Cspaces contain a positive real mark.

Definition of a Delementary HPNs [L. GHOMRI]
A hybrid DHPN is a basic structure PNHD = (P, T, h, E, , PrÃ©, Post, Tempo, V, M0).
The parameters P, T, h, E, , tempo, V, M0, are identical to those of hybrid PN and Pre and Post are the front and rear incidence application, such as:

(Pi, Tj) PC x TD : PrÃ© (Pi, Tj) = Post (Pi,
Tj)= 0

(Pi, Tj) PD x TC : PrÃ© (Pi, Tj) = Post (Pi, Tj). Conditions (1) and (2) means no arc connects a place to a continuous smooth transition, and if an arc connects a discreet spo Pi continuous transition
Tj, the arc connecting Pi with Tj must exist. Physically this means that the discrete PN evolves independently from continuous Petri nets, but controls the evolution of the latter. Places (p1) and (p2) are initially marked, which corresponds to the initial state (green light in channel 2, and red light in the opposite lane 1). (50) and (40) are the durations of red and green lights. Places (synch) ensure ignition in the two opposite ways synchronization. We note that the TPN modelling the switching sequences of lights is a timed event graph Gdet (where the transition from one state into another is determined by a unique event where there is no conflict and no ambiguity). From the T1 and T4 transitions, the red light is on in both (safety margin). Switching the lights is done through the transition T2. After crossing T2, the lights turn to the opposite state (green light on the
road and red light in channel 2).


Modelling the crossroads by HPNs

Modelling of channel 1 by RdPCC
h: P T {D, C} is an application which designates the discrete nodes, h (x) = D, and continuous nodes, h (x) = C;
E is a finite set of events;
: TD E is a function that associates to each discrete transition to an event E;
P1
number
T1 0.9
P2
number of
Pre and Post denote the impact front and rear applications, these applications must meet the following conditions:
(Pi, Tj) PD x TC : PrÃ© (Pi, Tj) = Post (Pi, Tj) ;
Tempo : TD Q+ is an application that associates to each Dtransition Tj its crossing interval [j, j].
of
vehicles 10
T2
15
0.6
empty spaces
Figure 3. RdPCC of channel 1
The marking of the spot P1 represents the number of vehicles on the path OE. The number of empty spaces in the OE path is shown by the marking of the place P2. The access to the channel is modelled by the transition T1 whose crossing frequency corresponds to the inflow of vehicles that stretch of road, is de. The exit of vehicles of one way is modelled by the T2 transition whose crossing frequency is determined by the outflow of road vehicles which is ds.
6.3.3. Modeling the crossroads by HPNs
continuous model of Channel 2
discrete model of the
intersection lights
continuous model of Channel 1
P9

Modelling lights of the intersection by timed Petri nets TPN:

P1
red light
P5
green light
50 40
0.9
P10
15
d7=3
10
P1
red light 1
P5
green light 2
P2
sych
P6
red light
0.6
T1 50
P2
sych
T2
T4 40
P6
red light 2
P11
5
P12
20
0.6
0.9
P3 P7
green light
40
P4 P8
red light
red light
50
sych
P3
green light 1
P7
red light 2
T3 40 T5 50
P4 P8
red light 2 sych
T6
Figure 4. TPN model lights
Places (p1) and (p2) are initially marked, which corresponds to the initial state (green light in lane 2, and red light in the opposite lane 1). (50) and (40) are the durations of red and green lights respectively. Places (synch) ensure ignition synchronization in two opposite ways lights. We note that the TPN modelling the switching sequences of lights is a timed event graph GDET (where the transition from one state into another is determined by a unique event where there is no conflict and no ambiguity). From the transitions T1 and T4, the red light is turned on in both (safety margin). Switching the lights is made from the transition T2. After crossing of T2, after the crossing to the opposite state (green light in the lane 1 and red lane in the lane 2).
Figure 5. Model RDPH of the isolated intersection
In a controlled intersection, the evolution of the flow of vehicles is determined by the ignition sequence of green and red lights. The sequences of traffic lights are modelled by a timed PN. During the ignition phase of the green light is equal 40s of the lane 2, the flow of vehicles runs out in a continuously at a rate equal to the average output
0.9 pcu / s / lane which is considered constant in steady. When the light switches to red, the flow of vehicles is interrupted, and the section of the corresponding way is filled continuously when the red light equal to 50s with an average inflow equal to 0.6 pcu / s / ch considered constant over a given time interval. The continuous evolution of the cars flow through a complete cycle can be modelled by a continued Petri net with constant speed. For the lane 1, the output rate is equal to 0.6 pcu / s / lane during the green light is 40s and the inflow is equal to 0.9 pcu / s / lane when the red light is equal to 50s.
The continuous evolution of vehicle flow conditioned by the discrete states of lights gives rise to a hybrid system. The addition of the two TPN models and continuous constant speed PN led to the construction of a particular Hybrid PN called Delementary HPNs, where only the discrete model affects the evolution of the continuous model (crossing continuous transition is controlled by
marking discreet place). The continuous model has no influence on the discrete model.


Urban traffic control
Traffic control is a vast area in which several techniques and forms of signalling are used to increase the safety of users, reduce all types of pollution and streamline the operation of road infrastructure. Thus, traffic control is on various aspects such as limiting queues at intersections and
/ or minimizing lost time at traffic lights, to avoid congestion.

Methods of Control
Controlling a network of urban traffic is a complex problem that is often preferable to a modular approach. Several studies in the field provide control algorithms for a single junction. The model of global order is then constructed by the interconnection of basic models. In this paper, we propose a control algorithm with variable threshold, based on the D elementary HPN. But before we begin, we simulate the model of the isolated crossroads in operation controlled by a fixed plan of lights switching, in order to compare and validate the proposed method. Control by variable or controlled threshold is to move to the green light whenever the corresponding way is filled to a maximum limit to avoid congestion, and to turn to the red light (green light in the opposite direction) as soon as the way (which was green) contains a minimum number of vehicles (minimum threshold) to avoid the dead time corresponding to the unnecessary green.

Fixed cycle control: In this case the main control parameters, such as cycle time, green sharing and time difference are calculated offline from a history of data. These light plans are stored in the controller of each junction or in the central office and are applied at different times of the day and week (peak hours, weekends). [S. Cohen].

Control by ordered cycle:
Maximum threshold control method
Switching into the green is done in two cases:

If the maximum time of red light is passed and the maximum number of vehicles is not yet reached, switching to green light is automatic.

Otherwise, if the maximum number of vehicles is reached, the switching is done even if the maximum timing of the red light has not passed.
Control method by mixed threshold
Switching is done if:

The maximum timing of red light is passed and the maximum number of vehicles is not yet reached, switching to green light is automatic.

The maximum number of vehicles switching is achieved, even if the maximum timing of the red light is not passed.

The maximum duration of the green has passed and the minimum number of vehicles is not reached, the switch to the red light is automatic./p>

The minimum number of vehicles is reached and duration of the maximum green is not passed.
7.2. Conclusion 1:
In the first part of this paper, we proposed two control algorithms, which aim to change the cycle and switch the lights. A first fixed control algorithm cycle is a classic method of switching the lights on a fixed plan (50s for the duration of the red light and 40s for the duration of the green light). This method has proved to be unsuitable (congestion, blocking, long queues, …) and especially during times of increased
traffic.
A second control algorithm out of mixed threshold (top and bottom) which consists in switching phases of light when crossing the high threshold that characterizes the state of the street saturation where the light is red. This is to emphasize the reversal of the queue on the way in which the phase of light is "green." Similarly, the switch must be on when the low threshold that characterizes the state of minimum occupancy of the way where the light is green. This is to prevent long queues on the way that the phase of light is "red". In the second part of this paper we work on artificial intelligence techniques such as genetic algorithms, which are to seek an order minimizing a given criterion (lengths of queues, waiting times at the crossroads, …) .




Optimization by genetic algorithms
In this part of the paper, we propose an optimization method based on genetic algorithms to minimize the waiting time of vehicles in a crossroads lane managed by traffic lights. The problem at intersections is about choosing moments and switching times of the intersection lights, to avoid intensive filling and timeouts at the intersection lanes. For this, we thought about using variables calculated by the simulator RDPH, which are the markings in outflow continuous places to achieve an algorithm of optimization based on
geneticalgorithms.

Implementation of the simulator
The simulation field of road traffic is quite large and there are many simulators at the macroscopic level: simulators based on macroscopic models that use the theory of fluid dynamics. In addition, during this era of new technologies that makes the system complex has been implemented, such as ATT (Advanced Transport Telematics), radio guidance, etc.. There are also plans for the creation and development of smart cars [E. Bretz 1999]. In this order of ideas, the simulation of the traffic and transport plays a crucial role, since the implemented control centres need information to divert traffic or to evaluate different strategies to avoid congestion. These are the new challenges that have given rise to the macroscopic traffic simulators.
After establishing RDPH model, we developed a procedure executable by MATLAB software, which simulates the dynamic evolution of the model is the optimization procedure the waiting time of vehicles in the way of the realization of the crossroads RDPH simulator. The results of the simulator are used to construct an optimization algorithm based on genetic algorithms.
Figure 6. Development of a simulator Having in entries, the duration of 4 light
sequences (FV1, FV2, FR1, FR2), the flows of inputs to the ways, the maximum crossroads output speed, the simulator describes the dynamic evolution of the RDPH model by calculating continuous markings m1 and m2, instant corresponding to the number of vehicles on every way as well as the flows out ds1 and ds2. These data are injected into the optimization algorithm that give an objective function judiciously chosen, will determine the best plan of switching lights (durations of different sequences) that guarantee smooth traffic, avoiding roadway overfilling
sections near the intersection.

Assumptions and simulation equations
The inlet flow rates are measured by suitable sensors installed at the entrance of the roads such as the electromagnetic loops.
It is assumed that the duration of the green light never exceeds 40s and the duration of the red light never exceeds 50s.
When m10 and m20 are the initial values of continuous markings m1 and m2 (corresponding to the number of vehicles on the way 1 and 2 at time t
= 0) at the beginning of the simulation.

The equation of marking for the red light on the way 1:
mr1 = de1 * trouge + m10 (4) mr1: the number of vehicles in one lane when the red light is on.
de1: the input flow.
trouge: the duration of the red light. m10: the initial marking.

The outflow equation for the green light on the path 1:
ds1 = Vfree / S (5)
With Vfree, the maximum output rate of the assumed path is equal to 20km / h or 5.55m / s and S intervehicle spacing. So, ds variations depend only on the intervehicle space, i.e the sizes and types of vehicles that occupy the road.

Marking the equation when the green light is turned on in the lane 1
mv1 = (ds1de1). * tvert (6) ds1: the output rate.
de1: the input flow.
tvert: the duration of the green light.

The equation of the total cycle time is: C=tvert+trouge+ts (7)
trouge: the duration of the red light.
ts: time synchronization between the green and red lights. For safety reasons at the end of each phase, all the lights of the intersection remain red for some time (ts).




Optimization with genetic algorithm
9.2. Construction of genetic algorithms:
The optimization is a central topic in operations research. A big number of problems of the decision taking help may be described in the form of optimization problems. The problems of identification, supervised neural networks or the search for the shortest path are, for example, optimization problems.
9.1. Metaheuristic
They make a family of optimization algorithms to solve approximately difficult optimization problems, for which there is no known effective conventional method. They are generally used as generic methods that can handle a wide range of different problems, without requiring major changes in the algorithm used.
Metaheuristics are often classified according to two sets:

Algorithm based on running single solution: The metaheuristic manipulates a point, and decides at every iteration what will be the next point example: Tabu search, the silulÃ© Annealing.

Population method: The metaheuristic manipulates a population of points, a new set of points is selected at each iteration. We find thus the evolutionary algorithms and algorithms of ant colonies.

Basic concepts of a genetic algorithm
Genetic algorithms are part of the family of evolutionary algorithms. They are inspired from the natural evolution. With such methods, it is not to find an exact analytical solution, but to find a good solution in a satisfactory reasonable computation time. The first description of the process of genetic algorithms has been given by Holland in 1975, then Goldberg (1989) used them to solve practical optimization problems.
The purpose of these genetic algorithms is to optimize a predefined function, called objective function or fitness, they are working on a set of candidate solutions, called "population" of individuals or chromosomes (we use either individual or chromosome). They consist of a set of elements, called "genes" that can take multiple values, called "alleles."

The steps of the genetic algorithm
The genetic algorithm begins by generating an initial population of P individuals, for which we calculate their fitness and we select individuals through a selection method. These individuals will be handled by a crossover operator that chooses a probability P_cross. Their results can be transferred by a mutation operator with a mutation probability P_mut. Phases of selection and recombination (crossover nd mutation) are used to generate a new population of individuals that has good chances to be stronger than the previous generation.
Individuals from the recombination phase will be inserted through an insertion method in the new population, we assess the value of the objective function of each of its individuals. From one generation to another, the strength of individuals in the population increases and a stop test will be carried out to decide when to stop the algorithm. Figure 7 shows a diagram of the general functioning of the genetic algorithm.
generating an initial
population size Pm
evaluation of individuals size
evaluation of individuals size
selection for reproduction
selection for reproduction
crossing
crossing
mutation
mutation
until the stopping criterion is checked
evaluation of individuals insertion
Figure 7. General operation of the genetic algorithm
GAs are based on very simple mechanisms (basic manipulation of binary channels), they are robust because they can solve highly nonlinear, discontinuous, and effective problem because they do not develop a solution but a whole population of potential solutions and therefore they have a powerful parallelism. In contrast, for example, to the traditional methods of numerical solutions of gradient type, the AG is not based on an analytical approach, but an iterative and heuristic approach. for this, only some information are necessary for their use: The possible space of research is an efficient criterion corresponding to the fitness.
Main parameters:
The operators of the genetic algorithm are guided by a number of given structural parameters. The value of these parameters affects the success or failure and the speed of a genetic algorithm. We will discuss briefly the role of these parameters in the simple version we have chosen of the AG.
The size of population and the length of the encoding of each individual. If it is too big, computation time of the algorithm can be proved to be very important. If it is too small, it may converge too quickly to the wrong chromosome. The importance of the size is mainly due to the concept of implicit parallelism: the bigger is N, the higher is the number of the evaluated potential solutions in parallel with the GA.
The probability of crossing p_c: generally depends on the form of the performance function. Its choice is often heuristic (just like p_m). The higher it is, more people undergo major changes. Values are generally accepted between 05 and 09.
The mutation probability p_m. This rate is generally low since a high rate may lead to a sub optimal solution by disrupting the one that is optimal. Rather than reducing p_m, another way to prevent tampering with the best individuals is to use elitism: So, we can choose, for example, to reproduce identically the top 5% of the population of each generation, the operator of reproduction is only important within the remaining 95%.

Application of genetic algorithms in urban traffic
In the case of urban traffic, genetic algorithms are applied to an isolated intersection described by its macroscopic model. To optimize the waiting time in the ways of the crossroads by the genetic algorithms we take the following steps:

Initial population: First, we must represent the different states of the variable whose optimal value is sought in a usable form by a GA: the coding. This establishes a connection between the values of the variable and the individuals in the population to in a way to imitate the connection that exists in biology between genotype and phenotype (Some authors do not hesitate to make the parallel with biology and genotype, and talk about the phenotype regarding the binary representation of an individual, and phenotype with respect to its corresponding actual value in the field of research).
The AG starts with a population composed of a random selection of N individuals (chianes and chromosomes) in the chosen encoding. With binary coding, depending on the size 1 of the chain. Prints are made for each individual in {01}, according to a probability distribution (the united distribution is
commonly chosen). The performance of each of these individuals must be assessed.
In the macroscopic case, the basic entity is the lane of the intersection. So, the population is composed of individuals N, each individual is considered a way of crossing.

Composition of an individual: Each individual V is characterized by its genes that differentiate it from other individuals. In our study each lane of the junction is characterized by its macroscopic variables, we obtain:
V = {input rate, output rate, lane capacity, time of green light, time of red light }.
Generation of the initial population Initial size = 100 individuals
In the particular case of a binary coding, a decoding function must allow passage of the binary representation to the representation in terms of states of the initial variable. If this variable takes integer values, we have: d: {0,1} (where l is the length of the chaine). Decoding used is a simple change of basis, and so is the chain: the example below shows the value of the red light cycle 25.
One idea would be to encode each gene on chromosome by a chain of bits.
A = {0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0} can be
decoded so as to give the actual values by the use of matlab software.
The chain A is the actual value is 42 time red light cycle 25 of the 100 cycles.
Four values appeared on the table in the case of normal hours as an example to explain the application of a genetic algorithm on a crossroads. The initial population is initialized randomly. We choose a 16bit binary encoding.
Table 2. encoding and decoding cycle 25 of the original population
Individuals
binary encoding
decoding
The red light
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0
42.00
the green light
1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
34.00
The number of vehicles during the red light
0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
23.00
Marking during the green light
0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0
02.70
Output flow
0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0
00.73
After coding, we must simply define the fitness function by the following formula:
First, the value of the evaluation function in the population is calculated and passes the selection
1
1
1 = . 1
1+ 1 .( 11)
1.( 1 1)
(8)
step.

The Selection: The genetic algorithm uses the method of tournaments to make a selection, this works as follows: first N individuals are selected randomly. The individual with the lowest fitness among N individuals randomly drawn wins the tournament (we draw two individuals randomly in the population and reproduce the best of both in the new population.
We repeat this procedure until the
new population is complete). This process is repeated N times, where N is the population size.
The following table shows the values of the evaluation function before and after the selection.
Tab 3. Selection
Individuals
Before selection
After the selection
1
21.2699
0.6657
2
21.0127
1.5260
3
18.6833
8.1691
4
23.1337
9.9191
6
5
18.6833
10.8787
21.3463
11.5689
7
12.6490
12.2935
8
21.8445
12.6490
9
20.8190
13.7999
10
18.6833
14.2237
This method gives good results. However, as important as the selection phase, it does not create new individuals in the population. This is the role of crossover operators.
We now turn to the part of the cross: the parents are selected randomly. We randomly draw a crossroads; in this paper, we use two potential crossings: the first has a single point (the point of intersection is 9) and the second has two points (the points of intersection is 7 and 12). Crossing then occurs at this location with a probability p_c. The table below shows the effects of this operator to a single point.
Table 4. crossing
Before crossing
After crossing
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0.1500
0.2000
0.3000
0.4000
1.1000
1.2000
1.3000
1.4000
1.4500
2.0500
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
0
0
1
0
0
0
1
0
0
1
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
Table 4 gives the evolution of the 10 best individuals of the population among the 100 individuals in the pitch crosses two points. It is observed that the optimal convergence is much faster when the genetic algorithms are used. Then the replacement operator who decides to replace
Figure 8. Genetic Algorithm for Channel 1 The fitness function:
100% of the population P is applied to the population P is entirely replaced by P 'and its size is fixed:
After several generations, the best fitness results are obtained to optimize waiting time of vehicles in the intersection lanes. This example is part of work and will continue to generate successive generations until the minimum value of fitness game that plays
1 = . 1
1
1
1+ 1 .( 11)
1.( 1 1)
de1: input flow
ds1: output rate of the lane 1 mr1: lane capacity 1
trouge1: time of the red light of the lane 1 Green1: time of the green light from the lane 1 The same genetic algorithm is built for lane 2.
(9)
red state 1
green state 2
optimizing the objective function by genetic algorithms
red state 1
green state 2
optimizing the objective function by genetic algorithms
a role for the new command switch, and the following results are represented by the simulation.
Intput flow
Then the two genetic algorithms are inserted into the global optimization algorithm according to the following scheme:
Output flow
time red light of the lane 1
time green light the lane 1
lane capacity 1
the number of vehicles of the channel 1
methods. We can confirm that the use of genetic algorithms is more efficient than other competing methods and minimizes the time and the number of vehicles at the intersection.
B. Rush hours 7:30 am to 9:00 pm:
Figure 9. Algorithm for global optimization


Simulation and discussion
Table 5. Genetic parameters used in the algorithms
50
40
fitness
fitness
30
20
10
0
0 5 10 15 20 25 30 35 40 45 50
time
Population size (N)
100
number of Variable
05
Length genes in binary
16
Chromosome length in binary
80
Pcroi
0.9
Population size after selection
50
Population size (N)
100
number of Variable
05
Length genes in binary
16
Chromosome length in binary
80
Pcroi
0.9
Population size after selection
50
50
40
fitness
fitnss
9.5.1. The Normal Hours 9:00 am to 11:30 pm 30
20 20
15
fitness
fitness
10
5
0
0 5 10 15 20 25 30 35 40 45 50
time
20
15
fitness
fitness
10
5
0
0 5 10 15 20 25 30 35 40 45 50
time
Figure 10. Optimization of waiting lines
To check the validity of this optimization method, I compare the results of genetic algorithms with the results of other classic commands. In Figure 10, the evaluation represents the optimization of waiting lines of the vehicles in the ways in the period between 09:00 h and 11:30 pm, individuals will be manipulated by two operators of the first crossing by crossing a single point represented by the left figure and the second is represented in two points on the right figure.
The blue line represents the simulation of waiting lines before genetic algorithms applied and the green line shows the simulation of waiting lines after the application of genetic algorithms.
We notice that after the application of genetic algorithms, the waiting lines of vehicles that are the time and the number of vehicles in the intersections lanes decease compared to the other
10
0
0 5 10 15 20 25 30 35 40 45 50
time
Figure 11. Optimization of waiting lines in the rush hours
Figure 11 shows the simulation of the evaluation function to optimize the waiting lines in the case of rush hours, the figure to the left shows the crossing on one single point and the figure on the right represents the crossing on two points.
We represent the method of genetic algorithms by the green line and the conventional method by the blue line. We notice that the method of genetic algorithms is more efficient compared to the other methods even in the case of rush hours.
the duration of the red light
50
the red light
the red light
40
30
20
10
0
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
the duration of the red light
50
the red light
the red light
40
30
20
10
0
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
Figure 12. Optimizing the duration of red lights in the NS and EW roads
The duration of green light
40
the green light
the green light
30
20
10
0
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
The duration of green light
40
the green light
the green light
30
20
10
0
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
Figure 13. Optimizing the duration of green lights in the NS and EW roads.
the number of vehicles of the channel NS for the red light
the number of vehicles
the number of vehicles
30
25
20
15
10
5
0
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
the number of vehicles of the channel EW for the red light
the number of vehicles
the number of vehicles
30
25
20
15
10
5
0
Figures 12, 13 and 14 show the comparison between the simulation results before applying the genetic algorithms and after the application of genetic algorithms in both lanes of the intersection isolated.
Figure 12 shows the optimization of the durations of red lights in both lanes of the intersection NS and EW, we notice that after the application of genetic algorithms, the length of red lights as shown by the blue line is optimized according to the other method represented by the red dotted line justified because the purpose of the genetic algorithm is to give us the best plan for switching the lights. The same with the figure 13 that represents the optimization of green lights.
Figure 14 shows the optimization of the numbers of vehicles in both lanes by genetic algorithms presented by the blue line. We see that the number of vehicles is decreasing in both and that the traffic is more fluid.


Conclusion and perspectives
During this first step, we realized a system based on RDPH simulator to study the dynamic behaviour of the flow of vehicles along the roads of the intersection isolated. During enough time of fluid traffic (out of rush hours) and rush hours. We have constructed a genetic algorithm to optimize filling states pathways by calculating the best plans of switching the intersection lights during the four phases. Once the simulator is completed, it will be the driver for the genetic algorithm to calculate the dial plans of the intersections lights.
Optimize the waiting time hasmany advantages: first save drivers time, but it is also about reducing pollution and fuel use and reduce congestion and improve road safety.
Some perspectives need to be explored: On the level of order, we are working on techniques of artificial intelligence in the context of multicriteria optimization. The modelling level, we plan to address the problem of a network of several intersections. Many methods may be used among other decentralized approaches where intersections are regulated separately, and centralized approaches based on multiagent technology.
0 10 20 30 40 50 60 70 80 90 100
the switching cycles
Figure 14. Optimization of the numbers of vehicles in the NS and EW roads

References

A. CorrÃ©a. "Modelling conflicts in algebra diodes application traffic control at intersections," PhD in Industrial Automation, University of Technology of Belfort Montbeliard, December 18, 2007.

C. Tolba. '' Contribution to the use of Petri nets for modeling and control of urban and interurban traffic,'' thesis to obtain the degree of Doctor of the University of Technology of Belfort Montbeliard, specialty Automation and Computer Science, the December 17, 2004.

D. Goldberg, 1989. Genetic algorithm in search, optimization and machine learning. Addison Wesley. 36

E. Bretz Transportation. IEEE Spectrum, vol. 36, n 1 (January), p. 98103

BD. Greenshields, 1935 A study of traffic capacity. Proceedings of the Highway Research Board. Vol 14, pp. 448477.

L. GHOMRI, H. ALLA, "Hybrid optimal delay systems using dynamic networks of hybrid Petri Control" ROADEF 2011, the 12th annual meeting of the French Society of Operations Research and Decision Support, Saint Etienne, 24 March 2011.

M. Dotoli, M. Pia Fanti, A. Giua and C. Seatzu,'' Modelling Systems by Hybrid Petri Nets: an Application to Supply Chains'', Dip. Elettrotecnica end di Elettronica, Politecnico di Bari.

M. Chabrol, D. Sarramia,'' Modeling System Object Oriented Information Systems Urban Traffic: multiagent approach'' Pascal University, Blaise –
ClermontFerrand II

M. S. EL HMAM,'' Contribution to hybrid modeling and simulation of traffic flow'', PhD Computer Science and Control Engineering, University of Artois, 12 December 2006 .

N. Farhi,'' Modeling Minplus and Control of Regular Towns Traffic'' yhÃ¨se Ph.D., University of Paris I, 2008.

Pierre Villard, tipe: Optimization of waiting times at a crossroads, 2008/2009

R. David, H. Alla, "Discrete, Continuous and Hybrid Petri Nets." Springer. Heidelberg, Germany, October 2004.