ВВЕДЕНИЕ 4
1. Теоретический обзор темы ВКР 5
1.1. Актуальность выбранной темы 5
1.2. Основные понятия и описание предметной области 7
1.3. Описание бизнес-процесса 14
1.4. Описание отношений сущностей из предметной области
2. Формализованное описание задачи и математическое обоснование предлагаемых алгоритмов 16
2.1. Постановка задачи о расстановке рекламных роликов
2.2. Описание предлагаемых алгоритмов 20
2.2.1. Жадный алгоритм 20
2.3.2. Комбинация жадного алгоритма с методом декомпозиции
2.3.3. Генетический алгоритм 33
3. Программная реализация и тестирование алгоритмов
3.1. Выбор программного обеспечения 42
3.2. Структура базы данных 43
3.3. Диаграмма пакетов 47
3.4. Описание пакета Main 48
3.4. Реализация жадного алгоритма 52
3.5. Реализация жадного алгоритма с методом декомпозиции
3.6. Реализация генетического алгоритма 57
3.7. Сценарий использования разработанного приложения
4. Исследование эффективности работы алгоритмов 62
ЗАКЛЮЧЕНИЕ 70
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 72
Данная выпускная квалификационная работа посвящена применению жадных и генетических алгоритмов в областях рекламного бизнеса, связанных с размещением рекламных сообщений в телевизионном эфире (см. ниже).
В компании BBDOзанимаются размещением рекламных сообщений в различных СМИ, в том числе на телевидении. В этой компании на данный момент применяются два метода размещения рекламных сообщений в эфире. Один из них - ручной подбор выгодных предложений закупщиками на основе их личного опыта и имеющихся аналитических данных, а второй, опирающийся на статистику телеканала, работает как итерационная сортировка, учитывающая ценность различных составляющих расстановки, и их соответствие прописанным базовым ограничениям.
Компания BBDOсоставляет расстановки для закупки как вручную, так и с помощью второго метода, встроенного в специализированное программное обеспечение автоматизации закупок. Используя второй метод, она сталкивается с трудностями, связанными с малыми возможностями адаптации под желания заказчика.
Метод, который сейчас использует компания BBDOдействует следующим образом:
1) Все рекламные блоки сортируются по аффинитивности (см. основные понятия и описание предметной области);
2) С учетом ограничений рекламные ролики назначаются на
рекламные блоки жадным алгоритмом.
Такой алгоритм имеет ряд недостатков:
1) Неравномерность распределения рекламных блоков, т.е. если самые аффинитивные блоки выходят в эфир в один день, то большинство рекламных роликов будет назначено на этот день;
2) Сложность учета ограничений (см. основные понятия и описание предметной области).
Эти проблемы, особенно проблема равномерности, являются причиной поиска новых решений задачи о расстановке роликов.
В данной работе предложены различные подходы к решению задачи размещения рекламы, произведено сравнение равномерностей полученных расстановок, точности учета ограничений, показаний критерия оптимальности (см. ниже) и скорости работы алгоритмов.
В рамках представленной работы формализована предметная область закупок рекламы на телевидении, сформулирована математическая постановка задачи составления оптимальной расстановки рекламных роликов, обоснован выбор жадного и генетического алгоритмов для решения поставленной задачи. Произведена модификация жадного алгоритма посредствам метода декомпозиции. Реализовано программное обеспечение, составляющее расстановку рекламных роликов. Исследована оптимальность полученных решений.
Генетический алгоритм оказался самым сбалансированным, его результат ближе всех к расстановке, полученной вручную. Метод декомпозиции сильно улучшает жадный алгоритм: он дает очень высокие показатели критерия оптимальности, сильный прирост к скорости работы и показывает высокое качество учета ограничений.
Установлено, что подход динамического программирования также подходит для решения поставленной задачи, однако по расчетам он будет работать медленнее, чем жадный алгоритм. Тем не менее при проведении этих расчетов детально не рассматривались способы контроля ограничений с помощью подхода динамического программирования, следовательно, есть вероятность, что подход динамического программирования может показать приемлемое быстродействие. Поэтому в следующих работах по данной проблематике необходимо реализовать подход динамического программирования и проанализировать результаты.
В решении задачи с помощью генетического алгоритма было выделено два подхода к кодированию вектора управляемых параметров для поставленной задачи. В следующих исследованиях необходимо реализовать бинарное кодирование и сравнить результаты двух подходов. Также необходимо исследовать применение различных генетических операторов и различных методов учета ограничений в генетическом алгоритме для данной задачи.
В следующих работах по данной проблеме следует улучшать механизмы учета желаний заказчика, т.к. в реалиях современного рекламного бизнеса их становится больше, следовательно, становится больше ограничений на расстановку различного типа.
Особенностью данной работы является то, что в ней приведено решение реальной задачи рекламного бизнеса, сформулированной по набору нужд рекламного агентства. Представленное программное обеспечение будет использовано как математическое обеспечение системы автоматизированного проектирования расстановок рекламных роликов в медиабаинге.
