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

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

3.3.3.3. Генерация допустимого плана Web-страницы

Автор предлагает генерировать допустимый план оптимизируемой
Web-страницы q є Qopi путем решения вспомогательной оптимизационной задачи.
Сформулируем систему ограничений вспомогательной задачи.
К первой группе ограничений относятся ограничения на максимальный объем полстраниц (18):



ЕСЛИ учесть, что параметры %{j»th) для фиксированных блоков bq € заданы жестко, можно привести ограничения к виду:




Обратим внимание, что в правой части ограничений находятся посто-

янные значения

Ко второй группе ограничений относятся ограничения на отображение оптимизируемых блоков (19), (20) и (21).
Целевая функция задачи имеет следующий вид:
ф,= I Z^^,/^^^max. (22)
Коэффициенты Ф{Я*у\ь) в Целевой функции задают вес соответствую- щих параметров Назначая различные значения весовых коэффици- ентов в целевой функции, можно управлять отображением соответствующих оптимизируемых информационных блоков на Web-странице.
3.3.3.4. Пример генерации допустимого плана Web-страницы Построим допустимый план Web-страницы на примере Web-страницы «Кофе» (см. табл. 3).
Множество оптимизируемых блоков состоит из десяти блоков «Кофе
... » B^f" = Ь2у..., Ь]0} каждый объемом по 20кБ. Фиксированные блоки («Панель навигации» и «Оформление») занимают суммарный объем // кБ. Таким образом, максимально доступный размер полстраниц Web-страницы «Кофе» сокращается со 120 кБ до 120-11=109 кБ.
Запишем ограничения на максимальный объем полстраниц:
1^,м-20<109, у = 1,2

Для каждого из оптимизируемых блоков bq є В^' необходимо выбрать номер полстраницы, на которой его следует отображать:



^V".V ^г,.*.,> - Ц«льіе числа.
Если 4(> > = 1 и ?(^,^,=0, блок Ьц отображается на первой полстранице; если ^>(^\ьч) = ^ и ?(,<;>,/,у) ~К блок bq отображается на второй полстранице.
Таким образом, в систему оіраничений добавляется еще десять групп ограничений (по числу оптимизируемых блоков).
Остается только назначить коэффициенты в целевой функции. Их должно быть 10 • 2 = 20 (десять блоков по два параметра каждый). Назначим коэффициенты случайным образом.

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






+ 14-^ч^)+^-^^»+7-^і + 3'^Л)+6Ь^'Л)
+71-V^+n,V^)+l5"V4^)+82-V>.M+55,V.^>^,nax-


20•*cV^м+20•^)+м•Vм + 20•^•»л)+20•V^м + 20-^ + 20.^

20-^^v + 20-^^M+20-^M + 20"*(^M + 20-«rv«.M
+ 20-V»A> + 20-V4M + 20VA)+20'VM + 20-*^,i,a9. Кофеї: ^.m+V'.v"1' Кофе 2: ?(«"\м+€(^\*,,=1. КофеЗ: ^.М+<^>Л)=1,
Кофе4: V,.«*)+^,,.M=1'
Кофе 5: 4<,,<'>.М+?(^.Л) = 1<
Кофе 6: ^..ЛЇ+^.Л)=1,
Кофе7: ?<,<и.м+<^.г.іМ = 1,
Кофе 8: ^.Л)+^Л)=1,
Кофе9: ^..>.M+V>.M = l> Кофе 10: V^o)+4(,<:Uo, = l,
^<«"'Л> ~ ^* ^<«"'.*,> ~ Челое число, для всех ^v € _у = 1, 2.


В результате решения данной задачи методом Гомори при помощи программы NLP, разработанной автором, получаем:
О™ =714, Кофе 1: 4(,<> '•М = = 0, Кофе 2: %{qo 'Л) = = 1, КофеЗ: 4{q« '.м = = 0, Кофе 4: %iqo ¦Л)= = 0, Кофе 5: ?<(7<. 'Л> ~ = 1, Кофе 6: ?<(?<. 'А) = °> ^':,А> = 1, Кофе 7: ?(41и = = 0, Кофе 8: <^„ >Л> = ^ ^и,А) Кофе 9: ^„ >А>= °> ^<Уг>А> = 1, Кофе 10: ^ = 0» ^ША> = Таким образом, мы получаем следующее отображение блоков на под-страницах Web-страницы «Кофе»: на первой полстранице отображаются
блоки «Кофе 1», «Кофе 3», «Кофе 4», «Кофе 7» и «Кофе 8» (?(<,<».^) = 1), на второй полстранице - оставшиеся блоки «Кофе 2», «Кофе 5», «Кофе 6», «Кофе 9» и «Кофе 10» ) = 1 )• Мы получили допустимый план отобра-
жения информационных блоков на Web-странице.
3.3.3.5.
Выбор метода генерации допустимого плана Web-страницы Задача генерации допустимого плана Web-страницы имеет линейную целевую функцию и линейную систему ограничений, включающую равенства и неравенства. Параметры решения задачи могут принимать булевские значения: 0 или У. Максимально возможное число параметров (переменных) равно произведению числа оптимизируемых информационных блоков на Web-странице на число полстраниц. По системе классификации, рассмотренной в [4, сс. 13-15], данную задачу можно отнести к классу оптимизационных задач линейного программирования с булевыми переменными или к более широкому классу задач дискретной оптимизации.
В качестве возможных методов для решения задачи генерации допустимого плана Web-страницы автором рассматривались методы целочисленного линейного программирования (в частности, метод Гомори [12, сс. 154-157]) и методы динамического программирования (в частности, метод решения обобщенной задачи о рюкзаке [15, сс. 251-258], далее метод ДП).
Практические расчеты показали, что при решении задачи генерации допустимого плана Web-страницы метод ДП, в целом, работает эффективнее метода Гомори при числе полстраниц не более четырех. Особенно хорошо это проявляется при решении задач с большим числом оптимизируемых информационных блоков (сотни и тысячи) и малым числом полстраниц (одна-две). Например, получить решение задачи о показе 400 информационных блоков на одной полстранице (всего 400 переменных) методом Гомори за приемлемое время не удается, тогда как метод ДП выдает решение за доли секунды .
Увеличение общего числа переменных не является столь критичным для метода ДП, как увеличение числа полстраниц (оно ведет к увеличению размерности «рюкзака» и делает невозможным применение на практике алгоритмов динамического программирования).
Метод Гомори эффективен при решении задачи генерации допустимого плана Web-страницы с числом подстраниц более четырех и общим числом переменных не более ста. Надо заметить, что общее число переменных при решении задачи методом Гомори возрастает также из-за несколько «неестественной» формулировки некоторых ограничений задачи на языке целочисленного линейного программирования. Например, в ограничении (20), задающем правило выбора полстраницы из множества подстраниц Yb для отображения на ней информационного блока, используется \УЬ I булевых переменных, в то время как для однозначного задания номера подстраницы было бы достаточно одной целочисленной переменной, принимающей значения от
Uoinj.
К сожалению, подобрать методы, эффективные при решении задачи генерации допустимого плана Web-страницы с числом подстраниц более четырех и общим числом переменных более ста, автору не удалось. Единственным утешением служит почти полное отсутствие практической необходимости решения таких задач. В реальных Интернет-магазинах Web-страниц со столь большим количеством информационных блоков и подстраниц обычно не встречается. В крайнем случае, всегда можно использовать те или иные пути уменьшения размерности задачи.
предыдущий следующий
= К содержанию =


3.3.3.3. Генерация допустимого плана Web-страницы - релевантная информация:

  1. 3.3.3.2. Генерация допустимого плана сети
    генерации допустимого плана сети необходимо выполнить следующие шаги: I) проверить неоптимизируемые Web-страницы сети q ? Q*** на соблюдение условия (18). Если условие (18) не соблюдается, делается вывод о невозможности генерации допустимого плана сети; 2) построить допустимые планы оптимизируемых Web-страниц сети q € Q0** (см. гл. 3.3.3.3). Если допустимый план Web-страницы построить не удается,
  2. 3.3.6. Решение задачи оптимизации сети Интернет-проекта с применением генетического алгоритма
    генерации допустимого плана сети потомка, в результате решения которой мы всегда получим жизнеспособную особь с фенотипическими признаками, построенными на основании комбинации генов родителей и случайного фактора мутации. Теперь остается нерешенным только вопрос о формировании начальной популяции (шаг 1 генетического алгоритма). На этом шаге необходимо сгенерировать множество жизнеспособных
  3. 3.3.3.1. Допустимость плана сети
    допустимости плана сети Интернет-проекта: план сети будет допустимым тогда, когда будут допустимыми планы всех ее
  4. 3.3.3.6. Пример допустимого плана сети
    допустимого плана для сети из табл. 2 и 3 представлен в табл. 5. Для экономии места представлена информация только об оптимизируемых Web-страницах
  5. В WAP - Банкинге, функции представительской компоненты выполняет встроенный в мобильный телефон WAP-браузер
    генерации ключей, управления сертификатами и другие компоненты. Все банковские АРМы, за исключением АРМа »Администратор системы», реализованы на базе технологий Internet - Банкинга, не требуют установки специализированного ПО, работают на любых современных компьютерах с любыми ОС и любыми Web-браузерами и содержат встроенные механизмы ЭЦП, шифрования и обеспечения целостности информации. [122]
  6. При составлении плана рекламной кампании…
    плана рекламной кампании следует [93] дать ответ на 4 вопроса: • что должна сделать реклама (обычными целями рекламы выступают увеличение осведомленности потребителя об определенной компании и ее продукции, переманивание потребителя у конкурентов, увеличение вероятности сохранения существующих потребителей и повышения уровня их лояльности, немедленный рост объема продаж или привлечения новых
  7. Выбор рекламных площадок. …
    плана размещения рекламы.Одним из первых решений при проведении рекламной кампании должно быть определение целевой аудитории. Принятие этого решения позволит перейти к следующему шагу - выбору сайтов или баннерных систем, охватывающих эту целевую аудиторию.По предложению диссертанта аудиторию того или иного ресурса можно оценить при помощи нескольких методов. Во-первых, это можно сделать по
  8. БИБЛИОГРАФИЧЕСКИЙ СПИСОК ЛИТЕРАТУРЫ
    плана маркетинга. - М.: ACT, 1996.-256 с.Бокарев Т.А. Энциклопедия интернет-рекламы. - М.: Промо-ру, 2000. - 399 с.Багиев Г.Л. Маркетинг - философия и инструментарий предпринима тельства// в кн. Маркетинг и предпринимательство: ученые записки факультета коммерции. - СПб.: Питер, 1995. - 318 с.Булгари М. PR в Интернет. - СПб.: АТА"БОЛГАР", 1999. - 340 с.Байков В. Интернет. Поиск информации.
  9. 1.2.3.5. Расширение возможностей системы
    генерации HTML-страниц. Первая версия этого языка была разработана в 1994 году. В принципе динамические HTML-страницы могут генерироваться и при помощи CGI-сценариев (см. предыдущий раздел). Но CGI-сценарии представляют собой отдельные процессы, запускаемые на выполнение по мере поступления запросов от пользователей, и при большом количестве таких запросов и их ресурсоемкости, может быть
  10. 3.3.1. Критерии оптимальности сети
    допустимые уровни затрат пользователей Cmjn и CmsK. Web-сайты, характеризующиеся затратами ниже Cmin, будут слишком примитивными, чтобы удовлетворять запросам пользователей (на них будет отсутствовать графика или необходимая информация о товарах). Web-сайты с затратами выше Стах не будут удовлетворять пользователей ввиду избытка рекламы, ненужной информации или неоптимальной структуры. В обоих