Кластерный генетический алгоритм для построения множества Парето в задаче многокритериальной оптимизации
Метод многокритериальной оптимизации с использование кластерного генетического алгоритма. Анализ необходимости дополнительной проработки механизма сравнения хромосом, возможное усиление векторного критерия оптимальности дополнительными условиями.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 27.02.2019 |
Размер файла | 291,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru//
Размещено на http://www.allbest.ru//
Кластерный генетический алгоритм для построения множества Парето в задаче многокритериальной оптимизации
Макушин Д. А.
Все большее распространение повсеместно получают различные стохастические и эволюционные алгоритмы. Одним из таких алгоритмов является кластерный генетический алгоритм, который, как и стандартный генетический алгоритм, основывается на эволюционных принципах, но в тоже время позволяет поддерживать до последнего шага своей работы разнообразие популяции, благодаря разбиению пространства поиска. Рассматривается применение этого метода для приближенного построения множества Парето в задаче многокритериальной оптимизации.
Ключевые слова. Многокритериальная задача, кластерный генетический алгоритм, множество Парето, эволюционные алгоритмы.
Постановка задачи. Совокупность частных критериев оптимальности образует векторный критерий оптимальности , где - вектор варьируемых параметров. Ставится задача минимизации каждого из частичных критериев в одной и той же области допустимых значений вектора варьируемых параметров . Запишем задачу многокритериальной оптимизации в виде
. (1)
Положим, что частные критерии оптимальности тем или иным образом нормализованы.
Векторный критерий оптимальности выполняет отображение множества в некоторую область , где - пространство критериев. Будем говорить, что вектор предпочтительнее вектора , и писать , если среди равенств и неравенств имеется хотя бы одно строгое неравенство. Аналогично, будем говорить, что векторный критерий оптимальности доминирует векторный критерий оптимальности , и писать , если .
Во множестве выделим подмножество точек, для которых в этом подмножестве нет точек, их доминирующих. Подмножество называется фронтом Парето, а подмножество , соответствующее множеству - множеством Парето (переговорным множеством, областью компромисса).
Ставится задача приближенного построения множества Парето (а тем самым, и фронта Парето) в задаче многокритериальной оптимизации (1) [2].
Метод многокритериальной оптимизации с использование кластерного генетического алгоритма. Особенностью кластерного генетического алгоритма (КГА) является наличие совершенно особенной подпопуляции, содержащей кластеры хромосом, которые формируются по принципу фенотипического отличия друг от друга. Эта подпопуляция позволяет поддерживать разнообразие основной популяции, необходимое для параллельного исследования всех областей пространства поиска.
Каждый кластер - это набор решений, которые обладают схожими свойствами (в данном случае, кодируемых хромосомами с похожими фенотипами).
Для определения меры близости в данном случае используется бинарная (Хемминга) метрика . Число кластеров зависит от параметров области поиска и задаваемого радиуса гиперсферы кластера . Если хромосом располагается в пределах до центроида кластера , то он считается принадлежащим . Кластеризация элементов популяции производится по принципу доминирования.
Пусть фрагментов популяции , представляющих собой кластеры. Хромосома является доминирующей в кластере, если для (здесь предполагается, что решается задача минимизации). Знак нестрого неравенства означает, что в кластере может быть более одного доминирующего решения. Поэтому хромосома является центроидом кластера тогда и только тогда, если для . Важно, что отдельные хромосомы, соответствующие этому неравенству, могут принадлежать одновременно и другим кластерам, а также доминировать сразу в нескольких кластерах [1].
Для обработки подпопуляции найденных центроидов вводятся две дополнительные вычислительные процедуры - выделения и копирования кластеров (рис.1)
.
Рис. 1. Структура кластерной модификации генетического алгоритма (ГА)
Процедура выделения кластеров состоит в определении кластеров, определяемых координатами центроидов. Под центроидом понимается хромосома, доминирующая все другие хромосомы принадлежащие к данному кластеру, находящиеся на расстоянии не превышающем от нее.
Центроиды кластеров сохраняются в отдельной подпопуляции. После этого основная популяция подвергается применению генетических операторов и претерпевает изменения, найденные кластеры теряются. Затем, для восстановления «присутствия» ГА в соответствующих участках поискового пространства, сохраненные центроиды копируются в основную популяцию.
Происходит это следующим образом: «худшая» хромосома из некоторого кластера заменяется своим центроидом. Если такая хромосома отсутствует, то на центроид заменяется «худшая» хромосома новой популяции, не принадлежащая ни одному из кластеров.
Так как в данном случае речь идет о многокритериальной задаче, соответствующие необходимые изменения претерпел генетический оператор отбора. Сравнение хромосом должно проводиться с использованием векторного критерия оптимальности. Кроме того, при решении многокритериальной задачи глобально лучшие решения отыскиваются на множестве Парето. С этой целью выполнено преобразование этапа оценки решений, полученных в ходе работы алгоритма. Таким образом, на этапе формирования новой популяции хромосом с множеством генов и множеством частных критериев оптимальности , в нее попадают лишь те хромосомы, которые удовлетворяют условию, что .
Реализация. Для того чтобы иметь возможность точной оценки аппроксимации, исследование эффективности выполнено для простой двумерной задачи с известным решением:
множество допустимых значений вектора варьируемых параметров
(2)
частные критерии оптимальности
(3)
Для КГА использованы следующие параметры: размер популяции ; вероятность скрещивания ; вероятность мутации ; Радиус гиперсферы кластера ; количество эпох .
Эффективность метода с учетом указанных условий иллюстрирует рисунок 2. Точные решения этой задач представляют собой отрезок прямой с координатами (0,0) и (1,1); Точный фронт Парето - дуга окружности проходящая через точки (0,2), (2,0), (0,5,0,5). Средняя ошибка аппроксимации на завершающем этапе работы алгоритма.
а) |
б) |
|
Рис. 2. Аппроксимация множества Парето (а) и фронта Парето (б) |
Для дальнейшего улучшения работы алгоритма необходима дополнительная проработка механизма сравнения хромосом и возможное усиление векторного критерия оптимальности дополнительными условиями. Например, минимизацией суммарной оценки частных критериев.
парето многокритериальный оптимизация кластерный
Литература
1. Казаков П. В. Кластерный генетический алгоритм синтеза оптимальных решений задачи инвестирования. - Брянский государственный технический университет, 2004. - 5 с.
2. Антух А.Э., Карпенко А.П., Семенихин А.С. Исследование эффективности архитектуры CUDA для аппроксимации множества Парето с помощью метода роя частиц. - Вестник ЮУрГУ №37(254), 2011 - С. 63-70.
Размещено на Allbest.ru
...Подобные документы
Описание генетических алгоритмов. Применение генетического алгоритма для решения задачи коммивояжера. Постановка задачи безусловной оптимизации. Изучение распространения генетических алгоритмов на модель с несколькими взаимодействующими популяциями.
дипломная работа [979,1 K], добавлен 30.05.2015Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Определение и описание "генетического алгоритма", идея которого состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Пример его тривиальной реализации на C++.
контрольная работа [172,1 K], добавлен 24.05.2010Анализ предметной области. Разработка генетического алгоритма для оптимизации инвестиций. Спецификация требований и прецедентов. Проектирование пользовательского интерфейса информационной системы. Модели данных, используемые в системе и их взаимодействие.
дипломная работа [2,1 M], добавлен 24.08.2017Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
лабораторная работа [20,2 K], добавлен 03.12.2014Сравнение результатов работы генетического алгоритма по решению "несимметричной незамкнутой задачи коммивояжера" с результатами работы алгоритма динамического программирования по параметрам - время работы, точность результата и объем используемой памяти.
курсовая работа [65,3 K], добавлен 16.04.2014Основные генетические операторы. Схема функционирования генетического алгоритма. Задачи, решаемые с помощью генетических алгоритмов. Математическая постановка задачи оптимизации. Решение Диофантова уравнения. Программная реализация. Создание пособия.
курсовая работа [391,4 K], добавлен 20.02.2008Первые работы по симуляции эволюции. Основные понятия генетических алгоритмов. Постановка задачи и функция приспособленности. Инициализация, формирование исходной популяции. Выбор исходной популяции для генетического алгоритма, решение задач оптимизации.
курсовая работа [714,1 K], добавлен 31.03.2015Этапы работы генетического алгоритма, область его применения. Структура данных, генерация первоначальной популяции. Алгоритм кроссинговера - поиск локальных оптимумов. Селекция особей в популяции. Техническое описание программы и руководство пользователя.
реферат [1014,2 K], добавлен 14.01.2016Методы решения задач параметрической оптимизации. Решение однокритериальных задач с параметром в целевой функции и в ограничениях. Решение многокритериальной задачи методом свертки критериев, методом главного критерия, методом последовательных уступок.
курсовая работа [1,5 M], добавлен 14.07.2012Программа реализации генетического алгоритма, использование визуальной среды программирования. Руководство пользователя, листинг программы. Возможность ввода параметров: объем популяции, число поколений, коэффициент скрещивания и мутации, число городов.
курсовая работа [2,9 M], добавлен 20.08.2009Разработка алгоритма оптимизации коэффициентов дискретного регулятора с законом ПИД по минимуму интегрального квадратичного критерия. Расчёт оптимальных параметров регулятора на основе описанных алгоритмов. Анализ переходных процессов в замкнутой системе.
практическая работа [1,4 M], добавлен 25.12.2011Операторы генетического алгоритма. Пример простейшей программы. Процесс генерации и накопления информации о выживании и продолжении рода в ряде поколений популяции. Программа, реализующая простой генетический алгоритм для нахождения минимума функции.
курсовая работа [39,3 K], добавлен 29.10.2012Содержание фундаментальной теории гена. Описание простого генетического алгоритма поиска оптимальных решений. Сущность понятий "кроссинговер", "сайт", "иллегальная рекомбинация". Этапы реализации алгоритма Девиса по перераспределению участков хромосом.
контрольная работа [23,7 K], добавлен 17.09.2010Необходимые условия экстремума. Разработка машинного алгоритма и программы многомерной оптимизации для градиентного метода с использованием метода равномерного поиска. Проверка необходимых и достаточных условий экстремума для найденной точки минимума.
курсовая работа [249,8 K], добавлен 25.09.2013Оптимизация показателей эффективности функционирования технологического контура системы управления космическим аппаратом, исследование свойств его показателей. Настройка нейронной сети, гибридизация генетического алгоритма с алгоритмами локального поиска.
дипломная работа [4,5 M], добавлен 02.06.2011Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Алгоритм реализации векторного пространства, метод фильтрации шумов на изображении. Формально-логическая модель разработки программного обеспечения, выбор инструментальных средств его реализации. Анализ точности совпадения распознанного изображения.
дипломная работа [2,7 M], добавлен 13.02.2013