Article Preview
TopIntroduction
The resolution of several black-box optimization problems has been possible due to the development of metaheuristics (Larrañaga & Lozano, 2001; Goldberg, 2002; Chakraborty, 2008). Also, engineering design problems have been solved by those same algorithms (Ruela, Cabral, & Aquino, 2010; Taroco, Carrano, & Neto, 2010). However, when the problem has strong correlated variables - as the deceptive problems (Goldberg, 2002) - classical metaheuristics may not have a high probability of success. The Evolutionary Compact Genetic Algorithm (ECGA) (Harik, Lobo, & Sastry, 2006) - based on the Compact Genetic Algorithm (Harik, Lobo, & Goldberg, 1999) - is an Estimation of Distribution Algorithm (EDA) (Larrañaga & Lozano, 2001) that identifies the correlated variables, called Building Blocks (BBs), and uses a recombination operator to combine the best found partial solutions of each BB in order to generate a new full solution of the problem.
This paper proposes the use of the Phylogenetic Differential Evolution (PhyDE) to identify the BBs of a deceptive problem. This technique employs a clustering algorithm named Neighbor Joining (Saitou & Nei, 1987), commonly used in Biology to create Phylogenetic Trees (Felsenstein, 2003).
While most EDAs, including ECGA, aim to find the BBs in each generation, Phylogenetic Algorithms (Vargas, Delbem, & de Melo 2010) first applies a process to identify the BBs of a problem, and soon after the BBs have been known, a local search algorithm, usually an exhaustive search, is applied to each BB in order to find its optimum configuration.
However, an exhaustive search must be avoided when a BB is composed of several bits, due to the exponential complexity of the problem. Thus, a better alternative to locate the optimum configuration must be used. The idea is to replace the exhaustive search with metaheuristics, and more than that, to employ an efficient metaheuristic incapable of solving large deceptive problems. To achieve this goal, a type conversion from binary to integer is required. Since the Differential Evolution (DE) algorithm presents one of the best results in the resolution of several problems (García, Molina, Lozano, & Herrera, 2009), it was chosen as the optimization algorithm to be used in this project.
Hard problems solved by EDAs are usually characterized by the number of variables, number of BBs that compose the problem, and their size. While the problem size is appropriately treated by existing algorithms, the size of the BBs is not. This is the main contribution of the proposed PhyDE. EDAs solve these problems using large number of evaluations (Harik, Lobo, & Sastry, 2006; Pelikan, Goldberg, & Cantú-Paz, 1999). By contrast, the proposed method is capable of solving problems with larger BBs in as few as half the number of evaluations. In general, results of EDAs are presented for BBs of size four. The experiments presented in this paper show a comparison using BBs composed of eight variables.
This paper is organized as followed: the next section introduces the concept of BBs and deceptive functions which are commonly used to test the performance of different EDAs. After that, we briefly present the way other algorithms find BBs, and then, we present methods of phylogenetic reconstruction used to identify BBs. Following this, two sections introduce the Phylogenetic Algorithms and the proposed PhyDE algorithm, which is composed of three sections detailing its steps: the construction of the Distance Matrix, the Neighbor Joining method and the construction of metavariables, and the Differential Evolution algorithm, used by the PhyDE to locate the optimum configuration for the identified BBs. Finally, the last section contains the explanation of the conducted experiments, and the results that show its efficiency. The results have shown that the technique proposed in this paper is approximately twice more efficient than the known ECGA.