Исследование эффективности гибридного самонастраивающегося эволюционного алгоритма оптимизации

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы технических и прикладных наук и отраслей народного хозяйства


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Секция «Математические методы моделирования, управления и анализа данных»
ESR = j P (r)dr
(3)
Здесь, а — левая граница оценки плотности распределения Р (г).
Для сравнения трех методов проведем эксперимент, в котором с помощью модели вАЯСН [5] сгенерируем выборку независимых измерений скалярной величины т{. Значение 7 = 1, объем выборки «= 250.
В параметрическом методе структура закона распределения — нормальная. Результаты эксперимента приведены на рис. 2.
При истинном значении Е8К = 0. 48 при 7 = 1, значения оценок на последнем шаге ЫК = 0. 477, ЬРМ = 0. 484 и РК = 0. 508. Большая погрешность, при сравнении с другими методами, при параметрическом подходе объясняется неправильным выбором структуры.
Рис. 4. Результаты работы трех методов
Библиографические ссылки
1. Crouhy M., Galai D., Mark R. Risk Management. McGraw-Hill. Р. 752. 2001.
2. Chen S. X Nonparametric Estimation of Expected Shortfall // Journal of Financial Econometrics, 6. Р. 87 107. 2008.
3. Rosenblatt M. Remarks on some nonparametric estimates of a density function // Ann. Math. Statist. 1956. V. 27. № 3. P. 832−835.
4. Parzen E. On Estimation of a Probability Density, Function and Mode // IEEE Transactions on Information Theory. Vol. Pami-4. № 6. 1982. P. 663−666.
5. Engle Robert F. 2001. GARCH 101: The Use of ARCH/GARCH Models in Applied Econometrics // Journal of Economic Perspectives. 15(4). Р. 157−168.
© Стрельников А. В., 2012
Рис. 3. Оценка дефицитных рисков
УДК 519. 68
А. В. Фисак Научный руководитель — Е. С. Семёнкин Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ГИБРИДНОГО САМОНАСТРАИВАЮЩЕГОСЯ ЭВОЛЮЦИОННОГО АЛГОРИТМА ОПТИМИЗАЦИИ
Исследовалась эффективность гибридного самонастраивающегося эволюционного алгоритма на тестовых задачах безусловной и условной оптимизации. Было проведено сравнение рассматриваемого алгоритма с другими процедурами оптимизации.
Генетические алгоритмы применимы для широкого круга задач. Однако чтобы добиться высокой надежности при сравнительно небольших вычислительных ресурсах, необходимо тщательно настраивать алгоритм. Выбор оптимальных настроек трудоемкий и времязатратный процесс, причем алгоритм необходимо настраивать отдельно для каждой задачи. В связи с этим возникает потребность в разработке самонастраивающегося генетического алгоритма. В рамках решения этой проблемы была разработана программная система, в которой на основе стандартного генетического алгоритма [1] был реализован гибридный самонастраивающийся эволюционный алгоритм.
Остановимся подробнее на самом гибридном алгоритме. Он базируется на гибридном самонастраивающемся эволюционном алгоритме Гомеса [2]. Этот алгоритм представляет собой гибридизацию генетического алгоритма и эволюционных стратегий, так как внутри хромосомы записываются действительными числами вероятности применения операторов. При этом вероятности выбора операторов для каждого индивида адаптируются отдельно. В алгоритме Гоме-са автоматизируется выбор типа всего одного генетического оператора. А так как это существенно не улучшает ситуацию с настройкой алгоритма, то была предложена модификация данной процедуры. Моди-
Актуальные проблемы авиации и космонавтики. Информационные технологии
фицированный алгоритм в процессе работы сам выбирает применяемые типы трех операторов, а именно селекции, скрещивания и мутации.
Рассмотрим схему реализованного гибридного самонастраивающегося эволюционного алгоритма. Он начинается с инициализации популяции. Также одновременно с инициализацией нужно задать начальные значения вероятностей выбора операторов для каждого индивида. Так как нет какой-либо априорной информации о том, какой оператор предпочтительнее, то начальные значения вероятностей будут равны между собой. Эти числа записываются в хромосому и не нулями и единицами, как решение задачи, а вещественными числами. Далее начинается первая итерация алгоритма: берем первого индивида и в соответствии с эмпирическими вероятностями, закодированными в нем, случайным образом выбираем операторы, которые будут к нему применены. Непосредственно применяем выбранные операторы, получаем потомков, случайно выбираем одного из них. Сравниваем его пригодность с пригодностью индивида, которого мы рассматриваем на текущем шаге, если она больше, то перемещаем найденного потомка в следующее поколение, если меньше, то перемещаем исходного индивида. После этого пересчитываем вероятности выбора операторов следующим образом: если потомок имеет большую пригодность по сравнению с исходным индивидом, то увеличиваем вероятности выбора использованных на данном шаге операторов селекции, скрещивания и мутации, если потомок имеет меньшую пригодность, то уменьшаем соответствующие вероятности. Затем перезаписываем полученные числа в индивида, которого переместили в следующее поколение и переходим к очередному индивиду. После того, как все хромосомы в популяции прошли развитие, заканчивается первая итерации алгоритма и начинается новая. Так продолжается до тех пор, пока не будут пройдено заданное пользователем число поколений.
Для проверки эффективности рассматриваемой схемы самонастройки, сравним разработанный гибридный алгоритм со стандартным генетическим алгоритмом на наборе из десяти тестовых функций безусловной оптимизации и десяти тестовых задачах условной оптимизации. В качестве критериев эффективно-
сти были выбраны — надежность алгоритма (процент удачных запусков, в ходе которых решение найдено с необходимой точностью) и среднее число поколений до первого обнаружения искомого решения.
Установлено, что гибридный алгоритм имеет надежность значительно больше, чем средний по эффективности генетический алгоритм, и почти на всех задачах имеет надежность, такую же или больше, чем генетический алгоритм с лучшими настройками. Также полученные результаты показали, что по скорости рассматриваемая модификация, если и проигрывает стандартному алгоритму, то немного.
Кроме этого, было проведено сравнение гибридного алгоритма с другими оптимизационными процедурами по методикам, предложенным на сайтах: http: //coco. lri. fr/COCOdoc/bbo_experiment. html и
http: //www. ntu. edu. sg/home/EPNSugan/ index_files/CEC-06/CEC06. htm. Сравнительный анализ подтвердил конкурентоспособность разработанного метода оптимизации относительно других алгоритмов, предложенных на вышеупомянутых сайтах.
В заключение можно добавить, во-первых, что проведенные исследования показали целесообразность использования гибридного алгоритма вместо обычного генетического, так как он не требует выбора ряда параметров и имеет показатели эффективности не хуже, чем генетический алгоритм с лучшими настройками. Во-вторых, алгоритм показал свою высокую эффективность на задачах как безусловной, так и условной оптимизации.
Библиографические ссылки
1. Сергиенко А. Б., Галушин П. В., Бухтояров В. В., Сергиенко Р. Б., Сопов Е. А., Сопов
С. А. Генетический алгоритм. Стандарт. Красноярск, 2010 [Электронный ресурс]. URL: http: //www. harrix. org/files/61/Geneticheskii_algoritm_St andart_Part_I_v1_8_Release_Candidate. pdf.
2. Gomez J. Self adaptation of operator rates in evolutionary algorithms // Proc. of Genetic and
Evolutionary Computation Conference 2004 (GECCO 2004). LNCS No. 3102, 2004. P. 1162−1173.
© Фисак А. В., 2012
УДК 519. 87
Д. И. Хритоненко Научный руководитель — Е. С. Семенкин Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск
ПРИМЕНЕНИЕ САМОНАСТРАИВАЮЩЕГОСЯ АЛГОРИТМА ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ КЛАССИФИКАЦИИ
Рассматривается самонастройка алгоритма генетического программирования при решении задач восстановления символьной регрессии и классификации. Разработанный алгоритм протестирован на ряде задач и сравнивается с базовым. На задачах классификации данный алгоритм сравнивается по эффективности со сходными ему алгоритмами.
При решении задач с помощью алгоритмов генетического программирования (ГП) [1] возникает проблема выбора их параметров. Для каждой решаемой
задачи существует свой, оптимальный в некотором смысле, набор параметров, который в свою очередь может изменяться во время работы алгоритма. Разу-

ПоказатьСвернуть
Заполнить форму текущей работой