Radiotekhnika
Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS


Тел.: +7 (495) 625-9241

 

Interval genetic algorithm of global constrained optimization

Keywords:

V. N. Panovskiy – Student, Moscow Aviation Institute (National Research University). E-mail: panovskiy.v@yandex.ru


In the given work the interval genetic algorithm, which was created by the author, for the solution of the global constrained optimization problem is considered. Also this algorithm can be used to solve the problem of determination of optimum program control of discrete and continuous dynamic systems. In the modern mathematics a great attention is given to the solution of problems of global optimization and to the synthesis of optimal control of dynamic systems. These problems arise during designing of planes, helicopters and spacecrafts, when the necessity of optimization of characteristic parameters and of creation of control systems arises. Existing numerical methods use different approaches, but their application is connected with various difficulties: the big computing loadings, requirements to problem statement, difficulties in reaching convergence. Thus, development of new methods of the optimization, which combine the newest mathematical approaches, is extremely important. Besides, it is necessary to notice that it is important to use and develop heuristic methods. Despite the lack of its strict substantiation, these methods give an acceptable solution of a problem in the majority of almost significant cases. Heuristic algorithms do not guarantee finding the solution and can give an incorrect solution in certain cases. However an essential advantage of such algorithms is their low computing complexity. This allows one to apply them to the solution of problems of the raised difficulty (for example, the problems belonging to NP class). In aggregate with key singularities of the interval analysis (handling of ranges instead of isolated points, low insistence to problem statement) development of heuristic interval algorithms is an extremely perspective direction. Like any genetic algorithm, the interval genetic algorithm bases on the process of natural evolution. Inheritance, mutation, selection and crossingover are the base. In the description genetic definitions are used: population – finite set of individuals (individuals are represented by chromosomes, where their parameters are encoded), chromosomes – ordered sequences of genes, gene – base element of the genotype and chromosomes, genotype– set of chromosomes of a given individual, phenotype – set of values corresponding to a given genotype (decoded structure of set of parameters). The main feature of the developed algorithm is the way of formalization of a problem. In the classic algorithm it is necessary to build uniform grid on the search area, each node of which is defined by its ordinal value in the binary system. In the given algorithm interval vector is coded by a bit string, where occurrence of the «1» means the appurtenance of the subinterval to component. The interval genetic algorithm is very flexible due to a sufficiently large number of created interval genetic operators. It can be easily tuned depending on characteristics of problem. The proposed algorithm was implemented in a software program. IDE – Microsoft Visual Studio, programming language– C#. In the given work the algorithm and the software of interval genetic algorithm for the solution of problems of global constrained optimization and of synthesis of optimal program control of discrete and continuous determined dynamic systems were created. Also solutions of model problems (including the problem of the orientation of the spacecraft), which demonstrate the effectiveness of the algorithm, are demonstrated.
References:

  1. Panteleev A. V. Primenenie e'volyuczionny'x metodov global'noj optimizaczii v zadachax optimal'nogo upravleniya determinirovanny'mi sistemami. M.: MAI. 2013.
  2. Panteleev A. V., Metliczkaya D. V. Primenenie geneticheskix algoritmov s veshhestvenny'm kodirovaniem k zadache optimal'nogo upravleniya diskretny'mi sistemami // Vestnik komp'yuterny'x i informaczionny'x texnologij. 2011. № 9. S. 17 – 23.
  3. Panteleev A. V., Metliczkaya D. V. Primenenie geneticheskix algoritmov s binarny'm kodirovaniem k zadache poiska optimal'nogo upravleniya neprery'vny'mi determinirovanny'mi sistemami // Aviakosmicheskoe priborostroenie. 2011. № 2. S. 23–30.
  4. Panteleev A. V., Metliczkaya D. V. Formirovanie geneticheskix algoritmov s veshhestvenny'm kodirovaniem v zadache sinteza optimal'nogo upravleniya diskretny'mi sistemami // Aviakosmicheskoe priborostroenie. 2011. № 3. S. 26–31.
  5. Panteleev A. V., Metliczkaya D. V. Primenenie geneticheskix algoritmov s binarny'm i veshhestvenny'm kodirovaniem dlya priblizhennogo sinteza suboptimal'nogo upravleniya determinirovanny'mi sistemami // Avtomatika i telemexanika. 2011. № 11. S. 117–129.
  6. Jaulin, L., Applied interval analysis. London: Springer-Verlag. 2001.
  7. Hansen, E., Walster, G., Global optimization using interval analysis. New York: Marcel Dekker. 2004.
  8. Holland, J., H. Adaptation in natural and artificial systems // Ann Arbor: University of Michigan Press. 1975.
  9. Bäck, T., Fogel, D. B., Michalewicz, Z., Evolutionary computation 1. Basic algorithms and operators // Bristol and Philadelphia: Institute of Physics Publishing. 2000.

June 24, 2020
May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio