45431

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

Доклад

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

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

Русский

2013-11-17

57.5 KB

34 чел.

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


 

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

22305. Данные и основные операторы 725.5 KB
  Хороший выбор структур данных позволяет разрабатывать на языке Паскаль простые и эффективные алгоритмы. Достоинства Паскаля: он ориентирован на структурное программирование имеет развитые средства контроля и достаточно прост в изучении; язык имеет хороший состав типов и структур данных; трансляторы с Паскаля есть во всех распространенных ПК; конкретные реализации языка дают возможность использовать все аппаратные средства ПК; на основе языка Паскаль разработана Delphi одна из современных систем визуального программирования....
22306. Организация лечебно-эвакуационного обеспечения населения при ЧС 269.5 KB
  Опыт ликвидации медико-санитарных последствий ЧС позволяет выделить общие факторы обстановки, которые, как правило, имеют место при всех ЧС, сопровождающихся значительными потерями населения, и влияют на организацию лечебно-эвакуационного обеспечения. К ним можно отнести следующие...
22307. МЕДИЦИНСКОЕ ОБЕСПЕЧЕНИЕ НАСЕЛЕНИЯ ПРИ ПРОВЕДЕНИИ МЕРОПРИЯТИЙ ГРЖДАНСКОЙ ОБОРОНЫ 196 KB
  Процесс оповещения населения обязательно сопровождается организацией оповещения органов управления и ответственных должностных лиц, принимающих решения о проведении конкретных мероприятий по защите населения, аварийно-спасательных и других неотложных работ в районах чрезвычайных ситуаций.
22308. Медико-санитарное обеспечение при ликвидации последствий чрезвычайных ситуаций техногенного (антропогенного) характера 233.5 KB
  Изучить классификацию АОХВ, характеристику очагов химического и радиационного заражения при авариях на радиационно опасных и химически опасных объектах. Изучить виды дорожно-транспортных аварий и катастроф, а также чрезвычайных ситуаций на пожаро - и взрывоопасных объектах
22309. ОРГАНИЗАЦИЯ ЛЕЧЕБНО-ЭВАКУАЦИОННОГО ОБЕСПЕЧЕНИЯ НАСЕЛЕНИЯ ПРИ ЛИКВИДАЦИИ ПОСЛЕДСТВИЙ НАПАДЕНИЯ ПРОТИВНИКА 160.5 KB
  Изучить организацию лечебно-эвакуационного обеспечения населения в очагах массовых санитарных потерь при применении противником ОМП. Рассмотреть организацию оказания медицинской помощи пострадавших, медицинскую сортировку. Изучить принципиальную схему развертывания этапа медицинской эвакуации, организацию медицинской эвакуации пострадавших
22310. Медико-санитарное обеспечение при ликвидации последствий чрезвычайных ситуаций природного характера (стихийных бедствий) 271.5 KB
  Изучить условия, определяющие систему лечебно-эвакуационного обеспечения населения при ликвидации последствий чрезвычайной ситуации природного характера, особенности формирования очагов массовых санитарных потерь при землетрясениях, наводнениях, лесных и торфяных пожарах
22311. РАБОТА НЕШТАТНЫХ АВАРИЙНО-СПАСАТЕЛЬНЫХ ФОРМИРОВАНИЙ ГРАЖДАНСКОЙ ОБОРОНЫ ЗДРАВООХРАНЕНИЯ ПРИ ПРОВЕДЕНИИ СПАСАТЕЛЬНЫХ РАБОТ 235.5 KB
  Первая врачебная помощь — комплекс общеврачебных мероприятий, оказываемых в целях устранения или ослабления последствий ранений (заболеваний), угрожающих жизни пораженным, раненых и больных, предупреждения развития опасных для жизни осложнений или уменьшения их тяжести, а также подготовки нуждающихся к дальнейшей эвакуации.
22312. Управління користувачами в невеликій мережі 28 KB
  Створюючи групи і додаючи в них користувачів ви визначаєте громадянство які мають права доступу до комп'ютерів в мережі. Крім того ви дістаєте можливість розділити користувачів на групи що володіють різними правами доступу. Двічі клацніть на значку Користувачі і паролі щоб відкрити діалогове вікно. Дозвольте користувачам обов'язково указувати свої ім'я користувача і пароль для чого встановите відповідний прапорець єдиний на вкладці Користувачі діалогового вікна Користувачі і паролі Перейдіть на вкладку Додатково.
22313. Використовування Windows 2000 Professional як Web-сервер 36 KB
  World Wide Web це компонент Internet що відповідає за надання інформації розваг служб а також проведення всіляких електронних транзакцій через Internet. І Internet і World Wide Web доступні цілодобово сім днів в тиждень. За всіма прекрасними декораціями World Wide Web ховається велика кількість серверів що містять Webсторінки і додаткові файли; такі сервери називаються Webвузлами.