Méthode de planification des expériences et optimisation des combinaisons

Ceci est l'article du troisième jour de Algorithm Advent Calendar 2015.

introduction

Nous présenterons une brève introduction de la méthode de planification expérimentale et une approche par optimisation combinée au fur et à mesure de son développement.

Contexte

A titre d'exemple du cas, «un capteur de 10 000 yens est placé aux points A et B, et un capteur de 30 000 yens est placé au point C».

le terme

Utilisez les termes suivants.

—— Facteur: Le sujet à examiner pour lequel vous souhaitez déterminer le niveau. Cette fois, c'est un candidat pour le placement du capteur. --Level: valeur possible du facteur. Cette fois, il existe trois types de coûts de capteur: 0 000 yens, 10 000 yens et 30 000 yens. --Interaction: L'effet d'un facteur dépend du niveau d'un autre facteur. --Latin Square: une matrice de nombres qui n'a pas les mêmes nombres dans ses lignes ou colonnes. --Méthode de planification expérimentale: une méthode pour mener des expériences efficaces. Ici, nous visons à réduire le nombre de cas.

Cette fois, on suppose qu'il n'y a pas d'interaction.

Comment trouver le nombre de cas à l'aide de la méthode de planification expérimentale.

Outre l'histoire de fond, en tant que théorie générale, je vais montrer un exemple avec 3 types de facteurs et 3 types de niveaux. En termes simples, vous avez besoin de 3 $ ^ 3 = 27 $ autant de cas.

Dans la méthode de planification expérimentale, le nombre de cas peut être créé en fonction du carré latin (illustré ci-dessous).

1 2 3
2 3 1
3 1 2

Si vous utilisez le carré latin, vous pouvez le faire efficacement dans 9 cas comme suit. Ces 9 cas comprennent toutes les combinaisons de facteurs et de niveaux, et le nombre de tous les facteurs et niveaux est le même.

9 cas sélectionnés (niveau pour chaque facteur)

Puisque chacun des 9 carrés du carré latin correspond au cas, considérez le numéro de ligne comme facteur 1, le numéro de colonne comme facteur 2 et le nombre carré comme facteur 3.

Inconvénients de la planification expérimentale

La méthode de planification expérimentale présente les inconvénients suivants.

Penser par optimisation combinée

Dans la méthode de planification expérimentale, après avoir sécurisé un certain nombre de facteurs / niveaux, le nombre de cas a été sélectionné pour être aussi petit que possible. Vous pouvez voir la même chose comme un problème d'optimisation. Plus précisément, spécifiez le nombre minimum d'observations qui incluent chaque niveau de chaque facteur et recherchez la méthode de sélection des observations par optimisation d'entiers mixtes.

Formulation

Fonction objective \sum_i{v_i} Nombre de cas requis
Contraintes \sum_i{\\{C_{ij} v_i | C_{ij} = k\\}} \ge N \forall j \lt 3, \forall k \in \\{0, 1, 3\\} Il doit y avoir au moins le nombre minimum de cas pour chaque facteur et chaque niveau
variable v_i \in \\{0, 1\\} \forall i \lt Nombre total de cas S'il faut sélectionner pour chaque cas

$ C_ {ij} $ représente le $ j $ ème niveau dans le cas $ i $ ème, et $ N $ représente le nombre minimum.

En utilisant Python, il peut être calculé comme suit. (On suppose que la variable cas contient le total des cas avec un coût d'achat de 50000 yens ou moins.)

python


from pulp import *
r = [0, 1, 3] #niveau
for N in [20, 40, 60, 120]: #Nombre minimum
    m = LpProblem()
    v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cases))]
    m += lpSum(v)
    for j in range(len(cases[0])):
        for k in r:
            m += lpSum(v[i] for i in range(len(cases)) if cases[i][j] == k) >= N
    m.solve()
    print(N, LpStatus[m.status], value(m.objective)) #Nombre minimum, statut, nombre de cas

résultat

Comparons-le avec le cas de l'échantillonnage aléatoire. Le nombre minimum d'échantillons aléatoires est une valeur approximative obtenue dans la simulation. Vous pouvez voir que le cas pourrait être sélectionné efficacement en utilisant l'optimisation de combinaison.

Nombre minimum Optimisation des combinaisons Échantillonnage aléatoire
20 400 caisses Caisse 3200
40 800 caisses 5700 cas
60 1200 caisses 7900 cas
120 Caisse 2400 14400 caisse

Recommended Posts

Méthode de planification des expériences et optimisation des combinaisons
La puissance des solveurs d'optimisation combinée
Séparation de la conception et des données dans matplotlib
Utiliser l'optimisation des combinaisons
Problème de fractionnement typique de la combinaison de problèmes
Trouver la main de "Millijan" par l'optimisation des combinaisons
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Optimisation du regroupement par combinaison
Décidons la position du service d'incendie par optimisation combinée
Mécanisme de pyenv et virtualenv
Pré-traitement et post-traitement de pytest
Enquête Star avec optimisation des combinaisons
Cohérence de la conception de l'API scikit-learn
Combinaison de récursif et de générateur
Jeux de regroupement avec optimisation des combinaisons
Combinaison de anyenv et direnv
Explication et mise en œuvre de SocialFoceModel
Différenciation du tri et généralisation du tri
Coexistence de pyenv et autojump
Utilisation et intégration de "Shodan"
Le problème des menteurs et de l'honnêteté
Apprentissage automatique et optimisation mathématique
Occurrence et résolution de tensorflow.python.framework.errors_impl.FailedPreconditionError
Comparaison d'Apex et de Lamvery
Installation source et installation de Python
Introduction et astuces de mlflow.
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée