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.
Simulated annealing construction of shortest (spanning/nonspanning
and closed/open) paths on generál connected graphs is discussed. A brief graphtheoretical analysis of the problem is given. A theorem has been proved that for connected graphs the shortest paths are semielementary, that is each edge on the path is visited at most twice in opposite directions. This observation considerably reduces the search space. Tasks may be further specified depending on whether the initial and terminal vertices are given or not. Similarly, in construction of shortest open paths a subtask is considered when the path must visit a prescribed subset of graph vertices. Illustrative calculations demonstrate that the proposed method results for incomplete graphs in the paths that are dosely related to optimal solutions.