TABU SEARCH WHEN NOISE IS PRESENT - AN ILLUSTRATION IN THE CONTEXT OFCAUSE AND EFFECT ANALYSIS

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than de terministic ones. When randomness is present in a problem, algorithm d esigners face new difficulties which complicate their task significant ly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment whe re the quality of feasible solutions cannot be computed easily. This n ew search principle is illustrated in the field of cause and effect an alysis where the true cause of an undesirable effect needs to be elimi nated. A set of n potential causes is identified and each of them is a ssumed to be the true cause with a given probability. The time to inve stigate a cause is a random variable with a known probability distribu tion. Associated with each cause is the reward obtained if the cause i s really the true cause. The decision problem is to sequence the n pot ential causes so as to maximize the expected reward realized before a specified time horizon.