An Incremental Evolutionary Approach to Tabu Search

An Incremental Evolutionary Approach to Tabu Search

Yoshinori Suzuki (Iowa State University, USA) and Juan David Cortes (Iowa State University, USA)
Copyright: © 2017 |Pages: 19
DOI: 10.4018/978-1-5225-2322-2.ch006


Based on recent viral transmission events in the swine species, we present a new framework to implement and execute tabu search (TS). The framework mimics the gradual evolutionary process observed when certain flu viruses move from one host population to another. It consists of three steps: (1) executing TS on a smaller subset of the original problem, (2) using one of its promising solutions as an initial solution for a marginally larger problem, and (3) repeating this process until the original problem is reached and solved. Numerical experiments conducted with randomly-generated vehicle routing instances demonstrate interesting results.
Chapter Preview

General Idea

The basic idea of our approach (framework) is inspired by the viral transmission incidents observed between swine (pig) and avian (bird) flues several years ago. These incidents showed that while influenza A virus (bird flu) in its original form can hardly infect human beings, it can transform itself into a new form which can pose threats to humans if it goes through pigs. In other words, while moving directly from birds to humans is an infeasible path for the flu, moving indirectly from birds to humans through pigs is a feasible path (see Figure 1). This means that, although a virus residing in one environment (E1) cannot move to a very different environment (EM) directly, it may be able to eventually transform itself into a new form that can reside in EM if, for example, it goes through an indirect transmission path: E1 → E2 → ... → Em → Em+1 → … → EM, where Em and Em+1 represent different, but similar, living environments (hosts populations) for the virus. Our approach is based on this idea of sequential (and gradual) viral transmission and evolution.

Figure 1.

Viral transmission paths


Complete Chapter List

Search this Book: