ICHEA for Discrete Constraint Satisfaction Problems

Anurag Sharma, Dharmendra Sharma

Research output: A Conference proceeding or a Chapter in BookConference contribution

1 Citation (Scopus)

Abstract

Constraint satisfaction problem (CSP) is a subset of optimization problem where at least one solution is sought that satisfies all the given constraints. Presently, evolutionary algorithms (EAs) have become standard optimization techniques for solving unconstrained optimization problems where the problem is formalized for discrete or continuous domains. However, traditional EAs are considered ‘blind’ to constraint as they do not extract and exploit information from the constraints. A variation of EA – intelligent constraint handling for EA (ICHEA) proposed earlier models constraints to guide the evolutionary search to get improved and efficient solutions for continuous CSPs. As many real world CSPs have constraints defined in the form of discrete functions, this paper serves as an extension to ICHEA that reports its applicability for solving discrete CSPs. The experiment has been carried on a classic discrete CSP – the N-Queens problem. The experimental results show that extracting information from constraints and exploiting it in the evolutionary search makes the search more efficient. This provision is a problem independent formulation in ICHEA.
Original languageEnglish
Title of host publicationAI 2012: Advances in Artificial Intelligence
Subtitle of host publication25th International Australasian Joint Conference
EditorsMichael Thielscher, Dongmo Zhang
Place of PublicationBerlin Heidelberg
PublisherSpringer
Pages242-253
Number of pages12
Volume7691
ISBN (Print)9783642351013
DOIs
Publication statusPublished - 2012
Event25th International Australasian Joint Conference (AI 2012) - Sydney, Sydney, Australia
Duration: 4 Dec 20127 Dec 2012

Conference

Conference25th International Australasian Joint Conference (AI 2012)
CountryAustralia
CitySydney
Period4/12/127/12/12

Fingerprint

Constraint satisfaction problems
Evolutionary algorithms
Set theory
Experiments

Cite this

Sharma, A., & Sharma, D. (2012). ICHEA for Discrete Constraint Satisfaction Problems. In M. Thielscher, & D. Zhang (Eds.), AI 2012: Advances in Artificial Intelligence: 25th International Australasian Joint Conference (Vol. 7691, pp. 242-253). Berlin Heidelberg: Springer. https://doi.org/10.1007/978-3-642-35101-3_21
Sharma, Anurag ; Sharma, Dharmendra. / ICHEA for Discrete Constraint Satisfaction Problems. AI 2012: Advances in Artificial Intelligence: 25th International Australasian Joint Conference. editor / Michael Thielscher ; Dongmo Zhang. Vol. 7691 Berlin Heidelberg : Springer, 2012. pp. 242-253
@inproceedings{b809a81d4c48413d8ad4e455d7684483,
title = "ICHEA for Discrete Constraint Satisfaction Problems",
abstract = "Constraint satisfaction problem (CSP) is a subset of optimization problem where at least one solution is sought that satisfies all the given constraints. Presently, evolutionary algorithms (EAs) have become standard optimization techniques for solving unconstrained optimization problems where the problem is formalized for discrete or continuous domains. However, traditional EAs are considered ‘blind’ to constraint as they do not extract and exploit information from the constraints. A variation of EA – intelligent constraint handling for EA (ICHEA) proposed earlier models constraints to guide the evolutionary search to get improved and efficient solutions for continuous CSPs. As many real world CSPs have constraints defined in the form of discrete functions, this paper serves as an extension to ICHEA that reports its applicability for solving discrete CSPs. The experiment has been carried on a classic discrete CSP – the N-Queens problem. The experimental results show that extracting information from constraints and exploiting it in the evolutionary search makes the search more efficient. This provision is a problem independent formulation in ICHEA.",
keywords = "Constraint satisfaction problems, ICHEA, Evolutionary algorithms",
author = "Anurag Sharma and Dharmendra Sharma",
year = "2012",
doi = "10.1007/978-3-642-35101-3_21",
language = "English",
isbn = "9783642351013",
volume = "7691",
pages = "242--253",
editor = "Michael Thielscher and Dongmo Zhang",
booktitle = "AI 2012: Advances in Artificial Intelligence",
publisher = "Springer",
address = "Netherlands",

}

Sharma, A & Sharma, D 2012, ICHEA for Discrete Constraint Satisfaction Problems. in M Thielscher & D Zhang (eds), AI 2012: Advances in Artificial Intelligence: 25th International Australasian Joint Conference. vol. 7691, Springer, Berlin Heidelberg, pp. 242-253, 25th International Australasian Joint Conference (AI 2012), Sydney, Australia, 4/12/12. https://doi.org/10.1007/978-3-642-35101-3_21

ICHEA for Discrete Constraint Satisfaction Problems. / Sharma, Anurag; Sharma, Dharmendra.

AI 2012: Advances in Artificial Intelligence: 25th International Australasian Joint Conference. ed. / Michael Thielscher; Dongmo Zhang. Vol. 7691 Berlin Heidelberg : Springer, 2012. p. 242-253.

Research output: A Conference proceeding or a Chapter in BookConference contribution

TY - GEN

T1 - ICHEA for Discrete Constraint Satisfaction Problems

AU - Sharma, Anurag

AU - Sharma, Dharmendra

PY - 2012

Y1 - 2012

N2 - Constraint satisfaction problem (CSP) is a subset of optimization problem where at least one solution is sought that satisfies all the given constraints. Presently, evolutionary algorithms (EAs) have become standard optimization techniques for solving unconstrained optimization problems where the problem is formalized for discrete or continuous domains. However, traditional EAs are considered ‘blind’ to constraint as they do not extract and exploit information from the constraints. A variation of EA – intelligent constraint handling for EA (ICHEA) proposed earlier models constraints to guide the evolutionary search to get improved and efficient solutions for continuous CSPs. As many real world CSPs have constraints defined in the form of discrete functions, this paper serves as an extension to ICHEA that reports its applicability for solving discrete CSPs. The experiment has been carried on a classic discrete CSP – the N-Queens problem. The experimental results show that extracting information from constraints and exploiting it in the evolutionary search makes the search more efficient. This provision is a problem independent formulation in ICHEA.

AB - Constraint satisfaction problem (CSP) is a subset of optimization problem where at least one solution is sought that satisfies all the given constraints. Presently, evolutionary algorithms (EAs) have become standard optimization techniques for solving unconstrained optimization problems where the problem is formalized for discrete or continuous domains. However, traditional EAs are considered ‘blind’ to constraint as they do not extract and exploit information from the constraints. A variation of EA – intelligent constraint handling for EA (ICHEA) proposed earlier models constraints to guide the evolutionary search to get improved and efficient solutions for continuous CSPs. As many real world CSPs have constraints defined in the form of discrete functions, this paper serves as an extension to ICHEA that reports its applicability for solving discrete CSPs. The experiment has been carried on a classic discrete CSP – the N-Queens problem. The experimental results show that extracting information from constraints and exploiting it in the evolutionary search makes the search more efficient. This provision is a problem independent formulation in ICHEA.

KW - Constraint satisfaction problems

KW - ICHEA

KW - Evolutionary algorithms

U2 - 10.1007/978-3-642-35101-3_21

DO - 10.1007/978-3-642-35101-3_21

M3 - Conference contribution

SN - 9783642351013

VL - 7691

SP - 242

EP - 253

BT - AI 2012: Advances in Artificial Intelligence

A2 - Thielscher, Michael

A2 - Zhang, Dongmo

PB - Springer

CY - Berlin Heidelberg

ER -

Sharma A, Sharma D. ICHEA for Discrete Constraint Satisfaction Problems. In Thielscher M, Zhang D, editors, AI 2012: Advances in Artificial Intelligence: 25th International Australasian Joint Conference. Vol. 7691. Berlin Heidelberg: Springer. 2012. p. 242-253 https://doi.org/10.1007/978-3-642-35101-3_21