差分进化算法，遗传差分获取 一个复杂二元函数在给定范围内的近似最优解（最大值or 最小值）_二元函数差分

差分进化算法：(Difference Evaluation)

例如面对以下问题：
求函数f(x)=x_1^2+x_22函数的极值点
->最小值点在 ( 0,0 )，最小值为0.
差分进化算法对于不可导或者不连续也可以进行求解

原理：

算法的主体分成4个步骤：
    1.初始化种群
    2.产生变异个体
    3.变异个体与原始种群交叉
    4.从变异个体和原始种群中筛选优秀个体
1
2
3
4
5

1. 初始化种群:

1.1 种群大小size:
    这表示种群中个体的个数，一般来说越大的值搜索到更优化的解的可能性更高
    这里选取size = 5

1.2 每个个体（解）的维度dimension：
    这是由目标函数决定的，f(x)=x_1^2+x_2^2 的输入有x1与x2两个参数，因此维度为2

1.3 解的搜索区间(min, max)：
    这里限定x_1 in(-1, 1)，x_2 in(-1, 1)，即min=-1, max=1。
    在给定搜索区间内随机生成5个可能的解，称为个体
    设他们分别是 (-0.3, 0.2), (0.1, 0.4), (0.9, -0.6),
    (-0.8, 0.4), (-0.1, 0.1)。这5个个体被称作种群.
1
2
3
4
5
6
7
8
9
10
11
12

2. 产生变异个体

2.1 得到初始种群后，DE算法通过差分的方法生成变异个体。
2.2 产生的方法是从种群中选择三个不同的个体a, b, c, 通过一下方式计算得到变异个体n：
N = a + F*(b-c)
F为缩放因子factor，它控制着变异程度。F越大，越不容易陷入局部极值点；
F越小，越有利于收敛到局部极值点
2.3 这里我们使用F=0.5 举例：
从种群中随机抽取 a=(-0.3, 0.2), b=(0.1, 0.4), c=(0.9, -0.6)
这三个个体，变异得到的新个体n即是
n=(-0.7,0.7)= (-0.3, 0.2) + 0.5*((0.1,0.4) - (0.9, -0.6))
重复上述过程得到一组变异个体n_1,n_2,n_3,n_4,n_5

3.变异个体与原始种群交叉

然后我们以一定概率让新产生的变异个体与原种群中个体进行交叉重组，这个概率记作CR，
示例中令CR=0.5
例如2中得到的变异个体n=(-0.7,0.7)让它与原始种群中的第三个个体(0.9,-0.6)进行交叉，
这意味着-0.7有50%的概率被替换为0.9，0.7有50%的概率被替换为-0.6，
最终我们得到的一个可能结果是 n=(-0.7,-0.6)，即0.7被替换为-0.6.

重复上述过程，我们得到了与原始种群交叉过后的新变异种群,new_n_1,new_n_2, new_n_3, new_n_4,new_n_5,
1
2
3
4
5
6
7

4.从变异个体和原始种群中筛选优秀个体

最后通过计算目标函数值，比较原始种群以及变异种群中的个体，选出下一代的原始种群。

例如原始种群中个体(0.9,-0.6)与变异种群个体n=(-0.7,-0.6)进行比较，
前者的目标函数值是1.17，后者的目标函数值是0.85，后者更接最小值点 (0,0)->0 ,
因此我们选择保留变异个体n，替换掉前者的个体，作为新的原始种群.
1
2
3
4
5

按照上述2-4步骤进行迭代后，得到的种群逐渐接近函数的最小值点，这个迭代次数可以由参数Round控制，更大的迭代次数可以使得收敛效果提高。最终我们只需要输出种群中目标函数值最小的个体即可.
求函数的最大最小值

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

class Population:
    def __init__(self, min_range, max_range, dim, factor, rounds, size, object_func, CR=0.75):
        """

        :param min_range: 搜索区间(min, max)：
        :param max_range:
        :param dim: 个体的特征维度
        :param factor:  F为缩放因子factor
            N = a + F*(b-c)，产生变异个体
            它控制着变异程度。F越大，越不容易陷入局部极值点；F越小，越有利于收敛到局部极值点
        :param rounds: 迭代次数设定
        :param size:种群大小size
        :param object_func: 目标函数 ， 来获取目标对应的极值点和对应极值
        :param CR:变异个体与原始种群交叉， 以一定概率让新产生的变异个体与原种群中个体进行交叉重组，这个概率记作CR，令CR=0.75
        """
        self.min_range = min_range
        self.max_range = max_range
        self.dimension = dim
        self.factor = factor
        self.rounds = rounds
        self.size = size
        self.cur_round = 1
        self.CR = CR
        self.get_object_function_value = object_func
        # 初始化种群
        self.individuality = [np.array([random.uniform(self.min_range, self.max_range) for s in range(self.dimension)]) for tmp in range(size)] # list object 100 x 2
        self.object_function_values = [self.get_object_function_value(v) for v in self.individuality]  # 相当于求得每一个 individuality 对应的value
        self.mutant = None

        self.result = {
            'epoch':[],
            'individual':[],
            'target':[]
        }

    def mutate(self): #   产生的方法是从种群中选择三个不同的个体a, b, c, 产生变异个体 N = a + F*(b-c)  F: factor 取 0.8, 通常在0-2之间
        self.mutant = [] # 保留所有产生的变异个体
        for i in range(self.size): # size  = 100
            r0, r1, r2 = 0, 0, 0
            while r0 == r1 or r1 == r2 or r0 == r2 or r0 == i: # 随机选择三个个体 a，b，c
                r0 = random.randint(0, self.size-1)
                r1 = random.randint(0, self.size-1)
                r2 = random.randint(0, self.size-1)
            tmp = self.individuality[r0] + (self.individuality[r1] - self.individuality[r2]) * self.factor
            # F为缩放因子factor，它控制着变异程度。F越大，越不容易陷入局部极值点；F越小，越有利于收敛到局部极值点


            # # 边界条件处理一种方法是将超过边界的向量使用可行域中随机产生的参数向量代替.
            # for t in range(self.dimension):
            #     if tmp[t] > self.max_range or tmp[t] < self.min_range:
            #         tmp[t] = random.uniform(self.min_range, self.max_range)
            #         # random.uniform(x, y) 方法将随机生成一个实数，它在 [x,y] 范围内。

            # 另一种是边界吸收处理
            for t in range(self.dimension):
                if tmp[t] > self.max_range :

                    tmp[t] = self.max_range

                if tmp[t] < self.min_range:

                    tmp[t] = self.min_range
                    # random.uniform(x, y) 方法将随机生成一个实数，它在 [x,y] 范围内。


            self.mutant.append(tmp)


    def crossover_and_select(self):
        """
        :param CR:变异个体与原始种群交叉， 以一定概率让新产生的变异个体与原种群中个体进行交叉重组，这个概率记作CR，令CR=0.75
        :return:
        """
        for i in range(self.size):
            Jrand = random.randint(0, self.dimension)
            for j in range(self.dimension):
                if random.random() > self.CR and j != Jrand: # 只允许一个基因交叉变异 且 变异机率大于CR
                    self.mutant[i][j] = self.individuality[i][j]
                tmp = self.get_object_function_value(self.mutant[i]) # tmp为变异个体对应的函数的解
                if tmp < self.object_function_values[i]:
                    self.individuality[i] = self.mutant[i]
                    self.object_function_values[i] = tmp


    def print_best(self):
        m = min(self.object_function_values)
        i = self.object_function_values.index(m)
        print("轮数：" + str(self.cur_round))
        print("最佳个体：" + str(self.individuality[i]))
        print("目标函数值：" + str(m))
        self.result["epoch"].append(self.cur_round)
        self.result["individual"].append(self.individuality[i].tolist())
        self.result["target"].append(m)

    def evolution(self):
        while self.cur_round < self.rounds:
            self.mutate()
            self.crossover_and_select()
            self.print_best()
            self.cur_round = self.cur_round + 1

    def get_result(self):

        return self.result

    def get_result_figure(self):

        plt.title(f"min_value in range[{self.min_range},{self.max_range}]")
        plt.plot(self.result['epoch'],self.result['target'])
        plt.show()
        plt.title("epoch & x1,x2")
        plt.scatter(np.array(self.result['individual'])[:,0],np.array(self.result['individual'])[:,1])
        plt.show()


#测试部分
if __name__ == "__main__":
    def f(v):
        return -(v[1]+47)*np.sin(np.sqrt(np.abs(v[1]+(v[0]/2)+47))) - v[0] * np.sin(np.sqrt(np.abs(v[0]-v[1]-47)))
    p = Population(min_range=-10000, max_range=10000, dim=2, factor=0.8, rounds=100, size=100, object_func=f)
    p.evolution()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

轮数：1
最佳个体：[10000.         -4740.41469117]
目标函数值：-14219.661493026237
轮数：2
最佳个体：[ 9003.07081002 10000.        ]
目标函数值：-16510.21805624861
轮数：3
最佳个体：[ 8984.09063298 10000.        ]
目标函数值：-17683.21246362536
轮数：4
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：5
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：6
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：7
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：8
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：9
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：10
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：11
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：12
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：13
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：14
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：15
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：16
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：17
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：18
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：19
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：20
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：21
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：22
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：23
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：24
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：25
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：26
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：27
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：28
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：29
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：30
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：31
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：32
最佳个体：[ 8958.37545984 10000.        ]
目标函数值：-18104.343783327717
轮数：33
最佳个体：[9637.45791559 9803.76399865]
目标函数值：-18316.637650292025
轮数：34
最佳个体：[9679.63079954 9837.55524059]
目标函数值：-18658.79704483886
轮数：35
最佳个体：[9679.63079954 9837.55524059]
目标函数值：-18658.79704483886
轮数：36
最佳个体：[9679.63079954 9837.55524059]
目标函数值：-18658.79704483886
轮数：37
最佳个体：[9481.06928592 9843.01119892]
目标函数值：-19185.616054082697
轮数：38
最佳个体：[9481.06928592 9843.01119892]
目标函数值：-19185.616054082697
轮数：39
最佳个体：[9481.06928592 9843.01119892]
目标函数值：-19185.616054082697
轮数：40
最佳个体：[9497.47220063 9870.04419247]
目标函数值：-19282.712002664353
轮数：41
最佳个体：[9497.47220063 9870.04419247]
目标函数值：-19282.712002664353
轮数：42
最佳个体：[9497.47220063 9870.04419247]
目标函数值：-19282.712002664353
轮数：43
最佳个体：[9497.47220063 9870.04419247]
目标函数值：-19282.712002664353
轮数：44
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：45
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：46
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：47
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：48
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：49
最佳个体：[9471.91565982 9843.01119892]
目标函数值：-19357.572436902658
轮数：50
最佳个体：[9472.84929577 9843.01119892]
目标函数值：-19362.121733898675
轮数：51
最佳个体：[9472.84929577 9843.01119892]
目标函数值：-19362.121733898675
轮数：52
最佳个体：[9472.84929577 9843.01119892]
目标函数值：-19362.121733898675
轮数：53
最佳个体：[9472.84929577 9843.01119892]
目标函数值：-19362.121733898675
轮数：54
最佳个体：[9472.84929577 9843.01119892]
目标函数值：-19362.121733898675
轮数：55
最佳个体：[9619.03185416 9769.1617669 ]
目标函数值：-19389.04330852446
轮数：56
最佳个体：[9619.03185416 9769.1617669 ]
目标函数值：-19389.04330852446
轮数：57
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：58
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：59
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：60
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：61
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：62
最佳个体：[9761.90029011 9717.40849542]
目标函数值：-19503.784731743173
轮数：63
最佳个体：[9897.61535105 9653.46890747]
目标函数值：-19518.946263344355
轮数：64
最佳个体：[9897.61535105 9653.46890747]
目标函数值：-19518.946263344355
轮数：65
最佳个体：[9897.61535105 9653.46890747]
目标函数值：-19518.946263344355
轮数：66
最佳个体：[9897.61535105 9653.46890747]
目标函数值：-19518.946263344355
轮数：67
最佳个体：[9895.54032901 9650.39768684]
目标函数值：-19553.570240713514
轮数：68
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：69
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：70
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：71
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：72
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：73
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：74
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：75
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：76
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：77
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：78
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：79
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：80
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：81
最佳个体：[9896.18791449 9649.22167885]
目标函数值：-19573.478084318398
轮数：82
最佳个体：[9887.62982795 9640.71247477]
目标函数值：-19574.881358214363
轮数：83
最佳个体：[9887.62982795 9640.71247477]
目标函数值：-19574.881358214363
轮数：84
最佳个体：[9889.88559147 9643.45592299]
目标函数值：-19576.038505590197
轮数：85
最佳个体：[9893.07060787 9645.89485901]
目标函数值：-19576.719363894073
轮数：86
最佳个体：[9893.07060787 9645.89485901]
目标函数值：-19576.719363894073
轮数：87
最佳个体：[9892.51644922 9645.77529045]
目标函数值：-19577.234654632033
轮数：88
最佳个体：[9892.51644922 9645.77529045]
目标函数值：-19577.234654632033
轮数：89
最佳个体：[9892.51644922 9645.77529045]
目标函数值：-19577.234654632033
轮数：90
最佳个体：[9892.51644922 9645.77529045]
目标函数值：-19577.234654632033
轮数：91
最佳个体：[9892.51644922 9645.77529045]
目标函数值：-19577.234654632033
轮数：92
最佳个体：[9892.59951608 9645.72634716]
目标函数值：-19577.366348888376
轮数：93
最佳个体：[9891.76864841 9644.98404249]
目标函数值：-19577.5281117334
轮数：94
最佳个体：[9891.74595722 9644.82764187]
目标函数值：-19577.600173159495
轮数：95
最佳个体：[9891.57750597 9644.6465669 ]
目标函数值：-19577.607112956084
轮数：96
最佳个体：[9891.57750597 9644.6465669 ]
目标函数值：-19577.607112956084
轮数：97
最佳个体：[9891.57750597 9644.6465669 ]
目标函数值：-19577.607112956084
轮数：98
最佳个体：[9891.57750597 9644.6465669 ]
目标函数值：-19577.607112956084
轮数：99
最佳个体：[9891.61597502 9644.7300245 ]
目标函数值：-19577.61574256794
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297

p.get_result_figure()
1
2

分析结果, 如上面所示 可以大致看出 最小值的取值点在 x1 逼近10000,的时候取得

二、改进的差分进化算法

（1）自适应差分进化算法

主要是使用了自适应算子。在基本的差分进化算法中，变异算子经常取常数，比较难准确确定，变异率太大，全局最优解低，变异率小，群体多样性下降，易出现‘早熟’的现象。我们可以设计这样的变异算子：

这样开始的时候变异算子为2F0，在初期可以保持多样性，防止早熟。随着进展，变异算子降低最后变为F0，避免最优解遭到破坏。

还可以设计一个随机范围的交叉算子：
        CR : 0.5*[1+rand(0,1)]
1
2

这样交叉算子的均值就在0.75，保持了群体多样性。

（2）离散差分进化算法

采用的是浮点数编码，用到了floor这个函数向下取整即可.

四、参数说明

种群数量NP：规模越大多样性越好，但是增加计算难度，一般在5D~10D之间，而且必须大于4. D : 为个体的特征维度

变异算子F：[0,2],决定偏差向量的放大比例。F=0.5是一个比较好的初始选择，如果过早收敛可以增大F或者NP

交叉算子CR： [0,1] ,CR越大，发生交叉的可能性就越大，一般CR=0.1，较大的CR会加速收敛。

终止条件：一般当目标函数值小于阈值时程序终止，一般取 le -6