ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 4, с. 24-38
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 004.031.43
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С САМООБУЧЕНИЕМ*
© 2015 г. В. А. Костенко, А. В. Фролов
Москва, МГУ
Поступила в редакцию 28.11.14 г., после доработки 22.12.14 г.
Рассматривается генетический алгоритм с самообучением, ориентированный на решение задач комбинаторной оптимизации. Самообучение заключается в изменении значений вероятностей скрещивания и мутации в зависимости от того, как изменилось значение функции выживаемости после применения операций на очередной итерации алгоритма. Приводятся результаты сравнения предложенного алгоритма с алгоритмом Холланда на задачах построения многопроцессорных расписаний и нахождения подмножества с требуемой суммой.
Б01: 10.7868/80002338815040101
Введение. Генетические алгоритмы (ГА), благодаря своей эффективности, применяются для решения таких задач, как построение оптимальных игровых стратегий, настройка и обучение нейронных сетей, оптимизация запросов в базах данных, построение расписаний [1, 2], различные задачи на графах (раскраска, задача коммивояжера, нахождение паросочетаний), машинного обучения [3] и многих других. Но при построении ГА для решения конкретной задачи требуется решить ряд проблем [1]. Одной из таких проблем является выбор значений вероятностей операций мутации и скрещивания, которые оказывают сильное влияние на эффективность работы алгоритма. В настоящее время не существует никаких теоретических результатов, позволяющих решить эту проблему. В большинстве практических применений генетических алгоритмов значения параметров операций скрещивания и мутации подбираются экспериментально.
Л.А. Растригин еще в 60-х годах предложил алгоритмы случайного поиска с самообучением для решения задач непрерывного математического программирования [4]. В ходе работы такие алгоритмы адаптируются к рельефу целевой функции. Основой методов случайного поиска служит итерационный процесс
Хк +1 = Хк + ак, к = 1, 2, ...,
где Xk — вектор оптимизируемых параметров после k-го шага, ak — некоторый вещественный коэффициент, б — равновероятный случайный вектор.
Алгоритмы случайного направленного поиска с самообучением заключаются в перестройке вероятностных характеристик поиска, т.е. в определенном целенаправленном воздействии на случайный вектор 6. Он перестает быть равновероятным и в результате самообучения приобретает определенное преимущество в направлениях наилучших шагов. Это достигается введением вектора памяти. Алгоритм рекуррентно корректирует значения его компонентов на каждой итерации в зависимости от того, насколько удачным или неудачным был сделанный шаг.
В настоящей статье предлагается введение в классический генетический алгоритм матриц вероятностей мутации и скрещивания и алгоритм изменения значений их элементов в зависимости от того, насколько удачным оказалось применение операции к определенному элементу решения.
1. ГА с индивидуальными параметрами вероятностей мутации и скрещивания. 1.1. Схема алгоритма. В классическом генетическом алгоритме Холланда [5] задаются значения вероятностей мутации и скрещивания, которые служат в качестве вероятностных порогов этих операций. На каждой итерации классического генетического алгоритма используются одни и те же значения этих параметров. Каждый элемент S популяции представляет собой закодированную строку-решение X:
* Работа выполнена при частичной финансовой поддержке Министерства образования и науки Российской Федерации. Соглашение № 14.607.21.0070.
Б — X, X — (Х1 Х2... х^ ).
Идея генетического алгоритма с самообучением заключается в введении индивидуальных параметров вероятности операций мутации и скрещивания для каждого элемента х^ строки-решения, а также в дальнейшей коррекции этих элементов на каждой итерации алгоритма в зависимости от того, насколько удачным или неудачным оказалось применение конкретной операции (мутации или скрещивания) к элементу решения.
Матрицы МтШ и Мсг вероятности мутации и скрещивания имеют размер N х Р, где N — число оптимизируемых параметров (обычно совпадает с числом элементов строки-решения), Р — размер популяции. Элементами матриц являются значения вероятностей мутации и скрещивания для каждого 1-го элемента XI решения в]-й строке популяции:
Л! г ты^Я, Р ег ^Н, Р
Мты, — (Щ, у )1 — ! у — 1, Мег — (Щ,у) I — 1,у — 1 •
Общую схему генетического алгоритма с самообучением можно представить следующим образом.
1. Сгенерировать случайным образом начальную популяцию.
2. Вычислить функцию выживаемости для каждой строки популяции.
3. Выполнить операцию селекции, сделать перестановку строк матриц мутации и скрещивания.
4. Выполнить операцию скрещивания:
4.1. Выбрать пары для скрещивания.
4.2. Для каждой выбранной пары:
1) с заданной вероятностью выполнить скрещивание, получить двух потомков;
2) скорректировать значения соответствующих элементов матрицы вероятности скрещивания и сделать перестановку элементов соответствующих скрещиваемым решениям строк;
3) произвести в популяции замену родителей на их потомков.
5. Выполнить операцию мутации, скорректировать значение соответствующего элемента матрицы вероятности мутации.
6. Если критерий останова не достигнут, перейти к шагу 2, иначе завершить работу.
Опишем далее основные операции генетического алгоритма с самообучением.
1.2. Операция мутации. Обозначим символом X = (х1х2 ... хп) "родительское" решение, имеющее номер] в популяции. Для элементов х I заданы ограничения А1 < х-1 < В. Каждое из значений XI имеет целочисленный тип. Введем степень мутации Бт, которая определяет, насколько
сильно могут измениться значения элементов вектора X. Оператор мутации X = т(Х, МтШ, Бт)
порождает новое решение X = (х1 х2... хп) по следующей схеме:
для каждого I = 1, п выбирается случайное число г1 е (0, 1) в соответствии с равномерным законом распределения;
новое решение определяется по следующей формуле:
X — |^(Х Бт) , г 1 <
[х;- иначе.
Здесь т«(х;, Бт) — функция мутации целочисленного значения, которая мутирует отдельные элементы вектора решения X следующим образом [2]:
1. хI представляется как битовая строка, определяется минимальное число необходимых для этого битов: Ь = 1о§2Гв; — А,!, где символами А, В1 обозначены соответственно нижняя и верхняя границы х , а символом Гх! обозначено минимальное целое число, большее или равное х;
2. Значение х представляется в следующем виде:
ь
Х I — л1 + ^ ак 2к,
к — 1
где ак — к-й бит строки;
3) вычисляется максимальное количество мутирующих битов: п х = [(ЬI — 1)(^т + 0.5)];
4) в соответствии с равномерным законом распределения выбирается случайный номер I, 1 < ¡1 < Ь, и в битовой строке инвертируется бит с номером ¡¡: а1 = 1 — ал; данный шаг повторяется п I раз;
5) вычисляется предварительный результат ?! функции мутации с использованием мутированной битовой строки:
Ь
I, = А( + ^ ак 2к;
к = 1
6) результат корректируется исходя из необходимости попасть в интервал Л1 < х 1 < В¡: т*(хь Бт) =
гI + В 1 - А, г 1 < А, г, А1 < г1 < В, г - (В, - А), г, > в.
Таким образом, оператор мутации X = т(Х, МтШ, 8т) действительно зависит от двух параметров: МтШ — матрица вероятности мутации;
8т > 0 — степень мутации (чем больше это число, тем выше вероятность того, что изменения в элементах родительского решения будут большими).
1.3. Операция скрещивания. Обозначим символами X = (х1х2 ... хп) и У = (у1у2 ...уп) "родительские" решения, выбранные для скрещивания и имеющие в популяции номерар и q соответственно, где х, у I — некоторые целочисленные значения. Параметры Рмш и РМАХ определяют пороги вероятности скрещивания, отвечающие за различные варианты обмена фрагментами строк. Оператор скрещивания сг(Х, У, МтШ, Рмш, РМАХ) порождает два новых решения
X = (х1х2...хп) и У = (у1у2...уп) по следующей схеме:
1. Согласно равномерному закону распределения выбирается случайный номер к, 1 < к < п.
2. Вычисляются средние вероятности скрещивания правых частей строк:
сг сг сг
сг тк р + ... + тп р сг тк д + ... + т
_ к, р "Т - • - т п, р рсг _ Шк, д т - - - т '» п, д
п - к + 1 у п - к + 1
3. Для "родительских" решений выбирается случайное число г с равномерным законом распределения.
4. Элементы нового решения определяются по следующим формулам:
сг сг
если рх > Рмах и Ру < Рмт:
у [у,, ,< к,
У 1 _ 1 • /
[ х, I > к;
сг сг
если Рх < РМ1М и Ру > РМАХ:
[ х, ,< к,
ху _ 1 >
Iу ¡, I > к,
у, = у,;
сг сг
если г < Рх и г < Ру :
л 1 X/, /< k,
X, = <
1У/, /> k,
J y, /< k,
У/ = 1 /> k.
1X ,
Оператор скрещивания зависит от одного параметра:
Mcr — матрица вероятности скрещивания.
Поскольку операция скрещивания перемещает оптимизируемые параметры Xj между строками популяции, то соответствующие перемещения после выполнения операции должны быть выполнены и в матрицах вероятности мутации и скрещивания.
Опишем далее несколько способов коррекции элементов матриц вероятностей, которые используются в методах случайного поиска с самообучением [4].
1.4. Абсолютный способ коррекции матриц вероятностей мутации и скрещивания. Зададим параметр 5 изменения значений элементов матриц вероятностей мутации и скрещивания, который определяет скорость их перестройки. Значения элементов матриц вероятностей изменяются в процессе работы генетического алгоритма, тем самым реализуя механизм самообучения, следующим образом.
Если после операции мутации /-го элемента решения, имеющего в популяции номер j, значе-
-, mut
ние функции выживаемости уменьшилось, то элемент mt j матрицы вероятности мутации, соответствующий вероятности мутации данного элемента решения, увеличивается на 5, иначе — уменьшается на 5. При этом значение тти/ должно находиться в пределах от 0.1 до 0.9.
г-. cr cr
Элементы m, j и mk t матрицы вероятности скрещивания, которые определяют вероятности скрещивания для /-го и k-го элементов решений в строках с номерами j и l соответственно, изменяются аналогичным мутации образом. При этом их значения должны находиться в пределах от 0.1 до 0.9.
Такой метод в отличие от классического ГА задает значения параметров
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.