Диплоидный генетический алгоритм со смертностью

Запропоновано метод удосконалення диплоїдного генетичного алгоритму оптимізації шляхом ймовірнісного обмеження тривалості життя особин. Середня тривалість життя особин визначається залежно від розміру популяції, виходячи з оцінки вартості заміщення Холдейна. Закон і параметри розподілу ймовірності с...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автор:	Махотило, К.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Назва видання:	Проблемы управления и информатики
Теми:	Методы обработки информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207317
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Диплоидный генетический алгоритм со смертностью / К.В. Махотило // Проблемы управления и информатики. — 2011. — № 3. — С. 138–150. — Бібліогр.: 23 назви. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207317
record_format	dspace
spelling	irk-123456789-2073172025-10-06T00:11:26Z Диплоидный генетический алгоритм со смертностью Диплоїдний генетичний алгоритм зі смертністю Diploid Genetic Algorithm with Mortality Махотило, К.В. Методы обработки информации Запропоновано метод удосконалення диплоїдного генетичного алгоритму оптимізації шляхом ймовірнісного обмеження тривалості життя особин. Середня тривалість життя особин визначається залежно від розміру популяції, виходячи з оцінки вартості заміщення Холдейна. Закон і параметри розподілу ймовірності смерті особини визначені за даними демографічної статистики. Показано ефективність методу при розв’язанні задач синтезу прямоспрямованих нейронних мереж. The method of improvement of diploid genetic algorithm via probabilistic limitation of individual’s lifespan is offered. Mean lifespan of individual is determined depending on the population size based on Haldane’s substitution cost estimation. The individual death probability distribution law and parameters are determined based on demographic statistics data. It is shown the efficiency of proposed method for synthesis of feedforward neural networks. 2011 Article Диплоидный генетический алгоритм со смертностью / К.В. Махотило // Проблемы управления и информатики. — 2011. — № 3. — С. 138–150. — Бібліогр.: 23 назви. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207317 519.7 10.1615/JAutomatInfScien.v43.i6.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Махотило, К.В. Диплоидный генетический алгоритм со смертностью Проблемы управления и информатики
description	Запропоновано метод удосконалення диплоїдного генетичного алгоритму оптимізації шляхом ймовірнісного обмеження тривалості життя особин. Середня тривалість життя особин визначається залежно від розміру популяції, виходячи з оцінки вартості заміщення Холдейна. Закон і параметри розподілу ймовірності смерті особини визначені за даними демографічної статистики. Показано ефективність методу при розв’язанні задач синтезу прямоспрямованих нейронних мереж.
format	Article
author	Махотило, К.В.
author_facet	Махотило, К.В.
author_sort	Махотило, К.В.
title	Диплоидный генетический алгоритм со смертностью
title_short	Диплоидный генетический алгоритм со смертностью
title_full	Диплоидный генетический алгоритм со смертностью
title_fullStr	Диплоидный генетический алгоритм со смертностью
title_full_unstemmed	Диплоидный генетический алгоритм со смертностью
title_sort	диплоидный генетический алгоритм со смертностью
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207317
citation_txt	Диплоидный генетический алгоритм со смертностью / К.В. Махотило // Проблемы управления и информатики. — 2011. — № 3. — С. 138–150. — Бібліогр.: 23 назви. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT mahotilokv diploidnyjgenetičeskijalgoritmsosmertnostʹû AT mahotilokv diploídnijgenetičnijalgoritmzísmertnístû AT mahotilokv diploidgeneticalgorithmwithmortality
first_indexed	2025-10-07T01:08:46Z
last_indexed	2025-10-07T01:08:46Z
_version_	1845283338235936768
fulltext	© К.В. МАХОТИЛО, 2011 138 ISSN 0572-2691 УДК 519.7 К.В. Махотило ДИПЛОИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ СО СМЕРТНОСТЬЮ Введение Генетический алгоритм (ГА) Холланда уверенно можно назвать самым рас- пространенным и универсальным методом оптимизации, моделирующим процесс естественной эволюции. Непростая полувековая история развития и распростра- нения ГА непосредственно связана с усовершенствованием вычислительной тех- ники и расширением сфер практического применения алгоритма [1]. В 1990-х гг. начался важный этап этой истории, связанный с использованием ГА для структур- ного и параметрического синтеза искусственных нейронных сетей (ИНС) [2–4]. Объединение двух этих технологий сформировало новую вычислительную пара- дигму [5] для решения широкого круга прикладных задач моделирования и уп- равления, а также совместно с нечеткой логикой и вероятностными методами стало неотъемлемой составляющей обобщенного понятия «мягких вычислений» (soft computing) [6]. Развитию методов эволюционного синтеза многослойных перцептронов (МСП) и сетей с радиальными базисными функциями (РБФ) содей- ствовали и ученые Украины, в том числе представители харьковских научных школ [7–12]. Новая сфера применения ГА предъявила новые требования к его эффектив- ности. Обучение ИНС вообще и прямонаправленных слойных сетей, в частности, относится к специфическому классу задач оптимизации, характеризующемуся высокой размерностью и крайне высокой степенью полимодальности. Кроме того, наличие участков насыщения в активационных функциях нейронов, а также экви- валентность различных комбинаций нейронов в слоях ИНС определяют наличие в рельефе целевой функции (ЦФ) множества обширных плато. Это приводит к увеличению числа итераций ГА и вычислений ЦФ, необходимых для решения оптимизационной задачи, а значит, увеличению риска неполучения за ограничен- ное время точно настроенной ИНС. Учитывая постоянный рост быстродействия компьютеров, эту проблему можно было бы считать некритической. Однако многолетний опыт применения ГА для синтеза нейросетевых моделей и систем управления динамическими объ- ектами и процессами [13, 14] показывает, что увеличение быстродействия нового поколения ЭВМ прежде всего используется для расширения класса решаемых за- дач, приближения их к реальным условиям, и значит, усложнения, а метод опти- мизации остается ограниченным в вычислительных и временнх ресурсах. По- этому поиск новых путей повышения эффективности ГА за счет усовершенство- вания и адаптации его к особенностям решаемых оптимизационных задач актуален и сегодня. К такому типу прикладных задач, выявляющих недостаточную эффектив- ность классического ГА в условиях ограниченного времени поиска, относится синтез нейросетевых моделей [15] и регуляторов температуры теплоносителя [16] для АСУ теплоснабжением от крупной загородной ТЭЦ. Цель данного исследова- ния — усовершенствование ГА в части механизма элиминации особей для обес- печения успешного и быстрого решения этих задач. Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 139 Генетический алгоритм ГА как метод глобальной оптимизации решает задачу extr;)(F x ,Dx (1) где x — вектор переменных задачи оптимизации, ;nRx )(F  — ЦФ задачи оп- тимизации, ;1:F n D — область допустимых значений x. В обобщенном виде ГА можно представить итерационной зависимостью вида },),(GA{)1( GAptt  ;}{ ,1 Nii   ,,  (2) где )(t — популяция особей в t-й эпохе эволюции; t — номер эпохи (итерации) ГА, }GA{  — набор правил преобразования генотипа популяции в каждой эпохе (репродуктивный план ГА); GAp — вектор настроечных параметров ГА (коэф- фициент селекции, частота мутации, кроссовера, инверсии и т.д.); N — количе- ство особей в популяции (размер популяции);  — особь;  — генотип особи (хромосома);  — приспособленность особи (например, для задач минимизации ).F(x Репродуктивные планы разных версий ГА описаны во многих рабо- тах, в частности, в [5]. В определенных условиях принятые при создании ГА упрощения природного процесса эволюции могут быть источником снижения его эффективности. Для используемой нами диплоидной версии ГА (ДГА) [7] с постоянным размером по- пуляции и элитарной стратегией элиминации таким источником может быть кон- цепция «бессмертности» особей. В соответствии с этой концепцией единственный путь удаления особи из популяции — ее вытеснение в конец ранжира более при- способленными потомками, поэтому любая особь родительской группы теорети- чески может находиться в популяции неограниченное число эпох, т.е. быть бес- смертной. Негативное влияние бессмертности особей проявляется в ряде сценари- ев развития эволюции, достаточно часто возникающих при решении сложных задач в том числе при синтезе ИНС, причем частота их возникновения и негатив- ные последствия выше для популяций меньшего размера. Первый, наиболее общий сценарий, — это появление в популяции «суперос- оби», значительно превосходящей по приспособленности остальных родитель- ских особей, но удаленной от них в пространстве поиска. Иллюстрирующий его условный пример развития эволюции популяции при бессмертности особей пред- ставлен на рис. 1. Появившаяся в начале сценария особь  расположена в точке локального экстремума x (обозначена кружком). Все остальные особи сконцентрированы вблизи другой точки локального экстремума x  (обозначена крестом), удаленной от x в поисковом пространстве. Точка x соответствует субоптимальному ло- кальному экстремуму, а x  — лучшему или, в частном случае, глобальному экс- тремуму. Однако  расположена точно в ,x а остальные особи недостаточно близки к ,x  поэтому  значительно превосходит их по приспособленности )()( i .],,1[  iNi Поэтому обозначим  как «суперособь» попу- ляции. Далее популяция эволюционирует, постепенно улучшая свою среднюю приспособленность, но длительное время не может произвести потомков, сравни- мых по приспособленности с «суперособью». И лишь после достаточно большого количества эпох популяция сжимается вокруг точки x  и вытесняет из себя  (см. рис. 1). 140 ISSN 0572-2691 x2 F(x) Избыточное время жизни особи Время жизни особи F(x) x2 x1 x1 x1 x1 x2 x2 x t Рис. 1 Анализ этого сценария показывает, что вклад «суперособи» в эволюцию по- пуляции не больше, чем роль источника генетического разнообразия. Если по- томки, полученные с участием , расположатся вблизи ,x то они не будут более перспективными, чем сама , а если расположатся в окрестности ,x  то будут содержать минимальное количество генов . Получение же потомков в других областях поискового пространства возможно и без участия  за счет мутации или рецессивных генов, т.е. гены «суперособи», обеспечившие ей высокую приспо- собленность, не будут унаследованы потомками, так как обладают низкой бене- фициарностью (выгодностью) для популяции. На рис. 1 период от появления «суперособи»  до ее вытеснения из популя- ции обозначен как «время жизни». Пока остальные особи популяции остаются менее приспособленными )()( i ],,1[ Ni ,i и невозможно опреде- лить, являются ли гены  бенефициарными, целесообразность сохранения или удаления  из популяции неочевидна. Однако после того как  перестает быть лучшей особью )()( 1 , целесообразность ее принудительного удаления с каждой следующей эпохой становится все более очевидной, так как оно лишь ускорит естественный процесс вытеснения из популяции. Этот период обозначен на рис. 1 как «избыточное время жизни». Обобщая этот пример, можно заключить, что независимо от места в ранжире чрезмерно длительное нахождение в популяции особей, не дающих конкуренто- способных потомков, бесперспективно для эволюции и снижает ее скорость. По- лучение от них потомства в избыточное время их жизни зря потребляет вычисли- тельный ресурс, а сами они, занимая место в родительской группе, ограничивают вхождение в популяцию менее приспособленных, но более перспективных по- томков. Чем меньше избыточное время жизни особи, тем выше скорость поиска решения. Другими сценариями, выявляющими негативное влияние бессмертности, яв- ляются попадание популяции на одно обширное плато в рельефе ЦФ и разделение популяции между несколькими областями локальных экстремумов с близкими Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 141 значениями ЦФ. Сценарий попадания популяции на плато характерен для приме- нения комбинированной методики синтеза РБФ-сетей, использующей матричный метод расчета выходных параметров РБФ-сети [11]. Эта методика упрощает по- иск оптимальных параметров скрытого слоя РБФ-сети и сглаживает ЦФ ГА, од- нако при этом на ландшафте ЦФ в областях локальных экстремумов образуются обширные плато. Сценарий разделения популяции между несколькими областями более характерен для синтеза МСП. Причиной его возникновения является нали- чие множества эквивалентных вариантов перестановок нейронов в скрытом слое, и значит, координат в векторе переменных задачи оптимизации. В обоих сценариях развития эволюции применение операторов комбинатив- ной изменчивости (кроссовера) с большой вероятностью дает потомков, облада- ющих приспособленностью, одинаковой с особями родительской группы. Попу- ляция резко снижает скорость своей эволюции, переходя от сжатия и направлен- ного движения в поисковом пространстве к хаотическому перемещению особей по плато или «перескакиванию» с одной области локальных экстремумов на дру- гую. Внешне это проявляется как «несжимаемость» популяции в пространствах поиска и значений ЦФ на протяжении большого числа эпох. Движущей силой эволюции становятся операторы мутационной изменчивости, т.е. случай- ный поиск, что негативно сказывается на скорости поиска решения. В такой ситу- ации удаление особей, слишком долго находящихся в популяции, позволяет осво- бодить место для потомков хоть и мене приспособленных, но расположенных в других областях поискового пространства, тем самым разнообразить популяцию и повысить эффективность комбинативной составляющей поиска. Таким образом, во всех рассмотренных выше сценариях развития эволюции принудительное удаление из популяции особей с низкобенефициарными генами не ухудшит поисковые способности ГА и должно положительно сказаться на ско- рости поиска. Наиболее перспективным способом выявления и удаления таких особей является введение в репродуктивный план ГА механизма естественной смертности, ограничивающего продолжительность жизни особей в популяции и регулирующего ее разнообразие. Первые исследования способов введения смертности в ГА были представ- лены в работах З. Михалевича в середине 1990-х годов. Он предложил вариант ГА с переменным размером популяции GAVaPS (GA with variable population size) [17], в котором управление размером популяции осуществляется с помощью ограничения продолжительности жизни особей. Особенностью GAVaPS и его многочисленных вариаций [18] является привязка максимальной продолжитель- ность жизни особи к ее относительной приспособленности в популяции, а также замена процедуры отбора на элиминацию старых особей. Другим подходом стал Adam-Eve GA, разработанный в [19] для приближе- ния GAVaPS к природным механизмам смертности. Продолжительность жизни особи в Adam-Eve GA регулируется оператором смерти, который применяется случайно с вероятностью 0,9 ко всем особям, чей возраст превысил установлен- ный порог. Однако правила выбора этого порога четко не определены. Эти варианты ГА со смертностью особей смогли показать принципиальную работоспособность и эффективность предложенного подхода, однако всем им свойственны общие серьезные недостатки. Использованные в них правила опре- деления продолжительности жизни или вероятности смерти особи не имеют ни биологического прототипа, ни математического обоснования, а настройки их па- раметров не является универсальными для разных задач. В данной работе, не претендуя на полное копирование природных механиз- мов смертности, предлагается новый подход к ограничению продолжительности жизни особи в ГА, базирующийся на математических моделях популяционной ге- нетики и результатах демографических исследований человеческой популяции. 142 ISSN 0572-2691 В рамках этого подхода смертность особи рассматривается как случайное явле- ние, вероятность которого зависит от возраста особи, а средняя продолжитель- ность жизни особей выбирается такой, чтобы обеспечить их бенефициарным ге- нам возможность закрепиться в популяции. Средняя продолжительность жизни особи Для определения средней продолжительности жизни особи в ГА воспользу- емся понятием математической теории популяционной генетики «цена замеще- ния» (substitution cost). Этот термин ввел один из основателей популяционной генетики Дж. Хол- дейн [20]. Упрощенно цена замещения sC — это нормализованное к размеру по- пуляции число смертей, необходимых для возникновения «замещения», т.е. заме- ны в геноме популяции одного гена новым бенефициарным, улучшающим при- способленность особи. Холдейн оценил, что для популяции диплоидных организмов постоянного размера цена замещения sC лежит в пределах от 10 до 100 и в среднем равна 30, т.е. замещение одного гена требует количество смертей особей, равное тридцатикратному размеру популяции. Холдейн указывал, что его оценка цены замещения получена при значитель- ных допущениях и в дальнейшем может быть существенно уточнена. Тем не ме- нее позже она стала основанием для спекуляций креационистов и формулирования так называемой «дилеммы Холдейна», которая используется ими для обоснования невозможности эволюции человека от общего прародителя до homo sapiens за не- сколько миллионов лет. Основой этих спекуляций является предположение, что цена замещения для mn одновременных мутаций равна .30 mn Однако на сего- дняшний день проведено множество исследований, уточняющих цену замещения с учетом различных особенностей эволюции популяций живых организмов и но- вых знаний о геноме человека [21]. В большинстве они показывают, что цена за- мещения для одновременных мутаций зависит от множества характеристик попу- ляции и растет намного медленнее mn или не зависит от mn вообще. Таким образом, оценка Холдейна цены замещения требует существенной коррекции для исследования процессов эволюции в природе. Однако она остается справедливой для моделирования эволюции искусственной популяции, отвечаю- щей принятым Холдейном допущениям. Среди них диплоидное представление особей, стационарность внешней среды, независимость генов в различных локу- сах, фиксированный размер популяции и коэффициент селекции (давления отбо- ра) sk равный 10 %. Всем им полностью удовлетворяет ДГА [7]. Поэтому, при- нимая в качестве правила независимость цены замещения от числа одновремен- ных мутаций, можно использовать оценку 30sC для определения средней продолжительности жизни диплоидной особи L ~ в ДГА. Положив, что в каждом поколении эволюции все потомки получаются с уча- стием особи — носителя бенефициарных генов, можно получить нижнюю оценку величины средней продолжительности жизни : ~ L ; ~ NCLNk ss  (3) ./ ~ ss kCL  (4) Верхняя оценка строится с учетом того, что средняя частота p участия роди- тельской особи — носителя бенефициарных генов в производстве каждого по- томка меньше единицы: . ~ NCLNpk ss  (5) Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 143 В случае ДГА с простым равномерным случайным отбором родителей сред- няя частота участия составляет , )1( 2 Nk p s  (6) отсюда . 2 )1(~ s ss k NkC L   (7) Подставляя значения параметров sC и sk в (4) и (7), получим, что продол- жительность жизни особи, обеспечивающая возможность успешного закрепления бенефициарных генов в популяции, удовлетворяет неравенству .135 ~ 300 NL  (8) Учитывая, что в общем случае разные особи родительской группы могут иметь разные шансы дать потомство в каждой эпохе, для различных стратегий от- бора можно сформулировать единое эмпирическое правило определения средней продолжительности жизни особей: .100 ~ NL  (9) Такой средней продолжительности жизни должно быть достаточно, чтобы особь успела закрепить свои бенефициарные гены в популяции. Если за это время особь не была естественным путем вытеснена ее более приспособленными потом- ками, можно считать, что ее гены оказались полезными только в локальном смысле и бесперспективны для дальнейшей эволюции всей популяции. Такую особь следует удалить даже ценой снижения средней приспособленности попу- ляции или потери лучшей особи, чтобы дать эволюции возможность, не дожи- даясь удачной мутации, «вернуться назад» и пойти другим путем, полностью используя механизмы рекомбинации. Вероятность смерти особи В ДГА, как в природе, смерть особи должна быть вероятностным, а не детер- минированным событием. Для определения закона, по которому будет выбирать- ся момент смерти каждой конкретной особи, воспользуемся методами демогра- фии и актуарной науки. Базовым показателем в них является динамика смертно- сти, характеризующаяся распределением вероятности смерти особей популяции в разном возрасте. И как показывают результаты относительно недавних иссле- дований, несмотря на все различия процессов старения у разных живых су- ществ, динамика смертности у них поразительно сходна [22]. На рис. 2, а приведена характерная для людей, мышей и дрозофил кривая выживания, т.е. зависимость доли r живых особей популяции от их относительно- го возраста ,l равного отношению возраста особи l к величине средней продол- жительности жизни L ~ для данного вида . ~ / Lll  Кривая выживания имеет ненулевой эксцесс и отличную от 1 асимметрию, поэтому распределение вероят- ности смерти особей не является гауссовым. Это наглядно подтверждает, что естественная смерть происходит не вследствие множества независимых случай- ных процессов (например, простого накопления случайных повреждений), а является результатом работы эволюционно закрепленного общего механизма, который и следует воспроизвести в ДГА. 144 ISSN 0572-2691 0 0,2 0,4 0,6 0,8 1 0 0,25 0,5 0,75 1 1,25 1,5 1,75 2 l  r 0 0,2 0,4 0,6 0,8 1 0 0,25 0,5 0,75 1 1,25 1,5 1,75 2 l * m 0 0,2 0,4 0,6 0,8 1 0 0,25 0,5 0,75 1 1,25 1,5 1,75 2 l  m а б Рис. 2 Возраст особи L в момент смерти, т.е. продолжительность ее жизни, — случайная величина непрерывного типа с функцией распределения ).()( lLPlFL  Тогда функция )(1)( lFls L — вероятность того, что особь доживет до возраста l. Она называется функцией дожития и традиционно используется в демографии и акту- арной науке: ),()( lLPls  ,0l ,1)0( s .0)( s (10) На базе функции дожития строится оценка интенсивности смертности ),(/)()( lslsl m являющаяся аналогом понятия «интенсивность отказов» в тео- рии надежности. Функция )(lm дает значение условной плотности распределения непрерывной случайной величины L (возраст в момент смерти) при условии до- жития особи до возраста l. По сути, )(lm определяет вероятность смерти особи в возрасте l — характеристику, необходимую для реализации механизма смертнос- ти в ГА: ),()( lLllLlPl m .10 m (11) На рис. 2, б приведена кривая интенсивности смертности, построенная как усреднение статистических данных о смертности в разных группах населения ве- дущих стран мира за последние 100–150 лет [22]. Исходя из принципа универ- сальности законов смертности, связанной со старением, эту кривую можно ис- пользовать для определения вероятности смерти особи в ГА. В демографии и актуарной науке для описания )(lm традиционно применяет- ся формула Гомперца: aleRl m )( [23], а в технике для описания аналогичной функции интенсивности отказов используется закон распределения Вейбулла: .)( cbll m Различия в преимуществах и недостатках этих формул существенны лишь при детальном изучении демографических данных, и ими можно прене- бречь при моделировании смертности в ГА. С точки зрения простоты про- граммной реализации предпочтительной является формула Вейбулла, так как она не содержит трансцендентных функций. Воспользовавшись ею для аппрок- симации статистических данных из [22], можно получить следующую аналитиче- скую зависимость: .) ~ /(01,0)( 8Lll m (12) Репродуктивный план ДГА со смертностью Для реализации предлагаемого механизма смертности в репродуктивном плане ДГА нужно учитывать возраст особей и модифицировать процедуру эли- минации. Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 145 В начале работы ГА в зависимости от размера популяции по (9) определяется средняя продолжительность жизни особей. На каждом шаге эволюции после ранжирования популяции с помощью (12) вычисляется вероятность смерти каждой особи в зависимости от ее возраста и случайным образом определяются умершие особи. Возраст особи принимается равным количеству эпох, в течение которых она находится в популяции. Затем из популяции элиминируются все умершие и наименее приспособлен- ные особи. Их общее количество oN определяется по следующему правилу:       ,если, ;если, NkNN NkNNk N sdd sds o (13) где dN — количество особей, умерших в данной эпохе. Количество наименее приспособленных особей ,wN элиминируемых из по- пуляции, равно .dow NNN  При выборе средней продолжительности жизни особей по (9) в большинстве случаев dN не больше единицы или двух. Ситуация, когда ,0wN т.е. количество умерших особей равно или превышает уровень, определяемый коэффициентом селекции, нетипична и может свидетельствовать о несоответствии настроек ГА сложности решаемой задачи. Далее, в соответствии с репродуктивным планом производятся oN потомков так, чтобы общий размер популяции оставался неизменным. Объединение такой схемы реализации механизма смертности с репродуктивным планом ДГА дает его новый вариант — диплоидный генетический алгоритм со смертностью (ДГАС), который представим в виде следующего итогового алгоритма. 0. Инициализировать популяцию .}{ ,1 Nii   0.1. Генерировать хромосомный набор особи i одним из двух способов: а) случайным образом генерировать бинарный код и назначить доминант- ность/рецессивность генов двух хромосом особи ;, BA i  б) бинарный код одной хромосомы i A получить по координатам извест- ного решения, доминантность/рецессивность генов назначить случайным обра- зом; хромосомный набор особи i BA, получить удвоением хромосомы: .AB  0.2. Рассчитать приспособленность особи .i 0.3. Вычислить среднюю продолжительность жизни особей . ~ L Шаг 1. Упорядочить популяцию по приспособленности особей: .1 ii Шаг 2. Элиминировать из популяции oN особей. 2.1. Вероятностным образом определить умерших особей и их количество .dN 2.2. Удалить из популяции dN умерших и wN худших особей. Шаг 3. Отобрать из родительской группы oN пар родителей ,),( BA j ,,1 oNj  .}{, ,1BA oNNii   Шаг 4. Произвести oN потомков ,j ,,1 oNj  отобранных пар родителей. 4.1. Получить хромосомный набор потомка .,: BA jj  4.1.1. Получить гамету от родителя .:A A j  4.1.1.1. Провести рекомбинацию сегментов хромосом родителя A: .,, 2,1, A BA rcrc  146 ISSN 0572-2691 4.1.1.2. Провести кроссоверы сегментов гамет: .,, 2,1,2,1, crcrrcrc  4.1.1.3. Из двух претендентов отобрать одну гамету: ., 2,1, crcrcr  4.1.1.4. Провести транслокацию генов: .trlcr  4.1.1.5. Провести инверсию генов: .invtrl  4.1.1.6. Провести мутацию генов: .mutinv  4.1.1.7. Передать гамету потомку: . j Amut  4.1.2. Получить гамету от родителя B: .B j  4.2. Оценить приспособленность потомка .: jj  4.3. Добавить потомка jj  ,, BA в популяцию на место элиминиро- ванной особи. Шаг 5. Если условия окончания поиска не выполнены, перейти к шагу 1. Сравнение эффективности ДГА и ДГАС Для оценки эффективности предложенного механизма смертности восполь- зуемся двумя тестовыми задачами. Первая задача — нахождение минимума десятимерной тестовой функции Швефеля: ,)(sin)(F 10 1    i ii xxx .500500  ix (14) Переменные ,10,1, ixi кодируются 14 битами каждая. Соответственно точ- ность нахождения координат минимума .062,0x Длина хромосомы 140 бит. Задача считается решенной при получении значений ЦФ ,8,4189)(F x что со- ответствует попаданию в область глобального минимума .3,09687,420 ix Вторая задача — синтез РБФ-сети, аппроксимирующей функцию одной пе- ременной: ;3)50sin(10 2  xxxy .10  x (15) Форма функции (15) соответствует особенностям задач моделирования су- точных графиков бытового потребления энергии жилыми массивами. Для аппрок- симации используется РБФ-сеть с 30 нейронами скрытого слоя. Целевой функци- ей задачи синтеза является среднеквадратичная ошибка (СКО) аппроксимации на наборе из 101 шаблона, полученного по значениям x, равномерно распределен- ным на интервале ]1,0[ . Синтез сети осуществляется с помощью комбинирован- ной методики [11], использующей ГА для настройки центров и ширин окон ба- зисных функций и матричный метод для расчета выходных весов сети. Для ГА число параметров задачи оптимизации составляет 60, каждый параметр кодирует- ся 10 битами, общая длина хромосомы 600 бит. Успешным решением задачи считается достижение заданного уровня СКО 002,0F при неограниченном времени поиска или достижение в серии прогонов (20–30 шт.) с ограниченным временем поиска заданных статистических показателей СКО: минимальная ,001,0min F средняя 0025,0avg F и максимальная .005,0max F На рис. 3 представлены минимальное ,min cN максимальное max cN и среднее avg cN количество вычислений целевой функции, требуемое для решения тестовой задачи (а — минимизация функции Швефеля, б — синтез РБФ-сети) с помощью ДГА и ДГАС. Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 147 0 50 100 150 200 0 100 200 300 400 500 Размер популяции 0 100 200 300 400 500 0 50 100 150 200 Nc 10 3 0 2 4 6 8 10 12 14 0 100 200 300 400 500 Размер популяции 0 100 200 300 400 500 0 2 4 6 8 Nc 10 6 10 12 14 а б Рис. 3 Примечание 1: — min cN для ДГА; — avg cN для ДГА; — min cN для ДГА; — min cN для ДГАС; — avg cN для ДГАС; — min cN для ДГАС. Как видно, кривые min cN и avg cN для ДГА и ДГАС достаточно близки, а наибольшие различия наблюдаются между кривыми .max cN Так, при использова- нии малых популяций размером до 50 особей ДГАС демонстрирует намного меньшие значения max cN по сравнению с ДГА. В случае относительно простой задачи минимизации функции Швефеля с увеличением размера популяции свыше 200 особей эффективность ДГА и ДГАС сравнивается и по этому показателю. А в случае более сложной задачи синтеза РБФ-сети преимущество ДГАС по величине max cN сохраняется и при больших размерах популяции, причем с ростом размера популяции кривая max cN для ДГАС растет так же, как avg cN для ДГА. Эти результаты подтверждают, что использование механизма смертности по- вышает эффективность ДГАС при неблагоприятных условиях эволюционного моделирования, когда эффективность обычного ДГА с «бессмертными» особями падает. А в благоприятных условиях, при удачном быстром ходе эволюции, когда максимальное время нахождения особи в популяции гораздо меньше рекомендо- ванной средней продолжительности жизни, механизм смертности фактически не срабатывает, и ДГАС превращается в обычный ДГА. Таким образом, обладая в среднем одинаковой с ДГА эффективностью поиска, ДГАС отличается значи- тельно меньшим риском ненахождения решения за ограниченное число вычисле- ний целевой функции, особенно при небольшом размере популяции. Для более детального анализа влияния механизма смертности на скорость поиска рассмотрим тестовую задачу синтеза РБФ-сети со вторым вариантом определения успешности ее решения. На рис. 4 представлены среднее Favg, ми- нимальное Fmin и максимальное Fmax значения ЦФ задачи после 40 тыс. (а) и 80 тыс. (б) эпох эволюции, оцененные по сериям прогонов ДГА и ДГАС при разных размерах популяции, а также отмечены уровни значений ЦФ, соответ- ствующие успешному решению задачи. Как видно, во всех случаях ДГАС справляется с поиском оптимального реше- ния не хуже ДГА и превосходит его при более жестких условиях эволюционного моделирования. Для критически малых популяций (до 25–50 особей) в результате прогона ДГА и ДГАС получаются близкие значения ЦФ. С увеличением размера популяции ДГАС начинает превосходить ДГА по эффективности, и это преимуще- ство сохраняется для популяций размером до 100 особей. С дальнейшим увеличе- нием числа особей эффективность ДГА и ДГАС становится одинаковой. 148 ISSN 0572-2691 0 0,002 0,004 0,006 0,008 0,01 0,012 0 25 50 75 100 125 150 Размер популяции Favg 0 0,002 0,004 0,006 0,008 0,01 0,012 0 25 50 75 100 125 150 Размер популяции Favg 0 0,001 0,002 0,003 0,004 0,005 0,006 0,007 0 25 50 75 100 125 150 Размер популяции F min 0 0,001 0,002 0,003 0,004 0,005 0,006 0,007 0 25 50 75 100 125 150 Размер популяции Fmin 0 0,005 0,01 0,015 0,02 0,025 0 25 50 75 100 125 150 Размер популяции Fmax 0 0,005 0,01 0,015 0,02 0,025 0 25 50 75 100 125 150 Размер популяции Fmax а б Рис. 4 Примечание 2: — для ДГА; для ДГАС. На рис. 4, а представлены результаты первого этапа тестирования — прого- нов, ограниченных 40 тыс. эпох эволюции. Как видно, преимущество ДГАС про- является при размерах популяции свыше 50 особей, и при размере популяции в 75 особей ДГАС выходит на уровни Favg , Fmin и Fmax , соответствующие успешному решению задачи. ДГА для этого требуется 100 особей, а так как в каждом прогоне количество эпох постоянно, то меньший размер популяции соответствует про- порционально меньшему количеству вычислений ЦФ и времени поиска решения. Результаты второго этапа тестирования — прогонов, ограниченных 80 тыс. эпох эволюции, представлены на рис. 4, б. В этом случае преимущество ДГАС Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 149 начинает проявляться уже при размерах популяции более 25 особей. Можно оце- нить, что на уровни Favg , Fmin и Fmax , соответствующие успешному решению за- дачи, ДГАС выходит при размере популяции в 65 особей, а ДГА для этого требу- ется около 85 особей. При этом по величине Fmin ДГАС выходит на требуемый уровень, начиная с размера популяции в 25 особей, а ДГА — 75 особей. Таким образом, введение механизма смертности позволяет на 25 % сократить размер популяции и количество вычислений ЦФ, требуемые для гарантированно успешного решения рассматриваемого типа задач. Для практического использования ДГАС можно рекомендовать размеры популяции в диапазоне от 50 до 125 особей. Заключение Предложенный в данной работе метод усовершенствования ГА путем введе- ния механизма смертности и ограничения продолжительности жизни особей ба- зируется на методах математической теории популяционной генетики, демогра- фии и актуарной науки. Однако очевидно, что он, по сути, является эмпирическим и не может претендовать на строгую доказуемость. Тем не менее приведенные результаты тестирования и накопленный опыт прикладных исследований показы- вают, что использование ДГАС повышает надежность решения за ограниченное время поиска задач синтеза нейросетевых моделей и регуляторов, имеющих 10 2 –10 3 настроечных параметров. В частности, ДГАС позволяет успешно решать задачу моделирования и управления температурой теплоносителя на ТЭЦ [15, 16]. К.В. Махотіло ДИПЛОЇДНИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ЗІ СМЕРТНІСТЮ Запропоновано метод удосконалення диплоїдного генетичного алгоритму оп- тимізації шляхом ймовірнісного обмеження тривалості життя особин. Середня тривалість життя особин визначається залежно від розміру популяції, виходячи з оцінки вартості заміщення Холдейна. Закон і параметри розподілу ймовірнос- ті смерті особини визначені за даними демографічної статистики. Показано ефективність методу при розв’язанні задач синтезу прямоспрямованих нейрон- них мереж. K.V. Makhotilo DIPLOID GENETIC ALGORITHM WITH MORTALITY The method of improvement of diploid genetic algorithm via probabilistic limitation of individual’s lifespan is offered. Mean lifespan of individual is determined depend- ing on the population size based on Haldane’s substitution cost estimation. The indi- vidual death probability distribution law and parameters are determined based on demographic statistics data. It is shown the efficiency of proposed method for syn- thesis of feedforward neural networks. 1. De Jong K. Genetic algorithms: a 30 year perspective // Perspectives on Adaptation in Natural and Artificial Systems; ed. by L. Booker, M. Mitchell Forrest, R. Riolo. — Oxford : Oxford Uni- versity Press, 2005. — P. 11–31. 2. Miller G.F., Todd P.M., Hegde U. Designing neural networks using genetic algorithms // Proc. 3rd Int. Conf. Genetic Algorithms and Their Applications; ed. by J.D. Schaffer. — San Mateo, CA : Morgan Kaufmann, 1989. — P. 379–384. 150 ISSN 0572-2691 3. Whitley D., Starkweather T., Bogart C. Genetic algorithms and neural networks: Optimizing con- nections and connectivity // Parallel Comput. — 1990. —14, N 3. — P. 347–361. 4. Fogel D.B., Fogel L.J., Porto V.W. Evolving neural networks // Biological Cybernetics. —1990. — 63, N 6. — P. 487–493. 5. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. — Харьков : Основа, 1997. — 112 с. 6. Zadeh L. What is soft computing? // Soft Comput. —1997. — N 1. — P. 1–2. 7. Klepikov V.B., Mahotilo K.V., Sergeev S.A. Modification of Holland’s reproductive plan for dip- loid populations // Proc. Int. Conf. Artificial Neural Nets and Genetic Algorithms; D.W. Pearson, N.C. Steele, R.F. Albrecht, Eds.; Ales, France : Springer-Verlag, 1995. — P. 337–339. 8. Klepikov V.B., Mahotilo K.V., Sergeev S.A., Voronovsky G.K. Neural technologies in electrical drive control // Proc. Int. Conf. Sterowanie w Energoelektronice i Napedzie Elektrycznym, Lodz– Arturowek, 15–17 listopada 1995. — P. 336–343. 9. Mahotilo K.V., Sergeev S.A. Evolutionary synthesis of dynamical object emulator based on RBF neural network // Proc. First Online Workshop on Soft Comput. WSC1; T. Furuhashi, Ed.; Nago- ya University, 1996. — P. 31–36. 10. Sergeev S.A., Makhotilo K.V., Voronovsky G.K., Petrashev S.N. Genetic algorithm for training dynamical object emulator based on RBF neural network // Intern. Journ. of Appl. Electromagne- tics and Mechanics. —1998. — 9. — P. 65–74. 11. Махотило К.В. Разработка методик эволюционного синтеза нейросетевых компонентов си- стем управления : Дисс. … канд. техн. наук: 05.13.06. — Харьков, 1998. —189 с. 12. Руденко О.Г., Бодянський Є.В. Штучні нейронні мережі. — Харків : ТОВ «Компанія СМІТ», 2006. — 402 с. 13. Клепиков В.Б., Махотило К.В., Сергеев С.А., Обруч И.В. Применение методов нейронных сетей и генетических алгоритмов в решении задач управления электроприводами // Элек- тротехника. —1999. — № 5. — С. 2–6. 14. Вороновский Г.К., Махотило К.В., Сергеев С.А. Опыт синтеза и использования математиче- ских моделей потребления электрической энергии в быту // Технічна електродинаміка. – 2004. — Темат. вип. Проблеми сучасної електротехніки. — С. 33–41. 15. Махотило К.В. Повышение точности моделирования среднечасовой температуры обратно- го теплоносителя ТЭЦ // Зб. наук. праць Ін-ту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — 2009. — № 53. — С. 118–128. 16. Вороновский Г.К., Махотило К.В., Сергеев С.А. Энергоэкономичное управление состояни- ем теплосети в крупных системах централизованного теплоснабжения // Технічна електро- динаміка. — Темат. вип. Проблеми сучасної електротехніки. Ч. 1. — 2006. — С. 129–135. 17. Arabas J, Michalewicz Z., Mulawka J. GAVaPS — a genetic algorithm with varying population size // Proc. First IEEE Conf. on Evolutionary Comput. — IEEE Press, 1994. — P. 73–78. 18. Eiben A.E., Marchiori E., Valko V.A. Evolutionary algorithms with on-the-fly population size ad- justment // Proc. Parallel Problem Solving from Nature – PPSN VIII, 8th Intern. Conf., Birming- ham, UK, September 18–22, 2004. — P. 41–50. 19. Feyzbakhsh S. Alireza, Matsui M. Adam-Eve genetic algorithm as a function optimizer // Proc. IEEE Intern. Conf. on Systems, Man and Cybernetics (SMC’99), 1999. — 1. — P. 613–624. 20. Haldane J.B.S. The cost of natural selection // Journ. of Genetics. — 1957. — N 55. — P. 511–524. 21. Nunney L. The cost of natural selection revisited // Annales Zoologici Fennici. —2003. — N 40. — P. 185–194. 22. Потапенко А.И. Предопределенность продолжительности жизни // Тр. научн. сессий МИФИ. Научн. сессия МИФИ-2002. Всерос. конф. «Радиационная безопасность человека и окружающей среды». — М. : МИФИ, 2002. — С. 116–124. 23. Гаврилов Л.А. Гаврилова Н.С. Биология продолжительности жизни. — М. : Наука, 1991. — 280 c. Получено 17.11.2010

Диплоидный генетический алгоритм со смертностью

Репозитарії

Схожі ресурси