A Modified Heuristic Procedure for NP-Complete Problems Supported by Genetic Algorithms

This work is based on the process of modifying an intelligent heuristic rule used in solving NP-Complete problems, where a study and a modification of a Flow Shop assignment heuristic has been carried out to solve a well-known classic Artificial Intelligent problem, which is the traveling Salesman problem. For this modification to be carried out successfully, the problem’s mathematical formulation had to be studied carefully and the possibility of reformulating the problem to be more suitable for the heuristic procedure. This may require some changes in the heuristic procedure itself, these adjustments were due to the noticeable differences like the symmetric property present in the traveling salesman problem environment and some other differences. Genetic Algorithm is added to improve the results obtained by the used heuristic, where the use of crossover and mutation procedures will provide better chances for the near optimal solution to be improved towards optimal solutions. The test problem is made on cities that lie on the regular square grid, which simplify the calculations of distance traveled between any two cities. Programs were written using C programming language, and timers were used to measure the elapsed time of calculations in order to assess the efficiency of the program.