poster

A Tabu history driven crossover operator design for memetic algorithm applied to Max-2SAT-problems

Authors:

M. Borschbach,

A. ExelerAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 605 - 606

https://doi.org/10.1145/1389095.1389214

Published: 12 July 2008 Publication History

Get Access

Abstract

The solution for the Max-2SAT is the starting point for a selection of these strategies by a brief review. Moreover, a memetic algorithm for Max-2SAT problems based on a specific crossover operator and an improved tabu search stage is presented. Simulation performed on several instances of Max-2SAT reference problems are used to evaluate the different memetic algorithm strategies applied in our approach and to compare it to the computational complexity of existing local search solutions.

References

[1]

A. Armando, C. Castellini, E. Giunchiglia, F. Giunchiglia, and A. Tacchella. SAT-based decision procedures for automated reasoning: a unifying perspective, 2002.]]

Google Scholar

[2]

B. Aspvall, M.F. Plass, and R.E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3):121--123, 1979.]]

Crossref

Google Scholar

[3]

A. Biere, A. Cimatti, E. Clarke, and Y. Zhu. Symbolic model checking without BDDs. Lecture Notes in Computer Science 1579:193--207, 1999.]]

Digital Library

Google Scholar

[4]

M. Borschbach and A. Exeler. A search agent for a Max-2SAT memetic algorithm approach. In Proceedings of Advances of Computer Application and COmputational Science (ACACOS), In: Selected Paper from the Conference in Hangzhou 2008.]]

Digital Library

Google Scholar

[5]

D. Boughaci, B. Benhamou, and H. Drias.Iga: An improved genetic algorithm for Max-SAT problems. In Indian International Conference on Artificial Intelligence (IICAI)-07 2007.]]

Google Scholar

[6]

S.A. Cook. The complexity of theorem-proving procedures. In STOC pages 151--158, 1971.]]

Digital Library

Google Scholar

[7]

C. Fleurent and J. Ferland. Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26:619--652, 1996.]]

Crossref

Google Scholar

[8]

J. Frank. A study of genetic algorithms to find approximate solutions to hard 3cnf problems, 1994.]]

Google Scholar

[9]

M.R. Garey and D.S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness W.H. Freeman & Co., New York, NY, USA, 1990.]]

Digital Library

Google Scholar

[10]

I.P. Gent and T. Walsh. Towards an understanding of hill-climbing procedures for SAT. In National Conference on Artificial Intelligence pages 28--33, 1993.]]

Google Scholar

[11]

F. Lardeux, F. Saubion, and J.-K. Hao. Gasat: A genetic local search algorithm for the satisfiability problem. Evolutionary Computation 14(2):223--253, 2006.]]

Digital Library

Google Scholar

[12]

P. Pardalos, L. Pitsoulis, and M. Resende. A parallel grasp for Max-SAT problems, 1996.]]

Google Scholar

[13]

H. Zhang, D. Li, and H. Shen. A sat based scheduler for tournament schedules. In SAT 2004.]]

Google Scholar

Cited By

View all

Moscato PMathieson L(2019)Memetic Algorithms for Business Analytics and Data Science: A Brief SurveyBusiness and Consumer Analytics: New Ideas10.1007/978-3-030-06222-4_13(545-608)Online publication date: 31-May-2019
https://doi.org/10.1007/978-3-030-06222-4_13
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6

Index Terms

A Tabu history driven crossover operator design for memetic algorithm applied to Max-2SAT-problems
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A tabu search based memetic algorithm for the max-mean dispersion problem

Given a set V of n elements and a distance matrix d ij n n among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset M from V such that the mean dispersion (or distance) among the selected elements is maximized. Being a ...
On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems

Finding a good university timetabling system is not a simple task for a higher educational organisation. As a result, many approaches to generating sufficiently good solutions have been introduced. This is mainly due to the high complexity within the ...
A low-level hybridization between memetic algorithm and VNS for the max-cut problem
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

The Max-Cut problem consists of finding a partition of the graph nodes into two subsets, such that the sum of the edge weights having endpoints in different subsets is maximized. This NP-hard problem for non planar graphs has different applications in ...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
103
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moscato PMathieson L(2019)Memetic Algorithms for Business Analytics and Data Science: A Brief SurveyBusiness and Consumer Analytics: New Ideas10.1007/978-3-030-06222-4_13(545-608)Online publication date: 31-May-2019
https://doi.org/10.1007/978-3-030-06222-4_13
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

A tabu search based memetic algorithm for the max-mean dispersion problem

On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems

A low-level hybridization between memetic algorithm and VNS for the max-cut problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations