Генетический алгоритм для задачи максимизации заданной целочисленной функции

 

 

Содержание

 

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	3
Глава 1
Генетические алгоритмы. История развития, основные понятия. Простой генетический алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	4
1.1 История эволюционных вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .	4
1.2 Символьная модель простого  ГА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	4
1.3 Работа простого ГА. Отбор в группу размножения, кроссовер, мутация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	5
1.4 Шимы и строящие блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	8
Глава 2
Генетический алгоритм для задачи максимизации заданной целочисленной функции. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	10
2.1 Применимость ГА к задаче максимизации значения функции . . . . . .	10
2.2 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	10
2.3 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	11
2.4 Результаты работы и выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	12
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	14
Список использованных источников . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	15
Приложение	16

 

Введение

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

Теория эволюции, впервые представленная Чарльзом Дарвином в работе «Происхождение видов путём естественного отбора» [5], оказала огромное влияние на мировоззрения людей. Несмотря на то, что работа содержала ряд ошибочных положений, в ней был выявлен главный механизм развития: отбор в сочетании с изменчивостью. Во многих случаях специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

 

Глава 1

Генетические алгоритмы. История развития, основные понятия. Простой генетический алгоритм.

 

1.1 История эволюционных вычислений

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными стали генетические алгоритмы и классификационные системы Холланда, опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги "Адаптация в естественных и искусственных системах" [6], ставшей классикой в этой области. В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел и Уолш. Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

 

1.2 Символьная модель простого ГА

Цель в оптимизации с помощью ГА состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям. Чтобы реализовать генетический алгоритм, нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений.

Структура данных генетического алгоритма обычно состоит из одной хромосомы. Как правило, хромосома - это битовая строка.

Каждая хромосома представляет собой конкатенацию ряда подкомпонентов, называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в ГА. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров

Чтобы оптимизировать структуру, используя ГА, нужно задать некоторую меру качества для каждого решения в пространстве поиска. Для этой цели используется функция приспособленности (фитнес-функции). В функциональной максимизации целевая функция часто сама выступает в качестве функции приспособленности; для задач минимизации целевую функцию следует инвертировать и сместить затем в область положительных значений.

 

1.3 Работа простого ГА. Отбор в группу размножения, кроссовер, мутация

Имеются много способов реализации идеи биологической эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме.

НАЧАЛО /* простой генетический алгоритм*/

Создать начальную совокупность структур (популяцию)

Оценить каждую структуру

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* новая итерация (поколение)

Применить оператор отбора

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две структуры (родители) из множества предыдущей итерации

Применить оператор скрещивания с заданной вероятность к выбранным структурам и получить две новые структуры (потомки)

Оценить эти новые структуры

Если оператор скрещивания не применяется, то потомки становятся копиями своих родителей

Поместить потомков в новое поколение

КОНЕЦ

Применить оператор мутации с заданной верояностью

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ

Простой ГА случайным образом генерирует начальную популяцию особей. Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не сменится заданное число поколений. Может использоваться и какой-либо другой критерий останова. На каждом поколении ГА реализуется отбор особей в группу размножения пропорционально приспособленности, одноточечный оператор кроссинговера и оператор мутации. Каждой особи назначается вероятность Ps(i), равная отношению ее приспособленности к суммарной приспособленности популяции.

Затем происходит отбор особей в группу размножения. Простейший пропорциональный отбор - рулетка (roulette-wheel selection, Goldberg, 1989c) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью будут выбираться с большей вероятностью, чем особи с низкой приспособленностью.

После отбора n выбранных особей подвергаются кроссоверу (рекомбинации) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

Например, предположим, один родитель состоит из 10 нолей, а другой - из 10 единиц. Пусть из 9 возможных точек разрыва выбрана точка 3. Родители и их потомки показаны ниже.

			Кроссовер
Родитель 1	0000000000	000~0000000		->	111~0000000		1110000000	Потомок 1
Родитель 2	1111111111	111~1111111		->	000~1111111		0001111111	Потомок 2

Далее выполняются операторы мутации. В строке, которая подвергается мутации, каждый бит с вероятностью Pm изменяется на противоположный. Популяция, полученная после мутации, записывает поверх.

В настоящее время исследователи ГА предлагают много других операторов отбора, кроссовера и мутации. Например, турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2. Элитные методы отбора гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссовера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора. В двухточечном кроссовере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. В равномерном кроссовере каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.

 

1.4 Шимы  и строящие блоки.

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

Шима - это строка длины l (что и длина любой строки популяции), состоящая из знаков алфавита {0; 1; *}, где {*} - неопределенный символ. Каждая шима определяет множество всех бинарных строк длины l, имеющих в соответствующих позициях либо 0, либо 1, в зависимости от того, какой бит находится в соответствующей позиции самой шимы. Например, шима, 10**1, определяет собой множество из четырех пятибитовых строк {10001; 10011; 10101; 10111}. У шим выделяют два свойства - порядок и определенная длина. Порядок шимы - это число определенных битов ("0" или "1") в шиме. Определенная длина - расстояние между крайними определенными битами в шиме. Например, вышеупомянутая шима имеет порядок o(10**1) = 3, а определенная длина d(10**1) = 4.

Строящие блоки - это шимы обладающие:

1. высокой приспособленностью,
2. низким порядком,
3. короткой определенной длиной.

Приспособленность шимы вычисляется как среднее приспособленностей битовых строк, которые она определяет.

После процедуры отбора остаются только строки с более высокой приспособленностью. Следовательно, строки, которые являются примерами шим с высокой приспособленностью, выбираются чаще. Кроссовер реже разрушает шимы с более короткой определенной длиной, а мутация реже разрушает шимы с низким порядком. Поэтому такие шимы имеют больше шансов переходить из поколения в поколение. Холланд [6] показал, что, в то время как ГА явным образом обрабатывает n строк на каждом поколении, неявно обрабатываются порядка n3 таких коротких шим низкого порядка и с высокой приспособленностью (полезных шим, "useful schemata"). Он называл это явление неявным параллелизмом. Для решения реальных задач, присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей.

 

Глава 2

Генетический алгоритм для задачи максимизации заданной целочисленной функции.

 

2.1 Применимость ГА к задаче максимизации значения функции

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