Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency
In solving practically significant problems of global optimization, the objective function is often of high dimensionality and computational complexity and of nontrivial landscape as well. Studies show that often one optimization method is not enough for solving such problems efficiently - hybridiza...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
MGTU im. N.È. Baumana
2018-01-01
|
| Series: | Matematika i Matematičeskoe Modelirovanie |
| Subjects: | |
| Online Access: | https://www.mathmelpub.ru/jour/article/view/90 |
| _version_ | 1818268510270259200 |
|---|---|
| author | M. K. Sakharov A. V. Ponorenko |
| author_facet | M. K. Sakharov A. V. Ponorenko |
| author_sort | M. K. Sakharov |
| collection | DOAJ |
| description | In solving practically significant problems of global optimization, the objective function is often of high dimensionality and computational complexity and of nontrivial landscape as well. Studies show that often one optimization method is not enough for solving such problems efficiently - hybridization of several optimization methods is necessary.One of the most promising contemporary trends in this field are memetic algorithms (MA), which can be viewed as a combination of the population-based search for a global optimum and the procedures for a local refinement of solutions (memes), provided by a synergy. Since there are relatively few theoretical studies concerning the MA configuration, which is advisable for use to solve the black-box optimization problems, many researchers tend just to adaptive algorithms, which for search select the most efficient methods of local optimization for the certain domains of the search space.The article proposes a multi-memetic modification of a simple SMEC algorithm, using random hyper-heuristics. Presents the software algorithm and memes used (Nelder-Mead method, method of random hyper-sphere surface search, Hooke-Jeeves method). Conducts a comparative study of the efficiency of the proposed algorithm depending on the set and the number of memes. The study has been carried out using Rastrigin, Rosenbrock, and Zakharov multidimensional test functions. Computational experiments have been carried out for all possible combinations of memes and for each meme individually.According to results of study, conducted by the multi-start method, the combinations of memes, comprising the Hooke-Jeeves method, were successful. These results prove a rapid convergence of the method to a local optimum in comparison with other memes, since all methods perform the fixed number of iterations at the most.The analysis of the average number of iterations shows that using the most efficient sets of memes allows us to find the optimal solution for the less number of iterations in comparison with the less efficient sets. It should be additionally noted that there is no dependence of the total number of the algorithm iterations on the number of memes used.The study results demonstrate that the Hooke-Jeeves method proved to be the most efficient for the chosen functions, since its presence in a set of memes allows a significantly improving quality of the solution obtained. At the same time, the results of statistical tests show that the use of additional methods in a set of memes often has no significant effect on the results of the algorithm. |
| first_indexed | 2024-12-12T20:39:38Z |
| format | Article |
| id | doaj.art-cff8f34e1b7a4c2882cb10fef32cc7b8 |
| institution | Directory Open Access Journal |
| issn | 2412-5911 |
| language | Russian |
| last_indexed | 2024-12-12T20:39:38Z |
| publishDate | 2018-01-01 |
| publisher | MGTU im. N.È. Baumana |
| record_format | Article |
| series | Matematika i Matematičeskoe Modelirovanie |
| spelling | doaj.art-cff8f34e1b7a4c2882cb10fef32cc7b82022-12-22T00:12:47ZrusMGTU im. N.È. BaumanaMatematika i Matematičeskoe Modelirovanie2412-59112018-01-0106708210.24108/mathm.0617.000009087Investigating the Multi-memetic Mind Evolutionary Computation Algorithm EfficiencyM. K. Sakharov0A. V. Ponorenko1Bauman Moscow State Technical University, MoscowBauman Moscow State Technical University, MoscowIn solving practically significant problems of global optimization, the objective function is often of high dimensionality and computational complexity and of nontrivial landscape as well. Studies show that often one optimization method is not enough for solving such problems efficiently - hybridization of several optimization methods is necessary.One of the most promising contemporary trends in this field are memetic algorithms (MA), which can be viewed as a combination of the population-based search for a global optimum and the procedures for a local refinement of solutions (memes), provided by a synergy. Since there are relatively few theoretical studies concerning the MA configuration, which is advisable for use to solve the black-box optimization problems, many researchers tend just to adaptive algorithms, which for search select the most efficient methods of local optimization for the certain domains of the search space.The article proposes a multi-memetic modification of a simple SMEC algorithm, using random hyper-heuristics. Presents the software algorithm and memes used (Nelder-Mead method, method of random hyper-sphere surface search, Hooke-Jeeves method). Conducts a comparative study of the efficiency of the proposed algorithm depending on the set and the number of memes. The study has been carried out using Rastrigin, Rosenbrock, and Zakharov multidimensional test functions. Computational experiments have been carried out for all possible combinations of memes and for each meme individually.According to results of study, conducted by the multi-start method, the combinations of memes, comprising the Hooke-Jeeves method, were successful. These results prove a rapid convergence of the method to a local optimum in comparison with other memes, since all methods perform the fixed number of iterations at the most.The analysis of the average number of iterations shows that using the most efficient sets of memes allows us to find the optimal solution for the less number of iterations in comparison with the less efficient sets. It should be additionally noted that there is no dependence of the total number of the algorithm iterations on the number of memes used.The study results demonstrate that the Hooke-Jeeves method proved to be the most efficient for the chosen functions, since its presence in a set of memes allows a significantly improving quality of the solution obtained. At the same time, the results of statistical tests show that the use of additional methods in a set of memes often has no significant effect on the results of the algorithm.https://www.mathmelpub.ru/jour/article/view/90global optimizationmulti-memetic algorithmsmind evolutionary computation algorithm |
| spellingShingle | M. K. Sakharov A. V. Ponorenko Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency Matematika i Matematičeskoe Modelirovanie global optimization multi-memetic algorithms mind evolutionary computation algorithm |
| title | Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency |
| title_full | Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency |
| title_fullStr | Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency |
| title_full_unstemmed | Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency |
| title_short | Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency |
| title_sort | investigating the multi memetic mind evolutionary computation algorithm efficiency |
| topic | global optimization multi-memetic algorithms mind evolutionary computation algorithm |
| url | https://www.mathmelpub.ru/jour/article/view/90 |
| work_keys_str_mv | AT mksakharov investigatingthemultimemeticmindevolutionarycomputationalgorithmefficiency AT avponorenko investigatingthemultimemeticmindevolutionarycomputationalgorithmefficiency |