[数据结构与算法]启发式算法/人工鱼群算法

原理

人工鱼群算法模拟的鱼群在觅食时的行为
寻找：在视野范围内随机游动寻找更好的食物
追尾：往视野范围内食物更好的鱼游去
聚集：往视野范围内鱼群中心靠近（认为，鱼越多的地方食物越好）
移动：在视野范围内随机移动

代码

步骤：

1. 初始化种群
2. 开始觅食
3. 寻找：在视野范围内寻找更好的食物+避免拥挤
4. 追尾：向视野范围内食物更好的鱼游去+避免拥挤
5. 聚集：向视野范围内小鱼群中心游去+避免拥挤
6. 移动：视野范围内随机移动+避免拥挤
7. 达到截止条件（迭代次数，截止适应度）退出

代码：

import numpy as np
import matplotlib
import matplotlib.pyplot as plt

matplotlib.rcParams['font.family'] = 'STSong'
matplotlib.rcParams['font.size'] = 10


def fitness_F1(x):
    """
    适应度函数当作食物量，食物量越大越好
    :param x: 鱼所在位置
    :return:
    """
    return -np.sum(x ** 2) + 900


class Fish(object):
    """
    鱼
    """

    def __init__(self, x, fit=None):
        """
        初始化函数
        :param x: 鱼当前位置
        :param fit: 当前位置食物量，适应度
        """
        self.__x = x
        self.__fit = fit

    def set_x(self, x):
        self.__x = x

    def get_x(self):
        return self.__x

    def set_fit(self, fit):
        self.__fit = fit

    def get_fit(self):
        return self.__fit


class ArtificialFishSwarmsAlgorithm(object):
    """
    鱼群算法
    """

    def __init__(self, num_iter, fitness_end, x_min, x_max, NP, D, view, crow, times):
        """
        初始化
        :param num_iter: 迭代次数
        :param fitness_end: 截止适应度
        :param x_min: 下界
        :param x_max: 上界
        :param NP: 种群鱼数量
        :param D(dimension): 位置向量维数
        :param view: 视野范围
        :param crow: 拥挤度，限制视野内鱼总数
        :param times: 尝试寻找食物次数
        """
        # 截止条件
        self.num_iter = num_iter
        self.fitness_end = fitness_end
        # 解空间
        self.x_min = x_min
        self.x_max = x_max
        # 求解者
        self.NP = NP
        self.D = D
        self.population()
        # 算法参数
        self.view = view
        self.crow = crow
        self.times = times

    def population(self):
        """
        初始化种群
        假设解空间内统一分布的鱼为一群鱼
        :return: 解空间内统一分布的鱼群
        """
        self.fish_pop = []
        pop = np.random.uniform(self.x_min, self.x_max, (self.NP, self.D))
        for row in pop:
            fish = Fish(row, fitness_F1(row))
            self.fish_pop.append(fish)

    def frage(self):
        """
        觅食
        寻找：在视野范围内寻找更好的食物+不挤
        追尾：向视野范围内食物更好的鱼游去+不挤
        聚集：向视野范围内小鱼群中心游去+不挤
        移动：视野范围内随机移动+不挤
        :return: 最优解，每次迭代的最佳适应度
        """
        best_x = None
        best_fit_list = []
        for it in range(self.num_iter):
            fitness_list = []
            # 每一条鱼进行觅食
            for fish in self.fish_pop:
                # 寻找
                self.find(fish)
                # 追尾
                self.follow(fish)
                # 聚集
                self.concentrate(fish)
                # 移动
                self.move(fish)
                # 记录
                fitness_list.append(fish.get_fit())

            # 记录
            best_fit = np.max(fitness_list)
            best_fit_list.append(best_fit)
            best_x = self.fish_pop[np.argmax(best_fit)].get_x()
            print('第', it + 1, '迭代', '，蜜源位置：', best_x, '，最佳适应度：', best_fit_list[-1])
            # 截止条件
            if self.fitness_end < best_fit:
                break

        return best_x, best_fit_list

    def find(self, fish):
        """
        搜索
        在视野范围内寻找更好的食物+不挤
        :param: fish: 某条鱼
        :return:
        """
        for i in range(self.times):
            # 视野内随机移动距离
            distance = np.random.uniform(-self.view, self.view, self.D)
            # 鱼新位置
            new_x = fish.get_x() + distance;
            # 新位置拥挤继续寻找
            if self.crowed(Fish(new_x)):
                continue
            # 新位置不拥挤且适应度更好 更新鱼的位置和食物适应度
            elif fitness_F1(new_x) > fitness_F1(fish.get_x()):
                fish.set_x(new_x)
                fish.set_fit(fitness_F1(new_x))

    def follow(self, fish):
        """
        追尾
        向视野范围内食物更好的鱼游去+不挤
        :param: fish: 某条鱼
        :return:
        """
        # 找到视野内适应度最好的鱼
        best_fish = None
        best_fit = fitness_F1(fish.get_x())
        for o in self.fish_pop:
            if np.linalg.norm(fish.get_x() - o.get_x()) < self.view:
                fit = fitness_F1(o.get_x())
                if fit > best_fit:
                    best_fish = o
                    best_fit = fit
        # 视野内没有鱼
        if best_fish == None: return
        # 往视野内适应度最好的鱼随机移动
        for i in range(self.times):
            # 鱼新位置
            new_x = np.random.uniform(fish.get_x(), best_fish.get_x())
            # 新位置拥挤继续寻找
            if self.crowed(Fish(new_x)):
                continue
            # 新位置不拥挤更新鱼的位置和食物适应度
            else:
                fish.set_x(new_x)
                fish.set_fit(fitness_F1(new_x))

    def concentrate(self, fish):
        """
        聚集
        向视野范围内小鱼群中心游去+不挤
        :param: fish: 某条鱼
        :return: 向视野范围内鱼群中心游去+不挤
        """
        # 寻找视野范围内的鱼群
        view_fish_xs = [fish.get_x(), ]
        for o in self.fish_pop:
            if np.linalg.norm(fish.get_x() - o.get_x()) < self.view:
                view_fish_xs.append(o.get_x())
        # 视野范围内没有鱼
        if len(view_fish_xs) == 1: return
        # 计算中心点
        center_x = np.average(view_fish_xs)
        # 往鱼群中心移动
        for i in range(self.times):
            # 鱼新位置
            new_x = np.random.uniform(fish.get_x(), center_x)
            # 新位置拥挤继续寻找
            if self.crowed(Fish(new_x)):
                continue
            # 新位置不拥挤更新鱼的位置和食物适应度
            else:
                fish.set_x(new_x)
                fish.set_fit(fitness_F1(new_x))

    def move(self, fish):
        """
        移动
        视野范围内随机移动+不挤
        :param: fish: 某条鱼
        :return:
        """
        for i in range(self.times):
            # 鱼新位置 视野内随机移动位置
            new_x = fish.get_x() + np.random.uniform(-self.view, self.view, 2)
            # 新位置拥挤继续寻找
            if self.crowed(Fish(new_x)):
                continue
            # 新位置不拥挤更新鱼的位置和食物适应度
            else:
                fish.set_x(new_x)
                fish.set_fit(fitness_F1(new_x))

    def crowed(self, fish):
        """
        是否拥挤
        :param fish: 某条鱼
        :return: True-拥挤，False-不拥挤
        """
        # 在视野内鱼条数
        count = 0
        for other in self.fish_pop:
            # np.linalg.norm 求范数，默认一范数=欧式距离；linalg=line algebra线性代数
            if np.linalg.norm(fish.get_x() - other.get_x()) < self.view: count += 1

        # 视野内鱼条数大于限制条数self.crow
        if count <= self.crow:
            return False
        else:
            return True

    def show(self, x_best, fitness_list):
        """
        展示迭代过程
        :param x_best: 最优解
        :param fitness_list: 每次迭代适应度值
        :return:
        """
        print("最优解:", str(x_best))
        print("最优适应度:", str(fitness_list[-1]))

        plt.title("迭代过程")
        plt.xlabel("迭代次数")
        plt.ylabel("适应度")
        x = range(1, len(fitness_list) + 1)
        y = fitness_list
        plt.plot(x, y, label="AFSA")
        plt.legend()
        plt.show()


if __name__ == "__main__":
    afsa = ArtificialFishSwarmsAlgorithm(100, 900, -30, 30, 10, 2, 0.1, 5, 6)
    best_x, fitness_list = afsa.frage()
    afsa.show(best_x, fitness_list)