Гибридный генетический алгоритм на основе биологического апоптоза
Розглянуто класичний генетичний алгоритм та основні проблеми, що виникають при його реалізації. Запропоновано модифікацію даного алгоритму, яка змінює спосіб формування нових пар нащадків на основі механізму біологічного апоптозу. Введено поняття насиченості популяції та запропоновано використовуват...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207592 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Гибридный генетический алгоритм на основе биологического апоптоза / О.Г. Руденко, Р.В. Бобнев // Проблемы управления и информатики. — 2013. — № 1. — С. 115–125. — Бібліогр.: 6 назв. - рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860138477309394944 |
|---|---|
| author | Руденко, О.Г. Бобнєв, Р.В. |
| author_facet | Руденко, О.Г. Бобнєв, Р.В. |
| citation_txt | Гибридный генетический алгоритм на основе биологического апоптоза / О.Г. Руденко, Р.В. Бобнев // Проблемы управления и информатики. — 2013. — № 1. — С. 115–125. — Бібліогр.: 6 назв. - рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто класичний генетичний алгоритм та основні проблеми, що виникають при його реалізації. Запропоновано модифікацію даного алгоритму, яка змінює спосіб формування нових пар нащадків на основі механізму біологічного апоптозу. Введено поняття насиченості популяції та запропоновано використовувати поріг насиченості для покращення роботи алгоритму. Наведено результати експериментальних досліджень, які підтверджують ефективність запропонованих модифікацій при знаходженні екстремумів мультимодальних функцій.
A classic genetic algorithm and the key issues associated with its implementation are considered. A modification of the classic genetic algorithm which changes the way of creating new offspring’s pairs is presented. The modification is based on the biological apoptosis theory. The saturation population conception and the suggestion about usage of this conception as termination condition with the purpose of algorithm improving have been introduced. The experimental research results proving efficiency of suggested modifications in case of multimodal functions have been shown.
|
| first_indexed | 2025-12-07T17:47:46Z |
| format | Article |
| fulltext |
© О.Г. РУДЕНКО, Р.В. БОБНЕВ, 2013
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 115
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 519.71
О.Г. Руденко, Р.В. Бобнев
ГИБРИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
НА ОСНОВЕ БИОЛОГИЧЕСКОГО АПОПТОЗА
Введение. Генетические алгоритмы (ГА), предложенные Дж. Холландом [1]
и первоначально предназначенные для решения задач оптимизации в качестве до-
статочно эффективного механизма комбинаторного перебора вариантов решений,
в настоящее время широко используются при решении многих проблем, которые
могут быть сформулированы как задачи оптимизации, в частности, к таким зада-
чам относится нахождение экстремумов мультимодальных функций. Сам по себе
ГА представляет алгоритм, основанный на биологической модели эволюции, а
именно естественного отбора. В рамках терминологии ГА все действия произво-
дятся над генотипами, которые по аналогии с биологическим термином, пред-
ставляют собой набор генов, где геномом может выступать практически любое
числовое значение, над которым может быть определена операция мутации (по-
нятие мутации кратко описано ниже). В самом простом виде ГА можно разбить на
следующие составляющие:
• создание начальной популяции;
• селекция особей и размножение (кроссовер или кроссинговер);
• мутация особей;
• определение уровня приспособленности каждой особи (фитнесс-функции);
• естественный отбор на основе приспособленности каждой особи.
Традиционный ГА показан на рис. 1 сплошными линиями.
Создание популяции подразумевает создание случайной группы особей, каж-
дая из которых является генотипом, состоящим из набора генов.
Выбираемые каким-либо образом две пары, от которых будут произведены по-
томки, участвуют в репродукции, представляющей собой скрещивание (кроссинго-
вер). Для выбора таких пар применяют ряд методов, среди которых наиболее распро-
страненными являются метод «рулетки», ранжирование, случайный выбор, локаль-
ный отбор, отбор на основе усечения, турнирный отбор и др. [1–3]. Сама операция
репродукции представляет собой скрещивание (кроссинговер) двух генотипов.
Мутация особей или случайное изменение гена осуществляется путем изме-
нения последовательности знаков (при бинарном представлении это инверсия
случайного бита). Так как мутация гена порождает новый ген с другими свой-
ствами, в ГА ее можно заменить на случайный выбор одного гена из заданного
множества всех возможных генов.
Определение фитнесс-функции и вычисление ее для каждого индивида попу-
ляции является сугубо проблемно-зависимой частью, и выбор ее зависит не толь-
ко от поставленной задачи, но и от способа формализации задачи в рамках ГА.
Следует отметить, что если операции кроссинговера и мутации более или менее
формализованы, и по ним можно сделать приблизительную оценку производи-
тельности и затрат времени вычислений, то определение фитнесс-функции осу-
ществляется субъективно и ее вычисление для каждой особи может существенно
влиять на время работы алгоритма.
116 ISSN 0572-2691
Да
Нет
Идентичные пары
найдены
Нет
Да
Случайная выборка особей
Создание случайной популяции
Кроссинговер
Мутация
Выполнено ли условие
завершения?
Естественный отбор
на основе фитнесс-функции
Принудительная
(жесткая) мутация
Конец
Рис. 1
Естественный отбор является, по сути, отсеиванием неприспособленных осо-
бей из всей популяции. Однако простое отсеивание всех слабых особей нецелесо-
образно, так как из индивидуумов с наивысшим показателем фитнесс-функции
можно быстро попасть в локальный экстремум, а слабые особи, которые потенци-
ально могут быть новыми решениями, попросту будут отброшены. Данный недо-
статок должен устраняться мутацией, но не устраняется в силу ее обычно низкой
вероятности. Вследствие этого при решении мультимодальных задач зачастую
наблюдается преждевременная сходимость в локальные экстремумы и не гаран-
тируется нахождение глобального экстремума [2, 3].
Для устранения данного недостатка были предложены методы инбридинг и аут-
бридинг, использующие некоторое условие идентичности и отличающиеся лишь
способом выбора пар для репродукции путем формирования таких пар на основе
близкого или дальнего родства соответственно (под родством обычно понимается
расстояние между особями популяции в пространстве параметров). Комбинация
этих походов используется при решении многоэкстремальных задач. Существуют
также работы по самоорганизации вероятности мутации, меняющейся в процессе
работы ГА, которая корректируется в зависимости от степени сходимости к локаль-
ному минимуму. Одна из таких оценок степени сходимости — наблюдение разности
среднего и максимального значения целевой функции по популяции.
В данной работе предлагается модификация ГА, отличающаяся от методов
инбридинг и аутбридинг тем, что она не оказывает влияния на способ селекции
особей. Хотя она имеет некоторое сходство с адаптивным изменением вероятно-
сти мутации, существенная разница состоит в том, что предлагаемая модифика-
ция видоизменяет способ формирования новых пар потомков. И данная адаптация
происходит в процессе работы алгоритма, независимо от того, вся ли популяция
уже «забита» локальными экстремумами или только небольшая ее часть.
Апоптоз. В биологии существует понятие апоптоза — явления программиру-
емой клеточной смерти, сопровождаемой набором характерных цитологических
признаков (маркеров апоптоза) и молекулярных процессов, имеющих различия у
одноклеточных и многоклеточных организмов [4]. Роль апоптоза в организме
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 117
крайне важна, так как он позволяет убить «ненужные» идентичные клетки. Ос-
новной особенностью апоптоза является то, что этот процесс программирует
клетку на смерть путем мутации. Логично предположить, что если для кроссинго-
вера были выбраны две идентичные особи, то каков бы ни был способ обмена ге-
нами, потомки будут также идентичными и полностью унаследуют приспособ-
ленность родителей. Поэтому единственной возможностью введения разнообра-
зия в генофонд является мутация. Но так как мутация имеет, как правило, низкую
вероятность, и учитывая, что она обычно происходит для одного гена, максимум
что можно получить, это более точное решение, а при наличии нескольких реше-
ний найдено будет только одно. По аналогии с биологическим процессом можно
ввести некий механизм апоптоза и в ГА.
Для этого необходимо модифицировать метод селекции и кроссинговера. Если
после селекции две особи оказались идентичными, то осуществлять кроссинговер
не имеет смысла, так как предки будут полностью соответствовать родителям. За-
метим, что подобный механизм регуляции существует и в природе. Для введения
данного механизма в ГА необходимо лишь добавить определенную логику: если
после селекции оба родителя являются идентичными, то вместо кроссинговера сле-
дует провести репликацию и мутацию для двух потомков и одного из родителей.
Репликация необходима для поддержания численного соотношения вероятности
кроссинговера, а мутация одного из родителей — для уменьшения числа селекций с
идентичными родителями. Следует отметить, что одну из мутаций можно произве-
сти стандартным способом (случайный ген), а две — более глобально. Предложен-
ная дополнительная стандартная мутация необходима для повышения точности уже
имеющегося решения (если два родителя идентичны, то их приспособленность вы-
сока, а это означает, что они либо являются оптимальным решением, либо доста-
точно близки к нему). Под глобальной мутацией подразумевается мутирование хотя
бы половины генов. Это необходимо для достаточного удаления новой особи от
своих родителей, что не позволит привести в процессе эволюции опять к ним же.
Достичь лучших результатов можно генерированием полностью нового генотипа,
добавив, таким образом, целый новый вид. Модификация ГА с использованием ме-
ханизма апоптоза показана пунктиром на рис. 1.
Особенности работы ГА при введении механизма апоптоза. В классическом
ГА вся популяция постепенно забивается клонами одной и той же особи с макси-
мальным значением фитнесс-функции (назовем эту особь лидирующей). При этом
вероятность двух идентичных потомков при скрещивании стремится к единице до
определенного количества эпох. При введении механизма апоптоза каждая опера-
ция скрещивания, в которой участвуют идентичные родители, заменяется, по сути,
добавлением новых особей. Таким образом, вся популяция проходит один из трех
типов скрещивания: скрещивание с лидирующей особью, с другой какой-либо осо-
бью (если такие еще остались в популяции) и добавление кардинально новой особи
(когда оба предка являются клонами лидера). Как правило, после скрещивания слу-
чайной особи с лидирующей потомок получается с лучшим значением фитнесс-
функции, и далее этот потомок, постепенно перебирая разнообразные гены, эволю-
ционирует в ту же лидирующую особь вследствие влияния генов лидеров на после-
дующие получаемые образы. Если же в скрещивающиеся пары не попала лидиру-
ющая особь, происходит обычная работа ГА на области случайной популяции, где
нет одного из решений. Это приводит, по аналогии с традиционным ГА, к нахожде-
нию еще одного решения в популяции, которая осталась не «забитой» клонами ли-
дера. В результате новая преобладающая особь заполняет всю оставшуюся часть
популяции уже своими клонами, и вся исходная популяция разделяется, как прави-
ло, на два множества идентичных особей, первое из которых состоит из особи,
найденной первой (от которой пытался отойти механизм апоптоза), а второе — из
особи, найденной обычным ГА на оставшейся части популяции. Схематически опи-
санный процесс формирования конечной популяции при использовании апоптоза
показан на рис. 2.
118 ISSN 0572-2691
Да
Создание особи
случайно
Нет
Создание особи,
которая эволюционирует
в текущего лидера
Создание особи,
которая приведет
к еще одному лидеру
Да Нет
Являются ли особи
идентичными?
Есть ли среди
родителей лидер?
Случайный выбор особей
для кроссинговера
Конечная популяция
Рис. 2
Как видно из рисунка, конечная популяция после ряда эпох будет состоять из
случайных особей (их доля крайне мала), из особей клонов первого найденного
лидера и особей клонов лидера, который получился в результате неявного отделе-
ния популяции от первого найденного.
Хотя на первый взгляд может показаться, что механизм апоптоза должен
вносить достаточное количество случайных особей и по аналогии со вторым
найденным лидером будут найдены и остальные решения, на самом деле этого не
происходит вследствие того, что вероятность выбора двух идентичных особей,
когда популяция заполнена двумя лидирующими особями, существенно меньше
вероятности выбора из популяции, содержащей лишь одну лидирующую особь.
Так если вначале она стремилась к единице (лишь потому, что был один един-
ственный лидер), то сейчас она стремится к 0,25. Это получается, вследствие того,
что выбор двух особей необходимо произвести из двух подмножеств идентичных
особей, а не из одного, как было ранее. Поскольку теперь уже есть два вида осо-
бей (два лидера), то вероятность выбора каждого из них составляет 0,5, а вероят-
ность двойного такого выбора (когда две особи идентичны между собой и явля-
ются клоном одного из лидеров), будет равна 0,25.
Увеличение размера популяции не решает эту проблему, так как в результате
лишь увеличиваются размеры подмножеств лидеров: при попадании в кроссинговер
лидера и обычной особи операция приводит по пути эволюции к одному из подмно-
жеств, что и влечет за собой разрастание каждого из них. Однако данную особен-
ность работы алгоритма можно использовать как показатель «насыщенности» попу-
ляции (под «насыщенностью» понимается такое состояние популяции, при котором
практически вся она состоит из клонов одной или более особей, имеющих наивыс-
шие значения функции приспособленности). Покажем, как это можно использовать
на практике. Зададим, например, счетчик, состояние которого будет увеличиваться
на единицу каждый раз, когда срабатывает механизм апоптоза, при каждом выборе
идентичных родителей. Отношение значения этого счетчика к общему числу особей,
участвовавших в кроссинговере, даст нам вероятность апоптоза. Как только она при-
близится к значению 0,25, можно делать вывод, что ГА достиг своего «насыщения»
и популяция в основном состоит из двух подмножеств решений. Далее, если число
эпох не превысило заданный порог, можно предложить ряд вариантов нахождения
остальных экстремумов функции на основе того факта, что популяция «насыщена».
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 119
Опишем некоторые из них.
Вариант 1. Самый простой вариант состоит в заполнении популяции совер-
шенно новыми особями, сохраняя при этом два (или более, если таковые имеют-
ся) найденных решения отдельно от новой популяции. Далее происходит работа
ГА, аналогичная предыдущей, но найденные ранее решения в алгоритме не участ-
вуют. При этом, однако, нет гарантии того, что после очередного прохода алго-
ритма ГА на вновь созданной популяции не будут получены дублирующие реше-
ния, которые были сохранены ранее.
Вариант 2. Во втором варианте после достижения порога «насыщения» по-
пуляция заполняется новыми особями псевдослучайно. В этом случае каждому из
найденных решений сопоставляется определенный ареал с заданным радиусом
(подразумевается, что для данного ареала, который сопоставляется с решением,
это решение оптимально, с максимальным значением фитнесс-функции). Генери-
рование новых особей происходит с использованием правила, по которому вновь
получающиеся особи не должны попадать в этот ареал. При этом возникает во-
прос адекватности определения радиуса каждого из ареалов. Данный подход (как
и предыдущий) не дает стопроцентной гарантии того, что после работы ГА не бу-
дет дублирующих решений, он всего лишь существенно уменьшает вероятность
их появления.
Вариант 3. Наиболее разумным кажется способ, при котором найденные ре-
шения участвуют в процессе работы апоптоза ГА после «насыщения» популяции,
но не участвуют в кроссинговере. Для этого, когда для кроссинговера выбраны
две новые особи из популяции, следует сравнивать их не только между собой, но
и со всеми найденными ранее решениями, которые были сохранены после дости-
жения «насыщения». Если одна из вновь выбранных особей идентична какому-
либо из решений или отстоит от него на заданном минимальном расстоянии
(в случае если известен ареал обитания, как в предыдущем варианте), то данную
особь следует заменить полностью новой. Это необходимо для того, чтобы с вы-
сокой вероятностью особь, являющаяся либо уже одним из найденных решений,
либо очень близкой к нему, не превратилась в одного из «лидеров» и не заполни-
ла популяцию своими клонами. Следует заметить, что данная процедура замедлит
работу ГА после прохождения первого этапа обнаружения порога «насыщения»,
так как теперь после выбора двух родителей придется сравнивать их не только
между собой, но и со всеми найденными ранее решениями. А чем больше будет
найдено решений, тем медленнее будет происходить процесс кроссинговера.
Вариант 4. Еще одним вариантом использования найденной зависимости
может быть определение приблизительного числа эпох, за которое ГА доходит до
«насыщения». Определив это число, можно оценить количество эпох (например,
среднее значение количества эпох, за которые популяция доходила до «насыще-
ния»), при котором ГА не достигает «насыщения», но при этом получаются до-
статочно точные результаты, схожие с показанными для экспериментов с высокой
вероятностью мутации. Грубо говоря, задача сводится к определению числа эпох
в зависимости от параметров мутации и вероятности кроссинговера, за которое
популяция придет в «насыщенное» состояние. Например, обозначим Т найденное
число эпох. После этого выбирается такое число эпох, при котором популяция
не успеет дойти до «насыщения», но особи при этом уже будут располагаться на
местах искомых решений. Естественно, выбранное число эпох будет меньше,
чем Т, но находиться оно должно вблизи него. Варьируя расстояние конечного
числа эпох до «точки насыщения», можно регулировать точность найденных
решений.
Описанные выше варианты предполагают, что популяция насыщена в случае
отношения размера популяции и количества дубликатов особей равного или пре-
120 ISSN 0572-2691
вышающего 0,25. Однако можно принять данный порог значительно меньшим,
тем самым внося разнообразие популяции намного чаще, но и с меньшей точно-
стью решений.
Моделирование. Для сравнения эффективности работы предложенной мо-
дификации с классическим ГА был проведен ряд экспериментов по нахождению
экстремумов поверхностей мультимодальных функций.
Для моделирования использовались следующие функции:
,
11
1)( 6 −+
=
z
zg ,Cz∈ ;iyxz += ]2,2[, −∈yx (рис. 3, а); (1)
,
))(001,01(
5,0)(sin
5,0)( 22
222
yx
yx
zg
++
−+
+= ]10,10[, −∈yx (рис. 3, б); (2)
,1)4(sin)4(sin),( +π+π−π= yyxxyxg ]2,2[, −∈yx (рис. 3, в). (3)
Эксперимент 1. В этом эксперименте сравнивалась работа классического ал-
горитма и предложенной модификации ГА с апоптозом. При моделировании бы-
ли выбраны следующие параметры: вероятность мутации 0,003, вероятность
кроссинговера 0,7, число эпох 80, начальный размер популяции 100, максималь-
ный 200. Результаты эксперимента приведены на рис. 3. Здесь рисунки слева со-
ответствуют классическому ГА, а справа — предложенной модификации.
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
а
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
б
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 121
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
в
Рис. 3
Из экспериментов следует, что при стандартных параметрах ГА предложен-
ная модификация хотя и дает лучшие результаты, она лишь частично справляется
с поставленной задачей, так как находит не все решения, а как правило, два из
них. Следует добавить, что для поверхностей, у которых есть только один ярко
выраженный глобальный экстремум, оба решения иногда могут быть практически
видны как одно (например, рис. 3, в), поскольку оба могут лежать крайне близко
один к другому.
Эксперимент 2. Был проведен эксперимент с одной из известных модифика-
ций ГА, описанной в [5], в которой используются масштабирование фитнесс-
функции и распределение ее в определенном ареале, зависящем от разрозненно-
сти популяции. В этом случае функция приспособленности выглядит следующим
образом:
,
)),((
)(
)(
1
ji
N
j
i
is
xxdsh
xf
xf
∑
=
= (4)
где )( ixf — стандартная фитнесс-функция для i-й особи; )(dsh — функция со-
седства
σ≥
σ<
σ
−=
α
sh
sh
sh
d
dd
dsh
,0
,,1)( (5)
α — константа, регулирующая форму соседства (наиболее часто α = 1); shσ — за-
данный порог разрозненности особей (в данной работе взято значение 0,003).
Функция ),( ji xxdd = определяет расстояние i-й особи до j-го индивидуума. Вы-
бор наиболее эффективной функции расстояния между особями является отдель-
ной задачей (в данных экспериментах выбрано евклидово расстояние). Очевидно,
что данная модификация существенно увеличивает время работы ГА, так как ко-
личество вычислений в одной эпохе ГА значительно больше по сравнению с
классическим ГА.
На рис. 4, a–в приведены результаты работы описанного выше модифициро-
ванного ГА без апоптоза (рисунки слева) для указанных ранее поверхностей и с
применением модификации с апоптозом (рисунки справа).
122 ISSN 0572-2691
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
а
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
б
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
в
Рис. 4
Эксперимент 3. Исследовалась работа различных рассмотренных выше вариан-
тов использования порога «насыщения». На рис. 5 отображены результаты моделиро-
вания первого и четвертого предложенных вариантов. Для обоих вариантов исполь-
зовались одинаковые параметры мутации и кроссинговера (0,003 и 0,7 соответствен-
но), начальная популяция состояла из 100 индивидуумов, конечная — из 200, число
эпох равно 80. При реализации четвертого варианта было принято следующее прави-
ло для определения нужного количества эпох, для остановки ГА: число эпох для
остановки равно 70 % от числа, которое потребовалось для достижения «насыщения»,
т.е. если задано максимальное число эпох, равное 80, а реально ГА дошел до насыще-
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 123
ния за 25 (это приблизительное число, за которое доходит ГА до «насыщения» в опи-
санных экспериментах), то всего будет пройдено 43 эпохи, что практически в два раза
меньше ожидаемого числа. Отметим, что отношение в 70 % взято произвольно (две
третьих от числа, необходимого для «насыщения») и должно быть вычислено по ходу
работы ГА на основе отношения числа дубликатов особей к общему числу особей,
участвовавших в кроссинговере, для каждой из эпох.
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
0,00
1,00
0,25
0,50
0,75
– 1,00
0,00
1,00
2,00
а
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
0,00
1,00
0,25
0,50
0,75
– 5,00
0,00
5,00
10,0
б
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
– 2,00
4,00
– 0,50
1,00
2,50
– 0,25
0,50
1,25
2,00
в
Рис. 5
124 ISSN 0572-2691
Эксперимент 4. В данном эксперименте показан сравнительный анализ
предложенной модификации ГА и известной реализации иммунного алгоритма —
алгоритма клонального отбора (CLONALG) [6]. Исследовалось также влияние ве-
личины порога «насыщенности» популяции на свойства получаемых решений.
Как было сказано ранее, порогом, при котором следует выполнить один из пред-
ложенных вариантов, может быть число, гораздо меньшее 0,25. При этом есте-
ственно разброс решений будет значительно шире, но и количество их будет су-
щественно больше. На рис. 6 приведены результаты для случая выбора порога
«насыщения», равного 0,04 (для лучшего сравнения результаты отображены про-
екциями на плоскость входных данных).
– 1,00
0,00
1,00
2,00
– 1,00
0,00
1,00
2,00
а
– 5,00
0,00
5,00
10,0
– 5,00
0,00
5,00
10,0
б
– 0,25
0,50
1,25
2,00
– 0,25
0,50
1,25
2,00
в
Рис. 6
Заключение. Экспериментальное исследование предложенных модификаций
ГА подтвердило их работоспособность и целесообразность использования для
нахождения экстремумов мультимодальных функций. Данные модификации, как
Международный научно-технический журнал
«Проблемы управления и информатики», 2013, № 1 125
и традиционный ГА, требуют корректного определения числа эпох, однако в от-
личие от классического ГА, при незаданном или неизвестном числе эпох меха-
низм апоптоза может достаточно просто определить их количество без просмотра
всей популяции, а лишь используя данные, полученные в ходе работы алгоритма.
Более того, предложенный четвертый вариант обеспечивает определение необхо-
димого количества эпох для поиска решений, что существенно упрощает вычис-
лительную реализацию данных модифицированных алгоритмов.
Следует отметить, что параметр порога насыщения может выступать универ-
сальным коэффициентом для регуляции точности и количества находимых реше-
ний, что существенно упрощает задачу применения данного алгоритма.
О.Г. Руденко, Р.В. Бобнєв
ГІБРИДНИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ
НА ОСНОВІ БІОЛОГІЧНОГО АПОПТОЗУ
Розглянуто класичний генетичний алгоритм та основні проблеми, що виника-
ють при його реалізації. Запропоновано модифікацію даного алгоритму, яка
змінює спосіб формування нових пар нащадків на основі механізму біологічно-
го апоптозу. Введено поняття насиченості популяції та запропоновано викорис-
товувати поріг насиченості для покращення роботи алгоритму. Наведено ре-
зультати експериментальних досліджень, які підтверджують ефективність за-
пропонованих модифікацій при знаходженні екстремумів мультимодальних
функцій.
O.G. Rudenko, R.V. Bobniev
HYBRID GENETIC ALGORITHM BASED
ON THE BIOLOGICAL APOPTOSIS
A classic genetic algorithm and the key issues associated with its implementation are
considered. A modification of the classic genetic algorithm which changes the way
of creating new offspring’s pairs is presented. The modification is based on the bio-
logical apoptosis theory. The saturation population conception and the suggestion
about usage of this conception as termination condition with the purpose of algorithm
improving have been introduced. The experimental research results proving efficien-
cy of suggested modifications in case of multimodal functions have been shown.
1. Holland J.H. Adaptation in natural and artificial systems. — Ann Arbor, MI : Univ. Michigan
Press, 1975. — 183 p.
2. Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и
нечеткие системы. — М. : Горячая линия – Телеком, 2006. — 452 с.
3. Скобцов Ю.А. Основы эволюционных вычислений. — Донецк : ДонНТУ, 2008. — 326 с.
4. Гордеева А.В., Лабас Ю.А., Звягильская Р.А. Апоптоз одноклеточных организмов: меха-
низмы и эволюция // Биохимия. — 2004. — 69, вып. 10. — С. 1301–1313.
5. Goldberg D.E., Richardson J. Genetic algorithms with sharing for multimodal function optimiza-
tion // Proc. of the Second Int. Conf. on Genetic Algorithms, Mahwah, NJ, USA, Lawrence Erl-
baum Associates, Inc. — 1987. — P. 41–49.
6. De Castro L.N., Von Zuben F.J. Learning and optimization using the clonal selection principle //
IEEE Transact. on Evolut. Comput., Special Issue on Artificial Immune Systems. — 2002. — 6,
N 3. — P. 239–251.
Получено 19.01.2012
Статья представлена к публикации акад. НАН Украины А.В. Палагиным.
|
| id | nasplib_isofts_kiev_ua-123456789-207592 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T17:47:46Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Руденко, О.Г. Бобнєв, Р.В. 2025-10-10T09:10:55Z 2013 Гибридный генетический алгоритм на основе биологического апоптоза / О.Г. Руденко, Р.В. Бобнев // Проблемы управления и информатики. — 2013. — № 1. — С. 115–125. — Бібліогр.: 6 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207592 519.71 10.1615/JAutomatInfScien.v45.i2.80 Розглянуто класичний генетичний алгоритм та основні проблеми, що виникають при його реалізації. Запропоновано модифікацію даного алгоритму, яка змінює спосіб формування нових пар нащадків на основі механізму біологічного апоптозу. Введено поняття насиченості популяції та запропоновано використовувати поріг насиченості для покращення роботи алгоритму. Наведено результати експериментальних досліджень, які підтверджують ефективність запропонованих модифікацій при знаходженні екстремумів мультимодальних функцій. A classic genetic algorithm and the key issues associated with its implementation are considered. A modification of the classic genetic algorithm which changes the way of creating new offspring’s pairs is presented. The modification is based on the biological apoptosis theory. The saturation population conception and the suggestion about usage of this conception as termination condition with the purpose of algorithm improving have been introduced. The experimental research results proving efficiency of suggested modifications in case of multimodal functions have been shown. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Гибридный генетический алгоритм на основе биологического апоптоза Гібридний генетичний алгоритм на основі біологічного апоптозу Hybrid Genetic Algorithm Based on the Biological Apoptosis Article published earlier |
| spellingShingle | Гибридный генетический алгоритм на основе биологического апоптоза Руденко, О.Г. Бобнєв, Р.В. Методы обработки информации |
| title | Гибридный генетический алгоритм на основе биологического апоптоза |
| title_alt | Гібридний генетичний алгоритм на основі біологічного апоптозу Hybrid Genetic Algorithm Based on the Biological Apoptosis |
| title_full | Гибридный генетический алгоритм на основе биологического апоптоза |
| title_fullStr | Гибридный генетический алгоритм на основе биологического апоптоза |
| title_full_unstemmed | Гибридный генетический алгоритм на основе биологического апоптоза |
| title_short | Гибридный генетический алгоритм на основе биологического апоптоза |
| title_sort | гибридный генетический алгоритм на основе биологического апоптоза |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207592 |
| work_keys_str_mv | AT rudenkoog gibridnyigenetičeskiialgoritmnaosnovebiologičeskogoapoptoza AT bobnêvrv gibridnyigenetičeskiialgoritmnaosnovebiologičeskogoapoptoza AT rudenkoog gíbridniigenetičniialgoritmnaosnovíbíologíčnogoapoptozu AT bobnêvrv gíbridniigenetičniialgoritmnaosnovíbíologíčnogoapoptozu AT rudenkoog hybridgeneticalgorithmbasedonthebiologicalapoptosis AT bobnêvrv hybridgeneticalgorithmbasedonthebiologicalapoptosis |