Given a graph G= (V, E), a function f: V→Z and positive integer k, a set D ⊆ V is a k-domination if ∀ v ∈ V, v ∈ D or N[v] ∩ D ≥ k. The problem of minimum weight k-domination is an NP-hard problem and consists of obtaining a k-domination D such that ∑u∈D f(u) is minimal. This paper presents three approaches for the minimum weight k-domination problem with k=2: two evolutionary approaches, one being a Genetic Algorithm with local search and the other a Memetic Algorithm; besides a Simulated Annealing approach. The experiments considered a set of 1020 instances from the literature. Using the results obtained from the linear problem solver Gurobi, it was possible to show the convergence capacity of the proposed approaches for optimal solutions or near-optimal.