1 # 遗传算法特征: *空间, 定长编码
  2 # 选择: 择优选择
  3 # 交叉: 全空间可遍历
  4 # 变异: 增强全空间的搜索能力
  5 
  6 import numpy
  7 import matplotlib.pyplot as plt
  8 
  9 # 目标函数1
 10 def myfunc1(x):
 11    return (x ** 2 - 5 * x) * numpy.sin(x ** 2) * -1
 12 
 13 # 目标函数2
 14 # def myfunc2(x1, x2):
 15     # return (1 - x1) ** 2 + 100 * (x2 - x1 ** 2) ** 2
 16 
 17 
 18 # 遗传算法: 选择, 交叉, 变异
 19 class GA(object):
 20     
 21     def __init__(self, func, lbounds, ubounds, population_size=300, maxIter=500, pm=0.01, speed=3, cf=0.1):
 22         self.func = func                           # 目标函数
 23         self.lbounds = lbounds                     # 搜寻下界
 24         self.ubounds = ubounds                     # 搜寻上界
 25         self.population_size = population_size     # 种群规模
 26         self.maxIter = maxIter                     # 最大迭代次数
 27         self.pm = pm                               # 变异概率(0, 1)
 28         self.speed=speed                           # 种群收敛速度[1, +∞)
 29         self.cf = cf                               # 交叉因子(0, 1)
 30         
 31         self.size = len(lbounds)                   # 搜索空间的维度
 32         self.best_chrom_fitness = list()           # 最优染色体(染色体, 适应度)迭代记录列表
 33         self.__record_fitness = list()             # 种群适应度迭代记录列表
 34         
 35     def solve(self):
 36         # 种群随机初始化
 37         population = self.__init_population()
 38         # 记录种群最优染色体信息
 39         self.__add_best(population)
 40         
 41         for i in range(self.maxIter):
 42             # 种群更新
 43             population = self.__selection(population)
 44             population = self.__crossover(population)
 45             population = self.__mutation(population)
 46             
 47             # 上一代最优个体无条件保留至下一代
 48             population[0] = self.best_chrom_fitness[-1][0]
 49             # 记录种群最优个体
 50             self.__add_best(population)
 51 
 52         self.solution = self.best_chrom_fitness[-1]
 53 
 54     # 选择: 轮盘赌方法
 55     def __selection(self, population):
 56         # 适应度排序
 57         fitness = self.__cal_fitness(population)
 58         new_fitness = sorted(list((ele, idx) for idx, ele in enumerate(fitness)), key=lambda item: item[0], reverse=True)
 59         # 轮盘区间计算 -> 采用多项式函数对收敛速度进行调整
 60         roulette_interval = self.__cal_interval()
 61         # 随机飞镖排序
 62         random_dart = sorted(numpy.random.random(self.population_size))
 63         
 64         new_population = list()
 65         idx_interval = idx_dart = 0
 66         while idx_dart < self.population_size:
 67             if random_dart[idx_dart] > roulette_interval[idx_interval]:
 68                 idx_interval += 1
 69             else:
 70                 new_population.append(population[new_fitness[idx_interval][1]])
 71                 idx_dart += 1
 72         
 73         # 顺序打乱
 74         numpy.random.shuffle(new_population)
 75         return new_population
 76     
 77     # 交叉: 对称凸组合
 78     def __crossover(self, population):
 79         # 交叉随机数 -> 采用交叉因子提高计算精度
 80         alpha = numpy.random.random(self.population_size - 1) * self.cf
 81         
 82         for idx in range(self.population_size - 1):
 83             new_chrom1 = alpha[idx] * population[idx] + (1 - alpha[idx]) * population[idx + 1]
 84             new_chrom2 = alpha[idx] * population[idx + 1] + (1 - alpha[idx]) * population[idx]
 85             population[idx] = new_chrom1
 86             population[idx + 1] = new_chrom2
 87             
 88         return population
 89         
 90     # 变异: 全空间变异
 91     def __mutation(self, population):
 92         # 变异概率随机数
 93         mutation_prob = numpy.random.random(self.population_size)
 94         
 95         for idx, prob in enumerate(mutation_prob):
 96             if prob <= self.pm:
 97                 # 变异幅度随机数
 98                 mutation_amplitude = numpy.random.uniform(-1, 1, self.size)
 99                 for idx_dim, ampli in enumerate(mutation_amplitude):
100                     if ampli >= 0:    # 正向变异
101                         population[idx][idx_dim] += ampli * (self.ubounds[idx_dim] - population[idx][idx_dim])
102                     else:             # 负向变异
103                         population[idx][idx_dim] += ampli * (population[idx][idx_dim] - self.lbounds[idx_dim])
104                         
105         return population
106    
107     # 种群随机初始化
108     def __init_population(self):
109         population = list()
110         
111         for i in range(self.population_size):
112             chrom = list()
113             for j in range(self.size):
114                 chrom.append(numpy.random.uniform(self.lbounds[j], self.ubounds[j]))
115             population.append(numpy.array(chrom))
116         
117         return population
118     
119     # 种群适应度计算
120     def __cal_fitness(self, population):
121         fitness = list(self.func(*chrom) for chrom in population)
122         return fitness
123         
124     # 记录种群最优染色体信息
125     def __add_best(self, population):
126         fitness = self.__cal_fitness(population)
127         self.__record_fitness.append(fitness)
128         min_idx = numpy.argmin(fitness)
129         self.best_chrom_fitness.append((population[min_idx], fitness[min_idx]))
130         
131     # 轮盘区间计算
132     def __cal_interval(self, speed=2):
133         tmp = (numpy.arange(self.population_size) + 1) / self.population_size
134         tmp_normalize = tmp / (self.population_size + 1) * 2
135         
136         roulette_interval = list()
137         curr_sum = 0
138         for item in tmp_normalize:
139             curr_sum += item
140             roulette_interval.append(curr_sum)
141         
142         roulette_interval = numpy.array(roulette_interval) ** self.speed
143         return roulette_interval
144     
145     # 求解过程可视化展示
146     def display(self):
147         fig = plt.figure(figsize=(8, 5))
148         axes = plt.subplot()
149         axes.plot(self.__record_fitness, 'g.')
150         axes.plot(numpy.array(self.__record_fitness).sum(axis=1) / self.population_size, 'r-', label='$meanVal$')
151         axes.set(xlim=(-1, self.maxIter+1), xlabel='$iterCnt$', ylabel='$fitness$')
152         axes.set(title = 'solution = {}'.format(self.solution))
153         axes.legend()
154         fig.savefig('myGA.png', dpi=500)
155         plt.show()
156         plt.close()
157 
158 
159 if __name__ == '__main__':
160     ins = GA(myfunc1, [-9], [5], population_size=100, maxIter=1000, pm=0.01, speed=1, cf=0.1)
161     # ins = GA(myfunc2, [-10, -10], [10, 10], population_size=100, maxIter=500, pm=0.3, speed=1, cf=0.1)
162     ins.solve()
163     ins.display()

结果展示:
测试函数1:
\begin{equation}
f(x) = (x^2 - 5x)sin(x^2) \times -1 \qquad x \in [-9, 5]
\end{equation}