This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
The field of time series forecasting has grown up with the advent of greater computing power. During the past few decades, Genetic Algorithm (GA) has received a lot of attention. Due to its ease of applicability, numerous applications of GA are found. Double Exponential Smoothing is a technique that "smooths" the trend component in the data. There are two type of Double Exponential Smoothing i) Brown's One Parameter Linear Method ii) Holt's Two Parameter Method. One of the weaknesses in Double Exponential Smoothing methods is the parameters selection in model. Here, we propose to refine the Double Exponential Smoothing method by using GA in the parameters estimation. GA provides an alternative in determining the parameters in the Double Exponential Smoothing. Data from i) daily Kuala Lumpur Composite Index (KLCI) from January 2009 to September 2009 ii) daily USD/Ringgit exchange rate selling price in Forex Exchange from April 2008 to May 2009 were used in this study. A software name "DES system" has been developed as an interactive forecasting system for forecasting using the Double Exponential Smoothing method with the exploitation of GA. This software is written using Microsoft Visual C++ (with Microsoft Foundation Class (MFC)). The result shows that the Double Exponential Smoothing using GA in searching for the parameter has greatly improve its accuracy.
Keywords: Genetic Algorithm, forecasting, Double Exponential Smoothing, heuristic
Times Series forecasting techniques include exponential smoothing, regression model, autoregressive and moving average (ARMA), etc. Recently, an alternative approach for Time Series Forecasting has arises from the Artificial Intelligence (AI) field (Paulo Cortez et al., 2001). Artificial Intelligence (AI) algorithms include Artificial Neural Network (ANNs), Fuzzy method, CBR, Genetic Algorithm (GA) and data envelopment analysis, etc (Pei-Chann Chang et al., 2005). In particular, studies on the biological evolution Genetic Algorithms (GA) had enriched the potential use of AI. However, it is surprising to realize that the application of GA in forecasting is so scarce. Genetic Algorithm was pioneered in 1975 by Holland. The GA concept is to mimic the nature evolution of a population. The solution will compete for survival and the fitness of the solution improves over generations.
The Exponential Smoothing method is a popular tool in short-term forecasting. Double Exponential Smoothing is the specified smoothing method which handles time series data with trend. There are two type of Double Exponential Smoothing i) Brown's One Parameter Linear Method ii) Holt's Two Parameter Method.
Brown's prediction is described by (B Sliwczynski, 1992; Vijendra Kumar et al., 2000; Spyros Makridakis, 1976):
Single exponential smoothed value:
Double exponential smoothed value:
Adjustment of exponential smoothing:
Forecast for m period ahead:
Let , (6)
Holt's way of prediction is simpler than Brown's method because it does not use the dual smoothing (B Sliwczynski, 1992). Holt's prediction is described by (B Sliwczynski, 1992; Vijendra Kumar et al., 2000; Spyros Makridakis, 1976):
Let , (10)
A major drawback to the application of Double Exponential Smoothing (DES) in practice is the question of how to determine an appropriate value of the weighting factor or parameters. The determination of parameters value is crucial but difficult. The value chosen for parameters greatly affects accuracy.
There is no specified rule to determine parameters in Double Exponential Smoothing. Mostly, parameters are decided by forecaster intuitively or through trial and error. Don E. Gardner (1981) and Vijendra Kumar Boken (2000) are suggest writing computer program that consider the all parameters value ranging from 0.1 to 0.9 (with an interval 0.1). In this case, all the parameters combinations are considered. Then, select the one with minimum statistical error. Unfortunately, the methods mention as above is time consuming and costly.
Therefore, a good optimization technique is requiring for the best value parameters in minimizing the error values. Here, we proposed the refinement of Double Exponential Smoothing methods by using Genetic Algorithm search procedure for parameter estimations. Instead of consider the parameters with an interval 0.1; we are taking the parameters with an interval of 0.01. Using converging characteristics of Genetic Algorithm, we found the optimal solution (Zuhaimy Ismail, 2008).
INTEGRATION GENETIC ALGORITHM WITH DOUBLE EXPONENTIAL SMOOTHING
A software name DES system has been developed specifically as an interactive system for forecasting using Double Exponential Smoothing (specified for handle trend data). The aim of DES system is to search the smoothing parameter (0< <1 for Brown's and 0< <1, 0< <1 for Holt's) using Genetic Algorithm. This system is suitable for all type of time series data as long as the series contained trend factor (satisfied the nature of Double Exponential Smoothing). This software is written using Microsoft Visual C++ (with Microsoft Foundation Class (MFC)). It is a user-friendly system that is able to process the result within a short time. The step of integration Double Exponential Smoothing (DES) with Genetic Algorithm (GA):
Step 1: Initialization. Setting initial evolution step t= 1; setting the maximal evolution (maximum numbers of generations) step t=q (Ching-Hsue Cheng et al., 2010). Randomly generates an initial population, of size n. There is no clear theoretical formulae exist for the appropriate population size (Harun Kemal Ozturk, 2005). These initial solutions form the first population (Pei-Chann Chang, 2005). These potential solutions called "chromosomes" are allowed to evolve over a number of generations (improve it through repetitive application of mutation, crossover and selection operators).
Step 2: Decode the chromosomes. Decode the chromosomes to map the corresponding real numbers (Harun Kemal Ozturk et al., 2005). In here, we have two type of chromosome: i) chromosome with bits of length 7 when user choose to do Brown's model simulation (with parameter) ii) chromosome with bits of length 14 when user choose to do Holt's model simulation (with parameters and).
Step 3: Compute the fitness function. Evaluate the fitness of each individual in the population (Anant Oonsivilai et al., 2009). The fitness value of each chromosome is an index of the problem's design improvement suitability (Ching-Hsue Cheng et al., 2010). In our case, user has two choices. If user choose for Brown' simulation, it will refer to Brown's One Parameter Linear Method formula and later link to fitness function (MAE). If user choose for Holt' simulation, it will refer to Holt's Two Parameter Method formula and also link to fitness function (MAE).
Step 4: Elitism Strategy. Elitism strategy is applied in this research in order to have greater probability for good chromosomes to propagate excellent next generation. This mechanism selects P% individuals which have the best fitness values to be the offspring of the next generation while the remaining individuals execute the genetic operations (i.e., selection, crossover and mutation) (Ching-Hsue Cheng et al., 2010). In our case, 10% of parent chromosomes (2 elite chromosomes) and 90% offspring chromosomes (18 chromosomes) are used in this research.
Step 5: Selection. Selection is a process in which suitable chromosomes from the parents' populations for the next generation are chosen. The selection mechanism plays an important role for searching towards better solutions. In this step, the selection of this model is Roulette Wheel Selection.
The value of the fitness function represents the area proportion of each string on the roulette wheel which also represents the probability of being selected. Therefore, a chromosome with larger fitness function value means it has greater probability of being selected. The selection mechanism is applied twice in order to select a pair of individual to undergo crossover.
Step 6: Crossover. For each pair of parents selected in the previous step, the system randomly generates a real number (between zero and one) comparing it with crossover rate (CR) (between zero and one) (which define by user) to decide whether the two selected chromosomes perform the crossover operations. If the randomly generated real number is smaller than the value of CR, then the system exchanges some genes of the two selected chromosomes to evolve better chromosomes having higher fitness values (Shyi-Ming Chen, 2006). In simple words, each pair undergoes the crossover operation with a probability of Pc, producing two children by crossover (J. Alcaraz and C. Maroto, 2005).
The crossover operates by swapping corresponding segments of a string representation of the parents and extends the search for a new solution (Ching-Hsue Cheng et al., 2010). Two offspring are formed via partial exchange of bits between two selected parents (M.H. Afshar and M.A. Marino,2009). In this study, we are using the classical one point cross-over.
Step 7: Mutation. The system use a predefined parameter called the mutation rate (MR) (between zero and one) (user decide) to decide the mutation probability of the selected chromosome. The system randomly generates a real number (between zero and one) and compares it with the value of MR to decide whether the selected chromosome performs the mutation operation. If the randomly generated number is smaller than or equal to the value of MR, then the mutation operation mutates a selected gene of a chromosome (Shyi-Ming Chen et al., 2006). Thus, 0 may be changed to a 1 or vice versa (M.I. Friswell et al., 1998). By modifying one or more of the gene values of an existing individual, mutation creates new individuals, generally resulting in increased variability of the population. It insures that the probability of reaching any point in the search space is never zero.
Step 8: Replacement. The new population generated by the previous steps updates the old population (Pei-Chann Chang et al., 2005). This procedure is repeated to create successive generations (M.H. Afshar and M.A. Marino, 2009).
Step 9: Stopping criteria. The proposed algorithm is terminated if either one of the following conditions is satisfied (Ching-Hsue Cheng et al., 2010):
1. The maximum number of generations is achieved, t=maximal number of generation (q) or
2. The same solution has not been changed for the 20 generation (for Brown's method) or 50 generation (for Holt's method).
The chromosome with the highest fitness is adopted as the optimal solution of the problem. Else set t=t+1 and return to Step 2 (Harun Kemal Ozturk et al., 2005).
In order to make sure the parameters we generate along the process are satisfying the parameter constraint (between 0 and 1). We use the inversion operator to repair the chromosome that violate the constraint and further introduce the randomness in solution pool. The operator is use in accordingly to step 2 (Decode Chromosome) and step 7 (mutation).
The Kuala Lumpur Composite Index (KLCI) daily closing price from 02/01/2009 to 31/12/2009 with number observation n = 250 was employed. The number of observations is break into two set, the period ranging from 02/01/2009 to 24/12/2009 with number observation n = 246 was used in model development and 4 remainder is kept for the purpose of out-of-sample forecasting accuracy evaluation. This data set obtained from yahoo finance website, www.finance.yahoo.com.
The second set of data was USD/Ringgit exchange rate selling price in Forex Exchange from 1/4/2008 to 29/5/2009 with number observation n = 288 (Gan Long Fatt and Zuhaimy, 2009 ). Again, period ranging from 1/4/2008 to 25/5/2009 with number observation n = 284 was used in model development and remainder was kept as out-of-sample set.
RESULTS AND DICUSSION
Here, we discuss simulation on KLCI data only. The simulation on DES system is done using the following characteristic:
Population size (n): 20
(predefined in the system cannot edit by user)
Maximum Generation number (t): 250 (predefined in the system cannot edit by user)
Probability of crossover () : 0.5
Probability of mutation () :0.1
Type of Crossover: one-point crossover
We are using MAE as objection function (or fitness function) in order to find the optimum solution. In this work, the GA search is assumed to have converged if the best solution of the generations remains constant for a specified number of generations (exceed 20 generations for Brown's method and exceed 50 generations for Holt's method) (predefined in the system cannot edit by user) ( M.H. Afshar and M.A. Marino). We are running the simulation of Brown's One Parameter Linear Method for few times by clicked "Brown" button. The different solutions obtained from DES System (Brown's One Parameter Linear Method) were recorded in Table 1.
We found that alpha=0.53 is appeared most of the time which satisfied the convergence characteristic of Genetic Algorithm. Since our main objective function is to minimize the MAE, hence alpha=0.53 is chosen as our desired optimum solution. The same processes are repeated for Holt's Two Parameter Method by clicked "Holt" button. The solutions were recorded in Table 2.
The Holt's method simulation's results are not that consistent as Brown's method simulation. This may due to the solution representation (consist of alpha and gamma) has contain much more possible combination solutions. Alpha=0.98 and Gamma=0.23 with the minimum among the objective function (MAE) was chosen. The best results obtained by both methods were recorded in Table 3.
We found that Brown's method performed well in model fitting (except in MAE) but Holt's method was performed excellent in predicting the future (out-of-sample).
Figure 1 shows KLCI data's best forecasting result obtained from DES system when "Brown" button is clicked. Figure 2 KLCI data's best forecasting result obtained from DES System when "Holt" button is clicked. The result of alpha value, gamma value, MAE, MSE, MSE and MAPE were displayed in static boxes. There is a table consist value of actual and forecast data (fitted model only) and the value of forecast ahead was display on the screen directly. A graph of actual and forecast value (fitted model+forecast ahead) was plotted.
Here, we further investigate the accuracy of solutions that obtained from DES system and compare with some solutions by using different parameters which are determine intuitively. It is impossible to list down all the solution that using all the parameter values that lies in the range 0 to 1. This is because we are dealing with an interval parameter of 0.01 which have 99 possible values to consider in Brown's method () and 9801 possible combinations of values to consider in Holt's method (,). Table 4 is the results of KLCI data by using different parameters value in Brown's One Parameter Linear Method (fitted model). Table 5 is the results of KLCI data by using different parameters value in Holt's Two Parameter Method (fitted model). Refer to Table 4 and 5, the DES system results have the most minimum value in MAE, MSE, RMSE and MAPE.
Table 1: Different solutions of KLCI data obtained from DES System (Brown's One Parameter Linear Method)
Table 2: Different solutions of KLCI data obtained from DES System
Table 3: KLCI data's best solution obtained from DES System (Brown's One Parameter Linear Method and Holt's Two Parameter Method)
Figure 1: KLCI data's best forecasting result obtained from DES system (Brown's method
Figure 2: KLCI data's best forecasting result obtained from DES System (Holt's method)
Table 4: Results of KLCI data (case 1) by using different parameters values in Brown's One Parameter Linear Method (fitted model)
Brown's One Parameter Linear Method
results for fitted model with different parameter value
result obtained by DES system(GA)
Table 5: Results of KLCI data (case 1) by using different parameters values in Holt's Two Parameter Method (fitted model)
Holt's Two Parameter Method
results for fitted model with different parameter value
As a conclusion, DES system (integration of GA in DES) is able to identify the parameter values which minimize statistical error values. It is also time and cost saving if we compare with the methods that determine the parameter values by exhaustive search or
intuitively. The advantages of DES system is it do not require any specified skill, any procedure and easy to use. It is easy to update the fitted model when acquired new data. The model can be rebuilt within few second. However, we found that there is a limitation in DES where the model is unable to track the turning point in market direction.