USP Electronic Research Repository

ICHEA for discrete constraint satisfaction problems

Sharma, Anuraganand and Sharma, D.P. (2012) ICHEA for discrete constraint satisfaction problems. In: Advances in Artificial Intelligence. Lecture Notes in Computer Science, 7691 . Springer Berlin Heidelberg, Berlin, pp. 242-253. ISBN Print 978-3-642-35100-6 Online 978-3-642-35101-3

[thumbnail of ICHEA_-_nQueen.pdf] PDF - Published Version
Restricted to Registered users only

Download (366kB) | Request a copy

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.

Item Type: Book Chapter
Additional Information: DOI: 10.1007/978-3-642-35101-3_21
Uncontrolled Keywords: Constraints, constraint satisfaction problem (CSP), optimization problem, evolutionary algorithm (EA), intelligent constraint handling evolutionary algorithm (ICHEA), N-Queens problem
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Divisions: Faculty of Science, Technology and Environment (FSTE) > School of Computing, Information and Mathematical Sciences
Depositing User: Anuraganand Sharma
Date Deposited: 04 Oct 2013 01:13
Last Modified: 05 Oct 2018 04:11
URI: https://repository.usp.ac.fj/id/eprint/6651

Actions (login required)

View Item View Item