Главная / Алгоритмы и дискретные структуры /
Эволюционные вычисления / Тест 1
Номер 3
Ответ:
Эволюционные вычисления - тест 1
Упражнение 1:
Номер 1
Ответ:
Номер 1
Какие концепции составляют ядро генетических алгоритмов (ГА)?
Ответ:
(1) а) естественный отбор по Ч. Дарвину; б) эволюционная теория Ж. Ламарка;
(2) а) эволюционная теория Ж. Ламарка; б) генная структура хромосом; в) концепция мутации.
(3) а)концепция репродукции; б) концепция случайного замещения генов в хромосоме; в) выживание сильнейших особей в популяции.
(4) а) естественный отбор по Ч. Дарвину; б) генная структура хромосом; в) концепция мутации.
(5) а) концепция репродукции; б) выживание сильнейших особей в популяции по Ч.Дарвину.
(6) а) генная структура хромосом; б) концепция мутации.
Номер 2
Ответ:
Каковы операторы, с помощью которых в ГА генерируется следующее поколение особей?
Ответ:
(1) Оператор случайной перестановки пары генов в хромосоме, оператор кроссинговера, оператор репродукции.
(2) Оператор репродукции, оператор скрещивания, оператор мутации.
(3) Оператор репродукции, оператор мутации.
(4) Оператор мутации, оператор кроссинговера, оператор репродукции.
Каковы критерии останова ГА?
Ответ:
(1) Генерация заданного количества поколений особей.
(2) Достижение заданного качества одной из особей в очередном поколении.
(3) Достижение заданного качества по крайней мере двумя особями в очередном поколении.
(4) Генерация заданного количества поколений особей и достижение заданного качества одной из особей в очередном поколении.
Упражнение 2:
Номер 1
Ответ:
Номер 1
Чем отличается ГА от случайного поиска?
Ответ:
(1) В ГА используется информация, накопленная в процессе эволюции.
(2) В ГА поддерживается баланс между "эксплуатацией" полученных на текущий момент лучших решений (особей) и расширением пространства поиска.
(3) В ГА используется информация, накопленная в процессе эволюции, и поддерживается баланс между "эксплуатацией" полученных на текущий момент лучших решений (особей) и расширением пространства поиска.
(4) В ГА используется поиск, направляемый на очередной итерации с применением градиентных методов.
Номер 2
Ответ:
Каков в ГА наиболее популярный метод реализации оператора репродукции?
Ответ:
(1) Метод колеса рулетки.
(2) Метод пропорциональности значениям целевой функции.
(3) Метод обмена хромосом-родителей случайным образом выбранными их фрагментами одинаковой длины.
(4) Метод инвертирования случайным образом выбранных фрагментов одинаковой длины хромосом-родителей с последующем обменом этими фрагментами.
Номер 3
Ответ:
В чем состоит суть метода колеса рулетки при выборе особей для участия в операторе репродукции?
Ответ:
(1) Организация равномерного случайного выбора особей.
(2) Выбор особи с вероятностью, пропорциональной соответствующей ей площади колеса рулетки.
(3) Организация элитарного выбора особи на основе нормального закона распределения вероятностей.
(4) Организация элитарного выбора особи на основе распределения вероятностей по закону Пуассона.
Упражнение 3:
Номер 1
Ответ:
Номер 1
Выполните простой (одноточечный) оператор кроссинговера над хромосомами А и В, если точка кроссинговерарасположена сразу за
.
Ответ:
(1) Особи-потомки есть 100100 и 010101.
(2) Особи-потомки есть 100010 и 011010.
(3) Особи-потомки есть 100101 и 010101.
(4) Особи-потомки есть 011011 и 100010.
Номер 2
Ответ:
Выполните простой (одноточечный) оператор кроссинговера над хромосомами А и В, если точка кроссинговера.
Ответ:
(1) Особи-потомки есть 1010101 и 0100100.
(2) Особи-потомки есть 1010100 и 0110101.
(3) Особи-потомки есть 1000101 и 0110101.
(4) Особи-потомки есть 1010100 и 0100101.
Номер 3
Ответ:
Выполните простой (одноточечный) оператор кроссинговера над хромосомами А и В, если точка кроссинговера.
Ответ:
(1) Особи-потомки есть 11100100 и 11110101.
(2) Особи-потомки есть 11101000 и 11100101.
(3) Особи-потомки есть 11100101 и 11101010.
(4) Особи-потомки есть 11101011 и 11100101.
Упражнение 4:
Номер 1
Ответ:
Номер 1
Решается задача поиска экстремума функции вещественной переменнойна отрезке
cточностью до знаков после запятой с использованием ГА. Требуется найти диапазон представления решения задачи (особи-хромосомы)в виде двоичного числа. Отрезок
.
Ответ:
(1) Границы диапазона суть 10-значные двоичные числа, искомый диапазон есть [0000000000,1111111111].
(2) Границы диапазона суть 9-значные двоичные числа, искомый диапазон есть [000000000,111111111].
(3) Границы диапазона суть 8-значные двоичные числа, искомый диапазон есть [00000000,11111111].
(4) Границы диапазона суть 7-значные двоичные числа, искомый диапазон есть [0000000,1111111].
Номер 2
Ответ:
Решается задача поиска экстремума функции вещественной переменной.
Ответ:
(1) Границы диапазона суть 10-значные двоичные числа, искомый диапазон есть [0000000000,1111111111].
(2) Границы диапазона суть 11-значные двоичные числа, искомый диапазон есть [00000000000,11111111111].
(3) Границы диапазона суть 12-значные двоичные числа, искомый диапазон есть [000000000000,111111111111].
(4) Границы диапазона суть 13-значные двоичные числа, искомый диапазон есть [0000000000000,1111111111111].
Номер 3
Ответ:
Решается задача поиска экстремума функции вещественной переменной.
Ответ:
(1) Границы диапазона суть 9-значные двоичные числа, искомый диапазон есть [000000000,111111111].
(2) Границы диапазона суть 10-значные двоичные числа, искомый диапазон есть [0000000000,1111111111].
(3) Границы диапазона суть 11-значные двоичные числа, искомый диапазон есть [000000000000,111111111111].
(4) Границы диапазона суть 12-значные двоичные числа, искомый диапазон есть [000000000000,111111111111].
Упражнение 5:
Номер 1
Ответ:
Номер 1
Какие факторы оказывают обязательное влияние на выбор фитнесс-функции?
Ответ:
(1) Тип решаемой задачи(минимизация, максимизация) и объем вычислительных ресурсов.
(2) Наличие ограничений в решаемой задаче и возможность совмещения различных подцелей (для многокритериальных задач).
(3) Необходимость отражения наличия шумов окружающей среды.
(4) Свойства математической модели исследуемой задачи (например, гладкость функции, для которой ищется экстремум, ее дифференцируемость и т.п.)
Номер 2
Ответ:
Пусть H =01*110** есть схема (шаблон), используемая в ГА. Определите значение порядка схемы O(H) и ее длину L(H).
Ответ:
(1) O(H)= 4,L(H)= 5.
(2) O(H)= 5, L(H)= 5.
(3) O(H)= 5, L(H)= 4.
(4) O(H)= 6, L(H)= 4.
Номер 3
Ответ:
Каковы условия возрастания с ростом номера поколений числа хромосом, представляющих "хорошее" решение исследуемой задачи, из схемы-источника?
Ответ:
(1) Значение фитнесс-функции "хорошей" схемы-источника должно быть выше ее среднего значения по всей популяции.
(2) "Хорошая" схема-источник должна иметь малую вероятность мутации.
(3) "Хорошая" схема-источник должна иметь малую длину L(H).
(4) "Хорошая" схема-источник должна иметь большое значение порядка O(H).
Упражнение 6:
Номер 1
Ответ:
Номер 1
От чего зависит эффективность применения ГА?
Ответ:
(1) От вида и структуры фитнесс-функции.
(2) От мощности популяции.
(3) От вероятности и вида операторов кроссинговера и мутации.
(4) От вычислительной сложности получения значений фитнесс-функции.
(5) От структуры представления хромосом-решений.
Номер 2
Ответ:
Сформулируйте содержательный смысл фундаментальной теоремы ГА.
Ответ:
(1) Число "хороших" хромосом-решений исследуемой задачи, покрываемых схемой 
,возрастает с ростом 
числа итераций ГА как 
.
,возрастает с ростом числа итераций ГА как .
(2) Схемы малого порядка и малой длины с ростом числа итераций ГА формируют множество своих представителей, мощность которого растет по степенному закону.
(3) Схемы малого порядка и малой длины с ростом числа итераций ГА формируют множество своих представителей, мощность которого растет по показательному закону.
(4) Число "хороших" хромосом-решений исследуемой задачи, покрываемых схемой , возрастает с ростом числа итераций ГА как 
.
, возрастает с ростом числа итераций ГА как .
Номер 3
Ответ:
Сформулируйте содержательный смысл No Free Lunch теоремы.
Ответ:
(1) Среди всех эволюционных алгоритмов существует по крайней мере один, который дает лучшие результаты при решении всевозможных проблем.
(2) Невозможно выбрать генетические операторы и их параметры так, чтобы соответствующий эволюционный алгоритм давал лучшие результаты независимо от решаемой проблемы.
(3) Существует такое разбиение множества всех оптимизационных проблем, что для каждого такого подмножества найдется эволюционный алгоритм, дающий наилучшие результаты.
(4) Не существует лучшего алгоритма (эволюционного или любого другого типа) для решения всех оптимизационных проблем.