Самоконфигурируемый алгоритм генетического программирования

Секция «Математические методы моделирования, управления и анализа данных»

спектрометра с применением нелинейного зеркала над традиционным масс-рефлектроном.

а)

Зависимость разрешающей способности от массы для схемы: а - с линейным электростатическим зеркалом; б - с нелинейным электростатическим зеркалом

Также следует отметить, что выигрыш в разрешении увеличивается с ростом начального энергетического разброса ионов и позволяет разрешать массы до нескольких тысяч, сохраняя при этом высокую разрешающую способность (Я > 100) в диапазоне масс до 150 а.е.м. даже для температур порядка 1000 К, тогда как масс-спектрометр с применением линейного

зеркала при том же температурном разбросе имеет разрешение ЯМ 00 только в диапазоне масс до 25 а.е.м. С увеличением ускоряющего потенциала происходит повышение разрешающей способности приборов, поскольку уменьшается время, требуемое для разворота траекторий ионов, движущихся в начальный момент времени в направлении, противоположном направлению ускорения ионов. Также с ростом ускоряющего напряжения уменьшается выигрыш в разрешении, получаемом при применении нелинейного зеркала, однако превосходство прибора с нелинейным электростатическим зеркалом сохраняется.

Разработанный метод аналитического расчета распределения нелинейного потенциала электростатического ионного зеркала позволяет существенно расширить диапазон разрешаемых масс, расширить диапазон допустимых начальных энергий ионов вплоть до 100 %, а также повысить точность расчета распределения потенциала. Данный метод также позволяет упростить и ускорить процесс вычислений, поскольку исключает необходимость рассчитывать большое количество точек (как при использовании численных путей расчета), позволяет рассчитывать потенциалы колец нелинейного зеркала непосредственно по их координатам, а также обладает большей точностью, а следовательно, повышает разрешающую способность прибора.

Библиографические ссылки

1. Картаев В. И., Мамырин Б. А., Шмикк Д. В. Новый принцип фокусировки ионных пакетов во времяпро-летныхмасс-спектрометрах//ЖТФ. 1971. Т. 41. Вып. 7.

2. Картаев В. И., Мамырин Б. А., Шмикк Д. В. Новый безмагнитный времяпролетный масс-спектрометр с высокой разрешающей способностью //ЖТФ. 1973. Т. 64. Вып. 1.

3. Шмикк Д. В., Дубенский Б. Н. Отражатель масс-рефлектрона //ЖТФ. 1984. Т. 54. Вып. 5.

© Родин Д. В., 2012

УДК 519.8

М. Е. Семенкина Научный руководитель - Л. В. Липинский Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

САМОКОНФИГУРИРУЕМЫЙ АЛГОРИТМ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Приводится описание реализации самоконфигурируемого алгоритма генетического программирования, а также исследование его эффективности на тестовых и реальных практических задачах.

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

обычно называемые самоадаптивными, устраняющие процесс выбора настроек за счет их адаптации в ходе работы алгоритма.

Основная идея предложенных в данной статье алгоритмов относится к автоматизации выбора и использования генетических операторов, в связи с чем данные алгоритмы могут быть названы самоконфигу-

Актуальные проблемы авиации и космонавтики. Информационные технологии

рируемыми [1]. Предложенный алгоритм самоконфигурируемого генетического программирования (8СвР) использует динамическую адаптацию на уровне популяции [2] в ходе решения задачи и централизованную форму управления процессом настройки параметров. Вероятности для операторов быть выбранными для порождения очередного потомка адаптируются, исходя из успешности этих операторов на последнем поколении независимо от предыдущих результатов работы. Таким образом снимается типичная для централизованных подходов проблема больших затрат памяти [3]. Вероятности применения операторов не включены в хромосому и не являются объектом эволюции. Все операторы могут быть использованы в течение одного поколения для создания потомков.

Было проведено тестирование 8СвР на 17 тестовых задачах и сравнение эффективности с альтернативными подходами на практических задачах. По результатам решения этих задач 8СвР уступил одному алгоритму, специально разработанному для решения задач этого типа. 8СвР может быть рекомендован для решения задач символьной регрессии как лучшая аль-

тернатива стандартному алгоритму генетического программирования.

В результате проделанной работы можно сделать вывод о том, что SCGP, предложенный в данной статье, позволяет избегать затрат интеллектуальных и вычислительных ресурсов на настройку алгоритма без снижения эффективности.

Библиографические ссылки

1. Schaefer R., Cotta C., Koiodziej J., Rudolph G. (Eds.) Parallel Problem Solving from Nature - PPSN XI 11th International Conference, Krakow, Poland, September, 11-15. 2010.

2. Meyer-Nieberg S., Beyer H.-G. Self-Adaptation in Evolutionary Algorithms. In F. Lobo, C. Lima, and Z. Michalewicz (Eds.) Parameter Setting in Evolutionary Algorithm. Р. 47-75. 2007.

3. Gomez J. SelfAdaptation of Operator Rates in Evolutionary Algorithms. In Deb K. et al. (Eds.) GECCO 2004, LNCS 3102. Р. 1162-1173. 2004.

© Семенкина М. Е., 2012

УДК 519.68

О. Е. Семенкина Научный руководитель - Е. С. Семенкин Сибирский федеральный университет, Красноярск

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНОГО МУРАВЬИНОГО АЛГОРИТМА НА ЗАДАЧЕ КОММИВОЯЖЕРА

Проведено исследование эффективности и скорости работы параллельного муравьиного алгоритма на задаче отыскания кратчайшего маршрута.

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

Для реализации и исследования эффективности муравьиного алгоритма была использована оптимизационная задача, которая часто возникает на практике, а именно задача коммивояжера [1]. Формулировка задачи: Пусть имеется заданное множество из п городов. Требуется найти замкнутый обход минимальной длины с условием, что каждый город должен быть посещен единственный раз.

Муравьиный алгоритм основан на имитации поведения муравьев в природе [2]. Почти слепые животные, такие как муравьи, справляются с задачей отыскания кратчайшего пути от гнезда до источника пищи и обратно. Для обмена информацией они используют след фермента, оставляемый на пути. Муравей с большей вероятностью выбирает тот путь, на котором большее количество фермента.

Пусть Ту(1) это интенсивность следа на ребре (1, в момент времени 1. Интенсивность следа обновляется в соответствии с формулой тц^ + п) = р-т^) + Дт^, где р является коэффициентом таким, что (1-р) представляет собой испарение следа.

ДТу =

Z4

где Дт ij =

Q

—, если к-й муравей использует ребро (у) в своем обходе ^к

0, если не использует .

Р является постоянной, а Ьк - длина обхода к-го муравья. Пусть число "Лу, равное Ш^, называется видимостью, где ^ - длина пути между городами 1 и Вероятность перехода из города 1 в город} для к-го муравья выражается следующим образом

pk =

Ь (t) ]вЬ ]р

(t УТЬ,* Г

если k-й муравей еще

не посещал j-й город,

0

если к-й муравей

уже посещал ]-й город.

Здесь а и р являются параметрами, которые управляют относительной важностью следа и видимости.

Алгоритм показывает свою работоспособность и хорошую надежность при достаточном количестве ресурсов. Но необходимое количество ресурсов, а,

к=1

к