Research Repository

A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem

Karapetyan, Daniel and Gutin, Gregory (2011) 'A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem.' Evolutionary Computation, 19 (3). 345 - 371. ISSN 1063-6560

[img]
Preview
Text
1003.4314v1.pdf - Accepted Version

Download (379kB) | Preview

Abstract

Memetic algorithms are known to be a powerful technique in solving hard optimization problems. To design a memetic algorithm, one needs to make a host of decisions. Selecting the population size is one of the most important among them. Most of the algorithms in the literature fix the population size to a certain constant value. This reduces the algorithm's quality since the optimal population size varies for different instances, local search procedures, and runtimes. In this paper we propose an adjustable population size. It is calculated as a function of the runtime of the whole algorithm and the average runtime of the local search for the given instance. Note that in many applications the runtime of a heuristic should be limited and, therefore, we use this bound as a parameter of the algorithm. The average runtime of the local search procedure is measured during the algorithm's run. Some coefficients which are independent of the instance and the local search are to be tuned at the design time;we provide a procedure to find these coefficients. The proposed approach was used to develop a memetic algorithm for the multidimensional assignment problem (MAP). We show that our adjustable population size makes the algorithm flexible to perform efficiently for a wide range of running times and local searches and this does not require any additional tuning of the algorithm.

Item Type: Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 12:02
Last Modified: 24 May 2018 12:15
URI: http://repository.essex.ac.uk/id/eprint/22072

Actions (login required)

View Item View Item