Решение задач на тему: Генетические алгоритмы поиска глобального экстремума

Введение

Как известно, оптимизационные задачи заключаются в нахождении минимума или максимума целевой функции. Как правило, целевая функция - сложная функция, зависящая от некоторых входных параметров. В оптимизационной задаче требуется найти значения входных параметров, при которых целевая функция достигает минимального или максимального значения. Для этого существует целый класс оптимизационных методов, которые можно условно разделить на методы, использующие понятие производной (градиентные методы) и стохастические методы (методы, основанные на получении большого числа реализаций стохастического (случайного) процесса). С их помощью можно найти экстремальное значение целевой функции, но не всегда можно быть уверенным, что получено значение глобального экстремума. Нахождение локального экстремума вместо глобального называется преждевременной сходимостью. Для решения этой проблемы и проводится поиск новых оптимизационных алгоритмов. Предложенные сравнительно недавно - в 1975 году в Мичиганском университете Джоном Холландом (John Holland) генетические алгоритмы (ГА) основаны на принципах естественного отбора Ч. Дарвина и относятся к стохастическим методам.

Изначально новый алгоритм получил название "репродуктивный план Холланда" и в дальнейшем активно использовался в качестве базового алгоритма в эволюционных вычислениях. Идеи Холланда развили его ученики Кеннет Де Йонг (Kenneth Dе Jong) из университета Джорджа Мейсона (Вирджиния) и Дэвид Голдберг (David Е. Goldberg) из лаборатории ГА Иллинойса. Благодаря им, был создан классический ГА, описаны все операторы и исследовано поведение группы тестовых функций (именно алгоритм Голдберга и получил название "генетический алгоритм").

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

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

генетический оператор алгоритм функция

Оглавление

- Введение

- Эволюционные процессы в природе

- Принцип работы генетического алгоритма

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

- Операторы выбора родителей

- Рекомбинация воспроизведение

- Мутация

- Операторы отбора особей в новую популяцию

- Разнообразие генетических алгоритмов

- Модели параллельных генетических алгоритмов

- Модернизация генетических алгоритмов Заключение

- Список литературы

Заключение

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

Преимущества генетических алгоритмов:

не требуют никакой информации о поведении функции (например, дифференцируемости и непрерывности);

относительно стойки к попаданию в локальные оптимумы;

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

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

просты в реализации;

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

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

очень сложно найти точный глобальный оптимум;

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

сложно смоделировать для нахождения всех решений задачи;

Список литературы

. Батищев Д.И. Генетические алгоритмы решения экстремальных задач /Д.И. Батищев/ - Нижний Новгород: Нижегородский госуниверситет, 1995. - 62 с.

2. Дарвин Ч. О происхождении видов путём естественного отбора или сохранении благоприятствуемых пород в борьбе за жизнь /Ч. Дарвин/ - М.: АН СССР, 1939.

. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы /Л.А. Гладков, В.В. Курейчик, В.М. Курейчик/ - М.: ФИЗМАТЛИТ, 2006. - 320 с.

. Панченко Т.В. Генетические алгоритмы /Т.В. Панченко/ - Астрахань: издательский дом "Астраханский университет", 2007. - 87 с.

. Санкт-Петербургский государственный университет информационных технологий, механики и оптики. Генетические алгоритмы. [Электронный ресурс]. Режим доступа: http://rain.ifmo.ru/cat/. Загл. с экрана.

. Ю. Цой. Авторский сайт. [Электронный ресурс]. Режим доступа: http://www.qai.narod.ru/. Загл. с экрана.

. Исаев С.А. Популярно о генетических алгоритмах. [Электронный ресурс]. Режим доступа: http://algolist.manual.ru/аi/gа/ga1.php. Загл. с экрана.