Введение в эволюционное моделирование. Каширина И.Л. - 17 стр.

                                  17
го, f(S) и fср не остаются постоянными от поколения к поколению. Приспо-
собленности членов популяции знаменательно изменяются уже после не-
скольких первых поколений. Во-вторых, теорема схем объясняет потери
схем, но не появление новых. Новые схемы часто создаются кроссовером и
мутацией. Кроме того, по мере эволюции, члены популяции становятся все
более и более похожими друг на друга так, что разрушенные схемы будут
сразу же восстановлены.
       Однако, несмотря на простоту, теорема схем описывает несколько
важных аспектов поведения ГА. Мутации с большей вероятностью разру-
шают схемы высокого порядка, в то время как кроссоверы с большей веро-
ятностью разрушают схемы с большей определяющей длиной. Когда проис-
ходит отбор, популяция сходится пропорционально отношению приспособ-
ленности лучшей особи к средней приспособленности в популяции; это от-
ношение � �        мера давления отбора. Увеличение или Pc, или Pm или
уменьшение давления отбора ведет к увеличению разнообразия выборки или
исследованию пространства поиска, но не позволяет использовать все хоро-
шие схемы, которыми располагает ГА. Уменьшение или Pc, или Pm или уве-
личение давления выбора ведет к улучшению использования найденных
схем, но тормозит исследование пространства в поисках новых хороших
схем. ГА должен поддержать тонкое равновесие между тем и другим, что
обычно известно как проблема "баланса исследования и использования".
        4. Решение задачи коммивояжера с помощью
                 генетических алгоритмов
Введение в проблему коммивояжера
      Задача коммивояжера в теории дискретной оптимизации считается
классической тестовой задачей. Впервые она была сформулирована еще в
1759 году. Суть задачи состоит в том, чтобы найти кратчайший замкнутый
путь обхода нескольких городов, заданных своими координатами (или с по-
мощью матрицы расстояний между ними). Города могут посещаться только
единожды. Известно, что уже для 50 городов поиск оптимального пути
представляет собой сложную задачу, побудившую развитие различных но-
вых методов (в том числе нейросетевых и генетических алгоритмов).
Эта задача NP-полная (задача c экспоненциальной оценкой числа итераций,
необходимых для отыскания точного решения) и мультимодальная (имеет
локальные экстремумы). ГА используется для нахождения околооптималь-
ного пути за линейное время.