Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem

1.   Introduction

Many metaheuristic algorithms ^[1,2,3] have been derived from research of the collective behavior of social organisms. These are generally employed to solve global optimization problems. They simulate nature and human intelligence to achieve the optimal solution. There are three main categories ^{[4,5,6,7,8,9]}, as shown in Figure 1.

The first is based on the evolutionary process. For example, one of the first population-based stochastic algorithms ^[2], the genetic algorithm (GA), imitates the theory of evolution, with steps of dynamic adaptive adjustment to gain the most suitable chromosome. Similar algorithms include differential evolution (DE), which relies on mutation strategies and control parameters and whose values are difficult to determine. Zhou et al. ^[1] developed a self-adaptive differential evolution algorithm to greatly address a single batch-processing machine scheduling problem. Deng et al. ^[2] proposed a DE algorithm with wavelet basis function (WMSDE), which integrated a wavelet basis function and normal distribution, and improved the local search information and diversity of solutions. Zhao et al. ^[3] proposed a two-stage cooperative evolutionary algorithm with problem-specific knowledge to address energy-efficient scheduling of no wait flow shop problem (EENWFSP). Most evolutionary algorithms imitate biological characteristics, a series of mechanisms, such as competition orcooperation, are required to complete evolution.

In the real world, biological individuals lack complicated intelligence, but based on certain rules, biological groups experience interaction, the interaction between the individual and the environment can often produce evolutionary phenomena. This is the basis of swarm intelligence optimization. By observing biological populations, we are able to simulate their cooperative strategies, such as hunting, swarming, migration, and foraging, and apply them to system design and optimization. Kaveh et al. ^[4] presented the water strider algorithm (WSA), inspired by the lifestyle of water strider bugs, to tackle discrete structural design problems, such as health monitoring. Zhao et al. ^[5] proposed a cooperative water wave algorithm (CWWO) to address the DANIFSP with the goal of minimizing the maximum assembly completion time. Yapici et al. ^[6] proposed a novel algorithm that imitates the leadership hierarchy of swarms, which is called the pathfinder algorithm (PFA). We thus review the crowd-based metaheuristic intelligent optimization algorithms, such as poor and rich optimization (PRO) ^[7] and gaining sharing knowledge (GSK) ^[8], the latter was motivated by human lifespan. It involves junior and senior gaining, both followed by a sharing phase.

Algorithms based on physical rules and chemical reactions usually simulate physical laws in nature, such as gravity, annealing, collision, and inertial force, and apply them to combinatorial constraint optimization. Liu et al. ^[9] proposed a metaheuristic photon search algorithm (PSA) with good search efficiency and convergence speed. Pflug et al. ^[10] employed a new random gradient metaheuristic algorithm for structural optimization problems.

Metaheuristic algorithm is based on heuristic algorithm. It is a combination of random algorithm and local search algorithm. Through constantly iterative optimization, the exploration and exploitation of search space can be realized. From the practical perspective, these kinds of algorithms rarely require the characteristics of functions in the optimization field, and have strong robustness to the optimization of functions. As metaheuristic algorithm has the advantages of a simple principle, easy programmability, and few parameters, a slew of novel metaheuristic algorithms have emerged to solve NP problems in different fields. Recently, the algorithm has been applied to continuous constraint problems and discrete structural design problems in the fields of computer science, engineering optimization design ^[11], optimal scheduling ^[12], resource coordination and scheduling ^[13], multi-objective optimization ^[14] and combinatorial optimization ^[15]. Deng et al. ^[2] applied DE to an assignment problem of airport gate which was a large-scale NP problem with complex constraint. Dhiman et al. ^[16] illustrated MoSSE by combing the characteristics of spotted hyena optimizer (SHO) with other metaheuristics. After testing on IEEE CEC-9 standard test function, the findings showed the stability of MOSSE to deal with the real complex multi-objective optimization problems. Zhao et al. ^[17] proposed a cooperative multi-stage hyper-heuristic (CMS-HH) algorithm to address six specific combinatorial optimization problems. The experimental results demonstrate the efficiency and significance of CMS-HH algorithm. Yang et al. ^[18] proposed an improved DBSCAN optimized by arithmetic optimization algorithm (AOA) for achieving automatic optimization of parameters. The experimental data show that DBSCAN can provide highly accurately clusters more efficiently.

Whale optimization algorithm (WOA) ^[19] was proposed by Mirjalili, which mainly realized the optimization by simulating the behaviors of humpback whale. Through the test of 29 benchmark functions and the application of six practical engineering problems, the algorithm was proved that its better accuracy and speed of convergence than other metaheuristic algorithms. Nevertheless, we see from the literature that WOA is constantly changing the position of the leader, but it still leads to prematurity when the leader is trapped in the fake optimal solution.

In view of the shortcomings of WOA, a large number of scholars have conducted research on WOA. Many of them improved whale optimization algorithm through different strategies and mechanisms. Chakraborty & Saha et al. ^[20] integrated the modified mutual mechanism from symbiotic organisms search with WOA to alleviate inherent drawback of premature convergence. Jin et al. ^[21] proposed an algorithm with random evolution and special reinforcement called REWOA. Luo & Chen et al. ^[22] proffered a multi-strategy boosted mutative whale optimization algorithm (MBMWOA), which was integrated with the chaotic initial regulation and the "shrinking" strategy of local search. Yang et al. ^[23] proposed a cellular automaton mechanism to improve whale optimization algorithm for the robust extreme learning machine (ELM) training. The experiment showed the improved optimizer was around 7% superior to the basic.

In addition, in related work, the algorithm was improved by combining with other novel metaheuristic algorithms. For example, Fan & Chen et al. ^[24] proposed to combine WOA with the characters of salp swarm algorithm (SSA) and learning mechanism. Nguyen et al. ^[25] fused galactic swarm optimization (GSO) with the variant of the WOA to avoid early convergence. In addition, WOA is also broadly used in practical applications. Due to the simplicity and accuracy of ISP problems, Abdel-Basset et al. ^[26] presented a hybrid metaheuristic algorithm called HSMA_WOA. The performance of HSMA_WOA had been proved by chest radiographs.

In summary, WOA has strong adaptability to continuous optimization problems in various application fields. However, it has fewer applications in discretization applications. Zhang & Hong et al. ^[27] proposed a WOA integrated the dynamically adjusted weight and improved search strategy to solve the traveling salesman problem library (TSPLIB). Wang et al. ^[28] put forward an improved algorithm called CMWOA that contained chaotic and other improved strategies to solve difficult diagnosis problems. Hemmelmayr et al. ^[29] harnessed an adaptive large neighborhood search algorithm (ALNS) with whale optimization algorithm to get higher quality solutions in a multi-compartment capacitated arc routing problem. To sum up, WOA algorithm has strong global search ability in discretization, so it also has advantages in building DNA storage code sets. In view of the characteristics of high density and high persistence of DNA, DNA storage has broken through the difficulties of traditional computers in data storage and computing speed, and has become a feasible solution. Then for the DNA storage problem, the first consideration is the DNA coding problem. An effective model that stores a large amount of data in a small amount of DNA is crucial to improve the storage rate, that is, the model can construct a larger number of coding sets within a certain base length. In order to solve this key problem, it is necessary to construct enough coding sets under the same sequence length, further improve the lower bound of the coding set, so that it can store more information at a given length, and thus improve the storage coding rate. This is also the meaning of DNA storage coding research.

In this paper, a combinatorial strategy is applied to optimize the WOA to achieve better convergence performance, the optimized algorithm is applied to address the very large-scale discrete problems in the field of biological computing. The major contributions have been outlined as follows:

1) In this paper, we propose the enhanced quasi-opposite learning (EQOBL). During each iteration, the locations of individual whales are selectively updated to better expand the search scope of the whale and enhance WOA's ability to explore the space. By continuously reducing the distance difference between whale (the candidate individual) and prey (the global optimal individual), the convergence speed is accelerated, and the main objective of improving the quality and diversity of the whale population is finally achieved.

2) An improved nonlinear decreasing strategy of inertia weight with collaborative control parameter is proposed to improve the convergence accuracy of WOA and adjust the global and local search ability to find the optimum.

3) Considered the application in the construction of DNA storage code sets, by discretizing the whale optimization algorithm and using its special search rules, it can achieve breakthrough in the lower bounds under the same coding constraints and improve coding rate. The increased coding rate means that ISOWOA can effectively reduce the synthesis cost of sequences under the same performance requirements. Based on the characteristics of fourth-generation nanopore sequencing technology, the DNA storage codes after screening by ISOWOA can minimize the errors in sequencing and complete the access to large DNA files.

The rest of this paper is briefly summarized as follows: In the second section, we briefly represent the concept of WOA; In the third section, we propose the new combination strategy to enhance the WOA; In the fourth section, we demonstrate the results of the CEC standard test function experimental simulation, convergence image analysis, multi-dimensional test analysis and statistical discussion; In the fifth section, we showcase its advantages in building DNA storage coding set in the field of biological computing, and discuss the experimental results in detail. Finally, the research work is summarized and the future work is envisioned.

2.   Whale optimization algorithm

Humpback whales are generally 13–15 m, which are well known for their complex calls, extra-long front wings, and leaps out of the water. Lacking teeth and being unable to hunt large prey like other whales, humpbacks have evolved a different way of hunting—diving into deep water, creating bubble nets, and spiraling upward around their prey. Inspired by bionics, the whale optimization algorithm ^[19] was devised. The process is modeled as the three phases ^[19].

2.1.   Shrinking of the prey encirclement

Prey can be located and encircled. The position of individual represents a candidate solution. If the location of the target prey is unknown, WOA will assume that the optimal location of the current whale is the target prey's location. Candidate solutions will continuously approach to the optimal solution in subsequent iterations. Through comparative analysis of location information, the optimal candidate solution will be updated using its positions. Humpback whales constantly shrink the encirclement till the target prey is found. The update formula ^[19] is

where $\overrightarrow{Dis}$ is the distance from the optimal solution to the current individual whale in the jth-dimensional position. If $\overrightarrow{Whale}\left(t+1\right)$ has a better positional advantage than $\overrightarrow{{Whale}^{{*}}}\left(t\right)$, the optimal position is updated.

2.2.   The spiral hunting of humpback whales

The following formula shows the spiral position updating model of WOA, which is denoted ^[19] as

where $\cdot$ denotes multiplication. To align the probabilities of exploitation and exploration of WOA, the shrinkage encircling mechanism is assumed to have the same probability as the spiral updating position, i.e., ${{\mathit{\boldsymbol{P}}}} = {\bf{0.5}}$.

2.3.   Random hunting of humpback whales

This strategy updates the location of the search agent based on a randomly selected individual. It is shown mathematically as

where $\overrightarrow{{Whale}_{rand}}$ is a random whale, and $\overrightarrow{Dis}$ is the distance from the whale to the current individual, and $\overrightarrow{Whale}\left(t+1\right)$ is an updated population, and the value of $\overrightarrow{A\_Factor}$ is given by (4).

3.   ISOWOA algorithm

Although the whale optimization algorithm has the advantages of a simple principle, easy programmability, and few parameters, it has the drawbacks that local optimal solutions are prone to precocious convergence. The optimization results for various test functions are not ideal. This paper makes the following improvements.

3.1.   Nonlinear control parameter strategy

WOA determines the global or local search through the value of $A$, which is determined by the factor $a$. A larger value of $a$ confers a stronger global search ability, and a smaller value confers a stronger local search ability. In the original literature ^[19], $a$ is linearly decreasing. Hence, the algorithm has a better global exploration ability at the beginning, but it may exist the possibility of easily falling into a local optimum in the middle and late iterations. A nonlinear decreasing parameter is applied to enhance this performance. The model is shown in Figure 2, which keeps a relatively high value for a period of time at the initial phase, then rapidly reduces to a low level, and maintains a low value at the middle and later phase of the iteration. This is expressed as

The nonlinear control parameter $a$ has a high value, which improves the search ability of the ISOWOA. It decays rapidly to a lower value in middle iterations to realize the rapid transition from global search to local search, which is guaranteed through a low value in later iterations.

3.2.   Nonlinear decreasing strategy of inertia weight with collaborative convergence factor

The proposed time-varying inertia weight is based on PSO. The parameter $\omega$ is important in PSO and plays a decisive role in its overall performance ^[30]. The focus on optimization algorithms research is to enable the algorithm to find the corresponding global optimal solution on various test functions. Of course, a relatively optimal solution is acceptable in practice. We introduce a time-varying inertia weight $\omega$ to improve the convergence accuracy and convergence speed of WOA. It can make the algorithm adaptively adjust the update strategy in order to obtain the global optimal solution. In early iterations, the inertia weight of synergy $a$ makes ISOWOA have stronger global search ability, that is, ISOWOA explores the search space much widely. $\omega$ is positively correlated with $a$ and is given by

where ${a}_{max}$ and ${a}_{min}$ are the maximum and minimum of the convergence factor; ${\omega }_{max}$ and ${\omega }_{min}$ are defined as 0.8 and 0.4 respectively; and ${\mathrm{M}\mathrm{a}\mathrm{x}}_{\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}}$ defines as 500.

With the novel inertia weight, the three original search methods of WOA are changed to

where $b = randi\left(500\right), l = \left({a}_{2}-1\right){*}rand+1$, and ${a}_{2} = -1-\frac{t}{Ma{x}_{iter}}$.

$\omega$ is generally controlled by $a$, decreases nonlinearly, and has stronger adaptability, which is an important factor in balancing the abilities of the ISOWOA. After the coefficient amplification of $a$, the convergence speed is greatly improved. To avoid wasting computing resources through excessive development, the value of inertial weight decreases significantly with the rapid decline of the nonlinear convergence factor in the middle and later stages of iteration, which greatly enhances local search ability, improves convergence accuracy, avoids precocious convergence, and balances exploitation and exploration.

3.3.   Enhanced quasi-opposition learning method (EQOBL)

After Tizhoosh et al. ^[31] put forward the concept of opposition-based learning, it has been successfully applied in various metaheuristic algorithms. Dhargupta et al. ^[32] applied it to grey wolf optimization with remarkable results. The strategy has been broadly used in various metaheuristic algorithms. The opposition-based learning strategy can be briefly defined as follows:

$x = \left({x}^{1}, {x}^{2}, \cdots , {x}^{n}\right)$ is a point, where ${x}^{i}\in \left[{l}^{i}, {u}^{i}\right].{x}^{\mathrm{'}} = \left({{x}^{1}}^{'}, {{x}^{2}}^{'}, \cdots , {{x}^{n}}^{'}\right)$ is defined by its components: ${{x}^{i}}^{'} = {l}^{i}+{u}^{i}-{x}^{i}$ ^[31].

Aiming at the situation that the individual fitness is still too high after opposition learning, in this paper, we propose a variant of OBL, enhanced quasi-opposite learning method (EQOBL) to increase the quality and diversity of candidate solutions, which makes EQOBL participate in each iteration instead of completing the initialization. By continuously reducing the distance difference between whale (the candidate individual) and prey (the global optimal individual), the convergence speed is accelerated. The main objective of improving the quality and diversity of the whale population is finally achieved.

The proceed is described as follows:

1) Define a time-varying factor for judging the difference between the rest and the optimal individual.

2) Implement the EQOBL mechanism for individuals with greater differences than time-varying factors.

3) Among them, the correlation helps to select opposing individuals and opposing dimensions, thus limiting and guiding our search.

4) Then the transformed population was merged with the original population, and the optimal n individuals were selected by the elite mechanism to participate in the subsequent iterative optimization.

Algorithm 1 shows the EQOBL pseudocode, and Figure 3 shows the ISOWOA flowchart.

This strategy can well guide the evolution of the population, its strong convergence enables ISOWOA to more quickly approximate the global optimal value.

4.   Experimental simulation results

To better interpret the algorithm's performance, we selected 23 international standard test functions ^[33]. These 23 functions are composed of three types: 7 unimodal functions (F1–F7), 6 multimodal functions (F8–F13), and 10 fixed-dimension functions (F14–F23). The three types of functions will be compared with the table as the boundary. Unimodal functions enable the investigation of local convergence accuracy and global convergence speed and stability; Multimodal functions can well distinguish global search ability; Fixed-dimension functions can be used to analyze exploration ability and avoidance of local traps. Hence, these test functions can greatly prove the performance of the algorithm. Its mean, standard deviation, iterative convergence curve, and multi-dimensional function tests were compared to those of the basic WOA, several variants, and a modern metaheuristic algorithm. However, in accordance with the No Free Lunch Theorem (NFL) ^[34], algorithm cannot reach the theoretical extremum on all test functions, and none can achieve the optimal design for all applications. Therefore, algorithms may show superior performance on different functions.

4.1.   Effectiveness analysis of three improvement strategies

It can be seen from the above that this paper has made three improvements to the basic WOA algorithm, namely, the nonlinear control parameter strategy, the nonlinear decreasing strategy of inertia weight with collaborative convergence factor and the enhanced quasi-opposition learning method (EQOBL). In order to analyze the effectiveness of the three improved strategies, this section compares the original WOA algorithm with the WOA algorithm that only uses the nonlinear control parameter strategy (named ISOWOA-1), the WOA algorithm that only adds the nonlinear decreasing strategy of inertia weight with collaborative convergence factor (named ISOWOA-2), and the WOA algorithm that only introduces the enhanced quasi-opposition learning method (EQOBL) (named ISOWOA-3), which effectively proves the contribution of each strategy to the algorithm. Here, the widely used CEC 2005 benchmark test function is used as the evaluation standard. The Tables 1 and 2 shows the test results of the four algorithms against the test standard. Black font indicates the best result of the comparison algorithm.

From the experimental results, it can be seen that the improvement of WOA algorithm performance by using nonlinear control parameter strategy alone is limited, but the advantage of this strategy is that it can greatly improve the performance of the algorithm when mixed with other strategies. In addition, from F1–F13, it can be seen that the performance of WOA algorithm is improved most obviously by adding the nonlinear decreasing strategy of inertia weight with collaborative convergence factor alone. The order of magnitude of the convergence value of the function has been greatly improved, which indicates that the nonlinear decreasing strategy of inertia weight with collaborative convergence factor has the largest impact on the optimization performance of WOA algorithm among the three strategies, and further indicates that the nonlinear decreasing strategy of inertia weight with collaborative convergence factor is more effective. It can be seen from the composite functions such as F14 and F20–F23 that the convergence value of the function has been greatly improved, which proves that the introduction of the enhanced quasi-opposition learning method (EQOBL) has significantly improved the performance of the WOA algorithm.

In order to prove the optimization effect of the ISOWOA, we compared it to enhanced whale optimization algorithm (EWOA) ^[33], improved whale optimization algorithm with joint search mechanism (JSWOA) ^[35], classical WOA, augmented grey wolf optimizer (AGWO) ^[33], and adaptive whale optimization algorithm (AWOA) ^[35]. Among them, EWOA modified the stages of the WOA. JSWOA introduced the joint search mechanism. The data of AGWO and AWOA were from EWOA ^[33] and JSWOA ^[35], respectively. The algorithm was tested with the parameters of the comparative algorithms, i.e., a population size of 30, with 500 maximum iterations.

Due to the randomness of relevant parameters, each test function was run 30 times independently. Optimized algorithm performance is usually reflected by the average value and iterative convergence curve. The stability of the optimization algorithm is reflected by the standard deviation. Therefore, the average value and standard deviation of various functions were calculated, as shown in Tables 3–11. Convergence curve is shown in Figures 4–6. Modeling and testing were done with MATLAB R2017a on an AMD Ryzen 7 PC with 16GB RAM and Windows 10. The best mean and variance results are highlighted in boldface in the tables.

4.2.   Test of high-dimensional unimodal functions

A unimodal function has only one optimum, which is both local and global, i.e., the enhancement of global search ability helps to search for the global optimum.

To minimize the impact of contingency on the solution of the function, Table 3 lists the evaluation indexes of six metaheuristic algorithms after repeated iteration for 30 times in the unimodal function.

In Table 3, ISOWOA has good adaptability and stability when dealing with unimodal functions (F1–F7). Among them, F1–F3 functions all reach the theoretical extreme value in both mean value and standard deviation. In the solutions of F4–F7, for modified variants such as EWOA and JSWOA, the enhanced algorithm improves by one or three orders of magnitude in both mean and standard deviation, which shows that ISOWOA has good convergence accuracy and stability. In addition, F5 is a typical nonconvex function. As the bottom of this function is flat, which is called a valley or banana function. It's a great tool for evaluating the merits of an algorithm. On this function, the optimization value and standard deviation obtained in this paper are the better compared with all other algorithms, which proves that the algorithm has higher optimization accuracy under the premise of ensuring stability.

4.3.   Test of high-dimensional multimodal functions

Because multimodal functions have multiple local optimal values, the optimization algorithm needs a stronger global search ability. From the test results of F8–F13 in Table 4, we see that F8, F9, and F11 found the global optimal solution. They converged to the theoretical extreme value. The test results of F12 and F13 were one to four orders of magnitude higher than those of the enhanced metaheuristic algorithm and the variants of WOA, which further confirms the improvements of the proposed strategy. The quality of the sequence set in the iterative process was well controlled.

4.4.   Test of high-dimensional fixed-dimension multimodal functions

In Table 5, ISOWOA shows good performance on fixed-dimension multimodal functions. Among the 10 functions tested, there are a total of 6 functions whose average value and standard deviation are all equaled or exceeded those of the other algorithms, they are F14, F15 and F20–F23 functions respectively.

To sum up, 19 of the 23 functions of the algorithm proposed in this paper exceeded or equaled to other algorithms. Among them, F1–F3, F8, F9, and F11 converged directly to the theoretical optimum. Other test results were very close to the theoretical extreme values, achieving the desired effect. In addition, F5 also converged to the theoretical value near 0, which is the best convergence effect for the valley function among the six algorithms. So the proposed algorithm (ISOWOA) maintained a certain stability in many aspects and had good convergence accuracy.

According to the analysis of the experimental data, we see that ISOWOA is the best among the six algorithms in terms of optimization effect and algorithm stability. This further verifies the feasibility of various strategies introduced to address the shortcomings of the algorithm in this paper.

4.5.   Convergence analysis

Due to the limited data reduction of the algorithm, only WOA ^[19], improved whale optimization (IWOA), SCA ^[36], GWO ^[37], and MFO ^[38] were selected as reference objects to draw a function convergence curve. According to the curves in Figures 4–6, we can see that the convergence speed and precision of ISOWOA are better on the 23 test functions. This is because ISOWOA enhances search abilities.

It is not difficult to see from Figure 6 that the fixed-dimension F18–F23 functions can obtain the minimum value of functions with the smallest number of iterations compared with other variant algorithms, which once again proves the powerful optimization efficiency of ISOWOA. It is noted that F20 and F22 do not show optimal performance among all variant algorithms in early iterations, but it is clear from the image that the enhanced algorithm has powerful searching ability to achieve the best optimization performance in the middle and late stages. Therefore, it can be seen that ISOWOA is a balanced algorithm with better global and local search capabilities.

4.6.   Function test results of multiple dimensions

The optimized ISOWOA was applied to the tests of the three dimensions of 100,500, and 1000 to ensure that the multi-dimensional function could run independently and had a certain stability.

The test results show that ISOWOA can solve optimization problems of large dimensions without serious dimensional disasters. Since no corresponding data are listed in the original literature ^[19], the WOA data in Table 6 are current environmental test results. EWOA does not show super-scale optimization results; so, we selected results in the corresponding literature of JSWOA ^[35] and OBCWOA ^[39]. Tables 6–11 shows the horizontal comparison results.

From Tables 6 and 7, we can see that, in the 100-dimension function test, the horizontal comparison with the results in the references shows that ISOWOA still maintains its original stability without the occurrence of dimensional disasters, and results of the functions remain near the theoretical extreme value.

In view of F5–F7, the mean value of ISOWOA is also one or three orders of magnitude better than that of modern metaheuristic algorithm and variants of WOA.

From the results of 500-dimension functions in Tables 8 and 9, we can see that the valley function still shows a good effect. Although the order of magnitude has decreased precision, compared with other algorithms, it is still closest to the theoretical value.

We can see that, F1–F3 functions still maintain the theoretical extreme value in the 1000-dimension test. It is worth mentioning that F5 and F6 functions still maintain their precision on the basis of surpassing other metaheuristic algorithms. It can be seen from Tables 10 and 11 that the powerful optimization ability of the ISOWOA can greatly make F1–F4, F9 and F11 find the optimal value. The convergence accuracy of ISOWOA is still better than that of the other four algorithms in multi-dimensional function tests. On the whole, results of 39 multi-dimensional function tests exceed other algorithms except F7. These tests showed that ISOWOA is superior at solving large-scale multi-dimensional optimization problems and maintaining a certain stability while avoiding serious dimensional disasters. In summary, ISOWOA has remarkable performance in addressing complex higher dimensional functions. Because of this, this paper considers it can be greatly applied to deal multi-constraints in DNA storage.

4.7.   Wilcoxon's rank sum test and Friedman's nonparametric rank test

Wilcoxon and Friedman tests were employed for horizontal and vertical comparisons of the mean value of ISOWOA. We used statistical method (Wilcoxon's rank-sum and Friedman's nonparametric rank) to validate the superiority and significance of the ISOWOA and to investigate the difference between our algorithm and other improved algorithms, respectively. Because there are three sets of missing data in OBCWOA ^[39] and LWOA ^[39], we only selected the other five algorithms for significance analysis. The order of each algorithm using the rank-sum test is shown in Table 12.

It can be seen from Table 12 that the rank means of the six algorithms are 1.91 (ISOWOA), 3.02 (EWOA), 3.26 (JSWOA), 4.11 (WOA), 4.63 (AGWO), and 4.07 (AWOA). The priority order is ISOWOA $>$ EWOA $>$ JSWOA $>$ AWOA $>$ WOA $>$ AGWO. We see that ISOWOA ranks first, with an obvious horizontal comparative advantage, which demonstrates its superiority and significance. Table 13 lists the test results of all benchmark functions after vertical comparison, based on analysis using IBM SPSS Statistics 26 software. Based on a large number of statistical data, the significance level was set as 0.05. The confidence interval level (CILEVEL) was set to 95%. SPSS calculated the statistics and corresponding P-values. If P is less than 0.05, two algorithms can be considered to be significantly different, and there is no statistically significant difference when P is greater than 0.05.

Hence, a small P indicates a better solution effect, i.e., the tests of our optimization algorithm have a qualitative breakthrough compared with those of modern metaheuristic algorithm and variants of WOA. Table 13 lists the P-values. Where N/S/E/I represent the overall statistical quantitative analysis that ISOWOA is superior (S), equal (E) and inferior (I) compared with other algorithms in N problems.

We see that ISOWOA had more signification compared to other algorithms. Among them, P = 0.012 when comparing ISOWOA and EWOA, indicating a statistically significant difference. In addition, compared with AWOA, the algorithm proposed in this paper has a dominant ratio of 91.3%, which is not 100% because the function has reached the theoretical extreme value and cannot be further optimized. These results conform to the intuitive results in Tables 3–5.

4.8.   Performance of ISOWOA algorithm on CEC-2015 test function set

In order to better demonstrate the proposed ISOWOA, a set of 15 real-parameter single-objective optimization problems of IEEE CEC 2015 (CEC-1-CEC-15) is considered. The efficiency of the ISOWOA is compared against improved whale optimization algorithm (IWOA) ^[40] and modified firefly algorithm ^[41]. For minimum interference, each algorithm is executed for 51 runs over three dimensions, i.e., 30, 50, and 90. The best results for all tests are in bold in Tables 14–16.

When executed on 30 and 50 dimensions, it can be clearly seen from Tables 14–16 that the proposed ISOWOA is superior to the comparison algorithm in CEC-1, CEC-2, CEC-3, CEC-4, CEC-5, CEC-9, CEC-10, CEC-12, CEC-13, CEC-14 and CEC-15 benchmark functions. In addition, from any dimension, the results obtained by the proposed algorithm on CEC-1, CEC-3, CEC-4, CEC-5, CEC-12, CEC-13 and CEC-14 functions are always equal to or exceeded all other algorithms. To sum up, the proposed ISOWOA also performs the compared algorithms on most benchmark problems. Therefore, the test function set of CEC-2015 proves the superiority of ISOWOA algorithm again.

According to the analysis of the above experimental data, through the verification of CEC 2005 and CEC 2017 standard test function sets of different dimensions and scales, it can be concluded that the ISOWOA algorithm proposed in this paper has greatly improved the convergence effect compared with the original algorithm and other similar intelligent optimization algorithms. Among them, the average value obtained by ISOWOA algorithm in the unimodal function is closer to the theoretical optimal value, and the standard deviation is stable, which indicates that the improved algorithm has stronger exploration ability and makes the result closer to the global optimal value. In the multimodal function, both the function value and the standard deviation reach the minimum, which indicates that ISOWOA algorithm still has excellent optimization ability in the limited search space, and reflects that the algorithm proposed in this paper has better stability while ensuring higher performance. In addition, in the composite function, the improved algorithm also has different degrees of competitive advantages, which shows that the algorithm also has robustness in solving global optimization problems. The above indicates that the proposed algorithm is a satisfactory optimization algorithm with good performance and stability.

4.9.   Computational complexity analysis of the ISOWOA algorithm

The computational complexity of ISOWOA algorithm includes the following three main parts:

1) Population initialization. The computational complexity of this part depends on the population size N and the population dimension D, which generally does not exceed O (N^*D). The ISOWOA pro-posed in this paper can be compared with other algorithms, which is O (N^*D).

2) Calculation of initial population fitness. The computational complexity of this part depends on the population size N and the target fitness F, which generally does not exceed O (N^*F). The ISOWOA proposed in this paper can be compared with other algorithms, which is O (N^*F).

3) In the main cycle, the computational complexity of this part depends on the number of iterations T, the population size N, the population dimension D and the target fitness F, which generally does not exceed O (T^*N^*D + T^*N^*F).

The computational complexity of the algorithm proposed in this paper depends on the population location update and fitness calculation. The population location update is determined to adopt any of the three predator-prey methods through the cycle judgment conditions. As shown in the figure, when the algorithm meets the execution conditions, the left branch is executed, that is, randomly searching prey and surrounding prey. When the algorithm does not meet the execution conditions, it executes the right branch, that is, bubble prey. The computational complexity of this part does not exceed O (T^*N^*D), and the calculation of fitness does not exceed O (T ^* N ^* F). Therefore, the computational complexity of the main cycle can be expressed as O (T^*N^*D + T ^* N ^* F), which can also be compared with other algorithms. From the above analysis, we can conclude that the time complexity of the proposed ISOWOA algorithm is equivalent to that of other algorithms.

In general, the computational complexity of the ISOWOA algorithm proposed in this paper is as follows: O (ISOWOA) = O (Initialization whale population) + T ^* O (Estimate the fitness of whales) + T^*O (Update the position of all whales). Where O (Steps to initialize whale population) = O (N), T^*O (steps to estimate the fitness of whales) = T^*O (N), and T^*O (Steps to update the position of all whales) = T^*O (N^*D). So, the total time complexity is O (ISOWOA) = O (N) + T^*O (N) + T^*O (N^*D) = O (T^*N^*D).

5.   Applications in building DNA storage codes

5.1.   DNA coding

DNA coding refers to mapping a binary string into a corresponding base sequence by a certain coding method, that is, a sequence composed of A, T, C and G. Recently a group of new concepts were designed for DNA codes. DNA coding is used in technologies such as DNA computing ^[42], DNA nanostructures, data encryption, data storage, and DNA microarray technology and image encryption ^[43]. In these applications, information is always represented by a unique sequence of DNA, and processing is accomplished by hybridization between these DNA codes. The quality of the codes directly determines the success or failure of the application. Recently a group of new concepts were designed for DNA codes. Hong et al. ^[44] used theory to construct DNA coding sets and attempted to construct them by irreducible cyclic codes. Wang et al. ^[45] designed a new image encryption scheme combined with DNA encoding using chaotic sequence and diffusion operations of a DNA matrix, which can resist common attack methods. Song et al. ^[46] proposed a conversion method to achieve a storage rate of 1.9 bit/base. This method greatly meets the requirements of low encoding complexity.

For the DNA coding problem, the current research content is mainly divided into two aspects: coding quality and coding quantity. When solving practical problems, we need to choose the coding direction according to the focus of the problem: 1) Under the condition of sufficient coding quantity, the research goal is to improve the coding quality; 2) Under the premise that the coding quality has reached the requirements, the research goal is to improve the number of codes. In general, quality optimization and the number of DNA codes often fail to achieve a win-win situation. There is no good way to solve this NP-complete problem because the number of DNA codes always decreases with increasing constraints. Recently, Nguyen et al. ^[47] designed constrained codes with error-correction capability, which were capable of correcting a single insertion / edited. wang et al. ^[48] presented novel similarity significance (SS) model to measure the similarity between DNA sequences. With this model, they constructed thermodynamically stable DNA codes using a sorting-based algorithm. The coding quality is improved at the expense of the number of codes. It has strong limitations in practical applications, and only meets certain specific scenarios without considering the DNA storage coding rate. In addition, Cao et al. ^[49] improved the DNA storage coding rate by improving the MVO algorithm. Under the fixed sequence length, more DNA sequences were screened out, which reduced the storage cost to a certain extent. Limited by the performance of the algorithm, it cannot achieve a big breakthrough in the lower bound of the DNA storage coding set. How-ever, WOA algorithm has the advantage of strong global search ability in discrete problems. Under the premise of ensuring sequence quality, it can effectively improve the number of DNA coding storage coding sets. Based on this, WOA was introduced to DNA computing to construct DNA storage codes. The ISOWOA algorithm with three novel strategies can search for codes that meet the constraints in a wider range, realizing the construction of a larger number of coding sets within a certain base length, The in-crease in the size of the coding set means that shorter DNA strands can be used to store more data, which greatly improves the coding rate of storage and reduces the cost of data storage.

For the construction of DNA storage codes, we aim to further improve the size of coding set and the coding rate under the same constraint requirements ^[49]. According to the characteristics of DNA storage coding set, this paper models the combination constraint as a multi-objective problem of the algorithm, and converts the DNA sequence from A, T, C, G to 0, 1, 2, 3. Secondly, in order to match the transformation mechanism, the original continuous whale optimization algorithm is discretized. Finally, the improved ISOWOA is applied to screen the DNA storage coding sets that meet the four constraints of uncorrelated address, edit distance, no run length, and GC content.

5.2.   Constraints of DNA storage coding set

The constraints of DNA coding sets are categorized as combinatorial ^[50], application-oriented, and thermodynamic ^[51]. Combinatorial constraints include Hamming distance (HD), GC-content, forbidden constraints, and so on. Application-oriented constraints include uncorrelated and run-length constraints. Thermodynamic constraints include free energy, melting temperature, and minimum energy constraints. Our experiments have shown that reliable DNA codes designed with uncorrelated address, edit distance, no run-length, and GC-content. The experimental results show that the number of multi-constraint storage codes with different lengths constructed in this paper increases by 2–18%, reaching or exceeding the previous optimal construction ^[49].

5.2.1.   Editing distance constraint

The minimum edit distance (MED), or levenshtein distance, is the minimum operand required to convert one string to another. We set the minimum editing distance ^[49] as a similarity calculation function, which is used for the construction of DNA storage codes. There are two strings in $V$, and $uandv$ satisfy

where $d$ is an integer, and $\eta$ is the set of editing distance constraints for DNA sequences.

By introducing editing distance to the construction of a DNA storage code, problems, such as substitution, insert, and delete in nanopore sequencing technology, are well solved. Sequencing errors are minimally avoided. $G\left(u, v\right)$ represents the editing distance between $u$ and $v$. The objective function is

where $\mathrm{U}\mathrm{E}\left({u}_{i}\right)$ defines the minimum $G\left({u}_{i}, {v}_{j}\right)$.

5.2.2.   GC-content constraint

DNA computing requires stable and uniform DNA molecules, composed of A, T, C, and G bases. GC content is the ratio of guanine and cytosine in four DNA bases in a DNA sequence, and the content constraint must meet the range in chemical determination, generally $40\le GC\le 60$. Thus, we set a standard of $50$ for the sequence of GC-content.

For a sequence of length $s$, $GC\left(s\right)$ can be expressed as ^[49]:

where $\left|G+C\right|$ is the fixed number that are either G or C within each code.

5.2.3.   Sub-subheading

Run-length (RL) is the length formed by the repeated occurrence of each base in a data stream composed of sequences. Given the nature of DNA molecular synthesis and sequencing, repeated bases may lead to the failure of an experiment. For example, in ACGGGT, G is repeated; this sequencing can be misinterpreted as ACGT or ACGGT, which will lead to reading and writing errors. The constraint is defined as ^[49]

where ${S}_{i}$ is a DNA sequence $S({S}_{1}, {S}_{2}, {S}_{3}, \dots, {S}_{n})$ of length $n$.

5.2.4.   Uncorrelated address constraint

In computer science, basic units of memory used for data access are assigned unique serial numbers, also known as memory addresses, which refer to specific locations in a system. In DNA computing, to recover data information stored by DNA, molecules in the reaction pool must be prefixed with a specific address. Address sequences must not be similar, to avoid failed retrieval of data block information. Uncorrelated address constraints are defined as follows.

In sequences $L({l}^{1}, {l}^{2}, {l}^{3}, \dots {l}^{s})$ and $H({h}^{1}, {h}^{2}, {h}^{3}, \dots, {h}^{n})$, the suffix of $L$ cannot appear as the prefix of $H$, and vice versa ^[52].

Assuming that we define an uncorrelated address constraint distance as 3, then CTAGAT and CGACTA cannot occur together in the entire sequence pool, because CTA is a related character ^[49]. The coding set B obtained by the uncorrelated address constraint can not only eliminate cross-hybridization between addresses but can also avoid sequence selection errors in the sequencing process.

5.3.   Bounds on DNA storage codes

The steps of constructing DNA storage codes are as follows:

1) The required parameters and DNA sequence are initialized. Then, WOA is discretized. By evaluating their fitness, current optimal solution is screened out, and DNA sequences satisfying the constraint are incorporated to form the first-generation population.

2) The populations are sorted in order of fitness, by using the correlation to select the individuals and dimensions to be opposed.

3) The updated population is involved in iterative optimization, and the optimized result is taken as the input to determine whether the constraint conditions are met. If so, it is incorporated, otherwise iterative optimization is continued.

4) Finally, when the maximum number of iterations is reached, the DNA storage coding set is outputted.

Superscripts are presented in Table 17, where $d$ represents DMVO ^[49] and $i$ represent ISOWOA. In Table 18, ${A}^{GC, NL, UA}(n, d)$ represents a DNA coding set, which satisfies the editing distance, GC-content, no run-length, and uncorrelated address constraints. This value for ${A}^{GC, NL, UA}(n, d)$ represents the maximum number of DNA storage codes constructed by ISOWOA, satisfying the same constraints, where $d$ represents the storage editing distance, and $n$ represents the length of the DNA storage coding. From the perspective of biological computing, we aim to screen out more DNA storage codes with the same combinatorial constraints.

In fact, the combinatorial constraints applied in this paper can be regarded as a multi-objective application. Through the previous tests, it is verified that the ISOWOA proposed in this paper has strong equilibrium ability in solving multi-objective optimization problems. Because of this, ISOWOA is introduced as a method to construct the DNA storage coding set, and the reliability of the algorithm in practical application is further discussed.

In Table 18, we see that under the same constraints, the number of different length coding sets constructed by ISOWOA all equaled or exceeded DMVO algorithm. The lower bounds generally increased by 2–18%, which shows that our work has been significantly improved compared with that of our predecessors. If the sequence length is equal to 5, 6, 7, 8, 9, 10, the coding lower bound of the proposed algorithm has been broken through. It is worth noting that if $n = 10$ and $d = 6$, the number of DNA storage codes in our result is 18% higher than that in the optimal result of DMVO, meeting the evaluation index of the DNA sequence coding set.

In addition, the experimental data also show that the advantages of the algorithm are more significant with the increase of sequence length. When the editing distance constraint value is defined as 3, we can find that the lower bounds of DNA sequence length of 7, 8 and 9 constructed by the algorithm are increased by 5.7, 7 and 8% respectively. And the corresponding coding rate $R = log^4M/n$ is also increased by more than 1%. If d = 3, our coding rate at n = 9 (0.416) exceeds that at n = 10 (0.403), which also means that the algorithm can effectively reduce the synthesis cost of sequences under the same performance requirements. As expected, the enhanced algorithm shows good performance. The results confirm the applicability of ISOWOA to biological computing.

Finally, the non-payload DNA storage coding set after selection can avoid insertion, deletion, and replacement errors to the greatest extent in the process of nanopore sequencing. Based on this storage coding set, access to large DNA files can be successfully completed in the fourth generation of nanopore sequencing.

6.   Conclusions

In dealing with optimization problems, the whale optimization algorithm has the drawback that local optimal solutions are prone to precocious convergence, i.e., it is assumed to be the best solution when the global optimal solution has not been found. Based on this, the proposed algorithm integrates the strategies of enhanced quasi-opposition learning, a nonlinear convergence factor, and a new time-varying inertia weight with collaborative convergence factor, giving it a stronger search ability in the whole algorithm optimization stage. The adaptability and convergence precision of each iteration are improved, and the inherent defect of premature convergence is eliminated, so that it becomes an equilibrium algorithm. Through 38 benchmark functions, the proposed algorithm was compared to modern metaheuristic algorithm and variants of WOA on test cases based on multiple dimensions, number of iterations, mean value, and variance. The experiment shows that the results of 17 functions of CEC 2005 obtained by ISOWOA were obviously better than those of EWOA in terms of mean and standard deviation, and the results of another four functions were the same. In addition, the algorithm is superior to other algorithms in 11 functions in the test function set of CEC 2015, which again proves the superiority of ISOWOA algorithm. In biological computing, based on the same combinational constraints, the multi-constraint DNA storage coding set constructed by ISOWOA has a better solving effect than DMVO. The results show that the number of DNA storage codes filtered by ISOWOA increased by 2–18%, and the coding set can realize access to DNA files in biological experiments.

In future work, we will take DNA storage coding as the main research direction and apply various nature-inspired algorithms to address optimization problems, such as machine learning, engineering problems, networks, and benchmark functions.

Acknowledgments

This work is supported by the National Key Technology R & D Program of China (No. 2018YFC0910500), the National Natural Science Foundation of China (Nos. 61425002, 61751203, 61772100, 61972266, 61802040), LiaoNing Revitalization Talents Program (No. XLYC2008017), the Innovation and Entrepreneurship Team of Dalian University (No.XQN202008), Natural Science Foundation of Liaoning Province (Nos. 2021-MS-344, 2021-KF-11-03, 2022-KF-12-14).

Conflict of interest

The authors declare there is no conflict of interest.