Cet article est l'article du 7ème jour du "Calendrier de l'Avent 2019 d'intelligence et d'optimisation de groupe". N'est-ce pas cool avec le chaos ou l'AIWF? Alors j'ai enquêté et mis en œuvre.

Aperçu

L'optimisation de l'essaim de particules chaotiques (CPSO) est un algorithme d'optimisation qui incorpore le chaos dans PSO, qui est l'un des algorithmes méta-heuristiques. Comme d'autres algorithmes PSO, il existe de nombreuses variantes, mais l'article sous-jacent (https://www.sciencedirect.com/science/article/abs/pii/S0960077905000330) a été publié en 2005. .. Dans cet article, j'ai implémenté CPSO en Python et l'ai évalué avec une fonction de référence, je vais donc le résumer.

Algorithme et implémentation

CPSO est mis en œuvre approximativement par la procédure suivante.

Exécution PSO (utilisant AIWF * en poids)
Extraire les 1/5 premières particules
Effectuer CLS * sur les particules extraites pour mettre à jour la position
Réduisez la plage de recherche en fonction des informations de localisation de la particule qui a exécuté CLS
Régénérez aléatoirement les 4/5 particules inférieures de la nouvelle plage de recherche
Évaluez chaque particule et si la condition d'arrêt est remplie, terminez, sinon, revenez à 1.

AIWF (facteur d'inertie adaptative): facteur d'inertie adaptative. Une méthode proposée pour le coefficient d'inertie, qui est l'un des paramètres de PSO.
CLS (Chaotic Local Search): Recherche locale chaotique. Méthode proposée utilisée pour la recherche locale après l'exécution du PSO.

Dans l'article, seule la partie principale est codée. L'ensemble du code est disponible sur GitHub. https://github.com/TatsukiSerizawa/Meta-heuristic/blob/master/cpso.py

1. Exécutez PSO

Tout d'abord, lancez PSO. PSO trouve la solution optimale en mettant à jour chaque particule avec la position actuelle $ x $ et la vitesse $ v . La vitesse et la position de chaque particule en mouvement sont mises à jour par la formule suivante. $ v_{id}(t+1) = w_{id}(t) + c_p × r_p × (pBest_{id} - x_{id}(t)) + c_g × r_g × (gBest_{id} - x_{id}(t)) $ $ x_{id}(t+1) = x_{id}(t) + v_{id}(t+1) $$ Ici, la meilleure position trouvée par chacun est appelée le record personnel (pBest), et la meilleure position de l'ensemble du groupe est appelée le meilleur global (gBest). De plus, $ v_ {id} $ est la vitesse de la i-ème particule de d-dimension, $ x_ {id} $ est la position de la i-ème particule de d-dimension, $ w $ est le coefficient d'inertie, $ c_p $, $ c_g $ Est une constante appelée coefficient d'accélération, $ r_p $ et $ r_g $ sont des nombres aléatoires de 0 à 1. AIWF est utilisé pour le coefficient d'inertie, qui est un paramètre, et une constante de 2,0, qui est couramment utilisée, est spécifiée pour le coefficient d'accélération. En particulier, on dit que le coefficient d'inertie a un effet important sur les résultats, et plus la valeur est élevée, plus il est efficace pour la recherche globale, mais il y a le problème qu'il ne convient pas à la recherche locale. Par conséquent, AIWF répond au problème en modifiant la valeur de chaque particule. Le coefficient d'inertie w dans AIWF peut être calculé par la formule suivante.

w= \left\\{ \begin{array}{} \frac{(w\_{max} - w\_{min})(f-f\_{min})}{(f\_{avg}-f\_{min})}, \( f \leq f\_{avg}) \\\ w\_{max}, \( f > f\_{avg}) \end{array} \right.

Code AIWF

def aiwf(scores, W):
    for s in range(SWARM_SIZE):
        if scores[s] <= np.mean(scores):
            W[s] = (np.min(W) + (((np.max(W) - np.min(W)) * (scores[s] - np.min(scores))) / 
                    (np.mean(scores) - np.min(scores))))
        else:
            W[s] = np.max(W)
    return W

2. Extraire les 1/5 premières particules

Afin de décider de la particule pour effectuer CLS, le top 1/5 avec le meilleur score à la suite de PSO est extrait.

3. Effectuer CLS sur les particules extraites et mettre à jour la position

La recherche locale est effectuée par CLS. Lorsque $ x $ est la position de chaque particule, CLS est exécuté selon la procédure suivante.

Trouvez $ cx \ _ {i} ^ {(k)} $ $ \displaystyle cx_i^{(k)}= \frac{x\_{i}-x\_{max,i}}{x\_{max,i}-x\_{min,i}} $
Trouvez $ cx \ _ {i} ^ {(k + 1)} $ basé sur $ cx \ _ {i} ^ {(k)} $ $ cx\_{i}^{(k+1)}= 4cx\_{i}^{(k)}(1-4cx\_{i}^{(k)}) $
Trouvez et évaluez la position $ x \ _ {i} ^ {(k + 1)} $ en fonction de $ cx \ _ {i} ^ {(k + 1)} $ $ x\_{i}^{(k+1)}= x\_{min,i}+cx\_{i}^{(k+1)}(x\_{max,i}-x\_{min,i}) $
Si le nouveau résultat de l'évaluation est meilleur que $ X ^ {(0)} = [x \ _ {1} ^ {0}, ..., x \ _ {n} ^ {0}] $, ou itération maximale Lorsque le nombre est atteint, le résultat est sorti. Sinon, revenez à 2.

Code CLS

def cls(top_scores, top_positions):
    cx, cy = [], []

    min_x, min_y = min(top["x"] for top in top_positions), min(top["y"] for top in top_positions)
    max_x, max_y = max(top["x"] for top in top_positions), max(top["y"] for top in top_positions)
    
    for i in range(len(top_scores)):
        cx.append((top_positions[i]["x"] - min_x) / (max_x - min_x))
        cy.append((top_positions[i]["y"] - min_y) / (max_y - min_y))

    for i in range(K):
        logistic_x = []
        logistic_y = []
        chaotic_scores = []
        chaotic_positions = []
        for j in range(len(top_scores)):
            logistic_x.append(4 * cx[j] * (1 - cx[j]))
            logistic_y.append(4 * cy[j] * (1 - cy[j]))
            #Mettre à jour la position
            chaotic_x, chaotic_y = chaotic_update_position(logistic_x[j], logistic_y[j], min_x, min_y, max_x, max_y)
            chaotic_positions.append({"x": chaotic_x, "y": chaotic_y})
            #évaluation des notes
            chaotic_scores.append(evaluation(chaotic_x, chaotic_y))
        #Renvoie une valeur si le nouveau score est meilleur que le précédent, sinon cx,Mettre à jour cy et répéter
        if min(chaotic_scores) < min(top_scores):
            print("Better Chaotic Particle found")
            return chaotic_scores, chaotic_positions
        cx = logistic_x
        cy = logistic_y
    return chaotic_scores, chaotic_positions

#Mise à jour de la position chaotique
def chaotic_update_position(x, y, min_x, min_y, max_x, max_y):
    new_x = min_x + x * (max_x - min_x)
    new_y = min_y + y * (max_y - min_y)
    return new_x, new_y

4. Réduisez la plage de recherche en fonction des informations de localisation de la particule qui a exécuté CLS

Réduisez la plage de recherche suivante en fonction des résultats CLS. Sur la base des informations de position de la particule à l'aide de CLS, spécifiez à nouveau la plage de recherche à l'aide de la formule suivante. Cependant, lorsqu'elle est mise en œuvre comme décrit dans l'article, si la valeur maximale parmi plusieurs valeurs minimales est utilisée pour la valeur minimale et si la valeur minimale parmi plusieurs valeurs minimales est utilisée pour la valeur maximale, la valeur minimale et la valeur maximale seront Puisqu'il a été inversé, l'implémentation a utilisé la valeur minimale pour la valeur minimale et la valeur maximale pour la valeur maximale pour élargir la plage de recherche.

Code de réduction de la plage de recherche

def search_space_reduction(top_positions):
    min_x, min_y, max_x, max_y = [], [], [], []

    min_x.append(min(top["x"] for top in top_positions))
    min_y.append(min(top["y"] for top in top_positions))
    max_x.append(max(top["x"] for top in top_positions))
    max_y.append(max(top["y"] for top in top_positions))
    x = [top.get("x") for top in top_positions]
    y = [top.get("y") for top in top_positions]
    
    for i in range(len(top_positions)):
        min_x.append(x[i] - R * (max_x[0] - min_x[0]))
        min_y.append(y[i] - R * (max_y[0] - min_y[0]))
        max_x.append(x[i] + R * (max_x[0] - min_x[0]))
        max_y.append(y[i] + R * (max_y[0] - min_y[0]))
    
    #Selon le papier nouveau_min_x = max(min_x)Si vous le définissez sur, la valeur minimale et la valeur maximale seront inversées, corrigez-la.
    new_min_x, new_min_y = min(min_x), min(min_y)
    new_max_x, new_max_y = max(max_x), max(max_y)
    search_space_x = {"min": new_min_x, "max": new_max_x}
    search_space_y = {"min": new_min_y, "max": new_max_y}

    return search_space_x, search_space_y

5. Régénérez aléatoirement les 4/5 particules inférieures de la nouvelle plage de recherche

Étant donné que les particules 4/5 inférieures ne rentrent pas dans la nouvelle plage de recherche réduite, créez-en une nouvelle afin qu'elle tienne dans la plage. Les particules sont générées de manière aléatoire comme dans les paramètres initiaux.

6. Évaluez chaque particule et si la condition d'arrêt est remplie, terminez, sinon, revenez à 1.

Évaluez chaque particule. A ce moment, si le score est meilleur que le score défini à l'avance comme valeur de seuil, ou si le nombre maximum de recherches est atteint, la recherche se termine et le résultat est sorti. Si les conditions ne sont pas remplies, revenez à 1. et exécutez depuis PSO pour continuer la recherche.

Résultat de l'évaluation avec fonction de référence

Il existe de nombreuses fonctions de référence comme fonctions d'évaluation de l'algorithme d'optimisation. L'article de Tomitomi3 présente une introduction détaillée à la fonction de référence. Cette fois, j'ai utilisé la fonction Sphère introduite ici. La solution optimale pour cette fonction est $ f \ _ {min} (0, ..., 0) = 0 $.

Cette fois, la condition de fin était Score <1.000e-15 ou 10 itérations. En conséquence, nous avons pu observer comment il convergeait comme le montre la figure.

De plus, les résultats lors de l'exécution sans dessin d'image et lors de l'exécution d'un PSO simple sont les suivants. Si la précision est améliorée par CLS, le score est également mis à jour, et si la précision n'est pas améliorée, le score avant CLS est repris. Vous pouvez voir que la plage de recherche a été réduite à chaque fois et que le score s'est amélioré. De plus, comparé au résultat de l'exécution uniquement du PSO ci-dessous, on peut voir que la précision est améliorée, mais cela prend du temps.

CPSO log and result

Lap: 1
CLS:
before: 1.856166459555566e-09
after: 1.7476630375799616e-07
Search Area:
before
x: {'min': -5.0, 'max': 5.0}
y: {'min': -5.0, 'max': 5.0}
after
x: {'min': -0.0010838869646188037, 'max': 0.0013954791030881871}
y: {'min': -0.001201690486501598, 'max': 0.0016078160576153975}
Score: 1.856166459555566e-09

Lap: 2
CLS:
before: 2.0926627088682597e-13
Better Chaotic Particle found
after: 7.821496571701076e-14
Search Area:
before
x: {'min': -0.0010838869646188037, 'max': 0.0013954791030881871}
y: {'min': -0.001201690486501598, 'max': 0.0016078160576153975}
after
x: {'min': -7.880347663659637e-06, 'max': 1.5561134225910913e-05}
y: {'min': -1.83517959693168e-05, 'max': 1.853229861175588e-05}
Score:   7.821496571701076e-14

Lap: 3
CLS:
before: 6.562680339774457e-17
Better Chaotic Particle found
after: 5.0984844476716916e-17
Search Area:
before
x: {'min': -7.880347663659637e-06, 'max': 1.5561134225910913e-05}
y: {'min': -1.83517959693168e-05, 'max': 1.853229861175588e-05}
after
x: {'min': -3.794413350751951e-07, 'max': 1.6057623588141383e-07}
y: {'min': -2.7039514283878003e-07, 'max': 8.373690854089289e-08}
Score:   5.0984844476716916e-17

Best Position: {'x': 6.92085226884776e-09, 'y': 1.7568859807915068e-09}
Score: 5.0984844476716916e-17
time: 0.7126889228820801

PSO result

Best Position: {'x': -0.23085945825227583, 'y': -0.13733679597570791}
Score: 4.218973135139706e-06
time: 0.006306886672973633

Résumé

En expérimentant cette fois, j'ai pu connaître la précision et le temps d'exécution de CPSO. Cette fois, je l'ai évalué avec une fonction simple avec une solution optimale (monomodale), mais j'aimerais étudier s'il y a une opportunité de l'évaluer avec une fonction multimodale.

[PYTHON] Évaluez les fonctions de référence avec Chaotic PSO