Computer Science – Data Structures and Algorithms
Scientific paper
2010-03-23
Evolutionary Computation 19(3), pages 345-371, 2011
Computer Science
Data Structures and Algorithms
25 pages
Scientific paper
10.1162/EVCO_a_00026
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 a population size is one of the most important among them. Most 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 running times. In this paper we propose an adjustable population size. It is calculated as a function of the running time of the whole algorithm and the average running time of the local search for the given instance. Note that in many applications the running time of a heuristic should be limited and therefore we use this limit as a parameter of the algorithm. The average running time of the local search procedure is obtained during the algorithm's run. Some coefficients which are independent with respect to the instance or the local search are to be tuned before the algorithm run; we provide a procedure to find these coefficients. The proposed approach was used to develop a memetic algorithm for the Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) which is an extension of the well-known assignment problem. MAP is NP-hard and has a host of applications. We show that using adjustable population size makes the algorithm flexible to perform well for instances of very different sizes and types and for different running times and local searches. This allows us to select the most efficient local search for every instance type. The results of computational experiments for several instance families and sizes prove that the proposed algorithm performs efficiently for a wide range of the running times and clearly outperforms the state-of-the art 3-AP memetic algorithm being given the same time.
Gutin Gregory
Karapetyan Daniel
No associations
LandOfFree
A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-210941