Кластеризация, решение задач коммивояжера с помощью генетических алгоритмов. Разбиение участников рейда на группы методом древовидной кластеризации, выявление центра сбора участников с помощью генетических алгоритмов. Проверка качества кластеризации.
Участники рейда должны выйти из точки встречи, посетить по разу в неизвестном порядке магазины 2, 1, 3.. n и вернуться в точку сбора. В каком порядке следует обходить магазины в течение рейда, чтобы замкнутый путь (тур) участников был кратчайшим? Формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n - 1 других городов и вернуться в исходный. К задачам такого типа, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем. «Кластерный анализ - совокупность математических методов, предназначенных для формирования относительно «отдаленных» друг от друга групп «близких» между собой объектов по информации о расстояниях или связях (мерах близости) между ними.Термин кластерный анализ (впервые ввел Tryon, 1939) в действительности включает в себя набор различных алгоритмов классификации. Общий вопрос, задаваемый исследователями во многих областях, состоит в том, как организовать наблюдаемые данные в наглядные структуры, т. е. развернуть таксономии. Фактически, кластерный анализ является не столько обычным статистическим методом, сколько «набором» различных алгоритмов «распределения объектов по кластерам». Существует точка зрения, что в отличие от многих других статистических процедур, методы кластерного анализа используются в большинстве случаев тогда, когда вы не имеете каких-либо априорных гипотез относительно классов, но все еще находитесь в описательной стадии исследования.Диаграмма начинается с каждого объекта в классе (в левой части диаграммы). Другими словами, понижается порог, относящийся к решению об объединении двух или более объектов в один кластер. На этих диаграммах горизонтальные оси представляют расстояние объединения (в вертикальных древовидных диаграммах вертикальные оси представляют расстояние объединения).Объединение или метод древовидной кластеризации используется при формировании кластеров расстояния между объектами. Наиболее прямой путь вычисления расстояний между объектами в многомерном пространстве состоит в вычислении евклидовых расстояний. Если есть двух-или трехмерное пространство, то эта мера является реальным геометрическим расстоянием между объектами в пространстве (как будто расстояния между объектами измерены рулеткой). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. Это расстояние вычисляется следующим образом: расстояние (x, y) = i (xi - yi) 2Выбирается число k, и на первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом: выбор k-наблюдений для максимизации начального расстояния; Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий: кластерные центры стабилизировались, т. е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т. е. оценить, насколько кластеры отличаются друг от друга). При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части. Недостатки алгоритма k-средних: алгоритм слишком чувствителен к выбросам, которые могут искажать среднее.Генетические алгоритмы не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска «достаточно хорошего» решения задачи «достаточно быстро». Генетический алгоритм работает с популяцией - совокупностью особей, которые представляют собой возможные решения данной задачи. Хотя он не может найти лучшее решение, он может стать практически идеальным решением для расчета 100 туров по городу менее чем за минуту. Этот алгоритм использует жадные вычисления для расчета первоначальной популяции, отдавая предпочтение связи городам, которые находятся близко друг к другу. 2 наиболее сложных вопроса, с использованием генетического алгоритма для решения задачи коммивояжера является вопрос кодирования тура и алгоритм кроссовера, который используется, чтобы объединить два тура родителей, для получения потомков тура.Исходный файл данных содержит следующую информацию о магазинах - координаты в пространстве. Были использованы адреса магазинов сберегайка в Железнодорожном и Заводском районах города Орла. Орел, пл. Орел, ул. Орел, Курская 35 с 8-00 до 22-00На первом этапе выясним, формируют ли магазины «естественные» кластеры, которые могут быть осмыслены. Выберем Кластерный анализ в меню Анализ - Многомерный разведочный анализ для отображения стартовой панели модуля Кластерный анализ. Нажмем кнопку Переменные, выберем Все, в поле Объекты выберем Наблюдения (строки).
План
Оглавление
1. Введение
2. Теоретические основы кластерного анализа
2.1 Объединение (древовидная кластеризация)
2.1.1 Иерархическое дерево
2.1.2 Меры расстояния
2.1.3 Правила объединения
2.2 Метод К средних
2.2.1 Описание алгоритма
2.2.2 Проверка качества кластеризации
2.3 Кластеризация с помощью генетических алгоритмов
2.4 Решение задачи коммивояжера с помощью генетических алгоритмов
3.1 Описание объектов кластеризации
3.2 Разбиение участников рейда на группы методом древовидной кластеризации
3.3 Разбиение участников рейда на группы методом К средних
3.4 Разбиение участников рейда на группы и выявление центра сбора участников рейда с помощью генетических алгоритмов
3.5 Нахождение оптимальных путей для каждой из групп
4 Заключение
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
