Simulation and optimization of an isolated intersection with genetic algorithms

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 two-lane 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.

1. 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.

2. 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 P-timed 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).

3. 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.

4. 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 short-term 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 values

   can 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.

5. 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: east-west (E-W) and North-South (N-S). For simplicity, the lanes are supposed to be one-way 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

   1. Relationships and macroscopic parameters:

      • The average rate of

   q (t ,t

   , x) n(t1,t2 , x)

   (1)

   t

   t

   1 2

   2

   • t1

6. 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 D-elementary , 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.

   1. 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 C-pluses);

      PD = {PnC+1,, PnD} is the finite set of discrete places (or D-places);

      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 C-transitions);

      TD = {TmC+1,, Tm} is a finite set of continuous transitions (or transitions-C);

      V : TC R+ is an application that associates to each C-transition maximum speed of crossing: M0 is the initial marking, D-spaces contain a positive integer marking and C-spaces contain a positive real mark.

   2. Definition of a D-elementary HPNs [L. GHOMRI]

      A hybrid D-HPN 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:

      1. (Pi, Tj) PC x TD : Pré (Pi, Tj) = Post (Pi,

         Tj)= 0

      2. (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).

   3. Modelling the crossroads by HPNs

      1. 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 D-transition 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

      2. 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 D-elementary 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.

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

   1. 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.

      1. 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].

      2. 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, …) .

8. 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 time-outs 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.

   1. 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.

      1. 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 inter-vehicle spacing. So, ds variations depend only on the inter-vehicle 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 = (ds1-de1). * 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).

9. 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:

   1. 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.

   2. 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.

   1. 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."

   2. 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 non-linear, 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%.

   3. 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:

      1. 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.

      2. 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 16-bit 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.

      3. 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

   4. 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 N-S and E-W 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 N-S and E-W roads.

   the number of vehicles of the channel N-S 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 E-W 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 N-S and E-W, 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.

10. 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 multi-criteria 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 multi-agent 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 N-S and E-W roads

11. References

1. 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.

2. 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.

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

4. E. Bretz Transportation. IEEE Spectrum, vol. 36, n 1 (January), p. 98-103

5. BD. Greenshields, 1935 A study of traffic capacity. Proceedings of the Highway Research Board. Vol 14, pp. 448-477.

6. 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, 2-4 March 2011.

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

8. M. Chabrol, D. Sarramia,'' Modeling System Object Oriented Information Systems Urban Traffic: multi-agent approach'' Pascal University, Blaise –

   Clermont-Ferrand II

9. 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 .

10. N. Farhi,'' Modeling Min-plus and Control of Regular Towns Traffic'' yhèse Ph.D., University of Paris I, 2008.

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

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