Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.85
BINARY GENETIC ALGORITHM USING EDA-BASED PROBLEM DECOMPOSITION FOR LARGE-SCALE GLOBAL OPTIMIZATION
E. A. Sopov
Reshetnev Siberian State Aerospace University 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation
In recent years many real-world optimization problems have had to deal with growing dimensionality. Such optimization problems, that are called large-scale global optimization (LSGO) problems, contain many hundreds or thousands of variables and are not separable. Moreover, many real-world problems are usually complex for detailed analysis, thus they are viewed as the black-box optimization problems. Thus, we can use the “blind” search techniques only. The most advanced techniques for LSGO are population-based stochastic search algorithms and are based on cooperative coevolution schemes using the problem decomposition via variables. These algorithms are mainly proposed for the real-valued search space and cannot be applied for problems with discrete or mixed variables. In this paper a novel technique is proposed, that uses a combination of a binary genetic algorithm (GA) and an estimation of distribution algorithm (EDA). The GA is used for solving the main optimization problem, and the EDA is used for collecting statistical data based on the past search experience to provide the problem decomposition by fixing perspective genes in chromosomes. The proposed EDA-based decomposition technique has the benefits of two general LSGO concepts: the random grouping methods and the dynamic learning methods. A standard implementation of the EDA-based decomposition GA and an implementation using the island model for parallel computing are discussed. The results of numerical experiments for benchmark problems from the IEEE CEC competition on the LSGO are presented. The experiments show that the approach demonstrates efficiency comparable to other advanced techniques. At the same time, the proposed approach can be applied for LSGO problems with arbitrary variables as it uses the binary representation of solutions.
Keywords: binary genetic algorithm, estimation of distribution algorithm, problem decomposition, large-scale global optimization, LSGO, GA-EDA.
References

1. Mahdavi S., Shiri M. E. Rahnamayan Sh. Metaheuristics in large-scale global continues optimization: A survey. Information Sciences. 2015, Vol. 295, P. 407–428.

2. Potter M., De Jong K. A. Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evol. Comput. 2000, No. 8 (1), P. 1–29.

3. Yang Zh., Tang K., Yao X. Large scale evolutionary optimization using cooperative coevolution. Inform. Sci. 2008, No. 178 (15), P. 2985–2999.

4. Liu J., Tang K. Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution. In Intelligent Data Engineering and Automated Learning – IDEAL. 2013, P. 350–357.

5. Omidvar M. N., Li X., Mei Y., Yao X. Cooperative co-evolution with differential grouping for large scale optimization. IEEE Trans. Evol. Comput. 2014, No. 18 (3), P. 378–393.

6. Dong W., Chen T., Tino P., Yao X. Scaling up estimation of distribution algorithms for continuous optimization. IEEE Trans. Evol. Comput. 2013, No. 17 (6), P. 797–822.

7. Wang Y., Li B. A restart univariate estimation of distribution algorithm: sampling under mixed gaussian and lévy probability distribution. In IEEE Congress on Evolutionary Computation, CEC 2008 (IEEE World Congress on Computational Intelligence). 2008, P. 3917–3924.

8. Sopov E., Sopov S. The convergence prediction method for genetic and PBIL-like algorithms with binary representation. In IEEE International Siberian Conference on Control and Communications (SIBCON 2011). 2011, P. 203–206.

9. Gonga Y.-J., Chena W.N., Zhana Zh.-H., Zhanga J., Li Y., Zhange Q., Lif J.-J. Distributed evolutionary algorithms and their models: A survey of the state-of-the-art. Applied Soft Computing. 2015, No. 34, P. 286–300.

10. Sopov E. A Self-configuring Metaheuristic for Control of Multi-Strategy Evolutionary Search. ICSI-CCI 2015, Part III, LNCS 9142, 2015, P. 29–37.

11. Semenkin E. S., Semenkina M. E. Selfconfiguring Genetic Algorithm with Modified Uniform Crossover Operator. Advances in Swarm Intelligence. Lecture Notes in Computer Science 7331. Springer-Verlag, Berlin Heidelberg, 2012, P. 414–421.

12. Li X., Tang K., Omidvar M.N., Yang Zh., Qin K. Benchmark functions for the CEC 2013 special session and competition on large-scale global optimization. Technical Report, Evolutionary Computation and Machine Learning Group, RMIT University, Australia, 2013.

13. Test suite for the IEEE CEC’13 competition on the LSGO. Available at: http://goanna.cs.rmit.edu.au/~xiaodong/cec13lsgo/competition/lsgo_2013_benchmarks.zip.

14. Li X., Tang K., Omidvar M. N., Yang Zh., Qin K. Technical report on 2013 IEEE Congress on Evolutionary Computation Competition on Large Scale Global Optimization. Available at: http://goanna.cs.rmit.edu.au/~xiaodong/cec13-lsgo/competition/lsgo-competition-sumary-2013.pdf.

15. LaTorre A., Muelas S., Pena J.-M. Large scale global optimization: experimental results with MOSbased hybrid algorithms. In 2013 IEEE Congress on Evolutionary Computation (CEC). 2013, P. 2742–2749.

16. Wei F., Wang Y., Huo Y. Smoothing and auxiliary functions based cooperative coevolution for global optimization. In 2013 IEEE Congress on Evolutionary Computation (CEC). 2013, P. 2736–2741.


Sopov Evgenii Alexandrovich – Cand. Sc., docent, docent of Department of System analysis and operations

research, Reshetnev Siberian State Aerospace University. E-mail: evgenysopov@gmail.com.