Extending GENET to Solve Fuzzy Constraint Satisfaction Problems

Jason H. Y. Wong, Ho-fung Leung

Despite much research that has been done on constraint satisfaction problems (CSP’s), the framework is sometimes in exible and the results are not very satisfactory when applied to real-life problems. With the incorporation of the concept of fuzziness, fuzzy constraint satisfaction problems (FCSP’s) have been exploited. FCSP’s model real-life problems better by allowing individual constraints to be either fully or partially satisfied. GENET, which has been shown to be efficient and effective in solving certain traditional CSP’s, is extended to handle FCSP’s. Through transforming FCSP’s into 0 - 1 integer programming problems, we display the equivalence between the underlying working mechanism of fuzzy GENET and the discrete Lagrangian method. Simulator of fuzzy GENET for single-processor machines is implemented. Benchmarking results confirm its feasibility in tackling CSP’s and exibility in dealing with over-constrained problems.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.