РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ВЫБОРА ОПТИМАЛЬНЫХ ПЛАНИРОВОК ЭТАЖА МНОГОКВАРТИРНОГО ДОМА

IMPLEMENTATION OF A GENETIC ALGORITHM FOR SOLVING THE PROBLEM OF SELECTING OPTIMAL FLOOR LAYOUTS OF AN APARTMENT BUILDING

Regina Shayakhmetova

Student, Department of Information Systems, Kazan Federal University

Russia, Kazan

АННОТАЦИЯ

В работе рассмотрена задача выбора оптимальных планировок этажа с использованием генетического алгоритма средствами языка программирования Python.

ABSTRACT

The paper considers the problem of choosing the optimal floor layouts using a genetic algorithm using the Python programming language.

Ключевые слова: оптимальная планировка этажа, генетический алгоритм.

Keywords: optimal floor layout, genetic algorithm.

Введение

Область эволюционных вычислений начала зарождаться ещё в 1950-х годах. Основная её идея заключается в применении теории эволюции Дарвина в компьютерной программе. Эволюция подразумевает под собой улучшение плохого решения случайными мутациями до тех пор, пока задача не будет решена с заданной точностью. Существует частая проблема в задачах информатики – найти один единственный, оптимизированный, идеальный вариант решения задачи в огромном множестве возможных, причём проверить каждый из них не представляется возможным, так как заняло бы очень много времени и ресурсов. И алгоритмы из семейства эволюционных вычислений как раз могут помочь в решении подобных задач.

Концепция эволюционных вычислений включает в себя эволюционные стратегии, эволюционное программирование, генетическое программирование и генетические алгоритмы. Последним будет посвящена данная статья.

Генетические алгоритмы

Традиционный генетический алгоритм был разработан для решения задач, в которых пространство решений настолько велико, что алгоритм «грубой силы», когда мы проверяем каждое возможное решение, занимает слишком много времени. Рассмотрим пример: вам необходимо угадать число от одного до одного миллиарда. Хотя здесь и играет роль удача, при использовании алгоритма «грубой силы» придётся терпеливо ждать годами, пока вы досчитаете до миллиарда и тем самым переберёте все возможные числа. Однако если бы у вас была подсказка, насколько ваш ответ близок к верному, вы бы выбирали другие числа, более близкие к этому ответу, и тем самым смогли бы быстрее получить решение.

Опишем три основных принципа теории эволюции Дарвина, которые потребуются при реализации генетического алгоритма:

• Наследственность. Процесс, с помощью которого дети получают свойства своих родителей. Если существа живут достаточно долго, чтобы размножатся, то их черты передаются их детям в следующем поколении.
• Вариативность. Популяция должна содержать множество признаков и средств, с помощью которых можно будет вносить изменения. Отсутствие разнообразия в популяции приводит к тому, что все дочерние элементы всегда будут идентичны родителям и друг другу. Существа не смогут развиваться, поскольку новые комбинации признаков никогда не смогут возникнуть.
• Выбор. Необходим механизм естественного отбора, когда некоторые члены популяции будут иметь возможность стать родителями и передать свою генетическую информацию, а некоторые – нет. Обычно это называют «выживанием наиболее приспособленных».

Для того, чтобы смоделировать эволюционные процессы используются операторы и стратегии отбора.

Существуют основные виды генетических алгоритмов.

Операторы скрещивания:

• одноточечный кроссовер,

• двухточечный кроссовер,

• равномерный кроссовер.

Операторы мутации:

• одноточечная мутация,

• транслокация,

• инверсия.

Виды отбора особей в генетических алгоритмах:

• пропорциональный,

• рулетка,

• турнирный,

• отбор усечением,

• ранговый,

• элитный.

Прежде чем запустить генетический алгоритм необходимо закодировать признаки (параметры, по которым будет вестись отбор), сформировать из этих параметров фенотип и определить фитнесс-функцию (критерий приспособленности).

Различные виды генетического алгоритма будут отличаться операторами, видами отбора, кроме этого, существуют последовательные и параллельные алгоритмы, но всё они так или иначе будут следующую последовательность этапов:

1. формирование начальной популяции;

2. оценка особей популяции;

3. отбор;

4. скрещивание;

5. мутация;

6. формирование новой популяции;

7. Если популяция не сошлась, возвращаемся на второй этап, прекращение работ генетического алгоритма.

Решение задачи выбора оптимальной планировки этажа многоквартирного дома с помощью генетического алгоритма

Рассмотрим задачу, как оптимальным образом сгенерировать планировку этажа для многоквартирного дома по данным от заказчика. Необходимо выбрать оптимальный вариант количества и вида планировок квартир на этаже.

Целевые задачи две: попасть в процентное соотношение типа планировок и занять максимально точно площадь этажа.

Данные, которые требуются от заказчика, по параметрам этажа:

1. ширина этажа;

2. процентное соотношение квартир на этаже (то есть какой процент от всей площади на этаже занимают студии, однокомнатные, двухкомнатные и трехкомнатные квартиры);

3. количество поколений в генетическом алгоритме для поиска решения.

Данные на вход подаются в виде следующего массива значений, например, [1, 0, 25, 7, 0, 100, 0, 0]. Расшифровать это можно как: [число этажей, угол поворота, ширина этажа, глубина этажа, процент студий, процент однокомнатных квартир, процент двухкомнатных квартир, процент трёхкомнатных квартир].

Структура классов

В генетическом алгоритме рассматривает квартиру как ДНК, состоящую из двух генов:

1.  тип квартиры: торцевая, стандартная;

2. тип планировки: студия, однокомнатная, двухкомнатная, трёхкомнатная.

Структура ДНК этажа:

1. первый ген: ДНК квартиры с фиксированным геном «Тип квартиры» торцевая;

2. со второго по предпоследний ген включительно все квартиры со случайным типом планировки;

3. последний ген: ДНК квартиры также с фиксированным геном «Тип квартиры» торцевая.

Схематично ДНК квартиры и ДНК этажа можно изобразить так:

Рисунок 1. Схематичное изображение структуры ДНК квартир и этажа

Формирование первого поколения для задачи генерации оптимального плана этажа будет производиться следующим образом:

• по умолчанию задаём количество генерируемых планировок и квартир на этаже.
• Заполняем полученное поколение планировок конкретными квартирами из базы данных (первая и последняя квартира являются строго торцевыми).
• Определяем лучшую планировку этажа в поколении. Для каждой планировки определяем три дельты: отклонение от заданного процентного соотношения квартир, отклонение от заданной ширины этажа, сводное отклонение. Затем по наименьшему значению сводного отклонения выбирает лучшую планировку. После чего меняем размера этажа на число квартир в лучшем варианте.
• Передаем ДНК лучшего варианта в первом поколении в следующее поколение.

Все последующие поколения будут генерироваться по следующему принципу:

• На основе полученных вариантов из предыдущего поколения создаем варианты с измененными ДНК квартир. Вероятность мутации 1/20. Мутация затрагивает только тип планировки.
• Добавляем новые планировки, но с уже измененным количеством квартир на этаже.
• Заполняем полученное поколение планировок конкретными квартирами из базы данных.
• Определяем лучшую планировку этажа в поколении, то есть наиболее точную к данным заказчика.
• Передаем ДНК лучшего варианта в первом поколении в следующее поколение.

Результатом работы генетического алгоритма для задачи выбора оптимальной планировки этажа для многоквартирного дома будет итоговое распределение, которое будет состоять из следующих значений: количество (%) разных типов квартир на этаже, отклонение от данных заказчика.

Например, на вход подали массив [1, 0, 40, 10, 50, 30, 20, 0], расшифровка: [число этажей, угол поворота, ширина этажа, глубина этажа, процент студий, процент однокомнатных квартир, процент двухкомнатных квартир, процент трёхкомнатных квартир]. Результатом работы алгоритма при таких параметрах: ['S': 50.0, '1k': 33.333333333333336, '2k': 16.666666666666668, '3k': 0.0], отклонение 6.666666666666668/0/6.666666666666668, итоговая ширина этажа: 40.

Процентное соотношение студий, трёхкомнатных квартир и ширины этажа полностью удовлетворяет требованиям заказчика, а в процентах однокомнатных и двухкомнатных квартир есть небольшие отклонения. Расшифруем полученное отклонение, первое значение – это отклонение от исходных данных по процентам, второе – по площади, третье – сводное (объединённое) отклонение.

Список литературы:

1. Выращиваем ИИ — Генетические алгоритмы: введение: сайт. – URL: https://habr.com/ru/articles/498914/.
2. Сопов, Евгений Вероятностные генетические алгоритмы оптимизации сложных систем: моногр. / Евгений Сопов. - М.: LAP Lambert Academic Publishing, 2012. – 104 с.
3. Кристина, Брестер und Евгений Семенкин Адаптивный генетический алгоритм многокритериальной оптимизации / Кристина Брестер und Евгений Семенкин. - М.: LAP Lambert Academic Publishing, 2013. - 173 c.
4. Гладков Л.А. Генетические алгоритмы / Л.А.Гладков, В.В.Курейчик, В.М.Курейчик. М., 2010.
5. 2. QAI Main Page: Генетические алгоритмы и не только. Qai, 2003-2010. http://qai.narod.ru/.