Prírodou inšpirované algoritmy

Evolučné bannery

Evolučné bannery - výskumný projekt v tejto oblasti, ktorý sa zameral na automatizáciu dizajnu objektov WWW. Tradičná trhová komunikácia spočíva v akomsi odkaze, ktorý pošle inzercujúci zákazníkovi. Správa sa môže vyskytovať v rôznych podobách – reklama v novinách, billboard, reklama v rádiu, alebo reklamný banner na Internete. V závislosti na rozpočte inzerujúcej organizácie sa dôraz kladie na tri faktory :

1. dosah reklamy (počet oslovených zákazníkov)
2. frekvencia (ako často zákazník dostane k reklame)
3. kvalitatívne aspekty (určujú mieru akou reklama ovplyvní zákazníka)

Manažment firmy propagujúcej určitý produkt môže osobne navrhnúť reklamu a ušetriť tak financie, na druhej strane určite obmedzí dosah. Iným variantom je zamestnanie pomerne drahých profesionálnych dizajnérov. Dizajn reklamných plôch aplikovaním evolučných algoritmov sa sústredí najmä na kvalitatívne aspekty reklamy. Dizajny jednotlivých reklám sa zvyknú obvykle testovať ešte predtým ako sa dostanú do médií. Tradičné metódy testovania sú finančne náročné a zdĺhavé – vyžadujú prezentovanie reklám skupine osôb a následne ich ohodnotenie, zvyčajne vo forme dotazníkov, interview. Za posledných 10 rokov sa on-line médiá rozrástli do takej miery, že sú rovnocennými partnermi tlače a vysielania. Služby ako Compuserve, America Online majú vyvinutý grafický inteface už takmer 10 rokov. Tento krok otvára dvere novým, nápaditým dizajnom, reklama sa dostáva z pozície čisto písaného textu.

Potreby poskytovateľov reklamy, providerov a užívateľov vyústili do štandardného formátu internetovej reklamy – banneru. Najčastejšie používané bannery sú vo formáte GIF, GIF89 a JPEG. Ich veľkosť sa môže mierne odlišovať, ale väčšina má štandardnú veľkosť 468 x 60 pixelov.

Interaktívne bannery sú také, ktoré poskytujú istú interakciu so zákazníkom. Napríklad sa na ne dá kliknúť, objednať cez ne nejaký produkt, prípadne označiť nejakú informáciu atď.. Médiá ako WWW umožňujú automaticky vyberať bannery v závislosti na návštevníkovi stránky. Napríklad AltaVista automaticky zisťuje národnosť návštevníka a podľa nej prezentuje bannery produktov tejto krajiny v tomto jazyku.

Počet jednotlivých kliknutí na banner je priamo ovplyvnený jeho dizajnom. Prieskumy v tejto oblasti ukazujú, že animácie a najmä nápis click here zvyšujú počet kliknutí. Ako ďalšie faktory sa ukazujú samotný dizajn banneru, jeho veľkosť, farba a umiestnenie na stránke.

Niekoľko publikovaných vedeckých štúdií o efektivite bannerov na WWW dochádza k rôznym záverom. Niektoré hľadia na hranicu medzi reklamou a obsahom reklamy, iné skúmajú špecifické využitie. Boli vykonané experimenty nazvané copy test automation, čo v praxi znamená meranie počtu kliknutí na banner. Boli manuálne vytvorené štyri bannery takmer s takmer identickým dizajnom, výnimkou bol iba jeden riadok textu, kde boli použité štyri rôzne slogany (jedným z nich bol aj nápis „click here“). Výsledkom experimentov bolo zistenie, že nápis click here dosiahol najväčší úspech – dosiahol najväčší počet kliknutí. Inou metódou bolo vygenerovanie množstva bannerov a ich náhodné umiestnenie na rôznych stránkach. Ich ďalšie rozmiestňovanie po sieti sa modifikuje spätnou väzbou - podľa štatistík počtu kliknutí na ten ktorý banner.

Evolučný prístup

Nástroje na dizajn bannerov sa stávajú čoraz dostupnejšími, flexibilnejšími a zároveň aj autonómnymi, ale proces tvorby ešte stále vyžaduje pomerne veľa ľudského úsilia. Evolučné algoritmy pôvodne slúžili ako biologicky motivovaná forma na riešenie výpočtových problémov napr. optimalizácia a pod.. Behom posledných rokov sa však táto základná idea rozvinula viacerými smermi a v súčasnosti sa evolučné algoritmy používajú v omnoho väčšom spektre úloh. EA sú dnes modernou technikou na analýzu dát aj napríklad v oblasti marketingu. Existuje niekoľko oblastí marketingu, kde boli evolučné algoritmy úspešne aplikované (Financial services, Facility layout, Document Clustering and finally Development of world economic model).

Využitie evolučných algoritmov v oblasti elektronického obchodu je však ešte stále v zárodku, najmä v oblasti dizajnu reklamných. Aplikácie EA v marketingu sú zamerané najmä na simuláciu správania sa trhových mechanizmov, avšak použitie evolúcie v dizajne reklám predstavuje pomerne veľkú výzvu.

Problém: propagácia CD v online hodobnom obchode

Existuje mnoho online obchodov s hudobnými nosičmi, ktoré ponúkajú široký výber z CD, DVD, kaziet a iných. Táto štúdia bola zameraná na audio CD nosiče vzhľadom na ich najväčší percentuálny podiel z predaja. Internetové predajne obsahujú mnoho druhov bannerov oznamujúcich rôzne odkazy – zľavy, akcie, novinky a pod.. Takisto, nahradiť pôvodný banner „evolučným“ nepredstavuje veľký problém a nevyžaduje modifikovať dizajn samotnej stránky.

Takýto propagačný banner by mal zvýšiť, resp. podporiť predaj určitého produktu. Efektivita takéhoto spôsobu propagácie je závislá na obsahu reklamy (produkt, cena, atď.) a na forme ponuky (veľkosť, text, animácia, farba, atď.). V praxi sa ukazuje, čo i len jeden rozdielny riadok textu v banneri má obrovský dopad na efektivitu – počet kliknutí takto navrhnutých bannerov sa pohyboval v rozmedzí od 2.87% do 11.13%! Ak zákazník uzrie billboard, ako je možné zistiť, že práve toto bol dôvod, že si kúpil daný produkt? Interaktívne médiá teoreticky poskytujú možnosť ako spojiť tieto dve veci dokopy. Napríklad je možné „vystopovať“ cestu odkiaľ sa zákazník dostal na stránku produktu, teda je možné zistiť, či jednoducho klikal na bannery, alebo nie. V tomto prípade sa autori z technických príčin rozhodli merať iba click-through rate teda počet kliknutí na banner a predpokladali, že viac kliknutí vedie k väčšiemu predaju. Niektoré štúdie však tvrdia, že bannery sú efektívne, aj keď nedosahujú vysoké čísla click-rate.

Experimenty boli vykonávané v skutočnom online obchode s reálnymi zákazníkmi. Zvolený online obchod dosahoval približne 10 000 návštev denne. Každá jedna návšteva zákazníka môže generovať priemerne 10 zobrazení stránok. Približne 60 percent navštívených stránok obsahuje banner. Môžeme teda brať do úvahy zobrazenie banneru priemerne 60 000 krát. Na začiatku testov boli bannery umiestnené na 20 rôznych miestach na stránke (hlavná stránka, podstránka s novinkami, atď.). Človek – dizajnér, ktorý navrhuje bannery pre Boxman online obchod vytvoril pôvodný banner skúmaného produktu. Jeho úlohou bolo vytvoriť typický dizajn, s jedinou výnimkou – nemohol použiť animáciu. Potom ešte poskytol niekoľko doplňujúcich grafík a textov, pričom niektoré z nich boli také, ktoré sám zamietol počas procesu dizajnu banneru.

Dizajn pôvodného banneru

Za účelom štúdia vplyvu GA boli bannery rozdelené do troch skupín. Prvú tvorili bannery posledne evolvovanej generácie. Druhú skupinu tvorili bannery prvej generácie a nakoniec v tretej skupine sa nachádzali pôvodné bannery navrhnuté dizajnérom. Zakaždým, keď príde požiadavka na zobrazenie stránky s bannerom, server náhodne vyberie jednu z týchto skupín a náhodne vyberie banner z tej ktorej skupiny. Po ukončení experimentov autori prišli k dvom záverom. Bannery z tretej skupiny dosahovali vždy lepšie výsledky ako bannery z druhej skupiny. A bannery druhej skupiny na začiatku experimentu dosahovali lepšie výsledky ako tie z prvej skupiny, ale táto vlastnosť sa počas evolúcie menila tak ako sa bannery prvej skupiny vyvíjali.

Kódovanie

Po diskusii so skúseným dizajnérom autori vytvorili počiatočnú generáciu bannerov. Ako formát banneru bol zvolený statický GIF súbor. V budúcnosti je potom teoreticky možné rozširovať tento formát v rámci možnosti EA – ako je napríklad pridávanie animácií, využitie viacerých objektov, alebo menšie ohraničenia v renderovaní. Banner pozostával z nasledujúcich objektov:

Teoreticky bolo možné voľne evolvovať aj umiestnenie aj formu jednotlivých objektov na banneri. Tento prístup však vyžaduje komplikovaný algoritmus, preto bol banner rozdelený do štyroch sektorov – dvoch štvorcov, dvoch obdĺžnikov, obrázky mohli byť umiestnené v jednom zo štvorcov a texty v obdĺžnikoch.

Rozdelenie banneru na časti

Vzhľadom na toto rozdelenie veľkosť použitých obrázkov bola obmedzená na štandardných 52x52 pixelov, na evolúciu textu nebol kladený žiaden limit. V experimente bolo použitých niekoľko druhov fontov a viacero farieb a veľkostí písma. Jednotlivé bannery boli zakódované pre potreby EA do reťazca celých čísel a na začiatku experimentu pozostával chromozóm jedinca z približne 40 génov. Program bol vytvorený v jazyku C++, jedinci sa automaticky renderovali do GIF súborov. Systém bol najskôr otestovaný v off-line prostredí, potom nasadený v praxi.

Nasledujúci obrázok znázorňuje jedincov z populácie. Vidno na ňom rôzne dizajny a takisto rôzne hodnoty click-rate.

Populácia jedincov

Parametre algoritmu

Experimenty prebiehali s populáciou veľkosti 20 jedincov, pravdepodobnosťou kríženia 0.6 pre pár rodičov a pravdepodobnosťou mutácie jedného bitu 0.001. Použité bolo iba jednobodové kríženie s náhodne vybraným deliacim bodom. Vhodnosť každého jedinca v tomto prípade predstavoval priamo počet kliknutí na ten ktorý banner.

Kde je dizajnér?

V skutočnom marketingu sa o dizajn reklamy stará dizajnér. Môžu predstavovať takéto autonómne sa dizajnujúce bannery hrozbu pre dizajnérov? Všetko nasvedčuje tomu, že nie.

Kreativita je niekedy označovaná ako proces kombinovania existujúcich zložiek nejakým novým smerom, novým spôsobom. Problém pre človeka - dizajnéra je rozhodnúť, ktorý z nich je komerčne najefektívnejšou ideou. Ďalší problém predstavuje schopnosť generovať dostatočne veľké množstvo ideí. Oba problémy môžu byť riešené evolučným prístupom a dizajnér ich môže využiť vo svoj prospech.

Reprodukcia, časový problém

Vo väčšine prípadov je potrebné získať výsledky čo najskôr. Obvykle sa EA vykonávajú viac krát napr. tri spustenia s 200 generáciami v každom behu. Je to v podstate klasický prípstup v analýze dát. V niektorých prípadoch výsledky závisia na počte spustení programu. V tomto experimente bola jedna generácia bannerov zobrazená až dovtedy, pokiaľ bola možnosť vypočítať fitness. Ten moment na výpočet vhodnosti bol volený na základe troch metód.

1. Čas : fitness sa rátala po uplynutí istého času, napr. jedného dňa
2. Počet kliknutí: fitness sa rátala po určitom počte kliknutí na bannery – napríklad desaťnásobku veľkosti populácie
3. Najlepší banner: fitness sa vypočítala potom, čo niektorý z bannerov dosiahol určitý počet kliknutí, napr. 100

Preferovaná metóda a špecifické nastavenie môže byť evolvované iným GA. Rýchlosť, ktorou sa vygeneruje nová populácia bannerov - evolution rate - závisí na tom, ako často ju počítame. Bez ohľadu na zvolenú metódu trvá podstatne dlhšie vypočítavanie vhodnosti ako vygenerovanie novej populácie. Teda problémom nie je výpočtový čas procesora, ale evolution rate. Pre metódy 2 a 3 môže viesť vyššia frekvencia zobrazovania stránok k rýchlejšiemu evolution rate. Počas experimentov výskumníci môžu čakať pomerne dlhý čas na výsledky. Ale z hľadiska majiteľa online obchodu je rýchlosť evolúcie kritickým faktorom. Zobrazovanie niektorých bannerov môže byť prerušené – to sa stáva v prípade, keď je fitness určovaná z krátkeho časového intervalu, napr. na základe štatistík predaja z uplynuhého dňa. Ak je naopak rýchlosť evolúcie nízka, bannery nemusia mať dostatok času, aby sa evolvovali do chcenej podoby.

Nepretržitá evolúcia

Je vhodné ak sú výpočtové procesy adaptívna, tzn. reagujú na zmeny prostredia. A meniace sa prostredie je aj prostredie bannerov v online obchode. Návštevníckom sa môže daný produkt časom začať zdať nudný. Môžu často vídať jeden banner bez toho aby naň klikli. V niektoých prameňoch sa tento efekt nazýva klesajúca návratnosť. V takomto prípade je koncept jednotlivých krokov evolúcie zastaralý. Algoritmus môže bežať donekonečna, alebo aspoň dovtedy pokiaľ nezmeníme parametre, prípadne znovu nadizajnujeme bannery (objekty, obrázky atď.).

Záver

Táto štúdia demonštrovala možnosť využitia GA v oblasti dizajnu reklamných bannerov. Je však takmer nemožné objektívne vyhodnotiť efektivitu takéhoto evolučného prístupu. Zatiaľ je však možné vyvodiť niekoľko pripomienok. Rozdelením banneru do niekoľkých sektorov zjednodušuje reprezentáciu jedinca a softwarovú implementáciu. Akonáhle bude program dôkladne otestovaný, nepredstavuje veľký problém pridať viacero sektorov, prípadne manipulovať s viacerými objektami. Takisto voľba počtu kliknutí ako hlavého vstupu pre výpočet fitness predstavuje veľmi priamočiary prístup. Preto určovanie vhodnosti bannerov predstavuje väčšiu výzvu ako zrýchľovanie, alebo určovanie parametrov evolúcie. V rámci možného budúceho výskumu v tejto oblasti je samozrejme viacero smerov, ktoré možno preskúmať. Niektoré z nich sú:

• Aké a koľko elementov banneru je možné evolvovať?
• Ako môže interakcia s užívateľom ovpyvňovať fitness?
Estetická hodnota banneru je dôležitá pre človeka, ale je možne aby sa ňou riadil aj EA?
• Má evolúcia bannerov bežať nepretržite, alebo má byť prerušovaná?
• Aké je vhodné nastavenie EA?
• Ako môžu evolučné techniky požité pri dizajne ovplyvniť ostatné ukazovatele, ako napr. určovanie cien, výber produktov atď.?