NDLI: A hierarchical parallel genetic approach for the graph coloring problem

Content Provider	Springer Nature Link
Author	Abbasian, Reza Mouhoub, Malek
Copyright Year	2013
Abstract	Graph Coloring Problems (GCPs) are constraint optimization problems with various applications including time tabling and frequency allocation. The GCP consists in finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. We propose a hierarchical approach based on Parallel Genetic Algorithms (PGAs) to solve the GCP. We call this new approach Hierarchical PGAs (HPGAs). In addition, we have developed a new operator designed to improve PGAs when solving constraint optimization problems in general and GCPs in particular. We call this new operator Genetic Modification (GM). Using the properties of variables and their relations, GM generates good individuals at each iteration and inserts them into the PGA population in the hope of reaching the optimal solution sooner. In the case of the GCP, the GM operator is based on a novel Variable Ordering Algorithm (VOA) that we propose. Together with the new crossover and the estimator of the initial solution we have developed, GM allows our solving approach to converge towards the optimal solution sooner than the well known methods for solving the GCP, even for hard instances. This was indeed clearly demonstrated by the experiments we conducted on the GCP instances taken from the well known DIMACS website.
Starting Page	510
Ending Page	528
Page Count	19
File Format	PDF
ISSN	0924669X
Journal	Applied Intelligence
Volume Number	39
Issue Number	3
e-ISSN	15737497
Language	English
Publisher	Springer US
Publisher Date	2013-03-03
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Parallel genetic algorithms Graph coloring problem Artificial Intelligence (incl. Robotics) Mechanical Engineering Manufacturing, Machines, Tools
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

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

Multi-objective Genetic Algorithms for grouping problems

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

Incorporating Ancestors' Influence in Genetic Algorithms

A Memetic Approach to the Nurse Rostering Problem

Improving Parallel Ordering of Sparse Matrices Using Genetic Algorithms

A graph coloring constructive hyper-heuristic for examination timetabling problems

Neural Nets Trained by Genetic Algorithms for Collision Avoidance

Evolving Neuro-Controllers for a Dynamic System Using Structured Genetic Algorithms

A Genetic Algorithm for Multiobjective Robust Design

A hierarchical parallel genetic approach for the graph coloring problem

Similar Documents

Multi-objective Genetic Algorithms for grouping problems

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

Incorporating Ancestors' Influence in Genetic Algorithms

A Memetic Approach to the Nurse Rostering Problem

Improving Parallel Ordering of Sparse Matrices Using Genetic Algorithms

A graph coloring constructive hyper-heuristic for examination timetabling problems

Neural Nets Trained by Genetic Algorithms for Collision Avoidance

Evolving Neuro-Controllers for a Dynamic System Using Structured Genetic Algorithms

A Genetic Algorithm for Multiobjective Robust Design

A hierarchical parallel genetic approach for the graph coloring problem