I. Introduction of gray Wolf algorithm

Grey Wolf Optimizer (GWO) is a population intelligent optimization algorithm proposed by Mirjalili et al from Griffith University in Australia in 2014. This algorithm is an optimization search method developed by the gray Wolf predation activity, and it has strong convergence performance, few parameters, easy to implement and so on. In recent years, it has been widely concerned by scholars, and has been successfully applied to shop scheduling, parameter optimization, image classification and other fields.

Algorithm principle:

Gray wolves belong to the gregarious canid family and are at the top of the food chain. Gray wolves adhere to a rigid social dominance hierarchy. As shown in figure:

The first rung of the social hierarchy:The leader of the pack is marked as.Wolves are mainly responsible for making decisions about activities such as feeding, roosting, and sleeping time. Because the other wolves need obedienceWolf’s orders, soWolves are also known as dominant wolves. In addition,The Wolf is not necessarily the strongest Wolf of the pack, but in terms of management ability,The Wolf must be the best.

The second tier of the social hierarchy:The Wolf, it obeysWolf, and assistWolves make decisions. inWhen wolves die or grow old,The Wolf will becomeThe best candidate for Wolf. althoughThe Wolf to obeyThe Wolf, butWolves have control over wolves in other social hierarchies.

The third tier of the social hierarchy:The Wolf, he obeyed 、Wolves, who also dominate the rest of the hierarchy.Wolves are generally composed of juvenile wolves, sentinel wolves, hunting wolves, old wolves and nursing wolves.

The fourth rung of the social hierarchy:Wolves, which usually need to obey other wolves in the social hierarchy. Although it may seemWolves don’t play much of a role in the pack, but if notThe existence of wolves, wolves will have internal problems such as cannibalism.

The GWO optimization process includes social stratification, tracking, encircling, and attacking of gray wolves, as described below.

1) Social hierarchyWhen designing A GWO, the first step is to build a gray Wolf Social Hierarchy model. The fitness of each individual in the population was calculated, and the three gray wolves with the best fitness were marked as, 、And the rest of the wolves were labeled. In other words, the social hierarchy of the gray Wolf group is from high to low;, 、 及 . The optimization process of GWO mainly consists of the best three solutions in each generation population (i.e, 、) to guide completion.

When gray wolves search for Prey, they gradually approach the Prey and encircle it. The mathematical model of this behavior is as follows:

Where, t is the current iteration number:. Represents the Hadamard product operation; A and C are synergy coefficient vectors; Xp represents the position vector of prey; X(t) represents the position vector of the current gray Wolf; During the entire iteration, a decreases linearly from 2 to 0; R1 and r2 are random vectors in [0,1].

3) Hunring

Gray wolves have the ability to identify the location of potential prey (the optimal solution), and the search process depends on, 、Gray Wolf’s guide to complete. However, the solution space characteristics of many problems are unknown, and gray wolves cannot determine the exact location of prey (optimal solution). In order to simulate the search behavior of the gray Wolf (candidate solution), the hypothesis is given, 、Strong ability to identify the location of potential prey. Therefore, during each iteration, the best three wolves in the current population (, 、), and update other search agents based on their location information (including). The mathematical model of this behavior can be expressed as follows:

Type:,,Respectively represent the current population, 、Position vector of; X represents the position vector of the gray Wolf;,,Respectively represent the distance between the current candidate gray wolves and the optimal three wolves; When | A | > 1, gray wolves try to disperse in different areas and search for prey. When | A | < 1, the Wolf will focus its search on one or A few areas of prey.

As can be seen from the figure, the position of the candidate solution finally falls at, 、Define random circle position inside. In general,, 、The approximate position of the prey (lurking in the optimal solution) was first predicted, and then other candidate wolves randomly updated their positions near the prey under the guidance of the current optimal blue Wolf.

In the process of constructing the Attacking Prey model, the decrease of a value will cause the fluctuation of A value according to the formula in 2). In other words, A is A random vector on the interval [-a, A] (note: it is [-2a,2a] in the first paper of the original author, and is corrected as [-a, A] in the following paper), where A decreases linearly during the iteration. When A is in the range [-1, 1], the next position of the Search Agent can be anywhere between the current gray Wolf and the prey.

5) Hunt for prey(Search for Prey) Gray wolves mainly rely on, 、To find prey. They start dispersing to search for information about the location of prey, and then focus on attacking prey. For the establishment of decentralized model, the search agent can be removed from the prey by | A | > 1. This search method enables GWO to conduct global search. Another search coefficient in the GWO algorithm is C. It can be seen from the formula in 2) that C vector is a vector composed of random values in the interval range [0,2], and this coefficient provides random weight for prey to increase (| C | > 1) or decrease (| C | < 1). This helps GWO exhibit random search behavior during optimization to avoid the algorithm falling into local optimality. It is worth noting that C does not decrease linearly. C is a random value in the process of iteration, and this coefficient helps the algorithm to jump out of the local area, especially the algorithm becomes particularly important in the later stage of iteration.

Second, grid map introduction

There are two ways to represent the grid map, rectangular coordinate system and ordinal method. Ordinal method saves more memory than rectangular coordinate method

Indoor environment raster modeling steps

1. Selection of grid grain size

Grid size is a key factor. Grid selection is small, environmental resolution is large, environmental information storage is large, decision-making speed is slow.

The grid selection is large, the environmental resolution is small, the storage of environmental information is small, the decision-making speed is fast, but the ability to find paths in the dense obstacle environment is weak.

2. Obstacle grid is determined

When a robot enters a new environment, it does not know the information of indoor obstacles, which requires the robot to traverse the whole environment, detect the location of obstacles, find the serial number value in the corresponding grid map according to the location of obstacles, and modify the corresponding grid value. Free grids are assigned a value of 0 for grids that do not contain obstacles, and obstacle grids are assigned a value of 1 for grids that do.

3. Establishment of raster map of unknown environment

Usually set the end to a point can’t arrived, such as (1, 1), at the same time the robot in the process of pathfinding follow the principle of “down at the upper left”, namely the robot walk down first, when the robot detect obstacles ahead, robot turn to the right, follow these rules, the robot eventually can search out all the feasible path, And the robot will eventually return to its starting point.

Note: on grid maps, it is a rule that the size of an obstacle is always equal to the size of n grids, never half a grid.

Three, code,

clc; Close all the clear load (' data1. Mat ') S = (S_coo (2) 0.5) * num_shange + (S_coo (1) + 0.5); Corresponding number E = % starting point (E_coo (2) 0.5) * num_shange + (E_coo (1) + 0.5); PopSize=20; % Population size OldBestFitness=0; % Old optimal fitness value gen=0; % iteration count maxgen =100; % Maximum number of iterations C1 =0.6; % retention probability c2=0.3; % subwolves retention probability C3 =0.1; %% Alpha_score= INF; %change this to -inf for maximization problems Beta_score=inf; %change this to -inf for maximization problems Delta_score=inf; %change this to-INF for maximization problems %Initialize the positions of search agents %Initialize the path Group=ones(num_point,PopSize); % population initialization flag=1; Figure (1) Hold on for I =1:num_shange for j=1:num_shange if sign(I,j)==1 y=[i-1,i-1, I, I]; x=[j-1,j,j,j-1]; h=fill(x,y,'k'); Set (h, 'facealpha, 0.5) end s = (num2str ((I - 1) * num_shange + j)); Text (j-0.95,i-0.5,s,'fontsize',6) end end axis([0 num_shange 0 num_shange])% plot(S_coo(2),S_coo(1), 10, 'p', 'markersize', 'markerfacecolor', 'b', 'MarkerEdgeColor', 'm') % draw starting point the plot (E_coo (2), E_coo (1), 'o', 'markersize', 10,' markerFacecolor ','g','MarkerEdgeColor', 'c')% set(gca,'YDir','reverse'); % image rollovers for I = 1: num_shange plot (num_shange [0], [I - I - 1, 1], 'k -'); plot([i i],[0 num_shange],'k-'); End for I =2:index1 Q1=[mod(route_lin(i-1)-1,num_shange)+1-0.5,ceil(route_lin(i-1)/num_shange)-0.5]; Q2 = [mod (route_lin (I) - 1, num_shange) + 1-0.5, ceil (route_lin (I)/num_shange) to 0.5]; Plot ([Q1 (1), Q2 (1)], [Q1 (2) and Q2 (2)], 'r', 'our LineWidth, 3) end title (' the optimal route algorithm based wolves -'); % evolution curve Figure (2); plot(BestFitness); Xlabel (' iteration number ') yLabel (' fitness value ') grid on; Title (' evolution curve '); Disp (' Base Pack algorithm - Optimal route :') disp(num2str(route_lin)) disp([' distance from start to finish :',num2str(BestFitness(end))]);Copy the code

Complete code added QQ1575304183