Download Python Code (Zip)
Download MATLAB Code (Zip)
What is YUKI Algorithm
YUKI is a population based metaheuristic for global optimization. The idea behind it is to divide the search space and concentrate the search on the local region where the best solutions are found. The size of this region is dynamic: it adapts itself to the quality of the results around the best solution. Restricting the search to a small region brings two advantages; simplicity, and a clear and easy to interpret search behavior. The risk, however, is that a dynamically shrinking region may collapse onto a local optimum. YUKI avoids this by keeping a portion of the population exploring the space outside the local region even while the region contracts.
The local search area is centered on the best solution found so far, X_best, and its size is determined by the distance between this point and the mean of the personal bests, X_MeanBest;the center of the “cloud of best points”. The local boundaries are calculated independently for each dimension using the expressions: D = X_best − X_MeanBest , LT = X_best + D, and LB = X_best − D, clipped to the global bounds [lb, ub]. Because the box is defined per dimension, it can shrink at different rates along different axes.
The YUKI algorithm partitions the population into two groups. One group is tasked with exploring the search space beyond the local region, while the other focuses on searching within it. In the first version, the number of individuals in each group varied linearly over the iterations; more explorers in the early stages, more exploiters as the search matured. In the improved YUKI algorithm, this is replaced by a simpler scheme in which the rate is constant throughout the search and set by the user. This parameter is named EXP (exploration rate), with a value between 0 and 1, giving the portion of the population dedicated to exploration.
New solutions are generated through a two step process. Each individual first draws a candidate point PosLoc uniformly inside the local search area. Exploiters then settle around the current best: their final position lies on the ray from X_best through PosLoc, a fine-scale move tied to the size of the local box. Explorers instead use the distance between the locally generated point and their best historical point (personal best): the new solution is placed at PosLoc + (PosLoc − pbest), i.e. the personal best mirrored through the local sample. The length and direction of the jump therefore differ from one individual to another, which spreads the solutions in multiple directions and gives a good coverage of the search space outside the local region.
As the iterations progress, the personal bests improve and gather around the promising regions, so X_MeanBest gradually approaches X_best, the distance D decreases, and the local search area contracts around the optimum; allowing increasingly accurate identification of refined fitness values. If a new global best is discovered elsewhere, the box re-expands around it before contracting again, so the search can alternate between global and local phases. The goal of the algorithm is thus to minimize the distance between the center of the cloud of best points and the global best point, which in turn minimizes the size of the local search space.
📓 Manuscript (Word.docx)
Cite as
YUKI Algorithm and POD-RBF for Elastostatic and dynamic crack identification. Journal of Computational Science. 2021. https://doi.org/10.1016/j.jocs.2021.101451 (Download Preprint PDF)