Football Global Optimization Algorithms (Part 1)
Champions League Algorithm (League Championship Algorithm, LCA)
LCA is a stochastic population algorithm for continuous global optimization that simulates Europe's most prestigious club competition, in which artificial teams play in an artificial league over several weeks (iterations). In this algorithm, individual decisions are associated with teams. Each decision is interpreted as the current composition of the team. After a game between two teams, scheduled according to the league schedule, the suitability of each decision is assessed and SWOT analysiswhich results in a change in composition. New compositions are formed greedy algorithm and are retained only if their fitness level is not worse than the current one. To speed up the global convergence of the algorithm, there is an additional module for player transfers at the end of the season.
LCA models artificial primacy in the process of algorithm optimization based on some idealized rules:
– a team with greater game strength (the team's ability to defeat competitors) has a better chance of winning the game,
– a weaker team can win the game, but the chances of its victory are very small (the game strength determines the final result of the game with a probability less than one),
— the sum of the probabilities of victory of both teams participating in the match is equal to one,
– in the basic version of LCA the result of the game can only be a win or a loss (a draw is not allowed as an outcome of the game),
– Teams focus on the upcoming match, without taking into account future matches, and the team for the next round is formed only based on the results of the previous week.
The figure below shows an LCA flow chart that illustrates the optimization process of a basic LCA.
Golden Ball Algorithm (Golden Ball Algorithm, GBA)
GBA is a multi-population combinatorial optimization algorithm. In GBA, players are the solutions. They are assigned to different teams that make up a league. Teams compete against each other in matches, the results of which determine the process of exchanging players and coaches. At the beginning of the algorithm, an initial population is created and solutions (players) are randomly assigned to subsets of the system (teams). After the initial phase is complete, the first season begins. The season is divided into weeks during which teams practice and meet each other, competing in the league. When the season ends, a transfer phase begins during which players and coaches can be exchanged between teams. This process is repeated until the termination criterion is met.
It is logical to think that in the real world, the strength or power of each team is directly related to the quality of the players that make up its roster: the better the players, the stronger the team. So if one team is strong, it can win more games and get a better position in the league qualification.
The figure below shows the flow chart of this algorithm.
During the training phase, all players from each team improve. In real life, each team has its own training method. Some of these training methods are more effective than others. Therefore, some teams improve more than others. This fact is reflected in the league competition rankings, where teams that use more effective training are in a better position because their playing strength is greater than other teams and they can win more matches.
In the proposed methodology, each team has its own teaching method, expressed by some following function (successor function), which operates on a certain structure in the solution space. For example, for some routing problems, a function of this type may be the well-known 2-opt or 3-opt.
The training method is assigned randomly during the initialization process. For each training, this function is applied a certain number of times (until the termination criterion is reached). Different training functions affect each team differently. Because of this, the players of the teams also develop in a unique way, depending on the team they are in. This fact helps to explore and use the solution space more effectively, which is also enhanced by the fact that players can move from team to team.
It is important to note that the more times a function is applied, the more computational time is required. In addition, the fact that a function is applied more times does not mean better efficiency, since any player in any iteration can reach a local optimum. For this reason, as mentioned above, each training has its own termination criterion. Training ends when several players do not improve their performance after completing the next training iteration. Another type of training is individual training.
The transfer period is a process during which teams exchange players. In this way, all teams try to strengthen themselves by acquiring new players. In the world of football, this process happens every year. Usually, the best teams try to recruit the best players possible, while other teams have to settle for players of lower quality. In the algorithm, transfers depend on the team's position in the league. Teams in the top half of the standings are strengthened by the best players of the teams in the bottom half. While teams in the bottom half of the standings are satisfied with acquiring less good players from the weaker teams. It should be noted that the better the position of the team, the better the player it gets. That is, the best team gets the best player from the previous team in terms of ranking. Transfers help the search process because they allow different processing of solutions during execution, avoiding players getting into local optima and increasing the search power of the metaheuristic. In other words, this process of changing lineups improves the exploratory power of the method and, in particular, contributes to a wider use of promising areas of the solution space.
Another type of transfer is a downgrade. In the world of football, players change teams not only to join a better team and win more titles. Perhaps a player has been playing for a long time in one team and has exhausted his growth potential there. Then the player may decide to change teams, regardless of whether his target is a worse or a better team. This algorithm uses this fact as follows. If a player goes through a certain number of training sessions without improving his stats, he changes teams to a random one in order to receive training sessions determined by another successor function. The number of training sessions without improvements that must occur before the change is an input variable that the developer must manually specify in the method.
Moreover, in football, not only players are transferred between teams, coaches are also usually replaced when the teams they coach do not achieve the expected results. In each transfer period, all teams in the bottom half of the table change their training function (i.e., change their coach). The change of training is done randomly among all selected functions existing in the system. This random change, which affects all players in the team, also improves the exploratory power of the method.
The finalization of the algorithm depends on the fulfillment of three factors. If, compared to the previous season, the sum of the characteristics of all teams, the sum of the characteristics of the team captains and the best solution found in the system have not improved. When this finalization criterion is reached, the algorithm returns the solution with the best characteristic, which is the general solution for the problem under study.
Optimizing football play with substitutes (Soccer game optimization with substitute players, SGO)
SGO is a hybrid algorithm that combines the competition and reproduction processes of evolutionary algorithms with the information sharing of swarm intelligence algorithms. In SGO, the feasible search space is represented by a football field, and individual solutions are represented by players. During the game, players randomly change positions to explore the search space, or move toward the player holding the ball (the current best solution) to find a better position and become the player holding the ball.
The method is based on the motor behavior of football players, i.e. it transforms the basic behavior of players into an optimization method by simplifying the environment and rules. In a football match, a player takes a good position to dribble the ball and score a goal. Cooperation between players in a team is important. The ball moves between players, and the position of the ball is the main factor that takes into account the player's movement. A player who is not dribbling the ball will try to take a better position to become the dribble. Some players will move closer to the ball, while others will move further to explore the football field. In addition to the position of the ball, a player's movement is also influenced by nearby players and his own experience. A team is a simultaneous set of vector solutions. Each player encodes a set of decision variables. The quality of a player is assessed using his objective function. The player with the ball represents the best current solution obtained in the search process. The position of the dribble is transparent to the entire system, so all players have access to this information (the current best solution). This is similar to a real football game, where all players take the position of the dribble into account in their movements. During the game, the player dribbling the ball can either pass the ball to another player or continue to hold the ball.
Football League Competition Algorithm (Soccer League Competition, SLCA)
SLCA is a population metaheuristic that models the competition between teams within a league to achieve the top position and the internal competition between players for their personal ranking. In SLCA, players represent possible solutions, and player strength represents an objective value. Players compete to be the best player on the team (local optimum). The best players of each team in the league compete to be the best player in the league (global optimum).
Each team consists of 11 core players (defined by the main decision vectors in the algorithm) and several substitute players (described by reserved decision vectors). For each player, an objective function is calculated that characterizes the strength of the corresponding player. In the minimization problem, smaller values of the objective functions (cost functions) illustrate strong players. The overall strength of a team is defined as the average strength of its players, including both the core and the substitutes. After each match, a winner and a loser are determined, and some players (decision vectors) are changed. These changes, aimed at improving the performance of players and teams, are modeled using operators imitations, provocations, mutations And replacements. Imitation means that the main players imitate both the best player of their team and the best player of the league. The provocation operator performs the process by which the substitutes of the team strive to the average value of the main players' performance in order to become a main player. The mutation operator performs the correction function by which the main players of the losing team reconsider their play in order to avoid failures in future games. To perform this operation, the positions of some players are randomly changed. The replacement and substitution operators implement the process of finding the best solutions between the main and the substitutes.
In general, the described operators have the following effects in the algorithm:
The imitation operator accelerates the search capabilities of the algorithm, the provocation operator ensures the accuracy of solving optimization problems, the mutation and replacement operators help the algorithm avoid local extremes and plateaus.
After each game, the players are subject to the described operators (decision vectors), and the team characteristics are updated according to the new decisions. Obviously, strong teams are more likely to succeed in their future matches. This process continues until the end of the season, and the best player in the league shows the global optimum (the best solution) to the optimization problem. After each season, the players are assigned based on their updated playing strength. Before the start of a new season, the best players are assigned to the best teams, average players are assigned to teams with average performance, and weak players are assigned to teams from the bottom of the standings.
To find a solution to the problem, the SLCA algorithm quickly reaches local optima and considers the best of them as the global optimal solution using the imitation operator. The local optimal solution is then accurately approximated by the provocation operator. During the above operations, the mutation and replacement operators check for skew points to prevent ignoring any other possible local or global optimum points in the domain. The combination of the four operators along with the league ranking procedures makes this algorithm an excellent optimizer among many others and has very low sensitivity to the problem size.
Football League Optimization (Soccer League Optimization, SLO)
SLO is a population algorithm based on the results of the leading European football leagues. The initialization of the algorithm begins with the distribution of teams depending on their financial status: rich (the strongest), ordinary and poor (the weakest). The optimization process is based on simulating competition between teams of the three levels for the acquisition of the best players. The poorest teams find, train and sell young talented players to ordinary teams if they show good results. Ordinary teams either buy players from the poorest teams or find and train players themselves. Players with the best performance are sold to the strongest teams.
Football match algorithm (Football Game Algorithm (FGA))
The optimization process in FGA is an imitation of the movements of football players on the football field (search space) during the game. The algorithm is based on modeling the behavior of football players during the game to find the best scoring positions under the supervision of the team coach. The initial solution is defined as the initial composition of players on the field. It is assumed that the football players belong to one team that is losing the game and constantly strives to score more goals, thus attacking throughout the game. During the game, the football players randomly change their positions (solutions) and pass the ball forward. The player with better physical fitness has a better chance of receiving the ball. The peculiarity of this algorithm is the application of the following idealized rules:
— the running time of the algorithm is considered to be the total time of the match, and the search space for solutions is considered to be a football field;
– the football players belong to one team, which is considered to be losing or always wants to score more goals and attacks throughout the game;
— it is assumed that all players of the opposing team are located around the vertices of the minimization problem, which makes these places undesirable for the attacking team.
The initial lineup determines the initial position of the players on the field. Once the algorithm starts, each player moves around their last position (random walk) over time towards the ball. The ball is passed between players, and players in a better position have a better chance of receiving the ball.
The corresponding fitness values of each player indicate the quality of his position. The team coach remembers the best positions during the match and uses them to guide the players. He can also use the substitution option to replace a defender in a low-quality position with a fresh attacker in a better position and increase the chances of scoring. This strategy is valid until the end of the game or until the team scores a goal (modeled by the termination criteria). Without the coach's influence on the players' movements, their movements are of twofold nature. The first is a simple random walk, and the second is a movement towards the ball. Each player moves randomly from his last position to find a better position. In addition to the general movement of the players, the team coach uses his observations during the match to guide the players and place them in more advantageous positions. The coach's memory is actually the memory of the algorithm that allows him to save the best positions and the corresponding player characteristic values. There are two general strategies that the team coach can apply to increase the chance of scoring a goal (finding the global optimum).
The first is attack. In this strategy, the coach pushes the back line players forward to better positions and increases the pressure on the opposing team to increase the chances of success. The second is substitution. In this strategy, the coach takes advantage of the opportunity to replace weak players with stronger ones.
The amount of trainer memory allows players to move towards a larger number of potential solutions instead of the single best solution that is formulated in other algorithms such as the particle swarm method as a final convergence. This feature of the algorithm helps to clear the search space better and more efficiently than other metaheuristics. When choosing a larger amount of memory, the speed of finding the global optimum of the algorithm increases, but the accuracy decreases, and vice versa.
Recent sports research has shown that processes, concepts, rules and events in various sports can be viewed and modeled as new and effective search and optimization methods with exploration capabilities in many cases that can outperform existing classical optimization methods in various types of search spaces.
In this article, we briefly looked at several algorithms inspired by the most popular sports game in the world, but their number is somewhat larger than could be described in one article. Therefore, in the next article, I will talk about other “football” algorithms and analyze one of them in more detail.
UFO arrived and left a promo code here for our blog readers:
-15% on any VDS order (except for the Warming up tariff) — HABRFIRSTVDS
