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

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

• .
• .
• .
• (Правильный ответ) .

Чему соответствует найденное решение в вероятностном ГА?

• Точка в пространстве решений.
• Линия в пространстве решений.
• Вершина в гиперкубе пространства .
• (Правильный ответ) Подкуб в гиперкубе пространства .

Какой вектор представляет приведенную популяцию?

• (0,55;0,5;0,75;0,45).
• (Правильный ответ) (0,75;0,5;0,75;0,25).
• (0,75;0,50;0,25;0,75).
• (0,50;0,75;0,25;0,25).
• (0,10;0,75;0,45;0,20).

Что является особью в XCS системах?

• Вектор значений поощрений.
• (Правильный ответ) Популяция классификаторов.
• Отдельный классификатор.
• Подмножество классификаторов.
• Отдельное правило.

Что является базовым элементом эволюции в алгоритме SELFISH?

• Популяция.
• Мутация.
• (Правильный ответ) Ген.
• Особь.

Что определяет в приведенной формуле коэффициент ?

• Диапазон изменения случайного коэффициента .
• Диапазон изменения случайного коэффициента .
• Влияние социальной составляющей.
• (Правильный ответ) Влияние когнитивной составляющей.

Какие генетические операторы применяются в классическом ЭП?

• Кроссинговер.
• (Правильный ответ) Отбор особей.
• Рекомбинация.
• (Правильный ответ) Мутация.

Чему соответствует эволюция популяции в вероятностных ГА?

• (Правильный ответ) Траектория в гиперкубе пространстве .
• Точка в пространстве .
• Линия в пространстве решений.
• Точка в пространстве решений.

Приведенный рисунок отражает фронт Парето для какой задачи?

• Минимизация относительно первого критерия
• Максимизация относительно первого критерия.
• (Правильный ответ) Минимизация относительно 2-х критериев.
• Минимизация относительно второго критерия.
• Максимизация относительно 2-х критериев.
• Максимизация относительно второго критерия.

Какой из приведеннях вариантов выполнения усекающей мутации является правильным?

• (Правильный ответ)

Что представляет потенциальное решение задачи в муравьиных алгоритмах (МА)?

• (Правильный ответ) Путь на графе.
• Древовидная структура.
• Матрица вещественных чисел.
• Вектор вещественных чисел.
• Двоичная строка.

Какие особи удаляются из популяции в методе ранжирования по Парето.

• Доминируемые.
• (Правильный ответ) Недоминируемые.
• Случайные.
• С минимальным рангом.

Сколько подпопуляций используется в кооперативной коэволюции.

• (Правильный ответ) 2.
• 4.
• 8.
• 1.

Выполните простой (одноточечный) оператор кроссинговера над хромосомами А и В, если точка кроссинговера расположена сразу за -м геном хромосом при нумерации генов слева направо. .

• Особи-потомки есть 1000101 и 0110101.
• Особи-потомки есть 1010100 и 0110101.
• (Правильный ответ) Особи-потомки есть 1010100 и 0100101.
• Особи-потомки есть 1010101 и 0100100.

Пусть для тура при решении задачи коммивояжера выбрано представление в виде матрицы предшествования. Для тура требуется построить матрицу предшествования.

• (Правильный ответ)

123456710000100210111103100111041000110500000006100010071011110

123456710000100210111103100111041000110500000006101010071001110

123456710000100210111113100111041000100500000006100010071011110

123456710001000210111103100111041000110500000006101010071001110

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

• (Правильный ответ)

Выберите правильный вариант описания для -ЭС .

• родителей производят 1 потомок.
• Отбор1-й лучшей особи производится среди объединенного множества ( особей) родителей и потомков.
• (Правильный ответ) Отбор лучших особей производится среди потомков.
• (Правильный ответ) родителей производят потомков .

Что представляет популяцию в вероятностных генетических алгоритмах?

• Классификаторы.
• Вектор целых чисел.
• (Правильный ответ) Вектор вероятностей.
• Матрица.
• Двоичная строка

Чему соответствует особь в Мичиганском подходе?

• Граф.
• (Правильный ответ) Продукция
• Двоичная строка.
• Множество продукций.
• Массив целых чисел.

Сколько значений может принимать ген в алгоритме SELFISH?

• (Правильный ответ) Различное.
• 2.
• 4.
• 3.

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

, случайным образом получено 4 тура: (4,5,7,6), (11,8,9,1), (10,12,2,3).

• (Правильный ответ) В родительский пул вошли особи
• В родительский пул вошли особи
• В родительский пул вошли особи
• В родительский пул вошли особи

Что общего между Р и ГА?

• (Правильный ответ) Репродукция популяции.
• (Правильный ответ) Оценка фитнесс-функции особей.
• Генетические операторы.
• (Правильный ответ) Случайная генерация начальной популяции.
• (Правильный ответ) Случайный поиск.

Поясните содержательно существо метода отбора родителей на основе усечения.

• Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: .Далее формируются пары родителей .
• (Правильный ответ) Вначале отбираемые особи упорядочиваются согласно их значениям фитнесс-функции. Далее из них выбирается «лучшая» часть и, наконец, среди них случайным образом выбираются пары родителей. При этом используется параметр – порог отсечения , показывающий долю (часть популяции), которая отбирается в качестве родителей. Обычно .
• Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: . Далее из них случайным образом формируются пары родителей.
• Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: . Далее формируются пары родителей , где i=1,2,\dots,k/2.

В чем состоит существо селективного выбора?

• (Правильный ответ) Этот метод предполагает участие в выборе особей лишь с «хорошими» (выше среднего по популяции) значениями фитнесс-функции.
• Этот метод предполагает случайный выбор особей.
• Панмиксия и селективный выбор представляют собой эквивалентные методы выбора.

Для особей = 110101100101 и =101010110010 построить два потомка П1 и П2 с использованием многоточечного оператора кроссинговера.

Применить четырехточечный ОК, точки скрещивания 1, 3,6 и 10.

• (Правильный ответ) П1=101010110001, П2= 110101100110.
• П1=101001010110, П2= 101101100100.
• П1=110110101101, П2= 101001010110.
• П1=110010000101, П2= 101101010010.

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

• (Правильный ответ) .
• .
• .
• .

Вычислить вероятности отбора первых пяти особей при линейном ранжировании родителей (см. раздел 3.2.2 пособия) с точностью до четырех знаков. Исходные данные: мощность популяции равна 100, выбранный случайным образом параметр отбора .

• (Правильный ответ)

В чем отличие эволюции по Ламарку от эволюции по Дарвину?

• Какие-либо принципиальные отличия процессов эволюции по Ламарку и Дарвину отсутствуют.
• (Правильный ответ) По теории эволюции Ламарка после соответствующего преобразования особи с учетом влияния окружающей среды она помещается назад в текущую популяцию и имеет шанс на этапе отбора и кроссинговера передать информацию потомкам. По Дарвину окружающая среда не влияет на наследуемые признаки.
• Формирование следующего поколения по Дарвину осуществляется по принципу – выживает сильнейший. Причем отбор особей осуществляется только по значениям фитнесс-функций. По Ламарку отбор подразумевает учет еще одного параметра – коэффициент влияния окружающей среды.
• (Правильный ответ) По Ламарку в процессе эволюции окружающая среда оказывает прямое влияние на наследуемые признаки. Причем соответствующие изменения далее способны передаваться по наследству, что не предусматривает теория эволюции по Дарвину.

Какой двухуровневый гибридный алгоритм представлен на рисунке?

• Клеточный-«Рабочий хозяин».
• «Рабочий -хозяин»- «Клеточный».
• (Правильный ответ) «Модель островов»-модель островов.
• «Рабочий-хозяин»-«модель островов» (верхний уровень-нижний уровень).
• «Рабочий хозяин»- «Модель островов».

Что представляет потенциальное решение в классическом эволюционном программировании (ЭП)?

• Матрица из вещественных чисел.
• Граф.
• Двоичная строка.
• Дерево.
• (Правильный ответ) Автомат.
• Вектор вещественных чисел.

Какая мощность виртуальной популяции в компактном ГА?

• 1 особь.
• 4 особи.
• (Правильный ответ) 2 особи.
• 8 особей

Требуется найти оптимальное решение задачи коммивояжера любым из описанных в разделе 2 пособия методом, реализовав этот метод в виде программы на известном вам языке программирования. Исходные данные задачи представлены в виде квадратной матрицы, элементы которой интерпретируются как время переезда из города в город . 123451*42—52 *—193 *344 *115 *

• (Правильный ответ) Минимальный по времени маршрут коммивояжера есть (1-5-3-4-2-1)
• (Правильный ответ) Минимальный по времени маршрут коммивояжера есть (1-2-4-3-5-1)
• Минимальный по времени маршрут коммивояжера есть (1-2-5-4-3-1)
• Минимальный по времени маршрут коммивояжера есть (1-3-4-5-2-1)

Выполнить оператор мутации над вещественным числом V=101,75 с заданным шагом мутации .

• 101,7510
• 101,7650
• (Правильный ответ) 101,7515
• 101,7610

Какие характерные точки используются в ГА с адаптивными весами?

• (Правильный ответ) Максимальная экстремальная точка.
• (Правильный ответ) Минимальная экстремальная точка.
• Доминируемая экстремальная точка.
• Точка со среднеарифметическими значениями координат.

Как применяется «правило успеха»?

• (Правильный ответ) Увеличение отклонения , если .
• (Правильный ответ) Уменьшение отклонения , если .
• В каждом поколении.
• (Правильный ответ) После каждых поколений.

Как изменяется шаг мутации в современном ЭП?

• Размер шага изменяется случайно согласно распределению Рэлея.
• (Правильный ответ) Динамическое ЭП, где отклонение размера шага изменяется с течением времени в соответствии с некоторой детерминированной функцией.
• (Правильный ответ) Неадаптивное ЭП, где отклонения размера шага остаются постоянными.
• (Правильный ответ) Самоадаптивное ЭП, в котором отклонение размера шага изменяется динамически.

Какая популяция итеративно генерируется в алгоритме пошагового обучения?

• (Правильный ответ) Виртуальная популяция.
• Конечная популяция.
• Начальная популяция.
• Текущая популяция.

Какой метод отбора особей применяется в компактном ГА?

• (Правильный ответ) Турнирный.
• Локальный.
• Ранговый.
• Рулетка.

Выберите правильный вариант описания для -ЭС .

• Отбор1-й лучшей особи производится среди объединенного множества ( особей) родителей и потомков.
• (Правильный ответ) Отбор лучших особей производится среди объединенного множества ( особей) родителей и потомков.
• родителей производят 1 потомок.
• (Правильный ответ) родителей производят потомков.

Какие факторы оказывают обязательное влияние на выбор фитнесс-функции?

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

Что представляет потенциальное решение в эволюционных стратегиях (ЭС)?

• Дерево.
• (Правильный ответ) Пара векторов вещественных чисел.
• Двоичная строка.
• Вектор вещественных чисел.
• Граф.
• Матрица из вещественных чисел.

Какой двоичный код имеет продукция?

>

• (111 1).
• (101 0).
• (100 1).
• (Правильный ответ) (011 0).

Что отличает многократную ЭС от двукратной?

• (Правильный ответ) Наличие оператора рекомбинации.
• (Правильный ответ) Размер популяции.
• Различные вероятности выбора особей при отборе.
• (Правильный ответ) Одинаковая вероятность выбора особей для мутации.

Сформулируйте содержательный смысл No Free Lunch теоремы.

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

Какие методы самоадаптации используются в современном ЭП?

• (Правильный ответ) Аддитивные методы.
• На основе распределения Пуассона.
• (Правильный ответ) На основе логарифмически нормального распределения.
• (Правильный ответ) Робастное ЭП.
• (Правильный ответ) Мульликативные методы.

Чем отличается многокритериальная задача от однокритериальной ?

• (Правильный ответ) Числом критериев.
• (Правильный ответ) Размерностью пространства образов.
• Размерностью пространства решений.
• Числом функций ограничения.

Что отличает метод «муравьиная система» от простого МА?

• (Правильный ответ) Метод вычисления концентрации феромона.
• (Правильный ответ) Лучший баланс между влиянием интенсивности феромона