Je travaille sur un algorithme d'enchères automatiques pour les publicités (même si ce sera bientôt dans le passé). Aucun journal n'est stocké du tout. Par conséquent, je n'avais pas d'autre choix que de générer des données et inévitablement effectué la simulation.
Qu'est-ce que l'optimisation multifonction? Il y a une description comme suit.
Dans l'optimisation multi-objectifs, pensez à minimiser plusieurs fonctions objectifs $ \ bf {f} $. Idéalement, ce serait bien de pouvoir minimiser toutes les fonctions objectives $ f_1 $, ..., $ f_k $ en même temps. Cependant, cela signifie qu'il n'était pas nécessaire de le résoudre en tant qu'optimisation multi-objectifs en premier lieu. En effet, la minimisation d'une fonction objectif minimise les autres fonctions objectives en même temps. Par conséquent, le problème qui devrait généralement être traité dans l'optimisation multi-objectifs est qu'il existe une relation de compromis entre les fonctions objectif $ \ bf {f} $, de sorte que tenter de réduire une fonction objectif entraîne la taille des autres fonctions objectif. Il y a un cas. (Extrait du Guide pratique pour l'optimisation mathématique p.110)
En d'autres termes, minimisons (maximisons) la valeur de la fonction objectif dans une situation où "si vous la configurez, vous ne pouvez pas vous lever ici". En gros, vous trouverez une solution Pareto. Il existe différentes méthodes et la méthode diffère selon que le front de Pareto est convexe ou non convexe. 50 problèmes d'optimisation utiles pour l'application (série d'optimisation d'application) pour des méthodes spécifiques = 1211 & creativeASIN = 4254117884 & linkCode = as2 & tag = shimashimao06-22 "> 50 problèmes d'optimisation utiles pour l'application (série d'optimisation d'application) ) Sera utile. Cependant, cette fois j'ai choisi une méthode heuristique car je voulais effectuer des calculs à grande vitesse et je voulais optimiser pour un créneau horaire assez fin.
Cliquez ici pour les références. Real time bid optimization with smooth budget delivery in online advertising, Lee+, Turn Inc.,'13 [PDF] Veuillez vous référer à slidshare pour le contenu. .. (Cependant, si vous regardez cela maintenant, la partie interprétation est un peu fausse ... je vais la corriger si vous en avez envie w)
Le code est créé sur la base de cet article. Cependant, les parties qui mettent du temps à générer des données sont omises. Comme je l'ai écrit au début, comme il n'y a pas de données, j'ai mis en place un agent utilisateur et un agent de soumission pour faire une pseudo-offre. Le créneau horaire est défini sur 1 minute, le budget est réparti et le montant de l'offre est optimisé pour chaque créneau horaire.
Voici le code que j'ai créé. Puisqu'il est écrit par un non-ingénieur, je pense qu'il y a beaucoup de choses à faire, mais soyez patient.
Créez un site pour qu'un agent utilisateur visite le site.
python
# coding: utf-8
import random
class Agent:
def __init__(self,num):
random.seed(num) #Occurrence de semences aléatoires
self.ctr = random.uniform(0,1)
def get_ctr(self):
return self.ctr
def get_visiter_ctr(self, pred):
if random.uniform(0,1) > (1-pred):
return self.get_ctr()
else: return False
Ensuite, créez un agent (concurrent) pour soumissionner.
python
# coding: utf-8
import random
from math import ceil
class Agent:
def __init__(self,n):
random.seed(n) #Occurrence de semences aléatoires
self.ctr = random.uniform(0,1)
self.maxprice = random.randint(40,90)
def get_maxprice(self):
return self.maxprice
def get_bid_price(self, ctr, pred):
price = self.maxprice*ctr*pred
if random.uniform(0,1) > 0.35 :
return ceil(price) + random.randint(0,5)
else:
return False
Comment écrire le code de la partie optimisation.
python
# coding:utf-8
#cython: boundscheck=False
#cython: wraparound=False
import pyximport; pyximport.install()
from math import sin, cos, pi, fmod, sqrt, floor
import random
import useragent
import bidagent
import numpy as np
cimport numpy as np
cimport cython
DTYPE = np.float64
INTTYPE = np.int64
ctypedef np.float64_t DTYPE_t
ctypedef np.int64_t INTTYPE_t
cdef extern from 'stdlib.h':
ctypedef unsigned long size_t
void *malloc(size_t size)
void free(void *prt)
class CreatePredict:
pi2 = 2*pi
#random.seed(3)
PHI = 2*pi/8 #Représenter le déphasage
# TBit = 10000000.0
def __init__(self, period, agent_num):
self.minbit = 1000*agent_num/1000
self.E = 1250*agent_num/1000
self.PERIOD = period
self.OMEGA = self.pi2/self.PERIOD
self.AGENT_NUM = agent_num
def getvalue(self,period):
"""
Probabilité de venir sur le site
sin(theta) = sin(OMEGA*t + phi)
T = 2*pai/OMEGA
60*60*24=86400sec
OMEGA = 2pai/86400
"""
cdef sec
cdef np.ndarray[np.double_t, ndim=1] tmp = np.zeros(period,dtype=np.double)
for sec in xrange(period):
tmp[sec] = self.E * ( sin(self.OMEGA*sec - self.PHI) + 1 ) + self.minbit
return tmp/self.AGENT_NUM #Calcul de pred
cdef class ComputeBid:
cdef int time, day
gamma = 1.96 #Utilisé pour calculer l'intervalle de confiance(95%En supposant un intervalle de confiance)
beta1=0.3
beta2=0.8
theta_bin = 100
cdef np.ndarray \
bid_num,win_num,cmsp_bag,theta,ctr_hist,mu,sigma
cdef int period, daybuget, gcpc, bidcap, bin_n
cdef double ctrbin, avgprice
def __init__(self,period,daybuget,gcpc,bidcap,ctrbin):
self.period = period
self.ctrbin = ctrbin
self.daybuget = daybuget
self.gcpc = gcpc
self.bidcap = bidcap
self.bid_num = np.zeros(period, dtype=np.int64)
self.theta = np.zeros(self.theta_bin, dtype=np.float64)
#Stockage des histogrammes ctr
self.bin_n = int( float(1.0)/ctrbin )
self.ctr_hist = np.zeros((period,self.bin_n), dtype=np.int64)
self.mu = np.zeros(period, dtype=np.float64) #Valeur moyenne pour chaque emplacement de la tau du seuil d'enchère
self.sigma = np.zeros(period, dtype=np.float64) #Répartition du seuil d'enchère tau pour chaque créneau
self.avgprice = 0.0
def __dealloc__(self):
pass
def output(self, file,user_agent_num,bid_agent_num,days):
cdef int t,n,i,c,b
#Calcul de la prévision de visite
pred_creater = CreatePredict(self.period, user_agent_num)
#Occurrence de l'agent utilisateur
user_agent = [ useragent.Agent(n) for n in xrange(user_agent_num) ]
#Occurrence de l'agent de soumission
bid_agent = [ bidagent.Agent(n) for n in xrange(bid_agent_num) ]
for t in xrange(self.period*days):
self.time = fmod(t,self.period)
if fmod(t,self.period)==0:
if self.day!=0: self.avgprice /= sum(self.win_num)
self.bid_num = np.zeros(self.period, dtype=np.int64)
self.win_num = np.zeros(self.period, dtype=np.int64)
self.cmsp_bag = np.zeros(self.period, dtype=np.float64)
self.day+=1
print "progress:",t
#Calcul de la prédiction de visite
pred = pred_creater.getvalue(self.period)
#Calcul de l'allocation budgétaire pour chaque créneau
slot_bag = self.calc_slot_bag(pred)
#Obtenir le ctr des visiteurs
ctr = []
bidp = []
visit = 0.0
dbidprice = {}
for i in xrange(user_agent_num):
ctr.append( user_agent[i].get_visiter_ctr(pred[self.time]) )
#Calcul du montant de l'offre pour chaque agent
if ctr[i] == False: continue
visit += 1.0
"""Créer un histogramme de ctr"""
if self.day==1: self.get_hist(ctr[i])
maxprice = 0.0
for b in xrange(bid_agent_num):
price = bid_agent[b].get_bid_price(ctr[i], pred[self.time])
if price > maxprice:
maxprice = price
bidp.append(maxprice)
"""Comptez le nombre d'offres et déterminez le montant de l'offre"""
#Le rythme utilisé pour la tarification des enchères_Calculer le tarif
if self.bid_num[self.time]==0:
pacing_rate = 0.0
else:
pacing_rate = self.bid_num[self.time]/float(visit)
#Détermination du prix de l'offre
bidprice = self.calc_bidprice(self.day, ctr[i], pacing_rate)
print 'price',bidprice
#Jugement sur l'offre ou non
if bidprice == False: continue
"""Création d'un dictionnaire pour confirmer le montant de l'enchère calculé"""
if str(floor(bidprice)) not in dbidprice: dbidprice[str(floor(bidprice))] = 1
else: dbidprice[str(floor(bidprice))] += 1
#Si le montant de l'enchère dépasse le plafond, ce sera la valeur du plafond
if bidprice>self.bidcap: bidprice = self.bidcap
#Si vous souhaitez enchérir, vérifiez le nombre d'offres
self.bid_num[self.time] += 1
#Jugement d'avoir remporté l'offre
if bidprice > maxprice:
#Jugement sur l'opportunité de soumissionner
if slot_bag[self.time] - self.cmsp_bag[self.time] - bidprice > 0:
self.cmsp_bag[self.time] += bidprice
print 'cmsp=',self.cmsp_bag[self.time]
self.calc_theta(bidprice,maxprice)
self.win_num[self.time] += 1
#Calcul du coût moyen autour de 1bid
if self.day==1: self.avgprice += bidprice
print dbidprice
print np.float64(self.win_num)/self.bid_num
num1 = []
num2 = []
for i in xrange(self.period):
num1.append( str(slot_bag[i]) )
num2.append( str(self.cmsp_bag[i]) )
file.write(u'slot bags\n'+u','.join(num1)+u'\n')
file.write(u'comsumption bags\n'+u','.join(num2)+u'\n')
def get_hist(self,ctr):
"""Créer un histogramme CTR"""
cdef int bin
for bin in xrange(self.bin_n):
if bin*self.ctrbin<=ctr<(bin+1)*self.ctrbin:
self.ctr_hist[self.time,bin] += 1
break
def calc_bidprice(self, day, ctr, pacing_rate): #ctr[i]
cdef int i
tau = 0.0
if day<2:
if ctr>=0.2:
return random.randint(20,80)
else: return False
else:
if self.cmsp_bag[self.time]!=0.0:
#Calcul des impulsions de prédiction
imps = float(self.cmsp_bag[self.time])/self.avgprice
print 'imps',imps
#Calcul du nombre prévu d'offres
#win_rate = bid_num[self.time]/win_num[self.time]
bids = float(imps*self.bid_num[self.time])/self.win_num[self.time]
print 'bids',bids
#Calcul du nombre attendu de demandes
print 'pacing_rate',pacing_rate
reqs = bids/pacing_rate
else:
reqs=0.0
print 'reqs',reqs
#Obtenir le seuil d'enchère
for i in xrange(len(self.ctr_hist[self.time,:])):
if sum(self.ctr_hist[self.time,-(i+1):]) - reqs >0.0:
tau = float((self.theta_bin-1)-i)/self.theta_bin
break
#Calcul de la valeur moyenne
if self.time == 0: t = self.period - 1
else: t = self.time-1 #T voici t-Définir sur 1
div_t = float(1)/(self.time+1)
self.mu[self.time] = self.mu[t]+ div_t*(tau-self.mu[t]) #mu peut avoir besoin de sauvegarder l'emplacement actuel et l'ancien
#Calcul de la variance
self.sigma[self.time] = div_t*t*self.sigma[t] \
+ div_t*(tau-self.mu[t])*(tau-self.mu[self.time])
#Décision de tarification provisoire
u = ctr*self.gcpc # Ui = AR*G(CTR prédictif x CPC cible)
#Déterminez le prix en fonction du taux de soumission
# beta1=0.3, beta2=0.Régler sur 8
price = self.get_price(pacing_rate,u)
print 'price1',price
#Jugement sur l'opportunité de soumissionner
return self.judge_bid(pacing_rate,price,tau)
def calc_theta(self,bidprice,secprice):
cdef int b
theta = float(secprice)/bidprice
for b in xrange(100):
if 0.01*b<=theta<=0.01*(b+1):
self.theta[b] += 1
break
def calc_slot_bag(self,pred):
s = sum(pred)
prop = np.array(pred, dtype=DTYPE)/s
return prop*self.daybuget
def get_price(self,pacing_rate,u):
price = 0.0
if pacing_rate<=self.beta1:
s_theta = sum(self.theta)
s = 0.0
for i in xrange(len(self.theta)):
s += self.theta[i]
if float(s)/s_theta>0.01:
return i*(float(3.0)/(2*self.theta_bin))*u #price = self.theta[i]*u
elif pacing_rate>=self.beta2: # pacing_Peut avoir besoin de faire des prédictions de rage
lo =1.0 + (self.bidcap/self.avgprice-1.0)/(1.0-self.beta2) \
*(pacing_rate-self.beta2)
return lo*u
else:
return u
def judge_bid(self, pacing_rate, price, tau):
term2 = self.gamma*self.sigma[self.time]/sqrt(self.day)
print 'tau',tau
if tau<self.mu[self.time]-term2: #Limite de rejet des offres
return False
elif tau>=self.mu[self.time]+term2: #Limite inférieure d'acceptation des offres
return price
else:
if pacing_rate>random.uniform(0,1):
return price
else: return False
La compilation étant requise lors de l'utilisation de Cython, setup.py est également décrit pour le moment.
setup.py
python
# coding: utf-8
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
import numpy as np
setup(
name="CPWOPTcritical",
cmdclass={"build_ext":build_ext},
ext_modules=[Extension("CySimulation",["CySimulation.pyx"])],
include_dirs=[np.get_include()]#Spécifiez le chemin d'inclusion ici
)
De plus, comme il s'agit de Cython, la partie principale est séparée. Il est décrit ci-dessous.
main
python
# coding: utf-8
#import pyximport; pyximport.install()
import io
if __name__=='__main__':
import CySimulation
period = 1440 #Nombre de créneaux par jour
daybuget = 1000000 #Budget quotidien
goalcpc = 100 #CPC cible
bidcap = 90 #Plafond du montant de l'offre
ctrbin = 0.01 #Taille du bac de l'histogramme CTR
days = 2 #Journées de génération de données
user_agent_num = 600 #Nombre d'agents utilisateurs
bid_agent_num = 100 #Nombre d'agents de soumission
bid = CySimulation.ComputeBid(period, daybuget, goalcpc, bidcap,ctrbin)
with io.open('sin_test','a') as f:
bid.output(f,user_agent_num,bid_agent_num,days)
Il semble que cela se passera bien, mais je pense que la valeur à laquelle je m'attendais ne sort pas dans la partie où la génération de données a été omise ou où la partie prédite à partir des données passées a été ignorée. Comme les paramètres sont assez détaillés, il semble difficile d'obtenir des résultats suffisants à moins de les créer avec précision.
C'est une méthode assez heuristique, mais je pense que c'est la méthode la plus utilisable (papier) dans des conditions où une vitesse de 50 ms ou moins est requise en combinaison avec l'estimation CVR. Pour ce travail, le premier article que j'ai lu sur l'optimisation des enchères était celui présenté ci-dessus. J'ai lu d'autres articles, mais celui-ci a eu le plus fort impact. Si des journaux autres que IP et horodatage sont stockés, je souhaitais optimiser avec des données réelles basées sur cette méthode. Je suis désolé.
Si vous trouvez quelque chose d'étrange, nous vous serions reconnaissants de bien vouloir le signaler.