Efficient model building in competent genetic algorithms using DSM clustering

Article type: Research Article

Authors: Nikanjam, Amin | Sharifi, Hadi | Rahmani, Adel T.

Affiliations: School of Computer Engineering, Iran University of Science and Technology, Narmak, Tehran 1684613114, Iran. E-mails: nikanjam@iust.ac.ir, hsharifi@comp.iust.ac.ir, rahmani@iust.ac.ir

Note: [] Corresponding author. E-mail: nikanjam@iust.ac.ir.

Abstract: Detecting multivariate interactions between the variables of a problem is a challenge in traditional genetic algorithms (GAs). This issue has been addressed in the literature as the linkage learning problem. It is widely acknowledged that the success of GA in solving any problem depends on the proper detection of multivariate interactions in the problem. Different approaches have thus been proposed to detect and represent such interactions. Estimation of distribution algorithms (EDAs) are amongst these approaches that have been successfully applied to a wide range of hard optimization problems. They build a model of the problem to detect multivariate interactions, but the model building process is often computationally intensive. In this paper, we propose a new clustering algorithm that turns pair-wise interactions in a dependency structure matrix (DSM) into an interaction model efficiently. The model building process is carried out before the evolutionary algorithm to save computational burden. The accurate interaction model obtained in this way is then used to perform an effective recombination of building blocks (BBs) in the GA. We applied the proposed approach to solve exemplar hard optimization problems with different types of linkages to show the effectiveness and efficiency of the proposed approach. Theoretical analysis and experiments showed that the building of an accurate model requires O(nlog (n)) number of fitness evaluations. The comparison of the proposed approach with some existing algorithms revealed that the efficiency of the model building process is enhanced significantly.

Keywords: Estimation of distribution algorithm, model building, linkage learning, dependency structure matrix

DOI: 10.3233/AIC-2011-0498

Journal: AI Communications, vol. 24, no. 3, pp. 213-231, 2011