A Hybrid Evolutionary Algorithm for Some Discrete Optimization Problems

Discrete optimization methods are applied in time-dependent systems where there are problems of production management and job’s scheduling. One can encounter such problems in preparing travel itineraries for tourists, in op-timal ways (e.g. traveling salesman’s way), schedule plan-ning and in expert systems connected with taking optimal decisions. Many of these problems amount to determining optimal scheduling (permutation of some objects) and usu-ally they are NP-hard. They have also irregular goal func-tions and very many local minima. Classic heuristic algo-rithms (tabu search, simulated annealing and genetic algo-rithm) quickly converge to some local minimum and diver-sification of the search process is difficult. In this paper we present a hybrid evolutionary algorithm for solving permu-tation optimization problems. It consists in testing feasible solutions, which are local minima. ∗