Abstract
A dynamic version of Environmental Adaption Method (EAM) is proposed in this paper. Environmental Adaption Method for Dynamic Environment (EAMD) is an improvement over EAM, which works in dynamic environment with real valued parameters. Unlike EAM the theory of this algorithm is based on adaption of species in dynamic environment which gradually becomes more verse and deadly for their denizens. The species which are able to adapt in the changing environment, improves their fitness value by enhancing their phenotypic structure in the upcoming generations. Sudden and gradual dynamic changes in the environment assist species to converge towards the optimal fitness. Unlike EAM, EAMD is suitable for both unimodal and multimodal problems without the need of an alteration operator as there is enough diversity since the adaption is randomized, i.e. each possible solution can adapt anywhere within the search space. EAMD is compared with various algorithms tested on 24 benchmark functions against the Black Box Optimization Benchmarking (BBOB) test-bed at different dimensions with very promising results and EAMD shows its superiority over other state-of-the-art algorithms.
Keywords
Introduction
The main goal of any randomized optimization algorithm is to find the optimal solution with minimum effort i.e. minimum number function evaluations. This can be made possible through optimizing the convergence rate, stopping the solution to get stuck in the local optima and minimizing the computation time to find the optimal solution.
The major problem to achieve these goals is that in most of the cases user does not know the nature of the optimization problem (objective function) and without knowing the nature the desired optimality cannot be achieved. So, an automatic technique is required that can help to understand the problem statement and also guide the user to map the problem with an appropriate solution. In nature many such techniques are available that may help the user to understand the problem and also guide the search towards optimal solution.
For example Genetic Algorithm, Particle Swarm Optimization, Aunt Colony Bee etc. are based on the natural phenomena. They provide guidance to the researchers to get the optimal solution when the search direction is not clear.
An Environmental Adaption Method (EAM) is a nature inspired algorithm established earlier with binary valued encoding and static environment for obtaining optimal solutions [1, 2]. Even though good convergence rate, ability to capture multiple optimal solutions and auto tuning of random parameters, still there is a need to propose an improved version of EAM that can capture optimal solution as early as possible with improved convergence rate and more suitable for unimodal and multimodal problems with reduced computation time. It can also be able to provide a technique through which stagnation and stickiness of solution in local optima can be avoided very efficiently. All finite regions must be exploited and the probability of retrieving the optimal solution must be high.
An environment plays a vital role in the growth of individuals (species) and they have to face different problems during their journey of life. There are different factors like natural disasters, different types of diseases, lack of food, lack of fresh water and many more things are responsible for affecting the leaving environment of individuals directly or indirectly. These factors may impose negative changes that may affect the environment very badly. The changes in environment drive the individuals to improve their fitness gradually and help them to survive in the new environmental conditions. Thus, the individuals give response to the environmental changes in two ways either they adapt the potential changes or react against the changes. So, those who accept these changes, they survive and this is the key to survival otherwise they have to struggle for their existence. All individuals flourish to survive may adapt the harsh environment and the adapted traits can be inherited by the next generation. In the proposed algorithm, this idea of adaption in dynamic environment is adopted as an optimization technique. The term adaption is influenced by the dynamic changes in the environment. Like EAM, the proposed algorithm EAMD has established the idea of adaptive learning [3] which is a natural phenomenon that helps the individuals to adapt themselves in a new environment. The term adaptive plasticity assists unfit individuals to acquire higher fitness and this process of learning continues until population achieves the optimal fitness.
The Environmental Adaption Method for Dynamic Environment (EAMD) is a new version of EAM. The working of EAMD is different form EAM, because EAMD works in dynamic environment with real valued parameters. The adaption technique is different from EAM because in EAM, a new variable called environmental fitness is taken which is the average of the fitness of individuals for current generation. This average fitness is taken as the basis of the survival of individuals in the current generation and also forms a static environment. While EAMD has used the random adaption method guided by a global dynamic environment. EAMD has used a new term named “Adaption window (Environmental Window)”, which is used in place of environmental fitness. The Environmental Window directly managed by the environment to support life of individuals for surviving in the changing environment. Unlike EAM there is no need of alteration operator to maintain diversity because it is automatically maintained by the population size and Environmental Window. The selection operator is applied on intermediate population containing both the initial population and the adapted population. The best solutions are selected as the new population from this intermediate pool of solutions.
The performance of the proposed algorithm is checked over current state-of-the-art algorithms which are available on the COmparing Continuous Optimisers (COCO) framework [4]. Different dimensions have been taken to examine the performance of EAMD. The rest of the paper is organised into six sections; Section 2, discusses about the background details. Section 3, has given the summary of the related work. The proposed work has been given in Section 4, including biological base of the work, proposed method and related algorithms. Experimental settings and simulation strategies are discussed in Section 5. Section 6, shows the results obtained after simulation. The paper has concluded in Section 7. Section 8, gives information about the system configuration and time taken by algorithm to run a single instance in different dimensions.
Background details
Environmental Adaption Method (EAM)
EAM is a population based algorithm and it is adopted the process of adaptive learning. This learning involve three operators i.e. adaption, alteration and selection. An adaption operator processes on randomly generated initial population and helps every individual to update its phenotypic structure taking its current fitness and environmental fitness into account. During the changes in phenotypic structure some modification may be possible due to environmental noise and it is termed as Alteration. Alteration is the next operator after adaption and it is applied for maintaining the diversity in the solution space. After adaption and alteration, intermediate population is generated. Selection is the third operator used to select the best solutions from the intermediate generation with best fitness value. Unfit solutions are discarded form the current generation. These steps are repeated until either the maximum number of iterations or the desired solution has encountered. Thus the learning process helps to improve the fitness of individuals and hence the chances of survival in the newly changed environment.
EAM uses binary encoding and in the first generation population is created by the fixed number of random initial solutions. The next generation is created byapplying adaption, alteration and selection on thepopulation of the current generation. In adaption, an individual Pin adapts itself against the environment and generates its modified structure P′in = (α*(Decoded value in decimal of binary coding of P′in) |F (Pin)/Favg| + β) % 2l. Where F(Pin) is the fitness value of Pin, α and β parameters are the random numbers which are used in such a manner that guide the search towards finding the optimal solution, l represents the total number of bits that is required to encode an individual and Favg represents the average fitness of the current population and it is used to represent the current environmental fitness. Next, the alteration operator is applied after adaption and this alteration may result due to environmental noise. Alteration operator is used to exploit good regions. Finally selection operator is applied to choose best solutions with better environmental fitness while it keeps the population size equal to the initial population.
In EAM, an environmental fitness has been taken as a key term for creating an environment which is actually the average fitness of all solutions available in the current generation and it is represented by Favg. Here Favg is used to define the fitness level for survival and each solution in the solution pool has to refine its fitness, which must be greater than or equal to Favg otherwise rest of the solutions are discarded form the environment. The value of Favg is changed for every generation. For example if there are 10 solutions available in the solution space then the Favg is the average fitness value of 10 solutions and it represents the current environmental fitness. The Favg has been taken as criteria to check the strength of the individuals in a specific environment. The individuals whose fitness is higher than the environmental fitness will survive otherwise they will struggle for survival in the current environmental conditions. So the individuals always motivated by the environment to change their structure according to the gradual changes in the environment and achieve minimum fitness necessary for their survival in the changing environment.
According to this theory one thing is very clear that the environment is static and it is based on average fitness of the solutions (Favg). The Favg is fixed for each generation individually but it is different from one generation to another generation and changes itself according to the changes in the fitness of the individuals as the generation increases.
Related work
Various state-of-the-art algorithms have been taken from the COCO framework to do the performance evaluation of the proposed algorithm i.e. EAMD. The brief introduction of these algorithms is as follows:
Neal Holtschulte et al. have evaluated the performance of two cellular genetic algorithms (CGAs), a single-population genetic algorithm (GA), and a hill-climber (hill) on the BBOB test-bed [5]. They applied a change in mutation for these algorithms. They have used a per-gene mutation rate of 1/dimensionality in such a way that the mutation will occur per individual per generation on average. For GA and CGAs, two point crossover is used with 90% crossover rate.
Two CGAs i.e. ring CGA (ring) and grid CGA (canonical CGA [6]) is benchmarked with three different population sizes: 16, 49 and 100, GA (ga100) is benchmarked with a population size 100 and hill-climber (hill) is also benchmarked on 24 benchmark functions. There is no restart is used for any algorithm and 50,000 * D is used as a number of function evaluations, were D represent the number of dimensions. It is found that ring CGAs performs better than hill, grid CGAs and ga100 on the benchmarks taken in this paper.
Tran et al. has proposed an idea of multiobjectivization which is used to reformulate a single objective problem as a multi-objective one [5]. They have considered the NSGA-II variant with distance to the closet neighbour (DCN) as second objective (U-DCN) and U-zero is the second objective function with zero. Secondly, they have checked how much mutation is required to affect the search performance by comparing the variants where the original polynomial mutation [6] operator of NSGA-II is replaced with uniform mutation represented as P-DCN and P-zero.
Auger et al. have evaluated the performance of Pure-Random-Search algorithm (Random) on noise free BBOB-2009 test-bed [7]. This algorithm was proposed by Brooks in 1958. This is a very simple and popular algorithm and independently does sampling of each search point in the search space. It also keeps best solutions which are found during the sampling. The search boundary [−5, 5] has been taken for the experimental analysis, where D indicates the search dimension. The maximum function evaluation has been taken for this work is 105 * D. D is used to denote the dimension of the search space.
Sawyerr et al. [8] have checked the performance of projection based real coded genetic algorithm (PRCGA) on the noise free BBOB 2013 test-bed. PRCGA is an enhanced version of RCGA-P and it specially designed for RCGA which is based on the concept of orthogonal projection of a vector x on a vector y. Two mechanisms i.e. multiple independent startmechanism and a stagnation alleviation mechanism have been incorporated with PRCGA. Five operators are incorporated with PRCGA namely; tournament selection, blend-α crossover, non-function mutation, projection and a stagnation alleviation mechanism.
Sawyerr et al. [9, 10] have done a comparative study on real-coded genetic algorithms (RCGAs) for unconstrained global optimization with global and local exploratory search capabilities. Modified crossover with the search capabilities and a new global exploratory method are included in RCGA. These modifications help to improve the efficiency and robustness of RCGAs with the help of local and global exploration of the search region.
Cantu-Paz et al. [11] have proposed a parallel genetic algorithm with distributed panmictic populations in which they have examined the performance of an algorithm on physically distributed population which act like a single panmictic population. They proposed the idea of how to minimize the execution time with the use of optimal number of processors.
Proposed work
Biological motivation
When a population changes its living place from one environment to another environment then they have to face some changes in their phenotypic structure due to the new environmental pressure. The term phenotype is generally used as a synonym for trait in common use but actually the phenotype is used to indicate the state or value of a trait. Trait is used as an attribute or characteristic of specie, which is a final output of several biochemical and molecular processes. For example, a trait eye colour has different phenotypes such as blue, brown and hazel which are the observable trait. Actually the part we see is called phenotype.
The changes in environment, cause of some variation in the plastic traits (behaviour) and that happened especially due to the variation in phenotypic or genotypic structure. These variations have two aspects whether it might be favourable or unfavourable. If it is favourable then it helps species to survive in the new environmental conditions otherwise the unfavourable variations cause of putting down the chances of survival. Finally the favourably changed structure will be promoted by natural selection in the species.
Phenotype contains information related to the behaviour, life history of the species. Changes in the phenotypic structure induce the phenotypic information into the genetic structure of species and it is reflected in the further generations.
Proposed method
In the proposed approach Environmental Adaption Method for Dynamic Environment (EAMD), an environment contributes a vital role for species to refine their structure and also helps them to learn from the gradually changing environment. Since this concept automatically facilitate to produce optimal structure and it is used to design the proposed algorithm. The conference version of EAMD has published in [14] and compared with five algorithms for dimension size 2 and 10. The overview of EAMD is shown in Fig. 1.
EAMD is a population based, nature inspired and somehow related to evolutionary algorithm [15] that features a random adaption method headed by a global environmental changes with search space of real valued parameters unlike the fixed environment and binary valued parameter used in EAM. A new term, the “Environmental Window (EW)” has been used that shows how the environment is very significant to support life. The dynamic environment is created with the help of EW and for that the window size is decreased gradually over a few generations. The size of the EW represents the nature of the environment whether it is gentle or severe to survive. So, a large EW makes the environment very comfortable for its inhabitants to survive easily while smaller size of EW causes the environment severe for its inhabitants. Individuals may adapt the environment and gain better fitness values over time otherwise those who are not able to adapt the environment are decimated from the search space. Figure 1 shows the implementation of Environmental Window for getting the solution (s) which has (ve) better fitness.
Each parameter of an individual adapts with respect to its original position and the EW is relative to the position of each parameter. The adaption capability is determined by the size of EW. Each parameter of an individual may only adapt within the range of its environmental window. Suppose the minimum and the maximum possible value of each parameter is low and up, if the original position of a parameter of an individual is X and the environmental window size is W, then each parameter may adapt anywhere between its X–W to X+W. If X–W or X+W lies outside the boundaries of the search space (upper and lower bound of the search space) then the part which may adapt outside the boundary is clamped and confined to the search space ensuring that position of an individual does not venture outside the search space.
Let us consider an example test case in the BBOB test-bed to show the working of adaption operator.
The BBOB test-bed has optimal solutions lying between [−5, 5]D, hence the value of each parameter must be in between −5 to 5, hence low =−5 and up = 5. Let’s assume an individual with 2-D is at position X = 1 and Y = 4, with the current window size being W = 4. The X parameter of this individual may adapt anywhere between X–W/2 =−1 and X+W/2 = 3 and Y parameter may adapt between Y–W/2 = 2 to Y+W/2 = 6. Now, the upper boundary of possible adaption of the Y parameter lies outside the COCO domain range of [−5, 5]D, hence the upper boundary is clamped such that Y now adapts between Y–W = 1 and Y+W = 5.
Initially, the adaption capability of the individuals is large when the window size is large. The gradual decrease in window size causes the individuals who acquire better fitness after adaption is selected. The algorithm 1 is used for showing the process of adaption operator. The size of the environmental window decreases with the successive generations (iterations) and it confines adaption and guide the individuals towards the optimal solutions.
The role of the selection operator is very clear it makes sure that those individuals are selected which have better ability to adapt than others in the tough environmental conditions. The algorithm does not require an alteration operator as it is used in EAM maintain diversity, because in the proposed algorithm the diversity is dependent on the size of the population.
Since each individual can randomly adapt anywhere in the search space and it helps to explore the whole search space domain to maintain diversity. The size of the search space decides the selection of window size and amount to be decreased after specific number of iterations.
The shrinking of environmental window is decided by the window counter value. A window counter value determines after how many generations the environment will degrade. Here the window counter is dependent on the dimension and the calculation of counter value equation number 1.
When EAMD is used for any problems, the upper and lower limit of the search space decides the cost of maximum and minimum handled by each parameter. After completing every iteration, all parameters of a possible solution do mandatory adaption and as a result probability of acquiring adaption towards the optimal fitness by all available solutions in the same time span gradually decreases as the dimension size increases. This completely affects the convergence rate. So, to solve this problem, parameters of a solution are divided in to the groups of same size and adapt themselves one by one with selection after every adaption. This process improves the convergence rate at higher dimensions but little bit increases the number of fitness evaluation.
The adaption technique used in EAMD is implemented by the dynamic window. Also unlike EAM there is no need of alteration operator to maintain diversity because it is already maintained by the population size and adaption operator. After applying adaption an intermediate population is created. Intermediate population and the initial population create a solution pool. Selection operator is applied on this pool and best solutions are selected as the new population. The working model of EAMD is detailed in Fig. 1. The pseudo-code for the algorithm is shown in Algorithms 1 and 2, mentioned below.
Adaption operator: Notations
Maximum value for each parameter.
Minimum value for each parameter.
Current Environmental window size.
Current population.
Adapted population.
Algorithm 1: Adaption
Adaption (POP, W i)
APOP = rand ((X-Wi/2), Max)
APOP = rand ((X + Wi/2), Min)
APOP = rand ((X-Wi/2)(X+Wi/2))
EAMD: Notations
Maximum value for each parameter.
Minimum value for each parameter.
Environmental window size.
Window size counter.
Maximum number of generations.
Initial population.
Adapted population.
Intermediate population.
Algorithm 2: EAMD
initialize the window size W0 = MAX-MIN
initialize the population POP0
// fitness checking on 24 benchmark functions
evaluate the fitness:= f(x)
// call the Adaption function
APOPi = Adaption (POPi)
// generate the intermediate population
IPOPi = POPi U APOPi
// select the best individuals
POPi+1 = Selection (POPi, IPOPi)
// shrink the window size Wi using window
// counter limit
WCL = round (Dimension/1.5) + 10
set Wc = 0
increase window counter (Wc)
increase i
Selection Operator: Notations
Temp_POP: Temporary population.
Sort_POP: Sorted population.
Selection (POP, APOP)
Temp_POP = merge (POP, APOP)
Sort_POP = sort (temp_pop, ascending)
// selection of top n individuals from
POP = Sort_POP
Experimental settings and simulation strategies for benchmark testing
Settings
In the BBOB noiseless test-bed, [−5, 5] has been taken as a search domain for all 24 benchmark functions. EAMD has been tested over different dimensions like 2D, 3D, 5D, 10D, 20D and 40D, given on COCO framework [5, 16] without any restart mechanism. Here the lower bound and upper bound in the search domain is −5 and +5 respectively. Initially the window size is taken as Max-Min (5–(−5)) = 10 and the counter value decides the shrinking of window size i.e. after how many generations the window size will degrade from its previous size. The experiment is carried out with a population size 30*dim and the max function evaluations is calculated by the equation number 2. Here the dim indicates the dimension size. According to the equation number 2, the function evaluation is calculated as 40000 for 2D, 95000 for 3D, 187000 for 5D, 500000 for 10D, 1700000 for 20D and 6500000 for 40D. The total function evaluation for each dimension has been calculated by the equation number 3.
The data set for other algorithms are taken form the COCO framework [5], which is used to compare the performance with EAMD.
Twenty four noise free real-parameter single objective benchmark functions [17–19] are used to evaluate the performance of EAMD in terms of optimum solutions after a predefined number of generations and the valid convergence rate to the optimum solution. The benchmarks taken for this paper is widely used in [5–13]. These benchmark functions for the experiment are scalable with dimension and fifteen instances are generated for each benchmark function. The search domain of all functions are defined everywhere in RD and have their global optimum in [–5, 5]D. Most functions have their global optimum in [–4, 4]D which can also be a reasonable setting for initial solutions.
Simulation strategies
Simulation is carried out to check the quality of optimum solution and convergence rate of the newly introduced method in comparison with eleven state-of-the-art algorithms. The term Expected Running Time (ERT), applied in the figures and tables, are dependent on a given target function value (ft), and it is denoted by ft = fopt + Δ f, where Δ f = 10 −8, it is computed over all relevant trials as the number of function evaluations executed during each trial. #succ denotes the number of trials which is important to achieve to reach the final target ft.
In the experiment the rank-sum test is used to test the statistical significance for a given target Δ ft and this is used for each trial, either the number of required function evaluation to achieve the Δ ft (inverted and multiplied by −1), or, if the target was not reached, the best Δ f value achieved, measured only up to the smallest number of overall function evaluations for any unsuccessful trial under consideration if available.
Used notations
Δ f precision to reach, i.e., a difference to the optimal function value f opt and f opt is the optimal function value defined for each benchmark function individually. f target is the target function value to reach the optimal value. The smallest specified final target value is f target = f opt + 10 −8, but also larger values of target are evaluated. Ntrials is used in this paper for each function and dimensionality individually for each single setup. D indicates the search space dimensionality used for all functions. D = 2, 3, 5, 10, 20 and 40, where dimensionality 40 is the optional.
Results from simulations
Results from the experiment on the noiseless test-bed according to [19] on the benchmark functions given in [17, 18]) are presented in Figs. 4–7 and in Table 1. In tables Expected Running Time (ERT) is given fortargets 101, −1, −2, −5, −7 divided by the best ERT obtained during BBOB-2009 (given in the ERT best row), respectively in 2-D, 3-D, 5-D, 10-D, 20-D and 40-D. Italics format is used to show the median number of conducted functions, if ERT (10 −7) =∞. #succ is based on the number of trials required to reach the final target fopt + 10 −8.
Entries with the ↓ symbol are statistically significantly better (according to the rank-sum test) compared to the best algorithm in BBOB-2009, with p = 0:05 or p = 10 −k where k > 1 is the number followingthe ↓ symbol, with Bonferroni correction of 24. The “best 2009” line in the figures corresponds to the best ERT observed during BBOB 2009 for each singletarget.
Conclusion
Twelve different stat-of-the-art algorithms have been used to check the performance of EAMD. The benchmark functions used for the experimental work are categorized into two parts i.e. unimodal and multimodal. In unimodal, functions have three groups such as separable fcts, moderate fcts and ill-conditioned fcts and each group contains five different functions. Multimodal functions are categorized into two groups i.e. multimodal fcts and weakly structured multimodal fcts. They have also five different functions in each group. The “all functions” category is used to check the overall performance of the proposed algorithm on all functions (1–24) together. Performance of EAMD is checked over six different dimensions like 2-D, 3-D, 5-D, 10-D, 20-D and 40-D. In every dimension EAMD has shown its superiority over other algorithms except best 2009. It shows its strength for both unimodal and multimodal functions.
CPU Timing
The experiments have been implemented on Intel Core i7 3.4 GHz with 64 bit machine under Windows 7 using MATLAB. The time calculated as per function evaluation was 1.1, 1.1, 1.2, 1.4, 1.6, 2.0 times 10 −5 seconds for dimensions 2, 3, 5, 10, 20 and 40.
Footnotes
Acknowledgments
The authors of this paper want to deliver special thanks to the BBOB organizers for providing such a tremendous benchmark setup, different datasets (noise-less and noise-free) of different well established algorithms and outstanding high quality post processing utilities.