Эволюционное моделирование (ЭМ). Объекты исследования Схемотехническое и конструкторское проектирование РЭА и ЭВА. САПР печатных плат, БИС, СБИС, ССБИС, - презентация

1 Эволюционное моделирование (ЭМ)

2 Объекты исследования Схемотехническое и конструкторское проектирование РЭА и ЭВА. САПР печатных плат, БИС, СБИС, ССБИС, изделий микро и наноэлектроники. Принятие решений в неопределенных и нечетких условиях. Проблема выбора оптимальных решений в задачах науки и техники. Решение многоэкстремальных задач с линейными и нелинейными экстремальными функциями. Моделирование функциями ситуаций в реальном масштабе времени. Решение линейных и нелинейных транспортных задач. Решение комбинаторно логических задач искусственного интеллекта. Решение задач принятия решений военного назначения.

3 Эволюционное моделирование (ЭМ) - основано на аналогии с естественными процессами селекции и генетическими преобразованиями, протекающими в природе. Правила образования (синтаксис) системы ЭМ: построения модели эволюции; конструирования популяций; построения ЦФ; разработки ГО; репродукции популяций; рекомбинации популяций; редукции; Аксиомы системы ЭМ: «Выживание сильнейших», т.е. переход решений с лучшей целевой функцией в следующую генерацию. Размер популяции после каждой генерации остается постоянным. Обязательное применение во всех генетических алгоритмах операторов кроссинговера и мутации. Число копий (решений), переходящих в следующую генерацию, определяется по модифицированной формуле Холланда

4 Классификация алгоритмов эволюционного моделирования

5 Классификация стратегий поиска

6 Модель эволюции Ч. Дарвина – это условная структура, реализующая процесс, посредством которого особи (альтернативные решения) некоторой популяции, имеющие более высокое функциональное значение, получают большую возможность для воспроизведения потомков, чем «слабые» особи.

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

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

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

10 Модель нейтральной эволюции М. Кимуры Основана на нейтральном отборе. Эволюция заключается в реализации последовательностей поколений. В результате эволюции выбирается только один вид.

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

12 Модифицированная базисная структура ПГА

13 Одноточечный кроссинговер Рекомбинация участков хромосом, представленных непрерывными моледкулами ДНК. Здесь может быть выделено несколько подтипов рекомбинации: регулярная (общая) рекомбинация, представляющая собой кроссинговер, т.е. обмен гомологичными участками в различных точках гомологичных хромосом, приводящий к появлению нового сочетания сцепленных генов; спрайт - специфическая рекомбинация, т.е. обмен генных носителей, часто разных по объему и составу, на коротких специализированных участках; нереальная рекомбинация, реализующая негомологичные обмены. Негомологичный обмен в целом не представляет интереса, т.к. появляются нереальные решения исследуемой задачи. Схема реализации одноточечного кроссинговера

14 Двухточечный кроссинговер Т. Морган предположил, что кроссинговер может происходить не только в одной, но и в двух и даже большем числе точек. Схема двойного кроссинговера: а - до кроссинговера; б - во время кроссинговера; в - после кроссинговера На рисунке представлена экспериментально установленная схема двойного кроссинговера между хромосомами (w и f).

15 Селекция Оператор репродукции (селекция) (ОР) это процесс, посредством которого хромосомы (альтернативные решения), имеющие более высокое значение ЦФ (с «лучшими» признаками), получают большую возможность для воспроизводства (репродукции) потомков, чем «худшие» хромосомы. Селекция на основе рулетки Существует большое число видов операторов репродукции. К ним относятся: селекция на основе рулетки,селекция на основе заданной шкалы, элитная селекция, турнирная селекция.

16 Инверсия Инверсии – повороты участка или всей хромосомы на 180 градусов. Инвертированный участок при нечетной длине хромосомы включает центральный ген (перицентрическая инверсия) или не включает его при четной длине хромосомы (парацентрическая). здесь длина участка инвертированной хромосомы L(P1) = 3. А парацентрическая инверсия, например, такова:

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

18 Генетических алгоритмов Цель генетических алгоритмов состоит в том, чтобы: абстрактно и формально объяснить адаптацию процессов в ЕС и интеллектуальной ИС; моделировать естественные эволюционные процессы для эффективного решения оптимизационных задач науки и техники. В настоящее время используется новая парадигма решений оптимизационных задач на основе генетических алгоритмов и их различных модификаций. Генетические алгоритмы осуществляют поиск баланса между эффективностью и качеством решений за счет «выживания сильнейших альтернативных решений», в неопределенных и нечетких условиях. Генетические алгоритмы отличаются от других оптимизационных и поисковых процедур следующим: работают в основном не с параметрами задачи, а с закодированным множеством параметров; осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений; используют целевую функцию (ЦФ), а не ее различные приращения для оценки качества принятия решений; применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

19 Генетический алгоритм дает преимущества при решении практических задач. Одно из них – это адаптация к изменяющейся окружающей среде. При использовании традиционных методов все вычисления приходится начинать заново, что приводит к большим затратам машинного времени. При эволюционном подходе популяцию можно анализировать, дополнять и видоизменять применительно к изменяющимся условиям. Преимущество генетических алгоритмов для решения задач состоит в способности быстрой генерации достаточно хороших решений. При решении практических задач с использованием генетических алгоритмов обычно выполняют четыре предварительных этапа: выбор способа представления решения; разработка операторов случайных изменений; определение способов «выживания» решений; создание начальной популяции альтернативных решений.

20 Эффективность генетического алгоритма – степень реализации запланированных действий алгоритма и достижение требуемых значений целевой функции. Эффективность во многом определяется структурой и составом начальной популяции. При создании начального множества решений происходит формирование популяции на основе четырех основных принципов: «одеяла» – генерируется полная популяция, включающая все возможные решения в некоторой заданной области; «дробовика» – подразумевает случайный выбор альтернатив из всей области решений данной задачи. «фокусировки» – реализует случайный выбор допустимых альтернатив из заданной области решений данной задачи. Комбинирования – состоит в различных совместных реализациях первых трех принципов.

21 Простой (одноточечный) оператор кроссинговера Перед началом работы одноточечного оператора кроссинговера определяется так называемая точка оператора кроссинговера, или разрезающая точка оператора кроссинговера, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны». Одноточечный оператор кроссинговера Одноточечный оператор кроссинговера выполняется в три этапа: Две хромосомы A = а 1, а 2,.., аL и B = a 1, a 2,.., a L выбираются случайно из текущей популяции. Число k выбирается из {1,2,...,L-1} также случайно. Здесь L - длина хромосомы, k - точка оператора кроссинговера (номер, значение или код гена, после которого выполняется разрез хромосомы). Две новые хромосомы формируются из A и B путем перестановок элементов согласно правилу Р1: 1 1 | Р2: 0 0 | ________________ Р'1: 1 1 | Р'2 : 0 0 | 1 1 1

22 Двухточечный и N-точечный оператор кроссинговера В каждой хромосоме определяются две точки оператора кроссинговера, и хромосомы обмениваются участками, расположенными между двумя точками оператора кроссинговера. Р1: | 0 1 | 0 0 Р2: | 1 1 | 1 0 ____________________ Р'1: | 1 1 | 0 0 Р'2: | 0 1 | 1 0 Пример двухточечного оператора кроссинговера Развитием двухточечного оператора кроссинговера является многоточечный оператор кроссинговера или N-точечный оператор кроссинговера. Многоточечный оператор кроссинговера выполняется аналогично двухточечному оператору кроссинговера, хотя большое число «разрезающих» точек может привести к потере «хороших» родительских свойств. Р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 Пример трехточечного оператора кроссинговера

23 Универсальный оператор кроссинговера Вместо использования разрезающей точки (точек) в универсальный оператор кроссинговера определяют двоичную маску, длина которой равна длине заданных хромосом. Первый потомок получается сложением первого родителя с маской на основе следующих правил (0+0=0, 0+1=1, 1+1=0). Второй потомок получается аналогичным образом. Для каждого элемента в Р1, Р2 гены меняются. Р1: P2: ________________ маска _______________ P'1: P'2: Универсальный оператор кроссинговера Маска может быть задана или выбирается случайно с заданной вероятностью или на основе генератора случайных чисел. При этом чередование 0 и 1 в маске происходит с вероятностью 50%. В некоторых случаях используется параметризированный универсальный оператор кроссинговера, где маска может выбираться с вероятностью для 1 или 0 выше, чем 50%. Такой вид маски эффективен, когда хромосомы кодируются в двоичном алфавите.

24 Одноточечный и двухточечный операторы мутации Оператор мутации – это языковая конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части) создавать хромосому потомка. Простейшим оператором мутации является одноточечный. При его реализации случайно выбирают ген в родительской хромосоме и, обменивая его на рядом расположенный ген, получают хромосому потомка. Р1: | Р'1: | При реализации двухточечного оператора мутации случайным или направленным образом выбираются две точки разреза. Затем производится перестановка генов между собой, расположенных справа от точек разреза. Р: A | B C D | E F P': A E С D B F Одноточечный оператор мутации Р1 – родительская хромосома, а Р'1 – хромосома-потомок после применения одноточечного оператора мутации Двухточечный оператор мутации Р1 – родительская хромосома, а Р'1 – хромосома-потомок после применения двухточечного оператора мутации

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

26 Платоновы графы, то есть правильные многоугольники, которые, как считалось в древних учениях, обладают внутренней красотой и гармонией. Использовано отношение вход- выход «1 – многие». Отметим, что здесь могут быть использованы и другие отношения вход- выход: «1 – 1»; «многие – 1»; «многие – многие». Эффективность таких отношений проверяется экспериментально. Под эффективностью понимается степень реализации запланированной деятельности и достижения запланированных результатов. Схема поиска на основе тетраэдра

27 Упрощенные схемы организации связей при эволюционном поиске на основе Платоновых графов додекаэдра. Отметим, что здесь могут быть использованы и другие отношения вход-выход: «1 – 1»; «многие – 1»; «многие – многие». Схема поиска на основе додекаэдра

28 Метагенетический оптимизационный процесс Схема реализации процесса метагенетической оптимизации. Здесь основным является первый блок, в котором осуществляется реализация ГА, генерация новых решений, определение значения ЦФ и использование предыдущих решений для генерации лучших результатов. Второй блок позволяет использовать «историю» предыдущих решений для генерации лучшего множества параметров. В третьем блоке генерируется новое множество оптимизационных параметров.

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

30 Горизонтальная схема стратегии «эволюция – поиск – эволюция». Внутри блоков «Поиск 1 и Поиск 2» организованы коммутирующие блоки с n входами и n выходами. Это позволяет соединять входы блоков поиска с выходами n! способами, что дает возможность расширять просмотр пространства допустимых решений. Горизонтальная схема стратегии

31 Схема реализации стратегий «эволюция – поиск – эволюция – поиск – эволюция – поиск – эволюция». Схема стратегии «эволюция – поиск – эволюция – поиск – эволюция – поиск – эволюция»

32 Один из возможных строительных блоков построения многоуровневой архитектуры для решения инженерных задач. Здесь Р – начальная популяция альтернативных решений. На создание новой популяции Р' оказывают влияние не только генетический алгоритм и блок эволюционной адаптации, но и внешняя среда. Из таких строительных блоков, как из «кирпичиков», строится архитектура поиска любой сложности. Схема строительного блока Отметим, что принятие решений в неопределенных, расплывчатых условиях при решении инженерных задач – это генерация возможных альтернативных решений, их оценка и выбор лучшей альтернативы.

33 Схема параллельного эволюционного поиска Укрупненная схема параллельного эволюционного поиска при разбиении популяции на две подпопуляции. Здесь в блоках генетических операторов выполняются операторы ОК, ОМ, инверсии, сегрегации, транслокации, удаления и вставки. В блоке редукции производится удаление хромосом со значением ЦФ ниже средней.

34 Основные принципы совместного поиска: Принцип целостности. В генетических алгоритмах значение целевой функции альтернативного решения не сводится к сумме целевых функций частичных решений. Принцип дополнительности. При решении оптимизационных задач возникает необходимость использования различных не совместимых и взаимодополняющих моделей эволюции и исходных объектов. Принцип неточности. При росте сложности анализируемой задачи уменьшается возможность построения точной модели. Принцип управления неопределенностью. Необходимо вводить различные виды неопределенности в генетические алгоритмы. Принцип соответствия. Язык описания исходной задачи должен соответствовать наличию имеющейся о ней информации. Принцип разнообразия путей развития. Реализация генетических алгоритмов многовариантна и альтернативна. Существует много путей эволюции. Основная задача выбрать путь, приводящий к получению оптимального решения. Принцип единства и противоположности порядка и хаоса. «Хаос не только разрушителен, но и конструктивен», т.е. в хаосе области допустимых решений обязательно содержится порядок, определяющий искомое решение.

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

36 Схема параллельного поиска

37 Методы повышения эффективности эволюционного моделирования

38

39 Инструментальная среда эволюционного моделирования