-The increasing influence of optimization methods on modern technologies means that not only new algorithms are designed but old ones are improved. One of the classic optimization methods is the genetic algorithm inspired by the phenomenon of biological evolution. One of the modifications is Baldwin's approach as genetic assimilation. It is a process that creates permanent structures as an effect on the frequent use of specific organs. This paper presents four different algorithms that have been used as a Baldwin effect in the classical genetic algorithm. All techniques have been tested using 9 test functions and the obtained results are discussed.
I. INTRODUCTION
Describing things and process in nature very often comes to the mathematical description using equation or function. Especially when there are some parameters that make it impossible to determine what proportions should be maintained depending on other external factors. Moreover, even mathematical tools are not able to simply and quickly determine what is the solution for a more complex function or their dependencies.
One of the best existing methods of finding a global extreme for multi-variable functions are algorithms inspired by phenomena occurring in nature or behavior of a specific group of animals. It is visible on the developed research around the world and emerging publications. One of the most dynamically developing branches of optimization are heuristic algorithms, ie those that do not guarantee the correct solution in a finite time. An example of such a technique is the dragonfly algorithm [8] which is inspired by the static and dynamic behavior of dragonfly’s swarm. Again in [12], the authors described the mathematical model of behavior of polar bears which are forced to move on ice floe and hunt for seals in arctic conditions.
Not only the algorithms are developed but the applications that have complicated functions. One of such example is analysis of samples taken from a fluorescence microscope. In [19], optimization algorithms were used in the detection of bacterial shapes at various stages of life. Again in [17], this idea was used for charge and discharge electronic vehicles using building energy management system. Another application area is biometric security. In [10], voice samples were interpreted as two-dimensional images where important features to identify the owner of the voice were sought. Other application is Copyright held by the author(s). chat-bots were heuristic can be used as an engine [15]. For these type of apps, different notation are developed [3]. In [13], heuristic were used to extract brain tumor from MR images. Similarly in the area of smart technology optimization has a significant role. In [2], it was used in wireless sensor network, and in [16], modified technique has found application in optimization of coverage in visible light communication in smart homes systems.
In this paper, the idea of improving genetic algorithm by the introduction of Baldwin effect is presented.
II. OPTIMIZATION PROBLEM FORMULATION
It is quite often that some problems can be described by some function. And then, the smallest or largest value for a given function is wanted. Such a task is called an optimization problem. Let’s assume that x is a point in n–dimension, and function will be described in the following way f (x) : Rn ! R, then minimization problem can be defined as
subject to f (x) g(x) Li
0 xi
Ri
i = 0; 1; : : : ; n
1;
(
III. GENETIC APPROACH TO OPTIMIZATION
Through many ages, people observe the changes in natural processes. Then, many times, they tried to use this knowledge in science by creating computer methods based on those notices. In 70s of 20th century, the man called John Holland created the Genetic Algorithm, which was also the first evolutionary algorithm [4]. The inspiration of creating this technique was desire of making computer be able to solve problems likewise it goes in the natural evolution process. The initial idea of Genetic Algorithm was to create a population which contain some individuals and each of them had a unique binary genetic code assigned to it. Set codes correspond to chromosomes exist in organisms and that makes the elements of code equivalent to the genes. Subsequently, after many researches, there were implemented some improvements occurred during the noticed biological process of evolution. The observed operations start from the mechanism, which transforms the binary codes similarly as crossing–over, according to the Function 0 v n 1 f1(x) = 20 @ 0:2utu n1 X xi2A
i=1 f2(x) = Xn xi2 Yn cos pxi
i=1 4000n i=1 i f3(x) = 10n + X xi2 i=1
10 cos(2 xi) n X xi sin pjxij i=1 f4(x) = 418:9829n
n i f5(x) = X X x2
j i=1 j=1 n f6(x) = X ixi2 i=1 n f7(x) = X xi2 + i=1 n 1 f8(x) = X 100 xi+1
i=1n f9(x) = 12 X x4
i i=1 n X 0:5ixi i=1 !2 + n X 0:5ixi i=1
!4 x2 2 + (xi 1)2 i 16xi2 + 5xi process of inheritance. Then they based on mutation and selection. Holland discover that by adding the logic operators and using selection, the average value of population fitness can increase. The most important part of that is using encoding and genetic operators to solve problems. Nowadays, in the age of new technology, it is obvious to use for that the potential of advanced programming with high–performance computers. In this paper, the version of the genetic algorithm operating on numbers in the decimal notation was selected.
1) Genetic Algorithm (GA): The Genetic Algoritms is made of few steps. The first one is initialization in which the initial population is created. That step is about generating the size of population, the encoding of chromosomes and the formula for fitness function f ( ) with the appropriate restrictions. The main assumption here is about setting the size of population, because it is the parameter that affects on accuracy of the algorithm. If the population is too small then the algorithm finishes calculation without reaching the correct solution. On the other hand, when the number of individuals is too large, then it can aggravate the computer and make the calculations last very long. Other elements of initial population are set randomly.
Afterwards, there is made a selection of individuals. Some of them are passed to the next stage of calculations. That process is called reproduction. It can be done in many ways. Description one of them requires the use of probability that one individual xi is chosen to new generation. The probability of setting this individual in next population depends on the value of fitness function at exact point f (xi). The higher value of fitness function results in a higher probability at this point. The clue of this step is to create a random value pr for further description of new population selected from the existing generation P t. It can be described as
After few sampling of this variable, it is possible to introduce the distribution function of reproduction probability as ( pr(xit) = f(xit) xt i xi 2 P t t
: Pr(xit) =
i X pr(xit): j=1
In the next step there is a selection of individuals – if it is reproduced or not. The factor that determines this choice is a random variable from h0; 1i. The individual xi is reproduced as long as the following formula
Pr(xit 1) <
Pr(xit) is fulfilled. Genetic operators, like mutation and crossover, are responsible for creating a diverse population but they also take control of reproducing.
The first genetic operator mentioned above, the mutation, is about replacing the chromosomes. In this process a random variable belongs to h0; 1i is added to the chromosome xit+1mutated = xit + :
Then let the be the vector of random values and length equivalent to the number of individuals in generation. If for pm, which is the probability of mutation, is followed the ineqality
i < pm; then the chromosome is mutated.
The second of genetic operators is crossover. This process
is about exchanging genetic material. Two chromosomes are
(
Then whole new population has to be evaluated whether they fit to the conditions in environment. This process, called succession, is replacing the old generation with the new one.
Replacing all individuals in population is only one of the ways to carry out succession. The other way is to change just a part of old generation. Here, there becomes a need to choose a method of selection chromosomes. Anyway, a parameter g from h0; 100i can describe an amount of individuals from old generation that remained. Decision, which of individuals should be replaced, can be taken on many different levels: the ones that are similar to individuals in next population, the ones that are the least adapted, the ones that are selected by succession the ones that are chosen in random way.
The method which let the best chromosomes survive is succession. In that way, it doesn’t matter in which population some individuals appear – if they are ones of the best, then they stay to the end of algorithm. In every iteration individuals are ordered by value of fitness function f (xi). Then, some of the worst are replaced with new ones. By using some kind of "back-up" generation, the best individuals are stored through all the algorithm. It ensures that better ones will not be replaced by worse ones.
Algorithm 1 Genetic algorithm
1: Start,
2: Define all parameters - T , f ( ), n,
3: Generate the initial population,
4: t := 1;
5: while t T do
6: Select the best individuals for reproduction,
7: Apply crossover operation using Eq. (
Analysis of the direction of gradient decrease is one of the classic optimization methods [14]. Assume that x = (x0; : : : ; xn 1) is a start point. To find the direction, we need to calculate the negative gradient for each spatial coordinates according to
rfxi =
Using above calculation of calculated as
xit = xit + ( rfxit ); (
Iterated local search is one of the classic optimization technique called hill climbing [7]. The name is adequate to the operation of the algorithm, which for a given point x performs perturbation (i.e. random displacement) as
After observing the evolution process, James Mark Baldwin
claimed that there exists an ability to acquire new behaviours x0 = x ; (
Variable neighborhood search is another hill climbing method [9]. The algorithm assumes the creation of a set, then the use of another local search technique for each representative in this set and comparison with a given point.
If the new point proves to be better (using fitness function), the original one is overwritten by the neighbor.
Algorithm 4 Variable neighborhood search annealing process in thermodynamics, and more precisely how metals cool and anneal. It assumes that the temperature is high at beginning of the process what gives high probability of change. As the temperature decreases, the probability of change is smaller. In practice, this means that the probability of adopting a worse solution is higher at high temperature and smaller at lower.
The algorithm uses a modified thermodynamic equation what can be defined as
P (E) e T ;
(
(
< e T ;
Tk+1 = r Tk;
(
Algorithm 5 Simulated annealing
All techniques were implemented and tested (Baldwin effect for 20 steps, GA – 10000 iterations and 100 individuals) using all nine test functions. Each algorithm was made 100 times to get 100 solutions. The obtained points were used to calculate the average value of the fitness function as follows 100
100 1 X f (xi);
i=1 and then the error for each function was calculated as f (xideal) 100 i=1 100 1 X f (xi) :
All obtained results are presented in Tab. II and III. In almost every modification interpreted as Baldwin effect, the results were corrected what increased accuracy. Unfortunately, the improvement took place at the expense of increasing the time by adding additional calculations made at the local search. The best solution turned out to be the solution gained from genetic algorithm with simulated annealing in all cases.
Iterated and variable neighborhood returned improved results of the original algorithm, but in comparison to other used methods, they are the least favorable due to the number of calculations. The reason is a structure that uses an additional algorithm which doubles the number of operations.
Baldwin effect can be interpreted as correction for obtained results in each iteration. The obtained results showed the superiority of simulated annealing over other tested methods. In the case of iterated or neighborhood technique, the results obtained were better than the original version, but the execution time has increased quite significantly. It is worth noting that the Baldwin effect was performed only for 20 iteration what is not a large number.
Any modification that aims to increase the precision of
the algorithm for the selected point in a given place (only
local space-searching was considered in this paper) is worth
implementing in the case of creating hybrid methods and when
the accuracy is significant.
(