ПОПУЛЯЦИОННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ

Аннотация

В ряде случаев возникает необходимость установления соответствия между заяв- ленным и фактическим значением категориальной переменной на основе совокупности признаков объекта. В этом случае возникает потребность в классификаторе с оптималь- ной последовательностью рассматриваемых атрибутов с заданным значением целевой функции. Значением целевой переменной может быть: да, нет, номер сорта, номер класса и т.д. В работе решается задача построения классификационной модели в виде оптималь- ной последовательность рассматриваемых атрибутов и их значений, входящих в состав маршрута от корневой вершины к концевой вершине с заданным значением целевой пере- менной. Если требуется классификатор, включающий возможность альтернативных от- ветов, то вначале строятся независимо друг от друга оптимальные маршруты для каж- дого значения целевой переменной, а затем эти маршруты объединяются («склеиваются») в единое бинарное дерево решений. В алгоритме построения классификатора на основе метода кристаллизации россыпи альтернатив, каждое решение Qk интерпретируется в виде в ориентированного маршрута Mk на бинарном дереве решений. Назовем порядковый номер элемента в ориентированном маршруте Mk позицией siS={si|i=1,2,…,nA}. Элемен- том маршрута Mk является пара (xi,ui-), где xi соответствует Ai. ui- в маршруте Mk явля- ется ребром, выходящим из xi и соответствует выбранному вместе с Ai значению Ai. Вто- рой индекс элемента ui- определится после выбора Ai, помещенного в соседнюю с sj позицию sj+1. Работа алгоритма построения дерева решений базируется на использовании коллек- тивной эволюционной памяти, под которой подразумевается информация, отражающая историю поиска решения. Алгоритм учитывает тенденции к использованию альтернатив из наилучших найденных решений. Особенностями являются наличие непрямого обмена информацией – стигмержи. Совокупность данных об альтернативах и их оценках состав- ляет россыпь альтернатив. Рассмотрены ключевые моменты анализа альтернатив в про- цессе эволюционной коллективной адаптации. Экспериментальные исследования показали, что разработанный алгоритм находит решения, не уступающие по качеству, а иногда и превосходящие своих аналогов в среднем на 3–4 %. Временная сложность алгоритма, полу- ченная экспериментальным путем, лежит в пределах О(n2)-О(n3).