Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С




Скачать 42.34 Kb.
НазваниеСамоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С
Дата публикации21.12.2013
Размер42.34 Kb.
ТипДокументы
5-bal.ru > География > Документы
УДК 519.87

САМОАДАПТАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИ РЕШЕНИИ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

Брестер К. Ю.

научный руководитель д-р техн. наук Семенкин Е. С.

Сибирский государственный аэрокосмический университет

им. М. Ф. Решетнева

При решении оптимизационных задач, для которых классические методы являются неприменимыми, предпочтение отдается эволюционным, а именно генетическим, алгоритмам (ГА).

Для решения задач многокритериальной оптимизации применяется метод SPEA (Zitzler, Thiele), основанный на идее Парето-доминирования. Результатом его работы является множество точек – аппроксимация паретовского множества. Приведем схему метода:

  1. Инициализировать начальную популяцию .

  2. Скопировать в промежуточное внешнее множество индивидов, чьи векторы решений недоминируемы относительно .

  3. Удалить из промежуточного внешнего множества () индивидов, доминируемых относительно .

  4. Если мощность больше заданного значения, то применить механизм кластеризации.

  5. Сформировать внешнее множество из индивидов .

  6. Применить генетические операторы: селекция, скрещивание, мутация.

  7. Проверить выполнение критерия останова: если выполняется – завершить работу алгоритма, иначе – перейти к п. 2.

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

Известно, что результат работы ГА зависит от выбора вариантов генетических операторов, поэтому целесообразно применение механизмов самоадаптации к стандартному методу SPEA для обеспечения гарантированного уровня эффективности работы алгоритма.

В статье Дариди предложен следующий вариант адаптивной мутации:

(1)

где – номер текущего поколения, для которого рассчитывается вероятность мутации.

Идеи коэволюционного ГА были применены для реализации адаптивного оператора скрещивания. На каждом поколении генерирование новой популяции осуществляется всеми типами скрещивания: вариантам оператора выделяются ресурсы (доля индивидов популяции, генерируемых конкретным типом скрещивания на текущем поколении) в зависимости от числа индивидов во внешнем множестве, сгенерированных при помощи данного варианта скрещивания:

(2)

где – число индивидов во внешнем множестве, сгенерированных -ым типом оператора скрещивания, – мощность внешнего множества, – число индивидов в текущей популяции, сгенерированных -ым типом оператора, – мощность популяции.

Для каждого варианта оператора скрещивания вычисляется «пригодность» по формуле:

(3)

где – интервал адаптации, соответствует последнему поколению в интервале адаптации, – предыдущему и т.д.

Через каждые поколений осуществляется попарное сравнение «пригодности» вариантов скрещивания с целью перераспределения ресурсов:

(4)

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

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

Результат работы алгоритма оценивался метрикой IGD:

, (5)

где – фронт Парето, A – аппроксимация фронта Парето (результат работы алгоритма), v – точка фронта Парето, - минимальное расстояние между точкой и множеством А, вычисленное по евклидовой метрике.

Тестирование проводилось для различных комбинаций типов операторов, результат усреднялся по тридцати прогонам. При выделенном количестве ресурсов (число вычислений функции не более 300 тыс.) доля просматриваемого поискового пространства не превышала . Значения параметров: , , . В таблице 1 приведены полученные результаты:

Таблица 1 – Результаты тестирования адаптивного ГА

Номер тестовой задачи

Значение метрики IGD

Число поражений «стандартному» SPEA

1

0,10579

2

2

0,04160

3

3

0,0049

1

4

0,04493

2

5

0,34105

2

6

0,0088

2

7

0,11738

1


Анализ полученных результатов показал, что эффективность реализованного адаптивного метода SPEA соответствует уровню выше «среднего» ГА многокритериальной оптимизации. (Количество поражений «среднего» алгоритма – 4, 5 или 6 при числе различных комбинаций генетических операторов равном 9). Это значит, что, отказавшись от настройки параметров, можно обеспечить гарантированный уровень эффективности алгоритма против выбора последних наугад.

Добавить документ в свой блог или на сайт

Похожие:

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconО сравнении эффективности двух различных методов самонастройки генетического...
О сравнении эффективности двух различных методов самонастройки генетического алгоритма

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconНазвание «Оптимизация многоэкстремальных функций на основе кластерной...
Докладчик Казаков П. В., канд техн наук, Брянский государственный технический университет. (pvk )

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconГазоотвод с продольной стороны электролизера уколов А. А., научный...
Обеспечение высокой температуры газовоздушной смеси особенно актуально в условиях колебания концентрации со в анодном газе ниже 30...

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconАвтоматизированная информационная система обмена заказами такси паначев...
Сибирский федеральный университет, институт космических и информационных технологий

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconПараллельная реализация генетического алгоритма обучения нечетких когнитивных карт
Государственное бюджетное учреждение науки Российской Академии Наук Вычислительный центр им. А. А. Дородницына, Москва

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconИсследование бестраншейных технологий эвентов П. С. Научный руководитель...
...

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconСтроительные нормы и правила изоляционные и отделочные покрытия
Е. Д. Белоусов, канд техн наук Г. С. Агаджанов), сктб главтоннельметростроя Минтрансстроя СССР (кандидаты техн наук В. В. Крылова,...

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconГидравилческий удар в трубопроводах. Блинов Алексей научный руководитель...
Причинами, вызывающими гидравлический удар, могут быть: внезапная остановка насосов (турбин), резкое закрытие задвижки, аварии на...

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconИсследование коррозионных отложений в резьбовых соединениях насосно-компрессорных...
И, доступным на сегодняшний день, количество аварий насосно-компрессорных труб (нкт) в ряде случаев достигает 80% от общего числа...

Самоадаптация генетического алгоритма при решении задач многокритериальной оптимизации брестер К. Ю. научный руководитель д-р техн наук Семенкин Е. С iconИсследование кинематики движения режущего органа канатной пилы криворотова...
Рисунок 1- канатные пилы: а передвижная карьерная канатная пила csa-2037 hf на Бурейской гэс; б – стационарная канатная пила для...


Учебный материал


При копировании материала укажите ссылку © 2013
контакты
5-bal.ru