On Interdisciplinary Intersection of Unconventional Algorithms and Big Data Processing in Real World Problems: A Real World Example Based on Ho Chi Minh City Traffic

On Interdisciplinary Intersection of Unconventional Algorithms and Big Data Processing in Real World Problems: A Real World Example Based on Ho Chi Minh City Traffic

Ivan Zelinka (VSB Technical University of Ostrava, Czech Republic), Martin Kruliš (KSI, Czech Republic & Charles University in Prague, Czech Republic), Marek Běhálek (VSB Technical University of Ostrava, Czech Republic), Tung Minh Luu (Ton Duc Thang University, Vietnam) and Jaroslav Pokorný (Charles University in Prague, Czech Republic)
DOI: 10.4018/978-1-5225-1054-3.ch015
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Optimization algorithms are a powerful tool for solving many problems of engineering applications from different fields of real life. They are usually used where the solution of a given problem analytically is unsuitable or unrealistic. If implemented in a suitable manner, there is no need for frequent user intervention into the actions of the equipment in which they are used. The majority of the problems of real life applications can be defined as optimization problems, for example, finding the optimum trajectory of a robot, optimal data flows in various processes like city traffic optimization or modelling and optimization of the seasonal variances of supply, traffic and facilities occupation in tourism among the others. The structure of this chapter is such that on the beginning are introduced bio-inspired algorithms, then parallelization of algorithms and parallel hardware and at the end, open research on Ho Chi Minh City traffic optimization real world example is introduced. In Conclusion are discussed possibilities of mutual combinations of introduced methods.
Chapter Preview
Top

Introduction

Heuristic algorithms are a powerful tool for solving many problems of engineering applications from different fields of real life. They are usually used where the solution of a given problem analytically is unsuitable or unrealistic. If implemented in a suitable manner, there is no need for frequent user intervention into the actions of the equipment in which they are used.

The majority of the problems of real life applications can be defined as optimization problems, for example:

  • Finding the optimum trajectory of a robot,

  • The optimum thickness of the wall of a pressure tank,

  • The optimum setting of the regulator's parameters,

  • Optimal data flows in various processes like city traffic optimization or modelling and optimization of the seasonal variances of supply,

  • Traffic and facilities occupation in tourism, amongst the others.

In other words, the solved problem can be transformed into a mathematical problem defined by a suitable prescription, whose optimization leads to finding the arguments of the objective function, which is the goal – the problem solution.

The structure of this chapter is such that on the beginning are introduced bio-inspired (i.e. evolutionary) algorithms, then parallelization of such algorithms and parallel hardware. At the end, we sketch a problem of our research on Ho Chi Minh City traffic optimization as an illustrative real world example. In Conclusion are discussed possibilities of mutual combinations of introduced methods.

Top

Bio-Inspired Algorithms: A Light Overview

Countless examples illustrating problem of bio-inspired algorithms (Back, Fogel & Michalewicz, 1997) and its use on economic as well as industrial problems can be found. The solution of such problems usually requires working with the arguments of optimized functions, where the definition ranges of these arguments may be of a heterogeneous character, such as, for example, the range of integers, real or complex numbers, etc. Moreover, it may happen (depending on the case) that for certain subintervals from the permitted interval of values, the corresponding argument of the optimized function may assume values of various types (integers, real, complex). Besides this, various penalizations and restrictions can play a role within optimization, not only for given arguments, but also for the functional value of the optimized function. In many cases, the analytical solution of such an optimization problem is possible, nevertheless, considerably complicated and tedious. Evolutionary algorithms solve problems in such an elegant manner that they became very popular and are used in many engineering fields.

From the point of view of the most general classification, the evolutionary algorithms belong to heuristic algorithms. Heuristic algorithms are either deterministic or stochastic. The algorithms of the second group differ in that their certain steps use random operations, which means that the results of the solutions obtained with their use may differ in the individual runs of the program. It is therefore meaningful to run the program several times and select the best solution obtained.

Stochastic heuristic methods are sometimes called metaheuristics, because they only provide a general framework and the algorithms of the operation itself must be chosen (for example, by the operation of crossbreeding and mutation in genetic algorithms, operation of neighborhood in simulated annealing, “tabu search”, etc.) in dependence on the problem investigated. Because these methods are frequently inspired by natural processes, they are also called evolutionary algorithms. Depending on their strategy, they can be divided in two classes:

  • Methods based on point-based strategy such as, for example:

    • o

      Simulated annealing, (Kirkpatrick, Gelatt & Vecchi, 1983; Cerny, 1985; Telfar, 1996),

    • o

      Hill-climbing algorithm (Russell, Stuart & Norvig, 2003) and

    • o

      Tabu-search (Glover & Laguna, 1997).

      • These algorithms are based on the neighborhood operation of the current solution, in which we are looking for a better solution, for example by mutation of the original-previous solution.

  • Population-Based Strategy.

    • o

      Genetic algorithms (Davis, 1996; Goldberg, 1989; Michalewicz, 1996; Chu, 1997) are based on population strategy as well as another algorithms like differential evolution, particle swarm, SOMA (Davendra, Zelinka, 2016; Zelinka, 2004), etc.

Complete Chapter List

Search this Book:
Reset