This thesis demonstrates how metaheuristic algorithms can be used to find valid configurations for context-aware software. To represent families of context-aware software, the thesis describes and uses Context-dependent Feature Models (CFMs). Three different metaheuristic algorithms are introduced: Hill-climbing, Simulated Annealing and Genetic Algorithm. These three approaches are implemented in a reconfiguration engine that aims to find valid configurations on different sets of CFMs. Additionally, the paper presents a tool that randomly generates these datasets for the purpose of benchmark testing. Although randomly generated, the CFMs in the different datasets are defined by a range of predefined parameters. The performance of the metaheuristic algorithms is evaluated based on running time and the number of successful reconfigurations. For comparison, the results are compared to the performance of a CP-solver, called HyVarRec. This thesis highlights some key differences in how the three algorithms perform and how some specific properties of CFMs may cause one algorithm to perform differently from another. The general findings in this thesis suggest that Simulated Annealing (SA) is an efficient algorithm with a high probability of succeeding. Genetic Algorithm and Hill-Climbing (HC) are in general not as successful as SA. However, HC is very efficient and is often able to reconfigure models where SA is unsuccessful. Especially on smaller CFMs, the approach of running SA and HC together performs quite well when compared to HyVarRec.