One of the heuristic optimization methods that implements the simulation of an artificial immune system is discussed in this article. The list of optimization problems, their classification and known approaches of solving those ones are reviewed on the whole. The research of the main settings of operators in the proposed algorithm is applied to the different dimensions test problems. For the first time, an attempt of finding a universal approach of solving both combinatorial and continuous problems, applying the proposed algorithm, was implemented based on the common approach to the algorithm operators. The most efficient settings, based on the minimum solution search time criteria, are recommended for agent generation search, parental individuals selection, mutation, crossover, local search and population compression operators. Artificial immune systems, AIS, algorithm, optimization, heuristic method, mutation, Saaty
selection, combinatorial problems
Optimization problem solving in terms of the multicomponent industrial production is considered to be a daily practice. Decision makers are to incorporate several criterias, which are generally ranged by their significance, and to solve the problems in the multidimensional space. One of the mechanisms that allow solving this kind of complex mathematical problems is evolutionary decisionmaking technologies.
A feature of evolutionary technologies is the heuristic (usually not due to mathematical establishment) nature of the decision-making algorithm, which can be improved, using new, more effective in practice heuristics. Many of them belong to analogical methods - a tool of applied systems analysis, which is used for study and simulation of complex systems analogously to biological or inorganic nature.
One of described heuristics is an artificial immune systems simulation algorithm, which allows
finding a solution of the conditional or unconditional optimization problem, using a combination of
evolutionary operators that simulate the human immune system. A detailed analysis of artificial
immune system simulation algorithms applied to optimization problems solving is given in [
2021 Copyright for this paper by its authors.
Modeling artificial immune system (AIS) is a method of computable intelligence that uses the
analogy with one of the natural systems, namely the human defense system. As artificial neural
networks, artificial immune systems can learn new information, recall previously learned information,
and perform pattern recognition in a highly decentralized manner. In [
In research [
Authors [
Many efforts have been made by various researchers to increase the search effectiveness of AIS on
the different sides, namely: helping population diversity, adaptive parameters control, etc. Authors [
Instead, at work [
Previously with AIS, namely using an approach of clonal selection, resolve a combinatory problem
of optimal choice a carrier of the plurality outdoor advertising offers, available in the formulation of
the knapsack problem [
Also, an algorithm founded on clonal selection was used in [
Another approach also based on learning while working propose authors [
Similar principles use one recent research [
The idea of involvement local search to the modeling artificial immune system algorithm based on
the clonal selection use one of author's researches [
Summing up, mark the following features of modern algorithms that use AIS for modeling for solving optimization problems: applying different selection operators significantly improves search speed and effectivity; a new generation must create partially using crossover, not through only cloning; must use different mutation operators, and radius (size of surroundings) should be determined during the working of the algorithm (learn); not enough attention to compressed population operators, that determine the diversity of the new generation. 2.2.
Majority mentioned ideas is incorporated in the Hybrid Immune Network Optimization algorithm
with Saaty selection and Fibonacci search [
3. Depending on the cells' adaptability assessment of the current generation, the number of clones is assigned for each cell of the current generation - it is the selection operator.
4. Cloning of cells in an amount is determined by the selection operator. 5. Recombination of cloned individuals by using the operator of probability crossover. 6. Calculation the dynamic probability of mutation for clones and implementation of adaptive mutation operator.
7. Execution of the one-dimensional local search for each clone with a certain probability. The method of golden ratio (Fibonacci) for a random coordinate is used in continuous problems and hill climbing method is used in combinatorial problems instead – it is local search operator.
8. Compression of the general population of parents and clones using the appropriate to a specified level Np – it is compression operator. Memorizing the best of solution, if it has not occurred before.
9. Destruction of cells, whose age has reached the set value , from the current generation. Their place in the main population is occupied by cells, randomly generated uniformly in the search area.
10. The counter of generations increments = + 1. Go to the step 2. 11. The output of the current generation as a set of suboptimal solutions. 12. Stopping the algorithm.
Block diagram of the algorithm is shown in Figure 1. This algorithm research, its limitations, and optimal configuration of its operators are dedicated to the study. 2.3.
The foresaid Hybrid Immune Network Optimization algorithm was investigated both for solving
problems in an infinite space and for solving combinatorial kind of problems. The last one is
described in detail, following [
The other one combinatorial applied optimization problem is the steel amount minimization
problem which provides the steel order size limit of the only one cast volume [
In addition to reviewed applied problems, several test sets of various sizes and complexity were
used, which describe the knapsack problem, the minimum vertex cover problem, and the set partition
problem. All the problems are formulated according to the classic statements. All while in both case
of problem [
The test problems of Rastrigin, Ackley, Rosenbrock, and others considered in [
An additional factor that was studied in solving both combinatorial and continuous problems was the number of calls to the objective function. This factor is significant in case of the machine costs, especially in solving combinatorial problems, where the calculation of the objective function is based on matrix multiplication.
This issue is devoted to solving a number of applied and test problems using the algorithm described. The settings of algorithm operators that provide better convergence and search speed for the known optimal solutions are found. 3.1.
In any population-based global optimization algorithm like partial swarm optimization (PSO), evolution strategy (ES), GA, or AIS and among others a pseudo-random number generator is used to sample the first individuals of the initial generation from a uniform probability distribution (0; 1). If its generation power N is smaller than 103 – 104, it results in too nonuniform mesh.
The same authors suggest using quasi-random numbers, which have better homogeneity than
pseudo-random numbers [
The Halton sequence and the Hammersley set define two deterministic ways of sampling a Ddimensional space so that the consecutive points are as far apart as possible from each other. In essence, the Halton sequence and the Hammersley set are both a generalization of the Van der Corput sequence for multidimensional cases.
Sobol sequences are another widely used quasi-random number generator, which was invented by
Ilya M. Sobol back in 1967. This quasi-random number generator uses a base of 2 to generate
(0; 1), to then perform a special re-ordering of the master sequence for each one of the dimensions
of the sampled hyper-space [
The Figure 2 shows compared 1000 points in 2-dimension space from pseudo-random sample (top left), from the Halton sequence (top right), from the Hammersley set (bottom left) and from the Sobol sequence (bottom right). Quasi-random sequences cover the space more evenly than pseudo-random.
We applied the described generators in the algorithm shown in Figure 3 to the set covering
problem scpcyc07 from OR-Library (selection the minimum number of subsets from the 672 available
to cover the set of 448 graph vertices. Each subset contains exactly 4 vertices) [
Dimension of space
25 65 10 136 1702 118 1476 86 1099 111 1375 103 1258 84 1005 10274 11320 9920 9811 8917 8497
100 64987 103951 68357 61159 51478 66123
Table 1 contains comparing same pseudo-random and quasi-random generators for Rastrigin problem solving at 10, 25, 65 and 100 dimensions of continuous space. Instead, Figure 3 shows the time dependence of the best solution of the sets covering problem for the first 10,000 iterations.
All quasi-random generators show better result than pseudo-random generators. This result is also proved by increasing the dimension of the problem when filling the solution space becomes an important factor. Using of quasi-random generators accelerates on average the search for the global optimum by 12-20% of the time. 3.2.
One of the main factors that determine the efficiency of the optimization algorithm, based on the
artificial immune system, is the choice of parental individuals used to obtain clones. In [
]. The rating of each of candidate j is calculated by
= 1 + ⌊ ( ) ∙ ⌋, where k - the dimension of the scale (default k = 9). 1/ is used, and for the rest -
= 1 / 1 .
Construction of a matrix of pairwise comparisons for the first line of which an expression 1 = of the current generation.
The HINO-SF algorithm analysis with the described selector resulted in some limitations:
with a small population among potential parents there are 1 or 2 applicants, the solution of
which is better than the average value of the segment [
;
];
among the clones, the total majority (or all) will be descendants of one of the representatives
In fact, the selection operator described in [
A modified selector, based on the method of Saaty’s pairwise comparisons, also described in [
The calculation of the membership function is as follows:
| − | + 1, ≥ = { 1 ( ( )) = √∏
. , < =1 (1) (2) (3)
The most wide-spread types of selectors, such as rank (ordinal) and tournament (roulette), were
used for comparison of several problems solving, as well. Competitive ones are proved to be highly
efficient among other evolutionary algorithms - GA [
The comparison of these selection operators is demonstrated in Table 2. In this table, the selection operators are compared by two main factors: the number of iterations (generations) to the first global optimum occurrence and the number of calls to the objective function. Both values are calculated on average over 10 runs with different random initial values. Both combinatorial and continuous problems, as well as different dimensions are considered.
According to the results in Table 2, the following conclusions can be outlined: • The proposed selection operator based on the Saaty’s scale pairwise comparisons method is equally effective in both binary and continuous space;
• In some problems (minimum graph tree, Ackley problem) the proposed selector shows a higher efficiency than the tournament 1.5 - 3 times). The rest of the problems use the same time and access to the target function. 3.3.
The proposed AIS algorithm mainly differs from other analogues on the application of an adaptive crossover operator to clones, which involves the exchange of genetic information. It is to diversify the search for the best solution in the algorithm. Therefore, the more successfully it will perform, the greater speed is to find the global optimum. The choice of crossover type depends on the space in which it is applied to. The combinatorial problems were solved with approaches which differ from other ones applied to the solutions of continuous problems. The most essential factors for evaluating the solutions efficiency are the time spent searching for a solution and the value of the deviation of the objective function from the known global optimum.
Having used the selection, founded on modified Saaty operator, as well as the standard values of the mutation operators (their settings are drawn below) the previously described binary crossovers are compared. One-point, two-point and uniform crossovers were considered.
A comparison of the solution determining speed (in the number of iterations) and the deviation from the exact solution (in percent) is illustrated in Figure 4. The data in the figure is averaged over 10 runs with random initial populations.
According to the results, the two-point crossover happens to be the best for all combinatorial problems solutions. On the one hand, it collects the most detail about the parental genes (as well as the single-point crossover), but also provides some diversification due to two breaks in the genome. At the same time, offspring, produced with a uniform crossover, significantly differs from each of the parents for considered problems. The solutions are discarded in the new search area and in most cases are much worse than the parental individuals, so they are no longer used.
Particular attention was paid to the probability , which the crossover is applied to the newly formed clone with. In a wide range from 0 to 0.9 (sometimes up to 0.95), higher probability values resulted in a faster search for the global optimum regardless of problem type and its dimension. At the same time, while = 1, the search efficiency drops rapidly. Therefore, the crossover operator is recommended to use with probability differs from 1.
Having applied the selection founded on the modified Saaty operator, the generation value =
5, the number of offsprings = 50, the adaptive mutation operator described in [
A comparison of the solution determining speed (in the number of iterations) and the deviation from the exact solution is illustrated in Figure 5. The data in the figure is averaged over 10 runs with random initial populations.
Analysis of the results in Figure 5 proves that the Laplace and heuristic crossovers perform 2-2.5
times more iterations, while not providing a sufficient quality result on different problems of various
dimensions. The SBX crossover, which is used in the basic algorithm [
Meanwhile, a uniform crossover, which selects the parental genes with equal probability, resulted
in higher values of accuracy on large-scale problems. Similar results were obtained earlier in the study
of optimal settings of genetic algorithms [
The main operator responsible for finding a solution in the proposed algorithm, as in most implementations of the method of artificial immune systems, is the mutation operator. An adaptive operator, which randomly applies either a narrow mutation to search in the current solution neighborhood, or a broad mutation to change the search area, is proposed. As in the case of the crossover operator, the mutation operator form significantly depends on the space, where the problem is solved. The choice of mutation range performance (wide or narrow) is based on the usefulness assessment of the current cell on the utility assessments scale on the current iteration throughout the population. The scale is determined for each j-th cell individually with the formula = (1 −
)
− − , = [1: ], (4) where − clone number in the population of clones; – clone population size; − current iteration number; − provided maximum number of iterations; − the worst value of the objective function in the generation;
− the best value of the objective function in the generation; − the value of the objective function for the current clone; − the maximum allowable proportion of broad mutations in the total.
If a random (0; 1) is less than transition to a new search area. clone j (search in the solution neighborhood). Otherwise - a broad mutation is performed - the
For continuous space, it is proposed to use a combination of a broad Gaussian mutation and a
narrow polynomial distribution mutation. Both are described in detail in [
following (4), a narrow mutation is performed for
Having analyzed formula (4), it is easy to notice that the best representatives in the generation at the initial stage of the algorithm are prone to narrow search mutations, at the final - to wide. Instead, the worst members of the generation almost always perform only broad mutations. The dependence of the characteristic against the current iteration number, the clone adaptability degree and the admissible maximum proportion of wide mutations is illustrated by the graph in Figure 6.
Analyzing the obtained dependences, it is noticeable that in case of low γ values the worst clones in the population are almost always make a wide mutation, and successful clones make a narrow mutation. Increasing the dimension, the mutation nature choice is changing significantly. In multidimensional continuous space in case γ = 0.9 at the beginning of the calculation, the clones behave similarly to that described above. As we approach the end of the calculation, the proportion of narrow mutations decreases even for the best of the clones by 10 times.
When solving combinatorial problems, a point mutation of a certain number of genes is performed as a narrow mutation. The number of inverted genes is determined with the formula ( ) = { (1 + 0 − , 2 ∙ 0 ) , < ⁄2 ,
(5)
≥
⁄2
bits); 0
recommended 0
where t - number of current iteration;
– the minimum level of mutation (usually 1 or 2
– the prior probability of mutation operator using (global parameter of algorithm, in [
– maximum number of generations.
Then, regardless of the time of algorithm on the initial iterations mutation will be per-formed for all clones, on final - less than for a half of them.
Extensive mutation in combinatorial problems can be realized through saltation. It is the process of the exchange between a certain number of bits, which are located at a certain distance from each other in the genome. Saltation mutation is effective due to its saving the total number of 0 and 1 in the genotype, thus not rejecting the current solution too far in the search space.
The mutation radius adapting issue in continuous space remains to stay opened. For today, the authors do not manage to substantiate any pattern. The best solution time and accuracy are achieved with different settings for various problems and multidimensional space. 3.5.
One-dimensional local search, proposed in [
The topic of further research should be such a goal-oriented local search operator determination that would improve the objective function of a random descendant without spending significant computation time.
At the same time, the HINO-SF algorithm works effectively without the local search applying for
combinatorial problems solving. The limited local search based on the hill climbing method is
proposed earlier in [
The population compression operator determines the success of finding solutions in the paradigm
of artificial immune systems. It prevents premature convergence and coming to a halt in local
optimums, which is inherent in all evolutionary algorithms. In most sources [
It is proposed to link the similarity radius with the offspring mutation radius in the current generation. Thus, the mutation operator will operate in the current solution neighborhood, and the population compression operator - outside it. This ensures diversity in each of the generations. The main operator, which is responsible for the search intensification, as in most implementations of the artificial immune systems method, continue to be the mutation operator in any case. At the same time, the population compression operator assumes the role of diversifier.
Solving continuous problems, it was found that the optimal value of the compression operator radius is getting greater meanwhile space dimension is increasing. Optimality should be understood as the speed of global optimum achieving while maintaining population diversity. The dependence of the compression radius on the space dimension in solving the Rastrigin problem is shown in Figure 7.
Also, in Figure 7 it is clearly noticeably the best of several dozen regression models that describe the dependence of the compression operator radius on the space dimension. The power model with a power coefficient close to ½ is obtained. Therefore, the desired dependence can be assumed to have the form ( ) = 0 2√ , (6) where –problem dimension in continuous space ; 0 – a constant term, depending on the problem type and must be obeyed empirically.
In addition to that, the tendency illustrated in Figure 6 was not refuted, but also received an extra development. In particular, scaling the knapsack problem and using different numbers of individuals in the population, it was found that the best results in terms of convergence and repeatability are provided by the use as a coefficient in (6) the value
0 = 1⁄ (7)
Thus, it is further recommended to set the radius in the population compression operator proportional to the radical of the space dimension and inversely proportional to the population individuals number.
Based on the results of numerous experiments in solving known global optimization problems, the developed HINO-SF algorithm was investigated for its individual operators effectiveness. The following results were obtained: • Applying of quasi-random generators instead of pseudo-random ones for first and new individuals generation during the algorithm reduces the global optimum searching time by 12-20%.
• Adopting of the modified selection operator, based on the Saaty`s paired comparison method, allows to improve the solution finding dynamics by 1.5-3 times, comparing with the previous realization and to achieve greater reliability than in case of the rank or tournament selection operators using.
• The global optimum finding becomes more reliable applying the crossover operator. The twopoint crossover is the best for combinatorial problem, uniform crossover – for continuous problems relatively.
• The proposed adaptive mutation operator adjusts the narrow and wide mutations ratio, depending on the clone fitness and the iteration number. As soon as the space dimensionality increases, the proportion of wide mutations should be increased.
• The existing one-dimensional local search operator is considered to be ineffective and should be replaced. Applying one of the quasi-Newtonian methods instead of the zero-order methods might be promising.
• The population compression operator should be adaptive, considering the mutation radius at the current iteration, population size and space dimension.
The work [
The search for the global optimum and several local optimal solutions close to global one, which can be used as an effective alternative, is an essential scientific and technical problem. Its solution, using a developed and investigated optimization algorithm based on an artificial immune system modeling might make specific social and economic impact.
The article includes the investigation of the global optimization algorithm based on artificial immune systems modeling and the most effective settings of its individual operators. For the first time, an attempt of finding a universal approach to solving both combinatorial and continuous problems applying the proposed algorithm was implemented, using a common approach to the algorithm operators.
The most efficient settings, based on the minimum solution search time criteria, are recommended for search agent generation, parental individuals selection, mutation, crossover, local search and population compression operators.
A significant reduction in the number of objective function evaluations and the algorithm performance time was achieved. It allowed the proposed algorithm to become competitive towards other widely used global optimization methods. The proposed settings of the algorithm operators allow to reduce the optimization time by 2-4 times without losing accuracy for some solving problems.
The set of several test functions of various dimensions in continuous and binary spaces was used for the algorithm testing, which demonstrated in improved time criteria performance. It is reasonable to outline that the greatest benefits from algorithm settings usage can be obtained in large dimension problems.
The practical value of the work is to make possible the developed algorithm applying for global optimization problems solving, especially in case of a high dimension mathematical model of a problem. In particular, the approach can be applied to solve planning and control problems in metallurgical production to optimize technological processes.
The direction of further research is the best local search operator selection as well as the adaptation mechanism formation of the mutation operator as the main search element of the AIS optimization algorithm. Other essential research direction is the formation of an adaptive population compression operator, which would help to discover suboptimal solutions.
This publication was prepared as a part of the scientific theme 0121U109788 "Problems of modeling, optimization, and decision making in complex systems of different nature", which is implemented on the System Analysis and Control Department at Dnipro University of Technology.