A brief introduction of Longicorn beard search algorithm

Beetle Antennae Search-Bas, also known as Beetle Antennae Search, is an efficient intelligent optimization algorithm proposed in 2017. Similar to genetic algorithm, particle swarm optimization algorithm, simulated annealing and other intelligent optimization algorithms, tianox must search does not need to know the specific form of function, no virtual gradient information, can achieve efficient optimization. Compared with particle swarm optimization (PSO), longicorn search only requires one individual, namely one longicorn, which greatly reduces the computation.

2 Principles and code realization 2.1 Bionic principle Longicorn beard search algorithm developed by longicorn foraging principle inspiration. Biological principle: when cattle forage for food, longicorn cattle do not know where the food is, but according to the strength of the food smell to forage. Longhorn has two long feelers. If the smell on the left side is stronger than on the right side, the longhorn flies to the left. Otherwise, it flies to the right. Based on this simple principle, longhorns can find food efficiently. Longhorn beard search inspiration: the smell of food is equivalent to a function, this function in three-dimensional space each point value is different, longhorn two beard can collect their own nearby two points of smell value, longhorn’s purpose is to find the global smell value of the largest point. Mimicking the behavior of longicorn, we can efficiently conduct function optimization.

2.2 Algorithm Longus beetles move in three-dimensional space, and longus beetles search needs to be effective for any dimensional function. Therefore, longicorn whisker search is the extension of longicorn biological behavior in arbitrary dimensional space. The following simplified model was used to describe longicorn beetles: the left and right sides of longicorn beetles must be located on both sides of the center of mass. The ratio of step length to distance D0 between two whiskers is a fixed constant, that is, step= C *d0, where C is a constant. That is, big longhorns (long distance between two whiskers) take big strides, small longhorns take small steps. After the beetle flies to the next step, the head orientation is random.

Step 1: For an n-dimensional space optimization problem, we use XL to represent the left whisker coordinate, Xr to represent the right whisker coordinate, x to represent the centroid coordinate, and D0 to represent the distance between two whiskers. According to hypothesis 3, the orientation of the head of the beetle is arbitrary, and therefore the orientation of the vector from the right whisker to the left whisker of the beetle is arbitrary, so a random vector dir=rands(n,1) can be generated to represent it. Normalize this: dir=dir/norm(dir); So we get xL-xr =d0dir; Obviously, XL and Xr can also be expressed as the center of mass; Xl = x + d0dir / 2; Xr = x – d0dir / 2. Step 2: For the function f to be optimized, take the values of the left and right whiskers: Felft =f(xl); Fright = f (xr); Judge the two values. If Fleft

fright, in order to find the minimum value of F, the horny beetles move step in the direction of the right palp, i.e. X =x-stepnormal(XL-XR); In the above two cases, the sign function sign can be uniformly written as x= X-stepnormal (XL-XR)sign(fleft-fright)= X-stepDIR *sign(Fleft-fright). (Note: Normal is the normalized function)
,>

Dir =rands(n,1); Dir = dir/norm (dir); X =x+d0dir/2; Xr = x – d0dir / 2; % felft=f(xl); Fright = f (xr); % Whisker odor intensity x= X-step dirsign(Fleft-fright). Step size: Two recommendations: Use step=etastep in each iteration, where ETA is closer to 1 between 0 and 1, usually eta=0.95; Step0, temp= etATEMp, step=temp+step0. About the initial step size: the initial step size can be as large as possible, preferably equal to the maximum length of independent variable.

2. Introduction of BP neural network

BP (Back Propagation) neural network was proposed by Rumelhart and McCelland in 1986. See their paper Learning Representations by Back-propagating Errors published in Nature. BP neural network is one of the most widely used neural network models. BP network can learn and store a large number of input-output mode mappings without revealing the mathematical equations describing the mappings in advance. Its learning rule is to use the fastest descent method, through back propagation to constantly adjust the weight and threshold of the network, so as to minimize the sum of squares of error of the network.

Last time we said that the multilayer perceptron has a bottleneck in how to obtain the weights of hidden layers. Since we can’t get the weight of the hidden layer directly, can we adjust the weight of the hidden layer indirectly by getting the error of the output result and the expected output of the output layer first? BP algorithm is designed with this idea. Its basic idea is that the learning process is composed of two processes: signal forward propagation and error back propagation. In the forward propagation, the input sample is introduced from the input layer, and then transmitted to the output layer after being processed layer by layer by layer. If the actual output of the output layer is not consistent with the desired output (teacher signal), then the back propagation stage of the error is entered. In reverse transmission, the output is transmitted back to the input layer layer by layer through the hidden layer in some form, and the error is apportioned to all the units of each layer, so as to obtain the error signal of each unit, which is used as the basis for correcting the weight of each unit. The detailed flow of these two processes will be described later.

The signal flow diagram of BP algorithm is shown in the figure below 3. Analysis of BP network characteristics — BP three elementsWhen we analyze an ANN, we usually start from its three elements, namely, 1) network topology; 2) Transfer function; 3) Learning algorithm.The characteristics of each element add up to determine the functional characteristics of the ANN. Therefore, we also start from these three elements of BP network research.

3.1 Topology structure of BP networkAs we said last time, BP networks are actually multilayer perceptrons, so their topology is the same as that of multilayer perceptrons. Because the single hidden layer (three layer) perceptron has been able to solve simple nonlinear problems, it is the most common application. The topology of the three-layer perceptron is shown in the figure below. A simple three-layer BP: 3.2 Transfer function of BP networkThe transfer function adopted by BP network is nonlinear transformation function — Sigmoid function (also known as S function). Its characteristic is that the function itself and its derivative are continuous, so it is very convenient to deal with. Why this function is chosen will be further explained later when we introduce the learning algorithm of BP networks. The unipolar S-type function curve is shown in the figure below.The bipolar S-type function curve is shown in the figure below. 3.3 Learning algorithm of BP networkThe learning algorithm of BP network is BP algorithm, also known as δ algorithm (in the learning process of ANN, we will find many terms with multiple names). Taking three-layer perceptron as an example, when the network output is different from the expected output, there is an output error E, which is defined as follows Next, we will introduce the specific process of BP network learning and training.

Training a BP neural network is actually to adjust the weight and bias of the network. The training process of BP neural network is divided into two parts:

Forward transmission, layer by layer wave transfer output value; Reverse feedback, reverse layer by layer adjustment of weight and bias; Let’s look at forward transmission first. Before training the network, we need to randomly initialize weights and biases, take a random real number of [−1,1] [-1,1][−1,1] for each weight, take a random real number of [0,1][0,1] [0,1] for each bias, Then forward transmission begins.

The training of neural network is completed by multiple iterations, each iteration uses all the records of the training set, while each training network uses only one record, which is described abstractly as follows:

whileTermination conditions not met:for record:dataset:
        trainModel(record)

Copy the code

4.1 Backpropagation 4.2 Training termination conditionsAll the records of the data set are used in each training round, but when to stop the training, there are two stopping conditions: set the maximum number of iterations, for example, stop the training after 100 iterations of the data set, calculate the prediction accuracy of the training set on the network, and stop the training after reaching a certain threshold value

5.1 Network structure There are N nn neurons in the input layer, P PP neurons in the hidden layer, and Q QQ neurons in the output layer.

5.2 Definition of Variables Step 9: Judge the rationality of the model judge whether the network error meets the requirements. When the error reaches the preset precision or the number of learning times is greater than the maximum number designed, the algorithm ends. Otherwise, select the next learning sample and the corresponding output expectation, return the third part, and enter the next round of learning.

In the design of BP network, the number of layers of the network, the number of neurons in each layer, the activation function, the initial value and the learning rate should generally be considered. The following are some selection principles.

6.1 Layer theory of Network has proved that a network with deviation and at least one S-type hidden layer plus one linear output layer can approach any rational function. Increasing the number of layers can further reduce the error and improve the accuracy, but it also complicates the network. Also not to be used only with nonlinear activation function of single-layer network to solve the problem, because you can do it with a single network problems, using adaptive linear network will be solved, and the adaptive linear network speed, for the nonlinear function can only be used to solve the problem, single precision is high enough, also only add layer can achieve the desired results.

6.2 Number of Hidden Layer Neurons Network training accuracy can be improved by adopting a hidden layer and increasing the number of its neurons, which is much simpler than increasing the number of network layers in structural implementation. Generally speaking, we use precision and training network time to measure the design quality of a neural network: (1) When the number of neurons is too small, the network cannot learn well, and the number of training iterations is relatively large, and the training accuracy is not high. (2) When there are too many neurons, the network has more powerful functions and higher accuracy, and the number of training iterations is also larger, which may lead to over fitting. Thus, the principle of selecting the number of hidden layer neurons of neural network is as follows: on the premise of solving the problem, add one or two neurons to accelerate the error reduction speed.

6.3 Selection of Initial Weights Generally, the initial weights are random numbers ranging from −1 to 1. In addition, After analyzing how the two-layer network trains a function, Widelow et al. proposed a strategy of selecting an initial weight of S √r, where R is the number of inputs and S is the number of neurons at the first layer.

6.4 Learning Rate The learning rate ranges from 0.01 to 0.8. A large learning rate may cause system instability, but a small learning rate causes slow convergence and requires a long training time. For a more complex network, different learning rates may be required at different positions of the error surface. In order to reduce the training times and time for finding the learning rate, a more appropriate method is to adopt a variable adaptive learning rate, so that the network can set different learning rates at different stages.

6.5 Selection of Expected Error In the process of network design, an appropriate value of expected error should also be determined after comparative training, which is relative to the number of hidden layer nodes required. In general, two networks with different expected error values can be trained at the same time, and finally one of them can be determined by integrating factors.

7 Limitations of BP network BP network has the following problems: (1) Long training time is required: this is mainly caused by the small learning rate, which can be improved by changing or adaptive learning rate. (2) Completely unable to train: this is mainly reflected in the paralysis of the network. Usually, in order to avoid this situation, one is to choose a smaller initial weight and adopt a smaller learning rate. (3) Local minimum: The gradient descent method adopted here may converge to the local minimum, and better results may be obtained by using multi-layer networks or more neurons.

The main objective of P algorithm is to speed up the training speed and avoid falling into local minimum, etc. Common improvement methods include driving factor algorithm, adaptive learning rate, changing learning rate and action function shrinkage method. The basic idea of momentum factor method is to add a value proportional to the previous weight change to each weight change on the basis of back propagation, and generate a new weight change according to the back propagation method. The adaptive learning rate method is for some specific problems. The principle of the method to change the learning rate is that, in successive iterations, if the reciprocal sign of the objective function is the same for a certain weight, the learning rate of the weight increases; otherwise, if the sign is opposite, the learning rate of the weight decreases. And the shrink-back rule is to shift the function, which is to add a constant.

Three, some source code

The weight and threshold value of BP were optimized with longhorn whisker algorithm. The data samples were test data, not actual data of the paper, samples60Of which each sample has401Eigenvalues; NIR is the spectral data of the sample, and Octane is60*1Octane number of %1.0Version %% Clear all close all CLC TIC %% Load data Load spectra_data.mat % Randomly generate training set and test set temp=randperm(size(NIR,1)); % Training set --50A sample P = NIR (temp (1:50:)),';
T=octane(temp(1:50),:)'; % Test set --10A sample P_test = NIR (temp (51:end),:)';
T_test=octane(temp(51:end),:)';
N=size(P_test,2);
M=size(P,2); %% normalized [P, ps_input] = mapminmax(P,0.1); %p_train normalized processing, range is [0.1], the default is [- 1.1]
P_test = mapminmax('apply',P_test,ps_input); % use the same mapping for P_test [T, ps_output] = mapminmax(T, ps_output)0.1);
%% 
inputnum=size(P,1);
outputnum=size(T,1);
hiddennum=9; Net =newff(P,T, hiddenNum); net.trainParam.epochs =1000;
net.trainParam.goal = 1e-3;
net.trainParam.lr = 0.01; %% Longhorn algorithm initializes ETA =0.8;
c=5; % Relationship between step size and initial distance step=30; % Initial step size n=100; % Number of iterations k=inputnum*hiddennum+outputnum*hiddennum+hiddennum+outputnum; x=rands(k,1);
bestX=x;
bestY=fitness(bestX,inputnum,hiddennum,outputnum,net,P,T);
fbest_store=bestY;
x_store=[0; x; bestY]; display([' '0..'xbest=[',num2str(bestX'),'],fbest=',num2str(bestY)]) %% iteration partfor i=1:n
d0=step/c;
    dir=rands(k,1);
    dir=dir/(eps+norm(dir));
    xleft=x+dir*d0/2;
    fleft=fitness(xleft,inputnum,hiddennum,outputnum,net,P,T);
    xright=x-dir*d0/2;
    fright=fitness(xright,inputnum,hiddennum,outputnum,net,P,T);
    x=x-step*dir*sign(fleft-fright);
    y=fitness(x,inputnum,hiddennum,outputnum,net,P,T);
    if y<bestY
        bestX=x;
        bestY=y;
    end
    if y<0.001
         bestX=x;
        bestY=y;
    end
    x_store=cat(2,x_store,[i;x;y]);
    fbest_store=[fbest_store;bestY];
    step=step*eta;
     display([num2str(i),':xbest=[',num2str(bestX'),'],fbest=',num2str(bestY)])
end
M=size(P,2);
w1= bestX(1:inputnum*hiddennum);
B1= bestX(inputnum*hiddennum+1:inputnum*hiddennum+hiddennum);
w2= bestX(inputnum*hiddennum+hiddennum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum);
B2= bestX(inputnum*hiddennum+hiddennum+hiddennum*outputnum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum+outputnum); %% Network weight assignment %% Optimized weight and threshold test result %% Optimized weight and threshold inputnum=size(P,1); % input layer number of neurons outputnum=size(T,1); N=size(P_test,2);
M=size(P,2); Net =newff(P,T,9); %% Set network parameters: training times1000, training objectives0.001, learning rate00.1
net.trainParam.epochs =3000;
net.trainParam.goal = 1e-6;
net.trainParam.lr = 0.01; %% BP Initial weight and threshold w1num=inputnum*hiddennum; % Number of weights from input layer to hidden layer w2num=outputnum*hiddennum; W1 =bestX(1:w1num); % Weight from the initial input layer to the hidden layer B1=bestX(w1num+1:w1num+hiddennum);
w2=bestX(w1num+hiddennum+1:w1num+hiddennum+w2num); % initial hidden layer to output layer weight B2=bestX(w1num+hiddennum+w2num+1:w1num+hiddennum+w2num+outputnum); % Output layer threshold net.iw{1.1}=reshape(w1,hiddennum,inputnum);
net.lw{2.1}=reshape(w2,outputnum,hiddennum);
net.b{1}=reshape(B1,hiddennum,1);
net.b{2}=reshape(B2,outputnum,1);
%% 训练网络
net=train(net,P,T);
%% 测试网络
t_sim_P= sim(net,P);
t_sim_P_test= sim(net,P_test);
%% 反归一化
T=mapminmax('reverse',T,ps_output); The function error = fitness (x, inputnum, hiddennum outputnum,.net, P, T) % this function is used to calculate the individual fitness value input x % % % % inputnum input layer node number % hiddennum Hidden layer node %outputnum output layer node % NET network %P training input data %T training output data %% output %error individual fitness value %% extraction M=size(P,2);
w1=x(1:inputnum*hiddennum);
B1=x(inputnum*hiddennum+1:inputnum*hiddennum+hiddennum);
w2=x(inputnum*hiddennum+hiddennum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum);
B2=x(inputnum*hiddennum+hiddennum+hiddennum*outputnum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum+outputnum); %% network weight assignment net.iw{1.1}=reshape(w1,hiddennum,inputnum);
net.lw{2.1}=reshape(w2,outputnum,hiddennum);
net.b{1}=reshape(B1,hiddennum,1);
net.b{2}=reshape(B2,outputnum,1); Net = net (net,P,T); % % test Y = sim (.net, P); error=sum(abs(Y-T).^2)./M;
end



Copy the code

4. Operation results

Matlab version and references

1 matlab version 2014A

[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.