45431

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

Доклад

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

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

Русский

2013-11-17

57.5 KB

38 чел.

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


 

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

232. Материаловедение. Технология конструкционных материалов 351 KB
  Типы кристаллических решеток у металлов. Основные структурные составляющие сплавов. Превращения на линиях диаграммы при нагревании и охлаждении. Диаграмма распада аустенита при непрерывном охлаждении. Основные виды термической обработки стали.
233. Исследование электромеханических реле 508 KB
  Исследование работы электромагнитного реле РТ-40. Исследование электронных реле тока и реле времени. Исследование измерительного блока электронного реле тока (напряжения). Исследование схемы генератора меандра на КР1006ВИ1.
234. Разработка цифрового вольтметра, на основе метода двойного интегрирования 139.64 KB
  Структурная схема цифрового вольтметра и расчет основных его параметров. Схемотехника основных узлов цифрового вольтметра. Последовательный ввод информации с входа D и её сдвиг. Использование четырехразрядного реверсивного счетчика.
235. Розрахунок головної балки мостового вантажопідйомного крану 398.33 KB
  Розрахунок конструкцій за допустимими напруженнями. Визначення висоти основного перерізу балки з умов міцності (мінімальної маси). Визначення еквівалентних напружень у небезпечному перерізі балки. Стійкість нижньої частини вертикального полотна.
236. Информационное обеспечение департамента управления министерства финансов Республики Хакасия 562.5 KB
  Структура организации (функциональные и информационные связи). План и схема развёртывания комплекса программ. Составление заявки на ремонт неисправного, а также приобретение нового и модернизацию устаревшего аппаратного оборудования серверов и рабочих станции, а также сетевого оборудования.
237. Теоретический расчет работы электродвигателя 193.34 KB
  Определение мощности и частоты вращения двигателя, общий коэффициент полезного действия. Фактическая частота вращения на валу рабочей машины, расчет зубчатых колёс редуктора. Конструктивные размеры шестерни и колеса.
238. Система электронно-цифровой подписи 648.47 KB
  Изучения руководства пользователя программы, регистрация открытых ключей и проверка подписей. Вывод названия организации и составление отчетов по запросу банк - клиент. Проверка правильности работы программы и наличия цифровой подписи.
239. Расчет показателей судна и его энергетический установки 368.5 KB
  Обоснование эксплуатационных режимов работы главных двигателей СЭУ. Выбор схемы обеспечения судна электроэнергией и теплом. Выбор режима работы главных двигателей судна. Обоснование и выбор схемы энергетического теплоснабжения.
240. Принципы расчета оплаты труда персонала предприятия 479.5 KB
  Основные принципы организации оплаты труда, состав фонда оплаты труда. Теоретические основы системы организации и оплаты труда. Направления по усовершенствованию системы оплаты труда. Совершенствования системы оплаты труда для повышения ее стимулирующий функции.