Keywords : Heuristic


A New Heuristic Procedure for Quadratic Assignment Problems

Najla Akram Al-Saati

AL-Rafidain Journal of Computer Sciences and Mathematics, 2004, Volume 1, Issue 2, Pages 153-172
DOI: 10.33899/csmj.2004.164116

In this work, a new heuristic procedure is developed for the solution of Quadratic assignment problems after illustrating various known procedures, and an attempt to increase the efficiency of near-optimal solutions obtained from known heuristic procedures is carried out. Quadratic assignments are used for solving a wide range of problems such as the design of control panels to minimize execution time and the assignment of manufacturing departments among locations to achieve optimal product movements.
This work is based on developing a new heuristic procedure using an improved decision procedure developed form the NP-complete nature and environment of assignment problems. In order to assess the efficiency of the new procedure, which depends on constructing the solution, a comparison is made with that of VNZ (for Vollmann, Nugent and Zartler) which is considered to be one of the most efficient procedures used for solving such problems, and which depends on improving a given initial solution. Final results show a distinctive improvement in the solutions of the various randomly generated problems, and obviously, evidence of the exact solution gained using total enumeration techniques is far essential, as a measure, in the comparisons carried out between the resulting solutions of the mentioned procedures.
Three different tests are carried out in this work including 26 randomly generated problems, each is represented by a distance and a volume flow matrix with different matrix dimensions, to be employed in the process of evaluating the efficiency of the improved heuristic procedure in terms of solution accuracy and processing time consumption. C++ was employed in constructing the program structures of the mentioned procedures.
 
 

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

Najla Akram Al-Saati

AL-Rafidain Journal of Computer Sciences and Mathematics, 2004, Volume 1, Issue 1, Pages 120-137
DOI: 10.33899/csmj.2004.164101

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.