The task of automatic design space exploration of heterogeneous multi-processor systems is often tackled with Evolutionary Algorithms. In this paper, we propose a novel approach in combining Evolutionary Algorithms with symbolic techniques in order to improve the convergence speed. The main idea is to guide the search towards the feasible region by utilizing symbolic techniques. We will present experimental results showing the advantages of our novel approach, especially when the search space contains only few feasible solutions, what is often the case when designing heterogeneous multi-processor systems