Простой генетический алгоритм случайным образом формирует начальную популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнится заданное число поколений или иной критерий остановки. На каждом поколении реализуется отбор по критерию приспособленности. Первоначально каждый структуре назначается вероятность её участия в скрещивании ( - приспособленность i-ой структуры) затем происходит отбор особей для дальнейшей генетической обработки. После отбора, особи подвергаются скрещиванию. M строк случайным образом разбиваются на пары.
Скрещивание бывает одноточечное, двухточечное и равномерное (основано на вероятностях).
В равномерном скрещивании каждый бит первого родителя наследуется потомком с заданной вероятностью, в противном случае наследуется ген второго родителя.
Schema – строка длины l, состоящая из 0 или 1 и неопределенных символов.
Пример:
Каждая шима имеет 2 свойства – порядок и определенная длина.
· Порядок – число определенных битов;
· Определенная длина – расстояние между крайними определенными битами;
Приспособленность шимы определяется средним количеством строк, которые её содержат. После отбора остаются только строки с более высокой приспособленностью. Скрещивание реже разрушают шимы с более короткой определенной длиной, с более низким порядком, а мутация реже разрушает шимы с низким порядком и более высокой определенной длиной, поэтому такие шимы имеют больше шансов переходить из поколения в поколение.
Теорема шим
Простой генетический алгоритм экспоненциально увеличивает число примеров полезных шим или строящих блоков.
- число примеров шимы в поколении .
- вероятность участия шимы в скрещивании. - средняя приспособленность популяции. - средняя приспособленность строк популяции, являющейся примерами H (1).
- вероятность того, что шима переживет скрещивание (2).
- вероятность того, что шима переживет мутацию.
- данная форма верна при малом .
Вычислим ожидаемое число примеров шимыH в поколении. Простой генетический алгоритм каждой строке ставит в соответствие вероятность её выживания при отборе пропорционально её приспособленности. Предположим, что шимаH может быть выбрана количество раз. Вероятность того, что одноточечное скрещивание разрушит шиму, равна вероятности того, что точка разрыва попадет между определенными битами. Вероятность, того что шимаH переживет скрещивание, не меньше (1). Эта вероятность представляет собой неравенства, поскольку шима сможет выжить, если в скрещивании участвовал пример похожей шимы.
Вероятность того, что шимаHпереживет мутацию равна (2).
Тогда ожидаемое число примером шимыH в поколении будет равно:
Теорема шим показывает, что строящие блоки растут по экспоненте, в то время как шимы с приспособленностью ниже средней распадаются с той же скоростью.
Теорема шим описывает следующие аспекты поведения генетического алгоритма:
1) Мутации с большей вероятностью разрушают шиму более высокого порядка, а скрещивание с большей вероятностью разрушает шимы с большей определенной длиной;
2) Когда происходит отбор, популяция сходится пропорционально отношению приспособленности лучшей особи к средней приспособленности популяции. Это отношение называется мерой давления отбора;
3) Увеличение вероятности скрещивания или вероятности мутации, или уменьшение давления отбора ведет к увеличению выборки или исследованию пространства поиска, но не позволяет использовать все хорошие шимы, которым располагает генетический алгоритм;
4) Уменьшение вероятности скрещивания или вероятности мутации, или увеличение давления отбора ведет к улучшению использования найденныхшим, но тормозит исследование пространства поиска новых хороших шим;
5) Генетический алгоритм должен поддерживать равновесие между тем и другим, что известно как проблема баланса исследования и использования;
