Генетические алгоритмы |
Генетика
Скачать презентацию |
||
<< Основные понятия генетики | Наследование сцеплённое с полом >> |
Автор: Den. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока биологии, скачайте бесплатно презентацию «Генетические алгоритмы.ppt» со всеми картинками в zip-архиве размером 2405 КБ.
Скачать презентациюСл | Текст | Сл | Текст |
1 | Генетические алгоритмы. Состояние. Проблемы. Перспективы. | 27 | достижения запланированных результатов. Схема поиска на основе |
Лектор, заслуженный деятель науки и техники РФ, д.т.н., проф. | тетраэдра. | ||
Курейчик В.М. kur@tsure.ru. Технологический институт Южного | 28 | Архитектуры и стратегии генетического поиска. Упрощенные | |
Федерального университета в г. Таганроге. | схемы организации связей при эволюционном поиске на основе | ||
2 | Объекты исследования. Схемотехническое и конструкторское | Платоновых графов додекаэдра. Отметим, что здесь могут быть | |
проектирование РЭА и ЭВА. САПР печатных плат, БИС, СБИС, ССБИС, | использованы и другие отношения вход-выход: «1 – 1»; «многие – | ||
изделий микро и наноэлектроники. Принятие решений в | 1»; «многие – многие». Схема поиска на основе додекаэдра. | ||
неопределенных и нечетких условиях. Проблема выбора оптимальных | 29 | Архитектуры и стратегии генетического поиска. Схема | |
решений в задачах науки и техники. | реализации процесса метагенетической оптимизации. Здесь основным | ||
3 | Объекты исследования. Решение многоэкстремальных задач с | является первый блок, в котором осуществляется реализация ГА, | |
линейными и нелинейными экстремальными функциями. Моделирование | генерация новых решений, определение значения ЦФ и использование | ||
функциями ситуаций в реальном масштабе времени. Решение линейных | предыдущих решений для генерации лучших результатов. Второй блок | ||
и нелинейных транспортных задач. Решение комбинаторно логических | позволяет использовать «историю» предыдущих решений для | ||
задач искусственного интеллекта. Решение задач принятия решений | генерации лучшего множества параметров. В третьем блоке | ||
военного назначения. | генерируется новое множество оптимизационных параметров. | ||
4 | Эволюционное моделирование (ЭМ). - основано на аналогии с | Метагенетический оптимизационный процесс. | |
естественными процессами селекции и генетическими | 30 | Архитектуры и стратегии генетического поиска. А. Б. | |
преобразованиями, протекающими в природе. Правила образования | Оптимизационные задачи используют в качестве исходного не одно, | ||
(синтаксис) системы ЭМ: построения модели эволюции; | а несколько альтернативных решений. Причем в зависимости от | ||
конструирования популяций; построения ЦФ; разработки ГО; | сложности перерабатываемой информации исходные решения могут | ||
репродукции популяций; рекомбинации популяций; редукции; Аксиомы | быть получены на основе стохастических, детерминированных или | ||
системы ЭМ: «Выживание сильнейших», т.е. переход решений с | комбинированных алгоритмов. Далее полученные решения | ||
лучшей целевой функцией в следующую генерацию. Размер популяции | обрабатываются адаптированными к решаемой задачи генетическими | ||
после каждой генерации остается постоянным. Обязательное | алгоритмами. | ||
применение во всех генетических алгоритмах операторов | 31 | Архитектуры и стратегии генетического поиска. Горизонтальная | |
кроссинговера и мутации. Число копий (решений), переходящих в | схема стратегии «эволюция – поиск – эволюция». Внутри блоков | ||
следующую генерацию, определяется по модифицированной формуле | «Поиск1 и Поиск2» организованы коммутирующие блоки с n входами и | ||
Холланда. | n выходами. Это позволяет соединять входы блоков поиска с | ||
5 | Классификация алгоритмов эволюционного моделирования. | выходами n! способами, что дает возможность расширять просмотр | |
6 | Классификация стратегий поиска. | пространства допустимых решений. Горизонтальная схема стратегии. | |
7 | Модель эволюции Ч. Дарвина. – Это условная структура, | 32 | Архитектуры и стратегии генетического поиска. Схема |
реализующая процесс, посредством которого особи (альтернативные | реализации стратегий «эволюция – поиск – эволюция – поиск – | ||
решения) некоторой популяции, имеющие более высокое | эволюция – поиск – эволюция». Схема стратегии «эволюция – поиск | ||
функциональное значение, получают большую возможность для | – эволюция – поиск – эволюция – поиск – эволюция». | ||
воспроизведения потомков, чем «слабые» особи. | 33 | Архитектуры и стратегии генетического поиска. Один из | |
8 | Модель эволюции Ж. Ламарка. - основана на предположении, что | возможных строительных блоков построения многоуровневой | |
характеристики, приобретенные особью в течение жизни, | архитектуры для решения инженерных задач. Здесь Р – начальная | ||
наследуются его потомками. Данная модель оказывается | популяция альтернативных решений. На создание новой популяции Р' | ||
эффективной, когда популяция имеет сходимость в область | оказывают влияние не только генетический алгоритм и блок | ||
локального оптимума. | эволюционной адаптации, но и внешняя среда. Из таких | ||
9 | Модель эволюции де Фриза. В ее основе лежит моделирование | строительных блоков, как из «кирпичиков», строится архитектура | |
социальных и географических катастроф, приводящих к резкому | поиска любой сложности. Схема строительного блока. Отметим, что | ||
изменению видов и популяций. | принятие решений в неопределенных, расплывчатых условиях при | ||
10 | Модель К. Поппера. Эволюционная последовательность событий | решении инженерных задач – это генерация возможных | |
представляется в виде схемы F1?TS????F2, где F1 – исходная | альтернативных решений, их оценка и выбор лучшей альтернативы. | ||
проблема, TS – пробные решения, ?? - устранение ошибок, F2 – | 34 | Архитектуры и стратегии генетического поиска. Укрупненная | |
новая проблема. – Это условная структура, реализующая | схема параллельного эволюционного поиска при разбиении популяции | ||
иерархическую систему гибких механизмов управления, в которых | на две подпопуляции. Здесь в блоках генетических операторов | ||
мутация интерпретируется как метод случайных проб и ошибок, а | выполняются операторы ОК, ОМ, инверсии, сегрегации, | ||
отбор как один из способов управления с помощью устранения | транслокации, удаления и вставки. В блоке редукции производится | ||
ошибок при взаимодействии с внешней средой. | удаление хромосом со значением ЦФ ниже средней. Схема | ||
11 | Модель нейтральной эволюции М. Кимуры. Основана на | параллельного эволюционного поиска. | |
нейтральном отборе. Эволюция заключается в реализации | 35 | Основные принципы совместного поиска: Принцип целостности. В | |
последовательностей поколений. В результате эволюции выбирается | генетических алгоритмах значение целевой функции альтернативного | ||
только один вид. | решения не сводится к сумме целевых функций частичных решений. | ||
12 | Условная упрощенная модифицированная схема модели | Принцип дополнительности. При решении оптимизационных задач | |
синтетической теории эволюции. представляет интеграцию различных | возникает необходимость использования различных не совместимых и | ||
моделей эволюций. Условия внешней среды здесь – не только | взаимодополняющих моделей эволюции и исходных объектов. Принцип | ||
факторы исключения неприспособленных особей из популяции, но и | неточности. При росте сложности анализируемой задачи уменьшается | ||
формирующие особенности самой модели. Основным этапом в каждой | возможность построения точной модели. Принцип управления | ||
модели является анализ популяции ее преобразование тем или иным | неопределенностью. Необходимо вводить различные виды | ||
способом и эволюционная смена форм. | неопределенности в генетические алгоритмы. Принцип соответствия. | ||
13 | Модифицированная базисная структура ПГА. | Язык описания исходной задачи должен соответствовать наличию | |
14 | Одноточечный кроссинговер. Рекомбинация участков хромосом, | имеющейся о ней информации. Принцип разнообразия путей развития. | |
представленных непрерывными моледкулами ДНК. Здесь может быть | Реализация генетических алгоритмов многовариантна и | ||
выделено несколько подтипов рекомбинации: Схема реализации | альтернативна. Существует много путей эволюции. Основная задача | ||
одноточечного кроссинговера. регулярная (общая) рекомбинация, | выбрать путь, приводящий к получению оптимального решения. | ||
представляющая собой кроссинговер, т.е. обмен гомологичными | 36 | Основные принципы совместного поиска: Окончание. Принцип | |
участками в различных точках гомологичных хромосом, приводящий к | единства и противоположности порядка и хаоса. «Хаос не только | ||
появлению нового сочетания сцепленных генов; спрайт - | разрушителен, но и конструктивен», т.е. в хаосе области | ||
специфическая рекомбинация, т.е. обмен генных носителей, часто | допустимых решений обязательно содержится порядок, определяющий | ||
разных по объему и составу, на коротких специализированных | искомое решение. Принцип совместимости и разделительности. | ||
участках; нереальная рекомбинация, реализующая негомологичные | Процесс эволюции носит поступательный, пульсирующий или | ||
обмены. Негомологичный обмен в целом не представляет интереса, | комбинированный характер. Поэтому модель синтетической эволюции | ||
т.к. появляются нереальные решения исследуемой задачи. | должна сочетать все эти принципы. Принцип иерархичности. | ||
15 | Двухточечный кроссинговер. Т. Морган предположил, что | Генетические алгоритмы могут подстраиваться сверху вниз и снизу | |
кроссинговер может происходить не только в одной, но и в двух и | вверх. Принцип «Бритвы Оккама». Нежелательно увеличивать | ||
даже большем числе точек. Схема двойного кроссинговера: а - до | сложность архитектуры поиска без необходимости. Бритва Оккама – | ||
кроссинговера; б - во время кроссинговера; в - после | принцип выдвинутый английским философом XIV века Уильямом | ||
кроссинговера. На рисунке представлена экспериментально | Оккамом «Понятия, не сводимые к интуитивному и опытному знанию | ||
установленная схема двойного кроссинговерамежду хромосомами (w и | следует исключать из науки». Принцип гомеостаза. Генетические | ||
f). | алгоритмы конструируются таким образом, что любое полученное | ||
16 | Селекция. Оператор репродукции (селекция) (ОР) ? это | альтернативное решение не выходило из области допустимых. | |
процесс, посредством которого хромосомы (альтернативные | 37 | Схема параллельного поиска. | |
решения), имеющие более высокое значение ЦФ (с «лучшими» | 38 | Методы повышения эффективности эволюционного моделирования. | |
признаками), получают большую возможность для воспроизводства | 39 | Методы повышения эффективности эволюционного моделирования. | |
(репродукции) потомков, чем «худшие» хромосомы. Селекция на | 40 | Инструментальная среда эволюционного моделирования. | |
основе рулетки. Существует большое число видов операторов | 41 | Инструментальная среда эволюционного моделирования | |
репродукции. К ним относятся: селекция на основе | (интерфейс). | ||
рулетки,селекция на основе заданной шкалы, элитная селекция , | 42 | Экспериментальные исследования. | |
турнирная селекция. | 43 | Основные результаты научной школы «Теория и принципы | |
17 | Инверсия. Инверсии – повороты участка или всей хромосомы на | построения интеллектуальных САПР на основе бионических и | |
180 градусов. Инвертированный участок при нечетной длине | эволюционных моделей». Специальные математические модели на | ||
хромосомы включает центральный ген (перецентрическая инверсия) | основе графов и гиперграфов для решения оптимизационных задач; | ||
или не включает его при четной длине хромосомы | Интеллектуальные процедуры решения оптимизационных задач; Новые | ||
(парацентрическая). здесь длина участка инвертированной | стратегии моделирования различных эволюций; Наборы правил и | ||
хромосомы L(P1) = 3. А парацентрическая инверсия, например, | знаний для интеллектуальных решателей задач; Архитектура | ||
такова: | интеллектуальной программной среды для применения методов | ||
18 | Модели и архитектуры эволюции. Модель прерывистого | генетической оптимизации; Экспертные оболочки для решения | |
равновесия Гулда-Элдриджа. Согласно этой модели эволюция | оптимизационных задач; Исследование механизмов основных | ||
происходит редкими и быстрыми толчками. Структура микроэволюции. | генетических операторов и на их основе разработка новых | ||
Структура макроэволюции. Эта модель является развитием и | модификаций алгоритмов, обеспечивающих оптимизацию структуры | ||
модификацией модели Г. де Фриза. Здесь отмечается различие | поиска; Новые подходы к решению оптимизационных задач на основе | ||
причин, от которых зависят темпы микро- и макроэволюции. | стратегий «поиск – эволюция – поиск», «эволюция – поиск – | ||
19 | Определения и понятия генетических алгоритмов. Цель | эволюция»; Новые технологии решения оптимизационных задач на | |
генетических алгоритмов состоит в том, чтобы: абстрактно и | основе методов агрегации фракталов; Проблемно-ориентированные | ||
формально объяснить адаптацию процессов в ЕС и интеллектуальной | ГА, вырабатывающие решение комбинаторных задач, представленных | ||
ИС; моделировать естественные эволюционные процессы для | как задачи параметрической оптимизации; Новые подходы к решению | ||
эффективного решения оптимизационных задач науки и техники. В | оптимизационных задач на основе системного подхода и принципов | ||
настоящее время используется новая парадигма решений | самоорганизации и саморегулирования; Разработка алгоритмов | ||
оптимизационных задач на основе генетических алгоритмов и их | решения комбинаторно-логических задач на основе генетических, | ||
различных модификаций. Генетические алгоритмы осуществляют поиск | синергетических методов и методов самообучения адаптивных | ||
баланса между эффективностью и качеством решений за счет | систем; Реализация программного комплекса поддержки среды | ||
«выживания сильнейших альтернативных решений», в неопределенных | решения оптимизационных задач и управления на основе адаптивных | ||
и нечетких условиях. Генетические алгоритмы отличаются от других | поисковых алгоритмов. Комплекс ориентирован на работу с IBM PC, | ||
оптимизационных и поисковых процедур следующим: работают в | допускается также использование комплекса в корпоративной сети | ||
основном не с параметрами задачи, а с закодированным множеством | предприятия. Демонстрационная версия комплекса представлялась | ||
параметров; осуществляют поиск не путем улучшения одного | различных на научно-технических конференциях и семинарах, также | ||
решения, а путем использования сразу нескольких альтернатив на | на международной выставке CEBIT’98 в Ганновере (Германия), | ||
заданном множестве решений; используют целевую функцию (ЦФ), а | международной конференции «Искусственные интеллектуальные | ||
не ее различные приращения для оценки качества принятия решений; | системы IEEE AIS’02». | ||
применяют не детерминированные, а вероятностные правила анализа | 44 | Эволюционный алгоритм для решения задач одномерной упаковки. | |
оптимизационных задач. | Предлагаемый алгоритм использует эволюционные процедуры для | ||
20 | Определения и понятия генетических алгоритмов. Генетический | одномерной упаковки произвольно заданного количества элементов в | |
алгоритм дает преимущества при решении практических задач. Одно | блоки. Программный продукт реализован в среде MS Windows на | ||
из них – это адаптация к изменяющейся окружающей среде. При | языке Borland C++ 4.5. Среда функционирования: MS WINDOWS 98, | ||
использовании традиционных методов все вычисления приходится | XP, 2000. Системные требования: Pentium 333, 128Mb RAM, + 4 Mb | ||
начинать заново, что приводит к большим затратам машинного | дискового пространства, графическое разрешение 800 Х 600 | ||
времени. При эволюционном подходе популяцию можно анализировать, | пикселей. | ||
дополнять и видоизменять применительно к изменяющимся условиям. | 45 | Алгоритм для оптимальной 2D упаковки со связями. Алгоритм | |
Преимущество генетических алгоритмов для решения задач состоит в | для оптимальной 2D упаковки со связями разработан для решения | ||
способности быстрой генерации достаточно хороших решений. При | проблемы упаковки элементов СБИС. Элементом СБИС представляется | ||
решении практических задач с использованием генетических | в виде прямоугольника с входами/выходами, расположенными по | ||
алгоритмов обычно выполняют четыре предварительных этапа: выбор | краям. Программный продукт оптимальной 2D упаковки со связями | ||
способа представления решения; разработка операторов случайных | имеет удобный и наглядный интерфейс. Имеется встроенный редактор | ||
изменений; определение способов «выживания» решений; создание | задач. В программе имеются три основных блока: Окно Редактора, | ||
начальной популяции альтернативных решений. | Окно Инспектора свойств, Окно Алгоритма. Среда функционирования: | ||
21 | Определения и понятия генетических алгоритмов. Эффективность | MS WINDOWS 98, XP, 2000. Системные требования: Pentium 333, | |
генетического алгоритма – степень реализации запланированных | 128Mb RAM, + 4 Mb дискового пространства, графическое разрешение | ||
действий алгоритма и достижение требуемых значений целевой | 800 Х 600 пикселей. | ||
функции. Эффективность во многом определяется структурой и | 46 | Алгоритм канальной трассировки. Алгоритм предназначен для | |
составом начальной популяции. При создании начального множества | проектирования двухслойных СБИС. Область трассировки - канал, | ||
решений происходит формирование популяции на основе четырех | ограниченный двумя линейками контактов. Цель - размещение | ||
основных принципов: «одеяла» – генерируется полная популяция, | фрагментов цепей в минимальном числе магистралей. Программный | ||
включающая все возможные решения в некоторой заданной области; | продукт реализован в среде Windows на языке Си++ для IВМ РС. При | ||
«дробовика» – подразумевает случайный выбор альтернатив из всей | фиксированных значениях управляющих параметров программа имеет | ||
области решений данной задачи. «фокусировки» – реализует | оценку временной и пространствеpной сложности О(K), где K - | ||
случайный выбор допустимых альтернатив из заданной области | число связываемых контактов. Предложенная программа с небольшой | ||
решений данной задачи. Комбинирования – состоит в различных | модификацией применима для без сеточной трассировки соединений | ||
совместных реализациях первых трех принципов. | разной ширины в многослойной СБИС. | ||
22 | Простой (одноточечный) оператор кроссинговера. Р1 : 1 1 | 1 | 47 | Алгоритм N-мерной упаковки элементов со связями. Алгоритм |
1 1 р2 : 0 0 | 0 0 0 ________________ р'1 : 1 1 | 0 0 0 р'2 : 0 | оптимальной N-мерной упаковки со связями разработан для решения | ||
0 | 1 1 1. Перед началом работы одноточечного оператора | проблемы упаковки элементов, имеющих любое количество измерений. | ||
кроссинговера определяется так называемая точка оператора | Целью упаковки является нахождение такого легального размещения | ||
кроссинговера, или разрезающая точка оператора кроссинговера, | элементов, при котором объем ограничивающей прямоугольной | ||
которая обычно определяется случайно. Эта точка определяет место | области будет минимален. Программный продукт N-мерной упаковки | ||
в двух хромосомах, где они должны быть «разрезаны». Одноточечный | элементов со связями имеет удобный и наглядный интерфейс. | ||
оператор кроссинговера. Одноточечный оператор кроссинговера | Имеется встроенный редактор задач. В программе имеются три | ||
выполняется в три этапа: Две хромосомы A = а1, а2,.., аL и B = | основных блока: Окно Редактора, Окно Инспектора свойств, Окно | ||
a?1, a?2,.., a?L выбираются случайно из текущей популяции. Число | Алгоритма. Среда функционирования: MS WINDOWS 98, XP, 2000. | ||
k выбирается из {1,2,...,L-1} также случайно. Здесь L - длина | Системные требования: Pentium 333, 128Mb RAM, + 4 Mb дискового | ||
хромосомы, k - точка оператора кроссинговера (номер, значение | пространства, графическое разрешение 800 Х 600 пикселей. | ||
или код гена, после которого выполняется разрез хромосомы). Две | 48 | Алгоритм генетического разбиения гиперграфа на подграфы с | |
новые хромосомы формируются из A и B путем перестановок | элементами самоорганизации (ГАСЭС). Алгоритм ГАСЭС позволяет | ||
элементов согласно правилу. | решать задачу компоновки элементов СБИС по критерию суммарного | ||
23 | Двухточечный и N-точечный оператор кроссинговера. Р1 : 1 1 1 | числа цепей между узлами, с учётом тепловой совместимости | |
| 0 1 | 0 0 р2 : 0 0 0 | 1 1 | 1 0 ____________________ р'1 : 1 | компонуемых элементов. Программный продукт, позволяет проводить | ||
1 1 | 1 1 | 0 0 р'2 : 0 0 0 | 0 1 | 1 0. Пример трехточечного | экспериментальные исследования в зависимости от значений | ||
оператора кроссинговера. Р1 : 1 | 1 1 |0 1 | 0 0 р2 : 0 |0 0 |1 | основных параметров алгоритма и динамических параметров. В | ||
0 | 1 1 ____________________ р'1 : 1| 0 0 | 0 1 | 1 1 р'2 : 0 |1 | главном окне отображается процесс работы алгоритма и другая | ||
1 | 1 0 | 0 0. В каждой хромосоме определяются две точки | вспомогательная информация. Результаты экспериментальных | ||
оператора кроссинговера, и хромосомы обмениваются участками, | исследований показали, что ГАСЭС по сравнению с простым | ||
расположенными между двумя точками оператора кроссинговера. | генетическим алгоритмом (ПГА) позволяет повысить качество | ||
Пример двухточечного оператора кроссинговера. Развитием | компоновки схем от 2% до 5%, в зависимости от задачи. Системные | ||
двухточечного оператора кроссинговера является многоточечный | требования: Pentium II 400, 128MB RAM, HDD 5MB. Среда | ||
оператор кроссинговера или N-точечный оператор кроссинговера. | функционирования: MS Windows 9x, 2000, XP. | ||
Многоточечный оператор кроссинговера выполняется аналогично | 49 | Алгоритм канальной трассировки для цепей различной ширины. | |
двухточечному оператору кроссиновера, хотя большое число | Алгоритм канальной трассировки для цепей различной ширины | ||
«разрезающих» точек может привести к потере «хороших» | позволяет получить топологию канальной области с цепями, | ||
родительских свойств. | имеющими различную ширину. Алгоритм использует теорию | ||
24 | Универсальный оператор кроссинговера. Р1 : 0 1 1 0 0 1 P2 : | эволюционного моделирования и методы генетического поиска. | |
0 1 0 1 1 1 ________________ 0 1 1 0 1 0 ? маска _______________ | Программный продукт канальной трассировки позволяет проводить | ||
P'1 : 0 0 0 0 1 1 P'2 : 0 0 1 1 0 1. Маска может быть задана или | экспериментальные исследования в автоматическом и пошаговом | ||
выбирается случайно с заданной вероятностью или на основе | режиме. Критерии оптимизации алгоритма канального трассировщика: | ||
генератора случайных чисел. При этом чередование 0 и 1 в маске | ширина канальной области, суммарная длина цепей, число | ||
происходит с вероятностью ?50%. В некоторых случаях используется | межслойных переходов. Входные данные: число выводов; ширины | ||
параметризированный универсальный оператор кроссинговера, где | цепей; номера цепей, подключаемых к выводам. Выходные данные: | ||
маска может выбираться с вероятностью для 1 или 0 выше, чем 50%. | топология канала Среда функционирования: MS WINDOWS 98, XP 2000. | ||
Такой вид маски эффективен, когда хромосомы кодируются в | Системные требования: Pentium 333, 128Mb RAM, + 70 Mb дискового | ||
двоичном алфавите. Вместо использования разрезающей точки | пространства, разреш. 800*600. | ||
(точек) в универсальный оператор кроссинговера определяют | 50 | Алгоритм размещения на основе поисковой адаптации. Алгоритм | |
двоичную маску, длина которой равна длине заданных хромосом. | решает задачу размещения множества элементов в непересекающемся | ||
Первый потомок получается сложением первого родителя с маской на | множестве позиций. Используется новый критерий, учитывающий | ||
основе следующих правил (0+0=0, 0+1=1, 1+1=0). Второй потомок | распределение ресурсов коммутационного поля. Процесс решения | ||
получается аналогичным образом. Для каждого элемента в Р1, Р2 | задачи размещения осуществляется адаптивной поисковой | ||
гены меняются. Универсальный оператор кроссинговера. | процедурой, основанной на сочетании генетического поиска с | ||
25 | Одноточечный и двухточечный операторы мутации. Р1 : 0 1 1 | | адаптацией на основе самообучения и самоорганизации. Программный | |
0 1 1 р'1 : 0 1 0 | 1 1 1. Р : a | b c d | e f p' : a e с d b f. | продукт реализован в среде Windows на языке Си++ для IВМ РС | ||
Оператор мутации – это языковая конструкция, позволяющая на | Временная сложность при совместной работе алгоритмов и при | ||
основе преобразования родительской хромосомы (или ее части) | фиксированных значениях управляющих параметров на одной итерации | ||
создавать хромосому потомка. Простейшим оператором мутации | имеет оценку О(n). При совместной работе алгоритмов вероятность | ||
является одноточечный. При его реализации случайно выбирают ген | получения глобального оптимума составила 0.95. В среднем, трех | ||
в родительской хромосоме и, обменивая его на рядом расположенный | запусков программы со случайными начальными популяциями | ||
ген, получают хромосому потомка. Одноточечный оператор мутации. | достаточно для нахождения решения со средним отклонением от | ||
Р1 – родительская хромосома, а Р'1 – хромосома-потомок после | глобального оптимума в 1%. Системные требования: Pentium II 400, | ||
применения одноточечного оператора мутации. При реализации | 128MB RAM, HDD 5MB. Среда функционирования: MS Windows 98, 2000, | ||
двухточечного оператора мутации случайным или направленным | XP. | ||
образом выбираются две точки разреза. Затем производится | 51 | Алгоритм планирования кристалла СБИС. Алгоритм планирования | |
перестановка генов между собой, расположенных справа от точек | кристалла СБИС решает задачу размещении на поле кристалла | ||
разреза. Двухточечный оператор мутации. Р1 – родительская | блоков, имеющих заданную площадь и не имеющих фиксированных | ||
хромосома, а Р'1 – хромосома-потомок после применения | размеров. Блоки и кристалл имеют форму прямоугольников. | ||
двухточечного оператора мутации. | Программный продукт реализован в среде Windows на языке Си++ для | ||
26 | Архитектуры и стратегии генетического поиска. Схема при | IВМ РС. Оценка временной сложности на одной итерации – О(N). | |
наличии большого количества вычислительных ресурсов может быть | N-число блоков. Среда функционирования: MS WINDOWS 98, XP, 2000. | ||
доведена до N блоков. Причем N ? 1 блоков могут параллельно | Системные требования: Pentium 333, 128Mb RAM, HDD 5MB. | ||
осуществлять эволюционную адаптацию и через блоки миграции | 52 | Алгоритм эволюционного проектирования высокопроизводительных | |
обмениваться лучшими представителями решений. Последний блок | интегральных схем. Входные данные: набор элементов, описание | ||
собирает лучшие решения, может окончить результат работы или | связей между элементами. Результат: размещение элементов на | ||
продолжить эволюционный поиск. Схема эволюционного поиска на | коммутационном поле. Операционная система: Windows | ||
основе миграции. | 95\98\2000\XP. Оперативная память: 128 MB. Процессор: Pentium II | ||
27 | Архитектуры и стратегии генетического поиска. Платоновы | 667. При этих условиях размещение 4,5 тыс. элементов | |
графы, то есть правильные многоугольники, которые, как считалось | производится за 420 секунд. Алгоритм предназначен для | ||
в древних учениях, обладают внутренней красотой и гармонией. | многослойного размещения элементов интегральных схем с учетом | ||
Использовано отношение вход-выход «1 – многие». Отметим, что | неоднородности межэлементных соединений. Размещение элементов | ||
здесь могут быть использованы и другие отношения вход-выход: «1 | производится в нескольких слоях. При расчете функции пригодности | ||
– 1»; «многие – 1»; «многие – многие». Эффективность таких | используется модель задержки распространения сигналов Элмора. | ||
отношений проверяется экспериментально. Под эффективностью | Результат работы программы. | ||
понимается степень реализации запланированной деятельности и | |||
«Генетические алгоритмы» | Генетические алгоритмы.ppt |
«Ненаследственная изменчивость» - Делаем измерение. Норма реакции- степень варьирования признака от минимального до максимального значения. Цель занятия: Сущность метода. Проводится с использованием компьютерной технологии. Свойства модификационной изменчивости. Для удобства обработки результаты стоит немного округлить. Значение для отдельной особи, вида.
«Закономерности изменчивости» - Ген. 1.-Г 2.-Б 3.-Б 4.-А 5.-Б. Факторы окружающей среды. Проверка результатов теста. Лабораторная работа. Выводы: Фенотип. Формы изменчивости. Ген Фенотип Факторы окружающей среды Признак Генотип. Белок. Что изучает генетика? Составьте таблицу вариационнного ряда изменчивости фасоли. Каким способом передаются наследственные признаки?
«Наследственность и изменчивость» - Популяция состоит из наследственно различных особей или родственных групп – линий. На Тему: История развития генетики. Презентация. Экспериментально доказывая, что основными носителями генов являются хромосомы, и что гены располагаются в хромосомах линейно. Сам Дарвин приложил немало усилий для изучения наследственности и изменчивости.
«Законы Менделя» - При моногибридном скрещивании брались особи, различавшиеся только по одному признаку. Ab. Какое скрещивание называется моногибридным? AB. Р. Составитель учитель высшей категории Горячкина О.Ю. ?. AABB. П о в т о р и м. Третий закон Менделя – закон независимого комбинирования.
«Первый закон Менделя» - Генетические символы. История развития генетики. А. Объект изучения. Грегор иоганн мендель 1822-1884. Дано: Решение: А – желтые семена Р: ?АА х ?аа а– зеленые семена G А а. Задачи и методы генетики.Первый и второй законы г.Менделя. Моногибридное скрещивание. Первый закон менделя.