VEGAS - новый генетический алгоритм для задачи Выполнимость

Abstract

Мы исследуем модель генетических вычислений, в которой, в отличие от классической, рассматривается влияние популяции на окружающую среду. В качестве «полигона» выбрана важная как с практической, так и с теоретической точек зрения задача Выполнимость. Предложенный нами алгоритм VEGAS представляет собой локальный стохастический поиск и взвешивание ограничений, помещенные в рамки генетического подхода. По результатам тестирования VEGAS существенно превосходит алгоритм GASАТ - один из лучших разработанных для задачи Выполнимость генетических алгоритмов.

We study a model of genetic computations in which, in contrast to a classical model, population influences the environment. We apply this model to the SATISFIABILITY problem that is of both practical and theoretical importance. We develop VEGAS, an algorithm that uses local search and weighted constraints within the genetic approach. On a benchmark set of problems, VEGAS performs substantially better than GASAT, one of the best genetic SAT-solvers.