Теоретические основы кластерного анализа

Магазины перенумерованы числами jÎТ=(1,2,3..n). Тур участника может быть описан циклической перестановкой t=(j₁,j₂,..,j_n,j₁), причём все j₁..j_n – разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин  С_ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

                                                                                (1)

Во-первых, в постановке С_ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:

Сij³0; Cjj=∞

(2)

(последнее равенство  означает запрет на петли в  туре), симметричными, т.е.  для  всех i,j:

Сij= Сji.

(3)

и удовлетворять неравенству  треугольника, т.е. для всех:

Сij+ Сjk³Cik

(4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется  много прикладных задач, которые  описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j₁,j₂,..,j_n,j₁) и t’=(j₁,j_n,..,j₂,j₁) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и  последнем месте в циклической  перестановке номер j₁, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что  С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j)  проведено, если С_ij=0 и не проведено, если С_ij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n  вершинами, длина ребра (i,j)= С_ij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».

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

Итак, для решения этой задачи необходимо составить для каждой группы матрицу расстояний, размерностью n*n, где n – число посещаемых магазинов.

Диалоговое окно GH выглядит следующим образом. Оно похоже на надстройку поиск решений Exsel -  так же выбирается целевая функция, подбираемые параметры (в GH - хромосомы) и ограничения. Типы хромосом в нашем случае – перечисляемые и уникальные – поскольку в 1 магазин мы можем зайти 1 раз за рейд.

Результаты решения  задачи коммивояжера:

Удобнее всего пройти следующим образом:

	магазин	Расстояние	X	Y
9	12	0,000164537	52,941291	36,0495329
7	16	0,035143166	52,941127	36,0495329
4	19	0,003595822	52,925719	36,0179472
6	17	0,021212348	52,929289	36,017518
1	22	0,017418649	52,947761	36,0279465
5	18	0,004258032	52,949438	36,0452843
8	14	0,012212259	52,953496	36,0465717
3	20	0,02294063	52,950368	36,0583765
2	21	0,024728014	52,941291	36,0495329
10	начало	0,00	52,941205	36,0503464

Второй кластер:

#	магазин	Раcстояние	X	Y
9	начало	0,003121177	52,97995	36,053936
1	29	0,007659475	52,979654	36,057043
3	33	0,006574704	52,986268	36,060905
5	35	0,018209236	52,985157	36,067386
2	32	0,011545436	52,967197	36,064382
6	36	0,009761768	52,969808	36,053135
4	34	0,010376991	52,976914	36,046443
8	38	0,00064287	52,986707	36,042709
7	37	0,013405247	52,97995	36,053936

Графически:

 

 

 

 

 

Третий кластер

#	магазин	Расстояние	X	Y
3	24	0,01	53,0	36,1
6	27	0,00	53,0	36,1
5	26	0,03	53,0	36,1
1	10	0,04	53,0	36,1
4	25	0,01	53,0	36,1
2	23	0,02	53,0	36,1
7	начало	0,00	53,0	36,1

Графически:

 

 

 

 

 

Четвертый кластер

#	магазин	Расстояние	X	Y
14	30	0,009301024	52,97955019	36,08103275
15	31	0,001404058	52,97725043	36,07202053
13	28	0,012488011	52,97613926	36,07116222
12	15	0,00716988	52,96401796	36,06815815
11	13	0,009784826	52,95814993	36,07227802
1	1	0,005143315	52,96752871	36,07506752
2	2	0,005010066	52,96732159	36,08020666
8	8	0,002765151	52,97228873	36,08086109
10	11	0,012558553	52,97329662	36,08343601
3	3	0,004922581	52,96164176	36,08811378
4	4	0,006366903	52,96559018	36,09105349
7	7	0,016849194	52,96861877	36,09665394
5	5	0,020177267	52,95548708	36,10721111
6	6=начало	0,031567971	52,97509397	36,11197472
9	9	0,02068977	52,99804719	36,09030247

Графически:

 

 

 

 

 

 

 

 

На самом деле оказалось, что по представленным результатам  удобнее всего пройти, поскольку  меньше времени затрачено, чем обычно, выбранным путем прохождения по этим же магазинам просто рассматривая карту района.

 

Заключение

 

В данной курсовой работе были проанализированы сущности основных методов кластеризации и решения  задачи коммивояжера, рассмотрены их основные черты и элементы, а так же представлена классификация алгоритмов кластеризации. Кроме того, в работе приведено решение задачи коммивояжера на примере магазинов города Орла сети «Сберегайка» с применением методов кластерного анализа и сформулированы кратчайшие пути прохождения рейдов проверок по этим магазинам.

В ходе работы  было установлено, что наиболее удобными являются кластеризация  с помощью метода к-средних и  генетических алгоритмов. и дают они  достаточно согласованные результаты.

С помощью методов кластеризации большой объем магазинов разбили на группы для облегчения решения задачи нахождения оптимального пути рейдов проверок по магазинам, а так же вынесены предложения по изменению путей рейдов проверок, которые были успешно приняты и одобрены – на пути по точкам потрачено на 15 минут меньше времени чем обычно.

  

Список используемой литературы:

¹Мудров В. И., Задача о коммивояжёре, М., 1969;

1. ² Статистический словарь

2. ³ http://www.ligis.ru/effects/stat/modules/stcluan.html Наука и технологии Электронный учебник StatSoft Статистика.

3. ⁴ Кластерный анализ Дюран и Одел

4. ⁵ А. С. Тараскина
5. НЕЧЕТКАЯ КЛАСТЕРИЗАЦИЯ ПО МОДИФИЦИРОВАННОМУ
6. МЕТОДУ C-СРЕДНИХ И ЕЕ ПРИМЕНЕНИЕ ДЛЯ ОБРАБОТКИ
7. МИКРОЧИПОВЫХ ДАННЫХ

8. ⁶ Авторы: Вильям Кук Решение задачи коммивояжера c использованием генетических алгоритмов  Перевод: Поправко А.А. http://www.masters.donntu.edu.ua/2010/fknt/popravko/library/article10_ru.htm