More Related Content
Similar to GAによる広告出稿最適化 (20)
GAによる広告出稿最適化
- 1. ST3 . 「遺伝的アルゴリズム(GA: Genetic Algorithm )による広告出稿準最適化」 2010年6月20日(日) 橋本武彦 ID : takenotabi (Twitter:@takenotabi) 第5回 データマイニング +WEB 勉強会@東京 (Tokyo.Webmining#5)
- 3. 本日のテーマ 遺伝的アルゴリズム(GA: Genetic Algorithm )による広告出稿 準最適化 ~メディアプランニング業務支援オプティマイザー(※)への 適用事例 ※ オプティマイザー(最適出稿予算配分システム) 電通 “ DiaLog” 博報堂 “ HAAP” ~クロスメディア、マス4媒体、交通、ネット、 etc ブレインパッド “ L2Mixer” ~リスティングの ROI 最大化(数理計画法( 0-1 整数計画法)) ロックオン “アドエビス AutoBid” ~リスティングの T&D 組合せ最適化(GA)
- 5. メディアプランナーの悩み 1,000万円の予算(制約)のキャンペーンを考える際に、 どの雑誌に何回出稿する組合せが、一番、 GRP (閲読率の累積)が高くなるかを考える。 (ナップザック問題) ■ 雑誌情報(500誌) ・・・ 予算内に収まるすべての雑誌の組合せを考えれば良いのだが・・・ 組合せ①: an ・ an3 回+ JJ2 回 ⇒ GRP 〇〇% 組合せ②: JJ 2 回+ViV i8 回 ⇒ GRP 〇〇% 組合せ③: JJ 9 回+ViV i1 回 ⇒ GRP 〇〇% ・・・ 各雑誌の出稿有無に限っても、2 ^ 500・・・。さらに、出稿回数も入るので、現実的にはほぼ計算不能!(組合せの爆発) ⇒ 何らかの解探索手法が必要
- 8. GAの処理の流れ ■ 処理フロー・・・いずれも乱数処理 (突然変異)・・・局所解への陥りを防ぐ (交叉)・・・解探索 (選択)・・・適応度の高い個体を残す 適応度比例戦略、トーナメント戦略、 etc (初期)・・・乱数を用いて、ランダムに生成 (評価)・・・評価関数による適応度算出 ~予算内: GRP の高い順 ~予算外:予算との乖離が小さい順
- 9. GAのまとめ(長所 / 短所) ○ :長所 ・幅広い応用範囲を持っており、さまざまな問題に適応できる。 ・実用時間内に比較的優れた解を求めることができる。 ~”解空間構造が不明であり、決定的な優れた解法が発見されておらず、また、 全探索が不可能と考えられるほど広大な解空間を持つ問題に有効” × :短所 ・パラメータやコーディングに対する一般的な規範がない。 ~要チューニング(大変) ※ 適用領域 ・配送計画( TSP 問題) ・・・コンビニなど ・スケジューリング ・・・学校の時間割、ナースのスケジューリング、 etc etc
- 10. 参考文献 ■ wikipedia http://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0#SGA ■ 村上・泉田研究室 http://ipr20.cs.ehime-u.ac.jp/column/ga/index.html ■ 簡単そうで難しい組合せ最適化 http://www-or.amp.i.kyoto-u.ac.jp/members/yagiura/open-campus-2004/happyo-shiryo.pdf