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

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

Содержание

Введение

Глава 1. Аналитическая часть

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

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

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

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

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

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

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

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

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

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

Глава 2. Проектная часть

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

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

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

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

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

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

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

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

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

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

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

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

. Охрана труда и промышленная экология

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

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

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

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

.2.3 Освещение

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

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

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

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

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

Заключение

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

Приложение

Введение

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

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

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

1. Аналитическая часть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция приспособленности так же получила свое название из генетики.

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

В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции.

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

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

.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). Данный оператор применяется достаточно редко, но основной его целью является попытка найти порядок генов, который имеет лучший эволюционный потенциал. Инверсия также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить хорошие множества значений генов, он также одновременно пробует находить хорошее упорядочения генов. Это гораздо более трудная задача для решения.