NDLI: A genetic algorithm applied to graph problems involving subsets of vertices

Content Provider	IEEE Xplore Digital Library
Author	Alkhalifah, Y. Wainwright, R.L.
Copyright Year	2004
Description	Author affiliation: Dept. of Math. & Comput. Sci., Tulsa Univ., OK, USA (Alkhalifah, Y.; Wainwright, R.L.)
Abstract	Many graph problems seek subsets of their vertices that maximize or minimize objective functions on the vertices. Among these are the capacitated p-median problem, the geometric connected dominating set problem, the capacitated k-center problem, and the traveling tourist problem. Prior genetic algorithms research in this area applied a simple mutation of an allele by random replacement. Recently an enhanced operator called hypermutation was developed, proving to be very effective for solving the capacitated p-median problem. We propose a GA with a new heuristic called the nearest four neighbors heuristic (N4N) for solving graph problems requiring a subset of vertices. It is an extension of the hypermutation operator. Genetic algorithms that use each of these three mutation operators (simple, hypermutation, N4N) are applied to instances of the four graph-subset problems listed above. Results show that our N4N heuristic obtained superior results compared to the hypermutation and the simple mutation operators in every test case.
Sponsorship	IEEE Neural Network Soc. Evolutionary Programming Soc. IEE
Starting Page	303
Ending Page	308
File Size	409493
Page Count	6
File Format	PDF
ISBN	0780385152
DOI	10.1109/CEC.2004.1330871
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-06-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Genetic algorithms Genetic mutations Educational institutions Testing Algorithm design and analysis Telecommunication computing Transportation Processor scheduling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in