Improved and generalized learning strategies for dynamically fast and statistically robust evolutionary algorithms

Abstract

This paper characterizes general optimization problems into four categories based on the solution representation schemes, as they have been the key to the design of various evolutionary algorithms (EAs). Four EAs have been designed for different formulations with the aim of utilizing similar and generalized strategies for all of them. Several modifications to the existing EAs have been proposed and studied. First, a new tradeoff function-based mutation has been proposed that takes advantages of Cauchy, Gaussian, random as well as chaotic mutations. In addition, a generalized learning rule has also been proposed to ensure more thorough and explorative search. A theoretical analysis has been performed to establish the convergence of the learning rule. A theoretical study has also been performed in order to investigate the various aspects of the search strategy employed by the new tradeoff-based mutations. A more logical parameter tuning has been done by introducing the concept of orthogonal arrays in the EA experimentation. The use of noise-based tuning ensures the robust parameter tuning that enables the EAs to perform remarkably well in the further experimentations. The performance of the proposed EAs has been analyzed for different problems of varying complexities. The results prove the supremacy of the proposed EAs over other well-established strategies given in the literature.

Introduction

Since its advent, evolutionary optimization has gone through various stages of evolution that have made it more robust and fast; robust enough to be applied to all spheres of optimization problems and fast enough to take decisions in micro-seconds (Dimopoulos and Zalzala, 2000; Nissen and Propach, 1998; Yao et al., 1999). In the present scenario, evolutionary algorithms (EAs) are not limited to the applications in artificial intelligence, and have been increasingly used in various dimensions to solve real world problems (Dimopoulos and Zalzala, 2000; Sinha et al., 2003). Although, a plethora of literature pertaining to the search strategies adopted by various EAs is available (Nissen and Propach, 1998; Rana et al., 1996; Kazarlis et al., 2001; Yao et al., 1999; Salomon, 1998; Choi and Oh, 2000; Yoon and Moon, 2002; Kim and Myung, 1997; Storn, 1999), most of them restrict themselves to solving a particular class of optimization problem and thus, fail to provide generalized strategies that can be robustly used for wide spectrum of optimization problems in science, business and engineering applications. In general, optimization problems can be classified into two groups—numerical optimization and combinatorial optimization (Tsai et al., 2004; Gen and Cheng, 1999). Yet another classification exists that is based on the representation schemes—binary string, floating point string and integer bit string representation (Rana et al., 1996; Kazarlis et al., 2001; Yao et al., 1999; Salomon, 1998; Choi and Oh, 2000; Yoon and Moon, 2002; Kim and Myung, 1997; Storn, 1999; Zhang and Leung, 1999; Burke and Newall, 1999). In general, the first two representations are more suited and easy to implement on numerical optimization problems; whereas, the third representation enjoys solving the combinatorial optimization problems with a greater ease and efficiency (Nijssen and Bäck, 2003; Goldberg, 1989). Thus, to propose effective algorithms that would efficiently work in all the representations is a convoluted task. The schematic representation of various optimization problems along with their most suited representation classes are shown in Fig. 1.

All of the above-mentioned factors motivated the authors to propose robust and fast EAs with improved learning strategies to achieve the global optimization in all of these cases. Before introducing the proposed algorithms, the general formulation of a numerical optimization problem can be mathematically described as

$$\mathrm{minimize}g(\mathbf{t}),\mathbf{t}=(t_1,t_2,\dots ,t_n)\in {\mathbf{\Lambda }}^n\text{,}$$

where t∈Γ∩X,Γ represents the ‘feasible region’ defined as

$$\mathbf{\Gamma }=\{\mathbf{t}\in {\mathbf{\Lambda }}^n|c_j(\mathbf{t})⩽0\forall j\in \{1,2,\dots ,J\}\}\text{,}$$

where $c_j(\mathbf{t}),j\in \{1,2,\dots ,J\}$ are the ‘constraints’ on the problem; the n-dimensional ‘search space’ is defined by X⊆Λⁿ and is constrained by the ‘parametric constraints’ given below:

$$\underline{t_i}⩽t_i⩽{\overline{t}}_i,i\in \{1,2,\dots ,n\}$$

where $\underline{t_i}$ and ${\overline{t}}_i$ represent the lower and upper limits of the variable t_i. Here, it is evident that the solution is represented as floating point string of type A (Fig. 1); however, it can also be represented in the binary string (type B of Fig. 1) by considering the representation of floating numbers into binary numbers.

For the second class of optimization problems, i.e. combinatorial optimization problems, the general formulation can be given as

$$\mathrm{minimize}h(\mathbf{s})\mathbf{s}=(s_1,s_2\dots s_n)\in \mathbf{S}\text{,}$$

where S is the set of integers; $\mathbf{s}\in \mathfrak{J}\cap \Re ,\mathfrak{J}$ denotes the ‘feasible range’ of variables and is given by

$$\mathfrak{J}=\{\mathbf{s}\in \mathbf{S}|c_j^{\prime }(\mathbf{s})⩽0\forall j\in \{1,2,\dots ,J^{\prime }\}\}\text{,}$$

where c′_j(s) represents the ‘constraints’ of the problem; the ‘search range’ $\Re$ is defined by $\Re \subseteq \mathbf{S}$, which is constrained by the ‘individual range’ defined by

$${\underline{c}}_i^{\prime }⩽c_i^{\prime }⩽{\overline{c}}_i^{\prime },i\in \{1,2,\dots ,n\}\text{,}$$

where ${\underline{c}}_i$ and ${\overline{c}}_i^{\prime }$ are the lower and upper limits of the variable c′_j. Generally, this formulation is utilized for the type D representation. However, the representation type C is used in the combinatorial problems class mapped by traveling salesman problem (TSP). Its general formulation is described as

$$\mathrm{minimize}{f}_{\mathrm{TSP}}=\sum _{i=1}^N\sum _{j=1}^N{\mathrm{dist}}_{\mathit{ij}}{\Omega }_{\mathit{ij}}\forall i,j\in \{1,2,\dots ,N\}\text{,}\mathrm{and}i\ne j\text{,}$$

where

$${\Omega }_{\mathit{ij}}=\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{node}i\mathrm{and}j\mathrm{are}\mathrm{selected}\mathrm{in}\mathrm{the}\mathrm{tour},\hfill \\ 0\hfill & \mathrm{otherwise},\hfill \end{array}$$

subject to the constraints c_j″, j={1, 2, …, n}, where N is the number of nodes; dist_ij is the distance between nodes i and j; Here, only minimization cases are considered as the problems pertaining to maximization of objective can also be mapped into minimization problem by making suitable changes in the formulation.

Owing to the existence of all these formulations, authors intend to present some improved learning rules suited to each formulation in order to eliminate the difficulty and dilemma of the practitioners and users of EAs while searching the best strategy for their problem. In addition to this, various testing phases based on design of experiments are introduced in order to achieve robust parameter control and tuning.

In the earlier studies, various modifications to the initial versions of EAs have been proposed to suit the varying complexity of the optimization problems. Some of the vital factors that affect the search strategy of the EAs are: (1) population representation, (2) information sharing among members of the population, (3) mutation of the current population, (4) generation scheme for new population, (5) learning from previous generations (Kazarlis et al., 2001; Yao et al., 1999; Salomon, 1998; Choi and Oh, 2000; Yoon and Moon, 2002; Kim and Myung, 1997; Storn, 1999; Zhang and Leung, 1999; Burke and Newall, 1999; Eiben et al., 1999; Harik et al., 1999; Michalewicz et al., 2000; Runarsson and Yao, 2000; François and Lavergne, 2001; Kazarlis et al., 2001; Ong and Keane, 2004). Even a small variation in any of these factors has a considerable effect on the EA performance.

The following discussion provides an insight to some of the recent developments in the field of evolutionary computation. In order to do away the slow convergence of the classical evolutionary programming (CEP), Yao et al. (1999) introduced fast evolutionary programming (FEP) that utilized the mutation based on Cauchy function because of its higher probability of making longer jumps Runarsson and Yao (2000) introduced a novel approach to balance objective and penalty functions stochastically, i.e. ‘stochastic ranking’ and presented a fresh view on penalty function methods in terms of dominance of penalty and objective functions. Salomon (1998) presented a new hybrid approach, the evolutionary-gradient-search method for the problems pertaining to numerical optimization. A much broader collection of developments in evolutionary computation for manufacturing optimization can be found in Dimopoulos and Zalzala (2000). Zhang and Leung (1999) proposed an orthogonal genetic algorithm for multimedia cast routing that incorporated orthogonal design to crossover operation. Francois (1998) presented a mutation or selection evolutionary strategy (MOSES) to solve complex discrete optimization problems. It theoretically studied the relationship between convergence, parameters of the method, and the geometry of the optimization problem. An extensive empirical study on the synergy among multiple crossover operators has been provided in Yoon and Moon (2002).

Choi and Oh (2000) presented a new mutation rule for evolutionary programming (EP) that has been motivated from the back-propagation learning rule of the neural networks. A method of decomposing larger problems into smaller components, each of which is of a size that the EA can effectively handle, was proposed by Burke and Newall (1999) to solve timetabling problem. Eiben et al. (1999) provided a broader classification for parameter control mechanisms of EAs. They also provided a survey of various types of control that have been used by evolutionary computation community. A statistical method was described by François and Lavergne (2001), which was able to find good parameter settings for EAs. The method utilized a functional relationship between the algorithms performance and its parameter values. Yet another statistical approach can be found in Czarn et al. (2004).

Ahn and Ramakrishna (2003) described two elitism-based compact genetic algorithms in order to design efficient compact type GAs by treating them as the estimation of distributed algorithms (EDAs) to efficiently solve complex optimization problems. The compact GAs utilized the concept of successive learning in generations utilizing the probability strings for the solution representation. Various other learning approaches also persist in the literature. In general, learning algorithms are termed as learning automata approaches (Najim and Poznyak, 1994). In Agache and Oommen (2002), two new generalized pursuit algorithms were presented that falls in the category of fastest learning automata algorithms. Howell et al. (2002) proposed a hybrid genetic and learning automata approach that enjoys the merits of both the strategies. Various other relevant work like Papadimitriou (1994), Najim and Poznyak (1994) in the context of learning algorithms need to be mentioned here.

Many works have been reported in literature in order to map the system chaos and noise within the working dimensions of EAs (Nissen and Propach, 1998; Rana et al., 1996; Caponetto et al., 2003). Caponetto et al. (2003) introduced chaotic sequences instead of random sequences during all the phases of random evolution process. The approach was based on the spread spectrum characteristic of chaotic sequences. In Nissen and Propach (1998), noise function was introduced to the deterministic objective function values in order to map the practical scenario of the existence of noise while experimentation, stochastic simulation, sampling and even interaction with users.

As it can easily be manifested from the above literature review that though a wide range of modifications have been carried out to enhance the performance of EAs, a robust strategy is mandatory that can work in general for various formulations of objective functions found in the real world scenario. Also, an all purpose strategy for robust parameter control and tuning in the presence of noise is essential to help the practitioners of EAs to come out of the dilemma of choosing the control and tuning methods in changing situations.

The aims of this paper are manifold. First, it introduces the concept of developing general-purpose fast EAs that equivalently achieve better results in all the previously mentioned formulations (i.e. A, B, C, and D). Second, it utilizes the enhanced learning mechanisms for all these formulations in order to achieve better tradeoff between exploration and exploitation of the search space; and to achieve time gain over prevailing strategies. This has also been theoretically validated. Third, it introduces a new tradeoff function to decide the mutation step size. This function makes a tradeoff between the fast convergence of Cauchy function and the explorative search of Gauss function to achieve better solutions. Fourth, the chaotic sequences to map the random dynamics have also been utilized to mutate the solutions. Thus, the evolutionary strategies utilized in the paper, the mutation at each step is performed both by the tradeoff function and the chaotic sequence generator and the better offspring is evolved further. Fifth, the paper proposes a design of experiments model to conduct various experiments sequentially utilizing the orthogonal array that symbolizes the variation in various parameter values. This approach reduces the tedious task of parameter control and tuning that were earlier carried out by exhaustive experiments. Comparisons with the existing EAs are also carried out that utilize the well-designed experiments, and thus the efficacy of the strategies has been established. Finally, the noise factor has been incorporated in the deterministic objective function value, and designed experiments are conducted to establish the robustness of the algorithm.

The rest of the paper is organized in the following sequence: The next section introduces the main intricacies in defining the general-purpose EAs. Section 3 introduces new generalized learning strategies and presents the new guided mutation rule. It also provides the general-purpose algorithms for all the four problem types. Section 4 deals with the mathematical aspects of the proposed algorithms and establishes their convergence. Section 5 provides the classification of the test functions utilized to evaluate the effectiveness of the proposed algorithm for numerical optimization problems on the basis of their dimensional complexity and degree of entrapment. It also presents the test problems of combinatorial optimization utilized for the comparative study. Section 6 formulates the design of experiments for the parameter tuning and the analytical study of the proposed algorithm. The results of the extensive computational experiments, inferences drawn from it and related discussions are presented in Section 7. Section 8 concludes the paper.