Определение экстремумов функции с помощью генетических алгоритмов

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

СОДЕРЖАНИЕ 1
ВВЕДЕНИЕ 1
Что такое генетический алгоритм? 3
Постановка задачи 6
ЗАКЛЮЧЕНИЕ 8
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 10

Как понятно, оптимизационные задачи содержатся в нахождении минимума либо максимума целевой функции. Как верховодило, целевая функция - непростая и довольно значимая функция, которая зависит в первую очередь от неких входных характеристик.
В оптимизационной задаче требуется отыскать значения входных параметров, при которых целевая функция достигает наибольшего или малого значения. Для достижения этого есть цельный класс оптимизационных способов, разрешённые условно поделить на способы, которые используют понятие производной (градиентные методы) и стохастические методы (методы, которые основаны на получении огромного числа реализаций стохастического (случайного) процесса). С их поддержкой можно найти экстремальный смысл целевой функции, но не постоянно можно существовать убежденным, что по лучено значение глобального экстремума. Местоположение локального экстремума вместо глобального во всей науке называется преждевременной сходимостью.
Для решения данной трудности именно и проводится розыск самых новейших оптимизационных алгоритмов.
Предложенные сравнительно недавно - в 1975 году в Мичиганском институте Джоном Холландом (John Holland) генетические методы (ГА), которые были основаны на принципах естественного отбора Ч. Дарвина и относятся к стохастическим способам.
Изначально самый новейший алгоритм действий получил заглавие «репродуктивный план Холланда», и в предстоящем деятельно употреблялся в качестве базисного метода в эволюционных вычислениях. Идеи Холланда развили его воспитанники Кеннет Де Йонг (Kenneth De Jong) из института Джорджа Мейсона (Вирджиния) и Дэвид Голдберг (David E. Goldberg) из лаборатории ГА Иллинойса. Благодаря им, был создан строгий ГА, описаны все операторы и изучено поведение группы тестовых функций (конкретно алгоритм Голдберга и получил название «генетический алгоритм»).
Генетические алгоритмы - это адаптивные методы поиска, которые в крайнее время употребляются для решения задач оптимизации. В них используются как аналог механизма генетического наследования, и в том числе и аналог естественного отбора.
Данные алгоритмы эффективно и удачно используются в самых разнообразных областях знаний и идей (экономика, физика, технические науки и т.п.). Созданы разные трансформации ГА и изобретен разряд тестовых функций.

Делается намерение, что если к примеру, взять два полностью хороших решения задачи и каким-то любым образом заполучить из них новое решение, то обязательно в итоге будет высочайшая возможность того, что это новейшее решение выйдет неплохим или даже наиболее наилучшим.Для реализации этого употребляют моделирование эволюции (естественного отбора) или если легче - борьбы за выживание. В природе, по упрощенной схеме, любое четвероногое жаждет жить, чтобы бросить после себя как можно более потомства. Выжить в таковых критериях могут только сильнейшие.Тогда нам остается осуществить некоторую среду - популяцию, населить её решениями - особями, и устроить им борьбу. Для этого необходимо найти функцию, по которой будет складываться сила особи - свойство предложенного ею решения. Основываясь на этом параметре можно определить каждой особи численность оставляемых ею потомков, или вероятность того, что данная индивидуум оставит отпрыска. Причем, не исключен вариант, когда особь со очень низким значением этого параметра умрёт.Допустим нам нужно улучшить некоторую функцию F(X1,X2,..,Xn). Пусть мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать, как мы станем сохранять решения. По сути, нам нужно вместить все X1-Xn в некоторый вектор, который будет играть роль хромосомы. Один из наиболее распространенных методик – кодировать смысла переменных в битовом векторе. Например, выделим любому иксу по 8 бит. Тогда наш вектор будет длины L=8*n. Для простоты будем полагать, что биты лежат в массиве X[0..L-1].Пусть любая особь состоит из массива X и значения функции F на переменных, извлеченных из этого массива.Тогда ГА будет быть из последующих шагов:Генерация начальной популяции - наполнение популяции особями, в которых составляющие массива X (биты) заполнены случайным образом.Выбор родительской пары это из множества - постоянно использую привилегированный отбор, то есть забираем K особей с максимальными значениями функции F и составляю из них все вероятные пары (K*(K-1)/2).Кроссинговер - берем случайную точку t на массиве X (0..L-1).ныне, все элементы массива с индексами 0-t новейшей особи (потомка) наполняем элементами с теми-же индексами, но из массива X первой родительской особи. Остальные элементы заполняются из массива 2-ой родительской особи. Для другого потомка делается напротив - элементы 0-t берут от второго потомка, а другие - от главного.Новые особи с некой вероятностью мутируют - инвертируется беспорядочный бит массива Xданной особи. Вероятность мутации традиционно считают распорядка 1%.Полученные особи- HYPERLINK "javascript:edit_sin('697',%20'%D0%BE%D1%82%D0%BF%D1%80%D1%8B%D1%81%D0%BA%D0%B8',%20'%D0%BF%D0%BE%D1%82%D0%BE%D0%BC%D0%BA%D0%B8')" потомки прибавляются в популяцию после переоценки. Обычно новейшую особь добавляют в обмен самой плохой старой особи, при условии что значение функции на новой особи больше значения функции на старой-плохой особи.Если самое наилучшее решение в популяции нас не удовлетворяет, то переход на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются нескончаемо.Вообще, если взыскательно задерживаться правилам, то ГА обязан содержать еще такие шаги как отбор особей для размножения и генерация пар из отобранных особей. При этом каждая особь может быть задействована в одной и более паре, в зависимости от используемого метода.Однако я предпочитаю эти 2 шага кооперировать, используя построение пар "все на все" в элитной выборке. Имхо, так проще.Постановка задачиРассматривается многопараметрическая непрерывная задача оптимизации,в которой дифференцируемость, непрерывности, ублажение условию Гельдера (в том числе липшицируемость функции) не являются нужным свойством осматриваемого класса задач, не считая того, целевая функция может существовать совсем не определена за пределами возможной области, а внутри допустимой области обладать несколько глобальных экстремумов.Можно отметить по последней мере, три класса задач, которые могут быть решены представленным методом.