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

Вступление

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

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

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

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

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

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

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