个人关于优化算法的学习历程：SA GA TSP PSO NSGA-ii
下列代码为个人学习及复现的过程，不一定很正确，有一定参考性，NSGA-ii不在此展示，详情可见下一篇。
退火（SA）
退火简述：个人认为有点像穷举，在x附近左右横跳，达到条件降温，没达到升温
|
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 |
from math import * from random import random # 方程或问题的计算 func = lambda x, y: cos(x * y) + x * y + y ** 3 + x ** 2 x_min = -100 y_min = -100 x_max = 100 y_max = 100 # 设置 SA 参数 e = 1e-50 L = 2000000 at = 0.999 T = 1 # 选取 x(0) x = random() * (x_max - x_min) + x_min y = random() * (y_max - y_min) + y_min result = func(x, y) # 循环 for _ in range(L): # 计算 x‘ ，需要选取合适的计算方法，以下为两种计算方法，各有利弊 # x_ = random() * (x_max - x_min) + x_min # y_ = random() * (y_max - y_min) + y_min step = 0.1 x_ = x + (random() * (x_max - x_min) + x_min) * step x_ = x_max if x_ > x_max else x_min if x_ < x_min else x_ y_ = y + (random() * (y_max - y_min) + y_min) * step y_ = y_max if y_ > y_max else y_min if y_ < y_min else y_ result_ = func(x_, y_) # 判断是否满足退火条件 if result_ - result < 0 or exp((result - result_) / T) > random(): # 更新 result = result_ x = x_ y = y_ # 温度降低 降低到一定值推出 T *= at if T < e: break print(result, x, y) |
遗传（GA）
遗传简述：对问题编码，可以是二进制也可以是十进制或者是排列（各位都不一样），交叉，变异进化，其中会包含精英保留等操作，NSGA在此基础上加上了非支配排序。
|
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 |
from math import sin, pi from random import randint, random from operator import itemgetter, attrgetter # 方程或问题的计算 func = lambda x: x * sin(10 * pi * x) + 2 x_min = -1 x_max = 2 # 设置遗传算法各种参数，分别代表：小数点后精度(epsilon)，编码位数(coding digit)，交叉变换位置(t)，交叉概率(pc)，变异概率(pm)，种群大小(M)，循环次数(L) epsilon = 6 coding_digit = 22 t = 4 pc = 0.8 pm = 0.2 M = 1000 L = 100 # 初始化种群 class Population: x = None xFlag = 1 result = None def __init__(self, x): self.x = abs(x_max if x > x_max else x_min if x < x_min else x) self.xFlag = 1 if x > 0 else -1 self.result = func(self.x * self.xFlag) population = [] for i in range(M): x = (x_max - x_min) / M * i + x_min population.append(Population(x)) def binary(X: float) -> list: X = list(bin(int(X * 10 ** epsilon)))[2:] return ["0" for i in range(coding_digit - len(X))] + X def decimal(X: list) -> float: return int("".join(X), 2) / 10 ** epsilon def cross(X: list, Y: list) -> [list, list]: X_ = X[:t] + Y[t:] Y_ = Y[:t] + X[t:] return X_, Y_ def variation(X: list) -> list: # 可以固定变异的位置也可以随机，以下设置为随机 position = randint(0, coding_digit - 1) X[position] = "1" if X[position] == "0" else "0" return X for _ in range(L): # 对种群进行排序，并选出最小的种群 population = sorted(population, key=lambda X: X.result, reverse=True) population = population[:M] # 交叉 for i in range(0, M, 2): if random() < pc: x1, x2 = cross(binary(population[i].x), binary(population[i + 1].x)) x1 = decimal(x1) * population[i].xFlag x2 = decimal(x2) * population[i + 1].xFlag population.append(Population(x1)) population.append(Population(x2)) # 变异 length = len(population) for i in range(length): if random() < pm: x = decimal(variation(binary(population[i].x))) * population[i].xFlag population.append(Population(x)) sorted(population, key=lambda X: X.result) ans = population[0] print(ans.x * ans.xFlag, ans.result) |
蚁群（TSP）
蚁群简述：信息素的更新与获取，信息素可以不用完全按照公式，根据具体题目可以有所不同。
|
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 |
from math import sin, pi from random import random, choice import numpy as np import matplotlib.pyplot as plt func = lambda x: x * sin(10 * pi * x) + 2 x_min = -1 x_max = 2 # alpha = 2.5 # beta = 1 rou = 0.2 M = 100 L = 700 step = 1 Q = 1 population = [] t = [] possibility = [] for i in range(M): population.append(random() * (x_max - x_min) + x_min) t.append(func(population[i])) possibility.append(1 / t[i]) t_max = [] for loop in range(1, L + 1): step = 1 / loop tBest = max(t) for i in range(M): possibility[i] = (tBest - t[i]) / tBest if possibility[i] < random(): population[i] += step * choice([-1, 1]) else: population[i] += choice([-1, 1]) * random() * (x_max - x_min) / 2 population[i] = x_min if population[i] < x_min else x_max if population[i] > x_max else population[i] t[i] = rou * t[i] + Q * func(population[i]) t_max.append(func(population[t.index(max(t))])) I = t.index(max(t)) print(population[I], func(population[I])) plt.plot(np.linspace(1, L, L), t_max) plt.show() |
粒子群（PSO）
粒子群简述：速度的更新，包含个人学习速率和社会学习速率，不同点的速度不同，更新的速度不同。
|
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 |
from math import cos from random import random import numpy as np # 方程或问题的计算 func = lambda x, y: -(cos(x * y) + x * y + y ** 3 + x ** 2) x_min = -100 y_min = -100 x_max = 100 y_max = 100 # 设置参数 L = 100 omega = 1 groupLR = 0.5 socialLR = 1.5 M = 20 v_min = -1 v_max = 1 # 初始化种群 population = np.zeros(M * 2).reshape(M, 2) v = np.zeros(M * 2).reshape(M, 2) fitness = np.zeros(M) for i in range(M): population[i][0] = random() * (x_max - x_min) + x_min population[i][1] = random() * (x_max - x_min) + x_min v[i][0] = random() * (x_max - x_min) + x_min v[i][1] = random() * (x_max - x_min) + x_min fitness[i] = func(population[i][0], population[i][1]) # 初始化个人与种群最优解 # M * 2 personalBestFitness = fitness.copy() personalPopulation = population.copy() # 2 * 2 groupBest = population[fitness.argmax()].copy() groupBestFitness = fitness.max() for _ in range(L): for i in range(len(fitness)): # 更新速度 # 随时间适应度 + 个人学习速率 * （个人最好 - 当前） + 社会学习速率 * （团队最好 - 当前） v[i] = omega * v[i] + groupLR * random() * (personalPopulation[i] - population[i]) + socialLR * random() * (groupBest - population[i]) v[v < v_min] = v_min v[v > v_max] = v_max for i in range(len(fitness)): # 更新位置 population[i] += v[i] population[i][0] = x_min if population[i][0] < x_min else x_max if population[i][0] > x_max else population[i][0] population[i][1] = y_min if population[i][1] < y_min else y_max if population[i][1] > y_max else population[i][1] # 适应度更新 fitness[i] = func(population[i][0], population[i][1]) # 个人最好更新 if fitness[i] > personalBestFitness[i]: personalBestFitness[i] = fitness[i] personalPopulation[i] = population[i].copy() # 团队最好更新 if personalBestFitness.max() > groupBestFitness: groupBestFitness = personalBestFitness.max() groupBest = population[personalBestFitness.argmax()].copy() print(groupBestFitness, groupBest[0], groupBest[1]) |
浙公网安备 33010902002953号