Введение. 
Метагенетический алгоритм оптимизации параметров имитационной модели

Во многих случаях решения задач оптимизации с помощью генетических алгоритмов (ГА) предсказать поведение сложных многопараметрических и многоэкстремальных функций практически невозможно, поэтому предварительные исследования лишь в общем позволяют определить тенденцию влияния различных генетических операторов на эффективность ГА [1,3]. При создании алгоритмов обработки информации на основе ГА необходимо в каждом конкретном случае обеспечить автоматический подбор таких параметров алгоритма, которые обеспечивают его наибольшую эффективность. Поставленная задача может быть решена на основе использования внешнего ГА.

генетический алгоритм микропроцессорный розенброк.

Разработка метагенетического алгоритма

Алгоритм выбора параметров ГА с помощью ГА будем называть метагенетическим алгоритмом. Функционирование такого алгоритма будем рассматривать на примере оптимизации функций с одним локальным экстремумом (F1-функции Розенброка) и с многими экстремумами (F7-функции Растригина) [2]. Алгоритм выбора генетических операторов относится к алгоритму комбинаторной оптимизации и разрабатывается на основе двухэтапного ГА. На первом этапе (внешний ГА) определяются искомые операторы и, возможно, другие параметры, например, размер популяции, процент скрещивания и мутации и т. д.

В качестве генов в хромосоме внешнего ГА будем использовать поля, представленные на рис. 1.

Рис. 1 Представление хромосомы для внешнего ГА

На второй ступени (внутренний ГА) определяется наилучшее приближение к экстремуму для каждой хромосомы внешнего ГА.

Хромосома внутреннего ГА задается в соответствии с рис. 2, на котором x₁, x₂, …, x_n — параметры оптимизируемой функции. Критерием останова алгоритма является выполнение заданного пользователем числа итераций внешнего ГА, при этом выбирается лучшая из всех популяций хромосома, определяющая искомые параметры ГА.

Рис. 2 Представление хромосомы для внутреннего ГА

Для каждой итерации внешнего ГА реализуется определенное число итераций (поколений) внутреннего ГА.

Предложенный метегенетический алгоритм записывается следующим образом.

Шаг 1. Генерация потенциальных решений для внешнего алгоритма: задание пользователем вариантов реализации параметров внутреннего ГА: видов оператора кроссинговера, мутации, селекции, отбора, числа популяций и других параметров, которые подлежат перебору. Определение числа итераций внутреннего ГА-k. Задание числа внешних итерацийp, других параметров внешнего ГА Шаг 2. Начало работы внешнего алгоритма. Число итераций = p. Размер популяции = r.

Шаг 3. Селекция пар хромосом для скрещивания.

Шаг 4. Выполнить оператор кроссинговера.

Шаг 5. Выполнить мутацию.

Шаг 6. Для всех хромосом внешней популяции запустить внутренний ГА с целью определения функции Fitвнеш.

Шаг 7. Начало работы внутреннего ГА. Сгенерировать популяцию (в виде хромосом рис. 2) для внутреннего ГА. Установить число итераций k; размер популяции q.

Шаг 8. Применить генетические операторы (закодированные в хромосоме внешнего ГА) к популяции внутреннего ГА. Вычислить функции Fitвнутр. для всех хромосом внутренней популяции (вычисление значений функций F1 или F7).

Шаг 9. Сохранить лучшую хромосому популяции. k:=k-1.

Шаг 10. Если k0, то провести отбор q хромосом в соответствии с Fitвнутр. в новую популяцию; перейти к ш. 8.

Шаг 11. Завершить работу внутреннего ГА с выдачей лучшей хромосомы по всем популяциям внутреннего ГА.

Шаг 12. Сохранить лучшую хромосому внешней популяции. p:=p-1.

Шаг 13. Если p0, то провести отбор r хромосом в соответствии с Fitвнеш. в новую популяцию; перейти к ш. 3, иначе перейти к ш. 15.

Шаг 14. Завершить работу внешнего ГА с выдачей лучшей хромосомы по всем популяциям внешнего ГА.

Шаг 15. Останов.

Экспериментальное исследование данного алгоритма проводилось при следующих условиях. Число членов внешней популяции — 30 (максимальное число пар — 10). Число членов внутренней популяции — 50. Число итераций внутреннего алгоритма — от 25 (для функции Розенброка) до 50 (для более сложной функции Растригина), внешнего — 10. К исходной популяции во внешнем алгоритме при выполнении генетических операторов добавлялось по одному потомку от каждой пары.

Типы генетических операторов во внешнем ГА выбирались в соответствии с рекомендациями, полученными в [4]: учитывая сложность комбинаторной задачи в качестве кроссинговера использовался разработанный оператор рекомбинации; оператора мутации — инверсия; оператора отбора — «мягкая схема» .

Общее число вычислений функции Fit (внутреннего и внешнего алгоритма) для функции Розенброка составило около 300 000, для функции Растригина — 600 000−800 000. Для уменьшения вычислительной сложности алгоритмов Конструктора ГА целесообразно исследовать комбинированные алгоритмы [4].

Пример результатов работы предложенного Конструктора при выборе генетических операторов для оптимизации функций Розенброка и Растригина представлен на рис. 3.

Полученные результаты позволяют сделать следующие выводы: для сложных многоэкстремальных функций (например, для исследуемой функции Растригина) целесообразно использовать генетические операторы: кроссинговер — рекомбинация; мутация — инверсия; селекция — «дальнее родство», а для унимодальных (например, функции Розенброка): кроссинговер — одноточечный или двухточечный; мутация — генная; селекция — «ближнее родство» .

Рис. 3. Результаты работы внешнего генетического алгоритма ГА

Применение полученных с помощью внешнего алгоритма параметров ГА, используемых для оптимизации функций Розенброка, позволило сократить число итераций при поиске ~ до k=10−15 (по сравнению с k=25 в предыдущих экспериментах), а функции Растригина до k=20−25 (по сравнению с k=50) при той же точности.