научная статья по теме ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С САМООБУЧЕНИЕМ Кибернетика

Текст научной статьи на тему «ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С САМООБУЧЕНИЕМ»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 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 рублей.

Показать целиком