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