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

Вступление

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

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

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

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

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

Для тестовой модели мы подготовили базу планировок в 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

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