На этом шаге мы рассмотрим общий принцип решения этой задачи и приведем решающее ее приложение.
Предположим, что у нас есть некая информация, которую мы хотим сжать. Допустим, что это список предметов и их последовательность неважна, лишь бы все они не были повреждены. При какой последовательности элементов степень сжатия будет максимальной? Известно ли вам вообще, что для большинства алгоритмов сжатия порядок элементов влияет на степень сжатия?
Ответ будет зависеть от используемого алгоритма сжатия. В этом примере применим функцию compress() из модуля zlib со стандартными настройками. Далее показано полное решение для списка из 12 имен. Если не брать генетический алгоритм, а просто запустить compress() для 12 имен в том порядке, в котором они были представлены, то получим сжатые данные объемом 165 байт.
from __future__ import annotations from typing import Tuple, List, Any from chromosome import Chromosome from genetic_algorithm import GeneticAlgorithm from random import shuffle, sample from copy import deepcopy from zlib import compress from sys import getsizeof from pickle import dumps # сжатые данные объемом 165 байт PEOPLE: List[str] = ["Michael", "Sarah", "Joshua", "Narine", "David", "Sajid", "Melanie", "Daniel", "Wei", "Dean", "Brian", "Murat", "Lisa"] class ListCompression(Chromosome): def __init__(self, lst: List[Any]) -> None: self.lst: List[Any] = lst @property def bytes_compressed(self) -> int: return getsizeof(compress(dumps(self.lst))) def fitness(self) -> float: return 1 / self.bytes_compressed @classmethod def random_instance(cls) -> ListCompression: mylst: List[str] = deepcopy(PEOPLE) shuffle(mylst) return ListCompression(mylst) def crossover(self, other: ListCompression) -> Tuple[ListCompression, ListCompression]: child1: ListCompression = deepcopy(self) child2: ListCompression = deepcopy(other) idx1, idx2 = sample(range(len(self.lst)), k=2) l1, l2 = child1.lst[idx1], child2.lst[idx2] child1.lst[child1.lst.index(l2)], child1.lst[idx2] = child1.lst[idx2], l2 child2.lst[child2.lst.index(l1)], child2.lst[idx1] = child2.lst[idx1], l1 return child1, child2 def mutate(self) -> None: # поменять два элемента местами idx1, idx2 = sample(range(len(self.lst)), k=2) self.lst[idx1], self.lst[idx2] = self.lst[idx2], self.lst[idx1] def __str__(self) -> str: return f"Данные: {self.lst} Байты: {self.bytes_compressed}" if __name__ == "__main__": initial_population: List[ListCompression] = \ [ListCompression.random_instance() for _ in range(100)] ga: GeneticAlgorithm[ListCompression] = \ GeneticAlgorithm(initial_population=initial_population, threshold=1.0, max_generations=100, mutation_chance=0.2, crossover_chance=0.7, selection_type=GeneticAlgorithm.SelectionType.TOURNAMENT) result: ListCompression = ga.run() print(result)
Обратите внимание на то, как эта реализация похожа на реализацию из SEND + MORE = MONEY (см. 68 шаг). Функции crossover() и mutate() практически одинаковы. В решениях обеих задач мы берем список элементов, постоянно перестраиваем его и проверяем перестановки. Можно написать общий суперкласс для решения обеих задач, который работал бы с широким спектром задач. Любая задача, если ее можно представить в виде списка элементов, для которого требуется найти оптимальный порядок, может быть решена аналогичным образом. Единственная реальная точка настройки для этих подклассов - соответствующая функция жизнеспособности.
Выполнение этого приложения может занять очень много времени. Так происходит потому, что, в отличие от двух предыдущих задач, мы не знаем заранее, что представляет собой правильный ответ, поэтому у нас нет реального порога, к которому следовало бы стремиться. Вместо этого мы устанавливаем число поколений и число особей в каждом поколении как произвольное большое число и надеемся на лучшее. Каково минимальное количество байтов, которое удастся получить при сжатии в результате перестановки 12 имен? Честно говоря, мы не знаем ответа на этот вопрос. В нашем лучшем случае, используя конфигурацию из предыдущего решения, после 100 поколений генетический алгоритм нашел последовательность из 12 имен, которая дала сжатие размером 122 байтов.
. . . . .
Генерация 95 Лучшая 0.00819672131147541 Среднее 0.008180189515591614
Генерация 96 Лучшая 0.00819672131147541 Среднее 0.008168385245681593
Генерация 97 Лучшая 0.00819672131147541 Среднее 0.008175577949055914
Генерация 98 Лучшая 0.00819672131147541 Среднее 0.008162410390682438
Генерация 99 Лучшая 0.00819672131147541 Среднее 0.008159995142808333
Данные: ['Wei', 'Brian', 'Murat', 'Lisa', 'Dean', 'Joshua', 'Michael', 'Sarah',
'Melanie', 'Narine', 'Daniel', 'Sajid', 'David'] Байты: 122
Всего лишь 43 байта по сравнению с первоначальным порядком - экономия составляет примерно 26%. Можно сказать, что 26% не имеет большого значения, но если бы это был гораздо больший список, который многократно передавался бы по Сети, то экономия выросла бы многократно. Представьте, что бы получилось, если бы это был список размером 1 Мбайт, который передавался бы через Интернет 10 000 000 раз. Если бы генетический алгоритм мог оптимизировать порядок списка для сжатия, чтобы сэкономить 26%, то он сэкономил бы примерно 260 Кбайт на каждую передачу и в итоге 2600 Гбайт пропускной способности для всех передач. Это не очень большая экономия, но она может оказаться значительной настолько, что будет иметь смысл один раз запустить алгоритм и получить почти оптимальный порядок сжатия.
Однако подумайте вот о чем: в действительности неизвестно, нашли ли мы оптимальную последовательность для 12 имен, не говоря уже о гипотетическом списке размером 1 Мбайт. Как об этом узнать? Поскольку мы не обладаем глубоким пониманием алгоритма сжатия, следует проверить степень сжатия для всех возможных последовательностей в списке. Но даже для списка всего лишь из 12 пунктов это трудновыполнимые 479 001 600 возможных вариантов (12!, где знак ! означает факториал). Использование генетического алгоритма, который пытается найти оптимальный вариант, возможно, будет более целесообразным, даже если мы не знаем, является ли его окончательное решение действительно оптимальным.
На следующем шаге мы рассмотрим проблемы генетических алгоритмов.
