45431

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

Доклад

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

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

Русский

2013-11-17

57.5 KB

43 чел.

  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);  Некоторые разделы могут содержать подпункты. Так, например, экстремальные задачи включают в себя целый класс задач линейного и нелинейного программирования.


 

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

24955. Виды договоров в гражданском праве 32 KB
  В зависимости от основания классифицировать можно договоры как угодно. Поэтому делит все договоры на: договоры направленные на передачу имущества в собственность в аренду в пользование и т.; договоры направленные на выполнение работ; договоры направленные на оказание услуг; договоры направленные на создание коллективных обязанностей учредительные договоры; договоры направленные на использование результатов интеллектуальной деятельности. Учебник классифицирует гражданскоправовые договоры как соглашения сделки и договорные...
24956. Залог как способ обеспечения исполнения обязательств 80 KB
  Основной формой залога являлась фидуция архаичное право продажа закладываемой вещи с правом ее обратного выкупа. Однако этот вид залога являлся чрезвычайно обременительным для должника поскольку кредитор став собственником вещи мог ей распорядиться в результате чего должник лишался возможности выкупа вещи. В связи с этим Уложением Юстиниана такой вид залога был запрещен. Это вызвало к жизни другую форму залога пигнус ручной заклад.
24957. Банковская гарантия, удержание, задаток как способы обеспечения исполнения обязательств 80 KB
  Признаки способов обеспечения исполнения обязательств: o имущественный характер; обеспечивают интерес кредитора и направлены на исполнение обязательства; устанавливаются либо на основании закона либо по соглашению сторон; дополнительный акцессорный характер то есть они обеспечивают исполнение основного обязательства поэтому прекращение или недействительность основного обязательства влечет прекращение или недействительность его обеспечения за исключением банковской гарантии; они применяются вне зависимости от того причинены ли...
24958. Договор купли-продажи недвижимости 55.5 KB
  К отношениям по продаже недвижимого имущества часто применяются особые требования к договорам продажи недвижимости заключаемым на торгах в том числе на публичных правила ФЗ Об исполнительном производстве к ДПН в процессе приватизации нормы законодательства о приватизации; при этом положения ГК регулирующие порядок приобретения и прекращения права собственности применяются если законами о приватизации не предусмотрено иное. Переход права собственности на недвижимость от продавца к покупателю подлежит государственной регистрации...
24959. Жилищные правоотношения 62 KB
  Сущность жилищного вопроса заключается в недостатке жилища. Этой категорией охватываются отношения в сфере управления жилым фондом в том числе его государственный учет и контроль за его использованием и сохранностью; обеспечение граждан жилыми помещениями на условиях найма; обеспечение правильного использования жилищного фонда его эксплуатация и ремонт и т. Только на жилищные отношения распространяется действие норм жилищного законодательства а к отношениям лишь отдаленно связанным с удовлетворением жилищной проблемы эти нормы не...
24960. Гражданско-правовые проблемы приватизации жилищного фонда 81 KB
  Гражданскоправовые проблемы приватизации жилищного фонда Согласно Федеральному закону от 29 декабря 2004 г. N 1541I О приватизации жилищного фонда в Российской Федерации последние изменения от 29 декабря 2004 г. Имеется проблема приватизации коммунальных квартир и комнат в них. В Примерном положении о бесплатной приватизации жилищного фонда в Российской Федерации утвержденного решением коллегии Комитета РФ по муниципальному хозяйству от 18.
24961. Гражданско-правовое регулирование приватизации государственных и муниципальных предприятий 40.5 KB
  Гражданскоправовое регулирование приватизации государственных и муниципальных предприятий Определение: приватизация отчуждение переход недвижимого имущества из государственной или муниципальной собственности в частную собственность граждан или определенных юридических лиц в порядке установленном специальным законодательством а также переход в указанном порядке к названным лицам принадлежащих публичноправовым образованиям акций открытых акционерных обществ удостоверенных ими прав. Следует отличать от коммерциализации государственных...
24962. Договор хранения 72.5 KB
  Договор хранения Сложность и особенность хранения как обязательства по оказанию услуг заключается в двойственной природе данного договора. По договору хранения одна сторона хранитель обязуется хранить вещь переданную ей другой стороной поклажедателем возвратить эту вещь в сохранности: односторонний безвозмездный и реальный договор. В бытовой сфере где отношения сторон хранения продолжают носить личнодоверительный характер указанная элементарная конструкция может найти применение хотя и в этой сфере ее значение падает поскольку и на...
24963. Договор аренды 57 KB
  Договор аренды По договору аренды имущественного найма арендодатель обязуется предоставить арендатору имущество за плату во временное владение и пользование или во временное пользование. Договор аренды консенсуальный возмездный взаимный и двусторонний. В настоящее время объектами аренды могут быть земельные участки и участки лесного фонда. Единственным существенным условием договора аренды в силу требования закона является условие о предмете аренды.