遗传算法求解带约束优化问题（源码实现）

分手后的思念是犯贱 2022-11-18 10:51 274阅读 0赞

之前讲解了遗传算法原理，[万字字符长文带你了解遗传算法（有几个算例源码）][Link 1] 今天介绍了遗传算法如何求解带约束的优化问题。

## 求解方法 ##

1.  一开始设计编码规则时，让解编码就只可能在可行区域内。典型的例子是遗传算法做实数函数的优化，会给出 upper bound和lower bound，然后无论怎样的染色体，解码后都在这两个bound之间 。此方法前面的《万字字符长文带你了解遗传算法（有几个算例源码）》算例中有。
2.  设计合理的交叉算子和变异算子，使得满足这些算子本身的特性的前提下，还让算子运算后的染色体也在可行域内。此方法 例子见TSP求解。[遗传算法求最短路径（旅行商问题）python实现][python] 。此方法比较难写。
3.  罚函数法。万能方法。但罚函数太多或太严格，会导致效果很差。惩罚系数较大，族群会更加集中在可行域中，而不鼓励向不可行域探索。当惩罚系数过大，容易使算法收敛于局部最优；惩罚系数较小，族群会更积极在不可行域中进行大量探索，一定程度上能帮助寻找全局最优，但也有浪费算力的风险。当惩罚系数过小，算法可能会收敛于不可行解。
4.  在变异/交叉之后加入一个判断语句，判断是否满足约束条件，如果不满足，有两个策略：超出边界的放到边界上。或者超出边界的，重新初始化。

## 算例 ##

问题  
![20210331092553717.png_pic_center][]

此函数图像  
![20210329134113915.png_pic_center][]

算例求解  
文中的代码是python 编写的。都是基本代码  
用matlab的人也能看懂

import numpy as np
    import matplotlib.pyplot as plt
    from pylab import *
    mpl.rcParams['font.sans-serif'] = ['SimHei']
    mpl.rcParams['axes.unicode_minus'] = False
    
    
    ####################初始化参数#####################
    NP=50                 #种群数量
    L=2                 # 对应x,y
    Pc=0.5                 #交叉率
    Pm=0.1                 #变异率
    G=100                 #最大遗传代数
    Xmax=2                #x上限
    Xmin=1                 #x下限
    Ymax=0                 #y上限
    Ymin=-1                #y 下限
    
    
    
    ########################这里定义一些参数，分别是计算适应度函数和计算约束惩罚项函数############
    
    def calc_f(X):
        """计算群体粒子的目标函数值，X 的维度是 size * 2 """
        a = 10
        pi = np.pi
        x = X[:, 0]
        y = X[:, 1]
        return 2 * a + x ** 2 - a * np.cos(2 * pi * x) + y ** 2 - a * np.cos(2 * 3.14 * y)
    def calc_e(X):
        """计算群体粒子的目惩罚项，X 的维度是 size * 2 """
        sumcost=[]
    
        for i in range(X.shape[0]):
            ee = 0
            """计算第一个约束的惩罚项"""
            e1 = X[i, 0] + X[i, 1] - 6
            ee += max(0, e1)
            """计算第二个约束的惩罚项"""
            e2 = 3 * X[i, 0] - 2 * X[i, 1] - 5
            ee += max(0, e2)
            sumcost.append(ee)
        return sumcost
    
    
    ##############遗传操作方法#########
    
    def select(X, fitness):
        """根据轮盘赌法选择优秀个体"""
        fitness = 1 / fitness  # fitness越小表示越优秀，被选中的概率越大，做 1/fitness 处理
        fitness = fitness / fitness.sum()  # 归一化
        idx = np.array(list(range(X.shape[0])))
        X2_idx = np.random.choice(idx, size=X.shape[0], p=fitness)  # 根据概率选择
        X2 = X[X2_idx, :]
        return X2
    
    def crossover(X, c):
        """按顺序选择2个个体以概率c进行交叉操作"""
        for i in range(0, X.shape[0], 2):
            parent1=X[i].copy() #父亲
            parent2=X[i + 1].copy()#母亲
            # 产生0-1区间的均匀分布随机数，判断是否需要进行交叉替换
            if np.random.rand() <= c:
                child1=(1-c)*parent1+c*parent2 #这是实数编码 的交叉形式 shape(2,)
                #child1=child1.reshape(-1,2)
    
                child2=c*parent1+(1-c)*parent2 #shape(2,)
                #child2=child2.reshape(1,2)
                #判断个体是否越限
                if child1[0]>Xmax or child1[0] < Xmin:
                    child1[0]=np.random.uniform(Xmin, Xmax)
                if child1[1] > Ymax or child1[1] <Ymin:
                    child1[1] = np.random.uniform(Ymin, Ymax)
                if child2[0] > Xmax or child2[0] < Xmin:
                    child2[0] = np.random.uniform(Xmin, Xmax)
                if child2[1] > Ymax or child2[1] < Ymin:
                    child2[1] = np.random.uniform(Ymin, Ymax)
                ######通过比较父辈和子代的适应度值和惩罚项 来决定要不要孩子
                X[i, :]=child1
                X[i + 1, :]=child2
        return X
    
    
    def mutation(X, m):
        """变异操作"""
        for i in range(X.shape[0]):#遍历每一个个体
            # 产生0-1区间的均匀分布随机数，判断是否需要进行变异
            parent=X[i].copy()#父辈
            if np.random.rand() <= m:
                    child = np.random.uniform(-1,2,(1,2))# 用随机赋值的方式进行变异 得到子代
                    # 判断个体是否越限
                    if child[:,0] > Xmax or child[:,0] < Xmin:
                        child[:,0] = np.random.uniform(Xmin, Xmax)
                    if child[:,1] > Ymax or child[:,1] < Ymin:
                        child[:,1] = np.random.uniform(Ymin, Ymax)
                    ######通过比较父辈和子代的适应度值和惩罚项 来决定要不要孩子
                    X[i]=child
        return X
    
    #子代和父辈之间的选择操作
    def update_best(parent,parent_fitness,parent_e,child,child_fitness,child_e):
        """ 判 :param parent: 父辈个体 :param parent_fitness:父辈适应度值 :param parent_e ：父辈惩罚项 :param child: 子代个体 :param child_fitness 子代适应度值 :param child_e ：子代惩罚项 :return: 父辈 和子代中较优者、适应度、惩罚项 """
        # 规则1，如果 parent 和 child 都没有违反约束，则取适应度小的
        if parent_e <= 0.0000001 and child_e <= 0.0000001:
            if parent_fitness <= child_fitness:
                return parent,parent_fitness,parent_e
            else:
                return child,child_fitness,child_e
        # 规则2，如果child违反约束而parent没有违反约束，则取parent
        if parent_e < 0.0000001 and child_e  >= 0.0000001:
            return parent,parent_fitness,parent_e
        # 规则3，如果parent违反约束而child没有违反约束，则取child
        if parent_e >= 0.0000001 and child_e < 0.0000001:
            return child,child_fitness,child_e
        # 规则4，如果两个都违反约束，则取适应度值小的
        if parent_fitness <= child_fitness:
            return parent,parent_fitness,parent_e
        else:
            return child,child_fitness,child_e
    
    
    def ga():
        """遗传算法主函数"""
        best_fitness = []  # 记录每次迭代的效果
        best_xy = []#存放最优xy
        f = np.random.uniform(-1, 2, (NP, 2))  # 初始化种群 （生成-1,2之间的随机数）shape (NP,2)
        for i in range(G):#遍历每一次迭代
            fitness=np.zeros((NP, 1))#存放适应度值
            ee=np.zeros((NP, 1)) #存放惩罚项值
    
            parentfit = calc_f(f)#计算父辈目标函数值
            parentee = calc_e(f)#计算父辈惩罚项
            parentfitness = parentfit + parentee #计算父辈适应度值 适应度值=目标函数值+惩罚项
            X2 = select(f, parentfitness)#选择
            X3 = crossover(X2, Pc)#交叉
            X4 = mutation(X3, Pm)#变异
    
            childfit = calc_f(X4)  # 子代目标函数值
            childee = calc_e(X4)  # 子代惩罚项
            childfitness = childfit + childee  # 子代适应度值
    
            # 更新群体
            for j in range(NP):#遍历每一个个体
                X4[j],fitness[j],ee[j] = update_best(f[j], parentfitness[j], parentee[j], X4[j], childfitness[j],childee[j])
    
            best_fitness.append(fitness.min())
            x, y = X4[fitness.argmin()]
            best_xy.append((x, y))
            f=X4
            # 多次迭代后的最终效果
        print("最优值是：%.5f" % best_fitness[-1])
        print("最优解是：x=%.5f, y=%.5f" % best_xy[-1])
        # 打印效果
        plt.plot(best_fitness, color='r')
        plt.show()
    ga()

![2021052017090328.png_pic_center][] ![20210520170927711.png_pic_center][]

代码中：用于限制约束的有

1.  种群初始化时 ，限制。
2.  交叉变异后，加if 语句判断
3.  惩罚项

## 遗传算法二进制编码（求解复杂约束问题） ##

经过我多次对比，遗传算法 二进制编码要比实数编码要好。可能二进制编码中的交叉变异才更有意思。求解方法算法见下面链接：  
[电力期刊论文实现：遗传算法求解考虑输电损耗的负荷最优分配（二进制编码）][Link 2]  
![在这里插入图片描述][20210413163814931.jpg_pic_center]  
作者：电气 余登武

![20210413163914989.jpg_pic_center][]

[Link 1]: https://blog.csdn.net/KOBEYU652453/article/details/115505145
[python]: https://blog.csdn.net/KOBEYU652453/article/details/114787101
[20210331092553717.png_pic_center]: /images/20221022/0eac3c0723e94c62af99ce93ddc12493.png
[20210329134113915.png_pic_center]: /images/20221022/f99e1d6efb9149529a72cb1eeca1e261.png
[2021052017090328.png_pic_center]: https://img-blog.csdnimg.cn/2021052017090328.png#pic_center
[20210520170927711.png_pic_center]: /images/20221022/0c1f91809d64440fbeb58640783e4793.png
[Link 2]: https://blog.csdn.net/KOBEYU652453/article/details/117127271
[20210413163814931.jpg_pic_center]: /images/20221022/97b07a8ab7424601991e4fe43ae15c22.png
[20210413163914989.jpg_pic_center]: /images/20221022/0edd89180b4944b78d92661b95c4109e.png