45431

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

Доклад

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

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

Русский

2013-11-17

57.5 KB

41 чел.

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


 

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

54483. WORLD MUSIC 53 KB
  Nowadays many people enjoy music as their hobby. Thanks to this fact you can make many new friends, you can exchange cd’s, records, listen to music together and visit different concerts. For my person, music plays more important role in life than good pastime. It is something, which helps me to be in a good mood, understand different things and remove from tension. Music brings me pleasure and keen delight and fills my life with great expectations of joy and happiness.
54484. Музика охоплює весь світ 45 KB
  Мета: активізувати та розширити знання учнів про економіку країн, які є Батьківщиною видатних композиторів світу, узагальнити знання учнів про композиторів – класиків кінця 17 – початку 20 століття, розвивати навички самостійної роботи з інформаційним матеріалом, навички зв’язного мовлення, вчити співвідносити знання з різних галузей науки та мистецтва, виховувати культуру поведінки, формувати потребу сприймати та виконувати високохудожні музичні твори, виховувати інтерес до знань, залучати учнів до проведення нестандартних типів уроку.
54485. Героические образы в симфонической музыке 280 KB
  Цель. На примере творчества Д. Шостаковича и А. Пашкевича нацелить учащихся на понимание жизненного содержания музыки, которая воплощает образы реальных исторических событий – Великой Отечественной войны. Учить анализировать образное содержание и звучание музыки, находить общее в содержании разножанровых произведений.
54486. Музыка Чайковского как символ красоты, правды, искренности 81.5 KB
  Чайковского совершенствовать умения сравнивать музыкальные произведения формировать эмоциональнооценочное отношение к музыкальному произведению в процессе его интерпретации развивать способности творческого комбинирования воспитывать ценностные ориентации в сфере музыки. Оборудование: портрет Чайковского фонограммы карточки для составления модели музыкального произведения фильм Доживем до понедельника иллюстрации с сюжетом про вальс. Определение темы и задач урока 3 минуты Кто может назвать композитора чья музыка звучала...
54487. Предмет и метод экономической теории 17.71 KB
  В условиях рыночной экономики субъект, выполняющий экономические функции, называется экономическим субъектом (государство, различные фонды, объединения, ассоциации, фирмы и предприятия, домохозяйства, отдельный человек). В процессе деятельности экономических субъектов возникает экономическое явление.
54488. Музичні захоплення 157.5 KB
  Many people like music but “lovers of music” love it and try to fill every minute of their life with music. As a rule they don’t have much free time so they are very categorical in their choice of favourite music. A real “lover of music” chooses the best. And what about you? Do you belong to the category of “Music lovers”.
54490. Система уроков по теме «Музыка» 275 KB
  Ученики отвечают на вопросы. Ученики задают вопросы ученику возле доски ученик отвечает. Ученики слушают отвечают на вопросы. Ученики работают у доски и с места.
54491. The magic world of music 34.5 KB
  It is difficult to imagine our life without music .It helps us to live and relax. We are going to speak about music because it plays a great role in our lives. Music is everywhere It is in the streets, in the shops, in the parks, on the television sets.