Для того чтобы заполнить список obstacles, используется алгоритм обхода препятствий, который рассчитывает граф видимости. В Приложении 1 расположен исходный код программы на Delphi, решающий задачу коммивояжера с препятствиями. В данном коде комплекс функций InitialFullFill, FullFillNeighbour, NotTemporary, Intersect, PreIntersect, FinalTrans рассчитывает граф видимости и заполняет массив obstacles, позволяя алгоритму муравья обходить препятствий.

Массив obstacles так же как и массив TabuList заполняется нулями и единицами. К примеру, если элемент массива obstacles, то грань между узлами видима, если элемент массива obstacles, то грань между узлами не видима (пересекает какое-то препятствие).

Первым шагом функция InitialFullFill заполняет массив obstacles некой первоначальной величиной, которая соответствует непроверенному ребру. В качестве такой величины была выбрана . Если элемент массива obstacles, то ребро между узлами еще не проверено на пересечение с препятствиями. Функция InitialFullFill также записывает в элементы массива, расположенные на его диагонали. Это объясняется тем, что когда в алгоритме муравья агент переходит в узел , он записывает этот узел в список табу и уже не может его посетить. Значит, находясь в узле и выбирая следующий узел для движения, агент не может выбрать текущий узел для посещения. Элементы, стоящие на диагонали массива как раз и соответствуют переходу из узла в узел при условии что , поэтому из значения приравниваются .

Далее функция FullFillNeighbour заполняет элементы массива, которые соответствуют соседним узлам препятствия, значением . Таким образом, агент может передвигаться по границе препятствия, не пересекая её.

Функция PreIntersect передает функции Intersect координаты узлов одного непроверенного ребра графа и координаты всех узлов, которые образуют грани препятствия. Если непроверенное ребро графа с узлами не пересекает ни одной грани препятствия, то это означает, что ребро между узлами видимо и значение массива obstacles не меняется. Если же непроверенное ребро графа с узлами пересекает хотя бы одну грань хотя бы одного препятствия, то в массив obstacles записывается , то есть ребро между узлами не видимо.

Функция FinalTrans вызывается в конце, когда в массив obstacles записаны все ограничения. Функция изменяет все элементы массива, значение которых осталось равно 2, на новое значение - 0.

1.4.3 Пример работы алгоритма обхода препятствий

Для иллюстрации работы алгоритма обход препятствий, рассмотрим следующий пример, показанный на рисунке 8.



Рисунок 8. Задача с двумя городами и препятствием

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

На первом шаге функция InitialFullFill заполняет массив obstacles цифрами два, а по диагонали цифрами один. На первом шаге массив obstacles примет следующий вид (таблица 4):

Узлы	1	2	3	4	5	6
1	1	2	2	2	2	2
2	2	1	2	2	2	2
3	2	2	1	2	2	2
4	2	2	2	1	2	2
5	2	2	2	2	1	2
6	2	2	2	2	2	1

Таблица 4. Массив obstacles после функции InitialFullFill

Далее FullFillNeighbour заполняет элементы массива, которые соответствуют соседним узлам препятствия, значением . В данном примере соседними узлами препятствия являются следующие пары узлов: ; ; . Массив obstacles примет следующий вид (таблица 5):



Таблица 5. Массив obstacles после функции FullFillNeighbour

Узлы	1	2	3	4	5	6
1	1	2	2	2	2	2
2	2	1	2	2	2	2
3	2	2	1	0	2	0
4	2	2	0	1	0	2
5	2	2	2	0	1	0
6	2	2	0	2	0	1

Рассмотрим работу функции PreIntersect. Она поочередно проверяет, является ли ребро графа проверенным или нет. Если нет, то она передает функции Intersect координаты узлов непроверенного ребра и координаты узлов всех ребер препятствий.

Таким образом, на первом шаге функция проверяет элемент массива obstacles, который равен единице. Это означает, что ребро является невидимым, происходит переход к следующему ребру obstacles.

На втором шаге функция проверяет ребро , которое является непроверенным, поэтому функция PreIntersect передает функции Intersect координаты узлов этого непроверенного ребра и координаты узлов всех ребер препятствий. Функция Intersect возвращает значение типа Boolean; true соответствует тому, что ребра пересекаются, false соответствует тому, что ребра не пересекаются.

Intersect (ребро не пересекает ребро препятствия).

Intersect (ребро пересекает ребро препятствия, следовательно ребро является не видимым (запрещенным), поэтому в элемент массива obstacles записывается.

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

Intersect (ребро не пересекает ребро препятствия).

Intersect (ребро не пересекает ребро препятствия).

Intersect (ребро не пересекает ребро препятствия).

Intersect (ребро не пересекает ребро препятствия).

Таким образом, ребро не пересекает ребер препятствия, следовательно, ребро является видимым (разрешенным), поэтому в элемент массива obstacles не записывается (остается прежнее значение . Цикл продолжается, пока не будут проверены все ребра. Ребра, лежащие внутри препятствий, помечаются не видимые (не разрешенные).

Массив obstacles примет следующий вид (6):

Узлы	1	2	3	4	5	6
1	1	1	2	1	1	2
2	1	1	1	2	2	1
3	2	1	1	0	1	0
4	1	2	0	1	0	1
5	1	2	1	0	1	0
6	2	1	0	1	0	1

Таблица 6. Массив obstacles после функции PreIntersect

Функция FinalTrans производит окончательное преобразование массива obstacles, изменяя все элементы массива, значение которых осталось равно цифре два, на новое значение - цифре ноль.

Массив obstacles примет следующий вид (таблица 7):

Узлы	1	2	3	4	5	6
1	1	1	0	1	1	0
2	1	1	1	0	0	1
3	0	1	1	0	1	0
4	1	0	0	1	0	1
5	1	0	1	0	1	0
6	0	1	0	1	0	1

Таблица 7. Массив obstacles после функции FinalTrans

Итоговый массив описывает все возможные перемещения из всех узлов графа и используется далее в алгоритме муравья.

1.4.4 Структура данных алгоритма муравья

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

Константы:

- MAX_OBSTACLE_NODES - параметр, отвечающий за количество узлов препятствий;

- MAX_CITIES - параметр, отвечающий за количество городов;

- MAX_NODES=MAX_OBSTACLE_NODES+MAX_CITIES - параметр, отвечающий за общее количество узлов препятствий и городов.

- MAX_DISTANCE - параметр, отвечающий за максимальную дистанцию между городами;

- MAX_ANTS - параметр, отвечающий за максимальное количество муравьев.

- ALPHA, BETA, RHO, QVAL - параметры алгоритма муравья, подробно описанные выше;

- MAX_TOURS - параметр, отвечающий максимальную длину тура;

- MAX_TIME - параметр, отвечающий за количество итераций алгоритма;

- INIT_PHEROMONE - начальное значение феромона;

- NK - количество препятствий

Структура данных antType:

- curCity - параметр, отвечающий за текущий город, в котором находится агент;

- NextCity - параметр, отвечающий за следующий город, в который переходит агент;

- PathIndex - счетчик посещенных узлов препятствий;

- PathIndex_city - счетчик посещенных городов;

- Tabu - массив посещенных городов;

- Path - массив последовательности посещенных городов;

- TourLength - длина маршрута.

Структура данных cityType:

- X - координата X;

- Y - координата X;

Глобальная структура данных

- Distance - массив расстояний между городами и узлами препятствий;

- Cities - массив с координатами городов и координатами узлов препятствий;

- ants - массив, в котором записана информация про каждого агента. Элемент массива содержит минимальный путь;

- Obstacles - массив, содержащий информацию о графе видимости;

- pheromone: массив, в котором записана информация о количестве феромонов на видимых ребрах графа;

- best - наименьшая длина маршрута;

- bestIndex - номер агента с наименьшей длиной маршрут

- curTime - счетчик итераций;

- denom - используется для расчета формулы (4.1);

- Inf:array - массив, содержащий информацию о количестве городов, о количества препятствий и о количестве их ребер.

Структура cityType используется для определения координат городов и узлов препятствий. Структура antType представляет одного муравья. Кроме отслеживания текущего и следующего города на пути (поля curCity и nextCity) каждый муравей также должен учитывать города, которые уже были посещены (массив tabu), узлы, которые можно посетить, находясь в текущем узле (учесть массив obstacles), а также длину пройденного пути. Наконец, общая длина пуп сохраняется в поле tourLength.

Структуры данных в алгоритме включают также специальный двумерный массив distance, который содержит предварительно рассчитанные расстояния от одного города до всех других. Уровни фермента сохраняются в массиве pheromone. Каждый двумерный массив в алгоритме использует первый индекс в качестве начала ребра, то есть исходного города, а второй -- в качестве конечного.

1.4.5 Использование графа видимости в алгоритме муравья

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

В данном пункте рассмотрим то, как использовать граф видимости в алгоритме муравья. В Приложении 1 расположен исходный код программы на Delphi, сейчас же остановимся на основных этапах построения алгоритма движения муравья.

Сначала функция init выполняет три базовых действия, которые требуются для подготовки алгоритма муравья. Первое действие - это считывание координат городов. Кроме того, во время считывания городов одновременно очищаются массивы distance и pheromone.

Далее, немного оптимизируя алгоритм, выполняется предварительный расчет расстояний между всеми городами и узлами препятствий. Расстояния вычисляется с помощью обычной двумерной геометрии координат (теорема Пифагора).

Наконец, инициализируется массив ant. Муравьи должны быть равномерно распределены по всем городам. Для этого используется переменная to1 в качестве счетчика псевдоцикла. Когда значение переменной to1 становится равным номеру последнего города, она возвращается к первому городу, и процесс повторяется. Поле curcity в структуре ant устанавливается в значение текущего города (первого города для муравья). Затем очищаются списки tabu и path. Ноль в массиве tabu обозначает, что город еще не был посещен; единица свидетельствует, что город уже включен в путь муравья. В массив path помещается номер текущего города для муравья, и очищается поле tourLength (длина пути).

После завершения пути каждый муравей должен быть повторно инициализирован, а затем распределен по графу. Это выполняет функция restartAnts.

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

Функция selectNextCity позволяет выбрать следующий город для составления пути. Она вызывает функцию antProduct, которая используется для расчета уравнения (5).

Функция selectNextCity вызывается для заданного муравья и определяет, которую из граней можно выбрать в соответствии со списком tabu. На этом шаге список tabu уже включает в себя информацию обо всех видимых и невидимых гранях. Выбор грани основывается на вероятностном уравнении (5), которое вычисляет коэффициент заданного пути от суммы других путей. Первой задачей функции selectNextCity является расчет знаменателя выражения. После этого все ребра, которые агент может посетить из данного узла, проверяются с помощью уравнения (5), чтобы муравей мог выбрать путь. Как только ребро найдено, функция определяет город, к которому перейдет муравей. Следующая функция, simulateAnts, рассчитывает движения муравьев по графу.

Функция simulateAnts добавляет в список tabu, который содержит информацию о посещенных городах, информацию о видимых из текущего узла ребрах графа из массива obstacles. Затем функция проверяет, есть ли для агента, находящегося в текущем узле, следующий ход. Если агенту некуда идти, то есть в списке tabu нет , то функция рассматривает следующего агента. Если списке tabu есть хотя бы один , значит, муравей может совершить еще один ход. Если муравей еще не посетил все города, то есть если переменная pathIndex_city не равна MAX_CITIES, то в этом случае вызывается функция selectNextCity, которая определяет следующую грань. Затем выбранный узел сохраняется в переменной nextcity, а также в массивах path и tabu. Увеличивается на единицу переменная pathIndex, а если выбранный узел оказался городом, то увеличивается на единицу переменная pathIndex_city. Рассчитывается значение tourLength, чтобы сохранить длину пути.

Один вызов функции simulateAnts позволяет каждому муравью перейти от одного узла к другому. Функция simulateAnts возвращает нуль, если посещены все города, в противном случае - значение, отличное от нуля.

После завершения пути выполняется процесс обновления путей. Он включает не только обновление путей по количеству фермента, оставленного агентами, но и существующего фермента, часть которого испарилась. Эту часть алгоритма выполняет функция updateTrails.

Первая задача функции updateTrails заключается в том, чтобы испарить часть фермента, который уже находится на пути. Она выполняется на всех видимых ребрах графа с помощью уравнения (8). Следующая задача - получение нового фермента на путях, пройденных муравьями во время последних перемещений. Для этого необходимо пройти по элементам массива ant и, руководствуясь значением поля path, «распылить» новый фермент на посещенной муравьем грани в соответствии с уравнением (6). Затем следует применить параметр RHO, чтобы снизить интенсивность фермента, который выделяют муравьи.

После инициализации генератора случайных чисел и установки начальных значений параметров алгоритма запускается симуляция для количества шагов, заданного константой MAX_TIME. Когда муравей завершает путь (который он проходит с помощью функции simulateAnts), вызывается функция updateTrails для того, чтобы изменить окружающую среду.

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

1.4.6 Моделирование алгоритма муравья на ЭВМ

В данном разделе представлены результаты моделирования алгоритма муравья на примере задачи коммивояжера с препятствиями.

Моделирование производилось с двумя целями:

- изучение влияния параметров , , на сходимость алгоритма к оптимальному решению

- сравнение с алгоритмом Дейкстры.

Для изучения влияния параметров было произведено моделирование алгоритма муравья при различных значениях параметров , , . Тестируемые значения параметров выбирались в соответствии с рекомендациями основателя алгоритма Марко Дориго. /28/ Параметр Q не рассматривался, т.к. согласно данной работе величина Q не влияет на производительность алгоритма. В качестве постоянного значения Q было выбрано значение 20. Во всех экспериментах количество муравьев было равно количеству городов. Каждый муравей начинал свой путь из города, а не из вершины препятствия. Менялась величина одного параметра, при этом величина других параметров оставалась неизменной. В качестве постоянных параметров использовались следующие значения: . В каждом эксперименте изменялась величина только одного параметра. Изменяемые значения параметров: , , . Количество циклов алгоритма в каждом эксперименте менялось пропорционально количеству городов и равнялось MAX_TOURS * MAX_CITIES*10. Каждая комбинация параметров тестировалась десять раз.

Моделирование производилось на персональном компьютере на базе процессора Intel Core 2 Duo 2.67 GHz, с объемом оперативной памяти 2GB. Количество городов изменялось от 5 до 25 городов с шагом 5. Количество препятствий равнялось трем, конфигурация препятствий: треугольник, прямоугольник и восьмиугольник. Конфигурация препятствий, их координаты и координаты городов были заданы дипломным руководителем и представлены в Приложении 2.

Подробные результаты каждого эксперимента и все временные диаграммы, характеризующие влияние параметров , , расположены в Приложении 3. Анализ полученных результатов будет произведен в следующем разделе. В данном разделе остановимся на лучших решениях, которые были получены.

Вариант задачи с пятью городами

В связи с маленьким количеством городов, при всех комбинациях параметров, кроме , , была найдена минимальная длина пути: 199,361. Результат работы алгоритма проиллюстрированы на рисунке (9):



Рисунок 9. Результат работы алгоритма муравья для 5 городов.

Вариант задачи с десятью городами

В данном примере минимальная найденная длина пути составила: 262,045. Параметры, при которых она был найден:

, ,

, ,

, ,

, ,

Результат работы алгоритма проиллюстрированы на рисунке (10):



Рисунок 10. Результат работы алгоритма муравья для 10 городов.

Вариант задачи с пятнадцатью городами

В данном примере минимальная найденная длина пути составила: 303,926. Параметры, при которых оно был найден:

, ,

Результат работы алгоритма проиллюстрированы на рисунке (11):

Рисунок 11. Результат работы алгоритма муравья для 15 городов.

Вариант задачи с двадцатью городами

В данном примере минимальная найденная длина пути составила: 341,038.

Параметры, при которых она была найдена:

, ,

Результат работы алгоритма проиллюстрированы на рисунке (12):

Рисунок 12. Результат работы алгоритма муравья для 20 городов.

Вариант задачи с двадцатью пятью городами

В данном примере минимальная найденная длина пути составила: 375,068.

Параметры, при которых она была найдена:

, ,

Результат работы алгоритма проиллюстрированы на рисунке (13):



Рисунок 13. Результат работы алгоритма муравья для 25 городов.

Для сравнения с алгоритмом Дейкстры была рассмотрена работа аспиранта 301 кафедры МАИ Чжо Мьо Хана. /10/ В данной работе задача коммивояжера с препятствиями решена с помощью алгоритма Дейкстры. Для обхода препятствий использовалась диаграмма Вороного. Данная задача используется в качестве тестовой для сравнения её с алгоритмом муравья. Исходный код программы представлен в Приложении 4. Задача изображена на рисунке 14:

Рисунок 14. Тестовая задача, решенная с помощью алгоритма Дейкстры

Минимальный путь, найденный алгоритмом Дейкстры для данной задачи, составил 170,32.

Задача с такой же конфигурацией городов и препятствий была решена алгоритмом муравья. Использовались следующие параметры алгоритма:

, ,

Число муравьев равнялось количеству городов. Количество циклов алгоритма было задано равным 2400. Результаты моделирования представлены на рисунке 15:

Рисунок 15. Тестовая задача, решенная алгоритмом муравья

Минимальный путь, найденный алгоритмом муравья, составил 146,165. Таким образом, можно сделать вывод, что алгоритм муравья справился с тестовой задачей лучше.

1.5 Анализ полученных результатов

В данном подразделе проанализировано влияние параметров , , на сходимость алгоритма муравья к оптимальному решению.

В варианте задачи с пятью городами алгоритм муравья показывает наилучшие результаты (в десяти случаях из десяти) при следующих значениях параметров: , , . В дальнейшем будем называть эту комбинацию параметров набором номер один. Следует отметить, что в связи с относительно малым количеством городов, алгоритм достаточно хорошо сходится к минимальному решению и при всех остальных значениях параметров , , , кроме следующего: , , . Причина этого будет описана ниже.

С увеличением городов до десяти алгоритм муравья по-прежнему показывает наилучшие результаты при наборе параметров номер один. Средний путь составляет 256, 176. Алгоритм муравья находит близкие к этому найденному минимальному решению результаты (266, 306; 268, 173) при следующих значениях параметров: , , и , , . В дальнейшем будем называть их набором параметров номер два и три соответственно. При всех остальных значениях параметров алгоритм находит решения со средним значением, отличающимся от минимального найденного, в большую сторону более чем на 10.

На рисунке 16 в графическом виде представлена зависимость среднего найденного пути от нескольких наборов параметров.



Рисунок 16. Влияние параметров алгоритма на среднюю длину пути.

На данном рисунке:

график под номером 1 () соответствует набору параметров номер один: , , ;

график под номером 2 () соответствует набору параметров номер два: , , ;

график под номером 3 () соответствует набору параметров номер три:

, , ;

график под номером 4 () соответствует следующему набору параметров:

, , ;

график под номером 5 () соответствует следующему набору параметров:

, , ;

график под номером 6 () соответствует следующему набору параметров:

, , .

Зависимость длины среднего найденного пути от всех протестированных наборов параметров в графическом виде представлена на рисунке 22 в Приложении 3.

Как видно из рисунка 16, наилучший результат во всех пяти задачах достигается при наборе параметров номер один, затем при наборе параметров номер два и три. Следует отметить, что с увеличением количества городов увеличивается разница между длиной среднего пути, найденной при наборе параметров номер один и между длинами средних путей, найденных при всех остальных наборах параметров. При этом если для набора параметров номер и два и три эта разница не велика (не более 20), то для всех других наборов параметров (кроме нижеописанного) разница более существенна (более 50).

Единственным исключением является следующий набор параметров: , , . В нем с увеличением количества городов разница с минимальной найденной длиной пути уменьшается. Это можно объяснить тем, что параметр определяет вес расстояния при расчете вероятности по формуле (5). С увеличением количества городов увеличивается и минимальное расстояние, находимое алгоритмом муравья. Следовательно, увеличивается влияние параметра на найденное решение. Таким образом, при малом количестве городов (при пяти) влияние параметра мало и при значении алгоритм сходится к неоптимальному решению. При увеличении количества городов (более 15) влияние параметра увеличивается и разница с минимальной найденной длиной пути уменьшается.

Таким образом, можно заключить, что при дальнейшем увеличении количества городов следует использовать набор параметров номер один, либо набор параметров номер 6.

Время выполнения программы можно оценивать только в пределах одного варианта задачи, т.к. с увеличением количества городов пропорционально увеличивается количество циклов выполнения алгоритма. Как и следовало ожидать, при дробных значениях параметров и увеличивается время выполнения программы, т.к. эти параметры входят в уравнение (5) в качестве степеней. В зависимости от количества городов при дробных значениях параметров и это время увеличиваются на 30-50% по сравнению со временем выполнения программы при целых значениях и .

2. Экономическая часть

2.1 Определение целесообразности разработки алгоритма

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

Для экономической эффективности разрабатываемых алгоритмов и программного продукта (ПП) необходимо:

- определить целесообразность выполнения разработки;

- определить трудоемкость и затраты на создание ПП;

- определить показатели экономической эффективности разработки ПП.

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

Анализируемые характеристики качества алгоритмов и программных продуктов представлены в таблице 8.

Таблица 8. Характеристики качества алгоритмов и программных продуктов.

№	Характеристики качества ПП	Единица измерения	Значения характеристик качества ПП	Значимость характеристик
			аналог	новый вариант
1	Универсальность	Относительные единицы	1	2	0.2
2	Точность		1	1.3	0.2
3	Надежность		1	1.5	0.2
4	Возможность модернизации		1	4	0.4

Определим индекс технического уровня разработки по формуле:

где x_iН, x_iБ - уровень i-ой функциональной характеристики соответственно нового и базового ПП;

м_i - значимость i-ой функциональной характеристики;

n - количество рассматриваемых функциональных характеристик.

Значимость i-ой функциональной характеристики определяется экспертным путем, при этом учитывается условие:

.

Таким образом, индекс технического уровня равен:

Индекс технического уровня разрабатываемого ПП больше единицы, следовательно, делаем заключение о целесообразности разработки.

2.2 Определение трудоемкости разработки алгоритма и ПП

В процессе планирования разработки ПП определяется трудоемкость его создания. При традиционном программировании каждый элемент ПП содержит все этапы решения задачи, начиная с ввода исходных данных и кончая выводом результатов. Для этого случая затраты труда в чел.-час определяются по формуле:

t_ПП = t_О + t_И + t_А + t_К + t_ОТ + t_Д ,

где t_О - затраты труда на подготовку описания задачи;

t_И - затраты труда на изучение описания задачи;

t_А - затраты труда на разработку алгоритма решения задачи;

t_К - затраты труда на составление программы;

t_ОТ - затраты труда на отладку программы;

t_Д - затраты труда на подготовку документации по ПП.

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

,

где

q = 1200- - предполагаемое количество команд,

К_С - коэффициент сложности программы, характеризует относительную сложность программы по отношению к так называемой типовой задаче, реализующей стандартные методы решения, сложность которой принята равной единице (величина с лежит в пределах от 1,25 до 2). Для программного продукта, реализующего алгоритм, сложность задачи возьмем 1,6.

К_К - коэффициент коррекции программы в ходе разработки, т.е. увеличение объема работ за счет внесения изменений в алгоритм или программу по результатам уточнения постановок. В данном случае заказчик хорошо представлял себе, что он хочет получить, это не требовало многочисленных доработок. С учетом этого возьмем коэффициент равный 0,07.

Таким образом, условное количество команд в разрабатываемой программе:



Составляющие затрат труда рассчитываются по формулам:

;

;

;

;

,

где В - коэффициент увеличения затрат труда на изучение и постановку задачи вследствие их сложности и новизны (В = 1.2 - 3.0);

К=1 - коэффициент квалификации разработчика, определяется в зависимости от стажа работы и составляет:

- для работающих до двух лет - 0,8;

- от двух до трех лет - 1,0;

- от трех до пяти лет - 1,1 - 1,2;

- от пяти до семи - 1,3 - 1,4;

- свыше семи лет - 1,5 - 1,6.

Разработчик, которому было поручено это задание, имел опыт работы по специальности 2.5 года.

Цифры, находящиеся в знаменателях формул, характеризуют среднюю производительность труда программистов (число команд или операторов в час).

Таким образом, составляющие трудоемкости разрабатываемого ПП (чел.-час.):

;

;

;

;

;

Значение t_O примем равным 20 чел.-час.

Тогда общие затраты труда составляют:

t_ПП= 20 + 51.8 + 129.6 + 280.8 + 561.6 + 327.6 = 1319.6 чел.-час.

2.3 Календарное планирование

Календарное планирование создания ПП производится на основе данных о трудоемкости работ по его созданию.

Производственный цикл каждого этапа определяется по формуле:

;

где Т_Э - трудоемкость этапа, чел.-час.;

t_РД - продолжительность рабочего дня, ч. (t_РД = 8ч.);

q - количество работников одновременно участвующих в выполнении работ, чел.

Пересчет длительности производственного цикла, выраженной в человеко-часах, в календарные дни осуществляют умножением ее на коэффициент 1.4, т.е:

.

Произведем расчет длительности каждого этапа:

; ;

; ;

; ;

; ;

; ;

Результаты расчета и директивный график представлены в таблице 9.

Наименование этапов	Удельный вес, %	Трудоемкость этапа, чел.-час.	Количество исполнителей	Длительность этапа, кал. дни	Календарные дни
					30	60	90	120	150	180	210	240
изучение описания задачи	3.9	51.8	2	4.52
Разработка алгоритма	9.7	129.6	2	12.19
Составление программы	21.5	280.8	1	49.14
Отладка программы	41	561.6	1	98.3
Подготовка документации	23.9	327.6	1	57.33
Всего	100	1351.4		221.4

Таблица 9. Календарное планирование

2.4 Расчет заработной платы основного персонала

Заработная плата разработчиков программы рассчитывается на основе трудоемкости стадий работ. Часовые ставки определяются на основе должностных окладов разработчиков и разрядов работ (часовых тарифных ставок). Расчет заработной платы представлен в таблице 10.

№	Стадии (этапы)	Трудоемкость стадий, чел.-дн.	Исполнители	Днев. ставка руб.	Сред. днев. ставка руб.	З/п, руб.	З/п с уч. премий руб.
			Должность	Кол-во.
1	Подготовка описания и изучение задачи	5	программист	1	1000	1100	5500	7700
			ведущий специалист	1	1200
2	Разработка алгоритма	13	программист	1	1000	1100	14300	20020
			ведущий специалист	1	1200
3	Составление программы	49	программист	1	1000	1000	49000	68600
4	Отладка программы	98	программист	1	1000	1000	98000	137200
5	Подготовка документации	57	программист	1	1000	1000	57000	79800
	Всего	222					223800	313500

Таблица 10. Расчет заработной платы основного персонала

Премия составляет 40% от заработной платы. Заработная плата основного персонала рассчитана по формуле:

,

где k - количество этапов;

Т_Эi - трудоемкость i-го этапа;

- средняя часовая тарифная ставка оплаты труда работ i-го этапа.

2.5 Определение затрат на создание алгоритмов и ПП

Затраты на создание алгоритмов и ПП определяются по следующим статьям:

1. заработная плата основных исполнителей;

2. отчисления на социальные нужды;

3. накладные расходы;

4. прочие расходы.

Заработная плата основных исполнителей

Заработная плата основных исполнителей рассчитана в пункте 2.4 и, с учетом премий, составляет ЗП_П = 313500 р.

Отчисления на социальные службы

р.

Накладные расходы

,

р.

Прочие расходы

,

р.

Сводная таблица затрат

Затраты на создание алгоритмов и ПП сведены в таблицу 11.

№	Наименование статей затрат	Затраты, руб.	Удельный вес, %
1	Заработная плата основных исполнителей	315500	38
2	Отчисления на социальные нужды	106519	12.9
3	Накладные расходы	376200	45.3
4	Прочие расходы	31550	3.8
	Итого:	829769	100

Таблица 11. Структура затрат на создание алгоритмов и ПП

Цена предложения

Цена первоначально разработанных алгоритмов и ПП с учётом рентабельности разработки:

,

где З_ПП - затраты на создание алгоритмов и ПП;

ЗП_ПП - заработная плата основных исполнителей;

- рентабельность разработки ПП по отношению к оплате труда персонала, обеспечивающая безубыточную деятельность ( =200-400%; выберем значение - 250%)

Таким образом:

р.

2.6 Расчет экономической эффективности

Показатель годового экономического эффекта определяется по формуле:

,

где - годовые эксплуатационные затраты в информационной системе по базовому и новому варианту соответственно, руб.

Таким образом:

руб.

Для разрабатываемого ПП уровень экономической эффективности капиталовложений составляет:

,

.

Срок окупаемости затрат на создание алгоритмов и ПП определяется как величина, обратная Е_ПП:

2.7 Выводы

В данном разделе был проведен расчет затрат на разработку алгоритма муравья для решения задачи коммивояжера. На основании величины уровня экономической эффективности (Е_ПП=1.02), а также срока окупаемости затрат на создание алгоритма и ПП (около 11 месяцев) можно сделать вывод о том, что разработка и внедрение данного ПП являются экономически целесообразными и эффективными.



3. Охрана труда и окружающей среды

3.1 Введение

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

Характеристика технических средств.

В рабочем помещении размещены следующие технические средства:

1. Персональный компьютер, количество: 12.

Характеристики персонального компьютера предоставлены в таблице 12:

системный блок	U = 220 В, L = 35 дБ, P = 500 Вт
ЖК-монитор	U = 220 В, P = 35 Вт
клавиатура	U = 5 В, P = 1 Вт
манипулятор типа “мышь”	U = 5 В, P = 1 Вт

Таблица 12. Характеристики персонального компьютера.

2. Лазерный принтер, количество: 1.

Характеристики:

U = 220 В, L = 40 дБ:, P = 150 Вт.

3. Кондиционер, количество: 1.

Характеристики:

U = 220 В, L = 37-44 дБ:, P = 1550 Вт в режиме охлаждения, Р = 1420 Вт в режиме нагрева.

Характеристика помещения предоставлены в таблице 13:

Длина:	7 м
Ширина:	6 м
Высота:	3 м
Общая площадь комнаты:	42
Количество рабочих мест в помещении:	12
Площадь, приходящаяся на одного работника	3.5
Объем, приходящийся на одного работника	10.5

Таблица 13. Характеристика помещения

Естественное освещение осуществляется с помощью трех окон размером 1.5 х 2.5 .

Искусственное освещение осуществляется с помощью четырех светильников с четырьмя люминесцентными лампами.

Для поддержания благоприятных микроклиматических условий помещение оборудовано системой отопления и кондиционирования.

Анализ условий труда

Анализ условий труда будем осуществлять по следующей схеме:

Санитарно- гигиенические факторы:

Микроклимат

Освещение

Электробезосопасность

Шум

Вибрации

Электромагнитные излучения (ЭМИ)

Эргономика рабочего места

Психофизиологические факторы

Рассмотрим отдельно каждый из вредных факторов.



3.2. Санитарно- гигиенические факторы

3.2.1 Микроклимат

Вычислительная техника является источником существенных тепловыделений, что может привести к повышению температуры и снижению относительной влажности в помещении. Требования к микроклимату определяются ГОСТ 12.1.005-88 "Воздух рабочей зоны".

Работа по разработке алгоритма относится к категории Iа «Легкая физическая», т.к. работа производится сидя и не требует физического напряжения. Ниже, в таблице 14, приведены оптимальные параметры микроклимата согласно ГОСТ 12.1.005-88 «Воздух рабочей зоны».

Период года	Категория работ	Температура воздуха на рабочих местах	Относительная влажность	Скорость движения воздуха, м/с
Холодный	Легкая - I а	22-24	40 - 60	0,1
Теплый	Легкая - I а	23-25	40 - 60	0,1

Таблица 14. Оптимальные параметры микроклимата для помещений с ПЭВМ

Температура в помещении, в котором производится разработка алгоритма, составляет 23…24°С в теплый и 22…23°С в холодный периоды года. Относительная влажность - 45…60 %. Скорость движения воздуха - 0.08…0.1 м/с.

Для поддержания и контроля нормальных параметров микроклимата в рабочей зоне в холодное время применяют водяную систему отопления. В теплое время года применяется система кондиционирования воздуха, кондиционер AEG KWI 50i/KWA 50i.В данном кондиционере предусмотрены фильтры очистки воздуха, функция увлажнения воздуха и функция вентиляции.

Таким образом, параметры микроклимата помещения соответствуют допустимым параметрам ГОСТ 12.1.005-88.

3.2.2 Освещение

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

- естественное освещение, создаваемое непосредственно солнечным диском и диффузорным светом небесного излучения;

- искусственное освещение, источник - люминесцентные лампы или лампы накаливания;

- совмещенное (естественное и искусственное одновременно).

Чаще всего в рабочих помещениях используется совмещенное освещение.

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

В течение рабочего дня инженеру-программисту необходимо длительно концентрировать взгляд на экране монитора, в результате на инженера-программиста оказывается сильная зрительная нагрузка. Поэтому фактор освещённости является одним из главных производственных факторов, действующих на инженера-программиста. Требования к освещённости рабочего места для вычислительных центров (лабораторий) определяются по документу СНиП 23-05-95 «Естественное и искусственное освещение».

Для оператора ПЭВМ разряд и подразряд зрительной работы соответствует III г. Фон средний, контраст объекта с фоном высокий. В соответствии с вышеназванным документом норма освещенности работы такого рода должна быть равна 400 лк.

Искусственное освещение необходимо осуществлять в виде комбинированной системы с использованием люминесцентных источников света. Освещенность на поверхности стола в зоне размещения рабочего документа должна быть 300-500 лк. Допускается установка светильников местного освещения для подсветки документов. Местное освещение не должно создавать бликов на поверхности экрана и увеличивать освещенность экрана более 300 лк. Источники света необходимо равномерно распределять по комнате, компонуя их в сплошные или прерывистые линии.

Анализ освещенности на рабочем месте будет произведен ниже.

3.2.3 Электробезопасность

Электробезопасность обеспечивается в соответствии с ГОСТ 12.1.038 - 82 «Допустимые значения напряжения и токов».

Электрические установки, к которым относится практически все оборудование ПЭВМ, представляет для человека большую опасность. В частности, одним из источников опасности является электрическая часть, а именно входные цепи блока питания, который подключен к сети переменного тока напряжением 220В, частотой 50 Гц, с изолированной нейтралью. Выходные цепи блока питания составляют +/-15, +/-5 В. Используемое помещение с ПЭВМ относится к классу помещений без повышенной опасности с точки зрения поражения электрическим током. В помещении непроводящие полы, отсутствует токопроводящая пыль, электрически активная среда, возможность одновременного прикосновения к металлическим частям прибора и заземляющему устройству исключена, высокая температура и сырость отсутствует (согласно Правилам устройства электроустановок).

Пользователь должен выполнять общие требования по электробезопасности:

- не прикасаться к металлическим нетоковедущим частям системного блока ПЭВМ, которые могут оказаться под напряжением в результате повреждения изоляции;

- не использовать электрические приборы, такие как электрические плиты, чайники, обогреватели.

Так как все токоведущие части ПЭВМ в кабинете изолированы, то случайное прикосновение к ним исключено. Для обеспечения защиты от поражения электрическим током применяется заземление корпуса ПЭВМ подведением заземляющей жилы к питающим розеткам.

Уровень электробезопасности соответствует ГОСТ 12.1. 038. - 82.

3.2.4 Шум

Большое влияние на деятельность инженера-программиста оказывает уровень шума. Шум оказываем двоякое воздействие. С одной стороны, он непосредственно влияет на качество восприятия информации (сильный шум маскирует полезные звуковые сигналы). С другой стороны, шум косвенно влияет на работоспособность инженера-программиста, вызывая перестройку функционирования определенных физиологических систем организма.

Так, например, после шумового воздействия интенсивностью 120 дБ в течение одного часа требуется около пяти часов, чтобы вернулась к норме острота слуха. Шум вызывает также заметные сдвиги физиологических и психических функций. Воздействие шумом приводит к снижению скорости и точности сенсомоторных процессов, особенно страдают сложнокоординированные действия.

Под влиянием шума уменьшается скорость решения умственных задач и возрастает число ошибок, существенно снижается концентрация внимания.

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

Согласно ГОСТ 12.1.003 - 83 «Шум. Общие требования безопасности» на рабочих местах в помещениях для размещения шумных агрегатов вычислительных машин (АЦПУ, принтеры и др.) уровень шума не должен превышать 75 дБА.

Источниками шума на рабочем месте программиста являются: вентиляторы охлаждения ПК, жесткие диски, клавиатура, принтер, а также внешний шум с улицы. В помещениях с ПЭВМ снижение шума, создаваемого на рабочих местах, достигается двумя путями: ослаблением шума самих источников и проведением строительно-акустических мероприятий (изоляция источников шума, применение звукопоглощающих облицовок, экранирование рабочих мест и пр.). За счет современного оборудования уровень шума составляет примерно 35-40дБА, что соответствует допустимому значению.

3.2.5 Вибрация

Вибрации не должны превышать предельно допустимых значений, установленных ГОСТ 12.1.012-90 «Вибрационная безопасность. Общие требования». Уровень вибрации в помещениях вычислительных центров может быть снижен путем установки оборудования на специальные виброизоляторы.

Инженер-программист, работающий в вычислительном центре (лаборатории) за ПЭВМ, подвергается локальным вибрациям, создаваемыми вентиляторами в системном блоке, работой жесткого диска и устройства CD-ROM, передаваемыми ему через контакт с поверхностью стола. Уровень возможных вибраций от всех ПЭВМ, находящихся в помещении не превышает 10 дБ, тем самым удовлетворяет требованиям ГОСТ 12.1.012-90, в соответствии с которым, уровень локальных вибраций не должен превышать 75 дБ.

3.2.6 Электромагнитные излучения (ЭМИ)

Предельно - допустимые характеристики электромагнитного излучения определяются СанПиН 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» и дополнением СанПиН 2.2.2/2.4.2620-10, а также ГОСТом для ЖК-мониторов Р52324-2005 «Эргономические требования к работе с визуальными дисплеями, основанными на плоских панелях».

Основными составляющими частями персонального компьютера (ПК) являются: системный блок (процессор) и разнообразные устройства ввода/вывода информации: клавиатура, накопители, принтер, сканер и т.п. Каждый ПК включает средство визуального отображения информации, называемое по-разному: монитор, дисплей. ПК часто оснащаются сетевыми фильтрами (например, типа “Pilot”), источниками бесперебойного питания и другим вспомогательным электрооборудованием. Все эти элементы при работе ПК формируют сложную электромагнитную обстановку на рабочем месте пользователя (таблица 15)

Источник	Диапазон частот
Системный блок (процессор)	50 Гц - 1000 МГц
Устройства ввода/вывод информации	0 Гц, 50 Гц
Источник бесперебойного питания	50 Гц, 20 - 100 кГц

Таблица 15. ПК как источник ЭМП

Электромагнитные поля компьютера (особенно низкочастотные) оказывают определенное воздействие на человека. Установлено, что излучение низкой частоты в первую очередь негативно влияет на центральную нервную систему, вызывая головные боли, головокружение, стресс, тошноту, депрессию, бессонницу, отсутствие аппетита, стресс. Нервная система реагирует даже на кратковременные воздействия относительно слабых полей; изменяется гормональное состояние организма, нарушаются биотоки мозга. Особенно страдают от этого процессы обучения и запоминания.

При повышенном уровне напряженности полей следует сократить время работы за компьютером, делать пятнадцатиминутные перерывы в течение полутора часов работы и, конечно же, применять защитные экраны. Защитный экран, изготовляемый из мелкой сетки или стекла, собирает на себе электростатический заряд. Для снятия заряда экран монитора заземляют. На рабочем месте используются ЖК-мониторы, которые, в силу своей конструкции, не имеют мощных источников электрических и магнитных полей, поэтому их излучения значительно слабее, чем у обычных ЭЛТ-мониторов.

На рабочем месте установлены компьютеры, устройства ввода/вывода, источники бесперебойного питания и ЖК-мониторы, электромагнитные характеристики которых удовлетворяют требованиям СанПиН 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» и дополнению СанПиН 2.2.2/2.4.2620-10, а также ГОСТу Р52324-2005 «Эргономические требования к работе с визуальными дисплеями, основанными на плоских панелях».

3.2 Эргономика рабочего места

Требования к рабочему месту определяются в соответствии с ГОСТ 12.2.032-78 «Рабочее место при выполнении работ сидя. Общие эргономические требования», ГОСТ Р52324-2005«Эргономические требования к работе с визуальными дисплеями, основанными на плоских панелях», СанПиН 2.2.2/2.4.1340-03, «Гигиенические требования к персональным электронно-вычислительным машинам и организации работ» с дополнением СанПин 2.1.8/2.2.4.2620-10.

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

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

По условиям работы рабочее место программиста относится к индивидуальному рабочему месту для работы сидя.

Если рабочее место предназначено для работы как мужчин, так и женщин, то оптимальной является регулируемая высота рабочей поверхности в пределах670 - 700 мм, при отсутствии регулировки - 725 мм. Оптимальные размеры поверхности стола 1600 х 1000 . По форме она может быть прямоугольной, иметь вырез для корпуса работающего или углубление для клавиатуры. Под столом должно иметься пространство для ног с размерами по глубине 650 мм. Под столешницей рабочего стола предусматривается свободное пространство для ног размерами: по высоте - не менее 600 мм, по ширине - 500 мм, по глубине - 650 мм. Удаленность клавиатуры от переднего края стола до нижнего ряда клавиатура составляет 80-100 мм.

Рабочий стул программиста должен быть снабжен подъемно-поворотным механизмом. Высота сиденья должна регулироваться в пределах 400 - 550 мм, глубина в пределах 380 - 420 мм, а ширина - в пределах 400-450 мм. Высота верхней кромки спинки относительно сидения должна составлять 320 мм, ширина -360 - 400 мм. Угол наклона спинки стула к плоскости сиденья должен изменяться в пределах 95 - 110.

В данном помещении соблюдено оптимальное расположение оборудования, входящего в состав рабочего места. Обеспечено достаточное рабочее пространство, позволяющее выполнять все необходимые движения и перемещения согласно ГОСТ 12.2.032-78. Рабочее место соответствует характеристикам оптимального размещения предметов труда в зоне досягаемости рук программиста. Конструкции рабочих поверхностей соответствуют требованиям СанПиН 2.2.2/2.4.1340-03. Конструкция рабочего стола, рабочего стула обеспечивают оптимальное положение оператора в рациональной позе сидя. Высота сиденья регулируется в пределах 400-600 мм. ЖК-монитор соответствует требованиям ГОСТ Р52324-2005. Следовательно, можно сделать вывод о том, что в рабочем помещении выполняются требования к эргономике.

3.3 Психофизиологические факторы

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

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

Основными мерами по снижению физической и нервно-психической нагрузки являются следующие:

- Повышение уровня механизации и автоматизации трудоемких производственных процессов, использование современной высокопроизводительной техники;

- Совершенствование организации рабочих мест;

- Организация приемов и методов труда;

- Оптимизация темпа работы;

- Оптимизация режима труда и отдыха;

- Научно обоснованное установление норм обслуживания оборудования и норм времени его обслуживания с учетом объема информации, который работник может правильно воспринять, переработать и принять своевременное и правильное решение;

- Чередование работ, требующих участия разных анализаторов (слуха, зрения, осязания и др.);

- Чередования работ, требующих преимущественно умственных нагрузок с работами физическими;

- Чередование работ разной сложности и интенсивности;

- Оптимизация режимов труда и отдыха;

- Ритмизация труда (работа по графику с пониженной на 10-15% нагрузкой в первый и последний часы рабочей смены);

3.4. Расчет освещенности

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

Обычно искусственное освещение выполняется посредством электрических источников света двух видов: ламп накаливания и люминесцентных ламп. Будем использовать люминесцентные лампы, которые по сравнению с лампами накаливания имеют ряд существенных преимуществ:

- по спектральному составу света они близки к дневному, естественному свету;

- обладают более высоким КПД (в 1,5-2раза выше, чем КПД ламп накаливания);

- обладают повышенной светоотдачей (в 3-4 раза выше, чем у ламп накаливания);

- более длительный срок службы.

Расчет освещения производится для комнаты площадью 42 м², длиной 7 м и шириной 6 м.

Расчет освещения будем производить по методу коэффициента использования светового потока. Рассматриваемый метод позволяет производить расчет осветительной установки (ОУ) с учетом прямой и отраженной составляющих освещенности и применяется для расчета общего равномерного освещения горизонтальных поверхностей, равновеликих полу, при светильниках любого типа.