МЕТАЕВРИСТИЧНІ МЕТОДИ ПОШУКУ ОПТИМАЛЬНИХ КЛАСИФІКАЦІЙ

  • I. V. Kozin
  • E. K. Seliutin
Ключові слова: задача оптимальної класифікації, класифікація, еволюційний алгоритм, алгоритм мурашиної колонії, алгоритм перемішаних стрибаючих жаб

Анотація

Одним з головних завдань будь-якого наукового дослідження є задача класифікації. Хоча формалізація задачі класифікації є досить простою, рішення її може виявитися досить складним в обчислювальному сенсі. Більшість існуючих методів класифікації засновано на статистичних принципах, факторизації, кластерному та дисперсійному аналізі. Часто для побудови «хороших» класифікацій використовують системи, що здатні навчатись, зокрема, нейронні мережі. Складність завдання класифікації зумовлена невизначеністю розбиття на класи і складністю пошуку оптимальної класифікації за умов використання певного критерію оптимальності. Зазначено, що задача класифікації на кінцевій множині полягає в пошуку розбиття, що володіє деякими заданими властивостями. Розбиття множини задає канонічне відношення еквівалентності, пов'язане з цим розбиттям. Зокрема, два елементи вважаються еквівалентними, якщо вони належать одному елементу розбиття. З іншого боку, будь-яке відношення еквівалентності на кінцевій множині визначає його розбиття на класи еквівалентних між собою елементів. У цій статті розглядаються класифікації, які побудовано на основі відносини толерантності або близькості. При цьому розбиття на класи є неоднозначним і істотно залежить від вибору представників класів. В роботі показано, що задача пошуку оптимальної класифікації на скінченій множині за умов наявності критерію оптимальності може бути зведена до задачі пошуку оптимальної перестановки елементів цієї множини. Задача пошуку оптимальної перестановки відноситься до розряду важких в обчислювальному сенсі задач. У статті пропонується метод використання деяких відомих метаевристик до задачі пошуку субоптимальних перестановок елементів множини за заданим критерієм оптимальності. Розглянуто три метаевристики на перестановках елементів скінченої множини (еволюційний алгоритм, алгоритм мурашиної колонії і метод перемішаних стрибаючих жаб), які можна з успіхом застосовувати при вирішенні задачі пошуку оптимальної класифікації.

Переглядів анотації: 29
Завантажень PDF: 32
Опубліковано
2021-02-02