Лекция 16-17 Исследование качества работы алгоритмов

План

1. Скользящий контроль качества. Исследования средних показателей алгоритма. Модель пространства описания предметной области. Модель информации, известной эксперту.

2. Организация систем для поддержки и наполнения базы знаний.Онтологические базы знаний. Гибридные нейронные сети. Многоуровневая схема обработки информации для интеллектуальной обработки данных.

Генетические алгоритмы и моделирование биологической эволюции.

Основные понятия, принципы и предпосылки генетических алгоритмов.

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

Рисунок 1 – Модель эволюции в природе

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

Генетические алгоритмы (ГА) являются адаптивными методами функциональной оптимизации, основанные на компьютерном имитационном моделировании биологической эволюции. Основные принципы ГА были сформулированы Голландом (1975), и хорошо описаны во многих работах и на ряде сайтов в Интернете.

В настоящее время существует ряд теорий биологической эволюции (Ж.-Б.Ламарка, П.Тейяра де Шардена, К.Э.Бэра, Л.С.Берга, А.А.Любищева, С.В.Мейена и др.), однако, ни одна из них не считается общепризнанной. Наиболее известной и популярной, конечно, является теория Чарльза Дарвина, которую он представил в работе " Происхождение Видов" в 1859 году.

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

Это накопление информации происходит на различных уровнях иерархии популяции, как системы, включающей:

- элементы системы: отдельные особи;

- взаимосвязи между элементами: отношения между особями в популяции, обеспечивающие передачу последующим поколениям максимального количества информации об их выживании и продолжении рода (путем скрещивания наиболее приспособленных особей и наследования рациональных приобретений);

- цель системы: сохранение и развитие популяции, реализуется через цели особей: индивидуальное выживание и продолжение рода.

Лекция 18 Интеллектуальные средства и реализация интеллектуальных систем. Отображение интеллектуальной системы управления (ИСЦ) на архитектуру многопроцессорной вычислительной сети.

План

1. Характеристики ИСЦ и требования к надежности ИСЦ. Многопроцессорные вычислительные сети (МВС).

2. Задача оптимального отображения структуры ИСУ на архитектуру МВС. Постановка задачи отображения.

Примеры применения генетических алгоритмов

В 1994 году Эндрю Кин из университета Саутгемптона использовал генетический алгоритм в дизайне космических кораблей. За основу была взята модель опоры космической станции, спроектированной в NASA из которой после смены 15 поколений, включавших 4.500 вариантов дизайна, получилась модель, превосходящая по тестам тот вариант, что разработали люди.

Аналогичный генетический алгоритм был использован NASA при разработке антенны для спутника.

Джон Коза из Стэнфорда разработал технологию генетического программирования, в которой результатом эволюции становятся не отдельные числовые параметры " особей", а целые имитационные программы, которые являются виртуальными аналогами реальных устройств. Эта технология позволила компании Genetic Programming повторить 15 человеческих изобретений, 6 из которых были запатентованы после 2000 года, то есть представляют собой самые передовые достижения, а один из контроллеров, " выведенных" в GР, даже превосходит аналогичную человеческую разработку.

Сейчас плоды электронной эволюции можно найти в самых разных сферах: от двигателя самолета Боинг 777 до новых антибиотиков.

Генетические алгоритмы представляют собой компьютерное моделирование эволюции. Материальное воплощение сконструированных таким образом систем до сих пор была невозможна без участия человека. Однако интенсивно ведутся работы, результатом которых является уменьшение зависимости машинной эволюции от человека. Эти работы ведутся по двум основным направлениям:

1. Естественный отбор, моделируемый ГА, переносится из виртуального мира в реальный, например, проводятся эксперименты по реальным битвам роботов на выживание.

2. Интеллектуальные системы, основанные на ГА, конструируют роботов, которые в принципе могут быть изготовлены на автоматизированных заводах без участия человека.

Пример воплощения ГА в реальной битве роботов на выживание: в 2002 году в британском центре Magna открылся павильон Live Robots, где боролись за выживание 12 роботов двух видов: " гелиофаги", способные добывать электроэнергию с использованием солнечных батарей; " хищники", которые могли получать электроэнергию только от гелиофагов. Выжившие роботы загружали свои " гены" в погибших и, таким образом, образовывали новые поколения. Те хищники, которые забирали всю энергию у гелиофагов, теряли источник питания и погибали, не передавая свою тактику потомкам, поступавшие же " более разумно" продолжили свой род. В результате возникла равновесная сбалансированная искусственная экосистема с двумя популяциями.

Пример конструирования роботов роботами: в Brandeis University была создана программа Golem, которая сама конструировала роботов. В программу была база деталей, а также механизм мутаций и функция пригодности для " отсеивания" неудачников - тех, кто не научился двигаться. После 600 поколений за несколько дней программа получила модели трех ползающих роботов. Показательно, что роботы оказались симметричными, хотя симметрия никак не была явно прописана в правилах эволюции и исходных данных. Это означает, что она появилась в ходе моделирования машинной эволюции как полезная черта, позволяющая двигаться прямолинейно.

⇐ Предыдущая 1 2 3 4 5 6 78