View article

Due to the combinatorial explosions in solution space for scheduling problems, the balance between genetic search and local search is an important issue when designing a memetic algorithm [23] for scheduling problems. The main motivation of this research is to resolve the combinatorial explosion problem by reducing the possible neighborhood combinations using guided operations to remove these inferior moves. We proposed a new algorithm, termed as a Guided memetic algorithm, which is one of the algorithms in the category of evolutionary algorithm based on probabilistic models (EAPMs). The algorithm explicitly employs the probabilistic models which serves as a fitness surrogate. The fitness surrogate estimates the fitness of the new solution generated by a local search operator beforehand so that the algorithm is able to determine whether the new solution is worthwhile to be evaluated again for its true fitness. This character distinguishes the proposed algorithm from previous EAPMs. The single machine scheduling problems are applied as test examples. The experimental results show that the Guided memetic algorithm outperformed elitism genetic algorithm significantly. In addition, the Guided memetic algorithm works more efficiently than previous EAPMs and Elitism Genetic algorithm. As a result, it is a new break-through in genetic local search with probabilistic models as a fitness surrogate.

1. Introduction. As defined by Nareyek [33], there are two search-paradigms for search: refinement search and local search. The refinement search is iteratively narrowing process alternating between commitment and propagation while local …