Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ному алгоритму требуется ровно n+1 вычислений целевой функции для получения точки локального оптимума произвольной монотонной псевдобулевой функции.
Обобщенный алгоритм локального поиска для оптимизации унимодальных псевдобулевых функций
1. Произвольно выбираем точку X1 и определям ее (n/2)-соседние точки X2, X3, тАж , Xn, вычисляем значения функции в этих точках.
2. Генерируем точки Yj = (), j = 1, 2, тАж, n и вычисляем значения функции в этих точках.
. Определяем точку X* по правилу
и вычисляем значение функции в ней.
. Если f(X*)<f(Xj) " j = 1, 2, тАж, n и f(X*)<f(Yj) "j = 1, 2, тАж, n, то необходимо определить все точки Zi O1(X*) и вычислить значения функции в них. Далее выполнять с шага 6.
. Если f(X*)<f(Zi) "i = 1, 2, тАж, n, то вывести X*, f(X*) и остановиться (X* - точка минимума, функция f - унимодальная и монотонная).
. Выбрать точку X0 из условия
(X0) = min {f(X*), f(Xj), f(Yj), f(Zj), "j = 1, 2, ..., n}
. Определять точки Xj O2(X0), j = 1, 2, тАж, и вычислять f(Xj) до тех пор, пока не будет найдена такая точка Xj, что f(Xj)<f(X0).
. Если точка найдена, тогда X0 = Xj и вернуться к шагу 7.
. Среди точек Xk O1(X0) выбрать точку X*, дающую наименьшее значение функции.
. Если f(X*)<f(X0), то X*- точка минимума, иначе это - X0., переходим на шаг 7.
1.3Генетический алгоритм (ГА)
Название данного алгоритма объясняется тем, что в основе него лежит имитация процессов происходящих в природе, среди особей какой-либо популяции [5]. Индивид или особь представляет собой решение, закодированное произвольным образом, например в бинарную строку. Совокупность решений в фиксированный момент времени составляет популяцию. Индивиды текущей популяции конкурируют друг с другом за передачу своей генетической информации (создание потомков) в следующую популяцию. Отобранные индивиды из текущей популяции с помощью селекции, проходят этапы создания новых решений-потомков - рекомбинации и мутации. Основными операторами генетического алгоритма будем называть операторы скрещивания, селекции и мутации.
Селекция - это оператор, с помощью которого происходит выбор индивида из текущей популяции для участия его в рекомбинации и мутации при получении потомка. Рассмотрим основные виды селекций.
Пропорциональная селекция
Пропорциональная селекция может быть выполнена в виде алгоритма колеса рулетки. В данной селекции каждому индивиду из текущей популяции назначается пригодность быть отобранным пропорционально его пригодности. Пусть N - число индивидов в популяции и fi - пригодность i- го индивида в популяции тогда, например, если N = 4, f1 = f2 = 10, f3 = 15, и f4 = 25 колесо рулетки представлено на рисунке 1.3:
Рис. 1.3 Пример колеса рулетки
Проблемы с пропорциональной селекцией:
Преждевременная сходимость. Эта проблема возникает, когда на первых стадиях работы алгоритма в популяции появляется один или несколько супериндивидов, у которых достаточно большая пригодность, и они доминируют при выборе родителя для создания потомка. Вскоре каждая последующая популяция будет состоять из этих супериндивидов.
Стагнация
Ранговая селекция
В этом виде селекции индивиду назначается вероятность быть отобранным в зависимости от его места в упорядоченном ряду по пригодности индивидов текущей популяции. Таким образом, индивиды сортируются (ранжируются) на основе их пригодности таким образом, чтобы fi fj для i > j.
Затем каждому индивиду назначается вероятность pi быть отобранным.
Используемое распределение вероятностей:
- Линейное: pi = ai + b (a < 0).
Преимущества:
- Нет преждевременной сходимости, т.к. нет индивидов с Ni >> 1.
- Нет стагнации, так как и к концу работы алгоритма N1 N2 тАж .
- Нет необходимости в явном вычислении пригодности, т.к. для упорядочения индивидов достаточно иметь возможность их по парного сравнения.
Недостатки: значительные накладные расходы на переупорядочивание и трудность теоретического анализа сходимости.
Турнирная селекция
Одна из самых простых в реализации и эффективных в оптимизации является турнирная селекция. Для отбора индивида создается группа из M (M 2) индивидов, выбранных из текущей популяции случайным образом
Индивид с наибольшей пригодностью в группе отбирается, остальные - игнорируются
Преимущества:
- Нет преждевременной сходимости
- Нет стагнации
- Не требуется глобальное переупорядочивание
- Не требуется явное вычисление функции пригодности
Элитарная селекция
В данной селекции один или несколько лучших индивидов популяции всегда проходит в следующее поколение
Преимущество: гарантия сходимости, т.е. если глобальный максимум будет обнаружен, то ГА сойдется к этому максимуму
Недостаток: слабая глобальная сходимость, большой риск найти локальный минимумом
Скрещивание в ГА
Оператор скрещивание предназначен для поиска новых решений на основе отобранных селекцией родителей.
Одноточечное скрещивание представляет собой разделение родительских хромосом в выбранной случайным образом общей точке и обмен правыми частями. (ТС - точка скрещивания). Пример одноточечного скрещивания представлена на рисунке 1.4.