Tilted Forum Project Discussion Community  

Go Back   Tilted Forum Project Discussion Community > Interests > Tilted Technology


 
 
LinkBack Thread Tools
Old 03-01-2004, 03:57 AM   #1 (permalink)
Addict
 
Location: Grey Britain
Databases, Optimisation and Search Algorithms

I need to write a program that searches a very large databse with a view to optimising the value of a particular variable (or perhaps I should say field). Most of the fields in the database will be numerical and inter-related, but some are not. For this reason, I have been thinking of using a Genetic Algorithm or an Annealing Algorithm of some description, but this would not guarantee an absolute optimum value. I'm wondering if anyone has any good ideas on how to ensure an absolute optimum without having to perform a comprehensive search.
__________________
"No one was behaving from very Buddhist motives. Then, thought Pigsy, he was hardly a Buddha, nor was he a monkey. Presently, he was a pig spirit changed into a little girl pretending to be a little boy to be offered to a water monster. It was all very simple to a pig spirit."
John Henry is offline  
Old 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..
kel is offline  
Old 03-20-2004, 02:34 PM   #3 (permalink)
Once upon a time...
 
optimality cannot be acheived in a guaranteed fashion through stochastic methods.

IDA* is a good idea, kel's answer is pretty comprehensive. But I find it hard to think of a goal, unless you can test for optimality arbitrarily.

So you might be looking at B&B.

It's difficult to suggest something without knowing more about the problem, but you might be able to pre-calculate some predictor.

Try examining statistical methods before you do anything else.

Ideally, you could cook up some correlation factor and just extract the best one of those. If you are going down the annealing / genetic line, you must have a fitness function. Why not just apply the fitness function to the data? It means a comprehensive search, but you might be able to subdivide the data by sorting it and bounding it.
__________________
--
Man Alone
=======
Abstainer: a weak person who yields to the temptation of denying himself a pleasure.
Ambrose Bierce, The Devil's Dictionary.

Last edited by manalone; 03-20-2004 at 02:37 PM..
manalone is offline  
 

Tags
algorithms, databases, optimisation, search

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT -8. The time now is 04:51 AM.

Tilted Forum Project

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Search Engine Optimization by vBSEO 3.6.0 PL2
© 2002-2012 Tilted Forum Project

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360