In traditional optimization approaches the interaction of parameters associated with a problem is not a significant issue, but in the domain of Evolutionary Multi-Objective Optimization (EMOO) traditional genetic algorithm approaches have difficulties in optimizing problems with parameter interactions. Parameter interactions can be introduced when the search space is rotated. Genetic algorithms are referred to as being not rotationally invariant because their behavior changes depending on the orientation of the search space. Many empirical studies in single and multi-objective evolutionary optimization are done with respect to test problems which do not have parameter interactions. Such studies provide a favorably biased indication of genetic algorithm performance. This motivates the first aspect of our work; the improvement of the testing of EMOO algorithms with respect to the aforementioned difficulties that genetic algorithms experience in the presence of para meter interactions. To this end, we examine how EMOO algorithms can be assessed when problems are subject to an arbitrarily uniform degree of parameter interactions. We establish a theoretical basis for parameter interactions and how they can be measured. Furthermore, we ask the question of what difficulties a multi-objective genetic algorithm experiences on optimization problems exhibiting parameter interactions. We also ask how these difficulties can be overcome in order to efficiently find the Pareto-optimal front on such problems. Existing multi-objective test problems in the literature typically introduce parameter interactions by altering the fitness landscape, which is undesirable. We propose a new suite of test problems that exhibit parameter interactions through a rotation of the decision space, without altering the fitness landscape. In addition, we compare the performance of a number of recombination operators on these test problems. The second aspect of this work is concerned with developing an efficient multi-objective optimization algorithm which works well on problems with parameter interactions. We investigate how an evolutionary algorithm can be made more efficient on multi-objective problems with parameter interactions by developing four novel rotationally invariant differential evolution approaches. We also ask whether the proposed approaches are competitive in comparison with a state-of-the-art EMOO algorithm. We propose several differential evolution approaches incorporating directional information from the multi-objective search space in order to accelerate and direct the search. Experimental results indicate that dramatic improvements in efficiency can be achieved by directing the search towards points which are more dominant and more diverse. We also address the important issue of diversity loss in rotationally invariant vector-wise differential evolution. Being able to generate diverse solutions is critically important in order to avoid stagnation. In order to address this issue, one of the directed approaches that we examine incorporates a novel sampling scheme around better individuals in the search space. This variant is able to perform exceptionally well on the test problems with much less computational cost and scales to very high decision space dimensions even in the presence of parameter interactions.