-Increasing the use of heuristic algorithms in practical applications makes it necessary to perform numerous modifications in order to minimize possible disadvantages. Acceleration and increasing precision have become pressing problems of today's theory of applied computer science and optimization theory. In this work, the idea of a factor which minimizes the time to search the solution space by heuristic algorithms is presented. The proposed modification is described and tested for various test functions. The results are presented and discussed in terms of effectiveness of the proposed modifications.
Nowadays, IT solutions can be found everywhere from hospitals and factories to our own homes. Computer systems not only replace men at various levels of action, but also support our lives. In hospitals, the use of such solutions allow for faster diagnosis of disease or even prevent their uprising. In large factories, production of goods is done automatically, without the participation of the people due to a more accurate precision and high speed operation. Moreover, such systems have also found applications in our lives, eg.: washing machines or blood pressure monitors.
Each computer activity in their substrates has numerous algorithms, through which it operates in a certain way. Besides the classic algorithms, the application of computational intelligence is becoming increasingly popular because of the ability to obtain accurate results in a short time. Computational intelligence is represented primarily by three branches – fuzzy logic, neural networks and algorithms inspired by natural phenomena. The last group is classified also to optimization theory, which plays an important role in modern information technology. In [1], Dugun et al. showed that use of these algorithms allows for solving optimization problems of construction and in [2], an optimization technique used in order to solve the capacitated vehicle routing problems was shown. Additionally, in [3], the idea of using one of the optimization algorithms to minimize the drug protein integration energy was discussed. Again in [4], Mohandes discussed the problem of the quality of solar radiation received by the Earth’s surface and proposed the idea of modeling global solar radiation using neural networks and optimization algorithm.
Copyright c 2016 held by the authors.
Due to the numerous applications of optimization algorithms, in this paper we show that the introduction of local selection as a factor of decreasing the time of the algorithm is an effective modification. For testing purposes, some wellknown functions were taken and used for the purposes of verification of the proposed technique.
II. TEST FUNCTIONS FOR OPTIMIZATION PURPOSES Test functions for optimization problems are called multiobjective function, where the determination of a global minimum or maximum value is an unsolvable problem for well-known algorithms for finding extremes. Multiobjective functions are often called artificial landscapes due to the chart, which is often a complicated surface likened to the known landscapes found in nature.
The first function is called Egg holder’s function which includes many local extremes - it can cause getting stuck in one of them. The function is defined as fEggholder(x) = (x2 + 47) sin r x1 + (x2 + 47
2
x1 sin
pjx1
x2
47j ;
(
Easom function is the second function selected in the minimization problem. The function is described by the following equation fEasom(x) =
cos(x1) cos(x2)
exp((x1
)2 + (x2
)2) ;
(
The last function is a Himmelblau’s function representing a
flattened landscape and described as
fHimmelblau(x) = (x12 + x2
11)2 + (x1 + x22
7)2: (
Heuristic algorithms are one of the most important techniques for finding the global optimum for multiobjective function in large spaces solutions. Until today, several methods inspired by natural phenomena have been modeled. One of the drawbacks of this type of algorithms is no guarantee of a correct solution at a predetermined number of iterations. The analysis of the convergence of one of the methods, S.Arora and S.Singh shown in [5]. On the other hand, their use allows to obtain in a short time approximate solution using a computer with low computational efficiency. [0; 1] and r means the distance between xactual and xneighbor defined as the Euclidean metric
In 2012, Tang et al. [6] have created a model of behavior of wolves while looking for food and avoiding their enemies, which allowed for the creation of bio-inspired heuristic algorithm. The algorithm assumes that the wolf is represented as a point x in the solution space. Each wolf has a fixed visual area with a radius r – wolf can sense the company only in the visible range and only in this area, he can move (in one iteration). The position is evaluated in terms of fitness functions (x) what is understood as a quality of food in this area. There is a possibility that if the enemy of a wolf appears in his sight, he will escape to another position outside the range of his vision.
Wolves stick together, and so the greater the distance
between a pair of wolves, the place is less attractive. Wolf
moves to find prey, and therefore a better place (due to the
fitness function). The movement carried out by the following
equation
xnew = xactual + 0 exp( r2)(xneighbor
xactual) + ; (
Wolves hunt using a stalking process , what can be divided
into three stages of preying behavior – initiation, passive action
and escape. The first stage involves the movement in the
field of view of a wolf, which means finding a better place
according to
xneighbor;i)2:
xnew = xactual +
v ;
where v is the velocity of a wolf. Passive hunting means stay in
your current location, to the moment when the enemy appears.
The third stage occurs when the enemy is close to a wolf.
Escape is modeled by
xnew = xactual + s ;
(
One of the last algorithms inspired by the natural phenomenon algorithm is a model of water waves movement presented by Zheng et al. [7]. A point x = (x1; x2) in the solution space is called the wave. The algorithm simulates the movement of water waves, and so the following three
Start 2: Define the number of iterations T , number of wolves n, radius of the visual range r, step size s, velocity factor and coefficient appearance of the enemy palpha
Define fitness condition ( ) 4: Create an initial population of wolves in random t := 0 6: while t T do
if t > 0 then 8: Generate 80% of new waves
end if 10: for each wolf xactual in population do
Prey initiatively using (
end if 16: Generate new location
Generate random number 2 [0; 1] 18: if > palpha then
Escape to a new position using (
end for 22: if t 6= T then
Take 20% of the best adapted waves to the next iteration 24: end if
t + +, 26: end while
Return the best wolf xglobal as a solution 28: Stop operations are modeled - propagation, refraction and breaking. Propagation is understood as a movement of waves from deep water to shallow. During this movement, the wave height increases but the length decreases. This step is described as where v is random factor in the range of [ 1; 1] and (y) is a function that returns the value of the wavelength y and it is formulated as (y) min + ; new(y) = actual max min + where is a fitness function, min and max are respectively the minimum and maximum values in a particular iteration of the algorithm, is a small number to prevent division by zero and is the wavelength reduction coefficient.
After propagation, the next stage is refraction – it is a phenomenon of changes in wave direction, where the height reaches a value of 0. The new position after refraction of the wave is modeled as xactual = N ( ; ); (8) (9) (10) where N ( ; ) is a random number from the normal distribution with – mean and – standard deviation defined as 8 > < > : = jxglobal = jxglobal + xactualj 2
xactualj 2 ; (11) (12) (13) where xglobal is the best wave (solution) in current iteration. During refraction, the height of the wave is also modified by new = old (xactual) : (xnew)
The final stage of wave movement is breaking, which describes the movement of the wave at a depth below a certain threshold level – the velocity exceeds the wave celerity. The breaking stage is understood as a local search calculated as xnew = xactual + 2 N (0; 1); where
is the breaking parameter.
Algorithm 2 Water Waves Algorithm
In the heuristic algorithms, the initial population is selected at random. Such a solution for complex functions increases the risk of getting stuck in a local optimum (see Fig. 1). To remedy this situation, the initial population can be placed in specific locations in the solution space, i.e. all individuals are positioned at equally-spaced. As a result, the population forms a grid that covers the entire space. In the next step, each individual is multiplied to cover a larger area. For every individual is made local search. Each of the individuals is evaluated by fitness function and 25% of the best fittest are selected as the initial population.
Local search is done by a decrease gradient. The algorithm starts at a point x, for which (the negative for minimization problem) gradient is calculated as
@ (x1; x2) r xi = @xi for i = 1; 2: (14) Gradient indicates the direction of the fastest growth the value of the function at the measured point. In the next step, the next point is found according to the direction defined by the gradient as xnew = xactual r where is the value of step. A factor implementation is shown in Algorithm 3.
(15) x;
Numerical tests were performed to search global optimum of all functions described in Section II. For the selected amount of the population (n = 100 individuals) and iteration (10, 100, 1000) the results obtained for the original and modified methods. The results in terms of accuracy are presented in Tables I, II and III. The obtained average values for 10 experiments in terms of accuracy of the solution from time are presented in Fig. 4.
Based on the obtained data, the application of the modification in terms of accuracy is only cost-effective for a large number of iterations - the results are more accurate than others. For quantities less than 1000, better accuracy is achieved in the case of original algorithms. In terms of acceleration of the algorithm, additional calculations slow down the operations for small number of iterations. Similar to the accuracy, modifications is valuable when there will be a need for a much larger number of iterations.
The proposed modification reduces operational time heuristic algorithms and increasing the accuracy of their operation, assuming a large number of iterations or very accurate results. On the basis of the performed test for the selected function, the modification shown that it is possible to reduce the time. Algorithm 3 A factor algorithm
Wolf Search Algorithm obtained optimum x (x) (497,350286104414;413,316038741412) -445,109840056073 (470,030297278441;485,562031085399) -747,988554493845 (495,606099411662;401,486352105386) -787,798958711978 Wolf Search Algorithm with modification
obtained optimum x (x) (482,879289436564;394,047534639969) -532,10668463655 (362,447760432236;495,061778684641) -670,883977492652 (459,050439605047;407,631429847158) -827,9315354643
Water Wave Algorithm obtained optimum x (x) (416,564008862043;457,568839219198) -481,75325119652 (482,862816510192;394,327293482761) -522,678854547558 (429,694043635248;441,956854035126) -893,969574033705 Water Wave Algorithm with modification
obtained optimum x (x) (386,448251729109;445,815733413126) -78,0632300803166 (463,005703484177;494,428448618589) -481,70585333327 (514,777470228624;396,847095860563) -981,843214134724
Wolf Search Algorithm obtained optimum x (x) (2,34615738054093;3,25216948206172) -0,365027440014811 (3,9124181950057;3,62785225670219) -0,276365363830805 (2,96131405698197;2,17447623478923) -0,212171936285033 Wolf Search Algorithm with modification
obtained optimum x (2,51148351398831;3,47038642199262) (3,2396818237564;1,77784279537287) (2,19667368391374;1,37504338630244)
Water Wave Algorithm obtained optimum x (x) (2,1929323068787;2,67858712499895) -0,171094307906584 (3,5790521290987;3,95715529143678) -0,263663206287755 (3,89253193693819;2,23055503807522) -0,111170990040294 Water Wave Algorithm with modification
obtained optimum x (3,21630300125866;3,14909067244692) (2,63754989143347;2,82413371457911) (1,17472107344061;1,67250233454281)
Wolf Search Algorithm obtained optimum x (0,682362732329575;-0,67352732442018) (0,633187983945565;-1,88113112742134) (-1.0879799313;-0.9926871380) Wolf Search Algorithm with modification
obtained optimum x (-0,24526995711274;-0,385508137934612) (-0,0459746942138182;-0,795370650848081) (-0,234918390044439;-0,621006036932117)
Water Wave Algorithm obtained optimum x (-0,526868914965013;-0,343995140559969) (-0,086203324182985;-0,733375833711296) (-0,594777831153375;-0,345780614924515)
Water Wave Algorithm with modification
obtained optimum x (-0,877628832998513;-0,409932400290823) (-0,89729838347868;-0,823287643875595) (-0,282641141341366;-0,948922069253829) (x) 160,003686302222 163,753970449623 175.685