Week 9 Lecture 2


Введение

  • Основные темы лекции:

    1. Прямое и косвенное представление.

    2. Эпистатический ген.

    3. Частично отображенный кроссовер.

    4. Примеры.

1. Прямое и косвенное представление

Прямое представление:

  • Генотип = фенотип.

  • Пример:

    • Настройки машины.

    • Создание конечного автомата или другого контроллера.

  • Подходит для задач, где структура генома напрямую отражает желаемый результат.

Косвенное представление:

  • Генотип используется для построения фенотипа.

  • Пример:

    • Эволюция программ для создания решений.

  • Перспективно для разработки сложных структур или систем.

2. Представление в задачах

Пример: Генотип и фенотип в построении подземелий

  • Генотип: дерево кортежей.

  • Фенотип: игровая доска с размещенными комнатами.

  • Переход от одного к другому требует шага трансляции.

Самоизбегающая прогулка

  • Задача: пройти все клетки на сетке N×NN×N, не повторяя посещения.

  • Примеры представлений:

    • Последовательность направлений (вверх, вниз, влево, вправо):

      • Простое представление, но большое пространство поиска (4N−14N−1).

    • Оптимизация: сохранение направления агента:

      • Используются только три символа: вперед (F), налево (L), направо (R).

      • Сокращение пространства поиска (3N−13N−1).

3. Эпистаз

  • В генетике: эпистатический ген влияет на выражение других генов.

  • В эволюционных алгоритмах:

    • Действия в начале строки сильно влияют на итоговую приспособленность.

    • Пример:

      • Изменение первого шага может привести к полному провалу.

      • Изменение последнего шага имеет минимальный эффект.

4. Генетические операции

Кроссовер с частичным отображением (PMX - Partially-Mapped Crossover)

  • Используется в задачах упорядочивания (например, задача коммивояжера).

  • Суть:

    1. Определяются две точки разделения.

    2. Сегменты между точками обмениваются.

    3. Сохраняется структура родительских строк.

  • Пример:

    • Родители:

      • 2 6 7 1 9 0 5 4 8 3

      • 7 5 6 3 0 9 8 1 2 4

    • Потомки:

      • 2 6 7 1 9 0 5 4 2 4

      • 7 5 6 3 0 9 8 1 8 3.

Реальное представление

  • Переход от дискретных значений к вещественным числам.

  • Особенности:

    • Кроссовер — как для строк.

    • Мутация — добавление случайного значения.

    • Быстрая сортировка для упрощения обработки.

5. Коэволюция

  • Приспособленность оценивается не по целевой функции, а по взаимодействию с другими членами популяции.

  • Пример: Итеративная дилемма заключенного.

    • Два игрока соревнуются, выбирая стратегию сотрудничества или предательства.

    • Представления:

      • Конечные автоматы.

      • Марковские цепи.

      • Таблицы действий.

6. Пример: "Sunburn" (симуляция космических кораблей)

Корабли:

  • Генотип: строка символов, описывающая корабль.

    • (S) — щиты.

    • (G) — пушки (эффективность снижается с увеличением расстояния).

    • (L) — лазеры (равная эффективность на любом расстоянии).

    • (M) — ракеты (более эффективны на дальних расстояниях).

    • (D) — двигатели.

Алгоритм симуляции:

  1. Битвы между кораблями.

  2. Победители участвуют в кроссовере.

  3. Эволюция через гладиаторские поединки.

Пример генотипа:

  • SGLMSDSMGSLD,16 → преобразуется в:

    • SSSS SSSS SSSS GLMDMGLD,16.

Важные аспекты:

  • Щиты группируются в начале.

  • Двигатели располагаются в конце для повышения выживаемости.

7. Итоги

  1. Прямое и косвенное представление:

    • Выбор влияет на размер пространства поиска и эффективность решений.

  2. Эпистаз:

    • Ранние действия имеют решающее значение.

  3. Частично отображенный кроссовер:

    • Сохраняет структуру и подходит для задач упорядочивания.

  4. Примеры:

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