Читать онлайн «Сравнение генетических алгоритмов на примере задачи коммивояжера»

ВЕСТНИК ПЕРМСКОГО УНИВЕРСИТЕТА 20 0 9 Мат ем ат и к а. Механи к а. И нф о р м ат и к а Вып. 3(29) УДК 534. 870 Сравнение генетических алгоритмов на примере задачи коммивояжера Е. Ю. Данилова, А. Ю. Городилов Пермский государственный университет, 614990, Пермь, ул. Букирева, 15 Описаны схемы кодирования и операторы для двух конкретных генетических алгоритмов. Представлены результаты их сравнения на примере задачи коммивояжера. Для этих алго- ритмов собраны статистические данные по решению генерируемых случайным образом гра- фов. На основе полученных данных подобраны оптимальные параметры генетических алго- ритмов. 1. Введение использовании, как правило, получаются приближенные ответы. Насколько точным бу- Данная статья посвящена сравнению дет решение задачи, зависит от самого метода, двух генетических алгоритмов (ГА) на при- от графа, на котором строится решение, и от мере задачи коммивояжера – задачи нахож- различных случайных факторов. дения минимального гамильтонова цикла в При стохастических методах решение графе. задачи генерируется случайным образом. При Задача коммивояжера является NP- благоприятном исходе генерации получается полной, т. е. ее точное решение можно полу- достаточно точный ответ. чить в общем случае только полным перебо- Примером эвристического метода могут ром. Такие алгоритмы требуют больших вы- служить генетические алгоритмы. числительных ресурсов. Можно оценить ко- личество операций, необходимое для полного 2. Постановка задачи перебора всех возможных решений n- вершинного полного графа. Гамильтонов Генетические алгоритмы, построенные цикл однозначно описывается перестановкой для одной задачи, различаются, прежде всего, из n элементов. Поэтому полный перебор под- способами кодирования. Из способа кодиро- разумевает перебор всех возможных переста- вания, т. е. вида генотипа, проистекают виды новок. Но при этом следует учесть, что при скрещивания и мутации. изменении начальной вершины (при сдвиге Естественно, ГА применяются только в перестановки) решение остается одним и тем тех случаях, когда нахождение точного реше- же, т. е. нужно перебирать все перестановки, ния затруднено или даже невозможно. Поэто- начинающиеся с одного числа, например с 1. му при получении некоторого ответа в резуль- Отсюда очевидно, что количество всевозмож- тате работы ГА, как правило, сложно сказать, ных перестановок составляет (n-1)!. насколько он приближен к правильному отве- Для быстрого получения ответа исполь- ту. Отсюда возникает вопрос, при каких па- зуются стохастические и эвристические мето- раметрах генетический алгоритм работает ды. Эти методы не являются точными, при их наилучшим образом.