В статье рассматривается основные понятия генетического алгоритма и его составляющие. Рассмотрены такие процессы как выбор кроссовер и мутация. Кроме того, приводиться обзор работ учёных, где активно применяется возможности генетических алгоритмов. В статье рассмотрены две научные работы, где исследуется кластеризация изображений используя генетический алгоритм и применении генетических алгоритмов для решения проблемы расписания прибытия воздушных судов в системах с несколькими взлетно-посадочными полосами.
Ключевые слова: генетический алгоритм, кроссовер, отбор, мутация, хромосома, индивид, популяция.
The article discusses the basic concepts of a genetic algorithm and its components. Processes such as crossover selection and mutation are considered. In addition, an overview of the work of scientists is given, where the possibilities of genetic algorithms are actively used. The article considers two scientific papers that explore image clustering using a genetic algorithm and the application of genetic algorithms to solve the problem of aircraft arrival schedules in systems with multiple runways.
Keywords: genetic algorithm, crossover, selection, mutation, chromosome, individual, population.
Исследования в сфере информационно-коммуникационных технологии проводятся по всему миру, и вся сфера благодаря этому развивается быстрыми темпами. На сегодняшний день особенно большое внимание уделяется сфере искусственного интеллекта. Сама по себе сфера искусственного интеллекта является довольно большой сферой и в него входят многие направления. Такие как, машинное обучение, глубокое обучение, нейронные сети, генетические алгоритмы и т. д. Учёные со всего мира активно занимаются изучением и разработкой новых типов алгоритмов для улучшения работы искусственного интеллекта. В данной статье мы будем анализировать работу генетического алгоритма и проводить обзор существующих алгоритмов, а также их применение в реальных задачах.
Генетический алгоритм — это метод поиска, основанный на теории эволюции Дарвина, получивший в последние годы огромную популярность во всем мире. В последние годы международное научное сообщество проявляет растущий интерес к новой методике поиска, основанной на теории эволюции и известной как генетический алгоритм. Этот метод основан на используемых природой механизмах отбора, согласно которым наиболее приспособленными особями популяции являются те, которые выживают, легче адаптируясь к изменениям, происходящим в их среде обитания. Сегодня известно, что эти изменения происходят в генах особи (основной единице кодификации каждого из признаков живого существа) и что наиболее желательные ее признаки (т. е. те, которые позволяют ей лучше адаптироваться к окружающей среде) передаются их потомкам при размножении половым путем. Исследователь из Мичиганского университета Джон Холланд осознавал важность естественного отбора и в конце 60-х годов разработал методику, которая позволила включить его в программу. Его целью было заставить компьютеры обучаться самостоятельно. Техника, которую изобрел Холланд, первоначально называлась «репродуктивные планы», но стала популярной под названием «генетический алгоритм» после публикации его книги в 1975 году [1].
Достаточно полное определение генетического алгоритма предложено Джоном Коза: «Это в высшей степени параллельный математический алгоритм, который преобразует набор отдельных математических объектов относительно времени с помощью операций, смоделированных в соответствии с дарвиновским принципом воспроизводства и выживания каждый из этих математических объектов обычно представляет собой строку символов (букв или цифр) фиксированной длины, которая соответствует модели цепочек хромосом, и они связаны с определенной математической функцией, отражающей их приспособленность» [1].
Преимущества Генетического алгоритма.
Алгоритм заключается в следующем:
– Оптимизация с использованием непрерывных или дискретных переменных,
– Не требует производной информации,
– Одновременный поиск по обширной выборке на поверхности затрат,
– Учитывая большое количество переменных,
– Подходит для параллельных компьютеров,
– Оптимизация переменных поверхностей с очень сложными затратами (GA может прыгать от локального минимума),
– Предоставьте список оптимальных переменных, а не просто одно решение,
– Может кодировать переменные, чтобы оптимизация выполнялась путем кодирования переменных,
– Работает с сгенерированными числовыми данными, данными экспериментов или аналитическими функциями.
Генетический алгоритм исходит из набора случайно сгенерированных решений, называемых популяциями. В то время как каждый человек в популяции называется хромосомой, которая является представлением решения, и уровень приспособленности каждого оценивается с помощью заранее определенной функции. Ожидается, что в результате процесса естественного отбора генетических операторов гены двух хромосом (называемых родительскими) будут производить новые хромосомы с более высоким уровнем приспособленности в качестве следующего поколения или потомства. Хромосомы будут иметь итерацию, называемую генерацией. В каждом поколении хромосомы оцениваются по значению функции приспособленности. Через несколько поколений генетический алгоритм сойдётся к лучшей хромосоме, которая является оптимальным решением.
Генетический алгоритм — это самоорганизующаяся и адаптивная технология искусственного интеллекта. В алгоритме начальное решение называется начальной популяцией, и обычно популяция генерируется случайным образом в соответствии с определенными ограничениями. Популяцию можно разделить на независимых особей, также известных как хромосомы, что является одним из решений проблемы, и все особи составляют пространство понимания. Индивиды обычно представляются кодовыми строками, состоящими из двоичных наборов символов {0, 1}, множество индивидов представляют собой популяцию (рис. 1.), которые используются для описания различных параметров в практических задачах. В итерационном процессе алгоритма эволюция каждого поколения называется наследственностью. Генетический процесс состоит из трех операторов операций, а именно: оператора выбора, оператора скрещивания и оператора мутации. Кроме того, хорошие и плохие стороны индивида в генетическом процессе оцениваются по приспособленности, а приспособленность рассчитывается по адаптивной функции для каждого члена популяции. Чем выше приспособленность индивидуума, чем больше решение, которое он представляет, ближе к оптимальному, тем выше вероятность быть выбранным в следующее поколение. Вероятность исключения больше, что согласуется с идеей «выживает сильнейший» в теории эволюции [2].
Рис. 1. Популяция индивидов
Генетический алгоритм в основном состоит из следующих пяти этапов: инициализация популяции, оценка значения приспособленности, отбор, скрещивание и мутация [3].
– Выбор — это случайный процесс выбора родительской хромосомы из популяции на основе значения приспособленности каждой хромосомы [4]. Процесс отбора посредством турнира более эффективен, чем другие методы отбора, и приводит к оптимальным решениям [4]. Прежде чем начнется процесс отбора по турниру, необходимо определить количество участников. Затем отбор турниров случайным образом выбирает кандидата из популяции. Победителем турнира становится хромосома с наибольшим значением приспособленности. Этот процесс отбора повторяется до тех пор, пока 2 хромосомы не будут выбраны в качестве родительской пары.
– Кроссовер — это процесс объединения хромосом родителей для получения новой особи. Метод — Uniform Crossover. Этот метод определяет бинарный ноль и единицу, когда маска локуса имеет значение 1, первый источник имеет такой же состав генов, как и первый родительский элемент, второй источник имеет такой же состав генов, как и второй родительский элемент. Если маска локуса имеет значение 0, первый источник имеет вторые родительские генные композиции, а второй источник имеет первые генные композиции [4].
– Мутация — это генетический оператор, используемый для поддержания генетического разнообразия от одного поколения популяции хромосом генетического алгоритма до следующего поколения. Метод мутации, используемый в этой статье, представляет собой случайную мутацию. При случайной мутации мутировавший ген определяется частотой мутаций, а мутировавший ген выбирается случайным образом [5].
В работе авторов Gevin Valerian, Tri Sutrisno и Dyah Erny Herwindiat [2]. Авторы исследования занимались проверкой генетического алгоритма с отбором турниров и равномерным кроссовером для кластеризации сложных изображений. Авторы утверждают, что генетический алгоритм можно использовать для поиска оптимального центроида для кластеризации изображений (Рис.2). В исследовании использовались изображения пляжа, города, традиционные изображения рынка и изображения сада. Основываясь на результатах исследования, генетический алгоритм с турнирной селекцией и равномерным кроссовером можно использовать для кластеризации изображений, но в сформированном кластере есть некоторый выброс. На основании испытаний лучшими параметрами для кластеризации изображений с помощью генетического алгоритма с турнирным выбором и равномерным кроссовером являются популяция = 200, итерация = 200 и количество кластеров = 2. Значение пригодности генетического алгоритма увеличивается, когда популяция и значение итерации выше. Результат данного исследования может быть использован как ориентир при разработке кластеризации изображений.
Рис. 2. Трехмерный график сформированного кластера и центроида между пляжем и садом
Xiao-Bing Hu и Ezequiel Di Paolo провели исследования и вычисления об эффективной работе генетических алгоритмов с равномерным кроссовером для управления воздушным движением. В исследовании авторы выявили, что очередность и расписание прибытия воздушных судов (ASS) является серьезной проблемой в ежедневной работе органов управления воздушным движением. В работе сообщается о применении генетических алгоритмов для решения проблемы ASS в системах с несколькими взлетно-посадочными полосами. Большинство существующих генетических алгоритмов для ASS сталкиваются с проблемами осуществимости и эффективности при разработке своих эволюционных операторов, особенно кроссовера. Новый генетических алгоритм, описанный в этой статье, использует следующую взаимосвязь между самолетами для построения хромосом. Это позволяет создать высокоэффективный кроссовер оператор-унифицированный кроссовер, который вряд ли применим к тем генетических алгоритмам, которые проектируются непосредственно на основе порядка самолетов в очередях прилета. Основным преимуществом предлагаемого универсального оператора скрещивания является эффективность и результативность в идентификации, наследовании и защите общих последовательностей субтрафика без ущерба для возможности диверсификации хромосом, что продемонстрировано в обширном сравнительном исследовании моделирования. Приняв стратегию управления удаляющимся горизонтом, описанный генетических алгоритм демонстрирует хороший потенциал реализации в режиме реального времени для решения проблемы ASS.
Заключение
Подводя итоги, можно отметить, что генетические алгоритмы являются наиболее эффективными для выявления наилучшего решения в задачах реальной жизни. А также генетические алгоритмы позволяют проводит симуляции различных процессов бесконечное количество раз, что в свою очередь преимущественно повышает процент успешности получаемых результатов, при разработке различных аппаратно-программных средств. В процессе анализа различных работ с использованием генетических алгоритмов, можно сделать выводы, что генетический алгоритм можно использовать в качестве альтернативного способа кластеризации сложные изображения, хотя в сформированном кластере существуют некоторые выбросы. В будущем применение генетических алгоритмов во всех сферах жизни будет неизбежно.
Литература:
- Maad M. Mijwel. Genetic Algorithm Optimization by Natural Selection. computer science, 2016. DOI:10.13140/RG.2.2.23758.18246
- Gevin Valerian*, Tri Sutrisno and Dyah Erny Herwindiati. Image clustering using genetic algorithm with tournament selection and uniform crossover. IOP Conf. Series: Materials Science and Engineering. 2020. doi:10.1088/1757–899X/852/1/012043.
- Konar, Amit. Computational Intelligence Principles, Techniques, and Applications. Springer: Calcutta, India. 2005.
- Bai, L., J. Liang, & C. Dang. An Inititalization Method to Simultaneously Find Initial Cluster Centers and The Number of Clusters for Clustering Categorical Data. Knowledge Based Systems24. 2011. pp. 785–795.
- J P Dias and H S Ferreira. Automating the Extraction of Static Content and Dynamic Behaviour from eCommerce Websites 297–304 ANT. Procedia Computer Science. 2017.
- Xiao-Bing Hu∗, Ezequiel Di Paolo. An efficient genetic algorithm with uniform crossover for air traffic control. Computers & Operations Research 36 (2009) 245–259. doi:10.1016/j.cor.2007.09.005
