45431

Эволюционное программирование (генетические алгоритмы)

Доклад

Информатика, кибернетика и программирование

Метод алгоритм пример решения задачи Эволюционное программирование генетические алгоритмы Для эволюционного программирования должны выполняться следующие требования: 1Наличие пространства параметров x = {x1x2x3.е случайное варьирование параметров. Хромосома вектор варьируемых параметров решения Операции получение новых решений из существующих Скрещивание получение параметров хромосомы от родителей расширение области поиска Мутация ...

Русский

2013-11-17

57.5 KB

31 чел.

  1.  Генетические алгоритмы. Метод, алгоритм, пример решения задачи

Эволюционное программирование (генетические алгоритмы)

           Для эволюционного программирования должны выполняться следующие требования:

      1)Наличие пространства параметров x = {x1,x2,x3,...,xn}, называемое геномом.

            2)Возможность вариации в геноме - мутации. Т.е случайное варьирование

     параметров.

            3) Моделирование взаимодействия полученного варианта со средой. Оценка со

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

     признака.

          Примеры

 

          Проектирование волнореза в Новороссийске. Требовалось сконструировать

     волнорез. Обычными средствами это сделать продолжительное время не

     удавалось. Тогда было использовано эволюционное программирование. В

     качестве генома использовались геометрические параметры волнореза. Была

     создана модель окружающей среды, на которой отрабатывались возникающие

     вариации.

      

     рис.5.3

          Генерирование реалистичных изображений.

Описание можно посмотреть в  статьях:

     "Компьютер моделирует эволюцию растений",

     "Программы, моделирующие эволюцию биологических видов палеозоя и эволюцию

     английских   фамилий",

     "Программирование и искусство."

           Компоновка ракеты по обтекаемости. Есть три компоненты. Требуется  сложить их вместе для получения максимального объема и максимальной обтекаемостью. С помощью эволюционного программирования был получен следующий результат.

      

     рис.5.4

          Геометрическое моделирование.

      

     рис.5.5

           Набирая комбинации элементарных функций D1-D8, можно спроектироватьмножество различных геометрических областей. Например, ФОРМУЛА для  картинки сложной области может иметь вид:

     D1*(1-D2)+D3*D4*D7+D8*D6*D4*(1-D5) или подобный этому. Вариации могут  подвергнуться в формуле знаки, скобки, индексы. Будут получаться все новые фигуры.

           Требуется очень тщательно прорабатывать параметры генома. Он должен иметь как можно более общий вид. Варьировать параметры нужно непрерывней. На данной идее развился метод, получивший название "Искусственная жизнь" Artificial life.

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

     Черты метода:

     -адаптация решения к условиям внешнего мира,

     -передача черт по наследству,

     -мутации,

     -имитация выживаемости.

          Понятия метода.

     Хромосома - вектор варьируемых параметров решения

     Операции - получение новых решений из существующих

     Скрещивание - получение параметров хромосомы от родителей, расширение

     области поиска

     Мутация - случайное изменение параметров при копировании

     Реакция мира - уничтожение процента худших особей (по критерию среды),

     сужение области поиска

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

           

Генетические алгоритмы

      С математической точки зрения генетические алгоритмы (genetic algorithms, GA) - это разновидность методов оптимизации, объединяющая черты  вероятностных и детерминированных оптимизационных алгоритмов. Поиск оптимального решения с помощью GA начинается с представления параметров  решения в виде вектора (целочисленного или битового) - "генетического кода" или "хромосомы". Далее определяется набор операций, позволяющих получать новые решения из совокупности существующих. Продолжая аналогию с генетическими механизмами реального мира, "дочернее" решение может порождаться одним или двумя "родителями", наследуя черты обоих вследствие операций скрещивания. Однако (и это, пожалуй, самое важное) новые поколения копируют свойства предшественников неточно. Присутствует специальный механизм мутации, привносящий случайные искажения. Наконец, модель внешнего мира при реализации генетических алгоритмов обычно увы, отсутствует, что отличает GA от Artificial life в целом. Реакция внешнего мира заменяется заранее заданной целевой функцией, позволяющей сравнивать качество полученных решений. Далее все просто. На основе одного-двух начальных решений порождается первое поколение последующих решений. Для каждого вычисляется значение функции качества, после чего определенный процент наихудших решений уничтожается, а наилучших - скрещивается. Так появляется следующее  поколение. Мутации периодически расширяют базу для селекции, не позволяя  процессу вырождаться. Через несколько поколений значение функции качества  перестает расти. Это означает, что выведено семейство решений, наилучшим образом удовлетворяющих заданным критериям. Остается только "расшифровать"  генетический код итоговых решений и перевести их в привычный для разработчика вид.

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

      Представьте себе бесконечный теплый океан, населенный студнеобразными  комками биомассы. Каждый комок не имеет разума и органов чувств, однако наделен зачатками двигательных функций (скажем, способностью к  периодическим рефлекторным сокращениям). Единственное, что он умеет, - достигнув некоторого возраста, поделиться надвое, передав потомству свою  форму (с некоторыми искажениями, вызванными мутациями), а вместе с ней и способность к передвижению. К сожалению, это не главный обитатель океана. Подлинными его хозяевами являются акулы - быстрые, хищные и высокоорганизованные существа, которые едят все, что плавает медленнее их.  Поначалу кажется, что у несчастной биомассы нет никаких шансов на выживание, поскольку все, что она может противопоставить хищникам, - это скорость размножения. Но давайте запустим генетический алгоритм. Вот прошло сто поколений. Теперь океан населен разнообразными видами "червей", и иные из них достаточно успешно соревнуются с акулами по скорости передвижения. А часы эволюции идут... Прошло еще несколько сотен поколений. Где же наши бесформенные комки? По всему океану снуют красивые торпедообразные рыбы (некоторые даже снабжены разновидностью плавников). Теперь тяжелые времена переживают акулы: им в пищу достаются лишь редкие медлительные особи - следствие неудачных мутаций. Вдумайтесь - мы заведомо лишили бедный "кисель" шансов на появление зрения, сознания и каких бы то ни было средств защиты, оставив единственное оружие - право на эволюцию. И тем самым не только спасли его от вымирания, но и породили ряд новых,

более совершенных форм.

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

      Особняком стоит такая экзотическая область, как компьютерная вирусология.   Исследователи, использующие методы A-life, подошли к этой проблеме, трактуя компьютерные вирусы как специфическую разновидность искусственной жизни, способную к мутациям, размножению, инфицированию среды обитания и самосовершенствованию. При такой трактовке становится реальностью давняя идея об универсальном антивирусе, который будет обнаруживать не конкретные  виды вирусов (как большинство существующих программ), а проявления новых форм компьютерной жизни - изменение дисциплины обработки прерываний, нетипичное поведение известных программ, незнакомый "почерк" общения  программ с файловой системой и т. п. Фирма IBM уже анонсировала первый коммерческий антивирус, построенный на подобных принципах.

       

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

      Генетические алгоритмы в основном применяются для решения задач оптимизации, т.е. задач, в которых есть некоторая функция нескольких  переменных F(x1, x2, ... ,xn) и необходимо найти либо её максимум, либо её минимум. Функция F называется целевой функцией, а переменные - параметрами функции. Генетические алгоритмы "пришиваются" к данной задаче следующим образом. Параметры задачи являются генетическим материалом - генами. Совокупность генов составляет хромосому. Каждая особь обладает своей хромосомой, а, следовательно, своим набором параметров. Подставив параметры в целевую функцию, можно получить какое-то значение. То, насколько это значение удовлетворяет поставленным условиям, определяет характеристику особи, которая называется приспособленностью (fitness). Функция, определяющая  приспособленность должна удовлетворять следующему условию: чем "лучше" особь, тем выше приспособленность. Генетические алгоритмы работают с популяцией как правило фиксированного размера, состоящей из особей, заданных при помощи способа, описанного выше. Вот здесь начинается самое  интересное. Особи "скрещиваются" между собой с помощью генетических операторов(о том как происходит этот захватывающий процесс - отдельно), естественно, получается потомство, причем часть потомков заменяют представителей более старого поколения в соответствии со стратегией формирования нового поколения. Кстати, выбор особей для скрещивания проводится согласно селективной стратегии (selection strategy). Так вот,  заново сформированная популяция снова оценивается, затем выбираются наиболее достойные для скрещивания особи, которые "встречаются,  влюбляются, женятся", получаются дети, занимают место престарелых  индивидуумов и т.д.

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

    

Области применения ГА:

       Экстремальные задачи (нахождение точек минимума и минимума);

       Задачи о кратчайшем пути;

       Задачи компоновки;

       Составление расписаний;

       Аппроксимация функций;

       Отбор(фильтрация) входных данных;

       Настройка искусственной нейронной сети;

       Моделирование искусственной жизни (Artificial life systems)

       Биоинформатика (свертывание белков и РНК);

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

       Нелинейная фильтрация;

       Развивающиеся агенты/машины (Evolvable agents/machines);  Некоторые разделы могут содержать подпункты. Так, например, экстремальные задачи включают в себя целый класс задач линейного и нелинейного программирования.


 

А также другие работы, которые могут Вас заинтересовать

58148. Понятие об инфинитиве. Порядок слов в повествовательном предложении 130 KB
  Поскольку в современном английском языке у существительных есть всего два падежа, в предложении существует жесткий порядок слов, изменение которого может привести к нарушению смысла предложения.
58149. Сенсорный пульт управления 1.2 MB
  Основными критериями при выборе элементной базы являлись требования по надежности и температурному режиму. Также большое внимание уделялось габаритным размерам электронных компонентов и наличию технической документации.
58150. Неличные формы глагола. Причастие. Причастные обороты. Герундий. Герундиальные обороты 198 KB
  Being introduced on the railways, the automatic train control will facilitate both the work of the driver and the dispatcher. Comprising all spheres of railway operation telecommunication greatly contributes to increased reliability of railway service.
58151. Общество и государство 215.5 KB
  Общество - совокупность людей, объединенных сознанием того, что у них есть общие постоянные потребности и интересы, которые могут быть удовлетворены наилучшим образом только их совместными усилиями.
58152. Кодирование информации с помощью знаковых систем 75 KB
  Информационные процессы; рассказать учащимся о кодировании информации с помощью знаковых систем; рассказать учащимся о знаках их формах и значении; развивать у учащихся интерес к предмету и к работе на ПК; воспитывать дисциплинированность целеустремленность и трудолюбие.
58153. Место неметаллических элементов в периодической системе. Особенности строения атомов. Физические и химические свойства элементов - неметаллов 41 KB
  Место неметаллических элементов в периодической системе. Физические и химические свойства элементов неметаллов. По электронному строению внешнего энергетического уровня атомов большинство неметаллических элементов являются рэлементами...
58154. Системный блок компьютера. Устройства ввода 747.5 KB
  Что относится к устройствам ввода Информация в компьютер может вводиться с помощью самых разнообразных уст ройств но не каждое из них называют устройством ввода.