On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the Set Covering Problem

The construction of good starting solutions for multi-start local search heuristics is an important, yet not well-studied problem. In these heuristics, randomization methods are usually applied to explore new promising areas and memory mechanisms are incorporated with the main purpose of reinforcing...

Full description

Saved in:
Bibliographic Details
Published in:Computers & industrial engineering 2006-11, Vol.51 (3), p.362-374
Main Authors: Lan, Guanghui, DePuy, Gail W.
Format: Article
Language:English
Subjects:
Computer memory
Heuristic
Memory
Meta-RaPS
Metaheuristic
Multi-start methods
Randomized algorithms
Set covering
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The construction of good starting solutions for multi-start local search heuristics is an important, yet not well-studied problem. In these heuristics, randomization methods are usually applied to explore new promising areas and memory mechanisms are incorporated with the main purpose of reinforcing good solutions. Under the template of a typical multi-start metaheuristic, Meta-RaPS (Meta-heuristic for Randomized Priority Search), this paper presents several randomization methods and memory mechanisms with a focus on comparing their effectiveness and analyzing their interaction effects. With the Set Covering Problem (SCP) as the application problem, it is found that these randomization methods work well for Meta-RaPS with an improvement phase while the memory mechanisms better the solution quality of the construction phase. The quality and efficiency of Meta-RaPS can be improved through the use of both memory mechanisms and randomization methods. This paper also discovers several efficient algorithms that maintain a good balance between randomness and memory and finds the optimal or best-known solutions for the 65 SCP test instances from the OR-library.
ISSN:0360-8352
1879-0550
DOI:10.1016/j.cie.2006.08.002