1. Введение.
Целью данной работы являлась определение наилучшего оператора скрещивания для решения задачи управления активами.
Под активами понимается широкий спектр материальных и нематериальных объектов: здания, сооружения, земельные участки, объекты строительства, единицы оборудования, программные комплексы, базы данных, патенты, лицензии на природные ресурсы и т.д.
Можно выделить следующие методы управления активами:
· Метод общего фонда
· Метод распределения активов или конверсии средств
· Метод научного управления активами
Оптимизация процесса управления активами, также играет важную роль в управлении активами. Для решения задачи оптимизации можно использовать генетический алгоритм.
Данный алгоритм представляет собой метод эвристического поиска, основанный на теории естественной эволюции Чарльза Дарвина [1, с. 1].
Можно выделить следующие этапы работы алгоритма:
· Выбор функции приспособленности (фитнес-функции);
· Создание популяции;
· Начало цикла
1. Фаза скрещивания;
2. Фаза мутации;
3. Вычисление функций приспособленностей всех особей;
4. Фаза селекции;
5. Уничтожение популяции (в случае, если выполнено условие завершения ГА);
· Анализ полученных результатов;
Более подробно рассмотрим фазу скрещивания. Различные подходы к скрещиванию созданы в попытке получить оптимальное решение как можно раньше, при минимальном количестве поколений. Выбор операторов скрещивания оказывает большое влияние на производительность ГА. Операторы делятся на 3 категории: стандартные, двоичные и специальные, которые зависят от области применения.
В данной статье будут рассмотрены стандартные операторы скрещивания.
Цель скрещивания состоит в обеспечении смешивания решений и их сходимости к оптимальному результату.
2. Стандартные операторы скрещивания
2.1. Одноточечное скрещивание (1-point crossover)
Это одна из самых простых техник скрещивания, используемая для решения различных задач. Данный метод разбивает каждого родителя на две части и затем комбинирует их для получения потомка или решения [3, c. 1]. Родитель представляет из себя строчку с набором значений. Эту строку называют хромосомой, а единичное значение хромосомы – геном.
Хромосома – это упорядоченная последовательность генов.
Ген – это атомарный элемент хромосомы [4, c. 1].
Процесс работы алгоритма представлен на Рис.1.
Рис 1. – Схема работы одноточечного скрещивания
Недостатком данного метода является то, что потомки очень похожи на родителей.
2.2. Однородное скрещивание (Uniform crossover)
Метод обеспечивает единообразие в объединении генов обоих родителей. Он выполняет операцию обмена частей генома родителей, из которых будут сформированы потомки, путем выбора случайного действительного числа (от 0 до 1). Алгоритм отбирает двух родителей для скрещивания, из которых получаются два потомка из n генов, однородно отобранных от обоих родителей. Случайное действительное число определяет, выберет ли первый потомок i-й ген у первого или второго родителя.
В отличии от одноточечного скрещивания, в этом методе потомки наоборот будут слишком сильно отличаться от родителей.
2.3. Многоточечное скрещивание (K—point crossover)
Отличие данного метода от одноточечного скрещивания состоит в том, что родительские хромосомы делятся не на две части, а на К+1 частей.
Процесс работы алгоритма представлен на Рис.2.
Рис 2. Схема работы многоточечного скрещивания
Изменяя величину числа K, можно контролировать степень отличия потомков от родителей, это является несомненным преимуществом по сравнению с операторами, рассмотренными выше.
2.4. Оператор скрещивания «Перетасовка» (Shuffle crossover)
«Перетасовка» создает потомков, не зависящих от точек скрещивания их родителей. Метод использует тот же принцип, что и одноточечный оператор скрещивания, но к нему добавляется перемешивание.
Процесс работы алгоритма представлен на Рис. 3.
Рис 3. Схема работы оператора скрещивания «перетасовка»
Сначала, случайным образом смешиваются гены родителей. Затем, применяется одноточечное скрещивание. После, гены родителей комбинируются, и создают двух потомков. В конце, гены потомков возвращаются в порядок, который был до перетасовки.
2.5. Скрещивание по среднему значению (Average crossover)
Этот метод скрещивания основывается на величине значения генов. Из двух родителей, выбранных для скрещивания, получается только один потомок. Его получают путем подстановки среднего значения генов родителей. Каждый ген потомка – среднее значение соответствующих генов родителей [2]. Алгоритм метода представлен на Рис. 4.
Рис. 4 – Скрещивание по среднему значению.
Для использования данного метода при работе с активами, необходимо провести их нормирование.
2.6. Дискретное скрещивание (discrete crossover)
Данный метод использует случайное действительное число, для создания одного потомка из двух родителей. В отличие от равномерного скрещивания, в дискретном генерируется только один потомок. Он выбирает двух родителей X и Y и генерирует потомка Z так, что гены обоих родителей отбираются равномерно. Случайное число решает, от кого взять ген для потомка [2, c. 2].
2.7. Скрещивание по пороговому значению (Flat crossover)
Метод также использует случайное действительное число, чтобы создать одного потомка из двух родителей.
Так же, как и в дискретном, он отбирает гены у родителей на основе случайного действительного числа. Ген потомка формируется с помощью случайного числа, которое определяет какое значение гена (минимальное или максимальное) из соответствующих генов родителей будет у потомка.
Общим недостатком последних трех операторов является получение лишь одного потомка, и поэтому для сохранения популяции на том же уровне, при таком же числе вымирающих особей, что и у методов, рассмотренных ранее, необходимо увеличить число скрещиваний в 2 раза.
3. Заключение
Существует большое количество различных операторов скрещивания. Каждый из них имеет свои преимущества и недостатки. Большинство из них стремятся решить проблему быстрой сходимости популяции, из-за которой генетический алгоритм может отработать неверно. Для решения задачи управления активами лучше всего подойдет многоточечный метод или оператор скрещивания «Перетасовка». Так как используя эти методы потомки будут достаточно разнообразны.
Использованные источники:
1. Introduction to Genetic Algorithms [Электронный ресурс]. URL: https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3 (дата обращения 18.10.19).
2. Crossover operators in genetic algorithms: a review [Электронный ресурс]. URL: http://ictactjournals.in/paper/IJSC_V6_I1_paper_4_pp_1083_1092.pdf (дата обращения 18.10.19)
3. Genetic algorithms — crossover [Электронный ресурс]. URL: https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.htm (дата обращения 18.10.19)
4. Основные понятия генетических алгоритмов [Электронный ресурс]. URL: http://www.aiportal.ru/articles/genetic-algorithms/basic-concepts.html (дата обращения 18.10.19)
