Представим задачу в терминах эволюционных вычислений. Рассмотрим стандартный генетический алгоритм. Генетические алгоритмы работают с популяцией, каждая их хромосом которой представляет собой возможное решение данной задачи. В нашем случае решение — это разбиение неупорядоченного набора информационных ресурсов на кластеры.
Кодирование хромосом Хромосома представляет собой массив пар (документ, кластер). Длина такого массива всегда будет такой, сколько документов требуется разбить на кластеры. Соответственно, если стоит задача разбить информационные ресурсы на N кластеров, то его значения варьируются от 1 до N.
Селекция Каждая хромосома оценивается мерой ее «приспособленности» (fitness-function). Наиболее приспособленные особи получают большую возможность участвовать в воспроизводстве потомства. Используется пропорциональный отбор.
Кроссовер Используется как одноточечный, так и многоточечный кроссовер.
Мутация После стадии кроссовера выполняется операция мутации, которая в данной задаче представляет собой обмен двух случайных номеров кластеров. Номера документов, для которых значения кластеров меняются местами, выбираются случайным образом.
Оценка приспособленности (Fitness-function).
В результате применения генетических операторов мы получаем хромосому, представляющую собой возможный вариант решения. Представим информационный ресурс точкой в n-мерном пространстве терминов.
Индексатор формирует список слов документа по принципу «каждое слово отделяется от другого пробелом». Для каждого термина рассчитывается его вес в данном информационном ресурсе, то есть для каждого документа мы можем определить его координату, состоящую из частот встречаемости терминов в информационном ресурсе. Координатными осями в данном случае выступают термины.
Функцию оптимальности рассчитаем как сумму евклидовых расстояний от информационных ресурсов до центров соответствующих кластеров (к которым они отнесены).
