An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems

Anurag Sharma, Dharmendra Sharma

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

3 Citations (Scopus)

Abstract

Constraint satisfaction problems (CSPs) underpin many science and engineering applications. Recently introduced intelligent constraint handling evolutionary algorithm (ICHEA) in [14] has demonstrated strong potential in solving them through evolutionary algorithms (EAs). ICHEA outperforms many other evolutionary algorithms to solve CSPs with respect to success rate (SR) and efficiency. This paper is an enhancement of ICHEA to improve its efficiency and SR further by an enhancement of the algorithm to deal with local optima obstacles. The enhancement also includes a capability to handle dynamically introduced constraints without restarting the whole algorithm that uses the knowledge from already solved constraints using an incremental approach. Experiments on benchmark CSPs adapted as dynamic CSPs has shown very promising results
Original languageEnglish
Title of host publicationAn Incremental Approach to Solving Dynamic Constraint Satisfaction Problems
Editors Huang, Tingwen, Zeng Zhigang, Li, Chuandong, Leung
Place of PublicationBerlin Heidelberg
PublisherSpringer
Pages445-455
Number of pages11
Volume7665
ISBN (Print)9783642344862
DOIs
Publication statusPublished - 2012
Event19th International Conference on Neural Information Processing 2012 - Doha, Doha, Qatar
Duration: 12 Nov 201215 Nov 2012

Conference

Conference19th International Conference on Neural Information Processing 2012
CountryQatar
CityDoha
Period12/11/1215/11/12

Fingerprint

Constraint satisfaction problems
Evolutionary algorithms
Experiments

Cite this

Sharma, A., & Sharma, D. (2012). An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. In Huang, Tingwen, Z. Zhigang, Li, Chuandong, & Leung (Eds.), An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems (Vol. 7665, pp. 445-455). Berlin Heidelberg: Springer. https://doi.org/10.1007/978-3-642-34487-9_54
Sharma, Anurag ; Sharma, Dharmendra. / An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. editor / Huang ; Tingwen ; Zeng Zhigang ; Li ; Chuandong ; Leung. Vol. 7665 Berlin Heidelberg : Springer, 2012. pp. 445-455
@inproceedings{8abca4fd27644c038b025a9110a85c1f,
title = "An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems",
abstract = "Constraint satisfaction problems (CSPs) underpin many science and engineering applications. Recently introduced intelligent constraint handling evolutionary algorithm (ICHEA) in [14] has demonstrated strong potential in solving them through evolutionary algorithms (EAs). ICHEA outperforms many other evolutionary algorithms to solve CSPs with respect to success rate (SR) and efficiency. This paper is an enhancement of ICHEA to improve its efficiency and SR further by an enhancement of the algorithm to deal with local optima obstacles. The enhancement also includes a capability to handle dynamically introduced constraints without restarting the whole algorithm that uses the knowledge from already solved constraints using an incremental approach. Experiments on benchmark CSPs adapted as dynamic CSPs has shown very promising results",
keywords = "Dynamic constraint satisfaction Problem, ICHEA, Evolutionary algorithms",
author = "Anurag Sharma and Dharmendra Sharma",
year = "2012",
doi = "10.1007/978-3-642-34487-9_54",
language = "English",
isbn = "9783642344862",
volume = "7665",
pages = "445--455",
editor = "Huang and Tingwen and Zeng Zhigang and Li and Chuandong and Leung",
booktitle = "An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems",
publisher = "Springer",
address = "Netherlands",

}

Sharma, A & Sharma, D 2012, An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. in Huang, Tingwen, Z Zhigang, Li, Chuandong & Leung (eds), An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. vol. 7665, Springer, Berlin Heidelberg, pp. 445-455, 19th International Conference on Neural Information Processing 2012, Doha, Qatar, 12/11/12. https://doi.org/10.1007/978-3-642-34487-9_54

An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. / Sharma, Anurag; Sharma, Dharmendra.

An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. ed. / Huang; Tingwen; Zeng Zhigang; Li; Chuandong; Leung. Vol. 7665 Berlin Heidelberg : Springer, 2012. p. 445-455.

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

TY - GEN

T1 - An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems

AU - Sharma, Anurag

AU - Sharma, Dharmendra

PY - 2012

Y1 - 2012

N2 - Constraint satisfaction problems (CSPs) underpin many science and engineering applications. Recently introduced intelligent constraint handling evolutionary algorithm (ICHEA) in [14] has demonstrated strong potential in solving them through evolutionary algorithms (EAs). ICHEA outperforms many other evolutionary algorithms to solve CSPs with respect to success rate (SR) and efficiency. This paper is an enhancement of ICHEA to improve its efficiency and SR further by an enhancement of the algorithm to deal with local optima obstacles. The enhancement also includes a capability to handle dynamically introduced constraints without restarting the whole algorithm that uses the knowledge from already solved constraints using an incremental approach. Experiments on benchmark CSPs adapted as dynamic CSPs has shown very promising results

AB - Constraint satisfaction problems (CSPs) underpin many science and engineering applications. Recently introduced intelligent constraint handling evolutionary algorithm (ICHEA) in [14] has demonstrated strong potential in solving them through evolutionary algorithms (EAs). ICHEA outperforms many other evolutionary algorithms to solve CSPs with respect to success rate (SR) and efficiency. This paper is an enhancement of ICHEA to improve its efficiency and SR further by an enhancement of the algorithm to deal with local optima obstacles. The enhancement also includes a capability to handle dynamically introduced constraints without restarting the whole algorithm that uses the knowledge from already solved constraints using an incremental approach. Experiments on benchmark CSPs adapted as dynamic CSPs has shown very promising results

KW - Dynamic constraint satisfaction Problem

KW - ICHEA

KW - Evolutionary algorithms

U2 - 10.1007/978-3-642-34487-9_54

DO - 10.1007/978-3-642-34487-9_54

M3 - Conference contribution

SN - 9783642344862

VL - 7665

SP - 445

EP - 455

BT - An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems

A2 - Huang, null

A2 - Tingwen, null

A2 - Zhigang, Zeng

A2 - Li, null

A2 - Chuandong, null

A2 - Leung, null

PB - Springer

CY - Berlin Heidelberg

ER -

Sharma A, Sharma D. An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. In Huang, Tingwen, Zhigang Z, Li, Chuandong, Leung, editors, An Incremental Approach to Solving Dynamic Constraint Satisfaction Problems. Vol. 7665. Berlin Heidelberg: Springer. 2012. p. 445-455 https://doi.org/10.1007/978-3-642-34487-9_54