Announcement for Downloading full text filePlease respect the Copyright Act.
All digital full text dissertation and theses from this website are authorized the copyright owners. These copyrighted full-text dissertation and theses can be only used for academic, research and non-commercial purposes. Users of this website can search, read, and print for personal usage. In respect of the Copyright Act of the Republic of China, please do not reproduce, distribute, change, or edit the content of these dissertations and theses without any permission. Please do not create any work based upon a pre-existing work by reproduction, Adaptation, Distribution or other means.
URN etd-0728104-092228 Statistics This thesis had been viewed 3159 times. Download 1195 times. Author Mei-Ching Chen Author's Email Address firstname.lastname@example.org Department Computer Science and Enginerring Year 2003 Semester 2 Degree Master Type of Document Master's Thesis Language English Page Count 72 Title Q'tron Neural Networks for Constraint Satisfaction Problems Keyword Question Answering Q'tron Neural Networks Constraint Satisfaction Problems Known-Energy System N-Queen Problem N-Queen Problem Known-Energy System Constraint Satisfaction Problems Q'tron Neural Networks Question Answering Abstract This thesis focuses on solving the constraint satisfaction problems using the Q'tron neural network (Q'tron NN) model, which is an extension of the Hopfield NN model. Due to a vast number of local minima, a Hopfield NN usually will pathologically report an unsatisfactory solution. To alleviate the symptom, a Hopfield NN is usually equipped with a noise-injection mechanism based on simulated annealing, e.g., Boltzmann machine and Cauchy machine. Although simulated annealing usually is able to improve a certain degree of solution quality, it doesn't guarantee that the final solution is optimal unless the system temperature is cooled down extremely slow. Moreover, the strength of random noise injected into each neuron is possibly unbounded at any time unless the system temperature has reached zero. This may lead the system to move toward a wrong direction, e.g., to depart from an optimal state. In fact, the systems controlled by simulated annealing are unknown-energy systems, to be detailed in the thesis.
The Q'tron NNs, on another hand, solve problems in a known-energy sense. That is, the lower energy range specified using the so-called solution qualifier, corresponding to a set of satisfactory solutions is known a priori. With such a piece of knowledge, the bounded noise spectra for Q'trons can be systematically determined. Injecting such random noises into Q'trons, the NN, as a result, will only settle down on a state whose energy is sufficiently low, i.e., the solution quality satisfies the criterion described by the solution qualifier. Therefore, the Q'tron NN will never report a false solution when it settles down. This is particularly important for solving constraint satisfaction problems. Besides, the known-energy property will render the NN intrinsically auto-reversible and, hence, enable the NN to be operated in a question-answering mode. A Q'tron NN to solve N-queen problem is demonstrated to highlight the concept, and the performance analysis with respect to the parameters of the Q'tron NN model is also provided.
Advisor Committee Tai-Wen Yue - advisor
Chang-Wu Yu - co-chair
Shang-Lin Hsieh - co-chair
Tai-Wen Yue - co-chair
Files Date of Defense 2003-07-23 Date of Submission 2004-07-28