Проекты

Решение задачи Хейльбронна для треугольников в пространстве и плоскости через задачу глобальной оптимизации с использованием генетических алгоритмов

Работа призёра открытой городской научно-практической конференции «Курчатовский проект – от знаний к практике, от практики к результату» в секции «Идея»

Направление работы: Программирование
Авторы работы: ГБОУ Школа № 1532
Предметы: Биология, Информатика
Классы: 11 класс
Мероприятия: Открытая городская научно-практическая конференция «Курчатовский проект – от знаний к практике, от практики к результату» 2021 года

Актуальность

Проблема треугольников Хейльбронна (Heilbronn triangle problem) в дискретной теории геометрии является проблемой размещения точек в плоскости и пространстве по поиску такого расположения точек в квадрате, чтобы площадь минимального треугольника была максимальной среди всех расположений точек. Данная задача является нерешенной на данный момент; нам известны лишь верхние границы возможных решений, но методики, использованные для решения, могут помочь нам в исследовании генетического алгоритма, который позволяет осуществлять поиск оптимальных решений множества практических задач.

Цель

Найти эффективное решение проблемы треугольников Хейльбронна (Heilbronn triangle problem), а также исследовать работу генетического алгоритма с целью создания авторских модификаций, которые позволят увеличить эффективность самого алгоритма.

Задачи

  1. Реализовать стандартный генетический алгоритм на языке C++.
  2. Адаптировать стандартный генетический алгоритм под решение проблемы треугольников Хейльбронна (Heilbronn triangle problem).
  3. Получить решение данной задачи.
  4. Предложить авторские модификации, которые повышают эффективность решения данной задачи.
  5. Исследовать модификации и различные настройки генетического алгоритма, которые повышают эффективность решения данной задачи.

Оснащение и оборудование, использованное при создании работы

  • Язык программирования C++
  • Компьютер
  • Среда программирования CodeBlocks

Описание

Треугольники Хейльбронна

Работа была полностью выполнена на компьютере. Программа была написана на языке C++ в среде программирования CodeBlocks. Для решения поставленной задачи первоначально использовался стандартный генетический алгоритм, основанный на простейшем генетическом алгоритме Джона Холланда. На первом этапе производилась генерация первой популяции. Для решения проблемы треугольников Хейльбронна (Heilbronn triangle problem) требуется разместить в плоскости или пространстве точки, имеющие вещественные координаты, но стандартный генетический алгоритм работает с бинарными строками, вследствие чего были использованы специальные формулы, с помощью которых можно было переводить вещественные числа в двоичный вид и наоборот. На втором этапе была произведена запись полученной популяции в массив. На третьем этапе производился отбор родительских индивидов, они заложат основу для индивида-ребенка, который уже пойдет в популяцию следующего поколения. На четвертом этапе родительские особи, выбранные на этапе селекции, скрещиваются. На этапе мутации алгоритм изменяет случайное число в бинарной строке (индивиде) с некоторой вероятностью, которая была обозначена перед запуском алгоритма. Шестой этап – один из самых важных этапов, на котором производится проверка пригодности популяции. Получив нужные результаты из предыдущего этапа, алгоритм записывает его в удобный нам вид, параметры которого индивидуальны под нужды человека, использующего алгоритм, а также заданы до запуска.

Результаты работы/выводы

В результате стандартный генетический алгоритм работает, и для его проверки был написан алгоритм, основанный на методе Монте-Карло, который позволит нам понять, эффективнее ли алгоритм случайного перебора и работает ли он корректно.

В работе автор предложил решение задачи Хейльбронна для треугольников с помощью генетического алгоритма, а также двух модификаций, которые показали свою эффективность по разным параметрам работы. Также была заложена основа для дальнейшего изучения симбиотических генетических алгоритмов.