Constraint Satisfaction Problem For A Class Of Weight Learning Algorithm

Constraint satisfaction problem is one of the core problems in artificial intelligence. Constraint satisfaction technology has been widely applied in several areas such as engineering, computer science, etc. In recent years random and incomplete search algorithms, especially the local search algorithms, have been found to be effective in tackling the large constraint satisfaction problems(CSPs). Most local search algorithms incorporate various schemes that enhance local search to escape from local minima. GENET is a connectionist approach to constraint satisfaction and is a general local search algorithm. A CSP is represented by a network in which the nodes represent possible assignments to the variables and the edges represent constraints. One of the innovations in GENET is the use of and manipulation of weights assigned to the edges. The cost function is the sum of the weights tied to the violated constraints. The mm-conflicts heuristic repair local search procedure will ensure GENET convergence to some states, which could be solutions or local minimum. Each time the network converges to a local minimum, the weights associated to the violated constraints are decreased by 1, and the network is then allowed to converge again. Such weight-learning cycles continue until a solution is found or a stopping condition is satisfied. In this paper we extend and evaluate the GENET in a number of ways. Firstly two methods, the quickly determination of rational weights and the prevention of over distortion to the cost function are introduced as new features of RQ-GENET compared with GENET. Also a euristic Replace strategy is advanced to avoid the inefficiency during later search period. The HRT algorithm is the result of coupling RQ-GENET with "Heuristic Replace" strategy. Both RQ-GENET and HRT are outperform GENET more than 10 times in solving some famous RLFAP benchmarks. Secondly, a general algorithm, SWLA, is released by abstracting from several weight-learning algorithm including GENET. Further the SWLA is improved from two aspects to form the MCWLA algorithm. In the first place, to remove the side effect caused by constantly increasing the weights, a procedure that decrease every weight in proportion is embedded to restore the average weight to a preset value. In the second place, in order to exploit the information during the search process, we produce a weight-based crossover operator to hybridize the hunted local minima which enable the algorithm to search larger hopeful areas. MCWLA shows better performance than the famous GSAT in computing some very difficult graph coloring problem benchmarks. Moreover, it can find optimal solution in reasonable time while GSAT cannot even given a long time. Finally, The methods of incorporating some domain knowledge into the weight-learning algorithm are studied. Two concepts, "strong constraint" and "weak constrain" are introduced. We also reveal that the method of converting Hstrong constraint violation to "weak constraint violation" according to the problem speciality can greatly improve the performance. GENET-TP, a university examination timetabling algorithm, is brought forward in the light of this idea. Again our algorithm outperforms GENET. Moreover, it is quicker than the genetic algorithm which considered to be the best timetable algorithm for more than 100 times.