Генетика
<<  Характер наследования окраски шерсти у Американской норки Эвристические методы моделирования 7 класс  >>
Задача об «Умном муравье»
Задача об «Умном муравье»
Автомат Мура из 10 состояний
Автомат Мура из 10 состояний
Система из двух вложенных автоматов Мили
Система из двух вложенных автоматов Мили
Картинки из презентации «По технологии про еду» к уроку биологии на тему «Генетика»

Автор: Fedor Tsarev. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока биологии, скачайте бесплатно презентацию «По технологии про еду.ppt» со всеми картинками в zip-архиве размером 330 КБ.

По технологии про еду

содержание презентации «По технологии про еду.ppt»
Сл Текст Сл Текст
1Применение генетических алгоритмов для 15алгоритмов для генерации автоматов Мура и
генерации автоматов Мура и систем систем взаимодействующих автоматов Мили в
взаимодействующих автоматов Мили в задаче задаче об «Умном муравье».
об «Умном муравье». А. А. Давыдов, Д. О. 16Создание начального поколения.
Соколов, Ф. Н. Царев Научный руководитель Случайно генерируется заданное количество
– А. А. Шалыто 2008 год. (систем) автоматов Все автоматы содержат
2Автоматное программирование. одинаковое количество состояний. Давыдов
Предложено в России в 1991 году А. А., Соколов Д. О., Царев Ф. Н.
Программные системы предлагается Применение генетических алгоритмов для
разрабатывать так же, как выполняется генерации автоматов Мура и систем
автоматизация технологических (и не взаимодействующих автоматов Мили в задаче
только) процессов Система управления об «Умном муравье».
является системой взаимодействующих 17Формирование следующего поколения – 1.
конечных автоматов. Состояния События и Элитизм Фиксированная доля особей
входные переменные Выходные воздействия переходят напрямую Остальные – на основе
Конечный автомат Система конечных турнирной стратегии выбираются две особи
автоматов. Давыдов А. А., Соколов Д. О., из текущего поколения, и они с некоторой
Царев Ф. Н. Применение генетических вероятностью скрещиваются или мутируют.
алгоритмов для генерации автоматов Мура и Давыдов А. А., Соколов Д. О., Царев Ф. Н.
систем взаимодействующих автоматов Мили в Применение генетических алгоритмов для
задаче об «Умном муравье». генерации автоматов Мура и систем
3Преимущества автоматного подхода. взаимодействующих автоматов Мили в задаче
Обладает наибольшей эффективностью для об «Умном муравье».
систем со сложным поведением Формальное и 18Формирование следующего поколения – 2.
понятное описание поведения Автоматическая На нескольких островах эволюция происходит
генерация кода по диаграммам переходов независимо. Каждое фиксированное число
Возможность верификации программ Проектная поколений – обмен между случайными
документация. Давыдов А. А., Соколов Д. островами случайными элитными особями.
О., Царев Ф. Н. Применение генетических Давыдов А. А., Соколов Д. О., Царев Ф. Н.
алгоритмов для генерации автоматов Мура и Применение генетических алгоритмов для
систем взаимодействующих автоматов Мили в генерации автоматов Мура и систем
задаче об «Умном муравье». взаимодействующих автоматов Мили в задаче
4Решаемая проблема. Основная сложность об «Умном муравье».
в автоматном программировании – построение 19Мутация автомата Мура. Изменение
автоматов В большинстве случаев автоматы начального состояния Изменение действия в
проектируются вручную Однако эвристическое состоянии Изменение состояния, в которое
построение автоматов часто затруднено или ведет переход Изменение условия на
невозможно Решение – автоматическое переходе. Давыдов А. А., Соколов Д. О.,
построение конечных автоматов с помощью Царев Ф. Н. Применение генетических
генетического программирования. Давыдов А. алгоритмов для генерации автоматов Мура и
А., Соколов Д. О., Царев Ф. Н. Применение систем взаимодействующих автоматов Мили в
генетических алгоритмов для генерации задаче об «Умном муравье».
автоматов Мура и систем взаимодействующих 20Мутация пары автоматов Мили. Изменение
автоматов Мили в задаче об «Умном начального состояния Удаление (добавление)
муравье». перехода Изменение состояния, в которое
5Задача об «Умном муравье». Тор – 32x32 ведет переход Изменение действия на
89 клеток с едой 200 ходов Расположение переходе Мутация вложенного автомата.
еды и начальная позиция муравья Давыдов А. А., Соколов Д. О., Царев Ф. Н.
фиксированы Цель – создать муравья, Применение генетических алгоритмов для
который съест всю еду. Давыдов А. А., генерации автоматов Мура и систем
Соколов Д. О., Царев Ф. Н. Применение взаимодействующих автоматов Мили в задаче
генетических алгоритмов для генерации об «Умном муравье».
автоматов Мура и систем взаимодействующих 21Скрещивание автоматов Мура. На входе
автоматов Мили в задаче об «Умном две особи, на выходе – две особи Родители
муравье». – P1 и P2 Потомки – S1 и S2 Начальное
6Что умеет муравей? Определять состояние: S1.is = P1.is и S2.is = P2.is,
находится ли непосредственно перед ним еда либо S1.is = P2.is и S2.is = P1.is.
За один игровой ход совершить одно из Давыдов А. А., Соколов Д. О., Царев Ф. Н.
четырех действий: сделать шаг вперед, Применение генетических алгоритмов для
съедая еду, если она там находится генерации автоматов Мура и систем
повернуть налево повернуть направо ничего взаимодействующих автоматов Мили в задаче
не делать. Давыдов А. А., Соколов Д. О., об «Умном муравье».
Царев Ф. Н. Применение генетических 22Скрещивание переходов. Рассмотрим
алгоритмов для генерации автоматов Мура и состояние номер i «Перед муравьем нет еды»
систем взаимодействующих автоматов Мили в ? P1(i, 0) «Перед муравьем есть еда» ?
задаче об «Умном муравье». P1(i, 1) Аналогично: P2(i, 0), P2(i, 1),
7Конечный автомат – способ описания S1(i, 0), S1(i,1), S2(i, 0), S2(i, 1) Есть
муравья. Автомат с действиями на переходах 4 варианта для S1(i, 0), S1(i,1), S2(i,
(автомат Мили). Автомат с действиями в 0), S2(i, 1). Давыдов А. А., Соколов Д.
вершинах (автомат Мура). Система (пара) О., Царев Ф. Н. Применение генетических
автоматов взаимодействующих, с помощью алгоритмов для генерации автоматов Мура и
вложенности Придумать одиночный автомат с систем взаимодействующих автоматов Мили в
большим числом состояний – просто С задаче об «Умном муравье».
небольшим или систему автоматов – сложно 23Четыре варианта. Давыдов А. А.,
На рисунке – автомат Мили, 5 состояний, за Соколов Д. О., Царев Ф. Н. Применение
200 ходов – 81 единица еды. Давыдов А. А., генетических алгоритмов для генерации
Соколов Д. О., Царев Ф. Н. Применение автоматов Мура и систем взаимодействующих
генетических алгоритмов для генерации автоматов Мили в задаче об «Умном
автоматов Мура и систем взаимодействующих муравье».
автоматов Мили в задаче об «Умном 24Скрещивание пар автоматов Мили.
муравье». Внешние автоматы – аналогично автоматам
8Генетические алгоритмы – 1. Jefferson Мура Вложенные автоматы – или также
D., Collins R., Cooper C., Dyer M., скрещиваются, или один из детей наследует
Flowers M., Korf R., Taylor C., Wang A. вложенный автомат одного родителя, другой
The Genesys System. 1992. Кодирование – другого. Давыдов А. А., Соколов Д. О.,
автоматов битовыми строками Построен Царев Ф. Н. Применение генетических
автомат из 13 состояний, позволяющий алгоритмов для генерации автоматов Мура и
съесть всю еду за 200 ходов. Давыдов А. систем взаимодействующих автоматов Мили в
А., Соколов Д. О., Царев Ф. Н. Применение задаче об «Умном муравье».
генетических алгоритмов для генерации 25Функция приспособленности автомата
автоматов Мура и систем взаимодействующих Мура. F – количество еды, которое съедает
автоматов Мили в задаче об «Умном за 200 ходов муравей T – номер хода, на
муравье». котором муравей съедает последнюю единицу
9Генетические алгоритмы – 2. Angeline еды. Давыдов А. А., Соколов Д. О., Царев
P. J., Pollack J. Evolutionary Module Ф. Н. Применение генетических алгоритмов
Acquisition // Proceedings of the Second для генерации автоматов Мура и систем
Annual Conference on Evolutionary взаимодействующих автоматов Мили в задаче
Programming. 1993. Кодирование автоматов об «Умном муравье».
битовыми строками + «замораживание» 26Функция приспособленности пар
Построен автомат из 11 состояний, автоматов Мили. F – количество еды,
позволяющий съесть всю еду за 193 хода. которое съедает за 200 ходов муравей T –
Давыдов А. А., Соколов Д. О., Царев Ф. Н. номер хода, на котором муравей съедает
Применение генетических алгоритмов для последнюю единицу еды Z – число посещенных
генерации автоматов Мура и систем состояний у внешнего автомата C –
взаимодействующих автоматов Мили в задаче некоторый коэффициент, ключевой для
об «Умном муравье». генерации систем автоматов. Давыдов А. А.,
10Генетические алгоритмы – 3. Chambers Соколов Д. О., Царев Ф. Н. Применение
L. D. Practical Handbook of Genetic генетических алгоритмов для генерации
Algorithms, Volume 3, Chapter 26, 6 – автоматов Мура и систем взаимодействующих
Algorithms to Improve the Convergence of a автоматов Мили в задаче об «Умном
Genetic Algorithm with a Finite State муравье».
Machine Genome. CRC Press, 1999. 27Мутации поколений. Чтобы одни и те же
Кодирование автоматов битовыми строками + элитные особи «путешествуя» не заполонили
приведение автоматов к каноническому виду собой все острова, надо что-то делать.
Построен автомат из 8 состояний, Через фиксированное число поколений –
позволяющий съесть всю еду за 193 хода. «большая» мутация нескольких островов
Давыдов А. А., Соколов Д. О., Царев Ф. Н. «Большая» мутация острова – все особи либо
Применение генетических алгоритмов для заменяются на случайно сгенерированные,
генерации автоматов Мура и систем либо на мутированные. Давыдов А. А.,
взаимодействующих автоматов Мили в задаче Соколов Д. О., Царев Ф. Н. Применение
об «Умном муравье». генетических алгоритмов для генерации
11Генетические алгоритмы – 4. Царев Ф. автоматов Мура и систем взаимодействующих
Н., Шалыто А. А. О построении автоматов с автоматов Мили в задаче об «Умном
минимальным числом состояний для задачи об муравье».
«умном муравье» /Сборник докладов X 28Настраиваемые параметры алгоритма – 1.
международной конференции по мягким Число островов Размер поколения на одном
вычислениям и измерениям. СПбГЭТУ острове Время до «большой» мутации Доля
"ЛЭТИ". Т.2, 2007, с. 88–91. уничтожаемых островов во время «большой»
Генетическое программирование. Давыдов А. мутации Доля особей, переходящих в
А., Соколов Д. О., Царев Ф. Н. Применение следующее поколение Время между обменами
генетических алгоритмов для генерации особями между островами. Давыдов А. А.,
автоматов Мура и систем взаимодействующих Соколов Д. О., Царев Ф. Н. Применение
автоматов Мили в задаче об «Умном генетических алгоритмов для генерации
муравье». автоматов Мура и систем взаимодействующих
12Автомат из семи состояний. Построены автоматов Мили в задаче об «Умном
два автомата из семи состояниями после муравье».
перебора 160 и 230 млн. автоматов. Давыдов 29Настраиваемые параметры алгоритма – 2.
А. А., Соколов Д. О., Царев Ф. Н. Число обмениваемых особей Параметры малой
Применение генетических алгоритмов для мутации Параметры скрещивания Отношение
генерации автоматов Мура и систем «мутантов», случайных особей и детей
взаимодействующих автоматов Мили в задаче особей из текущего поколения при
об «Умном муравье». формировании следующего поколения С –
13Решаемая задача. Во всех описанных коэффициент влияния внешнего автомата.
работах строились автоматы Мили Цель Давыдов А. А., Соколов Д. О., Царев Ф. Н.
настоящей работы – построение автоматов Применение генетических алгоритмов для
Мура и систем взаимодействующих автоматов генерации автоматов Мура и систем
Мили. Давыдов А. А., Соколов Д. О., Царев взаимодействующих автоматов Мили в задаче
Ф. Н. Применение генетических алгоритмов об «Умном муравье».
для генерации автоматов Мура и систем 30Автомат Мура из 10 состояний.
взаимодействующих автоматов Мили в задаче Позволяет муравью съесть всю еду за 198
об «Умном муравье». ходов. Давыдов А. А., Соколов Д. О., Царев
14Предлагаемый подход – 1. Островной Ф. Н. Применение генетических алгоритмов
генетический алгоритм Автомат = начальное для генерации автоматов Мура и систем
состояние + описание состояний + вложенный взаимодействующих автоматов Мили в задаче
автомат Состояние = два перехода + об «Умном муравье».
действие в состоянии (для автомата Мура) 31Система из двух вложенных автоматов
Переход = номер состояния + действие (для Мили. Позволяет муравью съесть 87 единиц
автомата Мили). Давыдов А. А., Соколов Д. еды за 185 ходов. Давыдов А. А., Соколов
О., Царев Ф. Н. Применение генетических Д. О., Царев Ф. Н. Применение генетических
алгоритмов для генерации автоматов Мура и алгоритмов для генерации автоматов Мура и
систем взаимодействующих автоматов Мили в систем взаимодействующих автоматов Мили в
задаче об «Умном муравье». задаче об «Умном муравье».
15Предлагаемый подход – 2. class 32Спасибо за внимание! Спасибо за
Automaton { Transition[][] transitions; внимание! Давыдов А. А., Соколов Д. О.,
int initialState; Automaton Царев Ф. Н. Применение генетических
nestedAutomaton; char[] stateAction; // алгоритмов для генерации автоматов Мура и
для Мура }. Давыдов А. А., Соколов Д. О., систем взаимодействующих автоматов Мили в
Царев Ф. Н. Применение генетических задаче об «Умном муравье».
По технологии про еду.ppt
http://900igr.net/kartinka/biologija/po-tekhnologii-pro-edu-219672.html
cсылка на страницу

По технологии про еду

другие презентации на тему «По технологии про еду»

«Генетические болезни человека» - Мутации – наследственные изменения генетического материала. Гемофилия. Г.Гейне Наши врачи должны, как азбуку, знать законы наследственности. Мутации возникают внезапно, скачкообразно. Необходим постоянный медицинский контроль за умственным и физическим развитием ребенка. У супружеской пары, родился сын – дальтоник.

«Стрекоза и муравей» - «Не оставь меня, кум милый! Выучите наизусть басню Крылова "Стрекоза и Муравей", Нарисуйте одного из героев. Алгоритм чтения басни: В мягких муравах у нас. Стрекоза и Муравей. Подчеркните интонацией ироничное отношение к героям басни. Выберите тон чтения: речи героев, морали и пояснений автора.

«Схема алгоритма» - После школы иду гулять. Циклический алгоритм. Смотрю телевизор. Если завтра будет очень холодно, то я не пойду в школу. Схема алгоритма. Самостоятельно: После уроков я пойду домой. Конец. Обычно после школы я иду гулять, а когда возвращаюсь, делаю уроки. Графические объекты блок-схемы: Пример: Иначе придется идти на уроки.

«Генетическая связь» - Кислоты. CuO. Основания. Дайте определение понятию «Генетическая связь». Оксиды. Al(NO3)3. Как из простого вещества медь получить сложное вещество оксид меди (II)? Классификация неорганических веществ. Металлы. Связь между классами веществ, образованных одним элементом. Подумай и ответь. HCl. HNO3. Неметаллы.

«Генетические исследования» - Медико-генетическая консультация состоит из 4 этапов; диагноз, прогноз, заключение, совет. «Синдром мяукания». Популяционный метод. Синдром Клайнфельтера. Заболевание имеет полиорганные проявления. Генетика Методы исследования Генетика и здоровье Медико-генетические исследования Заключение. Скончался 6 января 1884, Брюнн, ныне Брно, Чешская Республика.

Генетика

16 презентаций о генетике
Урок

Биология

136 тем
Картинки
900igr.net > Презентации по биологии > Генетика > По технологии про еду