Введение в математическую генетику

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

БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

(БашГУ)

Курсовая работа

по дисциплине «Информатика»

на тему: «Введение в математическую генетику.»

Специальность: Программирование и экономическая информатика

УФА 2016

Содержание

Введение

1. Математическая генетика

1.1 История генетики

1.2 Генетический алгоритм. Основные понятия

1.3 Основные этапы генетического алгоритма

1.4 Область применения генетического алгоритма

2. Поиск численного решения целевой функции с использованием генетического алгоритма

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

2.2 Реализация решения задачи на С++

Заключение

Литература



Введение

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

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

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

математический генетика численный задача



1. Математическая генетика

1.1 История математической генетики

Общая популяционная генетика является в настоящее время идейной основой современной так называемой «синтетической» теории эволюции. Фундаментальный принцип естественного отбора как основного фактора эволюции был сформулирован Ч. Дарвином задолго от открытия механизмов генетики. Незнание основных закономерностей наследуемости привело Ч. Дарвина к гипотезе о слитной наследственности, согласно которой задатки родителей перемешиваются наподобие жидкостей в организме потомка. В 1865 г. Г. Мендель открыл основные законы передачи наследственных факторов от родителя к потомку, показавших их дискретность. Менделевские законы стали известны в мировой науке лишь после их вторичного открытия в 1900 г., независимо друг от друга, Г. де Фризом, К. Корренсом и К. Чермаком. Дальнейшее развитие генетика получила в трудах Т. Моргана с сотрудниками, экспериментально доказавшими, что основными носителями наследственной информации являются хромосомы, в которых наследственные факторы -- гены -- располагаются линейно. Затем накопление экспериментальных фактов показало универсальность менделевских законов для всех организмов, размножающихся половым путем. Однако и после вторичного открытия законы Менделя и дарвиновская теория естественного отбора оставались двумя самостоятельными, никак не связанными направлениями. Более того, происходило их известное противопоставление друг другу. И лишь к 30-м годам было показано, что менделевская генетика и дарвиновская теория естественного отбора не только не противостоят друг другу, но и образуют новый синтез -- современную эволюционную теорию. Одновременно с возникновением фундаментальной системы концепций общей популяционной генетики, с их экспериментальной проверкой в лабораторных и природных условиях, происходило становление математической популяционной генетики. Одной из первых работ в этом направлении была работа известного английского математика Г. Г. Харди (1908 г.). В дальнейшем произошел настоящий «взрыв», когда число работ по математической популяционной генетике начало стремительно расти. Тогда же сформировались два основных подхода к задачам популяционной генетики. Первый, так называемый «детерминистский» связан в основном с работами Дж. Б. Холдена и Р. А. Фишера. При этом подходе популяции предполагаются достаточно большими, флуктуациями фазовых переменных пренебрегают и весь процесс эволюции популяций описывается изменением средних величин этих переменных во времени. В качестве фазовых переменных обычно используются концентрации или частоты как самих генов, так и некоторых их комбинаций (гамет или зигот) в популяции. Модель обычно описывает изменение этих концентраций или частот под действием таких факторов, как отбор, миграция, нарушение панмиксии и т. п. Сами факторы задаются некоторыми параметрами, входящими в правые части разностных или дифференциальных уравнений модели. Например, коэффициенты отбора являются параметрами, задающими давление отбора на различные генотипы. По сути дела, детерминистские модели являются динамическими моделями, где популяция представляется некоторой динамической системой, поведение которой как под действием различных внешних воздействий, так и при изменении внутренних закономерностей функционирования системы описывается траекторией в фазовом пространстве частот -- единичном симплексе, расположенном в положительном ортанте. Второй подход к задачам популяционной генетики, так называемый «стохастический» берет свое начало с работ С. Райта и Р. А. Фишера. При этом подходе изменение числа генов или их комбинаций в популяции рассматривается как марковский процесс. Здесь уже не требуется предположения о достаточно большой популяции, и стохастические модели с успехом применяются для анализа генетических процессов в малых популяциях, где флуктуации за счет случайности выборки могут быть значительными. Эти два подхода в достаточной степени отличаются друг от друга как по структуре моделей, так и по используемому математическому аппарату. Если в детерминистском подходе это качественная теория интегральных, дифференциальных и разностных уравнений и теория устойчивости, то в стохастическом это методы теории случайных процессов . Они отражают две различные стороны одного и того же явления -- эволюции популяций живых организмов. Если популяции достаточно велики, давление отбора выражено достаточно сильно, действие других факторов также весьма ощутимо, то поведение популяции на достаточно большом промежутке времени (большое число поколений) можно рассматривать как поведение некоторой динамической системы и описывать его детерминистской моделью. Если же давления отбора, мутационного процесса, миграции и других факторов слабы и практически не изменяют концентрации генов в течение одного поколения, а сама популяция имеет малую численность, то поведение популяции на достаточно малых временных промежутках (малое число поколений) в весьма большой степени определяется случайными факторами. По сути дела, стохастические модели нужно применять в том случае, когда типичные скорости направленных эволюционных изменений трудно уловить; тогда основную роль приобретают случайные воздействия. Проблема соотношения детерминистского и случайного в эволюции является одной из основных проблем современной эволюционной теории.

1.2 Генетический алгоритм. Основные понятия

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

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

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

Цель генетических алгоритмов состоит в том, чтобы:

· абстрактно и формально объяснить адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;

· моделировать естественные эволюционные процессы для эффективного решения оптимизационных задач .

Генетические алгоритмы имеют следующие отличия от других методов поиска и оптимизации:

· генетические алгоритмы работают не с параметрами задачи, а с закодированным множеством параметров;

· осуществляют оптимизацию не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений;

· используют целевую функцию, а не ее различные приращения для оценки качества принятия решений;

· применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

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

Популяция есть множество элементов . Каждый элемент этой популяции , как правило, представляет собой одну или несколько хромосом или особей.

Хромосома - некоторый конечный вектор размерности , состоящий из генов - элементов хромосом .

Каждый ген в хромосоме имеет свою позицию - локус. Функциональное назначение гена называется аллель.

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

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

Поколение - генерация, или процесс реализация одной итерации алгоритма.

Генотип (набор хромосом) каждой особи популяции описывает фенотип - его внешнее проявление. Фенотип каждого элемента оценивается при помощи «функции приспособленности», (fitness function). Эта функция используется для сравнения альтернативных решений между собой и выбора лучших. Отсюда следует, что основная задача генетических алгоритмов состоит в оптимизации целевой функции .

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

1.3 Основные этапы генетического алгоритма

Задание целевой функции. Целевая функция задается в зависимости от поставленной задачи так, чтобы она могла наиболее эффективно оценить приспособленность особи.

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

· принцип «одеяла» - генерируется полная популяция, включающая все возможные решения в некоторой заданной области;

· «дробовик» - случайный выбор альтернатив из всей области решений данной задачи;

· «фокусировки» - реализует случайный выбор допустимых альтернатив из заданной области решений данной задачи;

· комбинирования - состоит в различных совместных реализациях первых трех принципов.

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

Размножение (скрещивание). Генетический алгоритм предполагает два способа размножения: половое и бесполое. Бесполое размножение - самокопирование особи, которое может применяться, например, при недостаточном количестве элементов во множестве особей. Половое размножение в генетическом алгоритме обычно происходит между двумя особями, но допустимо использование большего количества объектов. Главное требование к размножению - чтобы потоки имели возможность унаследовать признаки от своих родителей. Основные методы кроссинговера:

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

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

· Упорядоченный оператор. Случайным образом выбирается разрывающая точка в одной из родительской хромосом. Затем блок генов, расположенный до точки разрыва копируется в новую хромосому. Остальные позиции в дочерней хромосоме дополняются генами из второй хромосомы в упорядоченном виде слева направо (берутся гены, которые еще не вошли в генотип дочерней хромосомы).

· Циклический оператор. Он выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей.

· Универсальный оператор кроссинговера. Широко применяется в решении задач из теории расписаний. Вместо разрезающей точки в универсальном операторе кроссинговера используется двоичная маска, длина которой равна длине заданных хромосом. Потомки получаются путем сложения в двоичной арифметике родительской хромосомы с маской.

· «Жадный» оператор. На каждом шаге создания дочерней хромосомы происходит частичный выбор локально оптимального значения между генами родительских хромосом .

Мутации. Проведение преобразований над генотипом одной особи. К основным операторам мутации относят:

· Одноточечный. Выбирается произвольный ген в родительской хромосоме и меняется местами с рядом стоящим геном.

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

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

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

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

· Селекция на основе заданной шкалы. При применении этого метода популяция сортируется на основе заданного критерия. Каждому элементу назначается определенное число, и селекция выполняется согласно этому числу.

· Элитная селекция. В этом случае выбираются лучшие (элитные) элементы, и преобразования происходят уже над ними. Этот процесс повторяется каждое поколение до тех пор, пока будут появляться новые элитные элементы.

· Турнирная селекция. Некоторое число элементов выбирается случайно, и лучшие элементы в выбранной группе выбираются для дальнейшего эволюционного поиска.

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

1.4 Область применения генетического алгоритма

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

Генетические алгоритмы широко применяются для решения следующих задач:

· оптимизация функций;

· оптимизация запросов в базах данных;

· решение задач на графах;

· настройка и обучение искусственной нейронной сети;

· игровые стратегии;

· моделирование искусственной жизни;

· теория приближений;

· решение задач о покрытиях и разбиениях т др.

2. Поиск численного решения целевой функции с использованием генетического алгоритма

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

Целевая функция будет иметь вид

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

Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.

Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.

2.2 Реализация решения задачи на С++

#include <iostream>

#include<stdlib.h>

#include <math.h>

#include <ctime>

using namespace std;

double func(double x)

{

return sin(M_PI * x / 180) - 1 / x;

}

double mutation(double x0, double x1) //мутация: генерация случайной //величины

{

const int NUM = 100000000;

return fabs((double)((rand() * NUM) % (int)((x1 - x0)*NUM) + 1) / NUM) + x0;

}

double inversion(double x, double eps) //инверсия: поиск в окрестностях точки

{

static int sign = 0;

sign++;

sign %= 2;

if (sign == 0) return x - eps;

else return x + eps;

}

void crossover(double *x, double eps, double x0, double x1) //скрещивание: //среднее арифметическое

{

int k = 99;

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

for (int j = i + 1; j < 8; j++)

{

x[k] = (x[i] + x[j]) / 2;

k--;

}

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

{

x[k] = inversion(x[i], eps); k--;

x[k] = inversion(x[i], eps); k--;

}

for (int i = 8; i < k; i++)

x[i] = mutation(x0, x1);

}

void sort(double *x, double *y) //сортировка

{

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

for (int j = i + 1; j < 100; j++)

if (fabs(y[j]) < fabs(y[i]))

{

double temp = y[i];

y[i] = y[j];

y[j] = temp;

temp = x[i];

x[i] = x[j];

x[j] = temp;

}

}

double genetic(double x0, double x1, double eps) //поиск решения с //использованием ГА

{

double population[100];

double f[100];

int iter = 0;

for (int i = 0; i < 100; i++) //формирование начальной популяции

{

population[i] = mutation(x0, x1);

f[i] = func(population[i]);

}

sort(population, f);

do {

iter++;

crossover(population, eps, x0, x1);

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

f[i] = func(population[i]);

sort(population, f);

} while (fabs(f[0]) > eps && iter<20000);

cout <<"Кол-во итераций: "<< iter << endl;

cout<<"Ответ: ";

return population[0];

}

int main()

{

setlocale(LC_ALL, "Russian");

srand(time(NULL));

cout << genetic(1.0, 10.0, 0.000001);

cin.get();

return 0;

}



Рисунок 1. Вывод решения на экран.



Заключение

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

В ходе изучения мы могли определить наиболее значимых положительных сторон:

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

· Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени .

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

Итак, задачи оптимизации (и не только) успешно решаются при помощи генетических алгоритмов.



Литература

1. «Лекции по нейронным сетям и генетическим алгоритмам» - #"_Hlt470119938">000007.htm.

2. Гальцына О.Л., Попов И.И. «Основы алгоритмизации и программирования».

3. Исаев С.А. Популярно о генетических алгоритмах (http://algolist.manual.ru/ai/ga/ga1.php).

4. Авторский сайт Ю. Цоя (http://www.qai.narod.ru/).

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

...