I. Introduction to intelligent water drop algorithm
1 overview In nature, the channel is composed of flowing water droplets move to create huge group, compared with the water droplets group itself, which flows through the channel is what they are in the surroundings, and the environment are the drastic change of flow direction of the water droplets groups, at the same time, the surrounding environment also influence the flow of water droplets group. For example, in the environment, solid boulders and soil hinder the flow of water droplets, while soft and loose soil has much less resistance to the flow of river water. In fact, the appearance of rivers in nature is the result of the long-term interaction between droplet groups and the surrounding environment. According to people’s common sense, most of the rivers and waterways in nature are zigzagging, but the water in the river is not like the human vision to the lake or the sea, but, the water droplets under the action of the earth’s gravity constantly forward flow. As we all know, the earth’s gravity direction pointing to the center of the earth, so if the surrounding environment without obstacles, water should be along the direction of gravity to the center of the earth movement: due to the gravity of the earth, the water droplets in the process of flow will get some acceleration, therefore with its movement speed will slowly rising. However, in reality, there is no such ideal state and no ideal straight path from the source of water to the center of the earth, and even the actual path of water dissipation is far different from the ideal path due to the influence of brick barriers, hence the appearance of the river we see today. It is found that it is optimal for water droplets to establish a channel of meters under the condition of movement. Water droplets in a river have two properties: they have a certain speed and they carry a certain amount of soil. In this case, the water droplets move the mud from one place to another as they move. As far as we know, the earth will be carried in water from high speed to the flow rate is low, the reason is that when the water droplets at high speeds of its kinetic energy is larger, can overcome the earth’s gravity to take the role of the soil, when the water flow with low speed, water droplets will carry soil in earth’s gravity deposited in the droplets travel path. For this reason, the earth will be in the region of the flow rate is higher allochthonous more and more, corresponding channel is becoming more and more deep, has attracted more and more flow here, which can hold more water, the soil and water droplets carried in flow speed is slow because of the earth’s gravity Unloaded and deposition in the riverbed. When a water droplet flows from one place to another in a river, the velocity of the droplet, the amount of soil carried by the droplet, and the amount of soil between the two places all change significantly: 1) the velocity of the droplet will increase as it flows; 2) The water droplets will carry more and more soil, and 3) the river bed between these two points will carry less and less soil.
In fact, as described above, water clearings carry a certain amount of soil from the riverbed as they move from one place to another, and the amount of soil in the river channel decreases and the amount of soil carried by the dropper body increases. In the process of this movement, the velocity at which the water droplets flow will also change. Speed larger droplets when flow carries on more mud from the river, in addition, due to the water flow speed with speed and it week associated with environment, the environment for the movement of the water droplets to play the role of a block, so when large amounts of surrounding soil, clear water flow rate in the period of path of growth will be slower, When the surrounding soil is small, the speed of water droplets in the period of path gain corresponding will be more and more quickly, will be easier to forward flow: within this we get move when the water droplets in the nature has the following properties: 1) high flow rate of water droplets than low flow rate of water droplets in the path moves can carries more of the earth: 2) The velocity increment obtained by water droplets in the path with less soil is greater than that obtained in the path with the most soil: 3) when water flow in choosing a path to the possibility of a larger move toward the path of the soil is less. 3 intelligent water basic principle of the algorithm Above has introduced the water droplets in nature has the characteristics of some typical, according to the above description of these features, according to the imagination of people, can the virtual human model is set up, known as intelligent water droplets (IWD), It has two important properties: Soil (IWD) is generally used to represent the amount of soil carried by water droplets, and Veloci TV (/WD) is used to represent the velocity of water flowing forward. In engineering problem solving, the surrounding environment of intelligent water droplets flowing represents the engineering problems we need to solve. Since the shortest path sought by intelligent water droplets in interaction is the optimal path found by us in solving engineering problems, soil(JWD) and Velocity (IWD), two important properties of intelligent water droplets, are constantly changing in the process of sub-path finding. We assume that some intelligent water droplets flow from a starting point to an end point in an environment where there may be more than one path from the beginning point to the end point. The environment referred to here is the engineering problem we need to solve in practice, which can be divided into two kinds of problems: first, in the case of the end point is known, to solve this kind of problem needs to find the best path from the beginning point to the end point according to a certain standard (usually distance). Second: in the case that the position of the end point is not known in advance, to solve this kind of problem, it is necessary to find the optimal position of the end point according to the cost or other standards.
Two, some source code
clear all;
clc;
format short g;
global D;
global q;
global q1;
global ss;
global E;
global L;
global ELL;
% test=xlsread('test.xlsx'.1);
%
% position=test(:,2:3);
% data=[
% 100 100 0 0 0 40
% 60 100 10 0.2 0 3
% 20 110 15 0.3 0 4
% 160 150 21 0.3 1 6
% 160 110 16 0.4 0 4
% 30 20 25 0.3 1 4
% 100 60 22 0.2 0 6
% 100 170 15 0.1 0 5
% 30 10 12 0.4 0 6
% 60 50 15 0.3 1 7
% 160 160 20 0.2 0 6
% 50 140 23 0.3 0 6];
position=[18.70 15.29
16.47 8.45
20.07 10.14
19.39 13.37
25.27 14.24
22.00 10.04
25.47 17.02
15.79 15.10
16.60 12.38
14.05 18.12
17.53 17.38
23.52 13.45
19.41 18.13
22.11 12.51
11.25 11.04
14.17 9.76
24.00 19.89
12.21 14.50]; % D D= squareForm (pdist(position(:,1:2),'euclidean')); % vehicle cost per vehicle: h % Fixed cost per vehicle: r. % vehicle speed v; % Maximum vehicle load Qmax. h=1; R=10; v=1; Qmax=200; epsilon=0.001;
R0=2; R1=0.8; % Vehicle travel time matrix T T=D/v between distribution center and demand points; % Maximum number of iterations Iter=30; % number of drops N N=size(position,1); % Speed update parameter: av=1; bv=0.01; cv=1; % soil volume update parameter: as=1; bs=0.01; cs=1; % Local soil renewal weight coefficient alpha=0.9; % Global soil renewal weight beta=0.9; % Initial amount of soil between any two points Initsoil Initsoil=1000; % initial soil mass matrix W?? W=ones(N)*1000; % Initial speed of each drop InitVel; % InitVel=100;
InitVel=randperm(100.1); % Global optimal objective function value TotalZ=1000000; % TotalRoute=[]; % main program t=0;
WaterDrop(1,N)=struct('SW', [],... % initial soil amount matrix corresponding to water droplets'Source', [],... The starting point of water droplets is1; Distribution center'Target', [],... %'VisitNode', [],... % Sequence of points visited (access path)'UnvisitNode', [],... % A collection of unaccessed points'Vel', [],... % Initial velocity of the drop'Soil', [],... % Initial amount of soil carried by water droplets'Q', [],... % The amount of water droplets loaded at departure'S', [],... % The time when the drop reaches source(k)'ZZ', [],... % The initial value of the object function corresponding to the drop'FK'[]); FV % q=test(:,4); % q1=TestData(:,5);
q=[0 6 5 11 6 3 8 5 6 4 5 7 6 10 9 4 7 8 ]';
% q1=[0 3.6 2 4.6 3.6 2.4 4.8 3 3.6 2.4 3 4.2 3.6 4 5.4 2.6 2.4 3]';
% ss=test(:,7); % Service time per demand point ss=[0 1.8 1.0 2.3 1.8 1.2 2.4 1.5 1.8 1.2 1.5 2.1 1.8 2.0 2.7 1.3 1.2 1.5]'; E=[0 5.0 4 1 2.0 5 2 1 3 1 2 2.0 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1;
L=[40 20 15 20 20 15 18 24 27 20 16 20 10 25 28 24.0 20 23]'; % % E=test(:,5); % L=test(:,6); % L=test(:,6); % Upper limit of time window for each demand point ELL=L-E; % EP=test(:,8); % LP=test(:,9); I=1:N; while t < Iter clc fprintf('The %d evolution \n',t+1); % Set the initial dynamic variable: % The optimal objective function value of this iteration Z=1000000; % Optimal path of this iteration Route=[];for k=1:N
WaterDrop(k).SW=W;
WaterDrop(k).Source=1;
WaterDrop(k).VisitNode=[1]; WaterDrop(k).UnvisitNode=I; WaterDrop(k).Vel= InitVel; % Initial amount of Soil carried by water droplets WaterDrop(k).soil =0; % WaterDrop(k).q (WaterDrop(k).source)=0; % The time when the drop reaches source(k); WaterDrop(k).S(WaterDrop(k).Source)=0; % Initial value of the objective function corresponding to the KTH drop WaterDrop(k).zz =0;
end
for k=1:N
while WaterDrop(k).Source~=1 || ~isequal(WaterDrop(k).UnvisitNode,[1])
WaterDrop(k).FK=[];
if WaterDrop(k).Source= =1
alt=2;
else
alt=1;
end
fori=alt:length(WaterDrop(k).UnvisitNode) WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))=WaterDrop(k).Q(WaterDrop(k).Source)+q(WaterDrop(k).UnvisitNode(i)); % Judge whether the load of point I is less than the maximum load of the vehicle and whether the time to reach point I is within the time window required by point Iif WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))<Qmax;
WaterDrop(k).FK=[WaterDrop(k).FK,WaterDrop(k).UnvisitNode(i)];
end
end
% for i=alt:N
% if ismember(i,WaterDrop(k).UnvisitNode)
% % ifsum(ismember(WaterDrop(k).UnvisitNode,i)) % WaterDrop(k).Q(i)=WaterDrop(k).Q(WaterDrop(k).Source)+q(i); % WaterDrop(k).S(i)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,i); % % Determine whether the load at point I is less than the maximum load of the vehicle and whether the time to reach point I is within the time window required by point I %if WaterDrop(k).Q(i)<Qmax && WaterDrop(k).S(i)>=E(i) && WaterDrop(k).S(i)<=L(i)
% WaterDrop(k).FK=[WaterDrop(k).FK,i];
% end
% end
% end
if isempty(WaterDrop(k).FK)
WaterDrop(k).Target=1;
else% Calculate the probability of reaching the next serviceable demand point % Determine whether the minimum amount of soil on the path from source(k) to the next serviceable demand point is less than0
Minsoil=0;
for u=1:length(WaterDrop(k).FK)
ifWaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u))<Minsoil Minsoil=WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u)); End end % Calculate the sum of the function f corresponding to the next service demand point (can increase improvement, adjust the node selection probability) SumF=0;
for u=1:length(WaterDrop(k).FK)
g(WaterDrop(k).Source,WaterDrop(k).FK(u))=WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u))-Minsoil;
f(WaterDrop(k).Source,WaterDrop(k).FK(u))=1/ (0.01+g(WaterDrop(k).Source,WaterDrop(k).FK(u))); SumF=SumF+f(WaterDrop(k).Source,WaterDrop(k).FK(u)); End % Find the probability corresponding to service demand point P=[]; U=[];for u=1:length(WaterDrop(k).FK) P=[P,f(WaterDrop(k).Source,WaterDrop(k).FK(u))/SumF]; U=[U,WaterDrop(k).FK(u)]; WaterDrop(k).Target= u (RoutedGame(P)); WaterDrop(k). Vel=WaterDrop(k).vel +av/(bv+ CV *WaterDrop(k).sw (WaterDrop(k).source,WaterDrop(k).target)^2); Maxtime=max(epsilon,WaterDrop(k).Vel); % TT(WaterDrop(k).source,WaterDrop(k).target)=D(WaterDrop(k).source,WaterDrop(k).target)/Maxtime; DeltaSW(WaterDrop(k).source,WaterDrop(k).target)= as/(bs+cs*TT(WaterDrop(k).source,WaterDrop(k).target)^2); WaterDrop(k).sw (WaterDrop(k).source,WaterDrop(k).target)=... (1-alpha)*WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).Target)-alpha*DeltaSW(WaterDrop(k).Source,WaterDrop(k).Target); WaterDrop(k).soil =WaterDrop(k).soil +DeltaSW(WaterDrop(k).source,WaterDrop(k).target); Penalty coefficient % cfe1=0;
% cfe2=0;
% cfe0=0; WaterDrop(k).S(WaterDrop(k).Target)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,Wa terDrop(k).Target); %if WaterDrop(k).S(WaterDrop(k).Target)<E
% cfe1=EP(WaterDrop(k).Target)*abs(E-WaterDrop(k).Target);
% elseif WaterDrop(k).S(WaterDrop(k).Target)>L
% cfe1=LP(WaterDrop(k).Target)*abs(WaterDrop(k).Target-L);
% end
% cfe0=cfe1+cfe2;
if WaterDrop(k).Target= =1% (Ordered collection) Distribution vehicle returns to the distribution center WaterDrop(k).visitNode =[WaterDrop(k).visitnode,WaterDrop(k).target]; % added the fixed cost of using one vehicle to the objective function (represents the loop formed for one vehicle) WaterDrop(k).ZZ=WaterDrop(k).ZZ+h*D(WaterDrop(k).Source,WaterDrop(k).Target)+D(WaterDrop(k).Source,WaterDrop(k).Target)* (R0+R1*(q(WaterDrop(k).Target)))+R; WaterDrop(k).Source=WaterDrop(k).Target; WaterDrop(k).Q(WaterDrop(k).Source)=0;
WaterDrop(k).S(WaterDrop(k).Source)=0;
else% Access Target(k) point, access point increased1A WaterDrop (k). VisitNode = [WaterDrop (k) VisitNode, WaterDrop (k). The Target]; % Drop a WaterDrop(k).UnvisitNode(WaterDrop(k).unvisitNode ==WaterDrop(k).target)=[]; %%%%%？？？？？ % Objective function only increases vehicle operating costs WaterDrop(k).ZZ=WaterDrop(k).ZZ+h*D(WaterDrop(k).Source,WaterDrop(k).Target)+D(WaterDrop(k).Source,WaterDrop(k).Target)* (R0+R1*(q(WaterDrop(k).Target))); WaterDrop(k).q (WaterDrop(k).target)=WaterDrop(k).q (WaterDrop(k).source)+ Q(WaterDrop(k).target); WaterDrop(k).s (WaterDrop(k).target)=WaterDrop(k).s (WaterDrop(k).source)+... ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,WaterDrop(k).Target); WaterDrop(k).source =WaterDrop(k).target; End % If the path of the KTH droplet has been completed (i.e. all demand points have been serviced)end
if WaterDrop(k).ZZ<Z
Z=WaterDrop(k).ZZ; Route=WaterDrop(k).VisitNode; Soil=WaterDrop(k).Soil; M=size(Route,2); The amount of soil outside the path remains unchanged.for i=1:M- 1
W(Route(i),Route(i+1)) = (1+beta)* W(Route(i),Route(i+1))-beta*Soil/(M- 1); End % Number of update iterations t=t+1;
end
TotalZ
TotalRoute
LL
DrawPath(TotalRoute,position); % iteration figure x=1:1:Iter;
y=bestZ;
plot(x,y,'r--')
%plot(x,y);
hold on
%plot(x,y1,'r--'); % adaptation average title('Optimization process')
xlabel('Number of iterations')
ylabel('Optimal fitness')
axis([0,Iter,500.1200])
Copy the code3. 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.