Transcript Bacterial Foraging Optimization

Bacterial Foraging
Optimization
Presented by: Adia Khalid
PhD (Scholar)
Home Energy Optimization in Smart Grid
Supervised by: Dr. Nadeem Javaid
1
Agenda
Introduction
Bacterial Foraging Algorithm
Home Energy Management
2
Introduction (1\4)
Natural selection method
Food Source
• eliminate animals with poor “foraging strategies”
Foraging strategies
• methods for locating, handling, and ingesting food
Food Quality
• favor those animals that have
• successful foraging strategies
Food Capturing
• obtain enough food to enable them to reproduce
• after many generations poor foraging strategies are:
• either eliminated or
• shaped into good ones i.e.. Redesigned
such evolutionary principles have led scientists in the field of “foraging
theory” to hypothesize
• it is appropriate to model the activity of foraging as an optimization
process
Passino, K. M. (2002). Biomimicry of bacterial foraging for distributed
optimization and control. IEEE control systems, 22(3), 52-67.
3
Digesting Food
Introduction (2\4)
A foraging animal main focus:
• maximize the energy obtained per unit time spent foraging
• In the face of constraints presented by its own
• physiology
Foraging focus
Energy
Maximization
• e.g., sensing and cognitive capabilities
• environment
Evolution has balanced these constraints
• sometimes referred to as
• optimal foraging policy
• such terminology is especially justified in case
• where the models and policies have been ecologically
validated
Passino, K. M. (2002). Biomimicry of bacterial foraging for distributed
optimization and control. IEEE control systems, 22(3), 52-67.
4
Constraints
• e.g., density of prey, risks from predators, physical characteristics of
the search area
o Physiology
o Environment
Introduction (3\4)
Optimal Foraging:
• Optimal foraging theory formulates the foraging
problem as an optimization problem.
• Optimization models valid for social foraging
• where groups of animals cooperatively forage
• Here, we explain the biology and physics underlying the
chemotactic (foraging) behavior of
•
E.coli bacteria for optimization named as Bacterial Foraging
Optimization
• Individual bacterium also communicates with others by
sending signals
• During foraging of a real bacteria two basic operations
• Swim
• Tumble
• performed by a bacterium at the time of foraging by
http://wikis.swarthmore.edu/mathbio/index.php?title=File:Optim
al_Foraging_Theory.jpg&limit=50
• a set of tensile flagella
Passino, K. M. (2002). Biomimicry of bacterial foraging for distributed
optimization and control. IEEE control systems, 22(3), 52-67.
5
Introduction (4\4)
E.coli bacteria:
• the ones that are living in our intestines
Structure
• Diameter: 1μm
• Length: 2μm
• Flagellum:
• Chemotaxes
• movement in the presence of
• chemical attractants and
repellants
• Counterclockwise:
• Swim
• Clockwise:
• Tumble
Bactria chemotactic
Movement
6
Bacterial Foraging Algorithm (1\2)
Reproduction:
Chemotaxis:
When a bacterium meets a favorable environment (rich in After calculating fitness value for each bacteria,
• reproduction allows the bacteria to survive and
nutrients and noxious free),
reproduce
• it will continuous swimming in the same direction,
if nutrient increase in the direction of swim
tumble
run
run
when it meets an unfavorable environment,
•
it will tumble, i.e., change the direction of swim
tumble
run
tumble
Elimination and dispersal:
Swarming:
E. Coli bacterium has a specific sensing actuation and The chemotaxis provides a basis for local search
and reproduction speeds the convergence
decision making mechanism
• To avoid trap bacteria in local minimum
• On each move
•
It releases attracts to signal other bacteria to swarm towards its
7
• Elimination-Dispersal is done
Bacterial Foraging Algorithm (2\2)
The algorithm models bacterial
• Population: {i ϵ pop, where pop have 1:Np elements}
• Chemotaxis: {for j=1:Nc elements}
• Swarming: {for s=1:Ns elements}
• Reproduction: {for k=1:Nr elements}
• Elimination and Dispersal Steps: {for l=1:Ne step}
• Another parameter
• C: Step Size for the dimension
 i  j  1, k , l    i  j , k , l   C i 
J
i
health

dlt i 
dlt T i dlt i 
N c 1
 J i, j, k , l 
j 1


J (i, j , k , l )  J (i, j , k , l )  J cc  i  j , k , l , P  j , k , l 
d 1

J cc   100( i i, d  1  ( i i, d ) 2 ) 2  ( i i, d   1) 2
d 1
8

Home Energy Management (1/10)
BFA Mapping on Home Energy Management (HEM)
Target: We have to optimize the energy usage
• By scheduling the home appliances
• Pass the on-peak hour load on off-peak hour
Ji
health
9
Home Energy Management (2/10)
BFA Mapping on Home Energy Management (HEM)
Optimal Solution get form optimal search space
 Search space
 Population of group of bacteria's
BFA Parameters
HEM Parameters
Values
Population
Possible solution
30
Bactrians with in a swarm
Appliances
9
Bacterium status i.e. dead or alive
Appliance’s ON or OFF status
1 or 0
Elimination steps
Schedule
24 hour
Min (Cost)
vary
i
Fitness Level i.e. min(J health )
Cost depend on the power rate of an appliance and
price signals
10
Home Energy Management (3/10)
Peak Load Reduction
Meter
• Demand Response
• encourage the user to make changes in their demand
according to the price signals
Smart meter
Bulk meter
Implementation is possibly implemented using some energy
measuring consumption measuring meters:
• Bulk meter just save information with a single bulk
Flat rate
Tiered rate
Time based rate
• Smart meter record electricity usage information
frequently
Pricing schemes:
•Flat Rates - same rate during a given period of time
•E.g., 30-day bill cycle
•Tiered Rates - charge a different price based on blocks of usage
•e.g., first 500 kWh vs. next 500 kWh for 30-day billing cycle
•Time-based rate includes- Dynamic Rate and Time of Use
Dynamic
RTP
CPP
VPP
TOU
CPR
(TOU)
Dynamic Rate [*]
Real Time Price (RTP)
Critical Peak Pricing (CPP)
Curtailable/Interruptible (C/I)
Variable Peak Pricing (VPP)
Critical Peak Rebate (CPR)
11
[*]. Waterloo North Hydro, https://www.wnhydro.com/en/your-home/timeof-use-rates.asp. Last visited: 20 May 2016.
C/I rate
Home Energy Management (4/10)
TOU
20
18
Pricing Scheme[*]
16
14
• TOU: Prices set for the on-peak and off-peak hours,
12
10
• where hours divided into blocks and price for a particular block remain fixed
• RTP: Rates tariff based on the hourly bases usage of electricity
8
6
4
2
• Utilities regulates RTP in two parts
1) Base bill
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
calculated on the bases of define tariff for particular customer depend on
• customer baseline load (CBL)
2) Hourly prices apply according to the customer usage
RTP
30
25
• that is a difference between actual and CBL
20
𝑃𝑟𝑖𝑐𝑒 𝑈𝑛𝑖𝑡 ,
𝑖𝑓 𝐿𝑜𝑎𝑑 ≤ 𝑙𝑖𝑚𝑖𝑡
𝑅𝑇𝑃 =
……………….. (1)
𝑃𝑟𝑖𝑐𝑒 𝑈𝑛𝑖𝑡 + 𝐸𝑥𝑡𝑟𝑎𝑐ℎ𝑎𝑟𝑔𝑒 , 𝑖𝑓 𝐿𝑜𝑎𝑑 > 𝑙𝑖𝑚𝑖𝑡
• The C/I Option: Specifies conditions under which disturbance in service may occur
• A customer gives right to the Local Distribution Company (LDC) during the contract
• not the obligation to disturb the services
• In such situation LDC pays incentive to the customers through bill
reduction
12
15
10
5
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
[*]. Waterloo North Hydro, https://www.wnhydro.com/en/your-home/timeof-use-rates.asp. Last visited: 20 May 2016.
Home Energy Management (5/10)
Pricing Scheme[*]
• VPP: hybrid TOU and RTP
𝑜𝑛_𝑃𝑒𝑎𝑘
𝑉𝑃𝑃𝑡𝑜𝑡𝑎𝑙 = 𝑉𝑃𝑃ℎ𝑜𝑢𝑟
𝑜𝑓𝑓_𝑃𝑒𝑎𝑘
𝑉𝑃𝑃ℎ𝑜𝑢𝑟
= 𝑇𝑂𝑈
𝑜𝑛_𝑃𝑒𝑎𝑘
𝑉𝑃𝑃ℎ𝑜𝑢𝑟
= 𝑅𝑇𝑃
+
𝑜𝑓𝑓_𝑃𝑒𝑎𝑘
𝑉𝑃𝑃ℎ𝑜𝑢𝑟
CPP
……………. (2)
140
120
……………...(2a)
100
……………...(2b)
80
• CPP: Critical events may call during the specific period
60
40
• utilities observe high market price rate or during the power system emergency20
conditions
0
• Usually occur in hot summer weekdays
• Allow only 15 time per year
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
• CPR: During the critical event utilities increases the price for the specific time duration
• refunded it to customer
• when utilities observe any reduction in consumption
13
[*]. Waterloo North Hydro, https://www.wnhydro.com/en/your-home/timeof-use-rates.asp. Last visited: 20 May 2016.
Home Energy Management (6/10)
BFA Matlab Code
Fitness
Evolution
Bacterium\ Appliances
Vacuum
Cleaner
Water
Heater
Water
Pump
Dish
Washer
Refrigerator
AC
Oven
Washing
Machine
Cloth
Dryer
Jlast
1
0
0
1
0
1
1
1
1
101
0
1
1
1
1
0
0
0
0
100
1
1
1
1
1
0
0
1
1
99
1
0
1
1
0
0
1
1
0
100
for i=1:NP %
for j=1:D-1
if rand(1)>0.6
X=1;
else
X=0;
end
J(i)=sum(100*(x(k,j+1)-x(i,j)^2)^2+(x(i,j)-1)^2); % initial
fitness calculation
end
end
14
Home Energy Management (7/10)
BFA Matlab Code
Fitness
Evolution
Bacterium\ Appliances
Vacuum
Cleaner
Water
Heater
Water
Pump
Dish
Washer
Refrigerator
AC
Oven
Washing
Machine
Cloth
Dryer
J
0
1
0
0
0
1
1
0
0
100
1
1
1
0
0
1
1
1
0
110
1
1
0
1
1
1
0
1
0
106
0
0
1
0
1
0
1
0
0
105
for l=1:Ne % 24 l=elimination of dispersal step
for k=1:Nr % 4 k=reproduction
for j=1:Nc % 3 Chemotaxis Loop %
for i=1:Np % 4 Take a chemotaxis Step
del=(rand(1,D)-0.5)*2;
x(i,:)=x(i,:)+(C/sqrt(del*del'))*del; % C=
0.4 %Direction of Tumble i.e. new position of bacterium
for d=1:D-1
J(i)=sum(100*(x(i,d+1)-x(i,d)^2)^2+(x(i,d)-1)^2); %Fitness Evalutin
15
end
Home Energy Management (8/10)
BFA Matlab Code
Fitness
Evolution
Bacterium\ Appliances
Vacuum
Cleaner
Water
Heater
Water
Pump
Dish
Washer
Refrigerator
AC
Oven
Washing
Machine
Cloth
Dryer
Jlast
0
0
0
1
0
0
1
1
1
100
1
1
0
0
0
1
1
0
1
110
1
1
0
1
1
1
0
1
0
106
0
0
1
0
1
0
1
0
0
105
Updated the
bacterium\ appliances
status
for m=1:Ns % 2 swimming Step
if J(i)<Jlast(i)%Elimination and Dispersal Check
Jlast(i)=J(i);
x(i,:)=x(i,:)+C*(del/sqrt(del*del')); %Direction of Tumble i.e. new position of bacterium
for d=1:D-1
J(i)=sum(100*(x(i,d+1)-x(i,d)^2)^2+(x(i,d)-1)^2); %Fitness Function
end
else del=(rand(1,D)-0.5)*2;%Vector with random Direction
x(i,:)=x(i,:)+C*(del/sqrt(del*del'));
for d=1:D-1
J(i)=sum(100*(x(i,d+1)-x(i,d)^2)^2+(x(i,d)-1)^2);
end
end
end % end swimming
Step
16
end % end of bacterial population
Home Energy Management (9/10)
BFA Matlab Code
Cost
Bacterium\ Appliances
Vacuum
Cleaner
Water
Heater
Water
Pump
Dish
Washer
Refrigerator
AC
Oven
Washing
Machine
Cloth
Dryer
Cost_B
(cent)
0
0
0
1
0
0
1
1
1
48
1
1
0
0
0
1
1
0
1
30
1
1
0
1
1
1
0
1
0
45
0
0
1
0
1
0
1
0
0
50
end
for i=1:Np %% Check the Health
Cost_B(i)= min(Cost); % power_Rate * Electricity_Price
end
% end of reproduction step
17
Minimum cost will be
selected
Home Energy Management (10/10)
BFA Matlab Code
Fitness
Evolution
Bacterium\ Appliances
Vacuum
Cleaner
Water
Heater
Water
Pump
Dish
Washer
Refrigerator
AC
Oven
Washing
Machine
Cloth
Dryer
J
1
1
0
1
0
1
1
1
0
103
1
0
0
1
0
0
1
0
1
106
0
1
0
1
0
1
0
1
1
100
0
1
1
1
1
0
0
0
0
109
%% random elimination dispersion
for j=1:Np
for i=1:D
if rand(1)>=Ped
x(j,i)=1;
else
x(j,i)=0;
end
for d=1:D-1
J(i)=sum(100*(x(i,d+1)-x(i,d)^2)^2+(x(i,d)-1)^2);
end
end
end
18
end
19