RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Ж. вычисл. матем. и матем. физ., 2012, том 52, номер 1, страницы 164–176 (Mi zvmmf9646)  

Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)

Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности

Ю. А. Кочетов, А. В. Плясунов

630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН

Аннотация: Для задачи о разбиении графа на доли ограниченной мощности разработан метод генетического локального поиска. На каждой итерации метода имеется набор локальных оптимумов задачи. Этот набор используется для целенаправленного поиска новых локальных оптимумов с меньшей погрешностью. Установлена плотная PLS-полнота задачи нахождения локальных оптимумов с рядом полиномиально проверяемых окрестностей. Показано, что в худшем случае число локальных улучшений может оказаться экспоненциальным при любых правилах выбора направления спуска. Для частного случая задачи, когда веса ребер равны единице и нахождение локальных оптимумов является полиномиальной процедурой, проведены численные эксперименты. Результаты экспериментов свидетельствуют о высокой эффективности разработанного метода и возможности решать задачи большой размерности. Библ. 25.

Ключевые слова: задача о разбиениях графа, плотная PLS-полнота, локальный поиск, генетические алгоритмы.

Полный текст: PDF файл (237 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2012, 52:1, 157–167

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 29.03.2011
Исправленный вариант: 06.07.2011

Образец цитирования: Ю. А. Кочетов, А. В. Плясунов, “Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности”, Ж. вычисл. матем. и матем. физ., 52:1 (2012), 164–176; Comput. Math. Math. Phys., 52:1 (2012), 157–167

Цитирование в формате AMSBIB
\RBibitem{KocPly12}
\by Ю.~А.~Кочетов, А.~В.~Плясунов
\paper Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности
\jour Ж. вычисл. матем. и матем. физ.
\yr 2012
\vol 52
\issue 1
\pages 164--176
\mathnet{http://mi.mathnet.ru/zvmmf9646}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2953302}
\zmath{https://zbmath.org/?q=an:06057683}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2012CMMPh..52..157K}
\elib{http://elibrary.ru/item.asp?id=17313432}
\transl
\jour Comput. Math. Math. Phys.
\yr 2012
\vol 52
\issue 1
\pages 157--167
\crossref{https://doi.org/10.1134/S096554251201006X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000300287300015}
\elib{http://elibrary.ru/item.asp?id=17975588}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84856671220}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf9646
  • http://mi.mathnet.ru/rus/zvmmf/v52/i1/p164

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Фараонов, “Ситуационная модель выбора маршрута доставки при необходимости изменения опорного плана на основе нечетких множеств”, Транспорт: наука, техника, управление, 2012, № 12, 25–30  elib
    2. А. В. Фараонов, “Разработка ситуационной модели выбора маршрута доставки при необходимости изменения опорного плана на основе нечетких множеств”, Наука и техника транспорта, 2013, № 2, 40–49  elib
    3. Ю. А. Кочетов , Н. А. Кочетова, “Задача балансировки нагрузки на серверы”, Вестник Новосибирского государственного университета. Серия: Информационные технологии, 11:4 (2013), 71–76  elib
    4. А. В. Фараонов, “Ситуационная модель выбора маршрута доставки”, Прикладная информатика, 2013, № 2(44), 113–126  elib
    5. Ю. А. Кочетов, А. А. Панин, А. В. Плясунов, “Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования”, Дискретн. анализ и исслед. опер., 22:3 (2015), 36–54  mathnet  crossref  mathscinet  elib; Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Comparison of metaheuristics for the bilevel facility location and mill pricing problem”, J. Appl. Industr. Math., 9:3 (2015), 392–401  crossref
    6. Ю. А. Кочетов, А. А. Панин, А. В. Плясунов, “Генетический локальный поиск и сложность аппроксимации задачи балансировки нагрузки на серверы”, Автомат. и телемех., 2017, № 3, 51–62  mathnet  mathscinet  elib; Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Genetic local search and hardness of approximation for the server load balancing problem”, Autom. Remote Control, 78:3 (2017), 425–434  crossref  isi
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:208
    Полный текст:53
    Литература:26
    Первая стр.:13

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019