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

Для параллельного выполнения генетического алгоритма используем встроенные функции среды MATLAB, позволяющие распараллелить выполнение. Все эти функции входят в панель инструментов Parallel Computing Toolbox™ [9]. Данная панель инструментов позволяет использовать два подхода для решения параллельных задач.

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

обмен данными между ними.

Для включения режима pmode пользователю нужно ввести:

>> pmode start conf numlabs

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

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

Для простоты возьмем 4 подпопуляции. Обмен будет происходить каждые 20

поколений, согласно стратегии элитарности будут мигрировать 2 лучшие особи.

Таблица 2.5.3.1. – Сравнение эффективности решения задачи коммивояжера с помощью генетических алгоритмов

(с миграциями и без) с эффективными методами решения.

Количество	Генетический алгоритм без	Генетический алгоритм с
городов	миграций	миграциями
5	1,4274	1,4275
10	3,1710	3,17103
15	3,2266	3,2266
20	3,9634	3,9856
50	5,8946	5,8946
100	8,7381	8,7842
200	11,9872	12,0034
400	16,3385	16,3456
800	23,4532	23,5132
1600	33,2398	33,6429
3200	–	47,4307

Анализируя табл. 2.5.3.1 легко увидеть, что точность вычислений несколько ухудшается.

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

Таблица 2.5.3.2. – Сравнение времени решения задачи коммивояжера с помощью генетических алгоритмов (с миграциями и без) с эффективными методами решения.

Количество	Генетический алгоритм без	Генетический алгоритм с
городов	миграций	миграциями
5	82	22
10	1061	274
15	1532	382
20	2593	665
50	3812	954
100	6734	1785
200	25719	6241
400	145414	36749
800	480854	134628
1600	1465773	390526
3200	–	1268415

1600000
1400000
1200000
1000000	Генетический
800000	алгоритм без
	миграций
600000	Генетический
400000	алгоритм с
	миграцями
200000
0

Рисунок 2.5.3.1. – Сравнение зависимость времени выполнения генетического алгоритма с и без миграций.

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

табл. 2.5.3.4.). Настойки генетического алгоритма оставим прежними.

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

			Оптимизация	Оптимизация
	Исходное	Решение с	решения с	решения с
Количество		помощью	помощью	помощью
	полученное
городов		минимального	минимального	минимального
	решение
		остова	остова	остова
			(k = 3)	(k = 5)
5	1,4275	1,4275	1,4275	–
10	3,17103	3,1710	3,1710	3,1710
15	3,2266	3,2265	3,2265	3,2265
20	3,9856	3,4328	3,4328	3,4328
50	5,8946	5,8946	5,8946	5,8946
100	8,7842	7,5376	7,2316	7,2316
200	12,0034	10,1352	9,6252	9,6257
400	16,3456	14,6237	13,4672	13,4672
800	23,5132	19,7432	16,9965	16,9123
1600	33,6429	30,6541	27,4412	27,4412
3200	47,4307	45,8116	41,3276	41,3276
6400	–	62,4731	55,9865	55,9865
10000	–	70,7319	67,0552	67,0552

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

			Оптимизация	Оптимизация
		Решение с	решения с	решения с
Количество	Исходное время	помощью	помощью	помощью
городов		минимального	минимального	минимального
		остова	остова	остова
			(k = 3)	(k = 5)
5	22	0	0	–
10	274	0	0	0
15	382	0	0	0

	1400000
	1200000																Исходное время
	1000000
(мс)	800000
Время	600000																Решение с помощью
																	минимального остова
	400000
	200000																Оптимизация решения с
	0																помощью минимального
																	остова
	5	10	15	20	50	100	200	400	800	1600	3200		6400		10000
																	(k = 3)
				Количество городов

Рисунок 2.5.3.2. – График зависимости времени от числа городов для решения задачи коммивояжера.Набор данных – решение задачи, полученное с помощью эффективных способов.

Сравним так же для 400 городов время выполнения алгоритмов с миграциями и с варьирующимся количеством подпопуляций (рис. 16). Как видно из графика, ощутимый прирост дает уде разделение одной популяции на две, но затем эффективность от увеличения числа подпопуляций падает.

160000
140000
120000
100000
80000										Зависимость времени
										выполнения от числа
60000										подпопуляций
40000
20000
0
1	2	3	4	5		6		7		8

Рисунок 2.5.3.3. – Зависимость времени выполнения генетического алгоритма от числа подпопуляций.

4. ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ ПРОЕКТА

1. Выбор и обоснование методики расчёта экономической эффективности

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

Существует три основные группы методов, позволяющих определить эффект от внедрения:

• финансовые;

• качественные;

• вероятностные.

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

Часто применяются основные финансовые методы определения инвестиций в информационные технологии, такие как:

• NPV (Net present value) - чистый приведенный доход или чистая приведенная стоимость, это зависит от формулировки.

• IRR (Internal rate of return) - внутренняя норма доходности или внутренняя норма рентабельности, это тоже зависит от формулировки.

• Payback - срок окупаемости инвестиций.

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

2. Расчёт показателей экономической эффективности проекта

Методы оценки эффективности проекта предполагают необходимость оценки "доходной" и "затратной" части проекта.

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

• приобретение базового программного обеспечения: операционные системы, платформы БД;

• приобретение технических средств автоматизации;

• оплата услуг по проектированию и запуску системы в эксплуатацию;

• техническое сопровождение системы.

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

Внедрение автоматизированной системы не отразится на доходной части проекта, так как применение системы не даст прямого экономического эффекта.

К основным обобщающим показателям экономической эффективности относятся:

• годовой экономический эффект от разработки и внедрения автоматизированной системы;

• срок окупаемости автоматизированной системы;

• расчетный коэффициент эффективности капитальных затрат.

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

Годовой экономический эффект определяется по формуле:

Эг = C1-C2 (4.1.1)

Эг – годовой экономический эффект;

С1 – затраты, состоящие из затрат на оплату труда сотрудников, затрат на приобретение канцелярских принадлежностей, затрат на оплату коммунальных платежей, до внедрения автоматизированной системы;

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

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

E = Эг/КВ (4.1.2)

E – годовая экономическая эффективность;

Эг – годовой экономический эффект;

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

Срок окупаемости определяется по формуле:

Tок = 1/E (4.1.3)

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

E – годовая экономическая эффективность.

При расчете экономической эффективности системы в качестве базового варианта принят ручной метод обработки документации. Работу выполняют два человека: разработчик и тестостировщик. Заработная плата одного сотрудника в месяц составляет 140000 тг.

Затраты по оплате труда двух сотрудников составляют 280000 тг. в месяц. В год на заработную плату компания тратит: 280000 тг. * 12мес. = 3360000 тг.

Затраты на социальные отчисления составляют 5% от годовой заработной платы, т.е. 3360000 * 5% = 168000 тг.

Итого затраты на двух сотрудников составляют 3360000 + 168000 = 3528000 тг.

Затраты на канцелярские принадлежности – 5000 тг.

Затраты на оплату коммунальных платежей в месяц составляют 17000 тг. в месяц, с учетом того, что кВт/час стоит 15 тг. Затраты в год составляют 17000 тг. * 12 мес. = 204000 тг.

Наименование затрат	Годовые затраты, руб.
Затраты на оплату труда	3528000
Затраты на канцелярские принадлежности	5000
Затраты на оплату коммунальных платежей	204000
Итого C1	3737000

Таблица 3.1 Годовые затраты в базовом варианте

После разработки заработная плата одного сотрудника в месяц составляет 60000 тг. Затраты по оплате труда четырех сотрудников составляют 240000 в месяц. В год на заработную плату компания тратит: 240000 * 12 мес. = 2880000 тг.

Затраты на социальные отчисления составляют 5% от годовой заработной платы, т.е. 2880000 тг. * 5% = 144000 тг.

Итого затраты на двух сотрудников составляют 2880000 + 144000 = 3024000 тг.(3945600 тг.)

Затраты на канцелярские принадлежности – 4000 тг.

Затраты на обучение четырех сотрудников – 100000 тг.

Затраты на оплату коммунальных платежей останутся прежними.

Наименование затрат	Годовые затраты, руб.
Затраты на оплату труда	3024000
Затраты на канцелярские принадлежности и обучение персонала	104000
Затраты на оплату коммунальных платежей	204000
Итого C2	3332000

Таблица 3.2 Годовые затраты во внедряемом варианте

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

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

Зосн = Tоб * 3ср.д (4.1.4)

Зосн – основная заработная плата;

Tоб – общая трудоемкость проекта, дни;

Зср.д – заработная плата разработчиков в день.

Оплата труда разработчика составляет 120,000 тг.

Оплата в день 120000 / 22 = 5454 тг./день

Время разработки проекта составляет 20 дней. Значит Зосн = 20 * 5454 = 109080 тг.

Накладные расходы составляют 20% от основной заработной платы разработчиков. Накладные расходы = 109080 * 20% = 21816 тг. (Накладные расходы = 27270 * 25% = 6817,5.)

Затраты на инструментальные средства 10000 тг.

Капитальные вложения (КВ) = 109080 + 21816 + 10000 = 140896 тг.

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

Годовой экономический эффект:

Эг = С1 – С2

Эг = 3737000 – 3332000 = 405000 тг.

Годовая экономическая эффективность:

Е = Эг/КВ

Е = 405000/140896 = 2,87

Срок окупаемости:

Ток = 1/Е

Ток = 1/2,87 = 0,35 года.

Рассчитаем общую трудоемкость разработки по формуле:

T = nраб * t (4.1.5)

T – трудоемкость разработки, норм/час;

n – число разработчиков;

t – время в часах.

Разработчик работает по 5 часов 16 дней.

T = 1 * 16 * 5 = 80 норм/час.

Рассчитаем трудозатраты на составление отчетов до внедрения проекта и после. На составление отчетов вручную специалист затрачивал около 40 мин (0,6 чел/ч), а после внедрения проекта затрачиваемое время сократилось до 10 мин (0,16 чел/ч).

T = T0 – T1

T = 0,6 – 0,16 = 0,44 чел/ч.

Относительный индекс производительности труда вычисляется по формуле:

Jпт = T1/T0 (4.1.6)

Jпт – относительный индекс производительности труда;

T1 – затрачиваемое время после внедрения проекта;

T0 - затрачиваемое время до внедрения проекта.

Jпт = 0,16/0,6 = 0,26.

Для составления отчета при использовании автоматизированной системы, по сравнению с ручной обработкой данных, требуется только 26% рабочего времени. Следовательно, экономия времени на составление отчетов – 74%.

Данный проект имеет положительную экономическую эффективность и окупает затраты на производство автоматизированной информационной системы.

За счет уменьшения трудоемкости, появляется возможность получить годовой экономический эффект – 405000 тг. Срок окупаемости капитальных затрат составляет 0,35 года. Экономия времени на составление отчетов с использованием данного проекта составляет 74%.

5 ОХРАНА ТРУДА И ПРОМЫШЛЕННАЯ ЭКОЛОГИЯ

5.1 Характеристика производственного объекта

Тема моей дипломной работы « Генетические алгоритмы как способ оптимизаций ».

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

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

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

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

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

Для анализа условий труда был выбран Международный Университет Информационных Технологий. Здание университета состоит из 10 этажей, с общей площадью 8578 м2. Для рассмотрения выбран №610 кабинет. Общая площадь компьютерного кабинета составляет 30 м2, высота 2,5 м. оборудована двумя окнами. Перечень оснащенности аудитории техническим оборудованием: 20 рабочих мест, 20 персональных компьютеров (20 системных блоков, 20 мониторов, 20 клавиатур и 20 мышек), 1 камера и 1 кондиционер.

Условия рабочего помещения, внутренний микроклимат внутри рабочего помещения соответствуют Трудовому кодексу РК [1].