Please use this identifier to cite or link to this item:
http://localhost:8081/xmlui/handle/123456789/8842
Title: | PARALLEL GENETIC ALGORITHM AND SIMULATED ANNEALING FOR QUADRATIC ASSIGNMENT PROBLEM |
Authors: | Singhal, Gagan |
Keywords: | CIVIL ENGINEERING;PARALLEL GENETIC ALGORITHM;SIMULATED ANNEALING;QUADRATIC ASSIGNMENT PROBLEM |
Issue Date: | 2011 |
Abstract: | Optimization Techniques seek to minimize or maximize a real function by systematically choosing the values of real variables from within an allowed set. It is broad field of study comprising of a variety of methods like linear programming, newton raphson etc to heuristic approaches ranging from the simplest nearest neighbor approach to modern evolutionary algorithms like Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization, and Bees Algorithm etc. These techniques are applied to problems of both continuous and discrete domains. Our work focuses on Genetic Algorithm and Simulated Annealing technique for combinatorial problems of discrete nature. These algorithms are tested on several instances of Quadratic Assignment Problem (QAP). This problem is NP-hard and even small instances may require long computation time. For this reason, we propose the parallel versions for these algorithms. Parallelization is achieved using message passing techniques of MPI library. The implementation of proposed algorithms and all its pre-requisites are coded using C programming language. Speedups obtained by the parallel versions of these algorithms have been studied. Results show that Genetic Algorithm performs better than Simulated Annealing in parallel scenarios. |
URI: | http://hdl.handle.net/123456789/8842 |
Other Identifiers: | M.Tech |
Research Supervisor/ Guide: | Misra, Manoj |
metadata.dc.type: | M.Tech Dessertation |
Appears in Collections: | MASTERS' THESES (Civil Engg) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CEDG21076.pdf | 3.58 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.