Искусство в IT-технологиях...

Тавридович Станислав Александрович. Оптимизация WEB-сайта интернет-магазина с использованием генетического алгоритма, 2004

3.3.4. Выбор метода решения задачи

На данном этапе необходимо выбрать метод решения поставленной оптимизационной задачи.
Задача имеет нелинейную целевую функцию, которая вычисляется на основании решения оценочной задачи - задачи моделирования сессий пользователей (см.
гл. 3.2.5). Система ограничений состоит из линейных равенств и неравенств. Все искомые переменные (параметры решения задачи) могут принимать булевские значения: 0 или L По системе классификации, рассмотренной в [4, сс. 13-15], данную задачу можно отнести к классу оптимизационных задач нелинейного программирования с булевыми переменными или к более широкому классу задач дискретной оптимизации.
С давних пор известны два основных пути решения оптимизационных задач: переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать1.
Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функ-



При написании разделов 3.3.4 и 3.3.5 использовалась статья «Генетические алгоритмы», находящаяся по адресу http:s/msLnestor.mimkby/kg/1999/kg99Q7/kg92R09Juml.
ции во всех возможных точках (при всех возможных значениях параметров), запоминая максимальное их них. Недостатком этого метода является большая вычислительная стоимость. Она увеличивается с ростом числа параметров задачи и диапазона их возможных значений. Однако, если число вариантов конечно1 и перебор всех вариантов за разумное время возможен, то можно быть уверенным в том, что найденное решение действительно оптимально.
При использовании локально-градиентного метода вначале выбирают некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности принимаемого решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный).
Посмотрим, насколько применимы описанные выше методы при решении задачи оптимизации сети Интернет-проекта [21, с. 30 или 32, сс. 136-137].
Эффективность применения переборного метода зависит главным образом от общего числа вариантов, которые следует рассмотреть. В тестовой задаче, приведенной в гл. 3.3.2, необходимо найти оптимальный набор из 46 параметров, каждый из которых может принимать одно из двух значений.
Таким образом, всего необходимо перебрать 2 «710' вариантов.
Даже если мы будем рассматривать миллион вариантов в секунду (что уже нереально), нам понадобится более 800 суток непрерывных вычислений.






Задача оптимизации сети Интернет-проекта (как и любая задача дискретной оптимизации) имеет конечное число вариантов решения [см. 4, сс. 13-15].
На самом деле, количество перебираемых вариантов можно сократить, если рассматривать только допустимые варианты . Количество допустимых вариантов значительно меньше. Например, в тестовой задаче на Web-страницах «Кофе» и «Чай» не нужно рассматривать все 210 - 1024 наборов параметров. Дело в том, что на каждой из подстраниц этих Web-страниц в соответствии с ограничениями на их объем может находиться по пять блоков с информацией о товарах. Следовательно, положение любых пяти блоков однозначно задает положение остальных, и для каждой Web-страницы необходимо рассмотреть только 25 = 32 варианта. На Web-странице «Главная страница» может находиться не более пяти информационных блоков. Следовательно, число вариантов сокращается с 216 = 65536 до суммы сочетаний из 16 блоков по 5, 4, 3, 2 и 1 блоку
5 5 \?А
YCH=Y——— = 16+120 + 560 + 1820+4368 = 6884. Общее число вариантов ГГ ^г!(!6-г)!
сокращается до 32 • 32 • 6884 * 7 • 106.
Однако в отличие от гипотетического Интернет-магазина из тестовой задачи, предлагающего пользователям всего 15 наименований товаров, реальные Интернет-магазины предлагают сотни и тысячи наименований товаров.
Следовательно, количество параметров для оптимизации в реальных задачах будет значительно больше, увеличится число вариантов и оптимизация перебором даже только допустимых вариантов станет нереальной.
Другой метод оптимизации - локально-градиентный эффективен при решении унимодальных задач. Как показывают практические вычисления, задача оптимизации сети Интернет-проекта мультилюдальна - она может иметь множество локальных оптимумов. Значит, и локально-градиентный метод не будет эффективным.
Выходом из создавшегося положения может служить применение некой комбинации переборного и локально-градиентного методов. Тогда можно будет надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета. Одним из таких комбинированных методов является так называемый генетический алгоритм. Алгоритмы этого типа мы рассмотрим в следующем разделе.
предыдущий следующий
= К содержанию =


3.3.4. Выбор метода решения задачи - релевантная информация:

  1. Исследование, проведенное автором, показало…
    выбору, сравнивают характеристики, обзванивают фирмы; неопытные потребители предпочитают консультировать у знакомых технических специалистов при выборе компьютернойтехники, поэтому, зачастую, в интернет-рекламе компьютерных фирм особая роль отводится коммуникативному воздействию на таких специалистов. В соответствии со спецификой интернет-рекламы компьютерных фирм автором была разработан набор
  2. Рост рынка сетевой рекламы связан не только с количественным ростом сетевой составляющей в рекламных бюджетах…
    выбором осуществлять какие-то дальнейшие действия, играя против рынка, либо согласиться с тем, что есть правила, которые надо соблюдать. Потому созданная в конце 2001 года российская Ассоциация Агентств Интернет-Рекламы (ААИР) объединила в своих рядах компании, работающие в области интернет-маркетинга, не столько ради борьбы с IMHO, сколько в общих глобальных целях. Своими основными задачами ААИР
  3. Выбор рекламных площадок. …
    выбору сайтов или баннерных систем, охватывающих эту целевую аудиторию.По предложению диссертанта аудиторию того или иного ресурса можно оценить при помощи нескольких методов. Во-первых, это можно сделать по такому признаку, как тематика. Во-вторых, для получения более точного и подробного демографического портрета аудитории можно воспользоваться такими методами, как проведение опросов или
  4. Введение
    выбор направления и сел едо ран и я, цели и задачи работы. Цел ыо^диссергацзю_цпо]|_работы является разработка модели и методов мониторинга и оценки защищенности веб-сайтов сеги Интернет. Поставленная цель исследования обуславливает необходимость решения следуюших основных задач: Провести анализ предметной области для установления существующих и перспективных подходов к вопросам оценки уровня
  5. Актуальность темы
    выбора стратегии и тактики проведения бизнес-операций. Динамичная коррекция набора механизмов интернет-маркетинга, оптимизация информационного содержания страниц сайта могут быть осуществлены за счет адаптации информационной структуры корпоративного сайта в соответствии с интересами его посетителей. Реализация процессов адаптации информационной структуры сайта в соответствии с интересами
  6. Задачи исследования
    выбора средств реализации адаптивных свойств корпоративного сайта. Разработка методики оптимизации информационной структуры корпоративного сайта, основанной на использовании интеллектуальных средств. Разработка показателей для поддержки принятия решений и анализа эффективности информационной структуры корпоративного сайта, учитывающих интенсивность использования механизмов интернет-маркетинга, их
  7. 1.2.2. Оптимизация сайта с целью повышения эффективности маркетинговой деятельности корпорации
    выбору из множества наиболее часто используемых ключевых слов такого подмножества, которое соответствует тематике корпоративного сайта, и грамотное размещение отобранных ключевых слов в тексте web-страницы. Повышение эффективности корпоративного сайта в этом случае возможно за счет увеличения числа посетителей сайта, получивших от поисковой системы (в ответ на свой запрос в виде ключевых слов)
  8. Самообучающиеся НС (без учителя).
    выборки, соотносится только с одним из выходных формальным нейроном - победителем, чей весовой вектор соответствует центру тяжести данного класса входных векторов. Соревновательный метод обучения используется в НС для визуализации многомерных данных на основе SOM Кохонена. Принцип формирования топографического отображения реализован в SOM - самоорганизующихся картах Кохонена (рис. 1.4) [90]:
  9. Нейро-экспертные системы
    выборки (в виде набора разноплановых экономических показателей) нейро-нечеткая сеть в процессе обучения автоматически преобразует скрытую в экономических показателях информацию в набор нечетких правил IF-THEN, образующих проблемно ориентированную базу знаний, т. е. извлекает знания из входного потока реальных данных. Нейро-нечеткая сеть может использовать стандартные алгоритмы обучения,
  10. СПИСОК ИСПОЛЬЗОВАННЫХ источников
    выбора // PC WEEK/RE 2004, № 25. С. 23,30. Nesteruk G. Ph., Kupriyanov M. C. Neural-fuzzy systems with fuzzy links // Proc. of the Vl-lh Int. Conference SCM'2003. - СПб.: СПГЭТУ, 2003. т. 1. С. 341-344. Джейн А.К., Мао Ж., Моиуддин К М. Введение в искусственные нейронные сети // Открытые системы. 1997. № 4. С. 16 - 24. ЮГСибуя М., Ямамото Т. Алгоритмы обработки данных: Пер. с япон. - М.: Мир,