Biasing Bayesian Optimization Algorithm using Case Based Reasoning

Studies show that application of the prior knowledge in biasing the Estimation of Distribution Algorithms (EDAs), such as Bayesian Optimization Algorithm (BOA), increases the efficiency of these algorithms significantly. One of the main advantages of the EDAs over other optimization algorithms is that the former provides a trail of probabilistic models of candidate solutions with increasing quality. Some recent studies have applied these probabilistic models, obtained from previously solved problems in biasing the BOA algorithm, to solve the future problems. In this paper, in order to improve the previous works and reduce their disadvantages, a method based on Case Based Reasoning (CBR) is proposed for biasing the BOA algorithm. Herein, after running BOA for solving optimization problems, each problem, the corresponding solution, as well as the last Bayesian network obtained from the BOA algorithm, will be stored as an entry in the case-base. Upon introducing a new problem, similar problems from the case-base are retrieved and the last Bayesian networks of these solved problems are combined according to the degree of their similarity with the new problem; hence, a compound Bayesian network is constructed. The compound Bayesian network is sampled and the initial population for the BOA algorithm is generated. This network will be applied efficiently for biasing future probabilistic models during the runs of BOA for the new problem. The proposed method is tested on three well-known combinatorial benchmark problems. Experimental results show significant improvements in algorithm execution time and quality of solutions, compared to previous methods.

► Application of the prior knowledge in biasing the Estimation of Distribution Algorithms (EDAs) increases their efficiency.
► One of the main advantages of the EDAs is that it provides a trail of probabilistic models of candidate solutions.
► In this paper, a method based on Case Based Reasoning is proposed to bias the BOA using its former probabilistic models.
► Herein, when a new problem arises, similar problems are retrieved and their Bayesian networks are used to bias the BOA.
► Experimental results show significant improvements in algorithm execution time and quality of solutions.