Контрольные вопросы Каковы " источники "
 Скачать 192.99 Kb.
|
|
Контрольные вопросы 1. Каковы "источники" ГА? 2. Какие генетические операторы используются в ГА? 3. Какую роль в ГА играет оператор репродукции (ОР)? 4. Опишите реализацию ОР в виде колеса рулетки и приведите пример его работы. 5. Придумайте другую реализацию ОР. 6. Опишите одноточечный оператор кроссинговера (ОК) и приведите пример его работы. 7. Предложите другую реализацию ОК. 8. Какую роль играет оператор мутации (ОМ)? 9. Опишите ОМ и приведите пример его работы. 10. Предложите другую реализацию ОМ. 11. Каковы основные параметры ГА? 1.Каковы "источники" ГА? Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в основополагающей работе и в дальнейшем были развиты рядом других исследователей. Наиболее известной и часто цитируемой в настоящее время является монография Д.Голдберга, где систематически изложены основные результаты и области практического применения ГА. ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. II. Какие генетические операторы используются в ГА? оператора репродукции (ОР); оператора скрещивания (кроссинговера, ОК); оператора мутации (ОМ). III. Какую роль в ГА играет оператор репродукции (ОР)? Процесс, в котором хромосомы копируются в промежуточную популяцию для дальнейшего "размножения" согласно их значениям целевой (фитнесс-) функции называется репродукцией. При этом большую вероятность попадания одного (или более) потомков в следующее поколение имеют хромосомы с лучшими значениями целевой функции . Оператор репродукции есть искусственная вариация выживания сильнейших. Сущствуют разные способы представления этого оператора в алгоритмической форме, но самым простым, и потому часто используемым, является метод - построение колеса рулетки. 4.Опишите реализацию ОР в виде колеса рулетки и приведите пример его работы. Каждая хромосома имеет сектор, пропорциональный по площади значению ее целевой функции. Для селекции хромосом используется случайный поиск на основе колеса рулетки. При этом колесо рулетки вращается и после останова ее указатель определяет хромосому для селекции в промежуточную популяц, ию (родительский пул). Хромосома, которой соответствует больший сектор рулетки, имеет большую вероятность попасть в следующее поколение. В результате выполнения оператора репродукции формируется промежуточная популяция, хромосомы которой будут использованы для построения поколения с помощью операторов скрещивания. 5. Придумайте другую реализацию ОР. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. 6. Опишите одноточечный оператор кроссинговера (ОК) и приведите пример его работы. Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью P_c выполняется в три этапа: 1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР). 2-й этап. Случайно выбирается точка скрещивания - число из диапазона [1,n-1] , где n – длина хромосомы (число бит в двоичном коде). Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания: Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:  7. Предложите другую реализацию ОК. Случайным образом генерируется двоичная маска кроссинговера той же длины (с тем же числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 – второму. Каждый бит потомка копируется из 1-го или 2-го родителя в соответствии со значением этого бита маски. 8. Какую роль играет оператор мутации (ОМ)? Оператор мутации необходим для "выбивания" популяции из локального экстремума и способствует защите от преждевременной сходимости. Достигаются эти чудеса за счет того, что инвертируется случайно выбранный бит в хромосоме. 9. Опишите ОМ и приведите пример его работы. Согласно схеме классического ГА с заданной вероятностью P_m ≈ 0,001 выполняется оператор мутации. Иногда этот оператор играет вторичную роль. Обычно вероятность мутации мала - Оператор мутации (ОМ) выполняется в два этапа.  Пример работы: #include unsigned short MutationMask[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000}; unsigned short Inds[50], // Популяция SelInds[50]; // Особи отобранные для скрещивания // оператор 1-точечного кроссинговера void Cross (int p1, p2, c1, c2) { unsigned short left, right; left = (unsigned short)(15.0 * (double)rand()/(double)RAND_MAX + 1); left = ((unsigned short)0xffff>>left)< right = (unsigned short)0xffff ^ left; Inds[c1] = (SelInds[p1] & left) | (SelInds[p2] & right); Inds[c2] = (SelInds[p2] & left) | (SelInds[p1] & right); } // оператор точечной мутации void Mutate (int j) { int i, L = Inds[j].GetChromosomeLength(); double rnd; for (i=0; i rnd = (double)rand()/(double)RAND_MAX + 1); if (mutationRate > rnd) { // mutationRate - вероятность мутации Inds[j] = Inds[j] ^ MutationMask[i]; } } } 10. Предложите другую реализацию ОМ. Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Вероятность мутации значительно меньше вероятности кроссинговера и редко превышает 1%. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер популяции. 11. Каковы основные параметры ГА? Основными параметрами ГА являются: - длительность эволюции (количество поколений); - размер популяции; - интенсивность (давление) селекции; - разновидность оператора кроссовера; - вероятность кроссовера РС; - разновидность оператора мутации; - вероятность мутации РМ; - величина разрыва поколений Т |