GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Мягкие вычисления(45761)
Эволюционные вычисления(31872)
Сортировка и поиск: Рецептурный справочник(30738)
Алгоритмы архивации данных(25046)
Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет(19449)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Алгоритмы » Эволюционные вычисления

Эволюционные вычисления


Yuri Burger
jo_kruger@mail.ru

Страницы: [ 1 ] [ 2 ] [ 3 ] [ 4 ]

  • Что такое мягкие вычисления?
  • Что такое "эволюционные вычисления"
  • Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума
  • ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
    • Что такое генетический алгоритм?
    • Кто придумал генетический алгоритм?
    • Преимущества генетических алгоритмов
    • Недостатки генетических алгоритмов
    • Что такое простейший генетический алгоритм, схема, теорема Холланда?
    • Обобщенная схема генетического алгоритма
    • ОТБОР
      • Турнирный отбор
      • Стратегия элитаризма
      • Рулетка
      • Пропорциональный отбор
    • ОБРАЗОВАНИЕ ПАР
    • РЕКОМБИНАЦИЯ
      • Классический (одноточечный) кроссинговер
      • Двуточечный кроссинговер
      • Унифицированный (однородный) кроссинговер
    • МУТАЦИЯ
      • Одноточечная мутация
      • Плотность мутации
      • Инцест
    • ПОЗИЦИОНИРОВАНИЕ
    • Фитнес-функция
  • РАСПРЕДЕЛЕННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
  • ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
    • Что такое генетическое программирование?
    • Терминальный алфавит, функциональный базис и их свойства
  • КОДИРОВАНИЕ РЕШЕНИЙ
    • Деревья поколений
  • Разное
    • Почему кроссинговер не может вывести популяцию из локального оптимума?
    • Тестовые задачи
    • Словарь
    • Советуемая литература
    Что такое мягкие вычисления?

    Термин "мягкие вычисления" введен Лофти Заде в 1994 году. Это понятие объединяет такие области как: нечеткая логика, нейронные сети, вероятностные рассуждения, сети доверия и эволюционные алгоритмы; которые дополняют друг друга и используются в различных комбинациях или самостоятельно для создания гибридных интеллектуальных систем. Поэтому создание систем работающих с неопределенностью, надо понимать как составную часть "мягких" вычислений.
    По существу в 1970 году Л.Заде был создан новый метод вычислительной математики, который был поддержан аппаратными средствами (нечеткими процессорами) который в ряде проблемных областей стал более эффективным, чем классические методы. Первоначально эти области входили в проблематику искусственного интеллекта. Постепенно круг этих областей существенно расширился и сформировалось направление "вычислительного интеллекта". В это направление в настоящее время входят:

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

    Что такое "эволюционные вычисления"
    Yuri Burger

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

    Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума
    Yuri Burger

    Пусть задана функция q(x), определенная во всех значениях x принадлежащих X. В общем случае x может быть вектором значений многопараметрической функции q(x).
    Тогда, в общей задаче оптимизации требуется найти вектор x=(x1,x2, ...,xn) из допустимой области X, который обращает в минимум целевую функцию q(x). Если необходимо найти максимум функции, то в качестве целевой берут обратную функцию -q(x).

    Теорема Вейерштрасса. Непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает своего минимума (максимума) по крайней мере в одной из точек этого множества.

    В общем случае глобальный минимум в точке x' области определения X характеризуется:

                        q(x')<=q(x) для всех x принадлежащих X
    
    Знак '<=' предполагает возможность существования нескольких минимумов. При таком определении глобальный минимум называют слабым.
    Сильный глобальный минимум определяется:
              q(x')<q(x) для всех x принадлежащих X при x' не равном x
    
    Минимум в точке x=x' называют локальным (относительным), если найдется такая окрестность O(x') точки x', что для всех x принадлежащих O(x') имеет место q(x')<=q(x)

    ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

    Что такое генетический алгоритм?
    Yuri Burger

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

    Кто придумал генетический алгоритм?

    В 1966 г. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях. В 1975г. Д.Х.Холланд предложил схему генетического алгоритма. Эти работы легли в основу главных направлений разработки эволюционных алгоритмов.
    Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда.

    Преимущества генетических алгоритмов

    • Не требуют никакой дополнительной информации о поверхности ответа;
    • Разрывы, существующие на поверхности ответа незначительно влияют на эффективность оптимизации;
    • Устойчивы к попаданию в локальные оптимумы;
    • Хорошо работают при решении задач многоцелевой оптимизации;
    • Могут быть использованы для широкого класса задач;
    • Просты и прозрачны в реализации;
    • Могут быть использованы в задачах с изменяющейся средой.

    Недостатки генетических алгоритмов

    Не желательно и проблематично использовать ГА:

    • В случае когда необходимо найти точный глобальный оптимум;
    • Время исполнения функции оценки велико;
    • Необходимо найти все решения задачи, а не одно из них;
    • Конфигурация является не простой (кодирование решения).
    • Поверхность ответа имеет слабоизменяющийся рельеф.
    Alexander Pavlov [2:5030/399.11]
    Необходимость поиска всех решений не является помехой. Исаев (статьи на www.algo.4u.ru) пишет: "...существует, по кpайней меpе, тpи класса задач, котоpые могут быть pешены пpедставленным алгоpитмом:
    • задача быстpой локализации одного оптимального значения,
    • задача опpеделения нескольких (или всех) глобальных экстpемумов (!),
    • задача описания ландшафта исследуемой функции, котоpая может сопpовождаться выделением не только глобальных, но и локальных максимумов.
    ...
    Для pешения втоpой задачи, очевидно, вопpосу "исследования" пpостpанства поиска должно уделяться гоpаздо большее внимание. Оно достигается за счет дpугого сочетания паpаметpов и достаточно большой численности популяции, пpи этом ГА сможет выделить несколько (или даже все) глобальные экстpемумы
    ...
    Для выделения нескольких глобальных максимумов, лучше использовать такую комбинацию [паpаметpов]: аутбpидинг в сочетании с инбpидингом, в качестве естественного отбоpа достаточно использовать элитный отбоp или отбоp с вытеснением (последний более надежный). Максимальная эффективность поиска достигается в сочетании аутбpидинга и инбpидинга, пpичем аутбpидинг pекомендуется использовать в начале поиска, достигая максимально шиpокого "исследования", а завеpшать поиск лучше уточнением pешения в локальных гpуппах, используя инбpидинг."

 
16.01.2003
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.