Artificial Intelligence Search Question

Question

Hello, everybody. I am working on a university timetable scheduler project. Mainly, I am using taboo search, but I want to ask:

In general search, you can explore all neighbors of the current state and then take the best state - according to a fitness or evaluation function, - but in such a project, generating all neighbors will make performance down, so is there any way that make me bypass such problem? For example, can I generate children for only one state and then benefit from this generation for all other states during the search process?

Please, if anyone has an expert in such algorithms, please tell me, because I have worked hard on such issues.

Thanks All
Hani Almousli

Answer 1

I'm no expert but it's usually not hard thinking about optimization for such calculations.
It really depends on the fitness function you use. Usually, knowing the fitness of a node you can deduce the range or even just worst to best case range of fitness of the children.
With a simple enough function you might actually be able calculate the fitness of the children even without explicitly generating them and then only generate them if its worth while.

Answer 2

Addendum to shoosh's comments: Are you looking for pruning? Numerous such strategies exist including this one. Remember, one size does not fit all. So, you will probably have to design a heuristic to suit your needs.

Answer 3

Addenda to previous comments: pruning can also be done at multiple levels, depending on your performance and memory constraints. For example:

1. Put the initial state into a priority queue.

2. Until termination (e.g. queue is empty, adequate solution found, time limit expired, ...), repeat the following:

   2.1. Take the top entry from the queue.

   2.2. Generate its children (using an estimator to get highest-value children first, if possible).

   2.3. As each child is generated, put it into the priority queue. Once the queue reaches a size limit (which you probably determine empirically by trial and error), each insertion into the queue should be accompanied by deletion of the lowest-value element in the queue.

Obviously, having good estimating/evaluating functions is important to making this work. Your queue evaluation function can be tweaked to take "generation" into account (e.g. giving a weighted bonus to states nearer the initial state, at shallower depth) to tune its bias between depth-preferences and breadth-preference.