Тема «Генетические алгоритмы»

Вопросы:

1. Классы задач оптимизации

2. Методы решения оптимизационных задач

3. Эволюционные вычисления

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

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

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

1. Классы задач оптимизации

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

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

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

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

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

1. Имеется некоторая известная функция от набора переменных Y = f (x₁, x₂, …x_n). Необходимо найти такие значения x_i, при которых функция Y принимает экстремальное значение.

2. Известен вид функции, т.е., известно количество слагаемых в правой части и степени переменных, однако значения коэффициентов при переменных неизвестны (классическая регрессионная задача).

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

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

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

F (X) = extr f(X),

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

В этом случае ищется экстремум путем изменения:

• независимых переменных во всех диапазонах значений, в которых они определены;

• коэффициентов при независимых переменных;

• вида зависимости между зависимой и независимыми переменными.