Multiple Traffic Signal Control Using A Genetic Algorithm

T. Kalganova, G.Russell, A. Cumming


Optimising traffic signal timings for a multiple-junction road network is a difficult but important problem. The essential difficulty of this problem is that the traffic signals need to coordinate their behaviours to achieve the common goal of optimising overall network delay. This paper discusses a novel approach towards the generation of optimal signalling strategies, based on the use of a genetic algorithm (GA). This GA optimises the set of signal timings for all junctions in network. The different efficient red and green times for all the signals are  determined by genetic algorithm as well as the offset time for each junction. Previous attempts to do this rely on a fixed cycle time, whereas the algorithm described here attempts to optimise cycle time for each junction as well as proportion of green times. The fitness function is a measure of the overall delay of the network. The resulting optimised signalling strategies were compared against a well-known civil engineering technique, and conclusions drawn.


Full Paper

ගූගල් ට්‍රාන්ස්ලිටරේෂන්

ඔබ මීට පෙර  ගූගල්  විසින් සපයන  ට්‍රාන්ස්ලිටරේෂන් භාවිතා  කර  තිබේද? මෙය සිංහලෙන්  ටයිප් කිරීම  සඳහා  ඉතා හොඳ මෙවලමුකි. මෙම  ලිපිය ටයිප් කළේද මෙම  මෙවලුම භාවිත කිරීමෙනි. ඔබ මේ සඳහා  කල යුත්තේ  සිංහලෙන්  ටයිප් කිරීමට  අවශ්‍යය  වචනය, එහි  ශබ්දය සෑදෙන ආකාරයට ඉංග්‍රීසි අකුරුවලින් ටයිප් කිරීමෙනි.  උදාහරණයක්  ලෙස 'විවෘත' වචනය ගනිමු. මෙම  වචනය ශබ්ද වෙන ආකාරයට ගූගල් ට්‍රාන්ස්ලිටරේෂන් වලදී ඉංග්‍රීසි අකුරුවලින් ටයිප් කරන්නේ 'wiwrutha'  ලෙසය. සමහරක් අමාරු වචන මුලදී ටයිප් කිරීමට අපහසු වුවද පුහුණුවක් ලැබූ පසු මෙය ඉතා පහසු වේ.

ගූගල් ට්‍රාන්ස්ලිටරේෂන් භාවිත කිරීමට ක්‍රම දෙකක් තිබේ.

1. http://www.google.com/transliterate/Sinhalese වෙබ් ලිපිනයට ගොස් එහි ඇති notepad එක භාවිත කර ඔබට අවශ්‍ය ලිපිය ටයිප් කර අවශ්‍ය තැනට පිටපත් කරගැනීම. මේ සඳහා ඉන්ටර්නෙට් පහසුකම ඔබගේ පරිගණකයේ තිබිය යුතුය.


2. http://www.google.com/transliterate/Sinhalese වෙබ් පිටුවේ ඉහළ දකුණු කෙළවරේ ඇති 'Google Transliteration IME' බාගත කොට ඔබගේ පරිගණකයට ස්ථාපනය කිරීම. මෙම මෘදුකාංගය ස්ථාපනය කළවිට  ඔබට  අවශ්‍ය වැඩසටහනට ගොස්  (උදා MS Word)  ඔබගේ පරිගණකයේ  keyboard setting එක Google Transliteration වලට මාරු කිරීම මඟින් එම වැඩසටහනේදී  සිංහලෙන් ටයිප්  කල හැකිය.

මේ පිළිබඳ වැඩි විස්තර Google IME හා Installing Google IME to type in Sinhala  මඟින් ලබා  ගත හැකිය.

IBM Can Predict Floods And Droughts Days In Advance

by Ariel Schwartz Tue Aug 23, 2011

IBM is testing a new system that--using just weather patterns and detailed maps--can accurately predict 100 hours of future river behavior. 

It's four days before a major flash flood will hit your local river. Authorities notify you and your neighbors, giving you all ample time to prepare, or at least enough time to move to higher ground. This isn't just a disaster preparedness obsessive's fantasy. IBM and researchers at the University of Texas at Austin have developed a piece of flood prediction technology that can accurately warn of impending disaster at up to a hundred times faster than other flood prediction models.

The researchers are currently testing the technology on Texas's 230 mile-long Guadalupe River (and over 9,000 miles of its tributaries), where every hour it has been able to generate 100 hours of accurate future river behavior based on weather predictions and precise maps of the river system. "We're taking in a series of data, running it through a simulation and analytics engine, and getting an output of the flow and depth of the river. If you compare the flows and depths to the topography of the [surrounding] land, you can make a prediction of where flooding will occur," explains IBM researcher Fadi Gebara.

The simulation and analytics engine is so efficient because it relies on two other pieces of advanced IBM technology: the ultra-fast POWER7 microprocessor and Deep Thunder, a weather modeling system that is far more accurate than your local weatherman. 

Currently, the gold standard for flood prediction is HEC-Res, a piece of simulation software from the Army Corps of Engineers. But using HEC-Res "to get an understanding of a very local river would take an enormous amount of time," says Gebara.

Gebara believes that IBM's technology could be used for more than just flood prediction; a modified version could also analyze future droughts and water surplus--a particularly attractive prospect for drought-stricken Texas.

The code base for IBM's software is already usable reliable, but Gebara worries that it might not initially get to the places that need it the most. In the U.S., the government provides detailed mapping of rivers and the land sitting next to it--information that is inputted into IBM's engine for more accurate predictions. But this isn't the case everywhere. So even though the technology could easily be deployed in, say, flood-prone Pakistan, it won't work well without detailed data inputs. "The issue is making sure you have good initial conditions to feed [the engine]," explains Gebara.

Still, IBM's flood prediction software will probably pop up soon in cities such as Rio de Janeiro, which already relies on IBM's water and weather analytics know-how. And when the flood waters start rising, residents will be well prepared.

ACS-TS: train scheduling using ant colony system

Keivan Ghoseiri and Fahimeh Morshedsolouk 

This paper develops an algorithm for the train scheduling problem using the ant colony system metaheuristic called ACS-TS. At first, a mathematical model for a kind of train scheduling problem is developed and then the algorithm based on ACS is presented to solve the problem. The problem is considered as a traveling salesman problem (TSP) wherein cities represent the trains. ACS determines the sequence of trains dispatched on the graph of the TSP. Using the sequences obtained and removing the collisions incurred, train scheduling is determined. Numerical examples in small and medium sizes are solved using ACS-TS and compared to exact optimum solutions to check for quality and accuracy. Comparison of the solutions shows that ACS-TS results in good quality and time savings. A case study is presented to illustrate the solution.

Full Paper

Ant Colony Optimization (ACO)

MathWorld

The ant colony algorithm is an algorithm for finding optimal paths that is based on the behavior of ants searching for food.

At first, the ants wander randomly. When an ant finds a source of food, it walks back to the colony leaving "markers" (pheromones) that show the path has food. When other ants come across the markers, they are likely to follow the path with a certain probability. If they do, they then populate the path with their own markers as they bring the food back. As more ants find the path, it gets stronger until there are a couple streams of ants traveling to various food sources near the colony.

Because the ants drop pheromones every time they bring food, shorter paths are more likely to be stronger, hence optimizing the "solution." In the meantime, some ants are still randomly scouting for closer food sources. A similar approach can be used find near-optimal solution to the traveling salesman problem.

Once the food source is depleted, the route is no longer populated with pheromones and slowly decays.

Because the ant-colony works on a very dynamic system, the ant colony algorithm works very well in graphs with changing topologies. Examples of such systems include computer networks, and artificial intelligence simulations of workers.

Picking a cricket 11 via genetic algorithm

The Times of India

'Cricket team selection using Genetic Algorithm'. This is the title of a paper accepted by the International Scientific Committee of the International Congress on Sports Dynamics held in Melbourne on September 1. The paper was presented by S N Omkar, the yoga guru of the Indian cricket team.

Omkar believes his procedure can help pick a team of 15 or so from the hundreds of aspirants. The theory, formulated along with R Verma of Regional Engineering College, Warangal, takes into account performance and fitness data of players and gives an optimised and balanced team with right number of batsmen, bowlers and wicket-keepers without any human interference.

The other paper submitted by Omkar dwells on 'Yogic Sun salutation for better cricketing'. The Bangalore-based IISc scientist explains his work in an exclusive interview to The Times of India . Excerpts:

Could you explain in simple terms the process of team selection through genetic algorithm?

Genetic algorithms are inspired by Darwin's theory of evolution. Simply said, problems are solved by an evolutionary process resulting in a best (fittest) solution (survivor). In other words, the solution is evolved.

The fitness of an organism is measured by its success in its life (survival). Algorithm begins with a set of solutions -- represented by chromosomes -- called population. In the context of the current problem, each population would consist of team cricketers randomly picked from the probables list. Several such teams, say 2000, are formed. A fitness function is evaluated for each team. The fitness function is based on the performance, health condition, experience, etc., of every member in the team. Constraints like number of spinners or fast bowlers required, scope for new players etc., can also be included.

Based on the fitness of each team, new teams with better fitness values are formed by using some operations like crossover and mutation. The new generation of teams thus formed are most likely to be better than the previous ones. This process of forming new generation of teams is continued until a best fitness value is obtained.

How is this procedure different from an evaluation of batting, bowling fielding performances with the help of statistics? What makes it foolproof?

Genetic algorithms belong to the class of stochastic search methods. It optimises the fitness function chosen, thus differing from statistics. Genetic algorithms operate on a population of solutions and in many practical problems they seem to yield good results.

Take for instance a batsman A (somebody like Srikkanth), who is flashy and wants to strike every ball, and musters up an average of 40. And another batsman B (somebody like Shiv Sundar Das perhaps) who is cautious and judicious, but has a batting average of 35. Let's assume other factors are equal. In this case, how does the method work? Who would gain entry into the team?

This can be taken care while defining the fitness or objective function. For example, objective function can include a parameter (strike rate) and more weightage can be given in case one is selecting the team for one-dayers.

Apart from this one can also include factors like performance of any individual against a particular team (within the country /abroad) in the past. Also, an individual's performance on a certain pitch can also be included in the fitness function.

Does this method take into consideration rival strengths too? This is vital in a 'human' selection procedure. For example, if Australia has five left-handers, would we go in for two off-spinners? Again, what kind of spinners __ finger spinners or tweakers?

It is possible. All these depend on how one defines the fitness or objective function.

Can this method evaluate who's the better bat -- Sachin Tendulkar and Brian Lara?

This method is used for optimization.

Artificial Neural Network

Wikipedia

An artificial neural network (ANN), usually called neural network (NN), is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes information using a connectionist approach to computation. In most cases an ANN is an adaptive system that changes its structure based on external or internal information that flows through the network during the learning phase. Modern neural networks are non-linear statistical data modeling tools. They are usually used to model complex relationships between inputs and outputs or to find patterns in data.

The original inspiration for the term Artificial Neural Network came from examination of central nervous systems and their neurons, axons, dendrites, and synapses, which constitute the processing elements of biological neural networks investigated by neuroscience. In an artificial neural network, simple artificial nodes, variously called "neurons", "neurodes", "processing elements" (PEs) or "units", are connected together to form a network of nodes mimicking the biological neural networks — hence the term "artificial neural network".

Because neuroscience is still full of unanswered questions, and since there are many levels of abstraction and therefore many ways to take inspiration from the brain, there is no single formal definition of what an artificial neural network is. Generally, it involves a network of simple processing elements that exhibit complex global behavior determined by connections between processing elements and element parameters. While an artificial neural network does not have to be adaptive per se, its practical use comes with algorithms designed to alter the strength (weights) of the connections in the network to produce a desired signal flow.

These networks are also similar to the biological neural networks in the sense that functions are performed collectively and in parallel by the units, rather than there being a clear delineation of subtasks to which various units are assigned (see also connectionism). Currently, the term Artificial Neural Network (ANN) tends to refer mostly to neural network models employed in statistics, cognitive psychology and artificial intelligence. Neural network models designed with emulation of the central nervous system (CNS) in mind are a subject of theoretical neuroscience and computational neuroscience.

In modern software implementations of artificial neural networks, the approach inspired by biology has been largely abandoned for a more practical approach based on statistics and signal processing. In some of these systems, neural networks or parts of neural networks (such as artificial neurons) are used as components in larger systems that combine both adaptive and non-adaptive elements. While the more general approach of such adaptive systems is more suitable for real-world problem solving, it has far less to do with the traditional artificial intelligence connectionist models. What they do have in common, however, is the principle of non-linear, distributed, parallel and local processing and adaptation.

For more details ...