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

APSchmidt · 发表于 2022-4-26 15:35

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

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

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

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

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

@author: Administrator
&#39;&#39;&#39;
#人工鱼群算法
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(&#34;a_fish.location&#34;, 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(&#34;轮次是&#34;, 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, &#39;*&#39;)
      plt.pause(0.1)

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

图1-2 迭代初期

图1-2 迭代中期

图1-3 最终状态

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

@author: Administrator
&#39;&#39;&#39;
#人工鱼群算法
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(&#34;a_fish.location&#34;, 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(&#34;轮次是&#34;, 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, &#39;*&#39;)
      plt.pause(0.1)

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

johnsoncodehk · 发表于 2022-4-26 15:39

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

IT圈老男孩1 · 发表于 2022-4-26 15:45

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

xiaozongpeng · 发表于 2022-4-26 15:52

好，谢谢

franciscochonge · 发表于 2022-4-26 15:56

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

RecursiveFrog · 发表于 2022-4-26 16:03

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

HuldaGnodim · 发表于 2022-4-26 16:03

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

redhat9i · 发表于 2022-4-26 16:13

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源