ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     19 Feb 2002  21:23:24
 To : All
 Subject : MildAlg FAQ: 07/10
 -------------------------------------------------------------------------------- 
 

 
 
 [ю]ДДДДДДДД Begin 07 ДДДДДДД
 
 >Почему у меня популяция пpи малых размерах вообще не сходится?
 >Yuri Burger [2:468/85.3]
 
      В  популяциях  с малым размером гены распространяются слишком быстро. Все
 особи становятся похожими (популяция сошлась) еще до того, как найдено решение
 задачи.  Получается  так,  что новый генотип с лучшей оценкой быстро вытесняет
 менее  хорошие  комбинации  ген,  исключая таким образом возможность получения
 более хорошего решения на их базе.
      Вторая  проблема  заключается  в  том,  что потомки, получаемые в большей
 популяции, скорее всего будут разнообразнее, чем потомки из меньшей популяции.
 С   одной   стороны,   при   малых   популяциях   внимание   алгоритма   будет
 сконцентрировано  на  некоторых  направлениях,  тоесть,  эти направления будут
 изучены  быстрей.  Hо  если  направление  изначально  было  ошибочным  (ложный
 оптимум) то алгоритм имеет все шансы застрять.
      Выходом  может  быть  увеличение  популяции, при условии что время работы
 алгоритма не критично.
      Также,  может  помоч  самоадаптация  алгоритма  при  выборе операторов (в
 тупиковых  ситуациях  увеличить  вероятность  применения случайного генератора
 особей).
      Еще  можно  попытаться  складировать  отдельно особи, генотип которых был
 утерян   популяцией,   и   временами  добавлять  эти  особи  (случай  удачного
 кровосмешения в племенных формациях).
 ******************************************************************************
 
 >Разное.
 >vitalie vrabie [2:469/303]
 
     ГА,  однородный  побитовый recombination, elitistic selection, все вектора
 одинакового размера.
     Ввёл  такое  понятие:  "однородность"  (степень  однородности)  популяции.
 Определяется  отношением  количества  одинаковых  битов  к  общему  их числу в
 векторе.
     Поясню на примере. Скажем, вектор из 10 бит. При следующей популяции:
 
                                 0101011100
                                 1100010100
                                 0101011110
                                  ^^ ^^ ^ ^
     Имеем  "однородность" равную 6/10 (шесть из десяти битов у всех одинаковые
 - в помеченных позициях).
     "Однородность" вычисляю перед каждой итерацией и использую как вероятность
 мутации.  Тоесть,  чем  однороднее  (скуднее)  генофонд,  тем выше вероятность
 мутаций.
 ******************************************************************************
 
 >ГА не рекомендуется, если нужно найти точный глобальный экстремум.
 >Почему?
 >Yuri Burger [2:468/85.3]
 
     Это  не  совсем  так...  Тоесть, это не значит что ГА не сможет найти его,
 совсем  нет...  Просто ГА не может определить когда он нашел точное глобальное
 решение..   Часто   используют   эффект  сходимостит  популяции  (когда  особи
 становятся одинаковыми), это позволяет организовать остановку алгоритма, но не
 гарантирует глобальность решения.
 ******************************************************************************
 
 > ГЕHЕТИЧЕСКОЕ ПРОГРАММИРОВАHИЕ
 
 ******************************************************************************
 
 >Что такое генетическое программирование?
 >Yuri Burger [2:468/85.3]
 
      Уж  не  знаю  почему  ГА  и  ГП  разделяют  на разные области, но я к ним
 отношусь как к одному и тому же.
      Единственное отличие ГП от ГА состоит в том, что каждая особь в популяции
 теперь  кодирует  не  числовые  характеристики,  которые  обеспечивают  задаче
 оптимальность,  а некоторую "программу", которая решает поставленную проблему.
      Под  словом "программа" здесь не стоит понимать реальную программу на Си,
 ассемблере и т.д. Чаще всего, такая программа - это всего навсего конфигурация
 дерева функции, нейронной сети или автомата.
      Алгоритм  работает  по  всем  законам  ГА,  лишь  при  оценке новой особи
 происходит  "исполнение"  программы, а затем оценка её деятельности. Hапример,
 в  задаче  автоматического  определения  функции  хромосома кодирует некоторую
 сложныю,  часто  многопараметрическую  функцию.  При  оценке происходит расчет
 закодированной  функции  на  тестовой  выборке  входных  значений, после чего,
 результаты  расчетов  сравниваются с тестовыми (экспериментальными) значениями
 искомой   функции   на   представленной  выборке, происходит расчет отклонения
 текущей  функции  от  искомой, которое используется как оценка особи. Уменьшая
 отклонение,  алгоритм  находит  неизвестную  функцию,  представленную тестовой
 выборкой.
      Впринципе,  возможно  создание  и реальной программы на некотором простом
 языке  (вроде  ассемблера).  Hо  тогда  возникает  проблема  исполнения  такой
 программы (чтоб не подвисла) и оценки результата.
      Пока что я видел такие направления в представлении программ:
 
      Деревья  поколений  -  кодируют  сложную  функцию,  представляя её в виде
 дерева  расчета (как при разборе выражений из теории трансляции). Используются
 при решении задачи автоматического определения функций.
 
      Hейронные   сети   -   множество   связанных  однотипных  элементов.  Для
 автоматического   определения   функций   не   подходят,  но  имеют  различные
 специфические применения.
 
      УHС  -  унифицированные  нейронные  сети  (модель  и  принципы применения
 предложены  мной  в  дипломной работе). Позволяют представлять любую расчетную
 многопараметрическую  сложную  функцию  в  компактном виде, присущем нейронным
 сетям.  Это  позволяет  применять  их  в  задачах  автоматического определения
 функций.  Также,  обладают  всеми  качествами  нейронных  сетей,  однако имеют
 слишком сложную топологию. Обучаются по ГА/ГП или К-Срезу.
 
      Автоматы  -  задают  последовательность переходов состояний. Используются
 как способ представления простых алгоритмов для "роботов". В сочетании с ГА/ГП
 использовались в игре на предсказание последовательности чисел.
 ******************************************************************************
 
 >Деревья поколений.
 >Yuri Burger [2:468/85.3]
 
      В  генетическом  программировании  особи  из популяции представляют собой
 программы.  Удобно  представлять  эти  программы  в виде деревьев, где функции
 представлены  внутренними  узлами,  к  которым  в  качестве входных параметров
 присоединены  поддеревья.  Листьями  такого  дерева  будут  константы, входные
 параметры задачи или директивные команды программы.
 
      Пример простой программы-дерева:
 
                                       =
                                       |
                                       +
                                      / \
                                     *   7
                                    / \
                                   x   3
 
      Такое  представление программ наглядно и легко реализуемо. Однако, работа
 с деревьями не всегда удобна при выполнении таких операторов, как кроссинговер
 и  мутация. Посути, необходимо реализовать совершенно новые операторы.
      Кроссинговер  будет  заключаться  в подмене одного из поддеревьев первого
 родителя на какое-либо поддерево второго родителя.
      Мутация  будет  выполнять  случайное  изменение  одного  из  узлов дерева
 (например смена функции или константы).
      Таким  образом, использование деревьев влечет за собой несколько проблем:
 необходимость  создания новых операторов мутации и кроссинговера; динамическая
 длина хромосомы, кодирующей дерево.
 ******************************************************************************.
 [ю]ДДДДДДДД End 07   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

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