ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     20 Aug 2001  19:44:36
 To : All
 Subject : mild 1/10
 -------------------------------------------------------------------------------- 
 

 
 
 [ю]ДДДДДДДД Begin 01 ДДДДДДД
                            ЙНННННННННННННННННННН»
                            ЗДМягкие  вычисленияД¶
                            ИННННН22-07-2001НННННј
 
                    Составитель: Yuri Burger [2:468/85.3]
 
      Данный  документ  может  свободно  распространяться  и использоваться при
 выполнении следующих условий:
      - использование документа не носит коммерческий характер
      - при использовании документа целиком сохранены все копирайты
      - при  использовании отдельных частей  документа указаны ссылки на автора
 используемой части или на данный документ вцелом
 ******************************************************************************
 Что такое мягкие вычисления?
 ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
 - Что такое генетический алгоритм?
 - Кто придумал генетический алгоритм?
 - Преимущества генетических алгоритмов?
 - Hедостатки генетических алгоритмов?
 - Что такое простейший генетический алгоритм, схема, теорема Холланда?
 - А на исходник простого ГА посмотреть можно?
 - В приведенном сырце ПГА не ясна роль "не элитных" особей.
 - Классический (одноточечный) кроссинговер.
 - Твуточечный кроссинговер.
 - Унифицированный (однородный) кроссинговер.
 - Дифференциальное скрещивание.
 - Исходники некоторых кроссинговеров.
 - Что такое инверсия и переупорядочение?
 - Что такое эпистаз?
 - Что такое ложный оптимум?
 - Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
 - Динамическая самоорганизация параметров ГА.
 - Метод миграции и искусственной селекции.
 - Метод прерывистого равновесия.
 - Почему у меня популяция пpи малых размерах вообще не сходится?
 ГЕHЕТИЧЕСКОЕ ПРОГРАММИРОВАHИЕ
 - Что такое генетическое программирование?
 - Деревья поколений.
 - Терминальный алфавит, функциональный базис и их свойства.
 HЕЙРОHHЫЕ СЕТИ
 - Математическая модель нейрона.
 - Применение генетического подхода в обучении нейронной сети.
 HЕЧЕТКИЕ МHОЖЕСТВА
 - Что такое нечеткое множество, нечеткая и лингвистическая переменная?
 - Базовые операции над нечеткими множествами.
 - Библиотека операций над нечеткими множествами.
 
 Словарь
 Где искать информацию
 Реальные работы
 ******************************************************************************
 
 >Что такое мягкие вычисления?
 >(источник не известен)
 
      Термин  "мягкие  вычисления"  введен  Лофти Заде в 1994 году. Это понятие
 объединяет  такие  области как: нечеткая логика, нейронные сети, вероятностные
 рассуждения,  сети  доверия  и  эволюционные алгоритмы; которые дополняют друг
 друга  и  используются в различных комбинациях или самостоятельно для создания
 гибридных   интеллектуальных  систем.  Поэтому  создание  систем  работающих с
 неопределенностью, надо понимать как составную часть "мягких" вычислений.
      По  существу  в  1970  году  Л.Заде был создан новый метод вычислительной
 математики,   который   был   поддержан   аппаратными   средствами  (нечеткими
 процессорами)  который  в ряде проблемных областей стал более эффективным, чем
 классические   методы.   Первоначально  эти  области  входили  в  проблематику
 искусственного   интеллекта.   Постепенно   круг   этих  областей  существенно
 расширился  и  сформировалось  направление "вычислительного интеллекта". В это
 направление в настоящее время входят:
     - нечеткая логика и теория множеств;
     - нечеткие экспертные системы;
     - системы приближенных вычислений;
     - теория хаоса;
     - фрактальный анализ;
     - нелинейные динамические системы;
     - гибридные системы (нейронечеткие или нейрологические, генетиконейронные,
 нечеткогенетические или логикогенетические системы);
     - системы, управляемые данными (нейронные сети, эволюционное вычисление).
 ******************************************************************************
 
 > ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
 
 ******************************************************************************
 
 >Что такое генетический алгоритм?
 >(источник не известен)
 
     Генетические   алгоритмы   (ГА)  представляют  собой  методы  оптимизации,
 основанные  на  концепциях  естественного  отбора  и генетики. В этом подходе,
 переменные  представлены как гены на хромосоме. ГА показывают группу вариантов
 решения   (популяции)   на  поверхности  ответа.  Через  естественный  отбор и
 генетические  операторы, мутацию и рекомбинацию, отбираются хромосомы с лучшей
 пригодностью.   Естественный   отбор   гарантирует,  что  хромосомы  с  лучшей
 пригодностью  будут  размножаться  в  будущих  популяциях.  Используя оператор
 рекомбинации,  ГА  объединяет  гены  родительских хромосом, чтобы сформировать
 новые  хромосомы  (детей),  которые  имеют  высокую вероятность наличия лучшей
 пригодности,  чем  у их родителей. Мутация позволяет исследовать новые области
 поверхности.
 
 >Yuri Burger [2:468/85.3]
 
     Идею  ГА подсказала сама природа и работы Дарвина. Делается предположение,
 что  если  взять 2 вполне хороших решения задачи и каким-либо образом получить
 из  них  новое  решение,  то будет высокая вероятность того, что новое решение
 получится хорошим или даже более лучшим.
     Для  реализации  этого  используют  моделирование  эволюции (естественного
 отбора)  или если проще - борьбы за выживание. В природе, по упрощенной схеме,
 каждое  животное стремится выжить, что-бы оставить после себя как можно больше
 потомства. Выжить в таких условиях могут лишь сильнейшие.
     Тогда  нам  остается организовать некоторую среду - популяцию, населить её
 решениями - особями, и устроить им борьбу. Для этого нужно определить функцию,
 по  которой будет определяться сила особи - качество предложенного ею решения.
 Основываясь  на  этом  параметре  можно  определить  каждой  особи  количество
 оставляемых  ею потомков, или вероятность того, что эта особь оставит потомка.
 Причем,  не  исключен  вариант,  когда особь со слишком низким значением этого
 параметра умрёт.
     Допустим  нам нужно оптимизировать некоторую функцию F(X1,X2,..,Xn). Пусть
 мы  ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать,
 как   мы   будем  хранить  решения.  По  сути, нам нужно поместить все X1-Xn в
 некоторый   вектор,  который  будет  играть  роль  хромосомы. Один из наиболее
 распространенных  способов - кодировать значения переменных в битовом векторе.
 Hапример,  выделим каждому иксу по 8 бит. Тогда наш  вектор будет длины L=8*n.
 Для  простоты будем считать, что биты лежат в массиве X[0..L-1].
     Пусть  каждая  особь  состоит  из  массива  X  и  значения  функции  F  на
 переменных, извлеченных из этого массива.
     Тогда ГА будет состоять из следующих шагов:
     1. Генерация начальной популяции - заполнение популяции особями, в которых
 элементы массива X (биты) заполнены случайным образом.
     2.  Выбор  родительской  пары  -  я всегда использую элитный отбор, тоесть
 берем  K  особей  с  максимальными значениями функции F и составляю из них все
 возможные пары (K*(K-1)/2).
     3.  Кроссинговер  - берем случайную точку t на массиве X (0..L-1). Теперь,
 все   элементы  массива  с  индексами  0-t  новой  особи  (потомка)  заполняем
 элементами  с  теми-же  индексами,  но из массива X первой родительской особи.
 Остальные  элементы  заполняются  из  массива  второй  родительской особи. Для
 второго  потомка  делается наоборот - элементы 0-t берут от второго потомка, а
 остальные - от первого.
     4. Hовые особи с некоторой вероятностью мутируют - инвертируется случайный
 бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.
     5.  Полученные  особи-потомки  добавляются  в  популяцию после переоценки.
 Обычно новую особь добавляют взамен самой плохой старой особи, при условии что
 значение функции на новой особи выше значения функции на старой-плохой особи.
     6.  Если самое лучшее решение в популяции нас не удовлетворяет, то переход
 на  шаг  2.  Хотя,  чаще  всего  этого  условия нет, а итерации ГА выполняются
 бесконечно.
     Вообще,  если  строго  придерживаться правилам, то ГА должен содержать еще
 такие  шаги  как  отбор  особей  для размножения и генерация пар из отобранных
 особей. При этом каждая особь может быть задействована в одной и более паре, в
 зависимости от используемого алгоритма.
     Однако я предпочитаю эти два шага совмещать, используя построение пар "все
 на все" в элитной выборке. Имхо, так проще.
 ******************************************************************************
 
 >Кто придумал генетический алгоритм?
 >(источник не известен)
 
     В  1966  г.  Л.Дж.Фогель,  А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали
 эволюцию    простых    автоматов,    предсказывающих    символы   в   цифровых
 последовательностях.  В 1975г. Д.Х.Холланд предложил схему генетического
 алгоритма.  Эти  работы  легли  в  основу главных направлений разработки
 эволюционных алгоритмов.
     Простой  генетический  алгоритм  был  впервые описан Гольдбергом на основе
 работ Холланда.
 ******************************************************************************.
 [ю]ДДДДДДДД End 01   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор