Ontologies to Lead Knowledge Intensive Evolutionary Algorithms: Principles and Case Study

Ontologies to Lead Knowledge Intensive Evolutionary Algorithms: Principles and Case Study

Carlos Adrian Catania (University of Strasbourg, Strasbourg, France), Cecilia Zanni-Merk (ICube Laboratory/INSA Strasbourg, Strasbourg, France), François de Bertrand de Beuvron (University of Strasbourg, Strasbourg, France) and Pierre Collet (University of Strasbourg, Strasbourg, France)
Copyright: © 2016 |Pages: 23
DOI: 10.4018/IJKSS.2016010105
OnDemand PDF Download:


Evolutionary Algorithms (EA) have proven to be very effective in optimizing intractable problems in many areas. However, real problems including specific constraints are often overlooked by the proposed generic models. The authors' goal here is to show how knowledge engineering techniques can be used to guide the definition of Evolutionary Algorithms (EA) for problems involving a large amount of structured data, through the resolution of a real problem. They propose a methodology based on the structuring of the conceptual model underlying the problem, in the form of a labelled domain ontology suitable for optimization by EA. The case studyfocuses on the logistics involved in the transportation of patients. Although this problem belongs to the well-known family of Vehicle Routing Problems, its specificity comes from the data and constraints (cost, legal and health considerations) that must be taken into account. The precise definition of the knowledge model with thelabelled domain ontology permits the formal description of the chromosome, the fitness functions and the genetic operators.
Article Preview

1. Introduction

In this article, we will show that the use of knowledge engineering can greatly enhance the definition of an evolutionary algorithm for a real case. This study is the result of a collaboration between our team and an Alsatian Patient Transportation Service (PTS), which has provided the real data.

The project is developed under the health care system environment, specifically oriented to the transportation of patients, normally from or to some health care center. The need to develop a specific application arises from the fact that companies that take care of the logistics of the trips must manage a large number of requirements and restrictions when making an itinerary. This logistics affects many enterprise resources, like employees and vehicles, which should be assigned in an efficient way in order to guarantee, among other things, the satisfaction of the patient and the conformity of numerous law regulations.

The problem consists in satisfying the daily requests of the patients while maximizing the benefits, minimizing the costs and fulfilling different constraints. The requests are basically for pick-ups and/or deliveries of the patients to or from their house to some health care center.There are different types of vehicles than can be used for a journey and each of them has an associated cost. There are also the costs for the assignment of a crew, composed by a set of one or two employees, to a given vehicle or for a given patient.

This particular case of Vehicle Routing Problem (VRP) can be defined as a Rich Vehicle Routing Problem (RVRP). According to a recent literature review (Lahyani et al. 2014), RVRP is defined as a problem which simultaneously includes several types of challenging and complicating features. It is associated with the complexity of real-life routing problems.

Many studies concern the Vehicle Routing Problem (Raghavan&Wasil, 2008). These studies can be categorized along two axes:

  • The solving approach; mainly exact algorithms or metaheuristics (stochastic or nature inspired algorithms) (Russell &Norvig, 2009)

  • The variants of the problem; including time windows constraints (Giraldez et al, 2005) or multiple heterogeneous vehicles with pick-up and delivery (Tasan& Gen, 2012), among others.

We have chosen to follow an approach based on Evolutionary Algorithms (EAs) for this specific problem to solve, since we will show in this article that some families of EA and Genetic Algorithms (GA) in particular are suitable for a knowledge driven definition.Genetic algorithms are stochastic search algorithms based on abstraction of the process of Darwinian evolution. They are based on a simple principle: better individuals survive and reproduce more often than other individuals. A classic genetic algorithm maintains a population of individuals, each of them encodes a candidate solution to a given problem. Each individual is evaluated by a fitness function, which measures the quality of its corresponding candidate solution. Then, a selection mechanism identifies the fittest individuals of the current population to serve as parents of the next generation. Hence, the better the quality of an individual, the higher the probability it reproduces and breed to form a next generation. This process is repeated until some stopping criterion. Usual stopping criteria can be that the fitness value is beyond a threshold or that a number of generationshave been reached. To explore the search space, different genetic operators are used during the evolutionary process. Classic genetic algorithms use two operators: mutation and crossover. However, several other operators can be chosen according to the kind of problem.

Even if this problem belongs to the family of Rich Vehicle Routing Problems (RVRP), it soon became clear that the solutions proposed in the literature, as specific as they are (Parragh et al.,2008), (Kilcher&Calvo, 2013), (Paquette et al, 2013) were not intended to take into account all the specific constraints of this particular VRP problem. In addition, we believe that this situation is found in many other optimization problems when the parameters are numerous and varied in nature. Thus, in our example, legal constraints such as the working time of ambulance attendants, or medical constraints such as the disinfection of the vehicles, or the personnel qualification, cannot be overlooked while minimizing costs or distances.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing