Knowledge Insertion: an Efficient Approach to Reduce Search Effort in Evolutionary Scheduling

Abstract

Evolutionary algorithms (EAs) are merely blind search algorithms, which only make use of the relative fitness of solutions, but completely ignore the nature of the problem. Their performance can be improved by using new multirecombinative approaches, which provide a good balance between exploration and exploitation. Even though in difficult problems with large search spaces a considerable number of evaluations are required to arrive to near-optimal solutions. On the other hand specialized heuristics are based on some specific features of the problem, and the solution obtained can include some features of optimal solutions. If we insert in the evolutionary algorithm the problem specific knowledge embedded in good solutions (seeds), coming from some other heuristic or from the evolutionary process itself, we can expect that the algorithm will be guided to promising subspaces avoiding a large search. This work shows alternative ways to insert knowledge in the search process by means of the inherent information carried by solutions coming from that specialised heuristic or gathered by the evolutionary process itself. To show the efficiency of this approach, the present paper compares the performance of multirecombined evolutionary algorithms with and without knowledge insertion when applied to selected instances of the Average Tardiness Problem in a single machine environment.

Keywords

• average tardiness scheduling problem
• evolutionary scheduling
• conventional heuristics
• problem specific knowledge