Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
?вухточечном скрещивании хромосома как бы замыкается в кольцо, выбираются 2 точки разрыва, родитель обмениваются частями (рис. 2).
Рис. 2. Двухточечное скрещивание.
При равномерном скрещивании потомок может унаследовать с равной вероятностью гены любого из родителей (рис. 3).
Рис. 3. Равномерное скрещивание.
Равномерное скрещивание по всей популяции (uniform gene pool recombination) получается применением равномерного скрещивание к всем членам популяции, т.е. потомок может унаследовать любой ген, имеющийся в популяции в заданной позиции хромосомы [53].
1.2.6Мутация
Оператор мутации - одноместный оператор поиска, случайное изменение в одном или нескольких генах индивида. В ГА мутация рассматривается как метод восстановления потерянного генетического материала, а не как поиск лучшего решения. Мутация применяется к генам с очень низкой вероятностью . Хорошим эмпирическим правилом считается выбор вероятности мутации равным , где - число генов в хромосоме (в среднем хотя бы один ген будет подвержен мутации). В случае бинарного алфавита мутация состоит в инвертировании случайно выбранных битов (рис. 4).
Рис. 4. Пример мутации в ГА.
1.2.7Пригодность индивидов (fitness - функция)
Пригодность индивида - это некоторая количественная оценка качества решения поставленной задачи. Функция пригодности может быть спроектирована с учетом особенностей решаемой задачи (что делает ГА довольно гибким, универсальным). Обычно функция пригодности принимает положительные значения, и значение пригодности максимизируют.
В общем случае при решении задач безусловной оптимизации в качестве значения функции пригодности может выступать значение оптимизируемого функционала ().
1.2.8Исследование работоспособности на тестовых задачах
Для исследования работоспособности ГА была разработана программная система GA lab, реализующая практически все основные параметры алгоритма. Эффективность алгоритма проверялась на тестовых функциях 1, 3, 4, 6-8, 15. Исследования проводились для ГА с одноточечным скрещиванием и ГА с равномерным скрещиванием по всей популяции. Реализованы пропорциональная, ранговая и турнирная (размер турнира - 2) селекции, низкая и высокая мутации. Использовалось стандартное бинарное и кодирование Грея. Размер популяции - 50. Количество прогонов алгоритма - 50.
Для оценки эффективности алгоритмов использованы два показателя: надежность и среднее число итераций. Надежность - процент успешных запусков (решение найдено) к общему числу запусков алгоритма. Среднее число итераций - номер итерации, когда найдено решение, усредненный по успешным прогонам. Алгоритм с наибольшей надежностью всегда считается лучшим. Среди алгоритмов с одинаковой надежностью - лучший тот, у которого наименьшее среднее число итераций.
Результаты тестирования представлены в таблице 1 (серым выделен алгоритм победивший на данной тестовой задаче). Из таблицы видно, что наиболее эффективным оказывается использование высокой мутации, которая помогает избежать локальной сходимости даже при использовании пропорциональной селекции (победители на Ф4, Ф6, Ф8). Код Грея в сочетании с представленными алгоритмами оказался не достаточно эффективным на Ф6 и Ф8, т.к. на этих функциях было бы лучше если соседние в бинаризованном пространстве точки оказались далекими в исходном - для Ф6 структура локальных оптимумов могла бы нарушиться, и оптимумов могло бы стать меньше; для Ф8 в новой системе окрестностей могли нарушиться множества постоянства.
Таблица 1. Сравнительный анализ эффективности генетических алгоритмов.
Тестовая задачаТип селекцииГА с одноточечным скрещиванием (низкая мутация)ГА с одноточечным скрещиванием (высокая мутация)ГА с равномерным скрещиванием по всей популяции (низкая мутация)ГА с равномерным скрещиванием по всей популяции (высокая мутация)Код ГреяБинарный кодКод ГреяБинарный кодКод ГреяБинарный кодКод ГреяБинарный кодНадеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Надеж-ностьСр. число итер.Ф1пропорц.24195415823176185228641887348418ранг.26325620843210018турнир.161546934154612Ф3пропорц.742520982312698420251681322016ранг.3429281283288528турнир.2415101044172410Ф4пропорц.2486134430815102751427251620ранг.4251010002420турнир.61441426812Ф6пропорц.41418928302019712141611322420ранг.001292361418турнир.21010700412Ф7пропорц.1028205482658142517361160236320ранг.101830714281830турнир.16161461020227Ф8пропорц.000000717002700525ранг.000000630турнир.00280000Ф15пропорц.52295218503236227027222087323420ранг.2633461698364823турнир.1211121150232818
1.3Метод изменяющихся вероятностей (МИВЕР) и исследование его работоспособности на тестовых задачах
1.3.1Общая схема МИВЕР
Метод изменяющихся вероятностей представляет собой семейство стохастических алгоритмов псевдобулевой оптимизации, имеющих общую схему, в основе которой лежит алгоритм случайного поиска с адаптацией [1]. В самом общем виде эта схема (обозначим МИВЕР1) применительно к задаче (2) выглядит следующим образом:
1.Задаются начальные значения компонент вектора вероятностей , .
.Случайным образом (в соответствии с распределением вероятностей ), независимо выбираются векторов .
.Вычисляются соответствующие значения функционала .
.Определяются и . Значения и и соответствующие векторы и запоминаются.
.По результатам п. 4 изменяются (в соответствии с правилом конкретного а?/p>