Please use this identifier to cite or link to this item:
Title: Solving NP Complete Problems using modified Genetic Algorithm operators
Researcher: Jain V.
Guide(s): Prasad J.S.
Keywords: Engineering and Technology,Computer Science,Computer Science Artificial Intelligence
University: MVN University,Palwal
Completed Date: 2018
Abstract: Travelling Salesman Problem, N-Queen Problem and Multiple Knapsack Problem are well known NP- Complete (NPC) and NP-Hard (NPH) problems. These problems have wide application area in science, engineering and in daily life. NPC and NPH problems cannot be solved in polynomial time using contemporary algorithms. Approximation and optimization techniques are applied to solve these types of problems to get the approximated results. In this research work, mutation and cross over operator is hybridized by applying greedy approaches in order to obtain the fast convergence of genetic algorithm. The quality of solution obtained through hybridization is superior as compared to other well-known techniques like ACO, PSO etc. The cross over and mutation GA operators are modified to implement the greedy approach in the proposed Greedy Genetic Algorithm (GGA). The proposed GGA improves the solution of TSP (path length) by 6%-19%, up to 16% profitable solution for multiple knapsack problems and also obtained N-Queen solution in reasonable good amount of time. Proposed GGA convergence rate is fast and quality of solution provided while solving NPC and NPH problems is found excellent. newline
Appears in Departments:Computer Science Engineering

Files in This Item:
File Description SizeFormat 
02_certificate.pdfAttached File605.39 kBAdobe PDFView/Open
03_abstract.pdf176.13 kBAdobe PDFView/Open
04_acknowledgement.pdf373.59 kBAdobe PDFView/Open
05_table of contents.pdf318.68 kBAdobe PDFView/Open
06_list of tables.pdf178.53 kBAdobe PDFView/Open
07_list of figures.pdf183.57 kBAdobe PDFView/Open
08_list of symbols and abbreviations.pdf290.97 kBAdobe PDFView/Open
09_chapter 1.pdf601.54 kBAdobe PDFView/Open
10_chapter 2.pdf393.54 kBAdobe PDFView/Open
11_chapter 3.pdf537.07 kBAdobe PDFView/Open
12_chapter 4.pdf616.48 kBAdobe PDFView/Open
13_chapter 5.pdf1.01 MBAdobe PDFView/Open
14_chapter 6.pdf189.56 kBAdobe PDFView/Open
15_references.pdf469.86 kBAdobe PDFView/Open
16_list of publications.pdf283.86 kBAdobe PDFView/Open
17_annexure 1.pdf293.91 kBAdobe PDFView/Open
1_title page.pdf353.28 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.

Altmetric Badge: