用人工鱼群算法优化参数并可视化

APSchmidt

0引言
在对事物建模，也就是用模型取描述事物的规律的时候，我们经常需要确定模型的参数。比如使用多元线性回归模型刻画人的(性别,年龄,身高)与体重的关系，实际上就是要确定3个自变量的系数和1个偏置。
怎么确定这个参数呢？我们可以设计一个函数，对参数的质量进行评价，然后通过改变参数来使这个评价函数的取值达到最大(或者最小)——此时，我们就得到了最好的参数。这个评价函数就是我们常听说的损失函数；而改变参数来使损失函数取得极值的操作，叫做优化。
在深度学习时代，梯度下降及其变种是最常见的优化算法。这些算法的特点是，基于损失函数的偏导数来计算参数变化的方向和步长，进而实现参数的改变。
损失函数不可导的情况下应该怎么办呢？比如我们要求这个函数的最大值:


这个函数表示一个三维空间中的曲面，而这个曲面是由两块平滑的曲面拼接起来的——接缝处是不可导的，没法求梯度。这时候，我们可以考虑使用人工鱼群算法来优化。
1人工鱼群算法的初级版本
            人工鱼群算法是李晓磊在2002年提出的一种仿生算法，主要用来做最优化。李晓磊做了一个假设，即鱼会尽可能地多吃来提升自己的生存率。然后他用一个简单的机制来刻画鱼的行为模式：为了找到更多的食物，鱼儿会在水里不断地寻找食物较多的地方。该机制的核心要素是两个：（1）鱼的游动；（2）食物浓度函数，即损失函数。如表1-1，是该算法的概念与其他场景里涉及的概念的对应关系。
                                        表1-1 概念对应关系


在参数优化的场景里，一条鱼会为了找到食物浓度最高的地方，在水体(也就是参数空间)里不断地游动，直到达成迭代终止条件。
1.1simple鱼的行为模式
为了多吃，一条鱼会依赖自己的器官判断水里食物的浓度，然后向食物浓度更高的地方游动。
1.2食物浓度函数
食物在水体中的浓度分布，决定了鱼群最终在水体中的大致位置。如何描述这个分布呢？用食物浓度函数。
食物浓度函数以水体位置为自变量、食物浓度值为因变量：


一条鱼的位置，就是我们要优化的参数向量。
1.3用简单的鱼群算法来函数极值
人工鱼群算法相对于梯度下降的一个缺点，就是无法用简单的符号来表达迭代过程，必须用较多的语言，所以有点抽象。这里直接用代码来展示人工鱼群算法里，鱼和鱼群是如何存在的。
假设我们要优化的是如下一个简单的函数:


我们可以使用如下代码求这个函数的最大值。
'''
Created on 2019年9月11日

@author: Administrator
'''
#人工鱼群算法
import numpy as np
import matplotlib.pyplot as plt

#第一阶段的人工鱼群只有追寻食物的机制。只让人工鱼寻找食物浓度最高的位置，就可以实现对一些的损失函数的优化了。
class AFish():
   
    def __init__(self):
        self.location = None#描述鱼在参数空间中位置的向量
        self.current_food_density = None
        
class AFSA():
   
    def __init__(self, fish_num = 100, location_dim=2, visual=0.01, try_num_searching_food=3):
        self.location_dim = location_dim
        self.fishes = None
        self.bulletin_fish = None
        self.visual = visual#所有鱼的视野范围。可以为每条鱼设置不同的视野大小，模拟个体差异
        self.try_num_searching_food = try_num_searching_food#多试几次有助于找到更好的方向。
        self.create_fishes(fish_num, location_dim)

        
    def food_density(self, location):
        x, y = location
        score = -(x**2+y**2 +2*y)#z=x**2+y**2 +2*y,需要加一个符号，让函数是凸的。如果需要优化的目标函数比较复杂，就没有这么直观了。
        return score
   
    def distance(self, location1, location2):
        return np.dot(location1, location2)
   
    #生成一个步长，目标是视野范围内的随机一个点
    def generate_a_step(self):
        step_vector = np.random.uniform(-self.visual, self.visual, self.location_dim)
        return step_vector
   
    def create_fishes(self, fish_num, location_dim):
        self.fishes = []
        for _ in range(fish_num):
            a_fish = AFish()
            a_fish.location = np.random.random(location_dim)
#             print("a_fish.location", a_fish.location)
            a_fish.current_food_density = self.food_density(a_fish.location)
            self.fishes.append(a_fish)
            if self.bulletin_fish==None:
                self.bulletin_fish = a_fish
            else:
                if a_fish.current_food_density > self.bulletin_fish.current_food_density:
                    self.bulletin_fish = a_fish
           
    def search_food(self, fish):
        for _ in range(self.try_num_searching_food):
            new_location = fish.location + self.generate_a_step()
            new_density = self.food_density(new_location)
            concentration = self.food_density(fish.location)
            if  new_density > concentration:
                fish.location = new_location
                concentration = new_density
            if concentration > self.bulletin_fish.current_food_density:
                self.bulletin_fish = fish
            
    #更新一条鱼的状态，并更新公示板        
    def update_a_fish(self, fish):
        self.search_food(fish)#模拟一条鱼找食物的动作
        
    def fit(self ,epoch_num=1000):
        
        #########将寻优过程可视化，不是必须的#########
        self.fig = plt.figure()
        self.ax = self.fig.add_subplot(1,1,1)
        x = list(map(lambda x: x.location[0], self.fishes))
        y = list(map(lambda x: x.location[1], self.fishes))
        self.ax.scatter(x, y)
        plt.ion()
        ############可视化部分####################
        
        for epoch in range(epoch_num):
            for fish in self.fishes:
                self.update_a_fish(fish)
            print("轮次是", epoch)
            print(self.bulletin_fish.location)
            
            self.show_locations()#可视化

    #把所有鱼的位置变化展示出来，参考了https://blog.csdn.net/omodao1/article/details/81223240
    def show_locations(self):
        x = list(map(lambda x: x.location[0], self.fishes))
        y = list(map(lambda x: x.location[1], self.fishes))
        try:
            self.ax.lines.remove(self.lines[0])
        except Exception as e:
            print(e)
        self.lines = self.ax.plot(x ,y, '*')
        plt.pause(0.1)

if __name__ == '__main__':
    afsa = AFSA()
    afsa.fit(epoch_num=1000)算法迭代的过程中，鱼群位置变化如图1-1,1-2,1-3。蓝色圆点是鱼的初始位置，五角星是实时显示的位置。我们可以看到，鱼群逐渐炒事食物浓度最高的地方聚集。



图1-2 迭代初期



图1-2 迭代中期



图1-3 最终状态

2人工鱼群算法的升级版本
前面提到的人工鱼有若干缺陷：（1）收敛速度慢；（2）容易收敛在局部最优。为此，通常需要设计一些策略来提升算法的性能。常见的策略就是让鱼有随机游动行为，以提升跳出局部最优的能力；让鱼有句群行为，提升收敛速度；让鱼有追随其他鱼的行为，提升收敛速度。
'''
Created on 2019年9月11日

@author: Administrator
'''
#人工鱼群算法
import numpy as np
import matplotlib.pyplot as plt

#第一阶段的人工鱼群只有追寻食物的机制。只让人工鱼寻找食物浓度最高的位置，就可以实现对一些的损失函数的优化了。
class AFish():
   
    def __init__(self):
        self.location = None#描述鱼在参数空间中位置的向量
        self.current_food_density = None

#一个鱼群
class AFSA():
   
    def __init__(self, fish_num = 100, location_dim=2, visual=0.01, try_num_searching_food=3):
        self.location_dim = location_dim
        self.fishes = None#存储鱼实例列表
        self.bulletin_fish = None#公告牌，存储混的最好的鱼的信息
        self.visual = visual#所有鱼的视野范围。可以为每条鱼设置不同的视野大小，模拟个体差异
        self.try_num_searching_food = try_num_searching_food#多试几次有助于找到更好的方向。
        self.max_fish_in_vision = 5#视野内鱼的最大个数，用于限制鱼的密度
        self.create_fishes(fish_num, location_dim)
        
    def food_density(self, location):
        x, y = location
        score = -(x**2+y**2 +2*y)#z=x**2+y**2 +2*y,需要加一个符号，让函数是凸的。如果需要优化的目标函数比较复杂，就没有这么直观了。
        return score
   
    def distance(self, location1, location2):
        return np.dot(location1, location2)
   
    #生成一个步长，目标是视野范围内的随机一个点
    def generate_a_step(self):
        step_vector = np.random.uniform(-self.visual, self.visual, self.location_dim)
        return step_vector
   
    #生成一个鱼群
    def create_fishes(self, fish_num, location_dim):
        self.fishes = []
        for _ in range(fish_num):
            a_fish = AFish()
            a_fish.location = np.random.random(location_dim)#随机制定初始位置
#             print("a_fish.location", a_fish.location)
            a_fish.current_food_density = self.food_density(a_fish.location)
            self.fishes.append(a_fish)
            if self.bulletin_fish==None:
                self.bulletin_fish = a_fish
            else:#如果这条鱼混的比公告牌上的肥鱼还要好，那么它上位
                if a_fish.current_food_density > self.bulletin_fish.current_food_density:
                    self.bulletin_fish = a_fish
                    
    #模拟鱼无目的的游动
    def random_move(self, fish):
        new_location = fish.location + self.generate_a_step()
        new_density = self.food_density(new_location)
        fish.location = new_location
        fish.current_food_density = new_density
   
    #模拟鱼朝向事物较多的方向游动
    def search_food(self, fish):
        for _ in range(self.try_num_searching_food):#试几次
            new_location = fish.location + self.generate_a_step()
            new_density = self.food_density(new_location)
            concentration = self.food_density(fish.location)
            if  new_density > concentration:
                fish.location = new_location
                concentration = new_density
            if concentration > self.bulletin_fish.current_food_density:
                self.bulletin_fish = fish
   
    #模拟鱼向鱼多的地方游动——食物多的地方，鱼就多。大体上，鱼多的地方，食物也许也多，值得赌一把
    def swarm(self, fish):
        fish_location_in_vision = []
        for a_fish in self.fishes:
            if self.distance(fish.location, a_fish.location) < self.visual:
                fish_location_in_vision.append(a_fish.location)
        if 0 < len(fish_location_in_vision) < self.max_fish_in_vision:
            center = np.mean(fish_location_in_vision)
            a_step_to_center = center - fish.location
            fish.location = fish.location + a_step_to_center*np.random.uniform(0, 1)
            #fish.location = (1 - np.random.uniform(0, 1)) + center
            fish.current_food_density = self.food_density(fish.location)
   
    #追尾行为。这里重复计算，一遍展示过程
    def follow(self, fish):
        fatest_fish_in_vision = None
        fish_num_in_vision = 0
        for a_fish in self.fishes:
            if self.distance(a_fish.location, fish.location)<self.visual:
                fish_num_in_vision += 1
                if fatest_fish_in_vision==None or self.food_density(a_fish.location) > self.food_density(fatest_fish_in_vision.location):
                    fatest_fish_in_vision = a_fish
        if fatest_fish_in_vision!=None and fish_num_in_vision<self.max_fish_in_vision:
            a_step_to_fatest = fatest_fish_in_vision.location - fish.location
            fish.location = fish.location + a_step_to_fatest*np.random.uniform(0, 1)
            #fish.location = (1 - np.random.uniform(0, 1)) + center
            fish.current_food_density = self.food_density(fish.location)  
            
    #更新一条鱼的状态，并更新公示板        
    def update_a_fish(self, fish):
        self.search_food(fish)#模拟一条鱼找食物的动作
#         self.swarm(fish)
#         self.follow(fish)
#         self.random_move(fish)#假如鱼没有觅食、追尾或者聚群，就随机移动一下。
        
    def fit(self ,epoch_num=1000):
        
        #########将寻优过程可视化，不是必须的#########
        self.fig = plt.figure()
        self.ax = self.fig.add_subplot(1,1,1)
        x = list(map(lambda x: x.location[0], self.fishes))
        y = list(map(lambda x: x.location[1], self.fishes))
        self.ax.scatter(x, y)
        plt.ion()
        ############可视化部分####################
        
        for epoch in range(epoch_num):
            for fish in self.fishes:
                self.update_a_fish(fish)
            print("轮次是", epoch)
            print(self.bulletin_fish.location)
            
            self.show_locations()#可视化
#             break

    #把所有鱼的位置变化展示出来，参考了https://blog.csdn.net/omodao1/article/details/81223240
    def show_locations(self):
        x = list(map(lambda x: x.location[0], self.fishes))
        y = list(map(lambda x: x.location[1], self.fishes))
        try:
            self.ax.lines.remove(self.lines[0])
        except Exception as e:
            print(e)
        self.lines = self.ax.plot(x ,y, '*')
        plt.pause(0.1)

if __name__ == '__main__':
    afsa = AFSA()
    afsa.fit(epoch_num=1000)增加了这些策略的鱼群寻优能力明显增强了。
3结束语
人工鱼群算法本身比较简单。实际应用的时候，我们需要针对任务特点制定优化目标，有时候还需要进行并行话改造以使用大数据场景——这才是有技术含量的部分。
注意：本文为李鹏宇(知乎个人主页https://www.zhihu.com/people/py-li-34)原创作品，受到著作权相关法规的保护。如需引用、转载，请注明来源信息：（1）作者名，即“李鹏宇”；（2）原始网页链接，即当前页面地址。如有疑问，可发邮件至我的邮箱:lipengyuer@126.com。

johnsoncodehk

请问和粒子群算法区别在哪？

IT圈老男孩1

粒子群算法没有专门学习过，说点我的理解啊:
(1)所基于的理论有区别。AFSA和PSO都是群体智能优化算法，前者模拟的是鱼的行为(觅食、追尾、聚群、随机游动)，而后者模拟的是鸟的行为(觅食、追随混的最好的鸟)。
(2)决定个体下一时刻的位置的方式不同，即位置更新规则不同。AFSA，基于个体当前位置的食物浓度(被优化的函数取值)、附近的鱼所处位置的食物浓度、整个鱼群发现的食物浓度最高的位置，这3种信息决定个体接下来的位置。PSO基于个体飞行(移动)的速度、已经去过的位置中距离食物最近(被优化的函数取值最高或者最低)、整个鸟群里混的最好的鸟的位置，来决定个体接下来的位置。
(3)从个体位置的更新规则来看，AFSA搜索全局最优、跳出局部最优的能力较强(随机游动；聚群行为中一般会设置鱼群的密度上限，是鱼群尽量分散活动)。

xiaozongpeng

好，谢谢

franciscochonge

如何在无线传感器网络覆盖方面应用呢，求指点！

RecursiveFrog

好问题，不过超出我擅长的领域啦。我查了一下，已经有一些相关研究了，比如黄瑜岳和李克清用这个算法优化无线传感器网络覆盖率(《基于人工鱼群算法的无线传感器网络覆盖优化》)。国外的相关研究应该也有。可以在知网、谷歌学术这些网站里花式搜索，找几篇、看看这些专家怎么定义的食物浓度和鱼。

HuldaGnodim

谢谢啦，我是有所了解了！但在应用到代码上就一下子，慌了！基础代码也看懂了！但到覆盖问题上映射一下子就，没路了，卡住好几天了！就来问问了[谢邀]

redhat9i

牛逼了。02年就已经搞出仿生算法来