Материал: Генетический алгоритм как метод оптимизации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.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. - Сравнение эффективности решения задачи коммивояжера с помощью генетических алгоритмов (с миграциями и без) с эффективными методами решения.

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

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

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

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

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

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

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

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

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

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

3. Экономическое обоснование проекта

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

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

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

          финансовые;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эг = C1-C2 (4.1.1)

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

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

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

= Эг/КВ (4.1.2)

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

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

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

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

Tок = 1/E (4.1.3)

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

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

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