Tilted Forum Project Discussion Community - View Single Post - Databases, Optimisation and Search Algorithms

kel · 03-01-2004, 09:19 AM

Without know anything about the nature of the problem space I can't say much.

Short answer: You can't. If you want to the perfect answer there is no substitute for IDA* and an admissible heuristic.

Long answer: It depends how effective your heuristics are and whether the problem space has many local maximums on the path to most good solutions.

How big is this database and is this a single value your trying maximize or a set of values that you wish to maximize.

The real bottomline comes down to the heuristic you develop. Start with subsets (REPRESENTATIVE subsets) of the data and compare the performance of various heuristics. Whether you use GA, Annealing, or local beam search (you should implement all three and see which works best with each heuristic).

Pretty printing is suprisingly useful in developing heuristics, the more information you have about what is going on during the actual search the more intuition you will have available to you for developing heuristics.

Also keep an eye on performance, a cleaner program will expand states faster, and allow you to gather results more quickly. Frequently with careful optimization you can make a simulation that runs in hours run on order of minutes. This isn't very important when your running the simulation for real, but when your developing and you need to run it many times to compare heuristics it can be a big deal.

More then anything else your choice of representation will dictate the performance of expansions. It's the usual balance between space and time, so if you have the space... use it! It will save you many hours twiddling your thumbs.

03-01-2004, 09:19 AM	#2 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	Without know anything about the nature of the problem space I can't say much. Short answer: You can't. If you want to the perfect answer there is no substitute for IDA* and an admissible heuristic. Long answer: It depends how effective your heuristics are and whether the problem space has many local maximums on the path to most good solutions. How big is this database and is this a single value your trying maximize or a set of values that you wish to maximize. The real bottomline comes down to the heuristic you develop. Start with subsets (REPRESENTATIVE subsets) of the data and compare the performance of various heuristics. Whether you use GA, Annealing, or local beam search (you should implement all three and see which works best with each heuristic). Pretty printing is suprisingly useful in developing heuristics, the more information you have about what is going on during the actual search the more intuition you will have available to you for developing heuristics. Also keep an eye on performance, a cleaner program will expand states faster, and allow you to gather results more quickly. Frequently with careful optimization you can make a simulation that runs in hours run on order of minutes. This isn't very important when your running the simulation for real, but when your developing and you need to run it many times to compare heuristics it can be a big deal. More then anything else your choice of representation will dictate the performance of expansions. It's the usual balance between space and time, so if you have the space... use it! It will save you many hours twiddling your thumbs. __________________ "It better be funny" Last edited by kel; 03-01-2004 at 10:14 AM..