Другие журналы

электронный научно-технический журнал

ИНЖЕНЕРНЫЙ ВЕСТНИК

Издатель: Общероссийская общественная организация "Академия инженерных наук им. А.М. Прохорова".

77-48211/451141 Эволюция «по-спартански»

Инженерный вестник # 08, август 2012
Файл статьи: 1Мясников_P.pdf (416.71Кб)
автор: Мясников А. С.

УДК 621.514

Россия, научно-исследовательский центр эксплуатации и ремонта авиационной техники 4 ЦНИИ Минобороны России

AlekseyMyasnikov@yandex.ru

 

Введение

В процессе работы над островным генетическим алгоритмом с динамической самоорганизацией параметров [1] автором были получены неожиданные результаты, которые помогают лучше понять законы искусственного и естественного отбора для объяснения явлений природы, а также исключения ошибок при проектировании генетических алгоритмов.

Одним из перспективных направлений развития генетических алгоритмов (ГА) является разработка новых и совершенствование известных генетических операторов, выяснения рациональной границы их применения в работе генетического алгоритма [2]. Отталкиваясь от исторического опыта древней Спарты [3], решено было использовать отдельные новаторские подходы спартанцев для улучшения своей «породы». Так, древнегреческий философ и биограф Плутарх из Херонеи в своём «Жизнеописании Ликурга» упомянул, что «Воспитание ребенка не зависело от воли отца, — он приносил его в лесху, место, где сидели старшие члены филы, которые осматривали ребенка. Если он оказывался крепким и здоровым, его отдавали кормить отцу, выделив ему при этом один из девяти земельных участков, но слабых и уродливых детей кидали в апотеты, пропасть возле Тайгета.» [4]. Почему спартанцы делали это, исторические книги не раскрывают, но существуют 2 основных версии: генетическая (попытка улучшения породы) и социальная (снять нагрузку с общества в воспитании, сохранении жизни слабых жителей Спарты). Современные ученые в принципе опровергают тезис о сбрасывании слабых детей спартанцев в пропасть [5]. Так или иначе, идею искусственного отбора «по-спартански» решено было исследовать путем моделирования эволюции в генетическом алгоритме. Идея простая, хотя циничная, жестокая и пугающая для цивилизованного человека.

  Цель исследования – оценить возможность применения искусственного отбора «по-спартански» в генетических алгоритмах для повышения эффективности их использования.

Моделирование эволюции «по-спартански»

Генетический алгоритм в общем случае состоит из следующей последовательности действий (рисунок 1).

1.    Генерирование начальной популяции родительских хромосом.

2.    Отбор хромосом в родительский пул для дальнейшего скрещивания и/или мутации.

3.    Скрещивание (одно-, двух-, многоточечное) случайно отобранных или отобранных по какому либо правилу (лучшая хромосома со всеми, лучшие с лучшими и др.) пар родительских хромосом.

 

 

Рисунок 1 - Схема работы генетического алгоритма

4.    Мутация (одно-, двух-, многоточечная, полная инверсия хромосомы). Мутация может быть опущена в некоторых итерациях (циклах эволюции) генетического алгоритма.

5.    Оценка пригодности потомков по заданному правилу (случайно, лучше средней приспособленности в родительской популяции, лучше лучшей приспособленности в родительской популяции и др.)

6.    Замещение в начальной популяции отобранных по заданному правилу (например, с наихудшей приспособленностью) родительских хромосом на отобранных потомков.

Проверка признаков окончания эволюции (по максимальному времени эволюции, по максимальному количеству поколений потомков, по максимальному времени неулучшения приспособленности в популяции и др.). Если не найден ни один из признаков окончания эволюции, то повторяются этапы 2…6.

Чтобы реализовать эволюцию «по-спартански», требуется внести некоторые коррективы в описанную выше последовательность действий. Итак, формально эволюция «по-спартански» представляется совокупностью следующих постулатов.

1.    Формирование начальной популяции производится случайным образом. Формально можно считать, что до какого-то момента в истории Древней Спарты старшие члены филы не занимались оценкой и отбором детей, поэтому спартанцы рождались естественным образом.

2.    Формирование родительского пула будем производить с помощью оператора 60-процентного элитарного отбора. Этот оператор формально описывает сложные условия выживания спартанцев (войны, болезни и т.п.).

3.    Отбор родительских пар хромосом для скрещивания осуществляется случайным образом. Здесь следует понимать, что в генетических алгоритмах понятие пола отсутствует, поэтому скрещиваться могут любые хромосомы с любыми. Историки не упоминают никаких особых традиций (правил, канонов) при создании брака, что оправдывает случайный отбор родителей. «Право выбора невесты оставалось за женихом (любой спартиат был обязан жениться до 30 лет). По древнему обычаю юноша похищал будущую жену и прятал ее у подруги» [6].

4.    Мутация маловероятна (ведь в древней Спарте не было негативных факторов, провоцирующих мутации – Чернобыльских АЭС, радиоизлучений, ГМО и т.п.), поэтому в работе генетического алгоритма используется для создания не более чем в 1 % потомков.

5.    Краеугольным камнем в эволюции «по-спартански» является оценка пригодности потомков. Поэтому при селекции используется следующее правило: отбираются только те потомки, приспособленность которых не хуже, чем средняя приспособленность в родительской популяции. В летописях Древней Спарты не упоминается о том, дети какого пола подвергались искусственному отбору (через сбрасывание слабых и уродливых детей в апотеты). Поэтому будем считать, что отбор из всех потомков только потомков с приспособленностью, превышающей среднюю приспособленность в родительской популяции, соответствует искусственному отбору «по-спартански».

6.    При замещении худших (по приспособленности) хромосом в родительской популяции отобранными потомками следует понимать, что часть родителей переходят в следующее поколение, т.е. формально генетический алгоритм содержит «условно-бессмертные» хромосомы, чего в обычной жизни не происходит – бессмертных людей не бывает.

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

Тестирование генетического алгоритма

Остановимся на функции приспособленности (здоровья, фитнеса) хромосом. В генетических алгоритмах эта функция определяет степень приспособленности хромосомы к окружающей среде. На деле функция приспособленности представляет собой целевую функцию от определенного набора аргументов. Целевой функцией (ЦФ) в математике обычно называют функцию, для которой нужно найти такой набор её аргументов, при котором функция принимает наибольшее или наименьшее значение. Например, найти самый быстрый путь от одной станции метро до другой (ЦФ – время в пути), или путь с наименьшим количеством пересадок (ЦФ – количество пересадок). Еще пример – найти самого богатого жениха (ЦФ – размер состояния жениха). Набор аргументов ЦФ в ГА кодируется в хромосому. Для сгенерированных, а также полученных в процессе мутации или скрещивания хромосом производится обратный процесс – декодирование – превращение хромосомы в набор аргументов ЦФ. Для декодированного набора аргументов вычисление значения ЦФ становится тривиальной задачей.

Полагая, что в реальной жизни Древней Спарты одни спартанцы оказывались более приспособленными (чтобы оставить потомство), чем другие благодаря различным навыкам (сила, выносливость, ловкость, хитрость, смекалка, внешняя привлекательность для девушек), функция приспособленности оказывается крайне сложной. Очевидно, что единственный достоверный способ узнать к чему приведет эволюция «по-спартански» – это смоделировать её на популяции реальных людей во временном периоде от 200 до 500 лет. Естественно, что такой эксперимент дорогой, жестокий и крайне длительный – одним словом, неосуществимый. Поэтому будем использовать искусственные функции приспособленности.

Обычно для тестирования любых алгоритмов оптимизации (в т.ч. ГА) используют тестовые целевые функции (Растригина, De Jong, Griewank, Gaussian quartic, и др.) [1]. Поверхность двухпараметрических функций Растригина и De Jong смотрите на рисунках 2 и 3. Как видно из рисунков, эти функции достаточно сложны (для нахождения их максимума), чтобы считать их столь же сложными, как и приспособленность спартанцев к жизни в Древней Спарте. Именно функции Растригина и De Jong использовались для анализа эволюции «по-спартански».

 

 

Рисунок 2 ‑ График двухпараметрической функции Растригина

 

Рисунок 3 ‑ График двухпараметрической функции De Jong

Анализ результатов моделирования эволюции «по-спартански»

На графиках рисунков 4 и 5 показано, как происходила эволюция при поиске максимума двухпараметрических функций Растригина и De Jong по мере рождения новых потомков.

Рисунок 4 ‑ График изменения приспособленности хромосом при эволюции
«по-спартански» на функции Растригина (абсолютный максимум 0,000)

 

Рисунок 5 ‑ График изменения приспособленности хромосом при эволюции
«по-спартански» на функции De Jong (абсолютный максимум 1,004)

 

Сразу бросается в глаза то, что эволюция «по-спартански» в отличие от альтернативных генетических алгоритмов [1] остановилась до того, как был найден максимум этих функций. Очевидно, что текущая популяция как в случае функции Растригина, так и функции De Jong сформировалась на одном из локальных максимумов (рисунки 2 и 3) и выход за пределы этих максимумов оказался невозможен только с помощью оператора скрещивания. Для продолжения эволюции требуется «свежая кровь». Эту функцию выполнил оператор мутации, который применяется (как мы условились ранее) с малой вероятностью. Скачки на графике рисунка 5 обусловлены именно применением оператора мутации. То есть при продолжении спартанского отбора Древняя Спарта не смогла бы получить более приспособленных потомков, иными словами –  привела бы к  тупику эволюции. В классических генетических алгоритмах отбор потомков менее жесткий, что позволяет «смешивать кровь» сильных и приспособленных спартанцев со слабыми особями. Это позволяет сдвинуть популяцию, «застрявшую» в локальном минимуме в сторону. Продемонстрируем это на примере функции Растригина (рисунок 2). Допустим, текущая популяция располагается на одном из правых локальных максимумов. Скрещивание хромосомы из этой популяции с одной из менее приспособленных хромосом из диаметрально-противоположной стороны графика функции Растригина позволяет получить потомка, находящегося на центральном глобальном максимуме. Парадокс: чтобы получить более сильного потомка иногда требуется скрестить сильную особь с мене слабой сильно отличающейся от сильного потомка особью.

Заключение

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

Список цитированных источников

1.                    Мясников А.С. Островной генетический алгоритм с динамическим распределением вероятностей выбора генетических операторов. URL: http://technomag.edu.ru/doc/136503.html (Дата обращения 27.05.2012г.).

2.                    Курейчик В.М. Генетические алгоритмы и их применение. Таганрогский РТУ, 2002 г. 244 с.

3.                    Дубровский И. Спартанский эксперимент // Вокруг света. — 2006. — № 1 (2784).

4.                    Плутарх. Сравнительные жизнеописания. Ликург и Нума Помпилий. М.:Правда, 1987г. Перевод  В.Алексеева.

5.                    Археологи доказали: спартанцы не сбрасывали детей со скалы. URL: http://www.newsru.com/world/11dec2007/spartans.html (Дата обращения 27.05.2012г.).

6.                    Волков А.В. Спарта. Со щитом и на щите. - М.: Вече, 2005. - 352 с. (Таинственные места Земли).


Тематические рубрики:
Поделиться:
 
ПОИСК
 
elibrary crossref neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (499) 263-69-71
  RSS
© 2003-2024 «Инженерный вестник» Тел.: +7 (499) 263-69-71