NDLI: Reactive prohibition-based ant colony optimization (RPACO): a new parallel architecture for constrained clique sub-graphs

Content Provider	IEEE Xplore Digital Library
Author	Youssef, S.M. Elliman, D.G.
Copyright Year	2004
Description	Author affiliation: Sch. of Comput. Sci. & IT, Nottingham Univ., UK (Youssef, S.M.; Elliman, D.G.)
Abstract	We introduce a new algorithm that combines the stigmergetic capabilities of the ant colony optimization (AGO) with local search heuristics to solve the maximum and maximum-weighted clique problem. Our new algorithm: A reactive prohibition-based ant colony optimization (RPACOMCP), complements the intelligent ant colony search with a prohibition-based diversification technique, where the amount of diversification is determined in an automated way through a feedback (history-sensitive) scheme. Based on prohibition, some local moves are temporarily prohibited in order to avoid repeated cycles in the search trajectory and to explore new parts of the total search space. Diversification could be enforced and the ACO search continued beyond local optimal points. One of the main advantages of this approach is the use of parallelism both to have a number of ant colonies searching simultaneously and to have a function distribution of local search procedures. This architecture thus provides a powerful tool to tackle difficult problems using all available processing power. The algorithm is tested on many representative DIMACS benchmark graph instances and results are compared with GLS [E. Marchiori, (2002)], a genetic local search approach for MCP. It is shown that the proposed PACO algorithm finds larger cliques in reasonable time, on average, on a wide majority of benchmark instances of the DIMACS library, even though it does not reach the best known results on a few benchmark instances. We also showed that the PACO algorithm outperforms the nonprohibition version on most hard graph instances.
Sponsorship	IEEE Comput. Soc.
Starting Page	63
Ending Page	70
File Size	173967
Page Count	8
File Format	PDF
ISBN	076952236X
ISSN	10823409
DOI	10.1109/ICTAI.2004.104
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-11-15
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Ant colony optimization Parallel architectures Feedback Computer science Benchmark testing Genetics Heuristic algorithms Computer architecture Parallel processing Libraries
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