ИТОГОВЫЙ ИНДИВИДУАЛЬНЫЙ ПРОЕКТ. Создание фонов с помощью генетического алгоритма

Муниципальное бюджетное общеобразовательное учреждение

«Гимназия № 44» г. Курска

ИТОГОВЫЙ ИНДИВИДУАЛЬНЫЙ ПРОЕКТ

Создание фонов с помощью генетического алгоритма

Автор: Казанцев Илья,

9Б класс

Учитель: Плешевцева М.В.,

учитель информатики

Курск- 2023

ОГЛАВЛЕНИЕ

I. ВВЕДЕНИЕ

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

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

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

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

Задачи:

1. Изучить историю создания и развития генетических алгоритмов
2. Исследовать конструкцию и возможности генетических алгоритмов
3. Интерпретировать оригинальную конструкцию для первичных тестов
4. Написать программу, которая будет последовательно создавать изображения, понравившееся пользователю
5. Провести тесты насколько программа может удовлетворить запросы пользователей

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

        Методы: анализ и восхождения от абстрактного к конкретному.

II. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

2.1. История создания

История генетических алгоритмов началась в середине 20 века со становлением теории эволюции. Один из основоположников генетических алгоритмов — американский математик Джон Холланд, который в 1975 году опубликовал исследование "Адаптивные системы программирования: генетические алгоритмы и их применение".

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

С того времени генетические алгоритмы широко используются в различных областях, таких как промышленность, бизнес, науку, медицину, инженерию и др. Они применяются, например, для оптимизации производственных процессов, поиска оптимальных параметров в задачах оптимизации, дизайна и создания сложных систем, предсказания рыночных тенденций и многих других задач.

Большой вклад в научное исследование генетических алгоритмов внесли Уоллис-Джонсон, Фогель, Рой и другие ученые, оттачивая методику и создавая различные модификации алгоритмов. В настоящее время генетические алгоритмы стали одним из самых популярных методов оптимизации и решения трудных задач, благодаря своей эффективности, универсальности и широкому спектру практических применений.

III. ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1. Исследование строения и возможностей генетических алгоритмов.

        Генетические алгоритмы распространены как методы оптимизации и приближения к конечному результату. Они способны почти со стопроцентной точностью приближаться к искомому результату, что хорошо сказывается при создании фонов, ведь вкусы людей субъективны и невероятная точность не требуется.

        Строение генеративного алгоритма:

1. Первой создаётся так называемая функция приспособленности или же fitness function. Она вычисляет приспособленность каждого индивида из поколения
2. Создаётся первое поколение
3. Создаётся функция отбора. Она может работать по разным принципам, но чаще всего используется принцип рулетки. Чем больше значение функции приспособленности, тем больше шанс выбора.
4. Создаётся функция скрещивания для получения новых индивидов, также применяется принцип мутации для увеличения разнообразия поколения
5. Индивиды с наименьшим значением функции приспособленности заменяются новыми
6. Если выходной результат получен, то цикл завершается, иначе цикл повторяется с 3 пункта

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

        3.2. Создание программы для нахождения похожего изображения

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

        На первых строках определяются основные функции для вычисления "фитнеса" (функции приспособленности) для каждой отдельной строки, для кроссовера, мутации и выбора лучших пространств состояний.

        На следующих строках заполняется начальная популяция строк, случайным образом их генерируя. После этого определяется функция, которая выбирает определенное количество процентов наиболее приспособленных строк из текущей популяции и создает из них новые поколения с помощью определенных алгоритмов кроссовера и мутации. После создания новых поколений, дети проверяются напригодность для следующего поколения и лучшие результаты сохраняются. Цикл повторяется до тех пор, пока не будет найдено наилучшее решение, то есть, пока на первом месте массива найденного поколения не будет заданной строки 'final'.

        Можно изменить параметры в коде: перечень символов (letters), начальное количество популяций строк (генерация), процент для создания новых поколений (percentage_of_children) и другие параметры, чтобы улучшить результаты.

        Алгоритм хорошо справлялся и после 200 поколений уже был прогресс, но после до 2000 поколения изменений не наблюдалось. Алгоритм лишь мог постоянно приближаться к искомому результату, но не достигал его. Это показало его возможности и подтвердило то, что данный алгоритм подходит для решения поставленной задачи.

        3.3. Создание программы для генерации картинок

        Рассмотрим пример использования ГА для создания изображения. Пусть каждый пиксель картинки будет задан тремя значениями R, G, B (красный, зеленый, синий) в диапазоне от 0 до 255. Начальная популяция будет состоять из случайных значений R, G, B для каждого пикселя. Фитнес-функцией будет сам выбор пользователя. Цель ГА - минимизировать значение фитнес-функции, чтобы создать наиболее похожее на желаемое изображение.

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

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

        В конце цикла изображение с наименьшей приспособленностью заменяется на только что сгенерированное.

        Ниже представлен пример работы алгоритма после 15 итераций.

Рис. 1

Рис. 2

Вывод: Программа показала хороший результат уже на 15-ой итерации, скорость создания одной картинки равна одной секунде. Как пользователь могу сказать, что программа удовлетворила запросы.

Рис. 3

        Выше представлены некоторые лучшие экземпляры, полученные в результате испытаний.

IV. ЗАКЛЮЧЕНИЕ 

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

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

Плюсы генетических алгоритмов:

1. Генетические алгоритмы могут решать сложные задачи оптимизации, которые не могут быть решены другими методами.
2. Генетические алгоритмы основаны на эволюционных процессах, что делает их гибкими и адаптивными к изменяющимся условиям.
3. Генетические алгоритмы могут использоваться для решения разнообразных задач, таких как оптимизация, прогнозирование, кластеризация, аппроксимация и т.д.
4. Генетические алгоритмы могут работать с большими объемами данных и сложными системами.
5. Генетические алгоритмы являются параллельными, что позволяет быстро решать задачи на многопроцессорных системах.

Минусы генетических алгоритмов:

1. Генетические алгоритмы могут потребовать большое количество вычислений, что занимает много времени и требует больших вычислительных мощностей.
2. Генетические алгоритмы могут давать только приближенный ответ на поставленную задачу.
3. Генетические алгоритмы могут попадать в локальный экстремум, что может снизить точность решения.
4. Генетические алгоритмы могут оказаться неработоспособными при недостаточном количестве данных или при некоторых ограничениях в задаче оптимизации.

V. СПИСОК ИСПОЬЗУЕМЫХ ИСТОЧНИКОВ 

1. https://ru.wikipedia.org/wiki/Генетический_алгоритм
2. https://habr.com/ru/post/128704/
3. https://cybernetics.fandom.com/ru/wiki/Генетический_алгоритм

VI. ПРИЛОЖЕНИЯ

Приложение 1

import math
import operator
import random
import parser
import cv2_rgb as cv2
import numpy as np


r = 0
g = 0
b = 0
x = 0
y = 0


elements = ["x", "y"]
operations = [[math.cos, math.sin, abs, math.acos, math.asin, math.pow], [operator.add, operator.sub, operator.mul]]
blank_image = np.zeros((500, 750, 3), dtype=np.uint8)
pics = []
fitness_array =[0 for i in range(6)]

def random_function_string(node, depth):
   if depth == 0:
       if node not in elements:
           return random.choice(elements)
       return node
   elif node in elements:
       return node
   elif node in operations[0]:
       if random.randint(0, 1) == 0 and depth < 4:
           child = random_function_string(random.choice(elements), depth - 1)
           if "cos" in str(node):
               return f"math.cos({child})"
           elif "sin" in str(node):
               return f"math.sin({child})"
           elif "abs" in str(node):
               return f"abs({child})"
           elif "acos" in str(node):
               return f"math.acos({child})"
           elif "asin" in str(node):
               return f"math.asin({child})"
           elif "pow" in str(node):
               return f"math.pow({child}, {random.randint(2, 5)})"
       else:
           child = random_function_string(random.choice(random.choice(operations)), depth - 1)
           if "cos" in str(node):
               return f"math.cos({child})"
           elif "sin" in str(node):
               return f"math.sin({child})"
           elif "abs" in str(node):
               return f"abs({child})"
           elif "acos" in str(node):
               return f"math.acos({child})"
           elif "asin" in str(node):
               return f"math.asin({child})"
           elif "pow" in str(node):
               return f"math.pow({child}, {random.randint(2, 5)})"
   else:
       if random.randint(0, 1) == 0 and depth < 4:
           left_child = random_function_string(random.choice(elements), depth - 1)
       else:
           left_child = random_function_string(random.choice(random.choice(operations)), depth - 1)
       if random.randint(0, 1) == 0 and depth < 4:
           right_child = random_function_string(random.choice(elements), depth - 1)
       else:
           right_child = random_function_string(random.choice(random.choice(operations)), depth - 1)
       if "add" in str(node):
           return f"({left_child} + {right_child})"
       elif "sub" in str(node):
           return f"({left_child} - {right_child})"
       elif "mul" in str(node):
           return f"({left_child} * {right_child})"


def make_functions():
   global r, g, b

   r_str = random_function_string(random.choice(random.choice(operations)), 3)
   r = parser.expr(r_str).compile()

   g_str = random_function_string(random.choice(random.choice(operations)), 3)
   g = parser.expr(g_str).compile()

   b_str = random_function_string(random.choice(random.choice(operations)), 3)
   b = parser.expr(b_str).compile()
   return (r_str, g_str, b_str)


def value_of_function_in_string(_x: int, _y: int):
   global x, y
   x = _x
   y = _y
   print(x, y)
   return (int(abs(eval(r)) * 100) % 255 + 1, int(abs(eval(g)) * 100) % 255 + 1, int(abs(eval(b)) * 100) % 255 + 1)



def print_image(x_start, y_start, x_end, y_end):
   global blank_image
   result = [make_functions(), [x_start, y_start, x_end, y_end]]
   for i in range(y_start, y_end):
       for j in range(x_start, x_end):
           blank_image[i][j] = value_of_function_in_string(i + 1, j + 1)
   return result




def fitness():
   global pics, fitness_array
   print('Введите последовательность картинок от наименее понравившихся к наиболее  понравившемся')
   array = list(map(int, input().split()))
   for i in range(6):
       fitness_array[array[i]-1] += (len(pics)-i-1) * 1000
   return fitness_array


def crossover_and_mutation(parent1, parent2):
   rs = [parent1[0], parent2[0]]
   gs = [parent1[1], parent2[1]]
   bs = [parent1[2], parent2[2]]
   r = random.choice(rs)
   g = random.choice(gs)
   b = random.choice(bs)

   if random.randint(0, 1) == 1:
       choice = random.randint(1, 3)

       if choice == 1:
           child = str(random.choice(operations[0])).split()[-1][:-1]
           if "cos" in str(r):
               r = r.replace('cos', child)
               return (r, g, b)
           elif "sin" in str(r):
               r = r.replace('sin', child)
               return r, g, b
           elif "abs" in str(r):
               r = r.replace('abs', child)
               return r, g, b
           elif "acos" in str(r):
               r = r.replace('acos', child)
               return r, g, b
           elif "asin" in str(r):
               r = r.replace('asin', child)
               return r, g, b

       elif choice == 2:
           child = str(random.choice(operations[0])).split()[-1][:-1]
           if "cos" in str(g):
               g = g.replace('cos', child)
               return r, g, b
           elif "sin" in str(g):
               g = g.replace('sin', child)
               return r, g, b
           elif "abs" in str(g):
               g = g.replace('abs', child)
               return r, g, b
           elif "acos" in str(g):
               g = g.replace('acos', child)
               return r, g, b
           elif "asin" in str(g):
               g = g.replace('asin', child)
               return r, g, b
       else:
           child = str(random.choice(operations[0])).split()[-1][:-1]
           if "cos" in str(b):
               b = b.replace('cos', child)
               return (r, g, b)
           elif "sin" in str(b):
               b = b.replace('sin', child)
               return r, g, b
           elif "abs" in str(b):
               b = b.replace('abs', child)
               return r, g, b
           elif "acos" in str(b):
               b = b.replace('acos', child)
               return r, g, b
           elif "asin" in str(b):
               b = b.replace('asin', child)
               return r, g, b

   return r, g, b






def selection():
   _fitness_array = fitness_array.copy()
   summa = sum(_fitness_array)
   probability = [i / summa for i in _fitness_array]
   parent1 = np.random.choice(len(_fitness_array), p=probability)
   summa -= _fitness_array[parent1]
   _fitness_array.pop(parent1)
   probability = [i / summa for i in _fitness_array]
   parent2 = np.random.choice(len(_fitness_array), p=probability)
   return crossover_and_mutation(pics[parent1][0], pics[parent2][0])


for i in range(2):
   for j in range(3):
       new_pic = print_image(j * 250, i * 250, j * 250 + 250, i * 250 + 250)
       pics.append(new_pic)


cv2.namedWindow("MyWindow", cv2.WINDOW_NORMAL)
cv2.imshow("MyWindow", blank_image)
cv2.waitKey(5000)


for _ in range(100):
   fitness()
   compose = zip(pics, fitness_array)
   compose = sorted(compose, key=lambda tup: tup[1], reverse=True)
   for i in range(len(compose)):
       pics[i] = compose[i][0]
   pics[0][0] = selection()
   print_image(pics[0][1][0], pics[0][1][1], pics[0][1][2], pics[0][1][3])
   cv2.imshow("MyWindow", blank_image)
   cv2.waitKey(5000)

cv2.destroyAllWindows()