Population algorithm based on fish school behavior

Within this community, genetic algorithms and their application in practice have been repeatedly discussed. In this article, I would like to share a relatively new method of optimizing functions based on the behavior of the school of fish in terms of food search.

Introduction

Since the middle of the last century, studies have been conducted on the simulation of the biological mechanisms of nature, in particular, related to the evolution process. Only by the 1980s did practical tests of these methods begin due to the need for effective ways to optimize n-ary functions that have high computational complexity, multi-extremes, etc. Speaking about terminology, it is worth mentioning that these algorithms belong to the class of stochastic search engines. In many sources one can also find such definitions as behavioral, intellectual, metaheuristic, or population . We will use the last term for the classification of our algorithm. Generally speaking, this algorithm can be determined more precisely using the following scheme.

Population algorithms are divided into the following categories:

• Evolutionary algorithms, including those genetic ones.
• Algorithms inspired by wildlife (for example, an algorithm for optimizing a swarm of fireflies, kukushkin search, etc.).
• Algorithms inspired by inanimate nature (for example, the gravitational search algorithm).
• Algorithms based on the behavior of human society (for example, the algorithm of evolution of the mind).
• Other algorithms.

Having dealt with the terminology, we proceed directly to the study of a population optimization algorithm based on the behavior of a school of fish.
')

Parsing algorithm

This algorithm was proposed in 2008 by Philo (B. Filho) and Neto (L. Neto).
As in all population algorithms, the following parameters are specified as input parameters: the fitness function (a function for which it is necessary to find extremes), the field of study of this function, and the parameters of the algorithm (about them later). In the current FSS algorithm ( F ish S chool S earch), the search area is an aquarium in which agents (fish) swim. As you know, in the conditions of the search for food, fish swim in a joint, therefore, in our case, the ultimate goal is the displacement of all agents to the area of ​​extremum of function. In general, the algorithm of the algorithm is as follows:

1. Initialization of the population (uniform distribution of fish in the aquarium)
2. Migration of agents to the food source (analogy: the greater the step agents performed in the direction of the extremum of the function, the more food they received)
3. Finishing the search

Need more details

The “Migration of agents” stage is performed iteratively, and in each of the iterations, the operators of two groups are executed:

1. Swimming operators that enable the migration of agents within the aquarium.
2. Feeding operators, fixing the success of the study of various areas of the aquarium.

It is time to talk about the parameters that the aquarium has, and its inhabitants.
So, we introduce the following variables, characteristic for the whole aquarium:
populationSize size - populationSize size (the number of fish in the school).
iterationCount - the number of iterations in the "Migration Agents" stage
lowerBoundPoint, higherBoundPoint - upper and lower search boundaries
individStepStart, individStepFinal - sets the initial and final radius of the search for food around agents
weightScale - the maximum weight of the agent.
These are the very parameters that the user enters. With their help, the ratio of the accuracy / time of the algorithm is adjusted.
The agents themselves are characterized by only two quantities:
swimStatePos - the position of the agent in different stages of swimming
weight - the current weight of the agent

Of course, with the software implementation of the algorithm in such a number of variables, it is obviously not enough, but for the time being we will not complicate our life .

Realizing that code is more important to programmers than empty chatter, we will delve into the algorithm using the following pseudo-code:

 initialize_randomly_all_fish; while (stop_criterion is not met) { for (each_fish) { individual_movement; evaluate_fitness_function; } feeding_operator; for (each_fish) instinctive_movement; calculate_barycentre; for (each_fish) do { volitive_movement; evaluate_fitness_function; } update_individidual_step; } 

Note: all the following explanations of the algorithm are designed for solving the problem of conditional function maximization, however, this should not raise doubts about the inoperability of this method when searching for minimum values ​​of a function.

1. So, as already mentioned, the first step is to initialize the entire population: randomly selecting the position of the agent within the aquarium ( swimStatePos[0] ) and setting a weight equal to half the maximum ( weight=weightScale/2 ) for all fish.
2. Then the main cycle of the algorithm begins, which characterizes the stage “Migration of agents to the food source”. In our case, the “Number of iterations” value ( iterationCount ) is used as a stopping criterion.
3. Then comes the individual stage of swimming agents. It is characterized by the fact that all fish in some area around themselves ( individStep ) are trying to find the best value of the function.
   If they succeed, then this step is fixed. Otherwise
   
   We believe that this movement was not.
4. Now you need to consolidate success in the individual stages of swimming. To do this, use the characteristic "Weight". It is equal to the change in the function of fitness for a given agent before and after the individual stage, normalized by the maximum change in function among the population: . Generally speaking, this is a distinctive feature of this algorithm, since we do not need to memorize the best agents in previous iterations.
5. After this, the fish perform the next stage of swimming - instinctive-collective. For the whole school of fish, the “Total migration step” value is calculated: .
   Its meaning is as follows: the entire population as a whole influences each agent, and the influence of an individual agent is proportional to its success in the individual swimming stage. Then the entire population is shifted by the calculated value of m:
   
   
6. Before the next swimming operation it is necessary to perform intermediate actions, namely: calculate the center of gravity of the whole jamb: .
7. We, or rather, fish, moved to the last stage of swimming: collective-willed. Here it is necessary to find out how the weight of the population has changed compared to the previous iteration. If it has increased, then the population has approached the area of ​​maximum function, therefore it is necessary to narrow the range of its search, thereby showing intensification properties. And vice versa: if the weight of the shoal has decreased, then the agents are looking for the maximum in the wrong place, therefore it is necessary to change the direction of the trajectory and show diversification properties.
   
   The value of collStep in the following formula is responsible for the step of volitional displacement. It is recommended to use a value that is 2 times larger than an individual search step. The dist operator calculates the distance between two points in a Euclidean space.
   
   ( The values ​​responsible for the position of agents are structural types of an n-dimensional point, for which the following operations are defined: add / subtract two points, add / subtract a point and a number, multiply / divide a point and a number, and compare points. To avoid of this geometric nonsense, it is considered to be considered as given for vector data types, having added some operations )
8. The last operator in the iteration is a linear decrease in the step of the individual search for the next iteration. In fact, this is already a modification of the standard FSS algorithm to increase search efficiency, which is performed according to the following formula:

Implementation and testing

Implementation

This algorithm formed the basis of my coursework (“Optimization program inspired by the fish school behavior”), which was presented at the defense on April 26th. Perhaps someone will be interested in why they passed their course papers so early. Without further ado, I can only say that this is all part of the plan for expelling students from the 1st year at the Faculty of Biotechnology (UI department) of the National Research University Higher School of Economics, who found themselves in the paws of the academic section, threatening the whole year with 30% deduction (on the reverse side of the coin The campaign slogan adorns: “We will accept everyone, and if necessary we will pay for the places at our own expense”). As part of the coursework project, the implementation was conducted in C # 4.0, the OpenTK library was selected as the graphic component (it represents the OpenGL wrapper for .NET), the user-defined functions were parsed using the library implemented in the Habré earlier . Unfortunately, I can’t upload the source code (the code is far from perfect, I realized this many times myself), but I’ll give the program itself to everyone’s discretion (links at the end of the article). For now, just a screenshot of the main window:

Testing

For population-based algorithms, testing is a fascinating thing, because the result of its work largely depends on the input parameters. In this article, we consider the following 2 graphs.

1. 
   
   • Search area: from (-100; -100) to (100; 100)
   • Number of iterations: 100
   • Population size: 50
   • Initial individual step: 10
   • Final individual step: 0.1
   • Maximum fish weight: 50
   
   So, by the end of the algorithm, the maximum value of the function was 9.999978 ..., and the average value of 9.999148 ... The graph of the change in the average value is as follows:
   
   That is, at the 15th iteration, the school of fish was in the positive half-plane along the axis OY. And since the 48th iteration, the average value of the function did not fall below 9. And here is the full picture of what is happening (view from the tip of the iceberg):
   
   
   
2. 
   
   • Search area: from (-100; -100) to (100; 100)
   • Number of iterations: 100
   • Population size: 50
   • Initial individual step: 10
   • Final individual step: 0.1
   • Maximum fish weight: 50
   
   
   By the end of the algorithm, the maximum value of the function was 19.999996 ..., and the average was 19.9994 ... The dynamics of the average value is as follows:
   
   
   Already with 42 iterations, the average value of the function was kept at a level not lower than 19. Animation of how the algorithm copes with multi-extremal functions (for Habrastorage, the file is too large, so there may be problems with displaying the image):
   

Sources

• You can download the program here (the kit includes: a program for studying functions from two variables with function reports from this article, a console version of the program with built-in functions from N variables, a description of the language for setting fitness functions (according to GOST, by the way))
• Perhaps the only Russian-language article that describes this algorithm: A. P. Karpenko. “Population Algorithms for Global Search Engine Optimization. Overview of new and little-known algorithms. Download .
• A website entirely dedicated to Fish School Search
• And another useful article in English
• Sources of the console version of the program (you can fork)

PS

Thanks for reading the article! We are happy to answer your questions in the comments.

UPD: Added source codes.