II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ
2.1. Важнейшие научные результаты
Авторы результата: д.ф.-м.н., зав. лаб. Ремесленников В.Н., к.ф.-м.н. Даниярова Э.Ю.
Сформулированы и доказаны объединяющие теоремы, дающие описание 7 различными способами координатных алгебр алгебраических множеств над произвольной нётеровой по уравнениям алгебраической системой. Эти теоремы позволяют при исследовании алгебраических множеств использовать как алгебраические, так и теоретико-модельные, геометрические методы.
Приведём для иллюстрации одну из доказанных теорем.
Теорема С. Пусть B нётерова по уравнениям алгебра языка L без предикатов. Тогда для любой конечно порождённой алгебры C языка L следующие условия эквивалентны:
C принадлежит квазимногообразию, порождённому алгеброй B;
C принадлежит предмногообразию, порождённому алгеброй B;
C вкладывается в прямую степень алгебры B;
C аппроксимируется алгеброй B;
C подпрямо вкладывается в конечную прямую сумму предельных алгебр над B;
C есть алгебра, определённая полным атомарным типом квазиэквациональной теории алгебры B в языке L;
C является координатной алгеброй некоторого алгебраического множества над алгеброй B, определённого системой уравнений в языке L.
Результат опубликован:
Daniyarova E., Miasnikov A., Remeslennikov V. Unification theorems in algebraic geometry, Algebra and Discrete Mathematics, 1 (2008), arXiv:0808.2522v1 [math.AG].
Daniyarova E., Miasnikov A., Remeslennikov V. Unification theorems in algebraic geometry // Abstracts of Intern. Algebraic Conference on the Occasions of the 100th Anniversary of Professor A.G. Kurosh, Moscow, 2008, 284–285.
Daniyarova E., Miasnikov A., Remeslennikov V. Universal algebraic geometry // Abstracts of Intern. Algebraic Conference “New algebraic-logical methods in solutions for systems of equations in algebraic structures”, Omsk, 2009, 8–9.
Remeslennikov V. Limit algebras // Abstracts of Intern. Algebraic Conference “New algebraic-logical methods in solutions for systems of equations in algebraic structures”, Omsk, 2009, p. 14–15.
Результат доложен:
Ежегодная научная сессия ОФ ИМ СО РАН, 28 сентября 2009 г.
Конференции в Италии Китае, Омске, Новосибирске.
Автор результата: старший научный сотрудник, к.ф.-м.н., доцент Еремеев А.В.
С использованием эффективных сводимостей установлена полиномиальная разрешимость задачи оптимальной рекомбинации в генетических алгоритмах для задач упаковки и разбиения множества, простейшей задачи размещения производства, а также задач булевого линейного программирования, имеющих не более двух переменных в каждом ограничении. Вычислительные эксперименты показали перспективность использования оптимальной рекомбинации.
Рассмотрена оптимизационная задача, состоящая в отыскании наилучшего по целевой функции решения-потомка из множества всех возможных потомков на выходе оператора рекомбинации в генетическом алгоритме (ГА). Пара родительских решений при этом считается заданной. Оптимальная рекомбинация исследуется в случае, когда решения задачи представляются бинарными векторами. С использованием эффективных сводимостей задач оптимальной рекомбинации нами установлена полиномиальная разрешимость подзадачи оптимальной рекомбинации для взвешенных задач упаковки и разбиения множества и простейшей задачи размещения производства, сформулированных как задачи булевого линейного программирования. Кроме того, показана полиномиальная разрешимость оптимальной рекомбинации на классе задач булевого линейного программирования, имеющих не более двух переменных в каждом ограничении. Установлена NP-трудность ряда задач оптимальной рекомбинации.
Проведены экспериментальные исследования операторов оптимальной рекомбинации, основанных на решении вспомогательных задач частично целочисленного линейного программирования. Для задачи управления поставками с ограничениями снизу на объем заказа разработано два варианта ГА. В первом алгоритме используется двоичное представление решений и оператор оптимальной рекомбинации. Второй ГА основан на представлении решений с использованием перестановок и на "жадном" декодере. Проведенные эксперименты показали, что ГА с оператором оптимальной рекомбинации имеет преимущество в стоимости получаемых решений по сравнению со вторым ГА, а также по сравнению с коммерческим пакетом решения частично целочисленных задач CPLEX. Аналогичные результаты получены для задач балансировки производственной линии и составления расписаний.
Результат опубликован:
Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // European Journal of Operational Research. Vol. 195 N 3, 2009, P. 770-779.
Eremeev A.V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Computation, Vol. 16 N 1, 2008, P. 127-147.
Результат доложен на ежегодной научной сессии ОФ ИМ СО РАН, 28 сентября 2009 г.
|
