Modern embedded systems are becoming increas- ingly multifunctional. The dynamism in multifunctional embed- ded systems manifests itself with more dynamic applications and the presence of multiple applications executing on a single em- bedded system. This dynamism in the application workload must be taken into account during the early system-level design space exploration (DSE) of multiprocessor system-on-a-chip (MPSoC)- based embedded systems. Scenario-based DSE utilizes the con- cept of application scenarios to search for optimal mappings of a multi-application workload onto an MPSoC. The scenario-based DSE uses a multi-objective genetic algorithm (GA) to identifying the mapping with the best average quality for all the application scenarios in the workload. In order to keep the exploration of the scenario-based DSE efficient, fitness prediction is used to obtain the quality of a mapping. This fitness prediction is performed using a representative subset of application scenarios that is obtained using co-exploration of the scenario subset space. In this paper, multiple fitness prediction techniques are presented: stochastic, deterministic, and a hybrid combination. Results show that, for our test cases, accurate fitness prediction is already provided for subsets containing only 1–4% of the application scenarios. Larger subsets will obtain a similar accuracy, but the DSE will require more time to identify promising mappings that meet the requirements of multifunctional embedded systems.