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

Упражнение 1:

Номер 1

Какие стратегии создания исходной популяции наиболее популярны при использовании ГА?

Ответ:

(1) Стратегия "дробовика".

(2) Стратегия фокусировки.

(3) Стратегия "одеяла".

(4) Комбинация стратегий "дробовика" и фокусировки.

(5) Комбинация стратегий "одеяла" и фокусировки.

Номер 2

Каким образом возможно отбор родителей методом рулетки преобразовать в чисто случайный отбор?

Ответ:

(1) Выполнить подходящее масштабирование значений целевой функции.

(2) Добавлять большую константу к каждому значению целевой функции.

(3) Разбить всю площадь круга рулетки на равные по площади сектора.

(4) Вычитать из каждого значения целевой функции ее максимальное значение.

Номер 3

Влияет ли величина значения фитнесс-функции особи в процессе эволюции на результат поиска оптимального решения?

Ответ:

(1) Величина значения фитнесс-функции никак не влияет на результат поиска оптимального решения с использованием ГА.

(2) Это зависит от метода отбора потомков: если, например, производится элитарный отбор, то особи с большими значениями фитнесс-функции быстро "вытесняют" из популяции остальные особи, что может привести к преждевременной сходимости ГА.

(3) Особи с очень маленькими значениями фитнесс-функции очень быстро исключаются из популяции, что приводит к преждевременной сходимости ГА.

(4) Если в начальной популяции значения фитнесс-функций для особей незначительно отличаются друг от друга, то это гарантирует получение оптимального решения.

Упражнение 2:

Номер 1

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

Ответ:

(1)

(2)

(3)

(4)

Номер 2

При локальном отборе родителей поясните понятие окрестности особи в случаях: а) линейного соседства; б) двухмерного 4-связного соседства; в) двухмерного 8-связного соседства.

Ответ:

(1) а) Предполагается, что особь расположена на одномерной линии. Ее соседям являются особи, расположенные слева и справа от нее на этой линии на расстоянии math

, которое может варьироваться. б) Предполагается, что особь расположена на плоской 4-связной решетке. Ее соседям являются особи, расположенные слева и справа, а также вверху и внизу от нее на этой решетке (крест) на расстоянии math

, которое может варьироваться. в) Предполагается, что особь расположена на плоской 8-связной решетке. Ее соседям являются особи, расположенные слева и справа от нее, а также вверху, внизу и по диагонали (звезда) на расстоянии math

, которое может варьироваться.

(2) В отличие от ответов в 1 п.п. а), б), в) величина math

варьироваться не может и полагается равной math

в п. а),

в п. б) и

в п. в).

(3) В отличие от ответов в 1 п.п. а), б), в) величина math

варьироваться не может и полагается равной math

во всех трех пунктах.

(4) В отличие от ответов в 1 п.п. а), б), в) величина math

варьироваться не может и полагается равной math

в п. а),

в п. б) и

в п. в).

Номер 3

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

Ответ:

(1) Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: math

. Далее формируются пары родителей math

, где i=1,2,\dots,k/2.

(2) Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: math

. Далее из них случайным образом формируются пары родителей.

(3) Вначале из текущего множества особей случайным образом выбирается половина и она упорядочивается согласно значениям их фитнесс-функций: math

.Далее формируются пары родителей math

.

(4) Вначале отбираемые особи упорядочиваются согласно их значениям фитнесс-функции. Далее из них выбирается "лучшая" часть и, наконец, среди них случайным образом выбираются пары родителей. При этом используется параметр – порог отсечения math

, показывающий долю (часть популяции), которая отбирается в качестве родителей. Обычно math

.

Упражнение 3:

Номер 1

Пусть имеется популяция, содержащая 12 особей math

, для которых известны значения фитнесс-функции : math

. Требуется произвести детерминированный турнирный отбор родителей в этой популяции за math

туров.

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

Ответ:

(1) В родительский пул вошли особи math

(2) В родительский пул вошли особи math

(3) В родительский пул вошли особи math

(4) В родительский пул вошли особи math

Номер 2

Пусть имеется популяция, содержащая 12 особей , для которых известны значения фитнесс-функции : . Требуется произвести детерминированный турнирный отбор родителей в этой популяции за  туров., случайным образом получено 6 туров: (5,7), (6,8), (12,1), (3,2),(4,11),(9,10).

Ответ:

(1) В родительский пул вошли особи math

(2) В родительский пул вошли особи math

(3) В родительский пул вошли особи math

(4) В родительский пул вошли особи math

Номер 3

Пусть имеется популяция, содержащая 12 особей math

, для которых известны значения фитнесс-функции : math

. Требуется произвести детерминированный турнирный отбор родителей в этой популяции за math

туров.

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

Ответ:

(1) В родительский пул вошли особи math

(2) В родительский пул вошли особи math

(3) В родительский пул вошли особи math

(4) В родительский пул вошли особи math

Упражнение 4:

Номер 1

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

Ответ:

(1) Панмиксия, селективный выбор.

(2) Инбридинг, аутбридинг (генотипный и фенотипный).

(3) Случайный выбор из особей, значения фитнесс-функций которых как минимум вдвое выше среднего значения по популяции.

(4) Комбинация инбридинга и аутбридинга.

Номер 2

В чем состоит существо панмиксии?

Ответ:

(1) Панмиксия –это случайный выбор особей из популяции для объединения в пару.

(2) Панмиксия– это эквивалент случайного выбора пары из элитарного подмножества популяции.

(3) Панмиксия – это объединение в пары наиболее близких по значениям фитнесс-функции соседей.

(4) Панмиксия – это объединение в пары наиболее далеких по значениям фитнесс-функции соседей.

Номер 3

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

Ответ:

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

(2) Этот метод предполагает случайный выбор особей.

(3) Панмиксия и селективный выбор представляют собой эквивалентные методы выбора.

Номер 4

Чем отличается инбридинг от аутбридинга?

Ответ:

(1) В инбридинге предполагается участие в выборе особей лишь с "хорошими" (выше среднего по популяции) значениями фитнесс-функции. В аутбридинге участвуют все особи текущего поколения независимо от значений фитнесс-функций.

(2) В инбридинге пары формируются из максимально далеких особей. В аутбридинге пары формируются из максимально близких особей.

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

Упражнение 5:

Номер 1

Для особей math

= 110101100101 и math

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

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

Ответ:

(1) П1=110010100101, П2= 101101110010.

(2) П1=110010101100, П2= 101101110010.

(3) П1=110011101101, П2= 101101110011.

(4) П1=110010101100, П2= 101101110110.

Номер 2

Для особей math

= 110101100101 и math

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

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

Ответ:

(1) П1=110110100101, П2= 101101010110.

(2) П1=110010100101, П2= 101101110010.

(3) П1=110101110001, П2= 101101100110.

(4) П1=1010010101100, П2= 101101110100.

Номер 3

Для особей math

= 110101100101 и math

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

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

Ответ:

(1) П1=110110101101, П2= 101001010110.

(2) П1=110010000101, П2= 101101010010.

(3) П1=101010110001, П2= 110101100110.

(4) П1=101001010110, П2= 101101100100.

Упражнение 6:

Номер 1

Пусть задана маска =(0110011010) , два родителя =1101101011 и =0101010100.Требуется найти потомка этих родителей с использованием оператора однородного кроссинговера.

Ответ:

(1) П=0100101010

(2) П=0101101110

(3) П=0101001110

(4) П=0100101010

Номер 2

Пусть заданы маски =(2,1,2,1) и =(1,2,1,2) , два родителя =(27,193,25,14) и =(16,7,9,8).Требуется найти двух потомков П1 и П2с использованием оператора дискретного скрещивания.

Ответ:

(1) П1=(16,25,9,14), П2= (27,193,25,8).

(2) П1=(16,193,9,14), П2= (27,7,25,8).

(3) П1=(16,193,9,14), П2= (27,7,25,9).

(4) П1=(16,25,9,14), П2= (27,7,25,8).

Номер 3

Пусть заданы родителя =(27,193,25,14) и =(16,7,9,8). Пусть случайным образом выбраны следующие масштабные множители  для и  соответственно для получения двух потомков О1 и О2. Требуется построить этих потомков с использованием оператора обычной промежуточной рекомбинации.

Ответ:

(1) П1=(21,5;44,2;23,4;17,48), П2=(22,6;23,48;17;10,4).

(2) П1=(21,5;62,8,2;23,4;9,8), П2=(22,6;10,35;17;10,4).

(3) П1=(21,5;44,2;23,4;10,4), П2=(22,6;62,8;17;10,4 ).

(4) П1=(21,5;44,2;23,4;9,8), П2= (22,6;62,8;17;10,4).

Номер 4

Пусть заданы родителя =(27,193,25,14) и =(16,7,9,8).Пусть случайным образом выбран масштабные множитель  и  для получения двух потомков П1 и П2. Требуется построить этих потомков с использованием оператора линейной рекомбинации.

Ответ:

(1) П1=(21,5;100;17;11), П2= (22,6;118,6;18,6;11,6).

(2) П1=(21,5;101;17,2;11), П2= (22,6;118,6;18,6;11,6).

(3) П1=(21,5;100;17;11,5),П2=(22,6;118,6;18,36;11,11).

(4) П1=(21,5;90;117;11), П2= (22,6;118,6;18,36;11,11).

Упражнение 7:

Номер 1

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

Ответ:

(1)

(2)

(3)

(4)

Номер 2

Выполнить оператор инверсии над хромосомой Р =1011100101, если в ней случайным образом были выбраны позиции 4 и 7.

Ответ:

(1) 1010101101

(2) 1010101011

(3) 1010111001

(4) 1010101010

Номер 3

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

Ответ:

(1) 101,7650

(2) 101,7515

(3) 101,7510

(4) 101,7610

Номер 4

Перечислите известные вам методы редукции, применяемые для сокращения промежуточной популяции и кратко охарактеризуйте их.

Ответ:

(1) Чистая замена, элитарная схема.

(2) Равномерная случайная замена, пропорциональная редукция.

(3) Селекционная схема, локальная замена.

(4) Фильтрация популяции по среднему значению целевой функции популяции.

Упражнение 8:

Номер 1

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

Ответ:

(1) Многократный запуск ГА на различных подмножествах пространства поиска решений, реализуемый либо параллельным способом, либо индуктивным.

(2) Разбиение популяции на несколько частей с выполнением соответствующей модификации фитнесс-функции.

(3) Применение простого ГА классическим стандартным способом.

(4) Предварительная оценка числа math

возможных экстремумов мультимодальной функции с последующем случайным разбиением пространства поиска на math

равных частей и поиска в них решений.

Номер 2

Что представляет собой ниша в ГА?

Ответ:

(1) Ниша – это совокупность особей популяции, концентрирующихся вокруг некоторой точки экстремума мультимодальной функции. Основная идея при поиске такой точки экстремума состоит в увеличении значений фитнесс- функции пропорционально числу особей в этой области.

(2) Ниша – это совокупность особей популяции, концентрирующихся вокруг некоторой точки экстремума мультимодальной функции. Основная идея при поиске такой точки экстремума состоит в уменьшении значений фитнесс- функции пропорционально числу особей в этой области.

(3) Ниша - это подмножество пространства поиска решений экстремумов мультимодальной функции, содержащее более одной точки экстремума.

(4) 4.Ниша - это подмножество пространства поиска решений экстремумов мультимодальной функции, содержащее ровно одну точку экстремума.

Номер 3

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

Ответ:

(1) Какие-либо принципиальные отличия процессов эволюции по Ламарку и Дарвину отсутствуют.

(2) По Ламарку в процессе эволюции окружающая среда оказывает прямое влияние на наследуемые признаки. Причем соответствующие изменения далее способны передаваться по наследству, что не предусматривает теория эволюции по Дарвину.

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

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

Номер 4

В чем состоит адаптация ГА?

Ответ:

(1) Адаптация ГА состоит в адаптации к решаемой проблеме и в адаптации к процессу эволюции.

(2) Адаптация ГА состоит в адаптации мощности популяции и вероятностей операторов кроссинговера и мутации.

(3) Адаптация ГА означает только адаптацию к применению нечетких контроллеров.

(4) Адаптация ГА – это процесс самонастройки параметров ГА в процессе выполнения эволюции.

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