Линейное генетическое программирование
- «Линейное генетическое программирование» не имеет отношения к « линейному программированию ».
Линейное генетическое программирование (ЛГП) [1] — это особый метод генетического программирования , при котором компьютерные программы в популяции представлены как последовательность инструкций императивного языка программирования или машинного языка . Прилагательное «линейный» связано с тем фактом, что последовательность инструкций обычно выполняется линейным образом. Как и в других программах, поток данных в LGP можно смоделировать в виде графа, который будет визуализировать потенциальное многократное использование содержимого регистров и существование структурно неэффективного кода ( интронов ), которые являются двумя основными отличиями этого генетического представления от более распространенного дерева. Вариант генетического программирования (TGP). [2] [3] [4]
Как и другие методы генетического программирования, линейное генетическое программирование требует ввода данных для запуска популяции программы. Затем выходные данные программы (ее поведение) сравниваются с некоторым целевым поведением с использованием функции приспособленности. Однако LGP, как правило, более эффективен, чем древовидное генетическое программирование, из-за двух его основных отличий, упомянутых выше: промежуточные результаты (хранящиеся в регистрах) могут использоваться повторно, и существует простой алгоритм удаления интронов. [1] который можно выполнить для удаления всего неэффективного кода перед запуском программ с нужными данными. Эти два различия часто приводят к компактным решениям и существенной экономии вычислительных ресурсов по сравнению с сильно ограниченным потоком данных в деревьях и общим методом выполнения всех узлов дерева в TGP.
Линейное генетическое программирование со значительным успехом применяется во многих областях, включая системное моделирование и управление системами. [5] [6] [7] [8]
Линейное генетическое программирование не следует путать с линейными древовидными программами в древовидном генетическом программировании, программой, состоящей из переменного числа унарных функций и одного терминала . Обратите внимание, что GP линейного дерева отличается от генетических алгоритмов битовой строки , поскольку популяция может содержать программы разной длины и может существовать более двух типов функций или более двух типов терминалов. [9]
Примеры программ LGP [ править ]
Поскольку программы LGP в основном представлены линейной последовательностью инструкций, их легче читать и использовать, чем их древовидные аналоги. Например, простая программа, написанная для решения задачи о булевой функции с тремя входами (в R1, R2, R3) и одним выходом (в R0), может выглядеть так:
R4 = R2 И R3 R0 = R1 ИЛИ R4 R0 = R3 И R0 R4 = R2 AND R4 # Это неэффективная инструкция R0 = R0 ИЛИ R2 R1, R2, R3 должны быть объявлены как регистры ввода (только для чтения), а R0 и R4 — как регистры вычислений (чтение-запись). Эта программа очень проста и содержит всего 5 инструкций. Но операторы мутации и кроссовера могли бы увеличить длину программы, а также содержание каждой ее инструкции.
Обратите внимание, что одна инструкция является неэффективной или интронной (отмеченной), поскольку она не влияет на выходной регистр R0. Распознавание этих инструкций является основой алгоритма удаления интронов, который используется для анализа кода перед выполнением. Технически это происходит путем копирования индивидуума, а затем однократного удаления интрона. Копия с удаленными интронами затем выполняется столько раз, сколько определяется количеством обучающих случаев. Примечательно, что первоначальный индивидуум остается нетронутым, чтобы продолжать участвовать в эволюционном процессе. Только выполняемая копия сжимается путем удаления этих «структурных» интронов.
Еще одна простая программа, написанная на языке LGP Slash/A, выглядит как серия инструкций, разделенных косой чертой:
input/ # получает введенные пользователем данные и сохраняет их в регистр F 0 / # устанавливает регистр I = 0 save/ # сохраняет содержимое F в вектор данных D[I] (т.е. D[0] := F) input/ # получает другой ввод, сохраняет в F add/ # добавляет к F текущие данные, на которые указывает I (т.е. F := F + D[0]) выход/. # выходных данных являются результатом F Представляя такой код в формате байт-кода , т.е. как массив байтов, каждый из которых представляет отдельную инструкцию, можно выполнять операции мутации , просто изменяя элемент такого массива.
См. также [ править ]
- Мультивыраженное программирование
- Декартово генетическое программирование
- Грамматическая эволюция
- Генетическое программирование
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б М. Брамейер, В. Банжаф, « Линейное генетическое программирование », Спрингер, Нью-Йорк, 2007 г.
- ^ Брамайер, М.: « О линейном генетическом программировании. Архивировано 29 июня 2007 г. в Wayback Machine », Дортмунд, 2003 г.
- ^ В. Банцхаф, П. Нордин, Р. Келлер, Ф. Франконе, Генетическое программирование - Введение , Морган Кауфманн, Гейдельберг/Сан-Франциско, 1998 г.
- ^ Поли, Р.; Лэнгдон, ВБ; Макфи, Северная Каролина (2008). Полевое руководство по генетическому программированию . Lulu.com, бесплатно доступный в Интернете. ISBN 978-1-4092-0073-4 .
- ^ М. Брамейер, В. Банжаф, Сравнение линейного генетического программирования и нейронных сетей в интеллектуальном анализе медицинских данных », IEEE Transactions on Evolutionary Computation , 5 (2001) 17-26
- ^ А. Гювен, Линейное генетическое программирование для моделирования суточного расхода временных рядов , J. Earth Systems Science , 118 (2009) 137-146
- ^ Р. Ли, Б. Р. Ноак, Л. Кордье, Дж. Бори, Ф. Харамбат, Уменьшение сопротивления модели автомобиля с помощью линейного генетического программного управления , Эксперименты с жидкостями , 58 (2017) 103
- ^ П.-Ю. Пассаджиа, А. Куанса, Н. Мазелье, Дж. Я. Корнехо Маседа, А. Курта, Управление срывом профиля крыла в реальном времени с обратной связью при больших числах Рейнольдса с использованием линейного генетического программирования , Физика жидкостей , 34 (2022) 045108
- ^ Основы генетического программирования .
Внешние ссылки [ править ]
- Slash/A Язык программирования и библиотека C++, специально разработанные для линейной общей практики.
- DigitalBiology.NET Вертикальная поисковая система для ресурсов GA/GP
- Discipulus Программное обеспечение для генетического программирования
- MicroGP (с открытым исходным кодом) Программное обеспечение для генетического программирования
- [1]