90362

Изучение генетических алгоритмов как способа оптимизации

Дипломная

Информатика, кибернетика и программирование

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

Русский

2015-06-04

1.04 MB

9 чел.

Содержание  

 

Введение

 

1.ГЛАВА 1. АНАЛИТИЧЕСКАЯ ЧАСТЬ

 

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

1.1.1. Описание генетических алгоритмов

1.2. Основные понятия генетических алгоритмов

1.3. Генетические операторы

1.4. Описание работы классического генетического алгоритма

1.4.1.  Генерация начальной популяции

1.4.2.Оценка популяции

1.4.3.  Проверка условия остановки

1.4.4.  Генерация новой популяции

1.5. Вывод наилучшей особи

 

2.ГЛАВА 2. ПРОЕКТНАЯ ЧАСТЬ

 

2.1. Применение генетических алгоритмов для решения задачи коммивояжера

2.1.1. Постановка задачи безусловной оптимизации

2.2. Ограничения при реализации генетических алгоритмов

2.3. Решение задачи коммивояжера с помощью генетического алгоритма

2.4. Реализация генетического алгоритма для решения задачи коммивояжера с использованием пакета MATLAB 7.5

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

2.5.1. Модель миграции генетических алгоритмов  

2.5.2. Островная модель генетических алгоритмов

 

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

 

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

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

 

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

 

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

5.2. Анализ опасных и вредных производственных факторов

5.2.1. Основные условия микроклимата в производственном помещении  

5.2.2.Шум и вибрация

5.2.3. Освещение

5.3. Мероприятия по технике безопасности во время работы

5.4. Мероприятия по технике безопасности в аварийных ситуациях

5.5. Расчеты подтверждающие или обеспечивающие безопасные условия труда

ЗАКЛЮЧЕНИЕ

 

ПЕРЕЧЕНЬ ПРИНЯТЫХ ТЕРМИНОВ, ПЕРЕЧЕНЬ СОКРАЩЕНИИ

 

СПИСОК ИСПОЛЗУЕМОЙ ЛИТЕРАТУРЫ

 

ПРИЛОЖЕНИЕ А. КОДИРОВАНИЕ ГРЕЯ

 

Введение

 

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

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

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

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

  1.  АНАЛИТИЧЕСКАЯ ЧАСТЬ

1.1 Генетические алгоритмы и традиционные способы оптимизации

1.1.1 Описание генетических алгоритмов

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

В 1975 г. вышла основополагающая книга Дж. Холланда (Holland) ―Адаптация в естественных и искусственных системах‖, в которой был предложен генетический алгоритм – алгоритм, основанный на принципах естественного отбора Ч.Дарвина.

Генетические алгоритмы относят к области мягких вычислений. Понятие «мягких вычислений» (Лофти Заде, 1994 г.) подразумевает под собой совокупность неточных, приближенных методов решения задач, зачастую не имеющих решение за полиномиальное время. Такие задачи возникают в области биологии, медицины, гуманитарных наук, менеджменте. Методы мягких вычислений хорошо дополняют друг друга, и часто используются совместно. В область мягких вычислений входят такие методы как:

- нечеткая логика;

- нейронные сети;

- вероятностные рассуждения;

- байесовские сети доверия1;

- эволюционные алгоритмы. [5]

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

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

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

Байесовские сети доверия – модель вероятностных и причинно-следственных отношений между переменными в статистическом информационном моделировании.

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

Целесообразность использования генетических алгоритмов изложена очень емко и кратко во фразе из статьи К. Де Йонга:

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

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

Генетические алгоритмы показывают блестящие результаты при решении сложных переборных задач (большинство из которых NP-полные, т.е. не решаются полным перебором за полиномиальное время), таких, например, как задача коммивояжера и поиск булевых термов.

1.2. Основные понятия генетических алгоритмов

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

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

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

Булев вектор  вектор, компоненты которого принимают значения из двух элементного (булева) множества значений, как правило {0, 1}.

Популяция  конечное множество особей.

Особь (индивидуум, организм) – набор хромосом с закодированными в них множествами параметров задачи, то есть решений, которые иначе называются точками в пространстве поиска (search points).

Хромосома  (цепочка  или  кодовая  последовательность)  –  это  вектор  генов.

Хромосома может быть представлена в виде булева вектора, полученного с помощью двоичного кодирования либо кода Грея (см. приложение А). Хромосома обозначается, как правило, A.

Ген (свойство, знак или детектор)  – атомарный элемент генотипа, в частности, хромосомы. Несет в себе наследственную информацию. Обозначается x.

Связь хромосомы и гена изображена на рисунке 1.

 

Рисунок 1.2.1 Распределение наследственной информации по длине хромосомы.

Генотип (структура) – набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в самом простом случае, генотип состоит из одной хромосомы).

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

Аллель  значение конкретного гена.

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

Множество позиций генов – локи.

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

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

составляющих множество потенциальных решений проблемы.

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

1.3. Генетические операторы

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

Оператор кроссинговера (кроссовера, скрещивания, рекомбинации)  оператор,при котором хромосомы обмениваются своими частями. Моделирует процесс скрещивания особей. Пусть  имеются  две  родительские  особи  с  хромосомами A и B. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой кроссинговера (crossover point), иногда она так же называется точкой разрыва. Описанный процесс изображен на рис. 1.3.1.

                           Рисунок 1.3.1 Одноточечный кроссинговер.

Данный тип кроссинговера называется одноточечным (single-point crossover), т.к. при нем родительские хромосомы «разрезаются» только в одной случайной точке. В двухточечноммноготочечном кроссинговере (multi-point crossover) вообще) кроссинговере хромосомы рассматриваются как циклы, которые формируются соединением концов линейной хромосомы. Для замены сегмента одного цикла сегментом другого цикла требуется выбор двух точек разрыва. В таком представлении, одноточечный кроссинговер может быть рассмотрен как двухточечный, но с одной точкой разреза, зафиксированной в начале строки. Следовательно, двухточечный кроссинговер решает ту же самую задачу, но более полно. В настоящий момент исследователи соглашаются, что двухточечный кроссинговер лучше, чем одноточечный. [7]

 

                             

                         Рисунок 1.3.2 Мутация хромосомы.

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

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

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

   (1.3.1)

где M – число бит в хромосоме.

Оператор инверсии (inversion)изменение порядка следования генов в хромосоме или ее фрагменте (рис. 4). Данный оператор применяется достаточно редко, но основной его целью является попытка найти порядок генов, который имеет лучший эволюционный потенциал. Инверсия также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить хорошие множества значений генов, он также одновременно пробует находить хорошее упорядочения генов. Это гораздо более трудная задача для решения.

 

                       

                                   Рисунок 1.3.3 Инверсия в хромосоме.

1.4. Описание работы классического генетического алгоритма

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

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

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

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

Имеется много способов реализации идеи биологической эволюции в рамках генетического алгоритма. Схема генетического алгоритма представлена на рис. 1.4.1.

Генерация

 Начальной 

популяции

 

     Оценка

                                                            популяции

Условие

Генерация новой

Нет

остановки

популяции

Да

Вывод

наилучшей особи

Рисунок 1.4.1 Схема работы классического генетического алгоритма.

Ниже подробнее рассмотрим шаги алгоритма.

1.4.1 Генерация начальной популяции

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

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

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

Для кодирования признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так, например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что значительно увеличивает размер поискового пространства. Одним из решений данной проблемы является использование кода Грея (см. приложение А). И, наоборот, для того чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующие этим признакам, то есть генотип объекта. Операция определения фенотипа объекта по его генотипу называется операцией декодирования или роста, то есть мы выращиваем фенотип из генотипа.

Таким образом,  для  того  чтобы  инициализировать  начальную  популяцию,

необходимо сначала определиться со способами кодирования особей. [3]

1.4.2 Оценка популяции

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

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

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

Таблица 1.4.2.1 Метод рулетки. Размер популяции = 5. Суммарная пригодность популяции = 200.

Особь

Пригодность

Вероятность выбора

Доля

Особь1

52

52/200 = 0.26

26%

Особь2

85

85/200 = 0.425

42.5%

Особь3

37

37/200 = 0.185

18.5%

Особь4

3

3/200 = 0.015

1.5%

Особь5

23

23/200 = 0.115

11.5%

Колесо рулетки

Особь5; 11,5%

Особь1; 26,0%

Особь4; 1,5%

Особь3; 18,5%

Особь2; 42,5%

Рисунок 1.4.2.1 – Оператор селекции типа колеса рулетки с пропорциональными функции приспособленности секторами

- Турнирная  селекция  (tournament  selection)    из  популяции,  состоящей  из  N

особей, создается группа из t (  ≥ 2) особей, выбранных случайным образом (рис. 1.4.2.1). Особь  с наибольшей  пригодностью в группе отбирается, остальные  – отбрасываются. Такая операция повторяется k раз. Затем отобранные особи используются для кроссинговера. Размер группы t часто равен 2, в таких случаях говорят о парных (двоичных)  турнирах  (binary  tournament).  Число  t  называется  численностью  турнира (tournament size).

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

- Отбор   усечением   (truncation   selection)   –   индивиды   сортируются 

(ранжируются) на основе их пригодности таким образом, чтобы    ≥   для   ≤ , т.е.

первым стоит наиболее приспособленный индивид. Число особей для скрещивания выбирается в соответствии с порогом T[0; 1]. Порог определяет, какая доля особей, начиная с самой первой (то есть самой приспособленной) будет принимать участие в отборе. Порог может быть задан и числом больше 1, тогда он будет равен числу особей из текущей популяции, допущенных к отбору. Среди особей, попавших "под порог", случайным образом N раз выбирается самая везучая, среди которых затем выбираются особи непосредственно для скрещивания.

Из-за того, что в этой стратегии используется отсортированная популяция, время еѐ работы может быть большим для популяций большого размера и зависеть также от алгоритма сортировки. [3]

1.4.3.  Проверка условия остановки

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

1.4.4.  Генерация новой популяции

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

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

- Стратегия элитарности (elitism strategy)  метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей и их потомков. Данный метод хорош с той точки зрения, что исключает «случайное блуждание по пространству поиска», поскольку осуществляется переход в следующее поколение самой лучшей особи (найденной на данном этапе поиска или ранее);

- Отбор с вытеснением (exclusion selection)  отбор, построенный на таком принципе, носит бикритериальный характер – то, будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие [2];

- Только потомки (детерминизм)  метод основан на построении новой популяции только из популяции потомков;

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

1.5.  Вывод наилучшей особи

Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается особь с наибольшим значением функции приспособленности.

Используя генетические операторы, схема генетического алгоритма будет выглядеть следующим образом [2]:

        

Рисунок 1.5.1 – Расширенная схема генетического алгоритма

2. ПРОЕКТНАЯ ЧАСТЬ

2.1. Применение генетического алгоритма для решения задачи коммивояжера

2.1.1. Постановка задачи безусловной оптимизации

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

2.2. Ограничения при реализации генетических алгоритмов

Суть  использования  генетических  алгоритмов  держится  на  трех  принципах:

кодирование, оценивание и воспроизводство, но с практической точки зрения имеют смысл иные качества, которые, однако, нисколько не отменяют основные параллели с эволюционными механизмами.

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

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

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

Основная цель   воспроизводства   –   получение   новых   вариантов   решений-

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

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

Так же важным параметром генетических алгоритмов является размер популяции.

При практической реализации возможны две крайности:

- слишком малый размер популяции (<10). Данный выбор в большинстве случаев годится только для очень простых задач. В противном случае будет наблюдаться быстрое вырождение популяции;

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

Исходя из данных рекомендаций, оптимальным размером популяции является 20-30 особей, однако в некоторых задачах требуется 50-100 особей. Исследования показывают, что размер популяции во многом зависит от размера хромосом. Так, для алгоритма с 32-битовыми хромосомами размер популяции будет больше, чем для алгоритма с 16-битовыми. [7]

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

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

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

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

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

- применение стратегии элитарности – позволяет гарантированно оставить в популяции наилучших особей;

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

2.3. Решение задачи коммивояжера с помощью генетического алгоритма

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

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

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

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

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

Пусть для простоты примера количество городов N = 8, тогда одной из возможных последовательностей городов будет путь, изображенный на рис. 2.3.1.

Город1

Город7 Город6

Город3 Город2

Город8 Город5

Город4

Рисунок 2.3.1. – Пример маршрута коммивояжера при обходе 8 городов

Закодируем  города  числами  от  1  до  8.  Тогда  тот  же  самый  путь  примет  вид:

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

= log2

(7)

Для  нашего  примера    = log2 8 = 3,  то  есть

для  кодирования  одного  гена

понадобиться 3 бита. Кодируем последовательность с помощью двоичного кодирования

(табл. 2.3.1):

Таблица 2.3.1 – Кодирование последовательности городов с помощью двоичного кодирования.

000

101

001

100

011

111

010

110

1

6

2

5

4

8

3

7

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

  1.  при случайной генерации начальной популяции может возникнуть хромосома, в которой будут повторяющиеся значения генов: 000 000 010

011 100 101 110 010.

  1.  хромосомы с повторяющимися генами может дать кроссинговер или мутация.

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

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

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

       2.4. Реализация генетического алгоритма для решения задачи коммивояжера с использованием пакета MATLAB 7.5

Пакет MALAB 7.5 предоставляет встроенную панель инструментов Genethic Algorithm and Direct Search Toolbox™, которая предназначена для расширенияфункциональных возможностей пакета генетическими алгоритмами. Работать с данной панелью инструментов можно двумя способами: с консоли или вызвав панель Genethic Algorithm Tool с помощью команды gatool. По сути, оба способа являются идентичными с той разницей, что используя панель Genethic Algorithm Tool, любые параметры генетического алгоритма настраиваются с использованием графической оболочки.

Рассмотрим встроенные функции для работы с генетическими алгоритмами [9]:

[x fval reason output population scores] =

 ga(@fitnessfun, nvars, options)  функция для нахождения минимума целевой функции; Входные параметры:  

 @fitnessfun – указатель функции в М-файле, по которой производится     расчет функции приспособленности;

 nvars – число независимых переменных для функции приспособленности;

 options – настраиваемые параметры генетического алгоритма; Выходные параметры:   x – конечная точка расчета;   fval – значение функции приспособленности в точке x; o reason – причина остановки алгоритма;    output – структура с информацией о эффективности работы алгоритма для  каждого выполненного поколения;

 population – состояние последнего семейства; o scores – конечное состояние;

 val = gaoptimget(options, ’Name’) – возвращает параметры используемого генетического алгоритма; Входные параметры:

 options – структура с параметрами генетического алгоритма;

 o ’Name’– имя параметра, значение которого нужно извлечь;

Выходные параметры:

 val – значение запрашиваемого параметра;

 options   =   gaoptimset(’param1’,   value1,   ’param2’,

 value2, ...) – устанавливает параметры генетического алгоритма;

Входные параметры:

 ’param1’ – имя параметра;

 value1  – устанавливаемое значение;

Выходные параметры:

 options – структура с параметрами генетического алгоритма.

Для решения задачи коммивояжера будем генерировать города случайным образом в отрезке [0, 1], при этом расстояния между городами подчиняются правилу треугольника.

Используя встроенные  функции  MATLAB,  реализуем  генетический  алгоритм  со следующими характеристиками и ограничениями:

  1.  Хромосома представлена в виде бинарного вектора;

  1.  Размер популяции – 50 особей;

  1.  Для расчета функции приспособленности используется стандартная функция travelling_salesman_fitness, принимающая в качестве аргумента хромосому (то есть одна из возможных перестановок городов) и возвращающая значение функции приспособленности для нее;

  1.  Кроссинговер: применяемая стратегия – генерация перестановок (используется стандартная функция crossover_permuation), вероятность кроссинговера

– 0.8;

  1.  Мутации: стратегия – так же применяется стандартная функция mutate_permutation, которая с определенной вероятностью генерирует перестановки в векторе пути, вероятность мутации – 0.2. Величина мутации такая большая, так как используется относительно небольшая популяция и велика вероятность попадания в локальный минимум;

  1.  Применяется стратегия элитарности; из каждой предыдущей популяции остается 2 наилучшие особи;

  1.  Критерием остановки выполнения алгоритма является сохранение значений функции приспособленности на протяжении 50 поколений (для количества городов >100), 1000 поколений (для 100 – 400 городов), 7500 поколений (>400 городов);

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

2 + 1, где k – шаг оптимизации, генерировались всевозможные перестановки, то есть вокруг города i генерировались перестановки в участке пути, в который входят города

−  … … +  . Количество перестановок тогда будет равно  2  − 1 ! .

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

Оптимизация

Оптимизация

Решение с

решения с

решения с

Количество

Точное

Генетический

помощью

помощью

помощью

городов

решение

алгоритм

минимального

минимального

минимального

остова

остова

остова

(k = 3)

(k = 5)

5

1,4274

1,4274

1,4608

1,4608

10

3,1710

3,1710

3,5153

3,1710

3,1710

15

3,2265

3,2266

3,3323

3,2265

3,2265

20

3,9634

5,5095

4,7750

4,7750

50

5,8946

7,9498

6,6888

6,2239

100

8,7381

10,790

10,051

9,3428

200

11,9872

15,1465

13,7863

12,8208

400

16,3385

20,6697

18,8074

17,4822

800

23,4532

29,5846

27,0346

25,5666

1600

33,2398

41,2549

37,8895

35,2624

3200

58,0455

53,1781

49,6798

6400

81,5697

75,82

72,8593

10000

101,539

93,6233

89,4984

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

Количество

Точное

Генетический

Решение с

Оптимизация

Оптимизация

городов

решение

алгоритм

помощью

решения с

решения с

минимального

помощью

помощью

остова

минимального

минимального

остова

остова

(k = 3)

(k = 5)

1

2

3

4

5

6

5

0

82

0

0

10

15

1061

0

0

50

15

12750

1532

0

0

421

20

2593

0

0

968

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

1

2

3

4

5

6

50

3812

0

15

1921

100

6734

0

15

6890

200

25719

0

46

13761

400

145414

31

93

21906

800

480854

78

156

49218

1600

1465773

343

617

93233

3200

1343

2089

189639

6400

6343

7456

386234

10000

26781

30421

586580

 

Анализируя табл. 2.4.2 и табл. 2.4.3, очевидно, что генетический алгоритм находит более точное решение по сравнению с решением задачи с помощью минимального остова даже с оптимизацией. Однако при решении задачи коммивояжера с помощью генетического алгоритма возникает ряд проблем – нужно менять условие остановки алгоритма в зависимости от числа городов, поскольку генетические алгоритмы имеют относительно плохую сходимость при большой длине хромосомы; так же генетические алгоритмы имеют не очень хорошие показатели по времени (рис. 2.4.1.).

1600000

1400000

1200000

)

1000000

(мс

Время

800000

600000

400000

200000

0

5

10

15

20

50

100

200

400

800

1600

3200

6400

10000

Количество городов

 

Точное решение

Генетический алгоритм

Решение с помощью минимального остова

Решение с помощью минимального остова (оптимизированное k = 3)

Решение с помощью минимального остова (оптимизированное k = 5


Согласно исследованиям генетические алгоритмы имеют трудоемкость в среднем

 

O(nт), где n  длина хромосомы (то есть количество городов), m – отражает влияние размера популяции и вероятностей генетических операторов. Узким местом генетических алгоритмов является многократное вычисление значения функции приспособленности.

Количество вычислений равняется:

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

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

Оптимизация

Оптимизация

Исходное

Решение с

решения с

решения с

Количество

помощью

помощью

помощью

полученное

городов

минимального

минимального

минимального

решение

остова

остова

остова

(k = 3)

(k = 5)

5

1,4274

1,4608

1,4608

10

3,1710

3,1710

3,1710

3,1710

15

3,2266

3,2265

3,2265

3,2265

20

3,9634

3,4328

3,4328

3,4328

50

5,8946

5,8946

5,8946

5,8946

100

8,7381

7,8422

7,5621

7,5621

200

11,9872

11,3452

10,0232

10,0232

400

16,3385

15,5464

14,6119

14,6119

800

23,4532

21,6932

19,7432

19,7432

1600

33,2398

35,0656

30,6541

30,6541

3200

45,8116

41,3276

41,3276

6400

65,3527

65,3527

10000

76,3488

76,3488

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

Оптимизация

Оптимизация

Решение с

решения с

решения с

Количество

Исходное время

помощью

помощью

помощью

городов

минимального

минимального

минимального

остова

остова

остова

(k = 3)

(k = 5)

5

82

0

0

10

1061

0

0

0

15

1532

0

0

0

20

2593

15

15

15

50

3812

93

76

76

100

6734

532

129

114

200

25719

1630

467

321

400

145414

5907

1945

1095

800

480854

37890

37436

35340

1600

1465773

108423

96790

93827

3200

245906

254242

252352

6400

1035621

676432

650936

10000

1356214

1295308

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

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

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

         2.5. Развитие генетических алгоритмов в сторону модели с несколькими

        взаимодействующими популяциями

        2.5.1. Модель миграции генетических алгоритмов

 

Генетические алгоритмы применяются и при параллельных вычислениях (parallel implementations).

Первым  подходом  является  распараллеливание  отдельных  шагов  алгоритма:

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

Однако, такой подход не очень удобен в программировании.

Наиболее часто применимой является модель миграции (Migration). Модель миграции представляет популяцию как множество подпопуляций. Каждая подпопуляция обрабатывается отдельным процессором. Эти подпопуляции развиваются независимо друг от друга в течение одинакового количества поколений T (время изоляции). По истечении времени изоляции происходит обмен особями между популяциями (миграция, "воровство невест"). Количество особей, подвергшихся обмену (вероятность миграции), метод отбора особей для миграции и схема миграции определяет частоту возникновения генетического многообразия в подпопуляциях и обмен информацией между подпопуляциями.

Отбор особей для миграции может проходить следующим образом:

  •  случайная однообразная выборка из числа особей;

  •  пропорциональный отбор: для миграции берутся наиболее пригодные особи.

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

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

Рисунок 2.5.1.1 – Миграция с топологией полной сети

Другая основная миграционная схема имеет топологию кольца (рис. 2.5.1.2.). Здесь особи передаются между соседними (по направлению обхода) популяциями. Таким образом, особи из одной подпопуляции могут мигрировать только в одну – соседнюю популяцию.

Рисунок 2.5.1.2. – Миграция с топологией кольца

Существует стратегия миграции, объединяющая первую и вторую модель, так же она позволяет разрешить коллизии первой модели. Как и при топологии кольца, миграция осуществляется только между ближайшими соседями, однако миграция в этой модели так же возможна между "крайними" подпопуляциями (тороидальные краевые миграции). [7]

        2.5.2. Островная модель генетических алгоритмов

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

Такие миграции позволяют подпопуляциям совместно использовать генетический материал.

Пусть выполняются 16 независимых генетических алгоритмов, используя подпопуляции из 100 особей в каждой. Если миграции нет, то происходит 16 независимых поисков решения. Все поиски ведутся на различных начальных популяциях и сходятся к определенным особям. Исследования подтверждают, что генетический дрейф склонен приводить подпопуляции к различным доминирующим особям. Это связано с тем, что, во-первых, количество островов, принимающих доминирующих "эмигрантов" с острова ограничено (2-5 островов). Во-вторых, обмен особями односторонен. Поэтому в большой популяции появляться группы островов с различными доминирующими особями. Если популяция имеет небольшой размер, то возможно быстрое мигрирование ложных доминирующих особей.

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

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

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

рассматриваемой модели с каждого острова миграции могут происходить лишь на определенное расстояние: 2-5 остовов в зависимости от количества популяций. Таким образом, каждый остров оказывается почти изолированным. Количество островов, на которые могут мигрировать особи одной подпопуляции, называют расстоянием изоляции.

Следует заметить, что в такой модели взаимомиграции исключены.

Рисунок 2.5.2.1. – Островная модель генетических алгоритмов

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

        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 - срок окупаемости инвестиций.

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

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

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

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

  •  приобретение базового программного обеспечения: операционные системы, платформы БД;
  •  приобретение технических средств автоматизации;
  •  оплата услуг по проектированию и запуску системы в эксплуатацию;
  •  техническое сопровождение системы.

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

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

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

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

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

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

                                           Эг = 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].

5.2 Анализ опасных и вредных производственных факторов

Опасные и вредные производственные факторы по природе возникновения делятся на следующие группы:

- физические;

- химические;

- психофизиологические;

- биологические.

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

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

- чрезмерная запыленность и загазованность воздуха;

- повышенная и пониженная влажность воздуха;

- недостаточная освещенность рабочего места;

- превышающий допустимые нормы шум;

- повышенный уровень ионизирующего излучения;

- повышенный уровень электромагнитных полей;

- повышенный уровень статического электричества;

- опасность поражения электрическим током;

- блеклость экрана дисплея.

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

Биологические вредные производственные факторы в данном помещении отсутствуют.

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

- нервно-эмоциональные перегрузки;

- умственное напряжение;

- перенапряжение зрительного анализатора.

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

5.2.1 Основные условия микроклимата в производственном помещении

Микроклимат производственных помещений — это климат внутренней среды этих помещений, который определяется действующими на организм человека сочетаниями температуры, влажности и скорости движения воздуха.

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

5.2.2. Шум и вибрация

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

Согласно ГОСТ 12.1.003-76 ССБТ эквивалентный уровень звука не должен превышать 50 дБА. Для того, чтобы добиться этого уровня шума рекомендуется применять звукопоглощающее покрытие стен.

В качестве мер по снижению шума можно предложить следующее:

- облицовка потолка и стен звукопоглощающим материалом (снижает шум на 6 – 8 дб);

- экранирование рабочего места (постановкой перегородок, диафрагм);

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

- рациональная планировка помещения.

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

Защиту от шума следует выполнять в соответствии с ГОСТ 12.1.003-76, а звукоизоляция ограждающих конструкций должна отвечать требованиям главы СНиП 11-12-77 “Защита от шума. Нормы проектирования”.

Все потенциально опасные и вредные производственные факторы учтены и нейтрализованы, согласно cанитарным правилам «Санитарно-эпидемиологические требования к обеспечению радиационной безопасности» [4].

5.2.3 Освещение

Работа, выполняемая с использованием вычислительной техники, имеют следующие недостатки:

- вероятность появления прямой блесткости;

- ухудшенная контрастность между изображением и фоном;

- отражение экрана.

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

Размещение светильников определяется следующими размерами: Н = 3 м —  высота помещения, hc = 0,25 м — расстояние светильников от перекрытия, hп = H - hc = 3 - 0,25 = 2,75 м — высота светильников над полом, hp = высота расчетной поверхности = 0,7 м (для помещений, связанных с работой ПЭВМ), h = hп - hp = 2,75 - 0,7 = 2,05 — расчетная высота.

Светильника типа ЛДР (2х40 Вт). Длина 1,24 м, ширина 0,27 м, высота 0,10 м.

L — расстояние между соседними светильниками (рядами люминесцентных светильников), Lа (по длине помещения) = 1,76 м, Lв (по ширине помещения) = 3 м.

l — расстояние от крайних светильников или рядов светильников до стены, l = 0,3 - 0,5L, lа = 0,5La, lв = 0,3Lв, la = 0,88 м., lв = 0,73 м.

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

Метод коэффициента использования светового потока предназначен для расчета общего равномерного освещения горизонтальных поверхностей при отсутствии крупных затемняющих предметов. Потребный поток ламп в каждом светильнике: Ф = Е * r * S * z / N * h, где Е — заданная минимальная освещенность = 300 лк., т. к. разряд зрительных работ = 3, r — коэффициент запаса = 1,3 (для помещений, связанных с работой ПЭВМ), S — освещаемая площадь = 30 м2, z —  характеризует неравномерное освещение, z = Еср / Еmin — зависит от отношения l = L/h , l a = La/h = 0,6, l в = Lв/h = 1,5. Т. к. l превышают допустимых значений, то z = 1,1 (для люминесцентных ламп).

N — число светильников, намечаемое до расчета. Первоначально намечается число рядов n, которое подставляется вместо N. Тогда Ф — поток ламп одного ряда.

N = Ф/Ф1, где Ф1 — поток ламп в каждом светильнике.

h — коэффициент использования. Для его нахождения выбирают индекс помещения i и предположительно оцениваются коэффициенты отражения поверхностей помещения r пот. (потолка) = 70 %, r ст. (стены) = 50 %, r р. (пола) = 30 %. Ф = 300 * 1,3 * 25 * 1,1 / 2 * 0,3 = 21450 лм.

Я предлагаю установить два светильника в ряд. Светильники вмещаются в ряд, так как длина ряда около 4 м. Применяем светильники с лампами 2х40 Вт с общим потоком 5700 лм. Схема расположения светильников представлена на рисунке 5.2.2.1

Рис. 5.2.3.1 - Схема расположения светильников

5.2.4 Электромагнитное и ионизирующее излучения

Большинство ученых считают, что как кратковременное, так и длительное воздействие всех видов излучения от экрана монитора не опасно для здоровья персонала, обслуживающего компьютеры. Однако исчерпывающих данных относительно опасности воздействия излучения от мониторов на работающих с компьютерами не существует и исследования в этом направлении продолжаются [4].

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

Максимальный уровень рентгеновского излучения на рабочем месте оператора компьютера обычно не превышает 10мкбэр/ч, а интенсивность ультрафиолетового и инфракрасного излучений от экрана монитора лежит в пределах 10…100мВт/м2.

Таблица. Допустимые значения параметров неионизирующих электромагнитных излучений (в соответствии с СанПиН 2.2.2.542-96)

Наименование параметра

Допустимые значения

Напряженность электрической составляющей электромагнитного

поля на расстоянии 50см от поверхности видеомонитора

10В/м

Напряженность магнитной составляющей электромагнитного

поля на расстоянии 50см от поверхности видеомонитора

0,3А/м

Напряженность электростатического поля не должна превышать:

для взрослых пользователей

для детей дошкольных учреждений и учащихся

средних специальных и высших учебных заведений

20кВ/м

15кВ/м

Для снижения воздействия этих видов излучения рекомендуется применять мониторы с пониженным уровнем излучения (MPR-II, TCO-92, TCO-99), устанавливать защитные экраны, а также соблюдать регламентированные режимы труда и отдыха.

5.3 Мероприятия по технике безопасности во время работы

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

Расположение оргтехники:

- системный блок – помещается на надежную поверхность  (крепкий стол, массивная подставка/тумба) – так, чтобы исключать даже случайное его сотрясение;

- дисплей необходимо устанавливать на такой высоте, чтобы центр экрана был на 15-20 см ниже уровня глаз. Расстояние от глаз до экрана – не менее 50 см;

- клавиатура располагается на расстоянии 15-30 см от края столешницы или на специальной выдвижной доске.

Не рекомендуется установка компьютера (и клавиатуры) на поверхность, которая создает блики и легко «собирает» статическое электричество (оргстекло, полированная и покрытая лаком доска).

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

Рабочая мебель:

- кресло – ширина и глубина сиденья не менее 40см.; спинка: высота опорной поверхности 30±2 см; ширина не менее 38 см.; подлокотники: длина не менее 25 см; ширина 5-7 см., высота над сиденьем 23+3 см.;

- стол – размеры рабочей поверхности (столешницы): длина – 80-120 см; ширина – 80-100 см.; высота (расстояние от пола до рабочей поверхности) 68-85 см; оптимальная высота 72,5 см.;

- подставки – для рук: опорная планка для запястья («подзапястник») - плоская или изогнутая пластина из мягкого материала; помещается перед клавиатурой. Для ног: ширина не менее 30 см; длина (глубина) не менее 40 см.

Помещение:

-площадь одного рабочего места с компьютером - не менее 6 м2;

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

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

Рабочая поза

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

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

Чтобы не травмировать позвоночник, важно:

- избегать резких движений;

- поднимаясь/садясь, держать голову и торс прямо.

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

Положение рук и ног

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

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

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

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

Дыхание и расслабление мышц

Во время работы за компьютером необходимо:

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

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

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

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

При ощущении усталости глаз нужно в течение 2-3 мин окинуть взглядом комнату, устремлять взгляд на разные предметы, смотреть вдаль (в окно).

Если резко возникло общее утомление, появилось дрожание изображения на экране дисплея (покачивание, подергивание, рябь), следует сообщить об этом руководителю.

5.4 Мероприятия по технике безопасности в аварийных ситуациях

Обеспечение пожарной безопасности организации должно осуществляться в соответствии с Законом Республики Казахстан «О пожарной безопасности», «Правилами пожарной безопасности в Республике Казахстан», СНиП, ГОСТ и другими нормативными правовыми актами Республики Казахстан, а также приказами и распоряжениями Работодателя [закон гражданской зашиты РК]

  5.4.1 Требования пожарной безопасности к помещениям

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

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

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

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

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

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

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

Устройства для само закрывания дверей необходимо содержать в исправном состоянии. Не допускается устанавливать какие-либо приспособления, препятствующие свободному закрыванию противопожарных или против дымных дверей (устройств).

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

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

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

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

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

При аренде помещений арендаторами выполняются противопожарные требования норм для данного типа зданий.

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

5.5 Расчеты, подтверждающие или обеспечивающие безопасные условия труда

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

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

Скорость звука в воздухе при нормальной температуре составляет приблизительно 340 м/с,

в воде –1 430 м/с, в алмазе — 18 000 м/с.

Звук с частотой от 16 Гц до 20 кГц называется слышимый, с частотой менее 16 Гц — инфразвук и более 20 кГц — ультразвук.

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

Интенсивность звука — это количество звуковой энергии, передаваемой звуковой волной за 1 с через площадку 1 м 2, перпендикулярную направлению распространения звука, Вт/м2.

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

Шум воспринимается весьма субъективно. При этом имеет значение конкретная ситуация, состояние здоровья, настроение, окружающая обстановка.

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

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

Таблица 5.5.1

Уровни звукового давления, дБ

Среднегеометрические частоты октавных полос, Гц

Уровни звука, эквивалентные уровни звука, дБА

86

31.5

71

63

61

125

50

54

500

49

1000

45

2000

40

4000

38

8000

50

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

Для решения вопросов о необходимости и целесообразности снижения шума необходимо знать уровни шума на рабочем месте оператора.

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

где Li – уровень звукового давления i-го источника шума;

n – количество источников шума.

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

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

Таблица 5.5.2  Уровни звукового давления различных источников.

Источник шума

Уровень шума, дБ

Жесткий диск

40

Вентилятор

45

Монитор

17

Клавиатура

10

Принтер

45

Сканер

42

Обычно рабочее место оператора оснащено следующим оборудованием: винчестер в системном блоке, вентилятор(ы) систем охлаждения ПК, монитор, клавиатура, принтер и сканер.

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

L=10·lg(104+104,5+101,7+101+104,5+104,2)=49,5 дБ

Полученное значение не превышает допустимый уровень шума для рабочего места оператора, равный 65 дБ (ГОСТ 12.1.003-83)[2]. И если учесть, что вряд ли такие периферийные устройства как сканер и принтер будут использоваться одновременно, то эта цифра будет еще ниже. Кроме того при работе принтера непосредственное присутствие оператора необязательно, т.к. принтер снабжен механизмом автоподачи листов.

Заключение

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

  1.  генетические алгоритмы являются эффективным средством оптимизации, но не самым быстрым;

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

  1.  генетические алгоритмы отлично поддаются распараллеливанию, для этого существует ряд моделей, например, островная модель;

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

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

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

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

Список использованных источников и литературы

  1.  Батищев Д. И., Неймарк Е. А., Старостин Н. В. Применение генетических алгоритмов к решению задач дискретной оптимизации / Д. И. Батищев, Е. А. Неймарк, Н. В. Старостин. – Н. Новгород: 2007. – 85 с.

  1.  Вороновский Г. К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г. К. Вороновский. – Х.: Основа, 1997. – 112 с.

  1.  Генетические алгоритмы [Электронный ресурс] // Генетические алгоритмы и не только. – Электрон. дан. – [б.м.], 2003-2007. - URL: http://qai.narod.ru/GA/ (Дата обращения: 01.06.2010).

  1.  Генетические  алгоритмы:  почему  они  работают?  Когда  их  применять? [Электронный ресурс] // Комптьютерра Online. – Электрон. дан. – [б.м.], 1997 – 2010. –                                URL: http://www.computerra.ru/offline/1999/289/2523/ (Дата обращения: 01.06.2010).

  1.  Мягкие вычисления [Электронный ресурс] // Википедия свободная энциклопедия. – Электрон. дан. – [б.м.], 2001-2010.- URL: http://ru.wikipedia.org/wiki/Мягкие_вычисления (Дата обращения: 01.06.2010). 

  1.  Рутковская   Д.,   Пилиньский   М.,   Рутковский   Л.   Нейронные   сети,

        генетические  алгоритмы  и  нечеткие  системы  /  Д.  Рутковская.  

         Рутковский; пер. с польск. И. Д. Рудинского. – М: Горячая линия, 2006.

  1.  Панченко Т. В. Генетические алгоритмы: учебно-методическое пособие /

         Т.В. Панченко. – Астрахань: Изд. дом «Астраханский университет», 2007.

  1.  De Jong, K.A. Introduction to the second special issue on genetic algorithms. / K.A. De Jong. – Machine Learning, 5(4). – p. 351-353.

  1.  Parallel Computing Toolbox User’s Guide. – MathWorks Inc., 2010. – 665 p.

  1.  Трудовой кодекс Республики Казахстан. Астана, Акорда, 15 мая 2007 года № 251-III ЗРК (с изменениями и дополнениями по состоянию на 17.01.2014).

   

  1.  Санитарные правила «Санитарно-эпидемиологические требования к обеспечению радиационной безопасности», утвержденные Правительством Республики Казахстан от 3 февраля 2012 года № 202.

  1.  Закон Республики Казахстан «О пожарной безопасности» от 22 ноября 1996 года № 48-I

        (с изменениями и дополнениями по состоянию на 13.01.2014 г.)

  1.  Санитарные правила «Санитарно-эпидемиологические требования к условиям работы с источниками физических факторов (компьютеры и видеотерминалы), оказывающие воздействие на человека», утвержденные приказом Министра здравоохранения Республики Казахстан от 1 декабря 2011 года № 1430.

  1.  Санитарные правила «Санитарно-эпидемиологические требования к эксплуатации и персональных компьютеров, видеотерминалов и условиям работы с ними», утвержденные приказом Министра здравоохранения Республики Казахстан от 25 апреля 2011 года № 217.

Приложение А. Кодирование Грея

Код Грея  непозиционный код с одним набором символов (0 и 1) для каждого разряда. Таким образом, в отличие от римской системы счисления число в коде Грея не является суммой цифр. Чтобы показать соответствие последовательности чисел коду Грея можно воспользоваться таблицей (табл. 11), но есть и наглядное правило построения этой последовательности.

Младший разряд в последовательности чисел в коде Грея принимает значения 0

или 1, затем следующий старший разряд становится единичным и младший разряд принимает свои значения уже в обратном порядке (1, 0). Этим объясняется название кода

– отраженный. Соответственно, два младших разряда принимают значения 00, 01, 11, 10, а

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

Таблица  – Числа в коде Грея и в двоичном коде

Таблица 11 – Числа в коде Грея и в двоичном коде

Число

Двоичный код

Код Грея

0

000

000

1

001

001

2

010

011

3

011

010

4

100

110

5

101

111

6

110

101

7

111

100

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

PAGE   \* MERGEFORMAT 1


 

А также другие работы, которые могут Вас заинтересовать

58359. Надёжная защита организма 60.5 KB
  Как вы думаете почему сплошной слой краски так повлиял на мальчика понизилась температура тела кожа не могла дышать поры были закрыты краской Какой орган мы будем изучать сегодня Орган осязания кожу. Какая кожа На доске карточки.
58360. Строение тела человека 60.5 KB
  Цель урока: Дать первоначальные сведения о работе внутренних органов человека. Задачи урока: обучающие: ввести понятие «внешнее» и «внутреннее» строение тела человека; познакомить с частями и внутренними органами человека...
58361. Урок Памяти, посвященный празднованию 65-летней годовщине Великой Победы 52.5 KB
  О Великой Отечественной войне; нарисовать рисунок на военную тематику; поинтересоваться у родителей бабушек дедушек об участии родственников в войне а по возможности найти и принести на урок фотографии того времени. Выставку подборку книг о войне так же можно составить с помощью детей.
58363. Урок письма 79.5 KB
  С этим трудно спорить но скажите вы любите получать письма от родных и близких Вам нравится их читать А чего не хватает коротким электронным сообщениям или мобильным звонкам Им не хватает теплоты душевности ведь когда читаешь письмо словно разговариваешь с близким тебе человеком.
58365. Свойства равнобедренного треугольника 1.51 MB
  Организационный момент Учитель: Здравствуйте ребята Сегодня на уроке мы совершим путешествие в Страну Треугольников. Остров высказываний Учитель: Мы только начали изучать великую страну Геометрия ее законы и обычаи. Учитель раздает карточки учащимся.
58366. Природа и люди Древней Индии 100.5 KB
  Учащиеся должны знать: географическое положение природные условия занятия религиозные верования жителей Индии. Стадия вызова: На доске иллюстрации по Индии и звучит музыка. Ребята как вы думаете что объединяет эту музыку и иллюстрации которые вы увидели...