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

[img] PDF - Published Version
Restricted to Registered users only

Download (357Kb)

    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 13:13
    Last Modified: 05 Oct 2018 16:11
    URI: http://repository.usp.ac.fj/id/eprint/6651
    UNSPECIFIED

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...