Понятия и определения теории генетических алгоритмов
В качестве примера рассмотрим два способа представления перестановок при решении оптимизационных задач. В первом случае будем использовать одного родителя, и получать потомка. Во втором операторе мы используем двух родителей, случайно выберем точку перестановки и для образования потомка возьмем первый сегмент у первого родителя, а второй сегмент - у второго. Первый оператор похож на бесполое размножение, а второй оператор - на половое размножение. Стоит отметить, что если первый оператор всегда генерирует реальное решение, то второй может генерировать недопустимые решения. Но это не мешает нам его использовать, просто требуется «восстанавливать» решения перед их оценкой. Например, можно использовать замещение. Как только это сделано для каждого повторяющегося решения, потомок будет восстанавливаться, и будет соответствовать реальному решению.
На третьем из рассматриваемых этапов задаются правила выживания решений для создания потомства. Так же как и со случайными операторами, существует множество способов проведения селекции. Простейшее правило - это выживание сильнейших, т. е. когда только лучшие решения выживают, а все остальные устраняются. Однако такое правило часто оказывается малоэффективным при решении сложных проблем, когда лучшие решения могут происходить от худших, а не только от самых лучших. Однако логично использовать принцип, что вероятность выживания хорошего решения должна быть выше.
Последний предварительный этап заключается в создании начальной популяции. Если у нас недостаточно знаний о проблеме, то решения могут случайным образом выбираться из всего множества возможных. Это означает генерацию случайных перестановок, где каждая перестановка представляет собой определенное решение. С другой стороны, можно использовать некоторые знания о задаче при создании начальной популяции, например, эти данные могут быть получены из опыта решения этой же задачи другими алгоритмами. Если эти решения действительно ценные, то они выживут и произведут потомство, если же нет, то они погибнут вместе с другими слабыми индивидами[1,5].