Fish School Search - Alchetron, The Free Social Encyclopedia

Fish School Search (FSS), proposed by Bastos Filho and Lima Neto in 2007 is, in its basic version, an unimodal optimization algorithm inspired on the collective behavior of fish schools. The mechanisms of feeding and coordinated movement were used as inspiration to create the search operators. The core idea is to make the fishes “swim” toward the positive gradient in order to “eat” and “gain weight”. Collectively, the heavier fishes are more influent in the search process as a whole, what makes the barycenter of the fish school moves toward better places in the search space over the iterations.

Simple computations in all individuals (i.e. fish)
Various means of storing information (i.e. weights of fish and school barycenter)
Local computations (i.e. swimming is composed of distinct components)
Low communications between neighboring individuals (i.e. fish are to think local but also be socially aware)
Minimum centralized control (mainly for self-controlling of the school radius)
Some distinct diversity mechanisms (this to avoid undesirable flocking behavior)
Scalability (in terms of complexity of the optimization/search tasks)
Autonomy (i.e. ability to self-control functioning)

Algorithm

FSS is a population based search algorithm inspired in the behavior of swimming fishes that expand and contract while looking for food. Each fish n -dimensional location represents a possible solution for the optimization problem. The algorithm makes use of weights for all the fishes which represents cummulative account on how successful has been the search for each fish in the school. FSS is composed of the feeding and movement operators, the latter being divided into three sub-components, which are:

Individual component of the movement

Every fish in the school performs a local search looking for promising regions in the search space. It is done as represented below:

x i ( t + 1 ) = x i ( t ) + r a n d ( − 1 , 1 ) s t e p i n d ,

where x i ( t ) and x i ( t + 1 ) represent the position of the fish i before and after the individual movement operator, respectively. r a n d ( − 1 , 1 ) is a uniformly distributed random number varying from -1 up to 1 and s t e p i n d is a parameter that defines the maximum displacement for this movement. The new position x i ( t + 1 ) 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 x i ( t + 1 ) = x i ( t ) .

Collective-instinctive component of the movement

An average of the individual movements is calculated based on the following:

I = ∑ i = 1 N Δ x i Δ f i ∑ i = 1 N Δ f i .

The vector I 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 I computation, every fish will be encouraged to move according to:

x i ( t + 1 ) = x i ( t ) + I .

Collective-volitive component of the movement

This operator is used in order to regulate the exploration/exploitation ability of the school during the search process. First of all, the barycenter B of the school is calculated based on the position x i and the weight W i of each fish:

B ( t ) = ∑ i = 1 N x i ( t ) W i ( t ) ∑ i = 1 N W i ( t ) ,

and then, if the total school weight ∑ i = 1 N W i has increased from the last to the current iteration, the fishes are attracted to the barycenter according to equation A. If the total school weight has not improved, the fishes are spread away from the barycenter according to equation B:

Eq. A:

x i ( t + 1 ) = x i ( t ) − s t e p v o l r a n d ( 0 , 1 ) x i ( t ) − B ( t ) d i s t a n c e ( x i ( t ) , B ( t ) ) ,

Eq. B:

x i ( t + 1 ) = x i ( t ) + s t e p v o l r a n d ( 0 , 1 ) x i ( t ) − B ( t ) d i s t a n c e ( x i ( t ) , B ( t ) ) ,

where s t e p v o l defines the size of the maximum displacement performed with the use of this operator. d i s t a n c e ( x i ( t ) , B ( t ) ) is the euclidean distance between the fish i position and the school barycenter. r a n d ( 0 , 1 ) is a uniformly distributed random number varying from 0 up to 1.

Besides the movement operators, it was also defined a feeding operator used in order to update the weights of every fish according to:

W i ( t + 1 ) = W i ( t ) + Δ f i m a x ( | Δ f i | ) ,

where W i ( t ) is the weight parameter for fish i , Δ f i is the fitness variation between the last and the new position, and m a x ( | Δ f i | ) represents the maximum absolute value of the fitness variation among all the fishes in the school. W is only allowed to vary from 1 up to W s c a l e / 2 , which is a user defined attribute. The weights of all fishes are initialized with the value W s c a l e / 2 .

The pseudo-code for FSS

Initialize user parameters
Initialize fishes positions randomly
while Stopping condition is not met do
Calculate fitness for each fish
Run individual operator movement
Calculate fitness for each fish
Run feeding operator
Run collective-instinctive movement operator
Run collective-volitive movement operator
end while

The parameters s t e p i n d and s t e p v o l decay linearly according to:

s t e p i n d ( t + 1 ) = s t e p i n d ( t ) − s t e p i n d ( i n i t i a l ) I t m a x ,

and similarly:

s t e p v o l ( t + 1 ) = s t e p v o l ( t ) − s t e p v o l ( i n i t i a l ) I t m a x ,

where s t e p i n d ( i n i t i a l ) and s t e p v o l ( i n i t i a l ) are user defined initial values for s t e p i n d and s t e p v o l , respectively. I t m a x is the maximum number of iterations allowed in the search process.

dFSS(Density based Fish School Search)

This version excels for multimodal hyper-dimensional functions. It includes modifications in the previous operators: Feeding and Swimming, as well as new: Memory and Partition operators. The latter two were introduced to account for the partition of the main school into subgroups. Some changes were also included in the stop conditions that now also have to consider subswarms.

wFSS(Weight based Fish School Search)

wFSS is a weight based niching version of FSS intended to produce multiple solutions. The niching strategy is based on a new operator called link formator. This operator is used to define leaders for the fishes in order to form sub-schools.

FSS-SAR(Stagnation Avoidance Routine Fish School Search)

In the original version of the algorithm, the individual movement component is only allowed to move a fish if it improves the fitness. However, in a very smooth search space, there would be many moving trials with no success and the algorithm could fail to converge. To solve these issues, was introduced a parameter X for which 0 <= X <= 1 in the individual component of the movement. X decays exponentially along with the iterations and measures a probability for a worsening allowance for each fish. It means that, every time a fish tries to move to a position that does not improve its fitness, a random number is chosen and if it is smaller than X the movement is allowed.

bFSS(Binary Fish School Search)

The bFSS intended to cope with premature convergence. Proposing the use of a binary encoding scheme for the internal mechanisms of the fish school search. It combined the FSS with fuzzy modeling in a wrapper approach for Feature Selection.

MOFSS(Multi-Objective Fish School Search)

In the MOFSS the operators are adapted to solve multi-objective problems. The algorithm deploys an External Archive to store the best non-dominated solutions found during the search process. This approach has been extensively used for different bio-inspired multiobjective optimizers. Furthermore, the solutions within the External Archive are used to guide the fish movements in the proposal version.

References

Fish School Search Wikipedia

(Text) CC BY-SA

Contents