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

• Supposons que vous souhaitiez effectuer une analyse à partir des informations du capteur. ――Il existe des capteurs de 10 000 yens et 30 000 yens, et il y a des moments où vous ne les mettez pas, il y a donc trois types de choix. --Il y a 20 candidats pour l'emplacement d'installation du capteur. ――Le coût d'achat total de tous les capteurs doit être maintenu en dessous de 50000 yens. ――Supposons que vous souhaitiez savoir où et combien de capteurs doivent être placés pour une vérification efficace.

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).

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)

• 1,1,1
• 1,2,2
• 1,3,3
• 2,1,2
• 2,2,3
• 2,3,1
• 3,1,3
• 3,2,1
• 3,3,2

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.

• Seul un nombre spécifique de facteurs et de niveaux peut être utilisé.
• Aucune condition supplémentaire ne peut être considérée.

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

$ 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.