Как стать автором
Обновить

Генетический алгоритм поиска решения для задачи по выбору планировок этажа многоквартирного дома

Время на прочтение6 мин
Количество просмотров8.5K

Вступление

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

Постановка задачи

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

Исходные данные

База планировок

Для тестовой модели мы подготовили базу планировок в Notion. В дальнейшем к ней легко подключиться по API из Google Colab.

База планировок квартир
База планировок квартир

Данные от Заказчика по параметрам этажа

  1. Ширина этажа

  2. Квартирограмма

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

Методика генетического алгоритма поиска решения

  1. Данные на входе

    1. Массив значений вида: [1, 0, 25000, 7000, 0, 100, 0, 0]

      1. Расшифровка: [Floors, Angle, Floor_width, Floor_deep, Room_S, Room_1k, Room_2k, Room_3k]

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

    1. Опишем квартиру (FLAT_DNA) как ДНК, состоящую из двух генов:

      1. Тип квартиры

        1. Торцевая (E)

        2. Стандарт (S)

      2. Тип планировки

        1. Студия (S)

        2. 1 комнатная (1k)

        3. 2 комнатная (2k)

        4. 3 комнатная (3k)

    2. ДНК этажа (FLOOR) будет иметь такую структуру:

      1. Первый ген = ДНК квартиры с зафиксированным геном “Тип квартиры” = (E)

      2. Со второго до предпоследнего все ДНК квартиры случайные

      3. Последний ген = ДНК квартиры с зафиксированным геном “Тип квартиры” = (E)

  3. Первое поколение (BuildNewGeneration)

    1. По умолчанию для первого поколения мы создаем (GENETIC_FLOOR.NEWBORN) планировок этажей и выбираем размер этажа = 10 квартирам (FLOOR_SIZE)

    2. Заполняем полученное поколение планировок конкретными квартирами из Базы Данных с помощью функции FillFloor

      1. В функции заложено правило, что первая и последняя квартира являются строго типа E, т.е. торцевыми

    3. Определяем лучшую планировку этажа в поколении (FindBestFloor)

      1. Для каждой планировки в поколении определяем 3 дельты:

        1. Отклонение от заданной процентовки квартир (DeltaP)

        2. Отклонение от заданной ширины этажа (DeltaS)

        3. Сводное отклонение (Delta)

        4. Выбираем вариант планировки с наименьшим значением сводного отклонения

        5. Меняем размер этажа на кол-во квартир в лучшем варианте (GENETIC_FLOOR.FLOOR_SIZE)

    4. Передаем ДНК лучшего варианта в первом поколении в следующее поколение

  4. Последующие поколения

    1. На основе полученных вариантов из предыдущего поколения создаем GENETIC_FLOOR.MUTATED вариантов с измененными ДНК квартир

      1. Вероятность мутации 1/20

      2. Мутация затрагивает только тип планировки

    2. Добавляем новые планировки, но с уже измененным количеством квартир на этажа (GENETIC_FLOOR.FLOOR_SIZE)

    3. Заполняем полученное поколение планировок конкретными квартирами из Базы Данных с помощью функции FillFloor

    4. Определяем лучшую планировку этажа в поколении (FindBestFloor)

    5. Передаем ДНК лучшего варианта в первом поколении в следующее поколение

Структура ДНК квартир и этажа
Структура ДНК квартир и этажа

Исходный код на Python

import random 
import copy
import pprint
from PIL import Image as IMG, ImageDraw, ImageFilter
import requests

class FLAT_DNA():
    
    Gens = {
        # Тип квартиры
        # E - Торцевая квартира, S - Стандартная квартира
        'Type': [['E', 'S'], 0.5], 

        # Планировка
        # S - Студия, 1k - 1 комнатная, 2k - 2 комнатная, 3k - 3 комнатная
        'Layout': [['S', '1k', '2k', '3k'], 0.5],
    }
    
    def __init__(self, DNA = None):

        self.DNA = {
            'Type' : random.choice(FLAT_DNA.Gens['Type'][0]),
            'Layout' : random.choice(FLAT_DNA.Gens['Layout'][0])
        }
        
        if DNA is not None:
            for i in DNA.keys():
              self.DNA[i] = DNA[i]
        
    def __repr__(self):
        return str(self.DNA)

class FLOOR():

  def __init__(self, N):
    self.N = N
    self.Plan = []
    for i in range(N):
      self.Plan.append([FLAT_DNA({'Type' : 'S'}), []])
    self.Plan[0][0].DNA['Type'] = 'E'
    self.Plan[-1][0].DNA['Type'] = 'E'

  # Функция наполнения ДНК этажа конкретными вариантами кварти из БД (случайным перебором)
  def FillFloor(self):
    for i in range(len(self.Plan)):
      if self.Plan[i][0].DNA['Type'] == 'E':
        flat = random.choice(DB_FlatType_Dict['Торцевая'])
        self.Plan[i][1].append(flat)
        #print(flat)
      if self.Plan[i][0].DNA['Type'] == 'S':
        flat = random.choice(DB_FlatType_Dict['Рядовая'])
        self.Plan[i][1].append(flat)
        #print(flat)
  
  # Функция определения фактической геометрии этажа и площади
  def FloorSquare(self):
    self.Width = 0
    self.Deep = 0
    for i in range(len(self.Plan)):
      self.Width += self.Plan[i][1][0]['properties']['Ширина']['number']
      self.Deep += self.Plan[i][1][0]['properties']['Глубина']['number']
    self.Square = self.Width * self.Deep

  # Функция генерации словаря с процентовкой квартир на этаже
  def FloorPercent(self):
    self.FloorPercent_Dict = {}
    for g in FLAT_DNA.Gens['Layout'][0]:
      if g not in self.FloorPercent_Dict.keys():
        self.FloorPercent_Dict[g] = 0
      for i in range(len(self.Plan)):
        if self.Plan[i][0].DNA['Layout'] == g:
          self.FloorPercent_Dict[g] += 1      
    for i in self.FloorPercent_Dict.keys():
      self.FloorPercent_Dict[i] = self.FloorPercent_Dict[i]*100/self.N

  def GetPNG(self):
    floor_img = IMG.new('RGB', (6000, 3000), color = 'white')
    W = 0
    for i in range(len(self.Plan)):
      url = self.Plan[i][1][0]['properties']['Foto']['files'][0]['file']['url']
      im = IMG.open(requests.get(url, stream=True).raw)
      floor_img.paste(im, (int(W/10), 0))
      W += self.Plan[i][1][0]['properties']['Ширина']['number']
    floor_img.save(f'./floor_img.png')


class GENETIC_FLOOR():

  FLOOR_SIZE = 10
  NEWBORN = 20
  MUTATED = 100
  SURVIVERS = 1

  # [Floors, Angle, Floor_width, Floor_deep, Room_S, Room_1k, Room_2k, Room_3k]
  def __init__(self, data):
    self.data = data
    self.Generation = {}

  def RunGenerations(self, N):
    for i in range(N):
      #print(f'--- Поколение №{(i+1)} ---')
      if hasattr(self, 'BestFloor'):
        # Создаем поколение и передаем в него лучший вариант из предыдущего поколения
        self.BuildNewGeneration([self.BestFloor[0]])
      else:
        # Создаем первое поколение
        self.BuildNewGeneration()
      # Определяем лучшый вариант в текущем поколении
      self.FindBestFloor(GENETIC_FLOOR.SURVIVERS)
      #print(f'Первый вариант в поколении: {self.Generation[0].Width}')
      #print(f'Ко-во вариантов в поколении: {len(self.Generation)}')
    print(f'Итоговое распределение квартир: {self.BestFloor[0].FloorPercent_Dict}, отклонения: {self.BestDeltaP}/{self.BestDeltaS}/{self.BestDelta}, ширина: {self.BestFloor[0].Width}')
      #print(f'Квартир на этаже: {self.BestFloor[0].N}')
  
  def BuildNewGeneration(self, Survivers_array=[]):
    NewGeneration = {}
    self.Generation = {}
    index = 0

    # Добавляем лучшие этажи из предыдущего поколения к новому поколению
    for i in Survivers_array:
        NewGeneration[index] = copy.deepcopy(i)
        index += 1

    # Меняем планировки в лучших вариантах из предыдущего поколения
    for i in Survivers_array:
      for k in range(GENETIC_FLOOR.MUTATED):
        for p in range(len(i.Plan)):
          if i.Plan[p][0].DNA['Type'] == 'E':
            if random.randint(1, 20) == 5:
              flat = random.choice(DB_FlatType_Dict['Торцевая'])
              i.Plan[p][1][0] = flat
              #print(f'Мутация торцевой квартиры')
          if i.Plan[p][0].DNA['Type'] == 'S':
            if random.randint(1, 20) == 5:
              flat = random.choice(DB_FlatType_Dict['Рядовая'])
              i.Plan[p][1][0] = flat
              #print(f'Мутация радовой квартиры')
        NewGeneration[index] = i
        index += 1

    # Добавляем новых вариантов к новому поколению
    for i in range(GENETIC_FLOOR.NEWBORN):
      N_new = GENETIC_FLOOR.FLOOR_SIZE + random.randint(-3, 4)
      if N_new<=0:
        N_new = 1
      floor1 = FLOOR(N_new)
      floor1.FillFloor()
      NewGeneration[index] = floor1
      index += 1

    self.Generation = copy.deepcopy(NewGeneration)

  def FindBestFloor(self, N=1):
    DeltaP = 1000000 # Отклонение по процентам
    DeltaS = 1000000 # Отклонение по площади
    Delta = 1000000 # Отклонение сводное
    #Delta_array = []
    BestFloor = []
    for i in self.Generation.keys():
      g = self.Generation[i]
      # Определили процентовку
      g.FloorPercent()
      # Определили геометрию
      g.FloorSquare()
      # Считаем отклонения от заданной процентовки
      DeltaP_tmp = self.CampareFloorPercent({'S': self.data[4], '1k': self.data[5], '2k': self.data[6], '3k': self.data[7]}, g.FloorPercent_Dict)
      # Считаем отклонение от Ширины этажа
      DeltaS_tmp = abs(g.Width - self.data[2])
      # Выводим сводное отклонение
      Delta_tmp = DeltaP_tmp + DeltaS_tmp / 1500
      if Delta_tmp < Delta:
        BestFloor.insert(0, g)
        DeltaP = DeltaP_tmp
        DeltaS = DeltaS_tmp
        Delta = Delta_tmp
        #Delta_array.append(Delta_tmp)
    self.BestFloor = BestFloor
    self.BestDelta = Delta
    self.BestDeltaP = DeltaP
    self.BestDeltaS = DeltaS
    GENETIC_FLOOR.FLOOR_SIZE = self.BestFloor[0].N


  def CampareFloorPercent(self, d1, d2):
    Delta = 0
    for i in d1.keys():
      Delta += abs(d1[i] - d2[i])
    return Delta

Результат работы алгоритма

Исходные данные: [1, 0, 60000, 10000, 10, 60, 30, 0]
Идет рассчет...
Итоговое распределение квартир: {'S': 12.5, '1k': 62.5, '2k': 25.0, '3k': 0.0}, отклонения: 10.0/5350/13.566666666666666, ширина: 54650
Итоговая длина этажа: 54650
Исходные данные: [1, 0, 60000, 10000, 10, 60, 30, 0]
Идет рассчет...
Итоговое распределение квартир: {'S': 12.5, '1k': 62.5, '2k': 25.0, '3k': 0.0}, отклонения: 10.0/800/10.533333333333333, ширина: 59200
Итоговая длина этажа: 59200
Исходные данные: [1, 0, 60000, 10000, 10, 60, 30, 0]
Идет рассчет...
Итоговое распределение квартир: {'S': 7.142857142857143, '1k': 57.142857142857146, '2k': 28.571428571428573, '3k': 7.142857142857143}, отклонения: 14.285714285714281/3000/16.28571428571428, ширина: 63000
Итоговая длина этажа: 63000
Исходные данные: [1, 0, 60000, 10000, 10, 60, 30, 0]
Идет рассчет...
Итоговое распределение квартир: {'S': 9.090909090909092, '1k': 63.63636363636363, '2k': 27.272727272727273, '3k': 0.0}, отклонения: 7.272727272727268/50/7.306060606060601, ширина: 60050
Итоговая длина этажа: 60050
Исходные данные: [1, 0, 60000, 10000, 10, 60, 30, 0]
Идет рассчет...
Итоговое распределение квартир: {'S': 10.0, '1k': 60.0, '2k': 30.0, '3k': 0.0}, отклонения: 0.0/850/0.5666666666666667, ширина: 60850
Итоговая длина этажа: 60850
Выбранные планировки, удовлетворяющие поставленной Заказчиком задаче
Выбранные планировки, удовлетворяющие поставленной Заказчиком задаче

Пример работы алгоритма

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
А у Вас есть опыт применения генетических алгоритмов?
40% Да26
60% Нет39
Проголосовали 65 пользователей. Воздержался 21 пользователь.
Теги:
Хабы:
Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку
Всего голосов 10: ↑9 и ↓1+8
Комментарии33

Публикации

Истории

Работа

Data Scientist
52 вакансии

Ближайшие события

19 марта – 28 апреля
Экспедиция «Рэйдикс»
Нижний НовгородЕкатеринбургНовосибирскВладивостокИжевскКазаньТюменьУфаИркутскЧелябинскСамараХабаровскКрасноярскОмск
22 апреля
VK Видео Meetup 2025
МоскваОнлайн
23 апреля
Meetup DevOps 43Tech
Санкт-ПетербургОнлайн
24 апреля
VK Go Meetup 2025
Санкт-ПетербургОнлайн
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань
14 мая
LinkMeetup
Москва
5 июня
Конференция TechRec AI&HR 2025
МоскваОнлайн
20 – 22 июня
Летняя айти-тусовка Summer Merge
Ульяновская область