GREEDY HEURISTIC METHOD FOR LOCATION PROBLEMS : научное издание

Описание

Перевод названия: МЕТОД ЖАДНЫХ ЭВРИСТИК ДЛЯ ЗАДАЧ РАЗМЕЩЕНИЯ

Тип публикации: статья из журнала

Год издания: 2015

Ключевые слова: p-median, k-medoid, k-means, Information Bottleneck Clustering, p-медианная задача, k-медоид, k-средних, метод "информационного бутылочного горлышка"

Аннотация: Authors consider multi-source location problems, k-means, k-median and k-medoid. Such problems are popular models in logistics (optimal location of factories, warehouses, transportation hubs etc.) and cluster analysis, approximation theory, estimation theory, image recognition. Various distance metrics and gauges allow using these Показать полностьюmodels for clustering various kinds of data: continuous and discrete numeric data, Boolean vectors, documents. Wide area of application of such problems leads to growing interest of researchers in Russia and worldwide. In this paper, the authors propose a new heuristic method for solving such problems which can be used as a standalone local search method (local search multi-start) or as the main part of a new algorithm based on ideas of the probability changing method. For the parameters self-tuning of such algorithm, the authors propose new meta-heuristic which allows using new algorithm without learning specific features of each solved problem. Algorithms were tested on various data sets of size up to 160000 data vectors from the UCI repository and real data of semiconductor devices examination. For testing purposes, various distance metrics were used. Computational experiments showed the high efficiency of new algorithms in comparison with local search methods used traditionally for the considered problems. In addition, results were compared with the evolutionary methods and a deterministic algorithm based on the Information Bottleneck Clustering method. Such comparison illustrated the ability of new algorithms to reach higher preciseness of the results in reasonable time. Рассматриваются задачи множественного размещения - k-средних, k-медианная и задача k-медоид. Данные задачи находят широкое применение как в качестве логистических моделей оптимального размещения складов, производств, транспортных узлов и т. д., так и опосредованно - в качестве наиболее популярных моделей кластерного анализа, автоматической группировки, теории аппроксимации, теории оценивания, распознавания образов. При этом использование различных метрик расстояния или мер сходства позволяет применять данные задачи в качестве моделей автоматической группировки данных самой разнообразной природы: непрерывных и дискретных числовых данных, векторов булевых значений, документов. Широтой области применения рассматриваемых задач определяется возрастающий интерес к ним со стороны как российских, так и зарубежных исследователей. Предложен новый эвристический метод решения таких задач, который может применяться как в качестве самостоятельного алгоритма локального поиска (мультистарт локального поиска), так и в составе нового алгоритма, использующего идеи метода изменяющихся вероятностей (МИВЕР). Для автоматической настройки параметров алгоритма схемы МИВЕР предложена новая метаэвристика, позволяющая использовать разработанный алгоритм без предварительного анализа особенностей конкретной задачи. Работа алгоритмов протестирована на различных наборах данных размерностью до 160000 векторов данных. В качестве тестовых примеров использованы как типовые наборы данных из репозитория UCI, так и реальные данные отбраковочных испытаний полупроводниковых приборов. При этом были использованы различные метрики расстояния. Эксперименты показывают высокую эффективность новых алгоритмов в сравнении с традиционными для данных задач методами локального поиска. Проведено сравнение новых алгоритмов с некоторыми эволюционными алгоритмами, а также с детерминированным алгоритмом, реализующим метод Information Bottleneck Clustering («информационного бутылочного горлышка»), показана способность новых алгоритмов достигать более высокой точности получаемых результатов за приемлемое время.

Ссылки на полный текст

Издание

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

Выпуск журнала: Т. 16, 2

Номера страниц: 317-325

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

Персоны

Вхождение в базы данных