Применение - генетический оператор
Cтраница 1
Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции. [1]
Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности, либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков, имеющей ту же численность. [2]
Предлагается один из таких способов, связанный с параллельным развитием нескольких популяций и применением генетических операторов к хромосомам из разных популяций. [3]
 |
Решение задачи с помощью классического генетического алгоритма.| Решение задачи с помощью эволюционного алгоритма ( эволюционной программы. [4] |
Эволюционные программы могут оставить постановку задачи в неизменном виде за счет модификации хромосом, представляющих потенциальные решения ( с использованием естественных структур данных), и применения соответствующих генетических операторов. [5]
Выбираются хромосомы, подлежащие репродукции, т.е. формируется родительский пул, особи которого в результате применения генетических операторов сформируют популяцию потомков. Под репродукцией в данном случае понимается процесс отбора ( селекции) и копирования ( размножения) хромосом для формирования из них переходной популяции ( родительского пула), особи которой будут подвергаться воздействию генетических операторов скрещивания, мутации и, возможно, инверсии. [6]
Прюгель-Беннетта [91] разработали теорию, которая на основе принципов статистической механики анализирует динамику ГА при решении комбинаторных задач. Статистическая механика используется в двух эвристиках: в первой - для надежного расчета ожидаемых результатов применения генетических операторов и для расчета отклонений от ожидаемых значений; во второй - для анализа информации, полученной из макропараметров методом максимума энтропии. Очевидно, что для любой популяции на основе математического ожидания и распределения ЦФ можно вычислить корреляцию. Каждому значению корреляции ставится в соответствие энтропия, равная минус логарифму от числа популяций, на которых корреляция принимает данное значение. Тогда максимум энтропии, согласно [91], соответствует наиболее часто встречающемуся значению корреляции среди всех популяций фиксированного размера. [7]
Второе различие между эволюционными стратегиями и генетическими алгоритмами кроется в организации процесса селекции. При реализации эволюционной стратегии формируется промежуточная популяция, состоящая из всех родителей и некоторого количества потомков, созданных в результате применения генетических операторов. С помощью селекции размер этой промежуточной популяции уменьшается до величины родительской популяции за счет исключения наименее приспособленных особей. Сформированная таким образом популяция образует очередное поколение. Напротив, в генетических алгоритмах предполагается, что в результате селекции из популяции родителей выбирается количество особей, равное размерности исходной популяции, при этом некоторые ( наиболее приспособленные) особи могут выбираться многократно. В то же время, менее приспособленные особи также имеют возможность оказаться в новой популяции. Однако шансы их выбора пропорциональны величине приспособленности особей. Независимо от применяемого в генетическом алгоритме метода селекции ( например, рулетки или рангового) более приспособленные особи могут выбираться многократно. При реализации эволюционных стратегий особи выбираются без повторений. В эволюционных стратегиях применяется детерминированная процедура селекции, тогда как в генетических алгоритмах она имеет случайный характер. [8]
Данный оператор сдерживает распространение особо сильных особей в популяции на первых поколениях с целью гарантированного непопадания в локальный оптимум. Для этого оператор мутации инвертирует определенное число битов в популяции на противоположные. Применение генетических операторов для поставленной задачи раскроя имеет некоторые особенности. При воспроизведении розыгрыш воспроизводимых особей реализуется с помощью случайного выбора на суммарном поле значений функции пригодности. Мутация представляется отношением числа измеренных битов к общему числу битов в популяции. [9]
Такое кодирование в виду большого числа нулей избыточное, хотя является наглядным и удобным для преобразований. Отметим, что применение стандартных генетических операторов для такой кодировки является неэффективным в виду большого количества получаемых несуществующих потомков. Предложим вместо матриц использовать списки связности. [10]
Главной концептуальной особенностью модели Tierra является конструкция устойчивого набора команд на машинном языке. Программа ( организм), написанная с помощью такого набора команд, может быть изменена путем случайной мутации или перестановки, но все же остается выполнимой. Иными словами, организмы способны эволюционировать благодаря применению генетических операторов. Хорошо известно, что для наборов команд машинного языка, используемых в традиционном программировании, это совсем не так. [11]
Поскольку аналитические методы исследования условий и скорости сходимости наталкиваются в этой области на серьезные проблемы, была разработана целая система тестовых задач ( benchmark), предназначенных выявить относительную эффективность различных версий алгоритма. На них же было осуществлено сравнение ГА с другими техниками и доказана уникальность его способностей для решения задач глобальной оптимизации. В настройке нуждаются, прежде всего, вероятности применения генетических операторов, оказывающие существенное влияние на сбалансированность процессов отбора и изменчивости. [12]
Машинный код системы Tierra составляют 32 команды. Каждая из них определена пятиразрядным числом. Таким образом, программа представляет собой конкатенацию этих чисел. Исходная программа может быть преобразована в другую программу путем применения генетического оператора, например, точечной мутации. Зеркальное отражение одного бита дает новую программу. Новая программа может, к примеру, содержать команду по operation там, где старая программа имела активную операцию типа перехода. [13]
Страницы: 1