О повышении эффективности параллельной версии многопопуляционного генетического алгоритма
Рассмотрены некоторые особенности параллельной реализации многопопуляционного генетического алгоритма, а также некоторые подходы по повышению его эффективности. Проведены расчеты по генерации эффективной начальной популяции, экспериментальная оценка способов сохранения популяции, а также рассмотрены...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/161683 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О повышении эффективности параллельной версии многопопуляционного генетического алгоритма / И.О. Лукьянов, Ф.А. Литвиненко, Е.А. Криковлюк // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 116-122. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161683 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1616832019-12-19T01:25:16Z О повышении эффективности параллельной версии многопопуляционного генетического алгоритма Лукьянов, И.О. Литвиненко, Ф.А. Криковлюк, Е.А. Рассмотрены некоторые особенности параллельной реализации многопопуляционного генетического алгоритма, а также некоторые подходы по повышению его эффективности. Проведены расчеты по генерации эффективной начальной популяции, экспериментальная оценка способов сохранения популяции, а также рассмотрены некоторые модификации генетического алгоритма для ускорения его сходимости. В результате достигнуто уменьшение количества рассмотренных альтернатив на 10 %. Розглянуті деякі особливості паралельної реалізації багатопопуляціонного генетичного алгоритму, а також деякі підходи щодо підвищення його ефективності. Проведено розрахунки по генерації ефективної початкової популяції, експериментальна оцінка способів збереження популяції, а також розглянуті деякі модифікації генетичного алгоритму для прискорення його збіжності. В результаті досягнуто зменшення кількості розглянутих альтернатив на 10 %. In this paper, we consider some features of parallel implementation of a multipopulation genetic algorithm, as well as some approaches to improve its efficiency. Calculations were carried out on the generation of an effective initial population, an experimental assessment of the methods of preserving the population, and also some modifications of the genetic algorithm to accelerate its convergence were considered. As a result, a decrease in the number of alternatives considered by 10 % was achieved. 2019 Article О повышении эффективности параллельной версии многопопуляционного генетического алгоритма / И.О. Лукьянов, Ф.А. Литвиненко, Е.А. Криковлюк // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 116-122. — Бібліогр.: 6 назв. — рос. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/161683 519.711: 519.711.3: 519.81 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассмотрены некоторые особенности параллельной реализации многопопуляционного генетического алгоритма, а также некоторые подходы по повышению его эффективности. Проведены расчеты по генерации эффективной начальной популяции, экспериментальная оценка способов сохранения популяции, а также рассмотрены некоторые модификации генетического алгоритма для ускорения его сходимости. В результате достигнуто уменьшение количества рассмотренных альтернатив на 10 %. |
| format |
Article |
| author |
Лукьянов, И.О. Литвиненко, Ф.А. Криковлюк, Е.А. |
| spellingShingle |
Лукьянов, И.О. Литвиненко, Ф.А. Криковлюк, Е.А. О повышении эффективности параллельной версии многопопуляционного генетического алгоритма Теорія оптимальних рішень |
| author_facet |
Лукьянов, И.О. Литвиненко, Ф.А. Криковлюк, Е.А. |
| author_sort |
Лукьянов, И.О. |
| title |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| title_short |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| title_full |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| title_fullStr |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| title_full_unstemmed |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| title_sort |
о повышении эффективности параллельной версии многопопуляционного генетического алгоритма |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161683 |
| citation_txt |
О повышении эффективности параллельной версии многопопуляционного генетического алгоритма / И.О. Лукьянов, Ф.А. Литвиненко, Е.А. Криковлюк // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 116-122. — Бібліогр.: 6 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT lukʹânovio opovyšeniiéffektivnostiparallelʹnojversiimnogopopulâcionnogogenetičeskogoalgoritma AT litvinenkofa opovyšeniiéffektivnostiparallelʹnojversiimnogopopulâcionnogogenetičeskogoalgoritma AT krikovlûkea opovyšeniiéffektivnostiparallelʹnojversiimnogopopulâcionnogogenetičeskogoalgoritma |
| first_indexed |
2025-07-14T14:16:17Z |
| last_indexed |
2025-07-14T14:16:17Z |
| _version_ |
1837632143614803968 |
| fulltext |
116 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Рассмотрены некоторые особенно-
сти параллельной реализации мно-
гопопуляционного генетического
алгоритма, а также некоторые
подходы по повышению его эффек-
тивности. Проведены расчеты по
генерации эффективной начальной
популяции, экспериментальная
оценка способов сохранения попу-
ляции, а также рассмотрены не-
которые модификации генетиче-
ского алгоритма для ускорения его
сходимости. В результате достиг-
нуто уменьшение количества рас-
смотренных альтернатив на 10 %.
И.О. Лукьянов, Ф.А. Литвиненко,
Е.А. Криковлюк, 2019
УДК 519.711: 519.711.3: 519.81
И.О. ЛУКЬЯНОВ, Ф.А. ЛИТВИНЕНКО,
Е.А. КРИКОВЛЮК
О ПОВЫШЕНИИ ЭФФЕКТИВНОСТИ
ПАРАЛЛЕЛЬНОЙ ВЕРСИИ
МНОГОПОПУЛЯЦИОННОГО
ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Введение. В мировой практике компью-
терного моделирования сложных стохасти-
ческих систем все большее распростране-
ние приобретает методология Data Farming
[1]. Для некоторых задач оптимизации, ре-
шаемых на основе данной методологии,
используется генетический алгоритм. Учи-
тывая данное, исследование особенностей
его применения, как для классической
модели, так и различных ее модификаций
(в частности, многопопуляционной версии)
остается актуальным [2 – 5].
Экспериментальное исследование осо-
бенностей и эффективности многопопуля-
ционного генетического алгоритма при
планировании и реализации оптимизаци-
онно-имитационных экспериментов пока-
зывают, что вырождение генетического ма-
териала является весомым фактором, кото-
рый негативно влияет на скорость сходи-
мости к оптимальному решению [6].
Вполне естественно предположить, что
избежать вырождения генетического мате-
риала можно с помощью правильно подо-
бранных параметров и стратегий алгорит-
ма. В этой работе представлены некоторые
подходы по выбору размера начальной по-
пуляции, а также рассмотрены стратегии
по эффективному использованию сгенери-
рованной начальной популяции и сохране-
нию ее разнообразности.
Цель данной работы – исследование не-
которых стратегий сохранения полезного
генетического материала начальной попу-
ляции для уменьшения количества рассмот-
О ПОВЫШЕНИИ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНОЙ ВЕРСИИ ...
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 117
ренных альтернатив решений и повышения скорости сходимости алгоритма.
В настоящей работе приняты следующие допущения:
– вместо имитационной модели предполагается использование однокрите-
риальной фитнесс-функции F, выступающей аналогом поверхности реакции не-
которой имитационной модели;
– при исследовании на данном этапе считаем, что значения, возвращаемые
фитнесс-функцией, являются детерминированной величиной (а не случайной
величиной, как это имеет место при моделирования сложных стохастических
систем), и имеют четко выраженный экстремум.
Описание тестовой задачи. Используя генетический алгоритм и распреде-
ленные вычисления, найти некоторую заданную строку длины L, состоящую из
символов конечного алфавита размерности a. Фитнесс-функция F сообщает о
количестве позиций в оцениваемом текущем решении, значения в которых не
совпадают со значениями в целевой (эталонной) строке. Таким образом, мини-
мальное значение известно и достигается при F = 0.
Используемый алгоритм, его параметры, а также их значения более подроб-
но описаны в [6].
Эксперименты проводились на отечественном суперкомпьютере с кластер-
ной архитектурой СКИТ-4 Института кибернетики НАН Украины с использова-
нием средств MPI (Message Passing Interface). Для осуществления стратегий об-
мена выделен один процессор с индексом 0 в качестве управляющего (master
process – MP). Все остальные процессоры являются управляемыми (worker
process – WP). На WP реализованы разные параллельно развивающиеся популя-
ции, которые выступают в качестве «островов» в многопопуляционной модели
генетического алгоритма.
Также приняты некоторые термины:
«правильный» ген – ген, значение которого совпадает со значением гена
в эталоне на соответствующей позиции;
начальная популяция – множество всех ненулевых хромосом-решений
для всех процессов;
полным генетическим материалом назовем набор генов, входивших
в начальную популяцию, значение которых совпадает со значениями генов эта-
лона на соответствующих позициях.
Генерация начальной популяции. Для генерации по возможности более
полного генетического материала необходимо выбрать соответствующее значе-
ние размера начальной популяции. Значение этого параметра, для данной зада-
чи, можно обосновать математически.
Для соответствующих расчетов будем использовать следующие значения:
длина искомой строки L = 100, размер начальной популяции на каждом процес-
соре l = 10, число популяций (процессоров) k = 15, число символов конечного
алфавита a = 33. Соответственно вероятность случайного выбора правильного
символа для конкретной позиции искомой строки при равномерном распреде-
И.О. ЛУКЬЯНОВ, Ф.А. ЛИТВИНЕНКО, Е.А. КРИКОВЛЮК
118 ISSN 2616-5619. Теорія оптимальних рішень. 2019 № 18
лении будет равна p = 1/a = 1/33, а число независимых испытаний по каждой
позиции искомой строки при случайной генерации начальных популяций (об-
щее количество сгенерированных строк): kl = 150.
Тогда вероятность Pa выбора правильного символа в заданной позиции ис-
комой строки хотя бы один раз при генерации всех начальных популяций равна
Под оптимальным будем понимать такой размер начальной популяции, при
котором после генерации начальных популяций, вероятность P(x) совпадения
символа, хотя бы для одной особи в произвольных x (близких к значению L)
позициях искомой строки, будет с заданной точностью равна единице. Эта веро-
ятность в нашем случае вычисляется следующим образом:
Определим соотношение между P(x) и P(x – 1):
При x = L :
Посчитав вероятность совпадения символов в интервале от 97 до 100 пози-
ций искомой строки после генерации всех начальных популяций, можно вычис-
лить их сумму:
Столь высокая вероятность обеспечивает генерацию достаточно полного
генетического материала практически во всех экспериментах.
Стратегии сохранения генетического материала на начальном этапе.
В работе [6] приведены результаты, показывающие, что до некоторой точки
работы алгоритма операции скрещивания обеспечивают достаточно высокую
скорость схождения к оптимуму. В то же время на заключительном этапе алго-
ритма важное значение приобретают операции мутации.
Эксперименты с использованием данного алгоритма показывают, что чем
ближе к оптимуму найденное решение, тем медленнее оно к нему приближается.
На рис. 1 показано, что на последние 10 % оптимума приходится около 40 %
О ПОВЫШЕНИИ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНОЙ ВЕРСИИ ...
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 119
всех вычислений. Такое увеличение количества итераций связано с тем, что по-
следние гены для нахождения оптимального решения получены исключительно
с помощью операции мутации, вероятность успеха которой крайне мала, если
сравнивать ее с вероятностью неудачи данной операции.
РИС. 1
Экспериментальным путем было определено, что при использовании
исключительно операций скрещивания, данный алгоритм в среднем достигает
84 % от оптимума. Если сгенерированная начальная популяция содержит около
100 % генов оптимального решения, логично предположить, что путем направ-
ленного скрещивания и селекции можно улучшить процент оптимума, достигну-
того исключительно операциями скрещивания, что в свою очередь должно
уменьшить количество итераций в целом.
Попробуем модифицировать стратегии алгоритма с целью более эффектив-
ного использования генетического материала начальной популяции и сохране-
ния его разнообразности.
Можно выделить следующие причины потерь полезного генетического
материала:
– потери при селекции: уникальный правильный ген может попасть в хро-
мосому с малым значением фитнесс-функции, которая может быть удалена из
популяции в результате селекции;
– потери при скрещивании: при скрещивании мы последовательно случай-
ным образом определяем предка, ген которого будет стоять на текущем месте
у потомка. Таким образом, если уникальный правильный ген не будет выбран,
он не будет распространен по популяции и может быть потерян в результате
селекции.
Для уменьшения потерь при селекции на ранних этапах работы алгоритма
модифицируем его следующим образом.
Одним из способов решения проблемы потерь при скрещивании может быть
порождение двух «противоположных» или «зеркальных» потомков, гены кото-
рых полностью не совпадают между собой. Таким образом, каждый правильный
И.О. ЛУКЬЯНОВ, Ф.А. ЛИТВИНЕНКО, Е.А. КРИКОВЛЮК
120 ISSN 2616-5619. Теорія оптимальних рішень. 2019 № 18
ген каждого предка будет передан в сгенерированную хромосому-решение
(рис. 2). При этом одна из результирующих хромосом-решений гарантированно
даст такое же или лучшее значение фитнесс-функции, по сравнению с ее родите-
лями, и с большей вероятностью останется в популяции. В результате данного
подхода количество итераций алгоритма (поколений) уменьшилось со 195 до 180.
РИС. 2
Так как для нахождения последних генов очень важны операции мутации,
логично предположить, что они дадут лучший результат, если проводить их с
лучшей хромосомой-решением в популяции, по сравнению с проведением мута-
ции с любой другой из элитной части. Использование этой стратегии на заклю-
чительном этапе алгоритма, в комбинации с применением «противоположного»
скрещивания, уменьшило количество итераций до 170.
Добавим, что если при скрещивании перезаписывать всю популяцию, т. е.
заменять все имеющиеся хромосомы-решения на полученные сгенерированные
хромосомы-решения, то можно практически избежать потери «правильных» ге-
нов во время селекции. Исключением будут являться случаи, когда в популяцию
попадает хромосома-решение из другой популяции. При использовании данной
стратегии важно, чтобы хромосомы-решения использовались во время скрещи-
вания только один раз. Для этого можно использовать различные стратегии их
выбора. Рассмотрим несколько вариантов:
– поочередное скрещивание – первая хромосома скрещивается со второй,
третья с четвертой и т. д.;
– сбалансированное скрещивание – первая хромосома скрещивается с по-
следней, вторая с предпоследней и т. д.
Для наглядности эксперимента вероятность мутации на начальном этапе ал-
горитма была равна 0, параметр точки перехода [6] установлен на уровне до-
стижения 90 % оптимума, вероятность мутации на заключительном этапе уста-
навливалась равной 0.75.
На рис. 3 показано сравнение данных стратегий скрещивания с произволь-
ной стратегией «противоположного» скрещивания. Здесь D – общее значение
О ПОВЫШЕНИИ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНОЙ ВЕРСИИ ...
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 121
«правильных» генов присутствующих во всей популяции, F – значение фитнесс-
функции для лучшей хромосомы-решения во всей популяции.
Поочередное скрещивание демонстрирует хорошие результаты по сохране-
нию генетического материала, показывая значение D в окрестности 100 %. Од-
нако, так как все предыдущие хромосомы-решения заменяются на сгенериро-
ванные, в селекции не участвуют хромосомы-решения из предыдущих итераций
алгоритма, что значительно понижает скорость схождения к оптимуму.
РИС. 3
Сбалансированное скрещивание, в свою очередь, так же показывает хоро-
шие результаты по сохранению популяции, но так как для скрещивания исполь-
зуются «лучшая» и «худшая» хромосомы-решения, в среднем скрещивание не
улучшает результата, который уже имелся в популяции. Это приводит к медлен-
ному схождению к оптимуму.
Выводы. В данной работе рассмотрены некоторые особенности параллель-
ной реализации многопопуляционного генетического алгоритма, а также неко-
торые подходы к повышению его эффективности. Проведены расчеты вероятно-
сти генерации эффективной начальной популяции, экспериментальная оценка
способов сохранения популяции, а также рассмотрены некоторые модификации
генетического алгоритма для ускорения его сходимости. В результате достигнуто
уменьшение количества рассмотренных вариантов решения (альтернатив)
на 10 %. В дальнейших исследованиях в качестве аналога поверхности реакции
имитационной модели планируется использование более сложных функций, ко-
торые будут включать непрерывные и малозначимые факторы, а также наличие
случайного влияния.
И.О. ЛУКЬЯНОВ, Ф.А. ЛИТВИНЕНКО, Е.А. КРИКОВЛЮК
122 ISSN 2616-5619. Теорія оптимальних рішень. 2019 № 18
І.О. Лук’янов, Ф.А. Литвиненко О.О. Криковлюк
ПРО ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ПАРАЛЕЛЬНОЇ ВЕРСІЇ
БАГАТОПОПУЛЯЦІЙНОГО ГЕНЕТИЧНОГО АЛГОРИТМУ
Розглянуті деякі особливості паралельної реалізації багатопопуляціонного генетичного алго-
ритму, а також деякі підходи щодо підвищення його ефективності. Проведено розрахунки по
генерації ефективної початкової популяції, експериментальна оцінка способів збереження по-
пуляції, а також розглянуті деякі модифікації генетичного алгоритму для прискорення
його збіжності. В результаті досягнуто зменшення кількості розглянутих альтернатив
на 10 %.
I.O. Lukianov, F.A. Lytvynenko, O.O. Krykovliuk
ABOUT INCREASING THE EFFICIENCY OF THE PARALLEL VERSION
OF A MULTIPOPULATION GENETIC ALGORITHM
In this paper, we consider some features of parallel implementation of a multi-population genetic al-
gorithm, as well as some approaches to improve its efficiency. Calculations were carried out on the
generation of an effective initial population, an experimental assessment of the methods of preserv-
ing the population, and also some modifications of the genetic algorithm to accelerate its conver-
gence were considered. As a result, a decrease in the number of alternatives considered by 10 % was
achieved.
Список литературы
1. Horne G.E., Meyer T.E. Data Farming: Discovering Surprise. Proc. of the Winter Simulation
Conf. 2005. P. 1082 – 1087.
2. Whitley D.A Genetic Algorithm Tutorial. Statistics and Computing. 1994. № 4. P. 65 – 85.
3. Whitley D. An overview of evolutoinary algorithims. J. of Inform. And Software Techn. 2001.
N 43. P. 192 – 215.
4. Пепеляев В.А. Об эволюционных подходах к оптимизации имитационного моделирова-
ния. Компьютерная математика. 2005. № 1. С. 48 – 54.
5. Пепеляев В.А. Об оценке эффективности оптимизационных метаэвристических страте-
гий. Теория оптимальных решений. 2006. № 5. С. 16 – 22.
6. Литвиненко Ф.А., Лукьянов И.О., Криковлюк Е.А. Особенности реализации параллель-
ной версии многопопуляционного генетического алгоритма. Компьютерная математи-
ка. 2019. № 2. С. 21 – 29.
Получено 25.03.2019
|