Data Clustering using Genetic Algorithm. Zheyung Feng.
Работа написана в 2012 и обладает максимально возможной , полнотой описания операторов
генетического алгоритма и их воздействие на производительность и определение глобального
минимума. Показывается добавление шагов k-mean к каждой итерации генетического алгоритма,
что приводит к заметному уменьшению шагов решения. Так же определено, что предварительная
сортировка данных приводит к увеличению вероятности нахождения локального минимума, но
операторы генетического алгоритма могут быть подобраны так, что исправляют эту возможную
ситуацию. Так же затронут вопрос неевклидовых кластеров вытянутой или серповидной формы, за
их нахождение отвечают операторы селекции, объединяющие и удаляющие кластера. Статья
является наглядным пособием по созданию инструментов классификации на основе GA.
Implementation and Analysis of Graph Algorithm Used for Software Plagiatism Identification. Dr. Carlos Rivero
То , что среди статей об классификации данных освещаю и статьи по поиску плагиата в
программах, говорит о моей цели объединить два механизма определения схожести.
Классификатор и анализ изоморфизма связаны между собой в том , что классификация кода не
может быть представлена евклидовом пространством, вместо этого определением разницы в коде
может заниматься изоморфный анализ графов активности, полученных ANTLR.
В статье не только рассматривается способ сохранения AST , в базе данных графов Neo4j , но и
алгоритм нахождения подобных поддеревьев в полученной базе данных. К сожалению, средства
нахождения изоморфизма в работе не указан, но они ссылаются на GraphQL и Nema.
Parallel programing with Inductive Synthesis. Shaon Barman, Rastislav Bodik, Sagar Jain, Yewen Pu, Saurabh Srivastava, and Nicholas Tung.
Эта работа может показаться сугубо математической, так как в ней обсуждается нахождение
коэффициентов факторизованного представления полинома, но в целом она рассказывает более
общий принцип адаптации выбранного алгоритма к необходимому математическому решению с
помощью gpu. Если представить, что генетический алгоритм действительно найдет подходящий
для решения проблем программный код, то параметры взаимодействия с этим кодом, как и
внутренние коэффициенты нужно будет вычислить. При этом можно применять индуктивный
подход. Такая операция перебора и определения коэффициентов возможна с помощью gpu.
Abstract Syntax Tree Generation using Modified Grammar for Source Code Plagiatism Detection. Resmi N. G. Soman K. P.
В статье от Resmi и Soman обсуждается каким образом пробовать делать грамматику для ANTLR ,
инвариантной к стилю написания кода. Затрагивается проблема вариаций в синтаксисе и
адаптация к комментариям и другим не связанным с синтаксисом элементам. Но к сожалению , не
решена инвариантность синтаксического сахара. Метод фильтрации кода на уровне грамматики ,
в принципе можно использовать как базовый при внесении AST в базу данных ArangoDB, но
парсинг полноценной грамматики и вычисление разницы между графами может пополнить
метаданные вершин графа, оставленными автором комментариями.
Genetic Algorithm for Clustering with an Ordered Representation. Jay Bhuyan
Работа представлена в 1991 году и отражает использование генетического алгоритма в
кластеризации данных, как нового метода, позволяющего обходить локальные минимумы в
решении. В примере рассматривается евклидово пространство и два вида жадных алгоритмов.
Алгоритм называется жадным , если он принимает во внимание оптимальное решение на каждом
шаге алгоритма.
Если данные заранее отсортированы , с применением эвристического сравнения данных между
собой, то генетический алгоритм получает схожесть.
Автор показывает , что применение эвристических правил в генетическом алгоритме позволяет
балансировать между производительностью и точностью. Также в эвристике автор предлагает
использовать противоположные суждения, для того чтобы найти глобальный оптимум. И главной
идеей является утверждение в том , что подготовленные данные лучше поддаются
классификации, и в этом могут помочь сортировки больших данных, которые я описал в блоге .
