Генетические алгоритмы оптимизации
Для построения оптимальных помехоустойчивых кодов используются генетические алгоритмы. В генетических алгоритмах в качестве «организмов» популяции используются таблицы полярности, а также три вида операций: генерирование случайных кодов для первого поколения, скрещивание кодов, мутация кодов. Для по...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2019 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/161935 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Генетические алгоритмы оптимизации / А.А. Вагис // Компьютерная математика. — 2019. — № 1. — С. 70-76. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161935 |
|---|---|
| record_format |
dspace |
| spelling |
Вагис, А.А. 2019-12-27T21:00:37Z 2019-12-27T21:00:37Z 2019 Генетические алгоритмы оптимизации / А.А. Вагис // Компьютерная математика. — 2019. — № 1. — С. 70-76. — Бібліогр.: 3 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161935 519.217.268 Для построения оптимальных помехоустойчивых кодов используются генетические алгоритмы. В генетических алгоритмах в качестве «организмов» популяции используются таблицы полярности, а также три вида операций: генерирование случайных кодов для первого поколения, скрещивание кодов, мутация кодов. Для побудови оптимальних завадостійких кодів виконувались генетичні алгоритми. У генетичних алгоритмах як «організми» популяції використовувалися таблиці полярності, а також три види операцій: вибір випадкових кодів для першого покоління; схрещування кодів; мутації кодів. We apply genetic algorithms to construct noise-free optimal codes. In genetic algorithms, the polarity tables are used as the “organisms” of a population, as well as three types of operations: generation of random codes for the first generation, crossing and mutation of codes. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Генетические алгоритмы оптимизации Генетичні алгоритми оптимізації Genetic algorithms of optimization Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Генетические алгоритмы оптимизации |
| spellingShingle |
Генетические алгоритмы оптимизации Вагис, А.А. Оптимизация вычислений |
| title_short |
Генетические алгоритмы оптимизации |
| title_full |
Генетические алгоритмы оптимизации |
| title_fullStr |
Генетические алгоритмы оптимизации |
| title_full_unstemmed |
Генетические алгоритмы оптимизации |
| title_sort |
генетические алгоритмы оптимизации |
| author |
Вагис, А.А. |
| author_facet |
Вагис, А.А. |
| topic |
Оптимизация вычислений |
| topic_facet |
Оптимизация вычислений |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Генетичні алгоритми оптимізації Genetic algorithms of optimization |
| description |
Для построения оптимальных помехоустойчивых кодов используются генетические алгоритмы. В генетических алгоритмах в качестве «организмов» популяции используются таблицы полярности, а также три вида операций: генерирование случайных кодов для первого поколения, скрещивание кодов, мутация кодов.
Для побудови оптимальних завадостійких кодів виконувались генетичні алгоритми. У генетичних алгоритмах як «організми» популяції використовувалися таблиці полярності, а також три види операцій: вибір випадкових кодів для першого покоління; схрещування кодів; мутації кодів.
We apply genetic algorithms to construct noise-free optimal codes. In genetic algorithms, the polarity tables are used as the “organisms” of a population, as well as three types of operations: generation of random codes for the first generation, crossing and mutation of codes.
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161935 |
| citation_txt |
Генетические алгоритмы оптимизации / А.А. Вагис // Компьютерная математика. — 2019. — № 1. — С. 70-76. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT vagisaa genetičeskiealgoritmyoptimizacii AT vagisaa genetičníalgoritmioptimízacíí AT vagisaa geneticalgorithmsofoptimization |
| first_indexed |
2025-11-26T14:38:18Z |
| last_indexed |
2025-11-26T14:38:18Z |
| _version_ |
1850624770395078656 |
| fulltext |
70 ISSN 2616-938X. Компьютерная математика. 2019, № 1
Для построения оптимальных
помехоустойчивых кодов исполь-
зуются генетические алгоритмы.
В генетических алгоритмах в
качестве «организмов» популяции
используются таблицы полярно-
сти, а также три вида операций:
генерирование случайных кодов
для первого поколения, скрещи-
вание кодов, мутация кодов.
А.А. Вагис, 2019
удк 519.217.268
А.А. ВАГИС
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
ОПТИМИЗАЦИИ
Введение. Генетический алгоритм (ГА) по-
зволяет найти удовлетворительное решение
труднорешаемых задач путем последова-
тельного подбора и комбинирования иско-
мых параметров с использованием механиз-
мов, напоминающих биологическую эволю-
цию. Источником возникновения этих мето-
дов стали несколько открытий в биологии.
Чарльз Дарвин опубликовал в 1859 году
свою знаменитую работу «Происхождение
видов», где были провозглашены основные
принципы эволюционной теории [1]: наслед-
ственность (потомки сохраняют свойства
родителей); изменчивость (потомки почти
всегда не идентичны); естественный отбор
(выживают наиболее приспособленные). Тем
самым было показано, какие принципы при-
водят к эволюционному развитию флоры и
фауны под влиянием окружающей среды.
Однако вопрос о том, как генетическая ин-
формация передается от родителей потом-
кам, долгое время оставался открытым.
В 1953 году в номере журнала Nature вышла
статья Уотсона и Крика, которые впервые
предложили модель двухцепочной спирали
ДНК [2]. Таким образом, стали известны все
необходимые компоненты для реализации
эволюционной модели.
Принцип работы ГА. Генетические алго-
ритмы оперируют совокупностью особей
(популяцией), которые представляют собой
строки, кодирующие одно из решений
задачи. Этим ГА отличается от большинства
других алгоритмов оптимизации, которые
оперируют лишь с одним решением, улуч-
шая его, как это происходит, например,
в градиентных методах. С помощью целевой
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ
ISSN 2616-938X. Компьютерная математика. 2019, № 1 71
функции приспособленности среди всех особей популяции выделяют: наиболее
приспособленные (более подходящие решения), которые получают возмож-
ность скрещиваться и давать потомство; наихудшие (плохие решения), которые
удаляются из популяции и не дают потомства. Таким образом, приспособлен-
ность нового поколения в среднем выше предыдущего. В классическом ГА
начальная популяция формируется случайным образом; размер популяции
(количество особей L) фиксируется и не изменяется в течении работы всего
алгоритма.
ГА дает преимущества при решении практических задач. Одно из них – это
адаптация к изменяющейся окружающей среде. В реальной жизни поставленная
задача может претерпевать большие изменения в процессе своего решения. При
использовании традиционных методов все вычисления приходится начинать
заново, что приводит к значительным затратам машинного времени. При эволю-
ционном подходе популяцию можно анализировать, дополнять и видоизменять
применительно к изменяющимся условиям, для этого не требуется полный
перебор.
На рисунке показана схема работы любого генетического алгоритма. Про-
анализируем работу ГА на примере определения оптимальных помехоустойчи-
вых генетических кодов.
РИСУНОК
Помехоустойчивость генетических кодов. В работе [3] исследована поме-
хоусточивость стандартного генетического кода относительно полярности
аминокислот при точечных мутациях нуклеотидов в кодоне. Если в результате
мутации полярный остаток в белке сменится на неполярный (или наоборот),
А.А. ВАГИС
ISSN 2616-938X. Компьютерная математика. 2019, № 172
то форма молекулы может измениться настолько, что белок не сможет выпол-
нять свою функцию. В табл.1 неполярные аминокислоты выделены жирным
шрифтом. Каждый триплет допускает 9 однократных замен, число кодирующих
аминокислоты триплетов равно 61. Для стандартного кода возможны 526 заме-
щений, в которых кодон до и после мутации не является одним из трех стоп-
кодонов, из них 364 замещения не меняют полярность, т. е. его помехоустойчи-
вость составляет 364/526 = 69,20 %. Помехоустойчивость кода – целевая функ-
ция в генетических алгоритмах при построении оптимальних кодов.
ТАБЛИЦА 1. Стандартный генетический код организмов
Второе основаниеПервое
основа-
ние T C A G
Третье
осно-
вание
T фенилаланин серин тирозин цистеин T
фенилаланин серин тирозин цистеин C
лейцин серин стоп стоп A
лейцин серин стоп триптофан
(W), н
G
C лейцин пролин гистидин агринин T
лейцин пролин гистидин агринин C
лейцин пролин глутамин агринин A
лейцин пролин глутамин агринин G
A изолейцин треонин аспарагин серин T
изолейцин треонин аспарагин серин C
изолейцин треонин лизин агринин A
метионин треонин лизин агринин G
G валин аланин асп. к-та глицин T
валин аланин асп. к-та глицин C
валин аланин глут. к-та глицин A
валин аланин глут. к-та глицин G
Для генетических алгоритмов нужно выполнять три вида операций: генери-
ровавать случайные коды для первого поколения; скрещивать коды; подвергать
коды мутациям.
Генерация. Пусть St – стандартный генетический код, S = {0,1, stop},
где 0 соответствует неполярным аминокислотам, 1 – полярным, ( )stP s ,
s S – вероятности встречи в нем соответствующих состояний:
11( ) | ( ) |
64stP s St s .
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ
ISSN 2616-938X. Компьютерная математика. 2019, № 1 73
Начальное поколение состоит из случайных «перестановок» стандартного
генетического кода, поскольку он уже обладает довольно высокой помехоустой-
чивостью, а наша цель состоит в построении оптимальных кодов. Тогда случай-
ный код code можно генерировать как
с вероятностью
с вероятностью
, ( ),
( )
, ( ).
st
st
x P x
code c
stop P stop
Скрещивание. Пусть заданы два кода 1code и 2;code тогда результат
их скрещивания ( )code c { 1( ),code c с вероятностью 1/2; 2 ( )code c , с вероят-
ностью 1/2}.
Мутации. Пусть задан код code и вероятность мутации p. Результат мутации –
с вероятностью
с вероятностью
с вероятностью
( ), (1 ),
, ( ) / (1 ( ( ))),
( )
, ( ) / (1 ( ( ))).
st st
st st
code c p
x pP x P code c
code c
stop pP stop P code c
Оптимальные генетические коды. В ГА в качестве «организмов» популя-
ции использовались не сами генетические коды, а таблицы полярности, которые
ставят в соответствие каждому кодону один из трех типов информации: поляр-
ную аминокислоту, неполярную аминокислоту или стоп-кодон. Таким образом,
значения клеток таблицы принадлежат множеству S = {0,1, stop}.
С помощью таблиц полярности можно избавиться от избыточной информа-
ции. Количество вариантов генетических кодов оценивается примерно величи-
ной 6421 (это число превосходит 8010 ), а таблиц полярности – всего 643
(это число не превосходит 3010 ). Поэтому с помощью генетических алгоритмов
удалось достаточно экономно и быстро построить оптимальные варианты по-
мехоустойчивых генетических кодов.
При выполнении операции мутации значение кода, соответствующее каж-
дому из 64 кодонов, может с определенной вероятностью p измениться на дру-
гое возможное значение, причем распределение вероятностей перехода соответ-
ствует распределению значений в стандартном генетическом коде.
А.А. ВАГИС
ISSN 2616-938X. Компьютерная математика. 2019, № 174
Использовались следующие параметры алгоритма: количество поколений
T = 50000; размер начального поколения N = 50; максимальный размер поколе-
ния L = 250; число скрещиваний и мутаций для каждого кода 4=N c и 2=Nm
соответственно; вероятность мутации в отдельном кодоне p = 0,1.
В отличие от методов оптимизации операции скрещивания и мутации при-
меняются для каждого кода в текущем поколении. Наихудшие помехоустойчи-
вые коды, которые например не удовлетворяют характеристикам стандартного
кода или близким кодам, удаляются из множества кодов поколения. Как извест-
но, в градиентных процедурах оптимизации поиск оптимального решения про-
водится на каждой итерации для одного или нескольких векторов состояний.
Один из полученных оптимальных симметричных генетических кодов по
отношению к полярности приведен в табл. 2. Этот код можно получить из стан-
дартного кода с помощью восьми парных перестановок. В симметричном коде
кодон ( )ijk кодирует полярную аминокислоту, а антикодон ( )kji – неполярную,
либо наоборот. С помощью генетических алгоритмов построены различные ва-
рианты наиболее помехоустойчивых кодов (78,30 %), отличающиеся от стан-
дартного кода числом стоп-кодонов и количеством триплетов, определяющих
полярные и неполярные аминокислоты (например, количество стоп кодонов в
кодах этого класса изменялось от 2 до 4, количество кодонов полярных и непо-
лярных аминокислот – от 27 до 34).
ТАБЛИЦА 2. Оптимальный симметричный код
Второе основаниеПервое
основа-
ние T C A G
Третье
основа-
ние
T фенилаланин стоп тирозин серин T
фенилаланин триптофан тирозин серин C
лейцин цистеин стоп серин A
лейцин цистеин стоп серин G
C лейцин пролин гистидин аргинин T
лейцин пролин гистидин аргинин C
лейцин пролин глутамин аргинин A
лейцин пролин глутамин аргинин G
A изолейцин глицин аспарагин серин T
изолейцин глицин аспарагин серин C
изолейцин глицин лизин аргинин A
метионин глицин лизин аргинин G
G валин аланин асп. к-та треонин T
валин аланин асп. к-та треонин C
валин аланин глут. к-та треонин A
валин аланин глут. к-та треонин G
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ
ISSN 2616-938X. Компьютерная математика. 2019, № 1 75
Заметим, что оптимальных помехоустойчивых кодов существует несколько.
Симметрия кода, понимаемая как переход от полярной аминокислоты к непо-
лярной при переходе от кодона к антикодону, не является необходимым услови-
ем оптимальности генетического кода.
Если в коде, приведенном в табл. 2, поменять местами аминокислоты столб-
цов C и A, получим код, для которого симметрия не выполняется вообще: кодон
и антикодон кодируют аминокислоту одного типа, поскольку неполярные амино-
кислоты содержатся в столбцах T и A, а полярные – в столбцах C и G. Поэтому
помехоустойчивость кода такая же, как у симметричного кода – 77,86 %.
Если во всех кодонах кода в табл. 2 переставить местами второй и третий
нуклеотиды, т. е. в каждой строке кодоны «повернуть на 90 градусов», получим
код с такой же помехоустойчивостью, что и симметричный код, в котором сим-
метрия выполняется примерно в половине случаев. В этом коде неполярные
аминокислоты определяются триплетами с третьим нуклеотидом T и C, а у по-
лярных аминокислот третий нуклеотид – A и G.
Выводы. ГА – новая фундаментальная область исследований, основанная
Д. Холландом, впервые примененная для решения задач оптимизации и распо-
знавания образов. ГА моделируют в определенной степени механизмы развития
органического мира на Земле. В настоящее время ГА – это мощный адаптивный
поисковый метод, основанный на эволюционных факторах конструирования
популяции, естественного отбора, селекции, мутации, которые реализованы
в работе для построения оптимальных генетических кодов.
Как уже отмечалось выше, число вариантов генетических кодов превосхо-
дит астрономическую величину 8010 . Если ежесекундно перебирать генетиче-
ские коды, то за 10 миллиардов лет количество просмотров не превосходит
величину 1810 . Такую мизерную долю как 6210 невозможно зафиксировать
даже в квантовой механике. Поэтому весьма проблематично путем естественно-
го отбора живых организмов построить стандартный генетический код с доста-
точно высоким уровнем помехоустойчивости.
В ГА в качестве «организмов» популяции использовались не сами генетиче-
ские коды, а таблицы полярности, которые ставят в соответствие каждому кодо-
ну один из трех типов информации: полярную аминокислоту, неполярную ами-
нокислоту или стоп-кодон. С помощью таблиц полярности удалось избавиться
от огромной избыточной информации.
С помощью генетических алгоритмов удалось построить оптимальные ва-
рианты помехоустойчивых кодов. Найти такие варианты генетических кодов на
основе оптимизационных градиентных процедур невозможно.
А.А. ВАГИС
ISSN 2616-938X. Компьютерная математика. 2019, № 176
О.А. Вагіс
ГЕНЕТИЧНІ АЛГОРИТМИ ОПТИМІЗАЦІЇ
Для побудови оптимальних завадостійких кодів виконувались генетичні алгоритми. У гене-
тичних алгоритмах як «організми» популяції використовувалися таблиці полярності, а також
три види операцій: вибір випадкових кодів для першого покоління; схрещування кодів; мута-
ції кодів.
A.A. Vagis
GENETIC ALGORITHMS OF OPTIMIZATION
We apply genetic algorithms to construct noise-free optimal codes. In genetic algorithms, the polar-
ity tables are used as the “organisms” of a population, as well as three types of operations: genera-
tion of random codes for the first generation, crossing and mutation of codes.
Список литературы
1. Дарвин Ч. Происхождение видов путем естественного отбора или сохранение благо-
приятных рас в борьбе за жизнь. Санкт-Петербург: Наука, 1991. 544 с.
2. Watson J.D., Crick F.H. A structure for Deoxyribose Nucleic Acid. Nature. 1953. 171.
P. 737 – 738.
3. Гупал А.М., Сергиенко И.В. Симметрия в ДНК. Методы распознавания дискретных
последовательностей. К.: Наукова думка, 2016. 228 с.
Получено 07.08.2019
Об авторе:
Вагис Александра Анатольевна,
доктор физико-математических наук, ведущий научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
|