Fish School Search. Fish School Search (FSS), proposed by Bastos Filho and Lima Neto in 2008 is, in its basic version, a unimodal optimization algorithm inspired by 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 have more influence on the search process as a whole, which makes the barycenter of the fish school move toward optima in the search space over successive iterations.

The FSS uses the following principles: 
 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 -dimensional location represents a possible solution for the optimization problem. The algorithm makes use of weights for all the fishes which represents cumulative 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:

where  and  represent the position of the fish  before and after the individual movement operator, respectively.  is a uniformly distributed random number varying from -1 up to 1 and  is a parameter that defines the maximum displacement for this movement. The new position  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 .

Collective-instinctive component of the movement
An average of the individual movements is calculated based on the following:

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

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  of the school is calculated based on the position  and the weight  of each fish:

and then, if the total school weight  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:

Eq. B:

where  defines the size of the maximum displacement performed with the use of this operator.  is the euclidean distance between the fish  position and the school barycenter.   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:

where  is the weight parameter for fish ,  is the fitness variation between the last and the new position, and  represents the maximum absolute value of the fitness variation among all the fishes in the school.
 is only allowed to vary from 1 up to , which is a user defined attribute. The weights of all fishes are initialized with the value .

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  and  decay linearly according to:

and similarly:

where  and  are user defined initial values for  and , respectively.  is the maximum number of iterations allowed in the search process.

Variations of FSS

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  for which 0 <=  <= 1 in the individual component of the movement.  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  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.

See also

 Ant colony optimization algorithms
 Artificial bee colony algorithm
 Particle swarm optimization

References

Nature-inspired metaheuristics