How to implement chicken flock algorithm in Python

Algorithm Introduction

Chicken Swarm Optimization, abbreviated as CSO (Chicken Swarm Optimization), although it has a background in so-called bionics, is essentially a variant of the particle swarm algorithm.

Simply speaking, a particle swarm is a group of particles. Each particle has its own position and speed, and each particle must be attracted by the best particle. In addition to these two rules, the particles They are completely equal to each other, except for their position and speed.

Of course, the particle swarm algorithm itself also has a bionics background. It is said that the inspiration comes from a flock of birds foraging. This is of course not important. It is nothing more than a group of equal particles turning into a group of equal birds.

The chicken flock algorithm adds different identity characteristics to these particles, or these birds, so that they are no longer equivalent to each other.

There are at least three classes in the chicken flock, namely roosters, hens and chicks. Each chicken has its own position and speed. But the difference is that the

• rooster is the most majestic. In principle, it can walk around at will. But sometimes when it notices other roosters, it will have the idea of ​​​​grabbing for food, which is equivalent to randomness. Drawing one of the other roosters affects its position.

• The hens are the most aggrieved. On the one hand, they have to accept the leadership of the rooster, and on the other hand, they have to compete with other hens for food.

• 小Chickens are the most carefree, just follow the hens.

As the positional relationship changes, hens and chicks may gradually forget the original leader, which means that the population relationship may change.

Python implements chickens and chicken flocks

First of all, we need to implement a chicken class. A chicken has two basic attributes, namely location and category.

import numpy as np
from random import gauss, random
randint = np.random.randint
uniRand = np.random.uniform

class Chicken:
    def __init__(self, N, xRange, order=0, kind=0):
        # 生成(N)维参数
        self.x = uniRand(*xRange, (N,))
        self.best = np.inf
        self.xBest = np.zeros((N,))
        self.kind = kind            # 鸡的类别
        self.order = order          # 鸡的编号
    
    # 设置自己的首领公鸡
    def setCock(self, i):
        self.cock = i

    # 设置自己的监护母鸡
    def setHen(self, i):
        self.hen = i

Kind is divided into three categories, namely roosters, hens and chicks. Among them, each hen has its own alpha rooster, and each chick has its own guardian hen.

order is the number of this chicken in the chicken flock, which is mainly reflected in the chicken flock.

There is a big difference between a chicken flock and a particle swarm. In the end, there is only one flock. In a chicken flock, each rooster has its own hens and chicks, which is equivalent to a small group. However, the relationship between chickens does not depend on the chickens themselves, so it needs to be implemented in the chicken flock

randint = np.random.randint
class Swarm:
    # cNum 鸡数，是三个元素的列表，分别是公鸡、母鸡和小鸡数
    # N参数维度
    def __init__(self, cNum, N, xRange):
        self.initCs(cNum, N, xRange)
        self.bestCS = deepcopy(self.cs)     #最佳鸡群
        self.best = np.inf  #全局最优值
        self.xBest = np.zeros((N,)) #全局最优参数
        self.N = N

    def initCs(self, cNum, N, xRange, vRange):
        self.cs = []
        self.cNum = cNum
        self.cocks = np.arange(cNum[0])     # 公鸡编号
        self.hens = np.arange(cNum[0], cNum[0]+cNum[1]) #母鸡编号
        self.chicks = np.arange(cNum[0]+cNum[1], np.sum(cNum))  #小鸡编号
        kinds = np.repeat([0,1,2], cNum)
        for i in range(sum(cNum)):
            self.cs.append(Chicken(N,xRange, vRange, i, kinds[i]))
            if kinds[i] > 0:
                cock = randint(0, cNum[0])
                self.cs[i].setCock(cock)
            if kinds[i] > 1:
                hen = randint(cNum[0], cNum[0]+cNum[1])
                self.cs[i].setHen(hen)

Among them, initCs is the function that initializes the chicken flock, in which the hen and the leader of the chickens, the rooster, The chicks' guardian hens are randomly generated.

Chicken flock update

The next step is the core part of the algorithm. Different chickens must follow different update rules. Among them, the rooster is the coolest, and its next position only depends on itself and other chickens. A randomly selected rooster.

cock

Remember that the number of the current rooster is i, and the number of the randomly selected rooster is j, j≠i, then the update method of the position of the i-th rooster is

x_i(t 1)=x_i(t)⋅(1 r)

where, r is generated through normal distribution The random number can be expressed as 1∼N(0,σ²), where σ² is

Among them, f is generally called the fitness factor, which is equivalent to the value obtained by stuffing a certain chicken into the function to be searched. For example, if you want to search for the minimum value of y=², if the current position of the chicken is 1.5, then f=1.5²=2.25. ε is a small amount that prevents division-by-zero errors.

But it should be noted that all x above do not represent a scalar, but an array.

The Python implementation is

# 写在Swarm类中
def cockStep(self):
    for i in self.cocks:
        # 第j只公鸡
        j = np.random.randint(self.cNum[0])
        if j==i:
            j = (j+1) % self.cNum[0]
        # 第i只公鸡
        ci = self.cs[i]
        # 第j只公鸡
        cj = self.cs[self.cocks[j]]
        sigma = 1 if cj.best > ci.best else np.exp(
            (cj.best-ci.best)/(np.abs(ci.best)+1e-15))
        ci.x *= 1 + gauss(0, sigma)

Hen

Suppose the current hen number is i. This hen must not only follow the leader rooster, but also Competing with other hens for food.

x_i(t 1)=x_i(t) k₁r₁(x_c−x_i) k₂r₂(x_j−x_i)

Among them, x_c is the leader rooster, and x_j is another hen or rooster. k₁,k₂ are coefficients, and their update logic is the same as that of rooster. When f_i is larger, it is expressed as

The code is implemented as

def henStep(self):
    nGuarder = self.cNum[0] + self.cNum[1] - 2
    for i in self.hens:
        guarders = list(self.cocks) + list(self.hens)
        c = self.cs[i].cock     #首领公鸡
        guarders.remove(i)
        guarders.remove(c)
        # 随机生成另一只监护鸡
        j = guarders[np.random.randint(nGuarder)]
        ci = self.cs[i]
        cj = self.cs[j]
        cc = self.cs[c]
        k1, k2 = random(), random()
        if cc.best > ci.best:
            k1 *= np.exp((ci.best-cc.best)/(np.abs(ci.best)+1e-15))
        if cj.best < ci.best:
            k2 *=  np.exp(cj.best-ci.best)
        ci.x += k1*(cc.x-ci.x)+k2*(cj.x-ci.x)

小鸡

The last is the update logic of the chicken. The chicken looks around the hen Food, its update logic is

x_i(t 1)=x_i(t) r(x_h(t)−x_i(t))

Among them, x_h is the guardian hen, r is a random number, and the algorithm is implemented as

def chickStep(self):
    for i in self.chicks:
        ci = self.cs[i]
        ci.x += 2*random()*(self.cs[ci.hen].x-ci.x)

for the whole chicken Group

As the saying goes, algorithms originate from life and are higher than life. In nature, seniority is emphasized, but in the chicken flock algorithm, strength is indeed the emphasis. If the chicken is lucky and gets better optimization results than the rooster, then the chicken will evolve into a rooster.

In other words, every once in a while, the identities of the chickens in the flock will be rearranged. The one with the best optimization effect is the leader rooster, the worse one is the guardian hen, and the worst one can only be the rooster. Chicken now.

def update(self):
    cn = np.sum(self.cNum)
    c1, c2 = self.cNum[0], self.cNum[0]+self.cNum[1]
    fitness = [self.cs[i].best for i in range(cn)]
    index = np.argsort(fitness)
    self.cocks = index[np.arange(c1)]
    self.hens = index[np.arange(c1,c2)]
    self.chicks = index[np.arange(c2,cn)]
    for i in self.cocks:
        self.cs[i].kind = 0
    for i in self.hens:
        self.cs[i].kind = 1
    for i in self.chicks:
        self.cs[i].kind = 2
    for i in range(cn):
        if self.cs[i].kind > 0:
            cock = self.cocks[randint(0, c1)]
            self.cs[i].setCock(cock)
        if self.cs[i].kind > 1:
            hen = self.hens[randint(c1,c2)]
            self.cs[i].setHen(hen)

Optimization iteration

At this point, the framework of the cluster algorithm has been successfully established. Next, the most critical part, optimization, will be implemented.

其基本逻辑是，输入一个待优化func，通过将每只鸡的位置x带入到这个函数中，得到一个判定值，最后通过这个判定值，来不断更新鸡群。

除了这个函数之外，还需要输入一些其他参数，比如整个鸡群算法的迭代次数，以及鸡群更新的频次等等

# func为待优化函数
# N为迭代次数
# T为鸡群更新周期
def optimize(self, func, N, T, msgT):
    for n in range(N):
        # 计算优化参数
        for c in self.cs:
            c.best = func(c.x)
        # 分别更新公鸡、母鸡和小鸡
        self.cockStep()
        self.henStep()
        self.chickStep()
        if (n+1)%T == 0:
            self.update()   #每T次更新一次种群
            self.printBest(n)
    self.printBest(n)

其中，printBest可以将当前最佳结果打印出来，其形式为

def printBest(self,n):
    fitness = [c.best for c in self.cs]
    best = np.min(fitness)
    ind = np.where(fitness==best)[0]
    msg = f"已经迭代{n}次，最佳优化结果为{np.min(fitness)}，参数为：\n"
    msg += ", ".join([f"{x:.6f}" for x in self.cs[ind].x])
    print(msg)

测试

算法完成之后，当然要找个函数测试一下，测试函数为

def test(xs):
    _sum = 0.0
    for i in range(len(xs)):
        _sum = _sum + np.cos((xs[i]*i)/5)*(i+1)
    return _sum

if __name__ == "__main__":
    cNum = [15,20,100]
    s = Swarm(cNum, 5, (-5,5))
    s.optimize(test, 20, 5)

测试结果如下

已经迭代4次，最佳优化结果为-5.793762423022024，参数为：
-6.599526, 3.117137, 5.959538, 7.225785, 5.204990
已经迭代9次，最佳优化结果为-10.61594651972434，参数为：
-7.003724, -5.589730, 0.981409, 12.920325, -19.006112
已经迭代14次，最佳优化结果为-9.143596747975293，参数为：
5.388234, -3.714421, -5.254391, -5.216215, -6.079223
已经迭代19次，最佳优化结果为-11.097888385616995，参数为：
-9.156244, -5.914600, -5.960154, 4.550833, 4.127889
已经迭代19次，最佳优化结果为-11.097888385616995，参数为：
-9.156244, -5.914600, -5.960154, 4.550833, 4.127889

The above is the detailed content of How to implement chicken flock algorithm in Python. For more information, please follow other related articles on the PHP Chinese website!