Multi-Objective Evolutionary Algorithms (MOEAs) have received increasing interest in industry, because they have proved to be powerful optimizers. Despite the great success achieved, MOEAs have also encountered many challenges in real-world applications. One of the main difficulties in applying MOEAs is the large number of fitness evaluations (objective calculations) that are often needed before a well acceptable solution can be found. In fact, there are several industrial situations in which both fitness evaluations are computationally expensive and, meanwhile, time available is very low. In this applications efficient strategies to approximate the fitness function have to be adopted, looking for a trade-off between optimization performances and efficiency. This is the case of a complex embedded system design, where it is needed to define an optimal architecture in relation to certain performance indexes respecting strict time-to-market constraints. This activity, known as Design Space Exploration DSE), is still a great challenge for the EDA (Electronic Design Automation) community. One of the most important bottleneck in the overall design flow of a embedded system is due to the simulation. Simulation occurs at every phase of the design flow and it is used to evaluate a system candidate to be implemented. In this chapter we focus on system level design proposing a hybrid computational intelligence approach based on fuzzy approximation to speed up the evaluation of a candidate system. The methodology is applied to a real case study: optimization of the performance and power consumption of an embedded architecture based on a Very Long Instruction Word (VLIW) microprocessor in a mobile multimedia application domain. The results, carried out on a multimedia benchmark suite, are compared, in terms of both performance and efficiency, with other MOGAs strategies to demonstrate the scalability and the accuracy of the proposed approach.