Схема работы генетического алгоритма
В модели представлены самоопыляющиеся растения, следовательно, в образовании потомка принимает участие лишь одна особь. Процесс размножения можно разделить на несколько стадий: 1. Инициализация набора хромосом и формирование начальной популяции. 2. Анализ приспособленности к условиям среды и возможности потомков. 3. Выполнение кроссинговера 1, формирование новой популяции. 4. Выполнение оператора мутации по выбору пользователя. 5. Сбор генотипа (переходная стадия для осуществления кроссинговера 2, аналогична телофазе I мейоза). 6. Кроссинговер 2. 7. Генерирование потомков. (Приложение стр. VI- VII) Повторяем шаги 3 – 7 пока не будет достигнут критерий окончания процесса. Пример результата работы программы: (Приложение стр. VIII, Табл. 5.)
Описание программного кода генетического алгоритма
Сначала дадим характеристику особи (Приложение стр. V, Рис.3): Формирование характеристики происходит комбинацией генов. Характеристика представляет совокупность признаков, например: «характеристика требования света» есть совокупность признаков, как ширина листа, его форма, цвет, покрытие и т.д.
Шаг 1. Инициализация изначальной особи. Первое растение появляется в программе с готовым набором основных генов. Каждый из генов отвечает за отношение растения к тем или иным условиям внешней среды, а так же за продолжительность его жизни, скорость размножения и количество потомков. Растение имеет изначально лишь 2 условные хромосомы, состоящие из 2-х нитей ДНК.
|
|
|
Кнопка «Старт» – запускает функцию start, генерирует 4 \\{1} случайных числа (от 0 до 63 т.е. 26), создавая исходный набор хромосом - нитей ДНК. Для применения генетического алгоритма кодируем значения исходного набора в виде двоичных последовательностей \\{2}, состоящих из 6 битов:
Private Function start()
Randomize Timer
For i = 2 To 5
Cells(i, j) = Int(Rnd(1) * 64) \\ {1},
k = Cells(i, j)
For d = 8 To 3 Step -1
Cells(i, d) = k Mod 2 \\{2}
k = k \ 2
сумма \\{3} которых по столбцу означает разные характеристики особи.
For i = 2 To 9
If Cells(i, j) = " " Then Sum = Sum Else Sum = Sum + Cells(i, j) \\{3}
Next i
(Приложение, стрVI)
Шаг 2. Вычисляем для особи ее пригодность, определяем число потомков. Осуществляем выбор родителя из имеющихся растений или генерируем новое растение. Анализируем приспособленность выбранной особи к условиям данной среды для определения наиболее вероятного количества потомков за всю жизнь данного растения.
Рассчитываем число потомков, используя критерии приспособленности:
Private Function zpotomki()
Обозначения:
A – свет (среда)
B – вода (среда)
C – почва (среда)
a1 – свет (требование особи)
b1 – вода (требование особи)
c1 – почва (требование особи)
|
|
|
N - количество потомков
T – время жизни
V – скорость размножения
K – коэффициент приспособленности
Y – количество потомков за время жизни = число циклов
a1 = | a1 - A |
b1 = | b1 - B |
c1 = C – c1
k = ((a1 + b1) * 1.314 + c1) \\ вклад в коэффициент приспособленности значений света, вода и почвы
Y = Int((n * T * v / 1.8 - k * 1.413) * 3.75) \\ число потомков Y = N * T * V = 0 при условии, если один из множителей равен нулю, то критерий окончания процесса.
В модели представлены две противоположные тенденции, борьба которых отвечает за приспособленность вида и число потомков. Первая тенденция представлена генетической наследственностью и условиями среды почвы, которая увеличивает рождаемость и понижает генетический груз. Вторая – представлена внешними условиями и понижает рождаемость с повышением генетического груза.
Шаг 3. Выполнение оператора кроссинговера 1 – перемешивание значений случайно отдельно взятых столбцов, что соответствует обмену аллельными генами между гомологичными хромосомами.
Private Function kros1() \\ – создание гамет относительно ячеек электронной таблицы (один из недостатков программы, который уменьшает «читаемость»)
Cells(15, 1) = Int(Rnd(1) * 12 + 3)
d = Cells(15, 1) \\{4}
В случайном столбце d \\{4} генерируются случайные значения до тех пор, пока контрольная сумма \\{5} их по столбцу не совпадет с первоначальными значениями \\{6}.
|
|
|
For i = 16 To 23 - s1
Cells(i, d + 17) = Int(Rnd * 2)
summk1 = summk1 + Cells(i, d + 17)
Next i
Cells(24, d + 17) = summk1 \\{5}
If summk1 <> sumk1 Then
Cells(24, d + 19) = "net"
Do Until summk2 = sumk1 \\{6}
summk2 = 0
For i = 16 To 23 - s1
Cells(i, d + 18) = Int(Rnd * 2)
summk2 = summk2 + Cells(i, d + 18)
Next i
Cells(24, d + 18) = summk2
Loop
End If
Шаг 4. Выполнение оператора мутации. Во время размножения растение может с определенной вероятностью, которая контролируется пользователем программы, мутировать. В модели используются 3 вида мутаций: 1) генная – изменение значений отдельного столбца (гена), 2) хромосомная – достройка и перестройка дополнительных ячеек в столбцах, что соответствует изменениям не отдельного гена, а отдельной хромосомы, 3) геномная – достройка и перестройка дополнительных столбцов и их ячеек, что соответствует образованию новых хромосом в генотипе.
Private Function mutt1() - \\ - мутация I
Randomize Timer
For i = 16 To 23
If Cells(i, j) = " " Then mz = mz + 1 \\{7} - считаем число пустых ячеек
Next i
For i = 16 To 23 – mz \\{8} - случайно заполняем тоже самое число элементов в столбце
Cells(i, j) = Int(Rnd * 2)
Next i
Private Function mutt2() - \\ - мутация II
Randomize Timer
For j = 3 To 8 + mu3
Cells(13, 1) = Int(Rnd * 4) - \\ достройка и перестройка дополнительных ячеек в столбцах
|
|
|
mu2 = Cells(13, 1)
For i = 20 To 20 + mu2
Cells(i, j) = Int(Rnd * 2)
Next i
Next j
Private Function mutt3()
Randomize Timer
For j = 9 To 8 + mu3 \\ достройка столбцов
For i = 16 To 19
Cells(i, j) = Int(Rnd * 2)
Next i
Next j
Шаг 5. Выполнение оператора сбора генотипа – стадия, соответствующая гаметогенезу с участием нескольких клеток, что позволяет предсказать большее количество вероятных гамет, которые могут быть получены в ходе гаметогенеза.
Private Function genotip()
Cells(i, j1) = Cells(i - 27, j) - \\ сбор генотипа - совмещение столбцов родителя Cells(i, j1) = Cells(i - 13, j) - \\ и столбцов после 1 кроссинговера
Шаг 6. Выполнение оператора кроссинговера 2. Кроссинговер 2 – обмен аллельными генами гомологичных хромосом с учетом сбора генотипа.
For i = 42 To 49 \\ для заданных строк
Cells(i, j) = Cells(i - 13, j)
Next i
Next j
For j = 3 To 2 * (8 + mu3) Step 2
Label3.Caption = Int(Rnd(1) * 5 + 3) \\ выбираем случайную строку и начиная от нее производим обмен до конца выбранного интервала
d = Label3.Caption
i = 42 + d
For i = i To 49
Cells(50, j) = Cells(i, j)
Cells(i, j) = Cells(i, j + 1)
Cells(i, j + 1) = Cells(50, j)
Next i
Next j
Шаг 7. Генерирование (синтез) потомка - выбор из 2-х одинаковых столбцов 1-одного. Генерирование потомка – выбор из получившегося разнообразия вероятностей гамет соответствующего условиям количества ДНК и хромосом для появления потомка, что соответствует слиянию гамет.
Randomize Timer \\ новый потомок формируется случайно из 2-х столбцов с учетом коэффициентов мутации 3, если она была.
For p = 3 To 8 + mu3
p1 = Int(Rnd * 2)
Cells(65, 3) = p1
For i = 55 To 62
Cells(i, p) = Cells(i - 13, 2 * (p - 1) - p1)
Next i
Next p
Затем производится анализ различий и сходств родителя и потомков – сравнение различных показателей генотипа, определение приспособленности потомков и сравнение с приспособленностью родителя, прогнозирование наиболее вероятного количества потомков образовавшихся особей.
Анализ работы модели
Для создания своей эволюционной модели использовал стандартный оптимизационный метод, базирующийся на эволюции популяции «особей». Каждая особь характеризуется приспособленностью – многомерной функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности. В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями.
Изучая различные виды эволюционных алгоритмов, пришел к выводу, что они в основном отличаются друг от друга тем, как осуществляют операции селекции (обычно с использованием мутации и рекомбинации) и создания потомков (либо полностью заменяет родителей потомками, либо включает в следующее поколение наиболее приспособленных родительских особей и потомков). [3]
При построении модели, аналогично описанию по созданию эволюционных алгоритмов [3, 4, 5] использую термины из биологии, с тем различием, что в качестве параметров, характеризующих одну «особь», здесь выступает массив, состоящий из четырех строк (аналогично в биологии – две хромосомы, каждая состоит из двух нитей ДНК). В проекте мою «популяцию» определяет не набор потенциальных решений, а созданная программой совокупность индивидуумов, которая характеризуется «пригодностью (приспособленностью)», качеством, определяющим возможность существования её в среде.
Фактически мною создана «Модель самоопыляющегося растения», в которой представлены две противоположные тенденции, отвечающие за приспособленность вида и число потомков. Первая тенденция представлена генетической наследственностью и условиями среды почвы, которая увеличивает рождаемость и понижает генетический груз. Вторая – представлена внешними условиями и понижает рождаемость с повышением генетического груза.
Функция Y в модели является характеристикой «пригодности», где критерием окончания процесса выступает условие равенства нулю числа потомков. Здесь k вклад в коэффициент приспособленности значений света, вода и почвы.
Y включает в себя продолжительность жизни (количество жизненных циклов), частота появления потомства (количество циклов размножения) и количество потомства, возможное за один цикл размножения, т.е. T, V и N.
Если исключить корректирующие влияние окружающей среды, возможно математически вычислить количество потомков за всю жизнь особи путем умножения показателей генетической предрасположенности N, T и V.
Но в представленной модели на количество потомства влияют не только три наследуемых пункта, напрямую влияющие на появление второго поколения особей, но и три пункта, корректирующие численность будущих поколений. Корректирующие пункты выражены условиями среды (а1, b1 и с1) и генетически наследуемыми требованиями к среде (A, B и С).
Растения расселяются на выбранной местности не случайным образом. Несколько видов конкурируют друг с другом за право занимать ту или иную единицу пространства. Наиболее приспособленные к жизни в выбранных условиях виды будут более конкурентоспособными. Благодаря изменениям растений, которые представлены «естественной селекцией» и мутациями можно наблюдать за тем, как вид, ставший фоновым для данного участка постепенно редеет, уступая место другим растениям.
В модели используются 3 вида мутаций: 1) генная – изменение значений отдельного столбца (гена), 2) хромосомная – достройка и перестройка дополнительных ячеек в столбцах, что соответствует изменениям не отдельного гена, а отдельной хромосомы, 3) геномная – достройка и перестройка дополнительных столбцов и их ячеек, что соответствует образованию новых хромосом в генотипе.
Из возможных комбинаций генотипов можно выделить генотипы, принадлежащие растениям-индикаторам. Эти растения приспособлены к жизни лишь на определенных условиях, что позволяет по их наличию судить об этих условиях. Генотип этих растений создает такие растения, которые крайне прихотливы к условиям жизни и обитают лишь в определенных условиях.
Результат работы программы эволюционного алгоритма представлен в таблице (Приложение стр.VIII Табл. 5) и диаграммах (Приложение стр. IX X Диагр. 8-11).
Таблица представляет собой библиотеку поколений случайно сгенерированного вида, имеющего в своем арсенале обитания 3 типа условий внешней среды - луг, лес, река. Из анализа данной библиотеки можно увидеть, что в случае потери приспособленности данного вида к одним из условий среды, через несколько поколений, в ходе естественного отбора и эволюции эту приспособленность возможно вернуть. В случае, если вид становится не приспособлен к обитанию во всех условиях сред (луг, лес, река) и географически он отделен от родственных с ним видов на других территориях, то данный вид исчезает.
В природных условиях каждый вид и отдельный организм сталкивается с трудностями среды, преодолевая которые, он развивается. Но это развитие не одинаково: кто-то встретится с еще большими трудностями и погибнет, а кто-то настолько продвинется вперед, что трудности либо будут незначительными, либо их вообще не будет.
Подобные скачки в развитии и влияют на колебания численности, выходящие за рамки отношений «хищник-жертва». Вид изменился и лучше приспособился благодаря изменчивости и отбору, который отсеивал изменения, не идущие во благо виду по естественным законам. Но если вид перестает сталкиваться с трудностями, что сильно увеличивает его численность, он теряет и воздействие на себя естественного отбора. Изменчивость остается, а корректирующее влияние естественного отбора утеряно - это приводит к деградации вида. Изменчивость создает неприспособленных особей, которые выживают и получают право на размножение, генофонд вида все больше наполняется генетическим грузом.
Избыток генетического груза ведет к снижению численности популяции, в связи с увеличением показателя их неприспособленности к условиям среды. Последствия накопления генетического груза, таким образом, различны: вид может исчезнуть, из-за нехватки приспособленных к среде особей, или он продолжает существовать, но в более ослабленной форме, чем та, к которой он пришел во время роста популяции. В последнем случае, вид вновь подвергается естественному отбору, уничтожающему особей с избытком генетического груза, а выжившие подвергаются воздействию изменчивости и вновь, в результате чего вид вновь развивается и преодолевает трудности, возникающие на его пути развития.
Пример подобного явления можно увидеть с помощью нашей модели. В долгосрочной перспективе один вид, изменяясь, порождает множество других родственных ему видов со своими характерными особенностями. Виды меняются, развиваются и деградируют. Часть из них накапливает огромное количество генетического груза, становится тупиковой ветвью эволюции и вымирает.
Практические наблюдения растительностью пойменного леса реки Куры показали закономерности расселения растений. В частности можно выделить наиболее интересные закономерности. На данной территории расселяются растения:
наиболее приспособленные к данным условиям, чем больше приспособленность вида, тем выше его численность; обнаружены растения-индикаторы, которые не способны жить в других условиях, что позволяет сделать вывод об условиях среды данной территории; циклические и нециклические абиотические изменения вызывают соответственные изменения растительного сообщества; нециклические изменения биотических факторов вызывают череду изменений данного биологического сообщества и, возможно, изменение абиотических факторов, зависящих от биологического сообщества (освещенность, влажность и т.д.).
ЗАКЛЮЧЕНИЕ
Эволюционная модель, созданная в проекте позволяет пошагово отображать процессы создания и развития особи. Программа позволяет определить количество потомков, используя характеристики внешней среды и особи, которые задаются основными критериями, влияющими на жизнь растения. Созданная теоретическая модель, демонстрирует приспособление видов к условиям жизни, их развитие и изменения вида (мутации) под влиянием внешних и внутренних условий. Она имитирует процессы, происходящие в природе. С помощью эволюционной модели биологической системы можно наглядно показать процессы эволюции, селекции, видового приспособления, видообразования, развития и деградации видов.
Материалы проекта могут быть интересны специалистам, изучающим оптимизационные алгоритмы, и полезны учащимся, при изучении эволюционных моделей.
Литература
1. Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма // Copyright © Vladimir Red'ko, Nov 2, 1999 //http://www.keldysh.ru/pages/BioCyber/Lectures/Lecture10/Lecture10.html
2. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. // М. – 1969г.// ISBN: 978-5-458-49798-5, 1969г.
3. Панченко, Т. В. Генетические алгоритмы [Текст] : учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань : Издательский дом «Астраханский университет», 2007.
4. Люк Ш. Основы метаэвристик. 2009/. http://qai.narod.ru/GA/metaheuristics.html
5. Генетический алгоритм. Просто о сложном из песочницы tutorial //http://habrahabr.ru/post/128704/
6. Н.Н. Наумова, И.С. Шварева, Г.Н. Лаврова и др. Методы экологических исследований для школьников: Учебно- методическое пособие / под ред. Н.Н. Наумовой, И.С. Шваревой – Ковров: Маштекс, 2007.
7. Флористический список. Кавказ, Ставропольский край, Курская // http://www.plantarium.ru/page/flora/id/61.html //
8. Галушко А. И. Флора Северного Кавказа. Определитель: в 3 т. / Под ред. С. К. Черепанова. Т. 1. Ростов-н/Д, 1978. 320 с.; Т. 2. Ростов-н/Д, 1980. 352 с.; Т. 3. Ростов-н/Д 1980. 328с.
9. Красная книга Ставропольского края: редкие и находящиеся под угрозой исчезновения виды растений и животных. Т. 1. Растения. Ставрополь, 2002. 384с.
10. Чернова Н.И., Былова А.М. Общая экология. Гл. 8.6.6. Математическое моделирование в экологии М.: Дрофа, 2007. - 416с. SBN: 978-5-358-03410-5
11. Казаков П. В. Эволюционное моделирование и его применение. / БГТУ кафедра «Компьютерные технологии и системы» 2009г.
[1] Цифровая лаборатория «Архимед 4.0», датчик освещенности DT009-4, датчик влажности
[2] Экологический ряд – совокупность растительных сообществ, располагающихся соответственно нарастанию или убыванию ведущих факторов среды, например, увлажнение, засоленность почвы (БСЭ)
Дата добавления: 2019-01-14; просмотров: 260; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!