10.14489/vkit.2016.04.pp.050-056

DOI: 10.14489/vkit.2016.04.pp.050-056

Коновалов И. С., Фатхи В. А., Кобак В. Г.
СТРАТЕГИЯ ЭЛИТИЗМА МОДИФИЦИРОВАННОЙ МОДЕЛИ ГОЛДБЕРГА ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИ РЕШЕНИИ ЗАДАЧИ ПОКРЫТИЯ МНОЖЕСТВ
(cc. 50-56)

Аннотация. Расммотрена задача нахождения минимального покрытия множеств, применяемая для решения важнейших задач дискретной оптимизации, таких как размещение пунктов обслуживания, назначение экипажей на транспорте, проектирование интегральных схем и конвейерных линий. Показаны преимущества и недостатки элитизма в модифицированный модели Голдберга генетического алгоритма, который помогает получить более точные решения благодаря сохранению лучших особей.

Ключевые слова: генетический алгоритм; задача покрытия множеств; модель Голдберга; стратегия элитизма; алгоритм Нгуена М. Х.; жадная стратегия Хватала; полный перебор.

Konovalov I. S., Fatkhi V. A., Kobak V. G.
ELITISM STRATEGY MODIFIED GOLDBERG MODEL OF GENETIC ALGORITHM IN SOLVING THE SET COVERING PROBLEM
(pp. 50-56)

Abstract. In article the set covering problem which is applied to the solution of the major tasks of the discrete optimization, such as placement of service stations, assignment of crews on transport, integrated circuit engineering and pipeline lines is described. Methods of the solution of this task can be broken into classes of confidants with a prior assessment, heuristic and exact methods. This article is devoted to applicability of heuristics, model-based Goldberg of the genetic algorithm. Article purpose – research of methods of increase of efficiency of the genetic algorithm, accuracy of the solution of the task of a covering by means of use of strategy of elitism. Advantages and shortcomings of elitism are considered. It is visually shown that the elitism helps to receive more exact decisions thanks to saving the best individuals, optimum number of elite individuals is 1–2. It is recommended to use 1 elite individual created by greedy algorithm in tasks of small dimensionality (< 150 x150) and 2 elite individuals created by greedy algorithm and Nguyen M. H. GA in tasks of big dimensionality (> 150 x150).

Keywords: Genetic algorithm; Set covering problem; Goldberg’s model; Strategy of elitism; Algorithm Nguyen M. H. ; Greedy strategy of Chvatal; Brute forse.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

И. С. Коновалов, В. А. Фатхи, В. Г. Кобак (Донской государственный технический университет, Ростов-на-Дону) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

I. S. Konovalov, V. A. Fatkhi, V. G. Kobak (Don State Technical University, Rostov-on-Don) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Коновалов И. С., Фатхи В. А., Кобак В. Г. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при реше-нии взвешенной задачи нахождения минимального по-крытия множеств // Тр. СКФ МТУСИ. 2015. Ч. I. Ростов-на-Дону: ПЦ «Университета». СКФ МТУСИ. 2015. С. 366 – 370.
2. Еремеев А. В. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. 2000. Т. 7, № 1. С. 47 – 60.
3. Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. 2000. Т. 7, № 2. С. 22 – 46 .
4. Кононов А. В., Кононова П. А. Приближенные алгоритмы для NP-трудных задач: учеб.-метод. пособие. Новосибирск: Новосиб. гос. ун-т, 2014. 117 с.
5. Chvatal V. A Greedy Heuristic for the Set-covering Problem // Mathematics of Operations Research. 1979. V. 4, № 3. P. 233 – 235.
6. Holland J. H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975. 245 р.
7. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989. 432 р.
8. Батищев Д. И. Генетические алгоритмы решения экстремальных задач: учеб. пособие. Воронеж: ВГТУ, 1995. 69 с.
9. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. 2-е изд. М.: ФИЗМАТЛИТ, 2010. 368 с.
10. Нгуен М. Х. Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. М.: Изд-во ЛКИ, 2008. T. 33, вып. 12. С. 206 – 219.
11. Эволюционные методы моделирования и оптимизации сложных систем: конспект лекций / Е. С. Се-менкин и др. Красноярск: СФУ, 2007. 310 с.
12. Панченко Т. В. Генетические алгоритмы: учеб.-метод. пособие / под ред. Ю. Ю. Тарасевича. Астрахань: АГУ, 2007. 87 с.

Eng

1. Konovalov I. S., Fatkhi V. A., Kobak V. G. (2015). Comparative analysis of the Chwatal greedy algorithm and Goldberg modified model for solving the problem of finding a minimum weighted in an open set. Trudy SKF MTUSI, Part I, pp. 366-370.
2. Eremeev A. V. (2000). Genetic algorithm for covering problem. Diskretnyi analiz i issledovanie operatsii, 7(1), pp. 47-60.
3. Eremeev A. V., Zaozerskaia L. A., Kolokolov A. A. (2000). The problem of set covering: complexity, algorithms, and experimental investigations. Diskretnyi analiz i issledovanie operatsii, 7(2), pp. 22-46.
4. Kononov A. V., Kononova P. A. (2014). Approximation algorithms for NP-hard problems: a teaching guide. Novosibirsk: Novosibirskii gosudarstvennyi universitet.
5. Chvatal V. (1979). A greedy heuristic for the setcovering problem. Mathematics of Operations Research, 4(3), pp. 233-235.
6. Holland J. H. (1975). Adaptation in natural and artificial systems. The University of Michigan Press.
7. Goldberg D. E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.
8. Batishchev D. I. (1995). Genetic algorithms for solving extreme problems: textbook. Voronezh: VGTU.
9. Gladkov L. A., Kureichik V. V., Kureichik V. M. (2010). Genetic algorithms. 2nd Ed. Moscow: FIZMATLIT.
10. Nguen M. Kh. (2008). Application of genetic algorithm to the problem of finding set cover. Dinamika neodnorodnykh system, 33(12), pp. 206-219, Moscow: Izdatel'stvo LKI.
11. Semenkin E. S. (2007). Evolutionary methods of modeling and optimization of complex systems: lectures ab-stracts. Krasnoiarsk: SFU.
12. Tarasevich Iu. Iu. (Ed.), Panchenko T. V. (2007). Genetic algorithms: teaching guide. Astrakhan': AGU.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.04.pp.050-056}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.04.pp.050-056}