Abstract:
|
In this paper we present a memetic algorithm for the minimum weighted
k-cardinality tree subgraph problem.
This problem consists in finding, in a given undirected weighted graph
G=(V,E,W), a tree T of k edges having
minimal total weight among all of k-trees that are subgraphs of G. This
problem was first described by Hamacher,
Jornsten, and Maffioli (1991) who also proved to be strongly NP-hard.
Given this observation, researchers have
focused on heuristic and metaheuristic algorithms to find suboptimal
feasible solutions for the problem, as a good way
to cope with most practical setting applications.
To our knowledge, no memetic algorithm (MA) has yet been reported for
this problem. It is known that some MAs have
a good synergy with Tabu Search when they use it as individual steps
for diversification and local optimization by the agents.
As a consequence, one of our main motivations was to obtain a new
implementation of an MA to the problem using an
existing implementation of Tabu Search to the problem (Blesa and Xhafa,
2000). We are currently implementing the
proposed algorithm. |