Генетические алгоритмы как перспективный метод оптимизации

Размещено на http://www.allbest.ru/

Генетические алгоритмы как перспективный метод оптимизации

Лоскутов И.В.

Шульгин А.О.

The article describes a genetic algorithm application for the decision of combinatory tasks or optimization various kind of functions. The feature of genetic algorithms is based on natural evolution in the nature and started with principles of inheritance and evolutionary selection. The modeling of natural process evolution and its application for the decision of optimization problems is a paramount problem for the given direction. The genetic algorithm is the most recent product of the artificial intelligence techniques.

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

Одна из основных проблем в науке и технике сегодня - это разработка теории, математических методов и моделей для эффективного принятия решения в сложных системах. Сложность систем, их уникальность приводит к необходимости поиска новых направлений моделирования и синтеза. Эти направления в настоящее время активно разрабатываются и составляют основу понятия “искусственный интеллект”. Именно на пути применения перспективных интеллектуальных технологий большинство исследователей надеется найти решение стоящих перед учеными и инженерами проблем и задач. При этом важнейшими задачами являются оптимизация сложных систем, построение интеллектуальных искусственных систем поддержки принятия решений, моделирование процессов эволюционного развития природы.

В последние два десятилетия при оптимизации сложных систем исследователи все чаше применяют природные механизмы поиска наилучших решений. Эти механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде па протяжении миллионов лет. Сегодня интенсивно разрабатывается научное направление Natural Computing “Природные вычисления”, объединяющее методы с природными механизмами принятия решений.

Целью настоящей статьи является изложение теоретических основ и примеров практического применения генетических алгоритмов (ГА) как нового перспективного метода оптимизации. Статья состоит из трех частей: в первой части излагается теория генетических алгоритмов, во второй - описывается пример генетической оптимизации, в третьей части дается обзор применения генетических алгоритмов.

История эволюционных вычислений началась с разработки ряда независимых моделей, среди которых были генетические алгоритмы и классификационные системы, созданные американским исследователем Дж. Холландом. Он предложил использовать методы и модели развития органического мира на Земле в качестве механизма комбинаторного перебора вариантов при решении оптимизационных задач [1]. Этот алгоритм, послуживший основой для дальнейших исследований в теории ГА, относился к классу последовательных алгоритмов, не обладал адаптивными свойствами, оперировал простыми бинарными строками и одной функцией соответствия. Компьютерные реализации этого механизма получили название “генетические алгоритмы”.

Согласно репродуктивному плану Холланда [1], генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:

Конструируется начальная популяция. Вводится начальная точка отсчета поколений t=0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.

Устанавливается значение t=t+1. Выбираются два родителя (хромосомы) для скрещивания. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.

Формируется генотип потомка. Для этого случайным образом выбирается один из потомков A(t), который сохраняется как член новой популяции. Далее к потомку A(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как A'(t).

Обновление текущей популяции путем замены случайно выбранной хромосомы на A'(t).

Определение приспособленности A'(t) и пересчет средней приспособленности популяции.

Если t = t^*, где t^* - заданное число шагов, то выполняется переход к этапу 7, в противном случае - переход к этапу 2.

Конец работы.

Основная идея эволюции, заложенная в различные конструкции генетических алгоритмов, проявляется в способности “лучших” хромосом оказывать большее влияние на состав новой популяции за счет длительного выживания и более многочисленного потомства.

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

Мутация - это фоновая операция, производящая случайное изменение в различных хромосомах. Наипростейший вариант мутации состоит в случайном изменении одного или более генов [2].

Скрещивание является главной генетической операцией. Эта операция выполняется над двумя хромосомами - родителями и создает потомка путем комбинирования особенностей обоих родителей [3].

Рисунок 1 - Применение генетических операторов

Рассмотрим нелинейную целевую функцию с ограничениями:

, где , .

Требуется найти: .

1. Для реализации генетического алгоритма необходимо закодировать оптимизируемые параметры в двоичные строчки. Длина строчки зависит от требуемой точности. Например, пусть переменная x_j имеет интервал изменения [a_j, b_j], и требуемая точность - пять знаков после запятой. В этом случае интервал изменения переменной x_j должен быть разбит как минимум на квантов. Требуемое число битов m_j, необходимых для кодирования, находится по формуле:

(1),

где - интервал изменения переменной, k - требуемая точность. Тогда по (1): m₁=16, m₂=19. Суммарная длина хромосомы, для кодирования параметров: , m=35 бит. Генерируется 10 случайных популяций, где каждая хромосома имеет длину 35 бит: v₁ =[01000001010100101001101111011111110],

v₂ =[10001110101110011000000010101001000],…,

v₁₀ =[01111101001110101010000010101101010].

2. Вычисляются по сгенерированным популяциям значения переменных x₁ и x₂:

(2).

Для первой популяции десятичные значения: x₁ - 16722, x₂ - 319230, тогда по (2): , x₁=0.6531,, x₂= 3.19198.

Соответствующие значения переменных: v₁=[x₁,x₂]=[0.653097, 3.191983], v₂=[x₁,x₂]=[0.834511,2.809287],…, v₁₀=[x₁, x₂]=[0.793504,3.259521].

3.Следующим шагом оценивается функция соответствия для каждой хромосомы: eval(v₁)=f(0.653097,3.191983)=20.432394, eval(v₂)=f(0.834511,2.809287)= -4.133627,…, eval(v₁₀)=f(0.793504,3.259521)=6.201905. Очевидно, что хромосома v₃ наиболее сильная, а хромосома v₆ наиболее слабая.

4. Наибольшее распространение на практике получил подход, называемый колесо рулетки [3]. Отбор осуществляется на основе некоторой функции распределения, которая строится пропорционально вычисленным функциям соответствия сгенерированных вариантов - хромосом.

4.1 Вычисляем общую функцию соответствия популяции:

(3),

F=242.208919.

4.2 Вычисляем вероятность отбора p_k для каждой хромосомы v_k:

F (4),

p₁=0.181398, p₂=0.079973,…, p₁₀=0.122645.

4.3 Вычисляем совокупную вероятность q_k для каждой хромосомы v_k:

(5),

где k =1,…,размер популяции. q₁=0.181398, q₂=0.181398,…, q₁₀=0.181398.

4. Вращаем колесо рулетки 10 раз и каждый раз отбираем одну хромосому для новой популяции. Генерируем случайное число r из интервала [0,1]. Случайная последовательность из интервала [0,1] имеет вид: 0.301431, 0.322062, …, 0.197577. Если , то выбираем первую хромосому v₁; иначе выбираем k-ю хромосому такую, что. Первое число r₁=0.301431 больше чем q₂ и меньше чем q₃. Это означает, что отбирается хромосома v₃. Второе число r₂=0.322062 также больше чем q₂ и меньше чем q₃. Следовательно, опять отбираем хромосому v₃ для новой популяции и так далее. Получим новую популяцию:

v?₁ =[11111000111000001000010101001000110] (v₃),

v?₂ =[11111000111000001000010101001000110] (v₃),...,

v?₁₀ =[10001110101110011000000010101001000] (v₂).

5. Применяем оператор мутации, тем самым изменяем один или несколько генов с вероятностью, равной коэффициенту мутации. Зададим коэффициенту мутации значение p_m=0.01, так что в среднем 1% всех битов популяции подвергнется операции мутации. Число битов во всей популяции составляет бит. Поэтому в среднем в каждом поколении мутирует 3.5 бита. Каждый бит имеет одинаковый шанс подвергнуться мутации. Таким образом, генерируется последовательность случайных чисел r_k, где (k=1…350) из интервала [0,1]. Предполагая, что мутируют следующие гены: Номера хромосом - 4, 5, 7, 10; Позиции бита в хромосоме - 6, 32, 1, 32.

После применения оператора мутации получается следующая популяция:

v??₁=[11111000111000001000010101001000110], v??₂=[11111000111000001000010101001000110],…, v??₁₀=[10001110101110011000000010101000000].

Соответствующие десятичные значения переменных x₁ и x₂ , а так же значения функции соответствия имеют вид: eval(v?₁)=f(1.083310,2.874312)=28.978472, eval(v?₂)=f(1.083310,2.874312)=28.978472,…, eval(v?₁₀)=f(0.834511,2.809232)=-4.138564. Таким образом, завершена одна итерация генетического алгоритма. Проделав 1000 итераций, получаем наилучшую хромосому в 419-м поколении: v^*=[01000011000100110110010011011101001], eval(v^*)=f(0.657208,2.418399)=31.313555. Получаем .

Рассмотрим основные направления применения генетических алгоритмов. К ним в первую очередь относятся: нахождение экстремумов математических функций, аппроксимация функций, параметрическая идентификация, решение задач управления сложными объектами, синтез и обучение нейронных сетей. Основные преимущества генетических алгоритмов приведены ниже в таблице:

Таблица 1 - Преимущества генетических алгоритмов

Такой список достоинств, проверенных при практическом решении целого ряда задач, подтверждает перспективность использования генетических алгоритмов [3].

Генетические алгоритмы опираются на естественную эволюцию в природе и исходят из принципов наследования и эволюционного отбора. Моделирование процесса естественной эволюции и его применение для решения задач оптимизации - это первостепенная задача для данного направления. В статье на примере задачи нахождения экстремума функции показано, как в алгоритмы решения задач оптимизации реализовать на языке генетических алгоритмов: случайность, многократность взаимодействия, основные генетические операторы. Проведенный нами анализ показывает, что эффективность генетических алгоритмов увеличивается с ростом размерности задачи оптимизации.

ЛИТЕРАТУРА

1. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. - London: Bradford book edition, 1994. - 211 с.

2. Вороновский Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев. - X. : ОСНОВА, 1997. - 112 с.

3. Букатова И.Л. Эволюционное моделирование и его приложения / И. Л. Букатова. - М. : Наука, 1979. - 231 с.

Размещено на Allbest.ru