4487

4216

كارشناسي ارشد

هوش مصنوعي و رباتيك

اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر

1387

نه، 96،[II] ص: مصور، جدول،نمودار

ص.ع. به انگليسي و فارسي

رسول موسوي

مازيار پالهنگ

29/2/1388

مهندسي برق و كامپيوتر

ID4216

به فارسي وانگليسي: قابل رويت درنسخه ديجيتال

Improving memory based heuristics in single agent searches Maryam Siahbani siabani@ec iut ac ir Date of Submission March 8 2009 Department of Electical and computer engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor Seyed Rasoul Mousavi srm@cc iut ac irAbstractObtaining optimal solution for most of the real world problems requires an exhaustive search through theproblem state space by considering all possible solutions To solve these problems more efficiently manydifferent heuristic search algorithms like A IDA KBFS etc have been proposed All of these algorithmsmake use of a heuristic evaluation function to evaluate the problem states The performance of such searchalgorithms depends on the accuracy of the heuristic functions In single agent search domains heuristicfunctions compute an estimate of the solution cost from the current state to the goal state If the heuristicfunction is admissible i e it never overestimates the cost of reaching the goal A and its variations areguaranteed to return an optimal solution if one exist The more accurate the heuristic function is the moreefficient the search algorithm will be Much research has been devoted to developing more accurate heuristicfunctions The main purpose of this thesis is to develop methods to improve the accuracy and the quality ofheuristic functions One of the important admissible heuristic functions already proposed is Pattern Databases PDBs whichis the state of the art method to optimally solve many combinatorial problems The main drawback of PDBsis the amount of memory they needed to store the database In this research we first try to solve the PDBmemory requirement problem We first introduce a new and general method to compress PDBs by usingmachine learning techniques Experimental results show the improvement achieved by our method over theprevious compression methods with respect to the amount of memory the number of generated nodes andconsequently run time Experimental results show that our full compression system reduces the size ofrequired memory by a factor of up to 61 In the second part of this thesis we use the Perimeter Search PS technique to improve the quality of theheuristic functions We suggest an efficient method to combine PS with PDBs The regular combination ofPS with PDBs needs a large amount of memory to save the PDBs We introduce a novel method to mapdifferent states of the problem to the goal state This allows us to combine these two methods by using alimited amount of memory We experimentally show that our method outperforms the state of the arttechniques Key words Heuristic Search Pattern Databases Compression Decision Tree Artificial Neural Networks Perimeter Search

رسول موسوي

مازيار پالهنگ