Combinatorial optimization is a discipline of decision making in the case of diserete alternatives. The Genetic Neighborhood Search (GNS) is a hybrid method for these combinatorial optimization problems. The main feature of the approach is iterative use of local search on extended neighborhoods, where the better solution will be the center of a new extended neighborhood. When the center of the neighborhood would be t.he better solution the algorithm will stop. We propose using a genetic algorithm to exi)lore the extended neighborhoods. This GA is characterized by the method of evaluating the fitness of individuals and useing two new operators. Computational experience with the Symmetric TSP shows that this approach is robust with respect to the starting point and that high quality solutions are obtained in a reasonable time.
This páper addresses several issues related to the approximate solution of the Single Machine Scheduling problém with sequence-dependent setup times using metaheuristic methods. Instances with known optimal solution are solved using a memetic algorithm and a multiple start approach. A fitness landscape analysis is also conducted on a subset of instances to understand the behavior of the two approaches during the optimization process. We also present a novel way to create instances with known optimal Solutions from the optimally solved asymmetric travelling salesman problém (ATSP) instances. Finally we argue for the test set of instances to be ušed in future works as a convenient performance benchmark.
Linear ordering problem is a well-known optimization problem attractive for its complexity (it is an NP-hard problem), rich library of test data and variety of real world applications. In this paper, we investigate the use and performance of two variants of genetic algorithms, mutation only genetic algorithms and higher level chromosome genetic algorithm, on the linear ordering problem. Both methods are tested and evaluated on a library of real world and artificial linear ordering problem instances.