A key concern in artificial-life-oriented research in complex systems has been the relationship between the dynamical behaviour of cellular automata (CA) and their computational ability. Along this line, evolutionary methods have been used to look for CA with predefined computational behaviours, the most widely studied task having been the Density Classification Task (DCT). It has recently been showed that the use of an heuristic guided by parameters that estimate the dynamical behaviour of CA, can improve evolutionary search. On the other hand, an approach that has been successfully applied to several kinds of problems is the Evolutionary Multiobjective Optimization (EMOO). Here, the EMOO technique called Non-Dominated Sorting Genetic Algorithm is combined with the parameter-based heuristic, and successfullly applied to the DCT, suggesting a positive synergy out of using the two techniques in the search for CA.