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

В задачах оптимизации часто применяется класс эвристических алгоритмов. К этому классу относятся и вероятностные эволюционные алгоритмы. Благодаря комбинированию случайного поиска и механизма уточнения (сохранения) решения даже при большом пространстве поиска решение может быть найдено в приемлемые временные рамки [1,2].

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

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

Рассмотрим задачу размерности и диапазон работ , сгенерируем 30 разных наборов данных (весов) работ и запустим по раз ГА для каждого из набора данных. Полученное значение представлено на Рис. 1, хорошо заметно, что точность алгоритма очень сильно зависит от исходных данных предназначенных для построения распределения.

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

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

Схема поиска минимального с лимитом итераций .

Ш.1 Установка текущего значения поиска . . Число запусков ГА на каждом шаге .

Ш.2 . Генерируем новое распределение, используя ГСЧ с . Получаем точное решение с помощью метода полного перебора (ПП) или метода ветвей и границ (МВГ) - .

Ш.2.1 , найденных точных решений

Ш.2.2 Получаем расписание с помощью ГА -

Ш.2.2 Если , то

Ш.2.3 Если то Ш.2. (Если ГА превысил значение минимальной точности, то переходим к поиску в новом распределении)

Ш.2.4 Если перейти к Ш.2.2

Ш.3 Если , то . Найдено новое значение .

Ш.4 Если , то Ш.2.

Ш.5 Выход с .

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

Процесс поиска минимального для задачи , диапазон работ , показан на Рис. 2 и Рис. 3. Достигнутое минимальное вероятность . Оценка минимального числа опытов при составит

Рис. 2. Процесс изменения Pmin в процессе поиска

Рис. 3 Значение Ps

Замечание: В большинстве языков программирования используются встроенные ГСЧ, дающие псевдо случайные последовательности чисел, целиком определяемые начальной точкой ГСЧ (seed). Таким образом, задав значение seed можно целиком воспроизвести работу ГА или сгенерировать постоянный набор весов работ.

Варианты заданий

Целью лабораторной работы является подтверждение стабильности ГА при фиксированном распределении, а также определение .