Особенности генетических алгоритмов

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

14

Содержание

Введение

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

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

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

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

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

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

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

2.2 Постановка задачи

2.3 Описание алгоритма

2.4 Результаты работы и выводы

Заключение

Список использованных источников

Приложение

Введение

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

Теория эволюции, впервые представленная Чарльзом Дарвином в работе «Происхождение видов путём естественного отбора» [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 строк на каждом поколении, неявно обрабатываются порядка n³ таких коротких шим низкого порядка и с высокой приспособленностью (полезных шим, "useful schemata"). Он называл это явление неявным параллелизмом. Для решения реальных задач, присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей.

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

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

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

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

2.2 Постановка задачи

В курсовой работе исследуется следующая оптимизационная задача:

Пусть задана целочисленная функция от четырёх переменных.

f(x1, x2, x3, x4) = |x1 - x2| + |x3 - x4| + |x1 * Sin(x2)|,

где x1, x2, x3, x4 - целые числа из отрезка [0, 1024]

Требуется найти максимум данной функции.

2.3 Описание алгоритма

ГА будет состоять из следующих шагов:

1. Генерация начальной популяции. В качестве хромосомы используется битовая строка из 40 элементов. Строка логически разбивается на 4 равные части по 10 бит, каждая из которых отвечает за свою переменную. Т.о. кодируются значения переменных от 0 до 1023. Начальная популяция состоит из n (рассмотрим варианты 100 и 200) особей, генотипы которых генерируются случайным образом.

2. Вычисляется значение фитнес-функции каждой особи, по которому производится сортировка. В качестве фитнес-функции можно взять значение максимизируемой функции, так как она удовлетворяет требованиям, предъявляемым к фитнес-функции (неотрицательна, значение фитнес функции лучших особей больше).

3. Выбор пары особей для размножения. Выбор происходит посредством метода рулетки. Для каждой особи вычисляется отношение её значения функции приспособленности к суммарному значению функции приспособленности популяции. В зависимости от этого значения особи выделяется некоторое количество ячеек в массиве рулетки. Выбор особей для составления пары происходит независимо в результате двух последовательных запусков рулетки.

4. К выбранной на предыдущем шаге паре особей применяется оператор одноточечного кроссинговера. Точка кроссинговера выбирается равновероятно, случайным образом. Из полученных потомков случайным образом выбирается один, который добавляется в новую популяцию.

5. Повторение пп.2-3 n раз. В результате на этом этапе получаем новую популяцию из n особей. Т.к. выбор родителей производится по числу особей в популяции (n раз), велика вероятность того, что в новую популяцию попадёт большое количество потомков скрещивания наиболее удачных особей. С другой стороны, у более слабых особей остаётся шанс попасть в новую популяцию, а значит меньше шанс «потерять» хорошие признаки, присущие в целом не самым удачным особям.

6. Этап мутации. Каждая особь из новой популяции мутирует с вероятностью 1%. То есть оператор мутации применяется к 1% особей. Оператор мутации заключается в инвертировании случайно выбранного гена в генотипе особи.

7. В соответствии с логикой элитного отбора добавим в новую популяцию 10% лучших особей прошлого поколения. Для этого отсортируем новую популяцию по значению фитнес-функции и будем последовательно просматривать 10% слабейших особей. Особь заменяется на элитную из прошлого поколения только в случае выигрыша в значении фитнес-функции. Т.е. замена происходит, если текущая особь не превосходит по значению фитнес-функции той, на которую её предполагается заменить.

8. пп.2-6 выполняются некоторое заранее определённое число раз (m).

2.4 Результаты работы и выводы

Тип	Число особей в популяции (n)	Число поколений (m)	Время работы	Результат
I	100	100	36 мс	3025,76
			34 мс	2976,76
			32 мс	3034,19
II	100	200	62 мс	3041,41
			74 мс	3045,39
			69 мс	3035,91
III	200	100	68 мс	3044,39
			53 мс	3041,41
			65 мс	3047,98
IV	200	200	139 мс	3057,99
			128 мс	3035,90
			138 мс	3057,99

Принципиальное отличие настроек II и III (n = 100, m = 200 и n = 200, m = 100) состоит в том, что в первом случае стартовое разнообразие меньше, меньше вероятность получить хорошие решения ещё на этапе генерации популяции, но развитие идёт дольше. То есть с одной стороны, есть опасность «пропустить» правильное решение, попав изначально в локальный максимум. Но в случае удачной стартовой популяции большее число шагов позволит лучше приблизиться к ответу. Соответственно вариант III менее подвержен опасности попадания в локальный максимум, но имеет меньше возможностей для улучшения найденных решений. IV вариант даёт наилучшие результаты как комбинация достоинств II и III вариантов.

Вычисление ответа методом полного перебора займёт порядка 3-4 часов (алгоритмическая сложность О(n⁴), где n=1024. Если считать, что за 1 сек выполняется порядка 10⁸ операций, время работы составит 1024⁴/10⁸/60/60 ? 3,3 часа). Если же зафиксировать значение первой переменной равным 1023 (сделать вывод об этом можно на основе работы алгоритма при больших ограничениях на значения переменных и по результатам работы генетического алгоритма), перебор сократится до O(n³), что позволит получить точное решение: F(1023, 11, 0, 1023) = 3057,99. То есть генетический алгоритм с параметрами n = 200, m = 200 нашёл точное решение за время порядка секунды, тогда как результатов перебора нужно ждать несколько часов.

Заключение

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

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

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

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

применение особенность генетический алгоритм функция

Список использованных источников

1. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования дискретных устройств. - М.: Физматлит, 2007.

2. Сперанский Д.В., Самойлов В.Г., Емельянова О.В. Введение в генетические алгоритмы. - Саратов: Изд-во Сар. гос. ун-та, 2006.

3. Рутковская Д., Пилиньский М., Рутковский Я. Нейронные сети, генетические алгоритмы как нечёткие системы. - М.: Горячая линия - Телеком, 2004.

4. Гладков Л.А., Курейчик В.В, Курейчик В.М. Генетические алгоритмы. - М.: Физматлит, 2007.

5. Дарвин Ч. Происхождение видов путём естественного отбора / Пер. и вводная ст. К.А. Тимирязева. М., 1952.

6. Холланд Дж. Генетические алгоритмы // В мире науки. 1992 № 9-10.

Приложение

class Program

{

static void Main(string[] args)

{

// Число особей в популяции

int initNum = 200;

// Число поколений

int numGen = 200;

Development dev = new Development(initNum);

Genotype g = dev.StartDevelopment(numGen);

Console.WriteLine(g.ToString() + "\nF = {0}\n", g.FitFunction);

Console.ReadLine();

}

}

/// <summary>

/// Класс для описания эволюции

/// </summary>

class Development

{

/// <summary>

/// Метод, реализующий подсчёт фитнес-функции

/// </summary>

/// <returns>Значение фитнес-функции</returns>

public static double GetFitFunction(int x1, int x2, int x3, int x4)

{

return Math.Abs(x1 - x2) + Math.Abs(x3 - x4) +

Math.Abs(x1 * Math.Sin(x2));

}

public static double GetFitFunction(Genotype g)

{

return GetFitFunction(g[0], g[1], g[2], g[3]);

}

Population _p;

/// <summary>

/// Популяция

/// </summary>

public Population Members

{

get{ return _p; }

}

/// <summary>

/// Конструктор с заданным числом особей

/// </summary>

/// <param name="num">Число особей в популяции</param>

public Development(int num)

{

Population.Init();

_p = new Population(num);

Genotype.Init();

}

/// <summary>

/// Метод запуска эволюции

/// </summary>

/// <param name="maxNum">Максимальное число поколений</param>

/// <returns>Особь с наибольшим значением фитнес-функции</returns>

public Genotype StartDevelopment(int maxNum)

{

_p.GenerateRandPopulation();

for (int i = 0; i < maxNum; i++)

{

_p.ChangeGeneration();

}

return _p[_p.Num - 1];

}

}

/// <summary>

/// Класс, описывающий популяцию

/// </summary>

class Population

{

static Random _rg;

/// <summary>

/// Инициализация статического рандомизатора класса

/// </summary>

public static void Init()

{

_rg = new Random();

}

Genotype[] _gen;

/// <summary>

/// Генотипы популяции

/// </summary>

public Genotype[] Members

{

get { return _gen; }

}

int _num;

/// <summary>

/// Число особей в популяции

/// </summary>

public int Num

{

get { return _num; }

}

Genotype[] _ngen;

int[] Arr4Roulett;

/// <summary>

/// Конструктор с заданным числом особей

/// </summary>

/// <param name="num">Число особей в популяции</param>

public Population(int num)

{

_gen = new Genotype[num];

_num = num;

}

/// <summary>

/// Генерация исходной популяции

/// </summary>

public void GenerateRandPopulation()

{

for (int i = 0; i < Num; i++)

{

_gen[i] = new Genotype();

_gen[i].GenerateRandGenotype();

}

}

/// <summary>

/// Доступ к генотипу из популяции

/// </summary>

/// <param name="idx">Порядковый номер</param>

/// <returns>Генотип</returns>

public Genotype this[int idx]

{

get { return _gen[idx]; }

}

/// <summary>

/// Метод, реализующий одноточечный кроссинговер

/// </summary>

/// <param name="m">1 родитель</param>

/// <param name="f">2 родитель</param>

/// <param name="s">1 потомок</param>

/// <param name="d">2 потомок</param>

public static void MakeCrossingover(Genotype m, Genotype f,

out Genotype s, out Genotype d)

{

int place = _rg.Next(1, Genotype.Length);

s = new Genotype();

d = new Genotype();

s.MakeCross(place, m, f);

d.MakeCross(place, f, m);

}

/// <summary>

/// Метод смены поколения

/// </summary>

public void ChangeGeneration()

{

Array.Sort(_gen);

Arr4Roulett = new int[1000];

GenerateArr4Roulette();

_ngen = new Genotype[Num];

for (int i = 0; i < _gen.Length; i++)

{

AddScion(i);

}

_gen = _ngen;

Array.Sort(_gen);

MakeMutation();

AddSomeParents();

Array.Sort(_gen);

}

/// <summary>

/// Мутация (вероятность мутации 1% для каждой особи)

/// </summary>

public void MakeMutation()

{

for (int i = 0; i < Num; i++)

{

if (_rg.Next(100) == 4)

{

_gen[i].MakeMutation();

}

}

}

/// <summary>

/// Добавляем в популяцию "лучших" из предыдущего поколения (1%)

/// </summary>

public void AddSomeParents()

{

int num = _gen.Length / 100 * 10; //10%

int i = num - 1;

int j = _gen.Length - 1;

while (i >= 0)

{

if (_ngen[i].FitFunction < _gen[j].FitFunction)

{

_ngen[i] = _gen[j].Clone();

j--;

}

i--;

}

}

/// <summary>

/// Создание массива для запуска рулетки

/// </summary>

public void GenerateArr4Roulette()

{

double sumVal = 0;

for (int i = 0; i < _gen.Length; i++)

{

sumVal += _gen[i].FitFunction;

}

int idx = 0;

for (int i = 0; i < _gen.Length; i++)

{

int temp = (int)(Math.Floor(_gen[i].FitFunction * 1.0 /

sumVal * 1000));

for (int j = 0; j < temp; j++)

{

Arr4Roulett[idx] = i;

idx++;

}

}

while (idx < 1000)

{

Arr4Roulett[idx] = _rg.Next(_gen.Length);

idx++;

}

}

/// <summary>

/// Добавление потомка

/// </summary>

public void AddScion(int idx)

{

Genotype m = _gen[Arr4Roulett[_rg.Next(1000)]];

Genotype f = _gen[Arr4Roulett[_rg.Next(1000)]];

Genotype s, d;

MakeCrossingover(m, f, out s, out d);

if (_rg.Next(2) == 1)

{

_ngen[idx] = s;

}

else

{

_ngen[idx] = d;

}

}

}

/// <summary>

/// Класс, описывающий генотип

/// </summary>

class Genotype : IComparable<Genotype>

{

public static readonly int NMAX = 1024;

/// <summary>

/// Длина битовой строки

/// </summary>

public static int Length

{

get { return 4 * 10; }

}

static BitVector32.Section[] _s;

static Random _rg;

/// <summary>

/// Инициализация рандомизатора и задание секций битовой строки

/// </summary>

public static void Init()

{

_s = new BitVector32.Section[4];

_s[0] = BitVector32.CreateSection((1 << 10) - 1);

_s[1] = BitVector32.CreateSection((1 << 10) - 1, _s[0]);

_s[2] = BitVector32.CreateSection((1 << 10) - 1, _s[1]);

_s[3] = BitVector32.CreateSection((1 << 10) - 1, _s[2]);

_rg = new Random();

}

BitVector32 _gen;

/// <summary>

/// Значение фитнес-функции особи с данным генотипом

/// </summary>

public double FitFunction

{

get { return Development.GetFitFunction(this[0], this[1],

this[2], this[3]); }

}

/// <summary>

/// Конструктор по умолчанию

/// </summary>

public Genotype()

{

_gen = new BitVector32();

}

/// <summary>

/// Конструктор копирования

/// </summary>

/// <param name="g">Копируемый генотип</param>

public Genotype(Genotype g)

{

_gen = g.ByteGens;

}

/// <summary>

/// Конструктор генотипа по значениям переменных

/// </summary>

public Genotype(int x1, int x2, int x3, int x4)

{

_gen[_s[0]] = x1;

_gen[_s[1]] = x2;

_gen[_s[2]] = x3;

_gen[_s[3]] = x4;

}

/// <summary>

/// Метод создания копии

/// </summary>

/// <returns>Копия</returns>

public Genotype Clone()

{

Genotype g = new Genotype(this);

return g;

}

/// <summary>

/// Метод генерации генотипа

/// </summary>

public void GenerateRandGenotype()

{

for (int i = 0; i < 4; i++)

{

_gen[_s[i]] = _rg.Next(NMAX);

}

}

/// <summary>

/// Метод получения потомка в результате кроссинговера

/// </summary>

/// <param name="place">Точка кроссинговера</param>

/// <param name="m">1 родитель</param>

/// <param name="f">2 родитель</param>

public void MakeCross(int place, Genotype m, Genotype f)

{

for (int i = 0; i < place; i++)

{

this._gen[1 << i] = m.ByteGens[1 << i];

}

for (int i = place; i < Genotype.Length; i++)

{

this._gen[1 << i] = f.ByteGens[1 << i];

}

}

/// <summary>

/// Доступ к участкам, отвечающим за каждую из переменных

/// </summary>

/// <param name="idx">Индекс переменной (от 0 до 3)</param>

/// <returns>Значение переменной</returns>

public int this[int idx]

{

get

{

return _gen[_s[idx]];

}

set

{

_gen[_s[idx]] = value;

}

}

/// <summary>

/// Свойство, реализующее доступ к битовому вектору

/// </summary>

public BitVector32 ByteGens

{

get { return _gen; }

set { _gen = value; }

}

/// <summary>

/// Метод, моделирующий мутацию генотипа

/// </summary>

public void MakeMutation()

{

this._gen[1 << _rg.Next(Genotype.Length)] =

!this._gen[1 << _rg.Next(Genotype.Length)];

}

#region IComparable<Genotype> Members

public int CompareTo(Genotype other)

{

if (this.FitFunction > other.FitFunction)

return 1;

if (this.FitFunction < other.FitFunction)

return -1;

return 0;

}

#endregion

public override string ToString()

{

return string.Format("x1 = {0}, x2 = {1}, x3 = {2}, x4 = {3}",

this[0], this[1], this[2], this[3]);

}

}

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