Thursday, September 10, 2009

Конференция в Кацивели: научные результаты

С 24 по 29 сентября сего года в Кацивели (поселок под Ялтой) состоится международный симпозиум "Питання оптимізації обчислень". Мой руководитель и я получили приглашение. Название наших с ним тезисов "Применение ЭВФ-алгоритмов в задачах теории расписаний". Основным результатом этих тезисов является утверждение об универсальности эволюционно-фрагментарных (ЭВФ) алгоритмов.

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

Фрагментарная структура - это упорядоченная тройка (X,Y,R), где X - множество элементарных фрагментов, Y - семейство допустимых фрагментов, R - правило присоединения элементарных фрагментов и/или допустимых фрагментов.

Например, в задаче Джонсона элементарными фрагментами являются работы, а допустимыми фрагментами любые непустые подмножества множества работ без повторений. То есть, в данном случае, правилом присоединения работ является отсутствие повторений.

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

Поскольку в области эволюционных вычислений для того, чтобы проверить эффективность алгоритма, применяется в основном тестирование (в концов концов единственный способ узнать об эффективности ЭА на практике - это проверить его на практике), предлагается провести вычислительный эксперимент. Для тестирования берется набор задач из OR-Library и вычисляется среднее отклонение от известного лучшего значения критерия. Кроме того, проводится сравнение со случайным поиском.

1 comment:

  1. Прикольно. По названию я сначала подумал, что в Грузию поедете =)

    ReplyDelete