Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Рассматривая некоторую задачу в виде задачи Constraint Satisfaction Problem (CSP), можно достичь нескольких важных преимуществ. Представление состояний в задаче CSP соответствует некоторому стандартному шаблону (т. е. выражается в виде множества переменных с присвоенными значениями), поэтому функцию определения преемника и проверку цели можно записать в универсальной форме, применимой ко всем задачам CSP. Более того, могут быть разработаны эффективные, универсальные эвристические функции, для созда­ ния которых не требуются дополнительные знания о конкретной проблемной области. Наконец, для упрощения процесса решения может использоваться сама структура графа ограничений, что позволяет в некоторых случаях добиться экспоненциального уменьшения сложности. Важную роль в решении ЗУО играют методы локального поиска, идея которых заключается в направленном исследовании многообещающих регионов пространства поиска вместо полного перебора всех возможных решений. [1]. Ниже будут рассмотрены некоторые из методов локального поиска и их основные особенности. Генетический алгоритм Генетическим алгоритмом (ГА) называется следующий объект: ГА(Р, г, I, si, Fit, cr,m,ot ) , (1) где Р - исходная популяция; г - количество элементов популяции; I - длина битовой строки, кодирующей решение; si -оператор селекции; Fit - функция фитнесса (функция полезности), определяющая «пригодность» решения; сг - оператор кроссинговера, определяющий возможность получения нового решения; т - оператор мутации; ot - оператор отбора. Пусть область поиска решения D задачи однокритериального выбора является конечным множеством решений, в котором каждое допустимое решение X е D является «-мерным вектором X (х ,.х2. ..., х„). Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь Н[ ( к - номер особи, t - момент времени эволюционного процесса). В качестве аналога особи в задаче оптими­ зации принимается произвольное допустимое решение X е D, которому прис­ воено имя Н ‘к. Действительно, вектор X - это наименьшая неделимая единица, характеризующая в экстремальной задаче внутренние параметры объекта оптимизации на каждом t-м шаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации некоторого критерия оптимальности J(X). Качественные признаки особи Н{ определяются как соответствующие точке X с именем Н{ (в простейшем случае битовой строке). Некоторая особь Н{ будет характеризоваться п генами, каждый из которых отвечает за форми­ рование целочисленного кода соответствующей переменной. Тогда структуру битовой строки можно интерпретировать хромосомой, содержащей п сцеп­ ленных между собой генов. Местоположение /-го гена в хромосоме - локус, значение - аллель h. 60