Fata Morgana Algorithm

A Fata Morgana of a cargo ship seen off the coast of Oceanside, California

The Fata Morgana Algorithm (FATA) is a swarm intelligence optimization algorithm designed to solve continuous multi-type optimization problems . FATA is inspired by the natural phenomenon of a mirage, known as "Fata Morgana," which occurs due to the refraction and reflection of light through layers of atmosphere with varying densities. This algorithm introduces two innovative strategies: the Mirage Light Filtering Principle (MLF) and the Light Propagation Strategy (LPS), which enhance the exploration and exploitation capabilities of FATA .

Overview

FATA was developed to tackle a variety of optimization challenges, including engineering problems. It combines mathematical modeling of the Fata Morgana effect, which balances global and local search strategies, to provide efficient solutions for both benchmark functions and real-world applications. The algorithm was tested against numerous competitive optimization methods and demonstrated superior performance.

Key Features

• Mirage Light Filtering Principle (MLF): A global exploration strategy that evaluates population quality and filters out individuals that are not contributing to the optimal solution.
• Light Propagation Strategy (LPS): A local exploitation strategy that improves convergence speed by simulating light refraction and total internal reflection, focusing on refining the solution.

Algorithm Inspiration: Fata Morgana Phenomenon

A Fata Morgana is a complex form of mirage, visible from the sea or land, which distorts objects like boats on the horizon. The phenomenon occurs when rays of light bend due to atmospheric conditions, specifically temperature gradients between layers of air.

FATA mimics this phenomenon by balancing between:

• Global search (exploration)—analogous to light filtering through various atmospheric layers.
• Local search (exploitation)—analogous to the refraction and reflection of light to sharpen the focus on the optimal solution.

Algorithm Structure

The FATA algorithm is composed of two primary strategies:

3.1 The Mirage Light Filtering Principle

The section shows the Fata Morgana algorithm’s population search strategy based on the principle of definite integral. During the physical process of mirage formation, the hull emits two types of light rays. The majority of the light rays belong to the first type, which do not propagate and form a mirage. The other type of light rays undergoes physical transformations that result in the formation of a mirage and are referred to as the mirage light $x$.

In FATA, distinguishing between the two types of light populations is crucial for the algorithm to find $x_{\text{best}}$. Therefore, FATA employs a light population quality evaluation strategy based on the definite integral principle to assess the different types of light populations. In swarm intelligence algorithms, population quality is evaluated by calculating individuals' fitness and then aggregating the fitness values for the entire population.

If the fitness of individuals in a light population is ranked, it forms a cumulative curve. To efficiently compute the fitness of different types of light populations (other light, the mirage light), FATA utilizes definite integration to evaluate the curve, using the integral value as a measure of fitness. The mirage light $x$ that is selected based on the definite integral principle is also referred to as the filtered mirage light population.

First, the strategy determines the population as other light or the mirage light based on the population quality to perform different search methods:

$x_{i}^{\text{next}}={\begin{cases}L_{b}+(U_{b}-L_{b})\cdot {\text{rand}}&{\text{if }}{\text{rand}}>P\\x_{\text{best}}+x_{i}\cdot {\text{Para}}_{1}&{\text{if }}{\text{rand}}\leq P{\text{ and }}{\text{rand}}<q\\x_{\text{rand}}+\left[0.5\cdot (\alpha +1)(U_{b}-L_{b})-\alpha x_{i}\right]\cdot {\text{Para}}_{2}&{\text{if }}{\text{rand}}\leq P{\text{ and }}{\text{rand}}\geq q\end{cases}}$

$P={\frac {S-S_{\text{worst}}}{S_{\text{best}}-S_{\text{worst}}}}$

$q={\frac {{\text{fit}}_{i}-{\text{fit}}_{\text{worst}}}{{\text{fit}}_{\text{best}}-{\text{fit}}_{\text{worst}}}}$

where $x$ is the light individual, and $x^{\text{next}}$ is the new individual. Among them, the expressions for the first-half refraction strategy, the second-half refraction strategy, and the total internal reflection strategy are:

$x_{i}^{\text{next}}=L_{b}+(U_{b}-L_{b})\cdot {\text{rand}}$

$x_{i}^{\text{next}}=x_{\text{best}}+x_{i}\cdot {\text{Para}}_{1}$

$x_{i}^{\text{next}}=x_{\text{rand}}+\left[0.5\cdot (\alpha +1)(U_{b}-L_{b})-\alpha x_{i}\right]\cdot {\text{Para}}_{2}$

In $P$, $S_{\text{worst}}$ represents the quality of the worst population. $S_{\text{best}}$ represents the quality of the best population. The mirage light populations have excellent population quality. In $q$, ${\text{fit}}_{i}$ represents the fitness of the current individual $(x)$. ${\text{fit}}_{\text{worst}}$ represents the fitness of the worst individual. ${\text{fit}}_{\text{best}}$ represents the fitness of the best individual.

Algorithm 1: The Mirage Light Filtering Strategy

${\text{Input: light individual }}x;$ ${\text{Fit the population quality function }}f(x){\text{ according to the fitness of the individuals;}}$ ${\text{Calculate the integrated area }}S{\text{ of the }}f(x){\text{ based on the principle of definite integration;}}$ $P={\frac {S-S_{\text{worst}}}{S_{\text{best}}-S_{\text{worst}}}}$ If ${\text{rand}}>P$ ${\text{The population is the light rays directed towards a medium with inhomogeneous density populations;}}$ ${\text{The population performs }}x_{i}^{\text{next}}=L_{b}+(U_{b}-L_{b})\cdot {\text{rand}};$ ${\text{Else}}$ ${\text{The population is the light rays not directed towards a medium with inhomogeneous density populations;}}$ ${\text{The population executes the search strategy (Eqs. (2-3));}}$ ${\text{End If}}$ ${\text{Return new individual }}x^{\text{next}};$

$y=f(x)=\sum _{j=0}^{n}c_{j}\phi _{j}x$

$S=\int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{n}}\cdot \left({\frac {(y_{0}+y_{1})}{2}}+{\frac {(y_{1}+y_{2})}{2}}+\cdots +{\frac {(y_{n-1}+y_{n})}{2}}\right)$

The Light Propagation Principle

The light propagation principle in FATA is executed after the mirage light filtering principle, and it serves as the individual search strategy of the algorithm responsible for local exploitation in the search space to find local minima. The light population of FATA, represented by the mirage light rays, starts from the small boat in the lower-left corner. First, it undergoes the mirage light filtering strategy, where the light population is evaluated and filtered based on the principles of calculus to select the individuals that form the mirage phenomenon. Furthermore, the filtered mirage light population undergoes refraction and reflection sequentially. The individual changes in the light population during refraction and reflection can be observed. The light rays change in direction and size during the processes of refraction and reflection.

The Fata Morgana algorithm designs the individual search strategy based on the light propagation principle combined with trigonometric functions. The algorithm chooses to execute the reflection strategy (the first half phase), the reflection strategy (the second half phase), and the refraction strategy based on the individual quality factor.

Light refraction (the first half phase). In the first half refraction, the light $x$ enters the medium with inhomogeneous density from an optically denser medium to an optical thinning medium, changing the direction and size of the light. The angle of incidence $i_{1}$ is smaller than the angle of refraction $i_{2}$.

In the first half refraction strategy, the new individual after the first half reflection strategy is:

$x^{\text{next}}=x_{\text{best}}+x_{z}$

where

$x_{z}=x\cdot {\text{Para}}_{1}$

and

${\text{Para}}_{1}={\frac {\sin(i_{1})}{C\cdot \cos(i_{2})}}=\tan(\theta )$

$x^{\text{next}}$ is the new individual. $x_{\text{best}}$ is the current best individual. $x_{z}$ represents the refraction step of the strategy. ${\text{Para}}_{1}$ is the first-half refraction ratio.

Light refraction (the second half phase). After performing the first half refraction phase, the light performs the second half refraction phase at random points. The angle of incidence $i_{3}$ is less than the angle of refraction $i_{4}$. The light propagates in a medium with inhomogeneous density, so the refractive index ${\text{Para}}_{2}$ changes continuously. In the second half refraction strategy, the light individual $(x_{f})$ will generate a new individual $(x^{\text{next}})$ based on random individuals $(x_{\text{rand}})$ in the search space.

$x^{\text{next}}=x_{\text{rand}}+x_{s}$

where

$x_{s}=x_{f}\cdot {\text{Para}}_{2}$

and

${\text{Para}}_{2}={\frac {\cos(i_{5})}{C\cdot \sin(i_{6})}}={\frac {1}{\tan(\theta )}}$

$x_{s}$ is the refraction step in the second half refraction strategy. $x_{\text{rand}}$ is a random individual from the population. ${\text{Para}}_{2}$ is the second refraction ratio.

The light total internal reflection. The total internal reflection phase is the final stage of light propagation in the formation of the mirage phenomenon. This is because as the refraction angle increases, the light undergoes total internal reflection in the medium with inhomogeneous density. The total internal reflection strategy drives the FATA population to explore in the opposite direction.

In the strategy, the light individual $(x)$ is transformed into the individual $(x^{\text{next}})$ to search for the target in the opposite direction.

$x^{\text{next}}=x_{f}=0.5\cdot (\alpha +1)\cdot (U_{b}+L_{b})-\alpha x$

$\alpha ={\frac {F}{E}}$

$x_{0}-x_{f}={\frac {F\cdot (x-x_{0})}{E}}$

$x_{0}={\frac {(U_{b}-L_{b})}{2}}+L_{b}={\frac {(U_{b}+L_{b})}{2}}$

Pseudocode

The following pseudocode outlines the structure of the FATA algorithm:

Input: parameters n, d, MaxFEs;
Output: best individual;
1. Initialize parameters Para1, Para2, α;
2. Initialize a population of size n;
3. Calculate fitness of each individual;
4. While (FEs <= MaxFEs):
    a. Update best fitness x_best;
    b. For each individual in the population:
        i. Execute Mirage Light Filtering Principle;
        ii. If rand > P, initialize the population randomly;
        iii. Else, execute Light Propagation Strategy:
        - Refraction (first and second phases);
        - Total Internal Reflection.
    c. Increment FEs;
5. Return the best individual x_best;

Applications

FATA has been applied to various benchmark optimization problems, including:

• Continuous multi-type functions.
• Real-world engineering problems such as structural design optimization and network scheduling.

The algorithm has consistently outperformed other optimization techniques in both accuracy and convergence speed.