NDLI: Improving GASAT by replacing tabu search by DLM and enhancing the best members

Content Provider	Springer Nature Link
Author	Kilani, Yousef
Copyright Year	2009
Abstract	The satisfiability problem (SAT), as one of the six basic core NP-complete problems, has been the deserving object of many studies in the last two decades (Lardeux et al. 2005, 2006). GASAT (Lardeux et al. 2005, 2006; Hao et al. 2002) is one of the current state-of-the-art genetic algorithms for solving SATs. Besides, the discrete lagrange-multiplier (DLM) (Wu and Wah 1999a, b) is one of the current state-of-the-art local search algorithms for solving SATs. GASAT is a hybrid algorithm of the genetic and tabu search techniques. GASAT uses tabu search to avoid restarting the search once it converges. In this paper, we improve GASAT by replacing the tabu search by the DLM algorithm. We show that the performance of the new algorithm, DGASAT, is far better than the performance of GASAT in solving most of the benchmark instances. We further improve DGASAT by introducing the notion of improving one of the best members in the current population at a time. We show through experimentation that DGASAT + is far better than DGASAT in solving nearly all the benchmark instances.
Starting Page	41
Ending Page	59
Page Count	19
File Format	PDF
ISSN	02692821
Journal	Artificial Intelligence Review
Volume Number	33
Issue Number	1-2
e-ISSN	15737462
Language	English
Publisher	Springer Netherlands
Publisher Date	2009-12-23
Publisher Place	Dordrecht
Access Restriction	Subscribed
Subject Keyword	SAT GASAT Tabu search DLM DGASAT DGASAT + Computer Science Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Linguistics and Language

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

Distributed SAT

Simple algorithm portfolio for SAT

Improving mobile search using content enrichment

Airport Gate Scheduling with Time Windows

The variants of the harmony search algorithm: an overview

Artificial intelligence and networking

Collaborative web search: a robustness analysis

A Tabu-Based Exploratory Evolutionary Algorithm for Multiobjective Optimization

Solving electrical power system problems by harmony search: a review

Improving GASAT by replacing tabu search by DLM and enhancing the best members

Similar Documents

Distributed SAT

Simple algorithm portfolio for SAT

Improving mobile search using content enrichment

Airport Gate Scheduling with Time Windows

The variants of the harmony search algorithm: an overview

Artificial intelligence and networking

Collaborative web search: a robustness analysis

A Tabu-Based Exploratory Evolutionary Algorithm for Multiobjective Optimization

Solving electrical power system problems by harmony search: a review

Improving GASAT by replacing tabu search by DLM and enhancing the best members