Operators and Functioning of FSS(Delivered Versions) from CIRG @ POLI/UPE
Version 1.0 – FSS (Vanilla Version)
General Definitions
-Aquarium: the hyper dimensional search space
-Fish (individual): a candidate solution for the optimization; they all have a Weight (W) and a Position (X)
-Food (concentration): the metaphor for guiding fish to “good” regions of the aquarium
-Swimming: an operator composed of three movements that are vectorially composed before the actual move
-Feeding: the operator that updates the fish weight according to the quality of motion (i.e. after swimming)
Operators
– Individual movement:
Every fish in the school performs a local search looking for promising regions in the search space. It is done as represented below:
[latex]\vec { x } \left( t+1 \right) =\vec { x } \left( t \right) +U(-1,1){ step }_{ ind }(t)\\ \\step_{ ind }(t+1)=step_{ ind }(t)-\frac { (step_{ ind\quad inicial }-step_{ ind\quad final }) }{ interations } [/latex]
where [latex]\vec { x } \left( t \right)[/latex] and [latex]\vec { x } \left( t+1 \right)[/latex] represent the position of the fish [latex] i [/latex] before and after the individual movement operator, respectively. [latex]U(-1,1)[/latex] is a uniformly distributed random number varying from -1 up to 1 and [latex]{ step }_{ ind }(t)[/latex] is a parameter that defines the maximum displacement for this movement. The new position [latex]\vec { x } \left( t+1 \right)[/latex] is only accepted if the fitness of the fish improves with the position change. If it is not the case, the fish remains in the same position and [latex]\vec { x } \left( t+1 \right) =\vec { x } \left( t \right)[/latex] and [latex]interations[/latex] is the number of interations used in the simulation.
– Feeding: (1.1)
The feeding operator is used in order to update the weights of every fish according to:
[latex]W(t+1)=W(t)+\cfrac { \Delta f }{ max(\left| \Delta f \right| ) } \\ \\ \Delta f=f\left[ \vec { x } (t) \right] -f\left[ \vec { x } (t-1) \right]\\ \\ [/latex]
Where [latex] W(t) [/latex] is the weight parameter for fish [latex] i [/latex], [latex] \Delta f [/latex] is the fitness variation between the last and the new position, and [latex] max(\left| \Delta f \right|) [/latex] represents the maximum absolute value of the fitness variation among all the fishes in the school. It is important to create a variable [latex](w\_scale)[/latex] to limit the weight of the fish, through tests it has been seen to be an important variable.
– Collective-instinctive movement: (1.2)
An average of the individual movements is calculated based on the following:
[latex]\vec { I } (t)=\cfrac { \sum _{ i=1 }^{ N }{ { \vec { \Delta x } }_{ i } } { { \Delta f }_{ i } } }{ \sum _{ i=1 }^{ N }{ { \Delta f }_{ i } } } \\ \\ \Delta \vec { x } =\vec { x } (t)-\vec { x } (t-1).[/latex]
The vector [latex] I [/latex] represents the weighted average of the displacements of each fish. It means that the fishes that experienced a higher improvement will attract fishes into its position. After the vector [latex] i [/latex] computation, every fish will be encouraged to move according to:
[latex] \vec { x } (t+1)=\vec { x } (t)+\vec { I } (t) .[/latex]
– Barycenter: (1.3)
the barycenter [latex]\vec { B } \left( t \right)[/latex] of the school is calculated based on the position [latex]{\vec { x } }_{ i } [/latex] and the weight [latex] { W_{ i }(t) } [/latex] of each fish:
[latex]\vec { B } \left( t \right) =\cfrac { \sum _{ i=1 }^{ N }{ { \vec { x } }_{ i } } { { W }_{ i }(t) } }{ \sum _{ i=1 }^{ N }{ W_{ i }(t) } } [/latex]
– Collective-volitive movement: (1.4 and 1.5)
The Collective-volitive movement is used in order to regulate the exploration/exploitation ability of the school during the search process.
[latex]\vec { x } \left( t+1 \right) =\vec { x } \left( t \right) +{ step }_{ vol }U(0,1)\cfrac { (\vec { { x } } (t)-\vec { B } (t)) }{ DE(\vec { { x } } (t),\vec { B } (t)) } \\ \\ \vec { x } \left( t+1 \right) =\vec { x } \left( t \right) -{ step }_{ vol }U(0,1)\cfrac { (\vec { { x } } (t)-\vec { B } (t)) }{ DE(\vec { { x } } (t),\vec { B } (t)) } \\ \\ \quad step_{ vol }(t+1)=step_{ vol }(t)-\frac { (step_{ vol\quad inicial }-step_{ vol\quad final }) }{ interations } [/latex]
where [latex] { step }_{ vol } [/latex] defines the size of the maximum displacement performed with the use of this operator. It is recommended to place the [latex] { step }_{ vol } [/latex] as the double of the [latex] { step }_{ ind} [/latex] . [latex] DE(\vec { { x } } (t),\vec { B } (t)) [/latex] is the euclidean distance between the fish [latex] i [/latex] position and the school barycenter and [latex] U(0,1) [/latex] is a uniformly distributed random number varying from 0 up to 1.
Pseudocode
1. Initialize fishes in the swarm
2. While maximum iterations or stop criteria is not attained do
3. for each fish i in the swarm do
a. update position applying the individual operator
[latex] \quad \quad \quad \quad \quad \vec { x } \left( t+1 \right) =\vec { x } \left( t \right) +U(-1,1){ step }_{ ind }(t)\quad \quad { \overrightarrow { temp } }_{ i }={ x }_{ i }(t)+{ \Delta x }_{ i }(t+1)[/latex]
calculate fish fitness [latex]{ f }_{ i }{ (\overrightarrow { temp } }_{ i })[/latex]
if [latex]{ f }{ (\overrightarrow { temp } }_{ i })<f({ x }_{ i }(t))[/latex]
[latex]\quad \quad \quad \quad \quad { x }_{ i }(t+1)={ \overrightarrow { temp } }_{ i }, \quad \quad \quad { f }_{ i }^{ (t+1) }={ f }_{ i }{ (\overrightarrow { temp } }_{ i })[/latex]
else
[latex]{ x }_{ i }(t+1)={ x }_{ i }(t),\quad \quad \quad \quad { f }_{ i }^{ (t+1) }={ f }_{ i }^{ (t) }[/latex]
b. apply feeding operator
update fish weight according to 1.1
c. apply collective-instinctive movement
update fish position according to 1.2
d. apply collective-volitive movement
if overall weight of the school increases in the cycle update fish position using 1.4
elseif overall weight of the school decreases in the cycle update fish position using 1.5
end for decrease the individual and volitive steps linearly
end while
A nice presentation explaining FSS operators and beyond (click to dowload)