On the Effects of Incorporating Memory in GC-AIS for the Set Cover Problem

Ayush Joshi, Jonathan E. Rowe, Christine Zarges

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

39 Downloads (Pure)

Abstract

Learning is an important part of the immune system by which the immune system maintains a memory of the infections it has encountered to protect against future attacks. In this paper we incorporate the mechanism of maintaining a memory in the recently proposed GC-AIS algorithm. GC-AIS has shown good performance on the static set cover problem (SCP) in recent work [13] and we are interested in investigating the merits of GC-AIS in a dynamic setting. We compare the affect of GC-AIS with and without a memory approach on the dynamic SCP instances, which are created with varying degrees of modifications to instances from [2]. Three types of modifications are proposed in the paper by adding, removing or editing the subsets from the original problem instances. It is shown that for the case of adding subsets to the original instance using our memory approach is always beneficial while for the case of removing subsets using our memory approach almost always results in worse performance than when not utilising memory. Finally in the cases with editing subsets it is shown that for lower levels of modification using our memory approach gives better results while when the level of modification is higher our memory based approach is worse than using no memory.
Original languageEnglish
Title of host publicationMIC 2015: The XI Metaheuristics International Conference
PublisherUniversity of Lille 1
Publication statusPublished - 2015
Event11th Metaheuristics Internation Conference (MIC 2015) - Agadir, Morocco
Duration: 07 Jun 201510 Jun 2015

Conference

Conference11th Metaheuristics Internation Conference (MIC 2015)
Country/TerritoryMorocco
CityAgadir
Period07 Jun 201510 Jun 2015

Fingerprint

Dive into the research topics of 'On the Effects of Incorporating Memory in GC-AIS for the Set Cover Problem'. Together they form a unique fingerprint.

Cite this