A list,
1 on the origin of artificial fish algorithm is xiao-lei li and others in 2002, swarm intelligence in the animal behavior research is put forward on the basis of a new type of Fang Sheng optimization algorithm, the algorithm according to the number of fish live in water the most is the place where the waters are rich in nutrients most this characteristic to simulate the foraging behavior of the fish to realize optimization. The algorithm mainly makes use of the three basic behaviors of fish: foraging, clustering and rejoining. The top-down optimization mode is adopted to start with the construction of the bottom behaviors of individuals and achieve the purpose of highlighting the global optimal value in the group through the local optimization of each individual in the shoal. This method adopts the bottom-up optimization idea. Firstly, the perception and behavior mechanism of a single individual is designed, and then one or a group of entities are placed in the environment, allowing them to solve problems in the interaction of the environment.
2. Ecological Basis In a body of water, the place with the largest number of fish is the place with the largest number of nutrients in the body of water. According to this characteristic, behaviors such as foraging, clustering and rear-chasing of fish can be imitated to achieve global optimization, which is the basic idea of fish swarm algorithm. In fish activities, foraging behavior, clustering behavior, rear-ending behavior and random behavior are closely related to the solution of optimal proposition. How to construct and realize these behaviors in a simple and effective way will be the main topic of algorithm implementation.
3 structural model of artificial fish Artificial fish is an abstraction and virtualization entity of real fish, which encapsulates its own data and a series of behaviors, can accept environmental stimulus information, and make corresponding activities. Its environment is determined by the solution space of the problem and the state of other artificial fish. Its behavior at the next moment depends on its own state and the state of the environment, and it also affects the environment through its own activities, and then affects the activities of other artificial fish. The external perception of artificial fish depends on vision. In the model of artificial fish, the following methods are used to realize the virtual vision of artificial fish:
Where is a random function, generates a random number between 0 and 1, and is the step size.
3.1 Encapsulated variables and function variables in the artificial fish: the total number of artificial fish, the state of the individual of the artificial fish (where is the optimal variable), the maximum stride length of the artificial fish, the Visual field of the artificial fish, the number of attempts, the crowding factor and the distance between the individual of the artificial fish. Function part: the food concentration at the current location of the artificial fish is expressed as (is the value of the objective function), and various behavior functions of the artificial fish (foraging behavior, clustering behavior, rear-ending behavior, random behavior and behavior evaluation function).
3.2 Description of four Basic behavior Algorithms of artificial fish 3.2.1 Foraging Behavior This is an activity of fish tending to food. Generally, it is believed that it selects the direction of action by perceiving the amount or concentration of food in the water through vision or taste. Set of artificial fish current state, and in its random choose another state perception scope, if get the state of the objective function is greater than the current state, the state of the new choice to get close to a step, on the contrary, to select the new state, judge whether meet the conditions, select number after reaching a certain number, if it still does not meet the conditions, the random moving step. Algorithm description: artificial fish within its field of vision randomly select a condition are calculated respectively and the objective function value and, if found than good, the direction towards a: otherwise, to continue the selection state within their field of vision, judge whether meet the conditions, after trial and error, there is still no progress conditions, random behavior is executed.
A large number or a small number of fish gather together to forage and avoid enemies, which is a survival mode formed in the process of evolution. Artificial fish explore the neighbor number of partners, partners and calculate the center position, and then put the new get the center of the objective function compared with the current position of the objective function, if the center position of the objective function is superior to the current position of the objective function and not very crowded, is the current position to the center position step, otherwise perform foraging behavior. When fish flock, they follow two rules: try to move toward the center of their neighbors, and avoid overcrowding. Algorithm description: The artificial fish searches for the number of partners and the central position of () in the current field of vision. If, then it indicates that the central position of partners is in an optimal state and not too crowded, then move one step toward the central position of partners; otherwise, foraging behavior will be carried out.
3.2.3 Rear-ending Behavior When a fish or several fish find food, the fish near them will follow, causing fish farther away to follow. When the objective function value of the optimal position is greater than the objective function value of the current position and it is not very crowded, the current position will move one step to the optimal neighbor fish; otherwise, the foraging behavior will be performed. Algorithm description: The artificial fish searches for the optimal partner of the function among the partners of () in the current field of vision. If, indicates that the surroundings of the optimal partner are not too crowded, then it moves one step toward the word partner; otherwise, it performs the foraging behavior.
3.2.4 Random Behavior It is a default behavior of foraging behavior and refers to the random movement of artificial fish in the field of vision. When they find food, they move quickly in the direction of more food. The algorithm describes the artificial fish moving one step randomly to reach a new state:
4. Artificial fish swarm algorithm Description Bulletin board is the place to record the optimal individual status of artificial fish. After completing an iteration, each artificial fish will compare its current state with the state recorded in the bulletin board. If it is better than the state in the bulletin board, it will update the state in the bulletin board with its own state, otherwise the state of the bulletin board will remain unchanged. When the iteration of the whole algorithm is over, the value of the bulletin board is the optimal solution. Behavior evaluation is a way to reflect the independent behavior of fish. When solving the optimization problem, two methods of evaluation are selected: one is to choose the optimal behavior execution; The other is to choose the better direction. To solve the maximum value problem, the heuristic method can be used, that is, to simulate and execute the behaviors such as clustering and reaming, and then evaluate the values after the actions and select the optimal one for execution. The default behavior is foraging. Termination condition of iteration: the usual method is to judge the allowable error of mean-square deviation fish obtained for many consecutive times; Or determine that the number of artificial fish clustered in a certain area reached a certain proportion; Or the mean value of successive times does not exceed the extreme value found; Or limit the maximum number of iterations. If the termination condition is met, the optimal record of the bulletin board is output. Otherwise continue iterating. Steps of artificial fish swarm algorithm:
Initialization Settings, including population size, initial position of no artificial fish, visual field of artificial fish, step length, crowding factor and repetition times; The adaptive value of each individual of the initial fish was calculated, and the optimal artificial fish state and its value were given to the bulletin board. Each individual was evaluated and the behaviors to be performed were selected, including foraging, clustering, rear-ending and random behaviors. Perform artificial fish behavior, renew themselves, generate new fish; Evaluate all individuals. If an individual is superior to the bulletin board, the bulletin board is updated to the individual; When the optimal solution on the bulletin board is within the satisfactory error bounds or reaches the upper limit of the number of iterations, the algorithm ends; otherwise, go to Step 3. 5. Optimization Principle of artificial fish swarm Algorithm In the process of optimization, artificial fish swarm algorithm may gather around several local optimal solutions, so that the artificial fish can jump out of the local optimal solution. The main factors to realize global optimization are as follows:
In the foraging behavior, when the number of repetitions is low, the artificial fish can move randomly and jump out of the local optimal solution. The random step size makes it possible for the artificial fish to turn to the global optimal solution on the way to the local optimal solution. The crowding factor limits the size of the swarm, so that the artificial fish can search for optimization more widely. The clustering behavior can make the fewer artificial fish trapped in the local optimal solution converge towards the global optimal solution and escape from the local optimal solution. The rear-end collision accelerates the artificial fish to swim to a better state.
6 Parameter setting and Performance 6.1 Convergence Base In artificial fish swarm algorithm, foraging behavior lays the foundation for algorithm convergence; The clustering behavior enhances the convergence stability of the algorithm. The rear-end collision enhances the speed and global convergence of the algorithm. The evaluation behavior also guarantees the convergence speed and stability of the algorithm.
6.2 Influences of Various Parameters on convergence Artificial fish swarm algorithm has five basic parameters: group size, visual field of artificial fish, step length, crowding factor and repetition times.
- Field of view: Since field of view has a great impact on all the behaviors in the algorithm, its change also has a complex impact on the convergence performance. When the visual field is small, the foraging behavior and random behavior of artificial fish are more prominent. When the field of vision is large, the rear-chasing behavior and clustering behavior of artificial fish will become more prominent, and the complexity of the corresponding algorithm will also increase. In general, the larger the vision, the easier it is for the artificial fish to find the global optimal solution and converge.
- Step size: For a fixed step size, with the increase of step size, the convergence rate is accelerated to a certain extent. However, when the step size exceeds a certain range, the convergence rate will slow down. If the step size is too large, the convergence rate will be greatly affected by the oscillation phenomenon. Using random walk a long way to a certain extent, prevent the occurrence of the phenomenon of shock, and greatly reduces the sensitivity of the parameter, but the fastest convergence speed and convergence rate of optimal fixed step, so, for a specific optimization problem, we can consider to use appropriate fixed step length or variable metric method to improve the convergence speed.
- Group size: The larger the number of artificial fish, the stronger the ability to jump out of the local optimal solution, and the faster the convergence rate. Of course, the cost is that the calculation amount of each iteration of the algorithm is also larger. Therefore, the number of graphs should be reduced as much as possible under the premise of stable convergence in the process of use.
- Number of attempts: The more attempts, the stronger the foraging ability of the artificial fish, and the higher the convergence efficiency. In the case of prominent local extremal value, it should be reduced appropriately to increase the probability of random swimming of artificial fish and overcome the local optimal solution.
- Crowding factor: in the maximum problem,; In the minimum problem,. Where is the extreme value close to the level, is the maximum number of artificial fish expected to gather in the neighborhood. With the combination of crowding factor and, the optimization results are affected by whether the artificial fish carries out rear-ending and clustering behavior. Taking the maximum value as an example (the case of the minimum value is just the opposite of the maximum value), the larger the maximum value is, the smaller the allowable crowding degree is, and the stronger the ability of the artificial fish to get rid of the local optimal solution is. However, the convergence rate will be slowed down, which is mainly because the artificial fish will walk away randomly to avoid overcrowding or be repelled by other artificial fish when approaching the optimal solution, and cannot accurately approach the extreme point. It can be seen that, although the introduction of “can avoid the artificial fish being overcrowded and falling into the local optimal solution, on the other hand, this parameter will cause the artificial fish located in the attachment of the extreme point to have mutually exclusive influence, and it is difficult to accurately approximate the extreme point. Therefore, for some specific problems where the local extremum is not very serious, the crowding factor can be ignored, so as to simplify the algorithm and accelerate the convergence rate and improve the accuracy of the results.
Description of rear-end collisions description of rear-end collisions
In the figure above, the artificial fish is the optimal artificial fish in their respective visual field, and its food concentration is, and is the circle with the center of the circle and the radius of the visual field, that is, the furthest distance that can be detected. The closer the artificial fish is, the better the state will be. In the maximum value case: when, all artificial fish execute the rear-end collision behavior and move toward; When, if the food concentration of is equal to the food circle of, then the artificial fish,, and between and carry out the rear-end collision behavior and move toward, and the artificial fish carry out foraging behavior. At this point, the larger the size is, the fewer artificial fish will execute the rear-end collision, and vice versa.
7. The characteristics of artificial fish swarm algorithm only need to compare the value of the objective function, and the property of the objective function is not required. The initial value of the requirement is not high, randomly generated or set as a fixed value can be strong robustness; The requirement for parameter setting is not high, and the tolerance range is large; The convergence speed is slow, but it has the parallel processing ability. Have good global optimization ability, can quickly jump out of the local best advantage; It can be used to quickly obtain a feasible solution for some situations with low requirements for intensive reading. It does not require a strict mechanistic model of the problem, or even an accurate description of the problem, which extends its scope of application.
Ii. Source code
clc
clear all
close all
tic
figure(1);hold on
ezplot('x*sin(10*pi*x)+2'[- 1.2]); %% Set the parameter fishnum=50; % to generate50Only artificial fish MAXGEN=50; % Maximum number of iterations try_number=100; % Maximum number of attempts visual=1; % Perceived distance delta=0.618; % Crowding factor step=0.1; % step size %% initialize shoal lb_ub=[- 1.2.1];
X=AF_init(fishnum,lb_ub);
LBUB=[];
for i=1:size(lb_ub,1)
LBUB=[LBUB;repmat(lb_ub(i,1:2),lb_ub(i,3),1)];
end
gen=1;
BestY=- 1*ones(1,MAXGEN); % The best function value in each step BestX=- 1*ones(1,MAXGEN); % the best independent variable in each step besty=- 100.; % optimal function value Y=AF_foodconsistence(X);while gen<=MAXGEN
fprintf(1.'%d\n',gen)
for i=1: fishnum % % cluster behavior [Xi1, Yi1] = AF_swarm (X, I, visual, step, delta, try_number, LBUB, Y); % % [Xi2, Yi2] = AF_follow rear-ended behavior (X, I, visual, step, delta, try_number, LBUB, Y);if Yi1>Yi2
X(:,i)=Xi1;
Y(1,i)=Yi1;
else
X(:,i)=Xi2;
Y(1,i)=Yi2;
end
end
[Ymax,index]=max(Y);
figure(1);
plot(X(1,index),Ymax,'. '.'color',[gen/MAXGEN,0.0])
plot(bestx(1),besty,'ro'.'MarkerSize'.100)
xlabel('x')
ylabel('y')
title('Optimal coordinate movement in fish swarm algorithm iteration') %% Optimization process diagramfigure
plot(1:MAXGEN,BestY)
xlabel('Number of iterations')
ylabel('Optimum value')
title('Iterative process of fish swarm algorithm')
disp(['Optimal solution X:',num2str(bestx,'% 1.4 f')])
disp(['Optimal solution Y:',num2str(besty,'% 1.4 f')])
toc
function [Xnext,Ynext]=AF_follow(X, I, Visual,step,deta,try_number,LBUB,lastY) % %X Position of all artificial fish % I Number of current artificial fish % Visual perception range %step Maximum moving step %deta crowding degree %try_number Maximum number of attempts %LBUB Upper and lower limits of each number %lastY Food concentration of last artificial fish position % output: %Xnext Xi artificial fish next position %Ynext Xi artificial fish next food concentration Xi=X(:, I); D=AF_dist(Xi,X); index=find(D>0 & D<visual);
nf=length(index);
if nf>0
XX=X(:,index);
YY=lastY(index);
[Ymax,Max_index]=max(YY);
Xmax=XX(:,Max_index);
Yi=lastY(i);
if Ymax/nf>deta*Yi;
Xnext=Xi+rand*step*(Xmax-Xi)/norm(Xmax-Xi);
for i=1:length(Xnext)
if Xnext(i)>LBUB(i,2)
Xnext(i)=LBUB(i,2);
end
if Xnext(i)<LBUB(i,1)
Xnext(i)=LBUB(i,1);
end
end
Ynext=AF_foodconsistence(Xnext);
else
[Xnext,Ynext]=AF_prey(X(:,i),i,visual,step,try_number,LBUB,lastY);
end
else
[Xnext,Ynext]=AF_prey(X(:,i),i,visual,step,try_number,LBUB,lastY);
end
Copy the codeThird, the operation result
Fourth, note
Version: 2014 a