Модификация структуры и параметров генетических алгоритмов с нечеткими операторами, реализуемых гибридными контроллерами

Полный текст

Введение Применение эволюционно-генетических методов AI, и в частности оптимизационных генетических алгоритмов - genetic algorithms (GA), обеспечивает построение достаточно универсальных систем оптимизации с различными архитектурами. В качестве примера таких систем можно привести гидромелиорацию в условиях нехватки оросительной воды. Известные аналитические методы математической оптимизации, применительно к решению задачи распределения водных ресурсов с нелинейной целевой функцией [1], не всегда могут обеспечить оптимальные результаты [2; 3]. Вследствие многочисленных технологических и экологических ограничений для решения задачи оптимизации распределения водных ресурсов требуется применение нелинейных методов, включая искусственного интеллекта - Artificial intelligence (AI) и эволюционно-генетического программирования. Генетические алгоритмы - это стохастические методы глобальной эвристической оптимизации, аналогичные природной эволюции [4-7]. В стандартных GA параметры, такие как вероятность кроссовера Pc и мутации Pm, фиксированы. Однако в адаптивных GA эти параметры динамически изменяются в зависимости от состояния популяции (например, разнообразия, фитнеса индивидов), чтобы избежать преждевременной сходимости или застоя. При этом эффективным является адаптационный подход, обеспечивающий структурно-параметрическую адаптацию GA в процессе его функционирования при решении оптимизационных задач [9-13]. Известны многочисленные исследования методов модификации GA, которые исследуют следующие базовые варианты: проблемно-ориентированная адаптация; процедурно-ориентированная адаптация [14; 15], нечеткие контроллеры, включая реализуемые аппаратно. Первый подход предполагает модификацию базовых компоненты GA (построение хромосомы особи, обоснование способов реализации процедуры отбора с учетом специфики оптимизационной задачи). Процедурно-ориентированная адаптация реализует модификацию архитектуры GA и его параметров в процессе оптимизации, включая начальные значения параметров. К ним относятся адаптивные фитнес-функции [18], а также корректировка значений вероятностей скрещивания Pc и мутации Pm [19; 20], либо увеличение самого гиперпространства возможных решений. В [7] описан подход, использующий значения вероятностей скрещивания и мутации в зависимости от значения фитнес-функции текущих особей. Следует также отметить интересные результаты гибридных параллельных (hybrid parallel) GA [22], а также time series (TS) forecasting GA, основанный на AI [23]. Адаптивная адаптация использует обратную связь в процессе моделирования эволюции для корректировки изменения параметров. Примером такого подхода в эволюционных стратегиях является известное «правило Решенберга», применяемое для корректировки величины вероятности в операторе мутации. В случае, если улучшающая результат мутация превысит порог, например, 0,2, величину мутации следует увеличить, и наоборот. Один из классических подходов к адаптации параметров, предложенный в [6], основан на анализе динамики фитнес-функции. Существуют также подходы на основе энтропии популяции или fuzzy-логики, но они сложнее в реализации. Ряд алгоритмов адаптивной модификации параметров скрещивания и мутация GA реализованы аппаратно, например, по патентам США US-4593367-A «Синтез архитектуры нейронных сетей с использованием генетических алгоритмов»[5]; патент US 6553357 B2 «Метод улучшения архитектуры нейронных сетей с помощью эволюционных алгоритмов».[6] Важной проблемой является выбор таких значений параметров проблемно-ориентированных GA, которые обеспечивают эффективную оптимизацию решения по совокупности критериев точности и быстродействия. Поскольку GA является динамическим и одновременно адаптивным, то неизменные значения его параметров противоречат самой идее эволюционной изменчивости. Отсюда возникает естественный эволюционный подход, основанный на адаптации компонентов GA в процессе его функционирования. Например, можно использовать обратную связь о текущем состоянии процедуры; определенные правила динамической модификации; механизм самоадаптации алгоритма. В [14; 16] приведены базовые подходы к адаптации, системно обеспечивающие повышение эффективности GA, включающие детерминированную адаптацию, адаптивную адаптацию, самоадаптацию и нечеткие контроллеры. Однако проблемы выбора метода модификации архитектуры GA и адаптации его параметров требуют дальнейшего исследования, чему посвящена настоящая статья. 1. Методы и материалы Цель исследования - обоснование метода нечеткой модификации параметров GA как нап-равления комбинаторного искусственного интеллекта (AI), программная реализация и оценка его эффективности тестовой функции. Анализ влияния базовых параметров GA на точность и производительность проводился на известной тестовой задаче OneMax, фитнес-функция для которой имеет вид [5], а максимум известен априори: (1) где i - номер гена в хромосоме; N - количество генов в хромосоме. Генетический оператор селекции реализовывался методом «турнирного отбора» с параметром n = 3 при рекомендациях размера турнира 2-4. Число эпох для сопоставимости получаемых результатов составляло n = 50 во всех экспериментах. Значение вероятности скрещивания (кроссовера) уменьшается для индивидов с высоким фитнесом, чтобы сохранить хорошие решения, и увеличивается для слабых, чтобы стимулировать поисковое разнообразие. Значение параметра вероятности кроссовера адаптируется в зависимости от величины фитнеса родителей: если , (2) где - среднее значение фитнес-функции. Для модификации вероятности мутации Pm использовалась аналогичная зависимость, но для отдельного индивида: (3) Мутация усиливается для индивидов ниже среднего, чтобы ввести больше случайности и избежать локальных оптимумов. Эти формулы применяются итеративно: на каждом поколении вычисляются и , затем для каждого соответствующего оператора (кроссовер/мутация) параметры корректируются. Если выполняется условие (популяция сходится), то и устанавливают в максимальные значения для «разгона» разнообразия. Размер популяции N выбирался в диапазоне 40…100 индивидов в данном исследовании не адаптировался, хотя может быть и динамическим. Малые размеры популяции (20…50) принимают для ускорения вычислений. Большие размеры (50…100) используют для задач с высокой размерностью, чтобы поддерживать разнообразие. Число эпох (поколений) выбиралось в диапазоне до 500 в зависимости от критерия остановки, например отсутствия улучшения в 50 поколениях. Для инициализации использовалась случайная равномерная популяция. Исследование методов адаптивной модификации GA осуществлялось на языке Python без использования специализированной библиотеки, например DEAP, для обеспечения воспроизводимости результатов. 2. Результаты Ниже представлены исследованные специфические особенности GA, протестированные на тестовой задаче OneMax, включая изменение структуры и параметров посредством нечетких контроллеров. 2.1. Исследование влияния структуры генетического алгоритма План проведения численных экспериментов с использованием тестовой задачи OneMax предусматривал: ¡ анализ эффективности генетического оператора мутации и исследование влияния вероятности мутации Pm; ¡ запуск «чистого» генетического оператора отбора без процедур скрещивания и мутации); ¡ результативность добавления процедуры «скрещивания», но без мутации; ¡ запуск и анализ классического варианта алгоритма. При проведении основных численных экспериментов принимались следующие значения базовых параметров GA: ¡ константы GA: population.size = 200; p_crossover = 0,9; p_mutation = 0,1; max_generations = 50; ¡ константа, представляющая длину подлежащей оптимизации битовой строк: one_nax_length = 70…100. Модифицированный код программы включал сохранение списка «values» - значений приспособленностей особей на каждой эпохе, а также их средних и максимальных значений. Результаты исследования конфигурации GA, включающей генетический оператор «чистой» мутации (случайный поиск без скрещивания) в зависимости от значения параметра вероятности мутации, представлены на рис. 1. Максимальное достигнутое значение составило Ymax = 90+ при существенном возрастании разброса между индивидуумами, однако решение задачи поиска максимума в таком варианте не достигнуто. Графический анализ динамики поиска, представленного на рис. 1, также показывает недостаточность принятого количества эпох, равного 50. a b c Рис. 1. Результаты генетического поиска в зависимости от значения вероятностимутации генетического алгоритма (случайный поиск без скрещивания): a - Pm = 0,1; b - Pm = 0,5; c - Pm = 0,9 И с т о ч н и к: выполнено Д.А. Рогачевым. a b c Рис. 2. Результаты генетического поиска максимума при числе эпох n = 50: a - применение только оператора «чистого» отбора без скрещивания и мутации;б - применение оператора «чистой» мутации (случайный поиск без скрещивания),в - совместное применение трех генетических операторов И с т о ч н и к: выполнено Д.А. Рогачевым. Результативность применения только генетического оператора «чистого» отбора без скрещивания и мутации для числа эпох 50 представлена на рис. 2, а. В случае применения только генетического оператора «чистого» отбора без скрещивания и мутации наибольшее достигнутое значение составило Ymax = 61, при этом решение задачи поиска максимума в таком варианте не достигнуто. Результативность применения генетического оператора «чистой» мутации (случайный поиск без скрещивания) представлена на рис. 2, б. Максимальное достигнутое значение составило Ymax = 82, но решение задачи поиска максимума в таком варианте также не достигнуто. Результативность совместного применения всех трех генетических операторов пред-ставлен на рис. 2, в. Максимальное достигнутое значение составило Ymax = 100, что соответствует достижению решения тестовой задачи поиска максимума. Наглядная последовательность фаз решения задачи OneMax классическим GA с тремя генетическими операторами представлена на рис. 3. a b c Рис. 3. Фазы решения поиска максимума при различных значениях числа эпох: a - n = 5; б - n = 25; в - n = 50 И с т о ч н и к: выполнено Д.А. Рогачевым. Отметим, что для отыскания удовлетворительного решения тестовой задачи OneMax принятого количества эпох оказалось достаточно. По результатам проведенных численных экспериментов можно сделать вывод о целесообразности совместного использования всех основных генетических операторов GA (Отбор; Скрещивание; Мутация). В следующих подразделах будут исследованы различные варианты модификации параметров GA, позволяющие повысить его эффективность и устойчивость. 3.2. Адаптация размера популяции особей Гипотезой исследования, проверенной численным исследованием, явилось предположение, что изменение размера численности популяции в процессе реализации GA повлияет на эффективность его применения. В [19] описан алгоритм «пилообразного» GA, в котором объем популяции комбинируется с периодической инициализацией (изменением), что обеспечивает возрастание эффективности алгоритма. Функция изменения объема популяции задается, например, зависимостью (4) с параметрами и . , (4) где - наибольший объем популяции, штук; - период новой инициализации, эпох. Согласно (4), график изменения размера популяции во времени имеет «пилообразную» форму, что обеспечивает компромисс между расширением области поиска и производительностью алгоритма. Возможно также аппаратное решение для адаптивной модификации GA, например, по патенту RU № 2602973 [25]. Для повышения эффективности работы, упомянутый контроллер снабжен блоком оптимизации параметров генетического алгоритма с тремя выходами, соответствующими генетическим операторам отбора, скрещивания и мутации, а также счетчиком итераций. 3.3 Корректировка параметров скрещивания и мутации методом нечеткого контроллера Нечеткие контроллеры (FLC, fuzzy logic controllers) - это мощный инструмент для динамической модификации параметров GA, таких как вероятность скрещивания и мутации. Они основаны на нечеткой логике Л. Заде, которая позволяет обрабатывать неопределенности и качественные знания (например, «разнообразие популяции низкое») через лингвистические переменные и правила. Это особенно полезно в GA, где фиксированные параметры могут привести к преждевременной сходимости или застою, а FLC адаптирует их на основе текущего состояния популяции (например, разнообразия или изменения фитнеса), балансируя между потенциалом поиска (exploration) и популяционным улучшением (exploitation). Применение FLC в GA основано на следующем подходе: на каждом поколении (или через фиксированное число поколений) контроллер оценивает входные метрики популяции, применяет нечеткие правила и формирует корректировки параметров. Это улучшает производительность GA на сложных задачах, таких как оптимизация с мультимодальными функциями. Такой подход описан в литературе как fuzzy adaptive GA (FAGA). Алгоритм применение FLC включает шесть этапов. 1. Определение входов (inputs) включая метрики, отражающие состояние GA. Типичными входами являются: ¡ разнообразие популяции (diversity): генотипическое (например, евклидова дистанция между хромосомами, ED) или фенотипическое (например, , где fmax и favg - максимальное и среднее значение фитнес-функции (ФФ); ¡ изменение ФФ (Δf), например, по зависимости Δf = (favgt - favgt-1) / favgt-1, (5) где t - текущее поколение. Другие метрики: VAC (variance of alleles in chromosomes) или AVA (average variance of alleles). Входы обычно нормализуют в диапазон [0, 1]. 2. Фаззификация (fuzzification) определяет нечеткие множества (membership functions, MF) для каждого входа. Обычно используют треугольные или трапецеидальные функции. Например, для diversity: «Low» (0-0,4), «Medium» (0,3-0,7), «High» (0,6-1,0). Математически степень принадлежности m(x) для треугольной MF с центром c и шириной w можно задать зависимостью m(x) = max(0,1 - |x - c|/w). (6) 3. База правил (rule base): создают правила вида «if-then» на основе экспертного знания. Правила связывают входы с выходами. Например: «(If diversity is Low and Δf is Small), then increase Pm strongly» (чтобы добавить разнообразия). Правила могут быть получены экспертными методами или оптимизированы (например, другим GA). 4. Инференс (inference): используют методы Мамдани или Сугено для агрегации правил. Для каждого правила вычисляют степень активации (min входных значений функций m(x) ), затем агрегируют выходы. 5. Дефаззификация (defuzzification): преобразуют нечеткий вывод в crisp-значение. Популярный метод - центр тяжести (centroid): y = ∑(mi·yi)/∑mi, (7) где yi - центры выходных MF. Новые параметры: Pcnew = Pcold·DPc (8) или Pcnew = Pcold + DPc (9) с ограничениями (например, Pc Î[0, 5, 0, 9]). 6. Интеграция в GA. Периодически вызывают FLC каждые k поколений. Начальные значения вероятностей рекомендуют принимать Pc ≈ 0,6 - 0,8, Pm ≈ 0,01 в зависимости от вида ФФ. 3.4. Численное исследование корректировки вероятностей скрещивания и мутации, реализуемой методом нечеткого контроллера Входами являются следующие величины: ¡ Diversity (PDM1 = fmax/favg), нормализовано в [1, 2] → [0, 1]); ¡ Δf (изменение среднего фитнеса, нормализовано в [-1, 1]). Параметры треугольных функций принадлежности (Membership functions): ¡ для diversity: Low (центр 0,2), Medium (0,5), High (0,8); ¡ для Δf: Negative (центр -0,5), Zero (0), Positive (0,5); ¡ для ΔPc, ΔPm: Small (0,7), Medium (1,0), Big (1,3). База продукционных правил нечеткого вывода включала полный набор из 9 правил «if-then» для двух входов, 3×3. Набор правил, записанный в форме словаря на языке Pethon, представлен на рис. 4. Прямоугольник: скругленные углы: rules = { ('low', 'negative'): {'delta_pc': 'small', 'delta_pm': 'big'}, ('low', 'zero'): {'delta_pc': 'medium', 'delta_pm': 'big'}, ('low', 'positive'): {'delta_pc': 'big', 'delta_pm': 'medium'}, ('medium', 'negative'): {'delta_pc': 'small', 'delta_pm': 'medium'}, ('medium', 'zero'): {'delta_pc': 'medium', 'delta_pm': 'medium'}, ('medium', 'positive'): {'delta_pc': 'big', 'delta_pm': 'small'}, ('high', 'negative'): {'delta_pc': 'small', 'delta_pm': 'small'}, ('high', 'zero'): {'delta_pc': 'medium', 'delta_pm': 'small'}, ('high', 'positive'): {'delta_pc': 'big', 'delta_pm': 'small'}, } Рис. 4. Фрагмент Базы экспертных правил в коде программы ГА И с т о ч н и к: выполнено Д.А. Рогачевым. База экспертных правил для баланса exploration/exploitation включает Ключи: (Diversity_Label, Delta_f_Label) и соответствующие им Значения (small, medium, big) словаря для 'delta_pc' и 'delta_pm'. 3.5. Код на Python для нечеткогоадаптивного генетического алгоритма Рассмотрим пример реализации простого генетического алгоритма с нечетким контроллером для адаптации параметров Pc (вероятность кроссовера) и Pm (вероятность мутации). Для работы с массивами использовалась библиотека NumPy, а для визуализации Matplotlib, отображающая эволюцию фитнес-функции). Fuzzy logic реализован с треугольными функциями принадлежности. Нечеткий вывод использует метод Мамдани без внешних fuzzy-библиотек. Решается задача OneMax: максимизация суммы битов в бинарной хромосоме длины 20/40. Популяция включает 50 индивидов, оптимизируемых в течение 50 поколений. Адаптация параметров происходит на основе метрик разнообразия (diversity) и значения изменения средней величины фитнес-функции. Фрагменты кода для функций одноточечного скрещивания и мутации приведены на рис. 5. Простые функции принадлежности (member-ship functions) μ(x) в [0, 1] треугольного вида с вершинами a, b, c задаются следующим фрагментом (рис. 6). Функция фаззификации для величины разнообразия (diversity) разбивает ее на лингвистические переменные low, medium, high. Она принимает на вход нормализованное в [0, 1] значение разнообразия div, а возвращает словарь с лингвистическими степенями принадлежности. Аналогично для delta принимает на вход нормализованное в диапазон [-1, 1] изменение delta (рис. 7). Значения для выходов: small = 0,7 (снижение), medium = 1,0 (без изменений), big = 1,3 (увеличение) определяет множители для Pc и Pm посредством строки: output_values = {“small”: 0.7, “medium”: 1.0, “big”: 1.3}. Инференс и дефаззификация реализуются методом Mamdani, вычисляющего приближенный центр (centroid), при этом агрегируются правила с min-активацией и вычисляет взвешенное среднее (рис. 8). Такая функция принимает на вход словари принадлежностей переменных div_fuzzy и delta_fuzzy, а возвращает в качестве выходов delta_pc, delta_pm - множители. В коде программы согласно правилам из базы (см. рис. 4) формируются лингвистические значения выходов. Например, если 1-й вход функции принимает лингвистическое значение 'small' и 2-й вход имеет лингвистическое значение 'negative', то параметр 'delta_Pc' принимает лингвистическое значение 'small', а параметр 'delta_Pm' - 'big'. Основной цикл GA с нечеткой адаптацией принимает на вход значение длины хромосомы chrom_length = 70, размер популяции pop_size и число эпох (поколений) Т = 150 и реализует все генетические операторы. Инициализация популяции задает случайные бинарные векторы. Прямоугольник: скругленные углы: def crossover(parent1, parent2, pc): if np.random.rand() < pc: point = np.random.randint(1, len(parent1) - 1) child1 = np.concatenate((parent1[:point], parent2[point:])) child2 = np.concatenate((parent2[:point], parent1[point:])) return child1, child2 return parent1, parent2 # Mutation function: flip bit with probability pm. # Inverts the bit (0->1 or 1->0) for each gene independently. def mutation(individual, pm): for i in range(len(individual)): if np.random.rand() < pm: individual[i] = 1 - individual[i] return individual Рис. 5. Фрагменты кода для функций одноточечного скрещивания и мутации И с т о ч н и к: выполнено Д.А. Рогачевым. Прямоугольник: скругленные углы: def triangular_mf(x, a, b, c): if x <= a or x >= c: return 0.0 elif a < x <= b: return (x - a) / (b - a) else: return (c - x) / (c - b) Рис. 6. Фрагменты кода для вычисления функций принадлежности И с т о ч н и к: выполнено Д.А. Рогачевым. Прямоугольник: скругленные углы: def fuzzify_diversity(div): low = triangular_mf(div, 0, 0.2, 0.4) medium = triangular_mf(div, 0.3, 0.5, 0.7) high = triangular_mf(div, 0.6, 0.8, 1.0) return {'low': low, 'medium': medium, 'high': high} # Fuzzification: for delta_f (fitness function changes). def fuzzify_delta_f(delta): negative = triangular_mf(delta, -1, -0.5, 0) zero = triangular_mf(delta, -0.2, 0, 0.2) positive = triangular_mf(delta, 0, 0.5, 1) return {'negative': negative, 'zero': zero, 'positive': positive} Рис. 7. Фрагменты кода для фаззификации И с т о ч н и к: выполнено Д.А. Рогачевым. Прямоугольник: скругленные углы: def fuzzy_inference(div_fuzzy, delta_fuzzy): delta_pc_num, delta_pc_den = 0, 0 delta_pm_num, delta_pm_den = 0, 0 for (div_l, delta_l), outputs in rules.items(): activation = min(div_fuzzy.get(div_l, 0), delta_fuzzy.get(delta_l, 0)) if activation > 0: delta_pc_num += activation * output_values[outputs['delta_pc']] delta_pc_den += activation delta_pm_num += activation * output_values[outputs['delta_pm']] delta_pm_den += activation delta_pc = delta_pc_num / delta_pc_den if delta_pc_den > 0 else 1.0 delta_pm = delta_pm_num / delta_pm_den if delta_pm_den > 0 else 1.0 return delta_pc, delta_pm Рис. 8. Фрагмент кода дефаззификации И с т о ч н и к: выполнено Д.А. Рогачевым. Типичные результаты работы GA для разных значений размера популяции представлены на рис. 9. В качестве выходного значения определяется лучшее рассчитанное значение фитнес-функции, получаемое в последнем поколении, и отрисовывает графики лучшего значения ФФ индивида и ее среднее значение по всей популяции. а b Рис. 9. Результаты работы GA с нечетким контроллером: а - chrom_length = 70, pop_size = 70; б - chrom_length = 70, pop_size = 90 И с т о ч н и к: выполнено Д.А. Рогачевым. На рис. 9 алгоритм успешно сходится к глобальному оптимуму задачи OneMax (фитнес-функция = 70, когда все биты = 1). Это ожидаемо для простой задачи с длиной хромосомы 70 при 150 поколениях, но нечеткий контроллер помогает адаптировать параметры, например, при низком разнообразии (популяция сходится). Нечеткий контроллер увеличивает Pm для добавления случайности, а при улучшении фитнес-функция - усиливает Pc для exploitation. В среднем сходимость происходит за 80…100 поколений (на основе типичных запусков), но из-за стохастичности инициализации алгоритма результат может варьироваться. Если запустить несколько раз, среднее значение фитнес-функции растет быстро в начале (благодаря высокой начальной Pc), затем стабилизируется. Нечеткая адаптация делает GA более робастным по сравнению с архитектурой с фиксированными параметрами. Возможно применение средства адаптации в форме нечеткого логического «контроллера», программно/аппаратно реализующего систему нечетких продукционных правил логического вывода. Заключение Проведенные на основе системного подхода исследования структур, параметров и результатов функционирования GA позволили обобщить направления модификации GA. Исследование влияния структуры и параметров GA на время и точность оптимизации функции приспособленности, проведенные на задаче OneMax с бинарным кодированием хромосомы, позволили сформулировать рекомендации по выбору макропараметров и обоснованно выбирать варианты модификации алгоритмов для конкретных предметных областей, включая распределение ограниченных водных ресурсов в острозасушливых условиях. Решение задачи эволюционно-генетической оптимизации показало применимость нечеткого контроллера для GA. Численными экспериментами показано, что среднее значение фитнес-функции быстро растет в начале процесса оптимизации благодаря высокому значению начальной вероятности Pc), затем стабилизируется. Нечеткая адаптация делает GA более робастным по сравнению с фиксированными параметрами.

Об авторах

Дмитрий Алексеевич Рогачев

Федеральный научный центр гидротехники и мелиорации им. А.Н. Костякова

Email: Rogachev.soft@gmail.com
ORCID iD: 0009-0003-4014-4770
SPIN-код: 1948-7354

кандидат технических наук, ведущий научный сотрудник

Российская Федерация, 127434, г. Москва, ул. Большая Академическая, д. 44, корп. 2

Алексей Фруминович Рогачев

Волгоградский государственный аграрный университет

Автор, ответственный за переписку.
Email: rafr@mail.ru
ORCID iD: 0000-0002-3077-6622
SPIN-код: 8413-5020

доктор технических наук, профессор кафедры математического моделирования и информатики

Российская Федерация, 400005, г. Волгоград, пр-т Ленина, д. 28

Список литературы

Дополнительные файлы