Impact of parallel memetic algorithm parameters on its efficacy

Miroslaw Blocho; Jakub Nalepa

doi:10.1007/978-3-319-18422-7_27

Impact of parallel memetic algorithm parameters on its efficacy

Miroslaw Blocho
, Jakub Nalepa

Department of Algorithmics and Software (RAU/RAU5)

Silesian University of Technology
ABB ISDC
Future Processing

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

1 Citation (Scopus)

Abstract

The vehicle routing problem with time windows (VRPTW) is an NP-hard discrete optimization problem with two objectives—to minimize a number of vehicles serving a set of dispersed customers, and to minimize the total travel distance. Since real-life, commercially-available road network and address databases are very large and complex, approximate methods to tackle the VRPTW became a main stream of development. In this paper, we investigate the impact of selecting two crucial parameters of our parallel memetic algorithm—the population size and the number of children generated for each pair of parents—on its efficacy. Our experimental study performed on selected benchmark problems indicates that the improper selection of the parameters can easily jeopardize the search. We show that larger populations converge to high-quality solutions in a smaller number of consecutive generations, and creating more children helps exploit parents as best as possible.

Original language	English
Title of host publication	Communications in Computer and Information Science
Editors	Stanislaw Kozielski, Dariusz Mrozek, Pawel Kasprowski, Bozena Malysiak-Mrozek, Daniel Kostrzewa
Publisher	Springer Verlag
Pages	299-308
Number of pages	10
ISBN (Print)	9783319184210
DOIs	https://doi.org/10.1007/978-3-319-18422-7_27
Publication status	Published - 2015

Publication series

Name	Communications in Computer and Information Science
Volume	521
ISSN (Print)	1865-0929

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 11 Sustainable Cities and Communities

Keywords

Island model
Number of children
Parallel memetic algorithm
Population size
VRPTW

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1007/978-3-319-18422-7_27

Cite this

Blocho, M., & Nalepa, J. (2015). Impact of parallel memetic algorithm parameters on its efficacy. In S. Kozielski, D. Mrozek, P. Kasprowski, B. Malysiak-Mrozek, & D. Kostrzewa (Eds.), Communications in Computer and Information Science (pp. 299-308). (Communications in Computer and Information Science; Vol. 521). Springer Verlag. https://doi.org/10.1007/978-3-319-18422-7_27

@inbook{e2ed4eb3de4b4b798b61aa8e6829b8c6,

title = "Impact of parallel memetic algorithm parameters on its efficacy",

abstract = "The vehicle routing problem with time windows (VRPTW) is an NP-hard discrete optimization problem with two objectives{\textemdash}to minimize a number of vehicles serving a set of dispersed customers, and to minimize the total travel distance. Since real-life, commercially-available road network and address databases are very large and complex, approximate methods to tackle the VRPTW became a main stream of development. In this paper, we investigate the impact of selecting two crucial parameters of our parallel memetic algorithm{\textemdash}the population size and the number of children generated for each pair of parents{\textemdash}on its efficacy. Our experimental study performed on selected benchmark problems indicates that the improper selection of the parameters can easily jeopardize the search. We show that larger populations converge to high-quality solutions in a smaller number of consecutive generations, and creating more children helps exploit parents as best as possible.",

keywords = "Island model, Number of children, Parallel memetic algorithm, Population size, VRPTW",

author = "Miroslaw Blocho and Jakub Nalepa",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.",

year = "2015",

doi = "10.1007/978-3-319-18422-7\_27",

language = "English",

isbn = "9783319184210",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "299--308",

editor = "Stanislaw Kozielski and Dariusz Mrozek and Pawel Kasprowski and Bozena Malysiak-Mrozek and Daniel Kostrzewa",

booktitle = "Communications in Computer and Information Science",

address = "Germany",

}

Impact of parallel memetic algorithm parameters on its efficacy. / Blocho, Miroslaw; Nalepa, Jakub.
Communications in Computer and Information Science. ed. / Stanislaw Kozielski; Dariusz Mrozek; Pawel Kasprowski; Bozena Malysiak-Mrozek; Daniel Kostrzewa. Springer Verlag, 2015. p. 299-308 (Communications in Computer and Information Science; Vol. 521).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Impact of parallel memetic algorithm parameters on its efficacy

AU - Blocho, Miroslaw

AU - Nalepa, Jakub

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - The vehicle routing problem with time windows (VRPTW) is an NP-hard discrete optimization problem with two objectives—to minimize a number of vehicles serving a set of dispersed customers, and to minimize the total travel distance. Since real-life, commercially-available road network and address databases are very large and complex, approximate methods to tackle the VRPTW became a main stream of development. In this paper, we investigate the impact of selecting two crucial parameters of our parallel memetic algorithm—the population size and the number of children generated for each pair of parents—on its efficacy. Our experimental study performed on selected benchmark problems indicates that the improper selection of the parameters can easily jeopardize the search. We show that larger populations converge to high-quality solutions in a smaller number of consecutive generations, and creating more children helps exploit parents as best as possible.

AB - The vehicle routing problem with time windows (VRPTW) is an NP-hard discrete optimization problem with two objectives—to minimize a number of vehicles serving a set of dispersed customers, and to minimize the total travel distance. Since real-life, commercially-available road network and address databases are very large and complex, approximate methods to tackle the VRPTW became a main stream of development. In this paper, we investigate the impact of selecting two crucial parameters of our parallel memetic algorithm—the population size and the number of children generated for each pair of parents—on its efficacy. Our experimental study performed on selected benchmark problems indicates that the improper selection of the parameters can easily jeopardize the search. We show that larger populations converge to high-quality solutions in a smaller number of consecutive generations, and creating more children helps exploit parents as best as possible.

KW - Island model

KW - Number of children

KW - Parallel memetic algorithm

KW - Population size

KW - VRPTW

UR - https://www.scopus.com/pages/publications/84929492635

U2 - 10.1007/978-3-319-18422-7_27

DO - 10.1007/978-3-319-18422-7_27

M3 - Chapter

AN - SCOPUS:84929492635

SN - 9783319184210

T3 - Communications in Computer and Information Science

SP - 299

EP - 308

BT - Communications in Computer and Information Science

A2 - Kozielski, Stanislaw

A2 - Mrozek, Dariusz

A2 - Kasprowski, Pawel

A2 - Malysiak-Mrozek, Bozena

A2 - Kostrzewa, Daniel

PB - Springer Verlag

ER -

Impact of parallel memetic algorithm parameters on its efficacy

Abstract

Publication series

UN SDGs

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this