Deterministic Helper-Objective Sequences Applied to Job-Shop Scheduling

摘要

A Multiple Objective Evolutionary Algorithm (MOEA) applied to the Job-Shop Scheduling Problem has been shown in the past to perform better than a single objective Genetic Algorithm (GA). Helper-objectives, representing portions of the main objective, were used in the past to guide the MOEA search process. This paper explores additional understanding of helper-objective sequencing. The sequence in which helper-objectives are used is examined and it is shown that problem specific knowledge can be incorporated to determine a good helper-objective sequence. Results demonstrate how carefully sequenced helper-objectives can improve search quality. Explanations are provided for how helpers accelerate the search process by distinguishing between otherwise similar solutions and by partial removal of epistasis in one or more dimensions. Good helper-objective sequence appears to break epistasis early in a search which implies that it is important for helper-objective methods to examine the sequence of objectives.