An elitist genetic heuristic for the K clusters with fixed cardinality problem

Lídia Ludovina Lampreia Caeiro Pica Lourenço; Graça Maria Marques da Silva Gonçalves

An elitist genetic heuristic for the K clusters with fixed cardinality problem

Lídia Ludovina Lampreia Caeiro Pica Lourenço, Graça Maria Marques da Silva Gonçalves

DM - Departamento de Matemática

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

Abstract

We study an elitist genetic heuristic for the K clusters with fixed cardinality problem. The genetic heuristic is based on a specific encoding that identifies the cluster each item is assigned to. A computational experiment is designed to compare the cost of the best feasible solution given by this genetic heuristic (a lower bound), with the lower bound obtained from an enlarged local search algorithm previously developed for this problem. For small instances the genetic lower bound is also compared with the optimum value obtained from a mixed-integer linear formulation defined for this difficult combinatorial problem. The results show good quality genetic heuristic solutions, obtained in short computing time

Original language	Unknown
Title of host publication	Mathematical Models and Methods in Modern Science
Pages	160-165
Publication status	Published - 1 Jan 2012
Event	14th WSEAS International Conference on Mathematical Methods, Computational Techniques and Intelligent Systems (MAMECTIS'12) - Duration: 1 Jan 2012 → …

Conference

Conference	14th WSEAS International Conference on Mathematical Methods, Computational Techniques and Intelligent Systems (MAMECTIS'12)
Period	1/01/12 → …

Cite this

@inproceedings{8b2e1b23d3694215b0e8ff07154077a3,

title = "An elitist genetic heuristic for the K clusters with fixed cardinality problem",

abstract = "We study an elitist genetic heuristic for the K clusters with fixed cardinality problem. The genetic heuristic is based on a specific encoding that identifies the cluster each item is assigned to. A computational experiment is designed to compare the cost of the best feasible solution given by this genetic heuristic (a lower bound), with the lower bound obtained from an enlarged local search algorithm previously developed for this problem. For small instances the genetic lower bound is also compared with the optimum value obtained from a mixed-integer linear formulation defined for this difficult combinatorial problem. The results show good quality genetic heuristic solutions, obtained in short computing time",

keywords = "K clusters, genetic heuristic, elitism, combinatorial problem, fixed cardinality",

author = "Louren{\c c}o, {L{\'i}dia Ludovina Lampreia Caeiro Pica} and Gon{\c c}alves, {Gra{\c c}a Maria Marques da Silva}",

year = "2012",

month = jan,

day = "1",

language = "Unknown",

isbn = "978-1-61804-106-7",

pages = "160--165",

booktitle = "Mathematical Models and Methods in Modern Science",

note = "14th WSEAS International Conference on Mathematical Methods, Computational Techniques and Intelligent Systems (MAMECTIS'12) ; Conference date: 01-01-2012",

}

TY - GEN

T1 - An elitist genetic heuristic for the K clusters with fixed cardinality problem

AU - Lourenço, Lídia Ludovina Lampreia Caeiro Pica

AU - Gonçalves, Graça Maria Marques da Silva

PY - 2012/1/1

Y1 - 2012/1/1

N2 - We study an elitist genetic heuristic for the K clusters with fixed cardinality problem. The genetic heuristic is based on a specific encoding that identifies the cluster each item is assigned to. A computational experiment is designed to compare the cost of the best feasible solution given by this genetic heuristic (a lower bound), with the lower bound obtained from an enlarged local search algorithm previously developed for this problem. For small instances the genetic lower bound is also compared with the optimum value obtained from a mixed-integer linear formulation defined for this difficult combinatorial problem. The results show good quality genetic heuristic solutions, obtained in short computing time

AB - We study an elitist genetic heuristic for the K clusters with fixed cardinality problem. The genetic heuristic is based on a specific encoding that identifies the cluster each item is assigned to. A computational experiment is designed to compare the cost of the best feasible solution given by this genetic heuristic (a lower bound), with the lower bound obtained from an enlarged local search algorithm previously developed for this problem. For small instances the genetic lower bound is also compared with the optimum value obtained from a mixed-integer linear formulation defined for this difficult combinatorial problem. The results show good quality genetic heuristic solutions, obtained in short computing time

KW - K clusters

KW - genetic heuristic

KW - elitism

KW - combinatorial problem

KW - fixed cardinality

M3 - Conference contribution

SN - 978-1-61804-106-7

SP - 160

EP - 165

BT - Mathematical Models and Methods in Modern Science

T2 - 14th WSEAS International Conference on Mathematical Methods, Computational Techniques and Intelligent Systems (MAMECTIS'12)

Y2 - 1 January 2012

ER -