Limits of scalability of multiobjective estimation of distribution algorithms

The paper analyzes the scalability of multiobjective estimation of distribution algorithms (MOEDAs), particularly multiobjective extended compact genetic algorithm (meCGA), on a class of boundedly-difficult additively-separable multiobjective optimization problems. The paper demonstrates that even if the linkage is correctly identified, massive multimodality of the search problems can easily overwhelm the nicher and lead to exponential scale-up. The exponential growth of the Pareto-optimal solutions introduces a fundamental limit on the scalability of MOEDAs and the number of competing substructures between the multiple objectives. Facetwise models are subsequently used to predict this limit in the growth rate of the number of differing substructures between the two objectives to avoid the niching method from being overwhelmed and lead to polynomial scalability of MOEDAs.