A New Metaheuristic Algorithm Called Treble Opposite Algorithm and Its Application to Solve Portfolio Selection

Optimization becomes an integral part of the wide range of practical works, especially in engineering. The examples are as follows. In the multi-energy system, optimization is needed to minimize the operational expenditures consisting of the energy purchasing cost reduced by energy sales and added with setup cost [1]. In the energy sector, optimization is implemented into wind-based energy systems to minimize the total electricity shortage [2]. Optimization is also used in the battery energy storage system to maximize revenue and minimize long-term capacity fading [3]. In the telecommunication sector, optimization is used in the vehicular ad hoc network (VANET) to increase throughput and reduce delay, packet loss rate, and cost of service [4]. In the manufacturing system, optimization is implemented into production scheduling with objectives such as tardiness, earliness, make-span, number of tardy and early jobs [5].

Optimization plays an important role in engineering because many practical engineering problems need to be solved based on certain objectives. It works by finding the best solution within the solution space or possible solutions [6] and working within the constraints or solution boundaries. Metaheuristics is a long decade tool for optimization. Its popularity comes from its superiority in producing acceptable or high-quality solutions with a limited computational resource. Moreover, metaheuristic is flexible in handling various optimization problems because it abstracts the problem and focus on its objectives and constraints [7]. As a trial-and-error approach, its stochastic-based method does not guarantee finding the real optimal solution [8].

There are a lot of metaheuristics that already exist in the recent years. Most of them are swarm-based metaheuristics. Many of them use metaphors as the inspiration of their strategy. Many swarm-based metaheuristics imitate animal behavior, such as grey wolf optimization (GWO) [9], marine predator algorithm (MPA) [10], slime mold algorithm (SMA) [11], pelican optimization algorithm (POA) [12], zebra optimization algorithm (ZOA) [13], coati optimization algorithm (COA) [14], butterfly optimization algorithm (BOA) [15], northern goshawk optimization (NGO) [16], guided pelican algorithm (GPA) [17], clouded leopard optimization (CLO) [18], Komodo mlipir algorithm (KMA) [19], cheetah optimizer (CO) [20], cat and mouse based optimizer (CMBO) [21], remora optimization algorithm (ROA) [22], and so on. Certain number of metaheuristics imitate human or social activities, such as modified social force (MSFA) [23], chef-based optimization algorithm (CBOA) [24], driving training-based optimizer (DTBO) [25], election-based optimization algorithm (EBOA) [26], and so on. Some metaheuristics do not use metaphor but directly use their main strategy for their name, such as average and subtraction-based optimization (ASBO) [27], golden search optimization (GSO) [28], total interaction algorithm (TIA) [29], and so on.

In almost all swarm-based metaheuristics, guided search becomes the primary strategy, while random or neighborhood search becomes the complementary one. In general, the solution will get closer to the better solution. This better solution can be the global, local, and some best solutions, or a mixture among them. In some metaheuristics, a solution interacts with other solution that is selected randomly. Then, the quality of this randomly selected solution is compared with the corresponding solution. The corresponding solution moves closer to the selected solution if the selected solution is better than the corresponding solution. Otherwise, the corresponding solution chooses to move away. Several metaheuristics also perform the guided search by moving away from the worst solution. This strategy is rational because improvement becomes more probable by moving closer to the better solution or moving away from the worse one.

Unfortunately, in the trial-and-error approach implemented in metaheuristic, getting closer to the better solution never guarantees improvement. Besides, performing neither narrow nor large local search space guarantees improvement too. Getting closer to a better solution may lead to the local optimal entrapment. Neighborhood search with a narrow local search space may lead to stagnation when the current solution is not in the area where the global optimal solution exists. On the other hand, neighborhood search with large local search space may throw away the current solution to the worse area.

The primary objective of this work to introduce a new swarm-based metaheuristic called the treble opposite algorithm (TOA). As its name suggests, TOA consists of three phases that are performed sequentially. The guided searches are performed in the first and second phases, while neighborhood search is performed in the third phase. There are two searches or walks that are opposites to each other. Meanwhile, there are two secondary objectives in this work. The first secondary objective is to evaluate the performance of TOA to solve both theoretical and practical problems. The second secondary objective is to promote the portfolio optimization problem representing the discrete problem as a use case rather than the common mechanical design problem.

The scientific contributions of this work can be described as follows:

(1) This paper introduces a new swarm-based metaheuristic that performs both getting closer to and away from the reference.

(2) This new metaheuristic also performs neighborhood searches with both narrow and wide local search space.

(3) This work evaluates the proposed metaheuristic through simulation to solve the set of 23 classic functions.

(4) The assessment is also taken by competing the proposed metaheuristic with five new swarm-based metaheuristics: GWO, GSO, ZOA, ASBO, and COA.

This work is carried out based on certain methodology. First, certain number of new swarm-based metaheuristics is reviewed, especially their fundamental strategy. Second, these existing metaheuristics are mapped and then the position of the proposed metaheuristic is investigated and introduced to make clear position to fill the gap in the recent development of metaheuristics. Third, the formal model includes the algorithm and mathematical representation of TOA constructed. Fourth, the assessment of the performance of TOA is carried out by challenging TOA to solve both theoretical and practical problems and its comparison with several latest metaheuristics. Fifth, the in-depth investigation regarding the assessment result and the drawback to the theoretical aspect is carried out to develop a comprehensive assessment of the proposed TOA, including its strength, weakness, limitation, complexity, and proposal for future studies.

The arrangement of the rest of this paper is as follows. The review regarding new swarm-based metaheuristics, especially related to their metaphor, mechanics, and the use case for assessment, is presented and summarized in section 2. A detailed description of the proposed metaheuristic, which consists of the fundamentals, algorithm, and formalization, is presented in section 3. The assessment of the proposed metaheuristic and its result is presented in section 4. The in-depth analysis regarding the result, findings, linkage to the theoretical basis, and the limitation of this work are discussed in section 5. In the end, the concluding remark and the potential for future works or developments are summarized in section 6.

The proposed treble opposite algorithm (TOA) is developed as a metaphor-free swarm-based metaheuristic. As a metaphor-free metaheuristic, TOA uses its main strategy for its name. Meanwhile, as a swarm-based metaheuristic, TOA uses guided search as its core search and random search as complementary. TOA consists of three phases performed sequentially. A guided search relative to the global best solution is performed in the first phase. A guided search relative to a target between two randomly selected solutions is performed in the second phase. A random search is performed in the third phase. Each phase consists of two searches where each search generates a candidate. Then, the better candidate between these two candidates will be assessed to replace the current solution. The rigid acceptance approach is implemented in TOA.

There are several reasons behind this concept. First, there is not any guarantee that moving toward a better solution guarantees improvement, especially in handling multimodal problems. Besides, the walk toward the best or better solution may end with the circumstance where the optimization process is entrapped within the region of the local optimal. Meanwhile, moving toward any direction without any certain guidance is far from wise. Second, the multiple search approach becomes more important as each has its advantages and disadvantages. Meanwhile, there is not any metaheuristic can accommodate all kinds of searches. Third, the walk should not rely only on the global best solution or the best solution among the population. Fourth, swarm-based metaheuristic should be enriched with random search. A rigid acceptance approach is needed to prevent the agent from moving toward a worse solution.

As a swarm-based metaheuristic, TOA is also a population-based metaheuristic. It means that TOA consists of a certain number of solutions. In general, as with other metaheuristics, TOA consists of two steps. The first step is initialization while the second step is iteration. In the initialization, all solutions are generated uniformly within the search space. It means all solutions within the search space have an equal opportunity to become the initial solution.

The first phase consists of a guided search relative to the global best solution. There are two walks in this phase. The first walk is the walk toward the global best solution. The second walk is the walk to avoid the global best solution. The first walk is common in many swarm-based metaheuristics because the improvement is more probable by getting closer to the global best solution. But moving toward the global best solution does not guarantee improvement, especially in handling multimodal problems. On the other hand, avoiding the global best solution can be seen as the exploration to anticipate if moving toward the global best solution may lead to stagnation or local optimal entrapment. This process is illustrated in Figure 1.

1.png

Figure 1. Guided search toward and opposite the global best solution

The second guided search consists of the guided search relative to the solution in the middle between two randomly selected solutions. This process can be viewed as a guided exploration. In many metaheuristics where there is an interaction between the corresponding solution and other solutions within the population, the reference is the randomly selected solution. Meanwhile, in TOA, there are two solutions that are selected randomly. Then, the target is not one of the selected solutions but the average of two random solutions. The reasoning is that the walk toward the existing solution is unnecessary because the quality of these solutions is already known. Meanwhile, it is important to search for someplace between two found solutions. There are two walks performed in this search. The first walk is a walk toward the target while the second walk is a walk to avoid the target. This strategy is different from many shortcoming metaheuristics regarding the interaction among solutions where the corresponding solution moves toward a randomly selected solution if this randomly selected solution is better than the corresponding solution and moves in the opposite way when the opposite circumstance takes place. This process is illustrated in Figure 2.

2.png

Figure 2. Guided search toward and opposite the middle between two randomly selected solutions

The third phase consists of two random searches, i.e., neighborhood searches. As neighborhood searches, these searches try to find better solutions around the corresponding solution. Meanwhile, there are differences between these two neighborhood searches. The first search is performed within a narrow local search space, while the second search is performed within the large local search space. The similarity among them is that the local search space declines linearly through iteration. This process is illustrated in Figure 3.

3.png

Figure 3. Neighbourhood search within the large and narrow local space

4.png

Figure 4. Flowchart of TSO

The rigid acceptance approach is performed for all solutions and the global best solution. The new solution or candidate replaces the previous solution only if the improvement happens. Otherwise, this candidate will be rejected. Moreover, each time there is a new solution or replacement, the global best solution will be updated. The rigid acceptance approach is also performed to update the global best solution.

This concept is then formalized in pseudocode presented in algorithm 1. x_b becomes the final solution. The initialization step is presented from line 2 to line 5. Meanwhile, the iteration step is presented from line 6 to line 15. Moreover, the illustration of the overall process of TOA is presented in the flowchart in Figure 4. The more detailed procedure in each process is mathematically presented using Eq. (1) to Eq. (15).

This population is formalized by using Eq. (1), where this population is presented with a set of solutions. x denotes the solution, X denotes the set of solutions, and n denotes the population size.

$X=\left\{x_1, x_2, x_3, \ldots, x_n\right\}$        (1)

The initialization is formalized by using Eq. (1). In Eq. (2), x_i,j denotes the solution i at dimension j, x_l,j denotes the lower boundary of dimension j and x_u,j denotes the upper boundary of dimension j. U represents the uniform random generator.

$x_{i, j}=U\left(x_{l, i}, x_{u, i}\right)$  (2)

The updating process of the current solution and the global best solution processes is formalized using Eq. (3) and Eq. (4). The improvement is measured based on the objective function f. In this work, the context of optimization is minimization. It means the lower objective score means this solution is better. x_b denotes the global best solution representing the best solution so far.

$x_i^{\prime}=\left\{\begin{array}{c}x_c, f\left(x_c\right)<f\left(x_i\right) \\ x_i, \text { else }\end{array}\right.$      (3)

$x_b^{\prime}=\left\{\begin{array}{c}x_i, f\left(x_i\right)<f\left(x_b\right) \\ x_b, \text { else }\end{array}\right.$     (4)

The first guided search procedure is formalized by using Eq. (5) to Eq. (7), where x_c11 and x_c12 denote the first and second walks in the first phase. Meanwhile, x_c1 denotes the candidate of the first phase.

$x_{c 11, j}=x_{i, j}+U(0,1) \cdot\left(x_{b, i}-2 x_{i, j}\right)$       (5)

$x_{c 12, j}=x_{i, j}+U(0,1) \cdot\left(x_{i, j}-2 x_{b, j}\right)$       (6)

$x_{c 1}=\left\{\begin{array}{c}x_{c 11}, f\left(x_{c 11}\right)<f\left(x_{c 12}\right) \\ x_{c 12}, \text { else }\end{array}\right.$        (7)

Processes in the second phase are formalized by using Eq. (8) to Eq. (12). Eq. (8) states that two randomly selected solutions are picked from the population uniformly where x_s denotes the selected solution. Eq. (9) states that the target (x_t) is determined in the middle between these two solutions. Eq. (10) represents the walk toward the target, while Eq. (11) represents the walk to avoid the target. x_c21,j and x_c22,j denotes the first and second candidates generated in the second phase at dimension j. x_c2 denotes the final candidate of the second phase.

$x_{s 1}, x_{s 2}=U(X)$        (8)

$x_{t, j}=\frac{x_{s 1, j}+x_{s 2, j}}{2}$       (9)

$x_{c 21, j}=x_{i, j}+U(0,1) \cdot\left(x_{t, j}-2 x_{i, j}\right)$         (10)

$x_{c 22, j}=x_{i, j}+U(0,1) \cdot\left(x_{i, j}-2 x_{t, j}\right)$       (11)

$x_{c 2}=\left\{\begin{array}{c}x_{c 21}, f\left(x_{c 21}\right)<f\left(x_{c 22}\right) \\ c_{22}, \text { else }\end{array}\right.$         (12)

The processes in the third phase are formalized using Eq. (13) to Eq. (15). t denotes the iteration while t_m denotes the maximum iteration. x_c31,j and x_c32,j denotes the first and second candidates generated in the third phase at dimension j. x_c3 denotes the final candidate of the second phase.

$x_{c 31, j}=x_{i, j}+0.1 U(-1,1) \cdot\left(1-\frac{t}{t_m}\right) \cdot\left(x_{u, j}-x_{l, j}\right)$       (13)

$x_{c 32, j}=x_{i, j}+U(-1,1) \cdot\left(1-\frac{t}{t_m}\right) \cdot\left(x_{u, j}-x_{l, j}\right)$        (14)

$x_{c 3}=\left\{\begin{array}{c}x_{c 31}, f\left(x_{c 31}\right)<f\left(x_{c 32}\right) \\ c_{32}, \text { else }\end{array}\right.$            (15)

In general, the performance of any metaheuristics can be drawn back to their exploration and exploitation capabilities. Exploration represents the ability of the metaheuristic in tracing solution within the search space [26]. Exploration is needed to find the area where the global optimal solution exists and to avoid the local optimal entrapment. In this context, exploration capability is usually linked to multimodal problems where these problems consist of multiple optimal solutions. In many cases, there are a lot of optimal solutions in one multimodal problem which means a metaheuristic will be easily trapped in the local optimal so that the area of global optimal solution will never be found. Exploitation represents the ability to improve the current solution by tracing possible solution near the current solution [26]. Exploitation can also be viewed as the ability to conduct the local search. The other issue is related to the condition when the agent is thrown away from the area where the global optimal solution. Based on these issues, in this section, the capability of TOA in handling exploration, exploitation, and avoiding being thrown away from the area of the global optimal solution will be discussed.

The main difference of TOA from other swarm-based metaheuristics is that TOA performs not just moving closer but also moving away. It means that without considering the quality of its reference, whether it is the global best solution or the randomly selected solution. It is different from GSO [28] and GWO [9] where these two metaheuristics performs moving closer only. This approach is also different from ASBO [27], COA [14], and ZOA [13] where the direction of the walk relative to other solutions is performed conditionally. The getting closer walk is performed only if the reference is better than the corresponding solution and choose to get away when the opposite circumstance takes place. As mentioned previously there is not any guarantee that getting closer to the better solution will end with improvement. Tracing both directions as implemented in TOA is proven better than implementing getting closer only or the optional direction.

The exploration capability of TOA is also enriched with the walk relative to the middle between two randomly selected solutions. It provides additional exploration because this location may not be traced yet. This concept is like GWO where the target is the resultant of the three best solutions in the current iteration or ASBO where one of the targets is the middle between the best and worst solutions in the current iteration.

Neighborhood searches performed in the third phase represent both exploration and exploitation capabilities. The neighborhood search with wide local search space represents the exploration while the neighborhood search with narrow local search space represents the exploitation. Although the local search space width of both neighborhood searches decreases linearly, the width of the second neighborhood search is still ten times than the first one.

The effort to avoid the agent moving to a worse solution or being thrown away from the current area is facilitated mainly by the rigid acceptance approach. This approach is important due to the result in handling the high-dimensional functions. It is shown that metaheuristics that implement rigid-acceptance approaches are far better than those that do not. The second protection comes from the local search space that is reduced linearly through iteration. This second approach gives more flexibility in the early iteration, and this flexibility becomes harder as the iteration goes. Simulated annealing is the early metaheuristic that introduces iteration-controlled flexibility. Meanwhile, MPA is the famous swarm-based metaheuristic that uses this approach by reducing the local search space through iteration. This approach is then adopted and modified by the later metaheuristics, such as POA, ZOA, COA, etc.

The superiority of TOA does not mean it has become the perfect metaheuristic. TOA is a metaheuristic that performs better than GWO, GSO, ZOA, COA, and ASBO in handling almost all functions in the set of 23 functions. Meanwhile, ZOA is better than TOA in handling Step, ASBO is better than TOA in handling Penalized, and COA is better than TOA in handling Hartman 6 and Shekel 5. Moreover, the final solution of TOA is still far from the global optimal in handling Rosenbrock, Step, Schwefel, Hartman 3, Shekel 5, Shekel 7, and Shekel 10.

The superiority of TOA in handling the portfolio optimization problem also does not guarantee that TOA is superior in handling all practical optimization problems. This portfolio optimization problem is generally an integer-based optimization problem because the decision variables are presented in integer format. The objective function is also simple accumulating the capital gain of all shares. Moreover, there is no stock in which the capital gain is negative. Meanwhile, this problem is more unique than the set of 23 functions because the quantity of stocks that should be purchased is limited by not only the maximum range but also the total investment. Meanwhile, there are various practical optimization problems in engineering where the decision variables are presented in floating point, and the objective function is more complex. Besides, there are various combinatorial optimization problems that can be explored to evaluate the effectiveness of TOA rather than numerical optimization problems as in this work.

This result motivates the modification and improvement of TOA in future work. Besides, there are a huge number of optimization problems spanning the wide area of engineering. These problems have their own characteristics, such as the objective and constraints. The objective can be a single objective or multiple objectives. Meanwhile, in many problems, some constraints may depend on other constraints, making these problems more difficult to solve. Many problems are combinatorial rather than numerical.

Moreover, future studies can be carried out based on the advantages and limitations of this current work. In regard that the searching in both opposite directions is better than searching in a single direction, this approach can be maintained in future development. Meanwhile, this TOA uses only two references: the best solution, and two randomly picked solutions. On the other hand, there are existing metaheuristics that use a better solution in the swarm or a collection of better solutions in the swarm as reference. This approach can be hybridized into the current TOA as improvement. Besides, the investigation of hybridizing TOA as a swarm-based metaheuristic with any evolution-based metaheuristic is also challenging. In the end, the modification or improvement can also be performed by implementing other stochastic distributions, such as exponential, Poisson, normal, Brownian, and so on.