A challenge in designing resource-constrained embedded systems for digital signal processing (DSP) is their complexity due to their vast design spaces, where only a fraction of implementations are feasible or optimal. A crucial tool to aid in this challenge is automated design space exploration (DSE). However, no exact, multi-objective, and preference-free DSE approach exists for DSP applications on resource-constrained embedded platforms. We propose a novel DSE solution with these ideal characteristics to perform DSE of analyzable DSP applications for tile-based multiprocessing embedded platforms. Our proposal harmonizes the exactness of constraint programming (CP) and the exploration efficiency of genetic algorithms (GA). Through this synergy, no single-objective reduction strategy or a priori objective preferences is required. We evaluate the proposal through state-of-the-art single-objective case studies and multi-objective case studies inspired by these. The evaluations show that our proposal improves the single-objective state-of-the-art and finds high-quality approximate Pareto-frontiers for the multi-objective case study. Therefore, our proposal is a more performant single-objective DSE solution than the state-of-the-art, and it is the first exact, multi-objective, and preference-free DSE approach for the problem addressed.