五大核心优化算法（python）

文摘 2024-09-01 17:32 辽宁

点击上方“进修编程”，选择“星标”公众号

超级无敌干货，第一时间送达！！！

金属质感分割线

本文讲述科研中的五大核心优化算法并用python实现：之前每个算法已经单独讲过了感兴趣的可以往前翻一翻。

遗传算法 (Genetic Algorithm):

一种基于自然选择和遗传学原理的启发式搜索算法，用于解决优化和搜索问题。

粒子群优化 (Particle Swarm Optimization, PSO):

模拟鸟群觅食行为的优化算法，通过粒子在搜索空间中的移动找到最优解。

模拟退火 (Simulated Annealing):

受金属退火过程启发的随机优化算法，通过逐渐降低温度来逃避局部最优解。

蚁群算法 (Ant Colony Optimization, ACO):

模仿蚂蚁觅食行为的优化算法，通过信息素的更新来寻找最优路径。

梯度下降法 (Gradient Descent):

通过计算损失函数的梯度来更新参数，逐步逼近最优解。

一、遗传算法

遗传算法 (GA) 是一种自适应启发式搜索算法，属于进化算法的大部分。遗传算法基于自然选择和遗传学的思想。这些算法智能地利用随机搜索，并提供历史数据，将搜索引导到解决方案空间中性能更好的区域。它们通常用于为优化问题和搜索问题生成高质量的解决方案。

遗传算法模拟自然选择的过程，这意味着那些能够适应环境变化的物种可以生存和繁殖并进入下一代。简而言之，它们模拟连续几代个体之间的“适者生存”来解决问题。每一代都由一群个体组成，每个个体代表搜索空间中的一个点和可能的解决方案。每个个体都表示为一个字符串/整数/浮点数/位。这个字符串类似于染色体。

遗传算法基础

遗传算法基于与种群染色体的遗传结构和行为的类比。以下是基于这种类比的 GA 的基础 -

种群中的个体竞争资源和配偶
那些成功（最适合）的个体会交配，从而产生比其他个体更多的后代
来自“最适合”父母的基因会在整个世代中传播，也就是说，有时父母会创造出比父母更优秀的后代。
因此，每一代都更适应其环境。

搜索空间

个体群体在搜索空间内维护。每个个体代表给定问题的搜索空间解决方案。每个个体被编码为有限长度的组件向量（类似于染色体）。这些可变组件类似于基因。因此，染色体（个体）由多个基因（可变组件）组成。

体能分数

每个个体都会被赋予一个适应度分数，该分数表明该个体的“竞争”能力。寻找具有最佳适应度分数（或接近最佳）的个体。

GA 维护 n 个个体（染色体/解决方案）的种群及其适应度得分。适应度得分较高的个体比其他个体有更多繁殖机会。选择适应度得分较高的个体，通过结合父母的染色体进行交配并产生更好的后代。种群规模是静态的，因此必须为新来者腾出空间。因此，一些个体死亡并被新来者取代，最终在旧种群的所有交配机会耗尽时产生新一代。希望在连续几代中，更好的解决方案将会出现，而适应度最低的个体则会死亡。

平均而言，每个新一代都比前几代的个体（解决方案）拥有更多“更好的基因”。因此，每个新一代都比前几代拥有更好的“部分解决方案”。一旦产生的后代与之前种群产生的后代没有显著差异，种群就会收敛。该算法被称为收敛到一组问题的解决方案。

遗传算法的算子

一旦创建了初始代，算法就会使用以下运算符来进化该代 -
1) 选择运算符：其思想是优先考虑具有良好适应度分数的个体，并允许它们将基因传递给后代。
2) 交叉运算符：这代表个体之间的交配。使用选择运算符选择两个个体，并随机选择交叉点。然后交换这些交叉点的基因，从而创建一个全新的个体（后代）。例如 -

3）变异算子：关键思想是在后代中插入随机基因，以保持种群的多样性，避免过早收敛。例如 -

整个算法可以概括为：

1）随机初始化种群 p 2）确定种群的适应度3）直到收敛重复：      a）从种群中选择父母      b）交叉并产生新种群      c）对新种群进行变异      d）计算新种群的适应度

使用遗传算法的示例问题和解决方案

给定一个目标字符串，目标是从相同长度的随机字符串开始生成目标字符串。在下面的实现中，进行了以下类比：

字符 AZ、az、0-9 和其他特殊符号被视为基因
由这些字符生成的字符串被视为染色体/解决方案/个体

适应度得分是特定索引处与目标字符串中字符不同的字符数。因此，具有较低适应度值的个体将获得更多优先权。

完整代码：

# Python3 program to create target string, starting from # random string using Genetic Algorithm 
import random 
# Number of individuals in each generation POPULATION_SIZE = 100
# Valid genes GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''
# Target string to be generated TARGET = "I love GeeksforGeeks"
class Individual(object):   '''   Class representing individual in population   '''  def __init__(self, chromosome):     self.chromosome = chromosome     self.fitness = self.cal_fitness() 
  @classmethod  def mutated_genes(self):     '''     create random genes for mutation     '''    global GENES     gene = random.choice(GENES)     return gene 
  @classmethod  def create_gnome(self):     '''     create chromosome or string of genes     '''    global TARGET     gnome_len = len(TARGET)     return [self.mutated_genes() for _ in range(gnome_len)] 
  def mate(self, par2):     '''     Perform mating and produce new offspring     '''
    # chromosome for offspring     child_chromosome = []     for gp1, gp2 in zip(self.chromosome, par2.chromosome):   
      # random probability       prob = random.random() 
      # if prob is less than 0.45, insert gene       # from parent 1       if prob < 0.45:         child_chromosome.append(gp1) 
      # if prob is between 0.45 and 0.90, insert       # gene from parent 2       elif prob < 0.90:         child_chromosome.append(gp2) 
      # otherwise insert random gene(mutate),       # for maintaining diversity       else:         child_chromosome.append(self.mutated_genes()) 
    # create new Individual(offspring) using     # generated chromosome for offspring     return Individual(child_chromosome) 
  def cal_fitness(self):     '''     Calculate fitness score, it is the number of     characters in string which differ from target     string.     '''    global TARGET     fitness = 0    for gs, gt in zip(self.chromosome, TARGET):       if gs != gt: fitness+= 1    return fitness 
# Driver code def main():   global POPULATION_SIZE 
  #current generation   generation = 1
  found = False  population = [] 
  # create initial population   for _ in range(POPULATION_SIZE):         gnome = Individual.create_gnome()         population.append(Individual(gnome)) 
  while not found: 
    # sort the population in increasing order of fitness score     population = sorted(population, key = lambda x:x.fitness) 
    # if the individual having lowest fitness score ie.     # 0 then we know that we have reached to the target     # and break the loop     if population[0].fitness <= 0:       found = True      break
    # Otherwise generate new offsprings for new generation     new_generation = [] 
    # Perform Elitism, that mean 10% of fittest population     # goes to the next generation     s = int((10*POPULATION_SIZE)/100)     new_generation.extend(population[:s]) 
    # From 50% of fittest population, Individuals     # will mate to produce offspring     s = int((90*POPULATION_SIZE)/100)     for _ in range(s):       parent1 = random.choice(population[:50])       parent2 = random.choice(population[:50])       child = parent1.mate(parent2)       new_generation.append(child) 
    population = new_generation 
    print("Generation: {}\tString: {}\tFitness: {}".\       format(generation,       "".join(population[0].chromosome),       population[0].fitness)) 
    generation += 1

  print("Generation: {}\tString: {}\tFitness: {}".\     format(generation,     "".join(population[0].chromosome),     population[0].fitness)) 
if __name__ == '__main__':   main()

输出：

Generation: 1    String: tO{"-?=jH[k8=B4]Oe@}    Fitness: 18Generation: 2    String: tO{"-?=jH[k8=B4]Oe@}    Fitness: 18Generation: 3    String: .#lRWf9k_Ifslw #O$k_    Fitness: 17Generation: 4    String: .-1Rq?9mHqk3Wo]3rek_    Fitness: 16Generation: 5    String: .-1Rq?9mHqk3Wo]3rek_    Fitness: 16Generation: 6    String: A#ldW) #lIkslw cVek)    Fitness: 14Generation: 7    String: A#ldW) #lIkslw cVek)    Fitness: 14Generation: 8    String: (, o x _x%Rs=, 6Peek3   Fitness: 13                           .                            .                            . Generation: 29    String: I lope Geeks#o, Geeks   Fitness: 3Generation: 30    String: I loMe GeeksfoBGeeks    Fitness: 2Generation: 31    String: I love Geeksfo0Geeks    Fitness: 1Generation: 32    String: I love Geeksfo0Geeks    Fitness: 1Generation: 33    String: I love Geeksfo0Geeks    Fitness: 1Generation: 34    String: I love GeeksforGeeks    Fitness: 0

注意：每次算法都以随机字符串开始，因此输出可能会有所不同

从输出中我们可以看到，我们的算法有时会停留在局部最优解，这可以通过更新适应度分数计算算法或调整突变和交叉算子来进一步改进。

二、粒子群优化算法

寻找给定系统特定参数的最优值以满足所有设计要求并同时考虑最低成本的过程称为优化。优化问题存在于所有科学领域。

传统的优化算法（确定性算法）存在一些局限性，例如：

单一解决方案
收敛到局部最优
未知搜索空间问题

为了克服这些限制，许多学者和研究人员开发了多种元启发式方法来解决复杂/未解决的优化问题。

算法的启发

粒子群优化 (PSO) 是一种强大的元启发式优化算法，其灵感来自自然界中观察到的群体行为，例如鱼和鸟群。PSO 是对简化社会系统的模拟。PSO 算法的初衷是图形化地模拟鸟群优雅但不可预测的舞蹈动作。

在自然界中，任何鸟类的可观察范围都限制在某个范围内。但是，如果群中有不止一只鸟，那么群中的所有鸟类都可以意识到适应度函数的更大表面。

让我们用数学模型来模拟上述原理，让群体找到适应度函数的全局最小值

适应度函数

1）Rastrigin函数

Rastrigin函数是一个非凸函数，常被用作优化算法的性能测试问题。

函数方程：

图 1：2 个变量的 Rastrigin 函数

对于优化算法来说，rastrigin 函数是非常具有挑战性的。其复杂的行为导致优化算法经常陷入局部最小值。平面上存在大量余弦振荡会给该函数带来复杂的行为。

2）球体函数

球函数是评估优化算法性能的标准函数。

图 2：2 个变量的球面函数

超参数的选择

问题参数：

维度数 ( d ) = 3
下限 ( minx ) = -10.0
上限 ( maxx ) = 10.0

算法的超参数：

粒子数（N）= 50
最大迭代次数 ( max_iter ) = 100
惯性系数 ( w ) = 0.729
认知系数（c1）= 1.49445
社会系数（c2）= 1.49445

输入

适应度函数
问题参数（如上所述）
种群规模（N）和最大迭代次数（max_iter）
算法特定的超参数（w，c1，c2）

代码

# python implementation of particle swarm optimization (PSO)# minimizing rastrigin and sphere function
import randomimport math # cos() for Rastriginimport copy # array-copying convenienceimport sys   # max float

#-------fitness functions---------
# rastrigin functiondef fitness_rastrigin(position):fitnessVal = 0.0for i in range(len(position)):  xi = position[i]  fitnessVal += (xi * xi) - (10 * math.cos(2 * math.pi * xi)) + 10return fitnessVal
#sphere functiondef fitness_sphere(position):  fitnessVal = 0.0  for i in range(len(position)):    xi = position[i]    fitnessVal += (xi*xi);  return fitnessVal;#-------------------------
#particle class class Particle:def __init__(self, fitness, dim, minx, maxx, seed):  self.rnd = random.Random(seed)
  # initialize position of the particle with 0.0 value  self.position = [0.0 for i in range(dim)]
  # initialize velocity of the particle with 0.0 value  self.velocity = [0.0 for i in range(dim)]
  # initialize best particle position of the particle with 0.0 value  self.best_part_pos = [0.0 for i in range(dim)]
  # loop dim times to calculate random position and velocity  # range of position and velocity is [minx, max]  for i in range(dim):  self.position[i] = ((maxx - minx) *    self.rnd.random() + minx)  self.velocity[i] = ((maxx - minx) *    self.rnd.random() + minx)
  # compute fitness of particle  self.fitness = fitness(self.position) # curr fitness
  # initialize best position and fitness of this particle  self.best_part_pos = copy.copy(self.position)   self.best_part_fitnessVal = self.fitness # best fitness
# particle swarm optimization functiondef pso(fitness, max_iter, n, dim, minx, maxx):# hyper parametersw = 0.729 # inertiac1 = 1.49445 # cognitive (particle)c2 = 1.49445 # social (swarm)
rnd = random.Random(0)
# create n random particlesswarm = [Particle(fitness, dim, minx, maxx, i) for i in range(n)] 
# compute the value of best_position and best_fitness in swarmbest_swarm_pos = [0.0 for i in range(dim)]best_swarm_fitnessVal = sys.float_info.max # swarm best
# computer best particle of swarm and it's fitnessfor i in range(n): # check each particle  if swarm[i].fitness < best_swarm_fitnessVal:  best_swarm_fitnessVal = swarm[i].fitness  best_swarm_pos = copy.copy(swarm[i].position) 
# main loop of psoIter = 0while Iter < max_iter:
  # after every 10 iterations   # print iteration number and best fitness value so far  if Iter % 10 == 0 and Iter > 1:  print("Iter = " + str(Iter) + " best fitness = %.3f" % best_swarm_fitnessVal)
  for i in range(n): # process each particle
  # compute new velocity of curr particle  for k in range(dim):     r1 = rnd.random() # randomizations    r2 = rnd.random()
    swarm[i].velocity[k] = (                 (w * swarm[i].velocity[k]) +                (c1 * r1 * (swarm[i].best_part_pos[k] - swarm[i].position[k])) +                (c2 * r2 * (best_swarm_pos[k] -swarm[i].position[k]))               ) 

    # if velocity[k] is not in [minx, max]    # then clip it     if swarm[i].velocity[k] < minx:    swarm[i].velocity[k] = minx    elif swarm[i].velocity[k] > maxx:    swarm[i].velocity[k] = maxx

  # compute new position using new velocity  for k in range(dim):     swarm[i].position[k] += swarm[i].velocity[k]
  # compute fitness of new position  swarm[i].fitness = fitness(swarm[i].position)
  # is new position a new best for the particle?  if swarm[i].fitness < swarm[i].best_part_fitnessVal:    swarm[i].best_part_fitnessVal = swarm[i].fitness    swarm[i].best_part_pos = copy.copy(swarm[i].position)
  # is new position a new best overall?  if swarm[i].fitness < best_swarm_fitnessVal:    best_swarm_fitnessVal = swarm[i].fitness    best_swarm_pos = copy.copy(swarm[i].position)
  # for-each particle  Iter += 1#end_whilereturn best_swarm_pos# end pso

#----------------------------# Driver code for rastrigin function
print("\nBegin particle swarm optimization on rastrigin function\n")dim = 3fitness = fitness_rastrigin

print("Goal is to minimize Rastrigin's function in " + str(dim) + " variables")print("Function has known min = 0.0 at (", end="")for i in range(dim-1):print("0, ", end="")print("0)")
num_particles = 50max_iter = 100
print("Setting num_particles = " + str(num_particles))print("Setting max_iter = " + str(max_iter))print("\nStarting PSO algorithm\n")


best_position = pso(fitness, max_iter, num_particles, dim, -10.0, 10.0)
print("\nPSO completed\n")print("\nBest solution found:")print(["%.6f"%best_position[k] for k in range(dim)])fitnessVal = fitness(best_position)print("fitness of best solution = %.6f" % fitnessVal)
print("\nEnd particle swarm for rastrigin function\n")

print()print()

# Driver code for Sphere function print("\nBegin particle swarm optimization on sphere function\n")dim = 3fitness = fitness_sphere

print("Goal is to minimize sphere function in " + str(dim) + " variables")print("Function has known min = 0.0 at (", end="")for i in range(dim-1):print("0, ", end="")print("0)")
num_particles = 50max_iter = 100
print("Setting num_particles = " + str(num_particles))print("Setting max_iter = " + str(max_iter))print("\nStarting PSO algorithm\n")


best_position = pso(fitness, max_iter, num_particles, dim, -10.0, 10.0)
print("\nPSO completed\n")print("\nBest solution found:")print(["%.6f"%best_position[k] for k in range(dim)])fitnessVal = fitness(best_position)print("fitness of best solution = %.6f" % fitnessVal)
print("\nEnd particle swarm for sphere function\n")

输出：

Begin particle swarm optimization on rastrigin function
Goal is to minimize Rastrigin's function in 3 variablesFunction has known min = 0.0 at (0, 0, 0)Setting num_particles = 50Setting max_iter    = 100
Starting PSO algorithm
Iter = 10 best fitness = 8.463Iter = 20 best fitness = 4.792Iter = 30 best fitness = 2.223Iter = 40 best fitness = 0.251Iter = 50 best fitness = 0.251Iter = 60 best fitness = 0.061Iter = 70 best fitness = 0.007Iter = 80 best fitness = 0.005Iter = 90 best fitness = 0.000
PSO completed

Best solution found:['0.000618', '0.000013', '0.000616']fitness of best solution = 0.000151
End particle swarm for rastrigin function



Begin particle swarm optimization on sphere function
Goal is to minimize sphere function in 3 variablesFunction has known min = 0.0 at (0, 0, 0)Setting num_particles = 50Setting max_iter    = 100
Starting PSO algorithm
Iter = 10 best fitness = 0.189Iter = 20 best fitness = 0.012Iter = 30 best fitness = 0.001Iter = 40 best fitness = 0.000Iter = 50 best fitness = 0.000Iter = 60 best fitness = 0.000Iter = 70 best fitness = 0.000Iter = 80 best fitness = 0.000Iter = 90 best fitness = 0.000
PSO completed

Best solution found:['0.000004', '-0.000001', '0.000007']fitness of best solution = 0.000000
End particle swarm for sphere function

三、模拟退火算法

模拟退火 (SA) 是一种概率技术，用于寻找优化问题的近似解。它特别适用于大型搜索空间，因为在这种空间中寻找精确解是不切实际的。该算法的灵感来自冶金学中的退火过程。

用 Python 一步步实现模拟退火

步骤 1：了解模拟退火

模拟退火算法的灵感来自冶金学中的退火过程。其关键思想是使用随时间逐渐降低的“温度”参数，使算法能够在高温下更自由地探索解决方案空间，并在温度降低时优化搜索。

第 2 步：定义目标函数

目标函数是我们想要优化（最小化或最大化）的函数。在这个例子中，我们将使用 Rastrigin 函数，它是优化算法的常用基准函数。

import random
def get_neighbor(x, step_size=0.1):    neighbor = x[:]    index = random.randint(0, len(x) - 1)    neighbor[index] += random.uniform(-step_size, step_size)    return neighbor

步骤 3：创建邻居函数

邻域函数通过对当前解进行微小的随机改变来生成新的候选解。

import random
def get_neighbor(x, step_size=0.1):    neighbor = x[:]    index = random.randint(0, len(x) - 1)    neighbor[index] += random.uniform(-step_size, step_size)    return neighbor

步骤 4：实现模拟退火算法

现在我们将实现模拟退火算法。主要部分是初始化解决方案、更新温度、生成新的候选方案以及决定是否接受它们。

def simulated_annealing(objective, bounds, n_iterations, step_size, temp):    # Initial solution    best = [random.uniform(bound[0], bound[1]) for bound in bounds]    best_eval = objective(best)    current, current_eval = best, best_eval    scores = [best_eval]
    for i in range(n_iterations):        # Decrease temperature        t = temp / float(i + 1)        # Generate candidate solution        candidate = get_neighbor(current, step_size)        candidate_eval = objective(candidate)        # Check if we should keep the new solution        if candidate_eval < best_eval or random.random() < math.exp((current_eval - candidate_eval) / t):            current, current_eval = candidate, candidate_eval            if candidate_eval < best_eval:                best, best_eval = candidate, candidate_eval                scores.append(best_eval)
        # Optional: print progress        if i % 100 == 0:            print(f"Iteration {i}, Temperature {t:.3f}, Best Evaluation {best_eval:.5f}")
    return best, best_eval, scores

步骤 5：运行算法

定义问题域，设置参数，并运行模拟退火算法。

# Define problem domainbounds = [(-5.0, 5.0) for _ in range(2)]  # for a 2-dimensional Rastrigin functionn_iterations = 1000step_size = 0.1temp = 10
# Perform the simulated annealing searchbest, score, scores = simulated_annealing(objective_function, bounds, n_iterations, step_size, temp)
print(f'Best Solution: {best}')print(f'Best Score: {score}')

Python 中的模拟退火实现

以下是包含所有步骤的完整代码：

import mathimport random
# Objective function: Rastrigin functiondef objective_function(x):    return 10 * len(x) + sum([(xi**2 - 10 * math.cos(2 * math.pi * xi)) for xi in x])
# Neighbor function: small random changedef get_neighbor(x, step_size=0.1):    neighbor = x[:]    index = random.randint(0, len(x) - 1)    neighbor[index] += random.uniform(-step_size, step_size)    return neighbor
# Simulated Annealing functiondef simulated_annealing(objective, bounds, n_iterations, step_size, temp):    # Initial solution    best = [random.uniform(bound[0], bound[1]) for bound in bounds]    best_eval = objective(best)    current, current_eval = best, best_eval    scores = [best_eval]
    for i in range(n_iterations):        # Decrease temperature        t = temp / float(i + 1)        # Generate candidate solution        candidate = get_neighbor(current, step_size)        candidate_eval = objective(candidate)        # Check if we should keep the new solution        if candidate_eval < best_eval or random.random() < math.exp((current_eval - candidate_eval) / t):            current, current_eval = candidate, candidate_eval            if candidate_eval < best_eval:                best, best_eval = candidate, candidate_eval                scores.append(best_eval)
        # Optional: print progress        if i % 100 == 0:            print(f"Iteration {i}, Temperature {t:.3f}, Best Evaluation {best_eval:.5f}")
    return best, best_eval, scores
# Define problem domainbounds = [(-5.0, 5.0) for _ in range(2)]  # for a 2-dimensional Rastrigin functionn_iterations = 1000step_size = 0.1temp = 10
# Perform the simulated annealing searchbest, score, scores = simulated_annealing(objective_function, bounds, n_iterations, step_size, temp)
print(f'Best Solution: {best}')print(f'Best Score: {score}')

输出：

Iteration 0, Temperature 10.000, Best Evaluation 53.95166Iteration 100, Temperature 0.099, Best Evaluation 49.75767Iteration 200, Temperature 0.050, Best Evaluation 49.74828Iteration 300, Temperatu...

四、蚁群算法

蚁群算法是模拟自然界中蚂蚁的寻路方法而产生的一种仿生算法。蚂蚁在运动过程中，能在所经过的路径上留下一种称为信息素的物质用于信息传递，而蚂蚁在运动过程中能够感知这种物质并利用它引导自己的运动方向，因此由大量蚂蚁组成的蚁群行为表现出一种正向的信息反馈现象：在某条路径上行进的蚂蚁越多，后者选择该路径的概率就越大。

ACO算法的实现需要分析几个要素，即建图、约束、信息素及启发信息、解决方案的构建、信息素更新等。

对于TSP问题：
构建图与问题描述一致，即每条边都有一个权重，表示点间距离。问题的状态是旅行商旅途中出现的所有可能状态的集合。
约束：TSP中唯一的约束条件为旅行商旅途中所有城市必须访问且每个城市只能访问一次。

信息素与启发信息：TSP中信息素表示在访问完城市i之后直接访问城市j的期望，启发信息表示蚂蚁随机选择下一个城市的概率，该值要根据实际情况选取，一般直接取两城市距离的倒数。
解的构建：每只蚂蚁最初从一个随机选择的起始城市出发，每次迭代后，蚂蚁将一个还未访问过的城市加入到解中，所有城市都被蚂蚁访问过后，终止解的构建。在解决方案的构建中，蚂蚁利用信息素和启发式信息以一定的概率P从候选城市中进行选择。

蚂蚁构造的路径越好，在路径的两边获取的信息素就越多。一般来说，如果某条边被更多的蚂蚁选中，并且该边所处的路径总长度越短，那么这条边获取的信息素就越多，在以后的迭代中被蚂蚁选中的概率就越大。

下面是用ACO解决TSP问题的python代码。

#Ant colony optimization to solve TSP problemimport numpy as npimport random as rd
def lengthCal(antPath,distmat):         #Calculate distance    length =[]    dis = 0    for i in range(len(antPath)):        for j in range(len(antPath[i]) - 1):            dis += distmat[antPath[i][j]][antPath[i][j + 1]]        dis += distmat[antPath[i][-1]][antPath[i][0]]        length.append(dis)        dis = 0    return length
distmat = np.array([[0,35,29,67,60,50,66,44,72,41,48,97],                 [35,0,34,36,28,37,55,49,78,76,70,110],                 [29,34,0,58,41,63,79,68,103,69,78,130],                 [67,36,58,0,26,38,61,80,87,110,100,110],                 [60,28,41,26,0,61,78,73,103,100,96,130],                 [50,37,63,38,61,0,16,64,50,95,81,95],                 [66,55,79,61,78,16,0,49,34,82,68,83],                 [44,49,68,80,73,64,49,0,35,43,30,62],                 [72,78,103,87,103,50,34,35,0,47,32,48],                 [41,76,69,110,100,95,82,43,47,0,26,74],                 [48,70,78,100,96,81,68,30,32,26,0,58],                 [97,110,130,110,130,95,83,62,48,74,58,0]])
antNum = 12                   #Ant numberalpha = 1                     #Pheromone importance factorbeta = 3                      #Heuristic function importance factorpheEvaRate = 0.3              #Pheromone evaporation ratecityNum = distmat.shape[0]pheromone = np.ones((cityNum,cityNum))                   #Pheromone matrixheuristic = 1 / (np.eye(cityNum) + distmat) - np.eye(cityNum)       #Heuristic information matrix, take 1/dismatiter,itermax = 1,100                       #Number of iterations
while iter < itermax:    antPath = np.zeros((antNum, cityNum)).astype(int) - 1   # Ant's path    firstCity = [i for i in range(12)]    rd.shuffle(firstCity)          #Randomly assign a starting city for each ant    unvisted = []    p = []    pAccum = 0    for i in range(len(antPath)):        antPath[i][0] = firstCity[i]    for i in range(len(antPath[0]) - 1):       #Gradually update the next city each ant is going to        for j in range(len(antPath)):            for k in range(cityNum):                if k not in antPath[j]:                    unvisted.append(k)            for m in unvisted:                pAccum += pheromone[antPath[j][i]][m] ** alpha * heuristic[antPath[j][i]][m] ** beta            for n in unvisted:                p.append(pheromone[antPath[j][i]][n] ** alpha * heuristic[antPath[j][i]][n] ** beta / pAccum)            roulette = np.array(p).cumsum()               #Generate Roulette            r = rd.uniform(min(roulette), max(roulette))            for x in range(len(roulette)):                if roulette[x] >= r:                      #Use the roulette method to choose the next city to go                    antPath[j][i + 1] = unvisted[x]                    break            unvisted = []            p = []            pAccum = 0    pheromone = (1 - pheEvaRate) * pheromone            #Pheromone volatile    length = lengthCal(antPath,distmat)    for i in range(len(antPath)):        for j in range(len(antPath[i]) - 1):            pheromone[antPath[i][j]][antPath[i][j + 1]] += 1 / length[i]     #Pheromone update        pheromone[antPath[i][-1]][antPath[i][0]] += 1 / length[i]    iter += 1print("The shortest distance is:")print(min(length))print("The shortest path is:")print(antPath[length.index(min(length))])

五、梯度下降

梯度下降是一种流行的优化算法，用于机器学习和深度学习，以找到给定模型的最佳参数或权重。梯度下降的目标是最小化成本函数，该函数衡量模型预测输出与实际输出之间的差异。

该算法通过迭代调整模型参数，沿着成本函数梯度下降最快方向调整，直到达到最小值。梯度是通过对每个参数求成本函数的偏导数来计算的。

梯度下降主要有三种变体：

批量梯度下降：在此变体中，梯度在整个数据集上计算，并且在每个时期之后更新参数。
随机梯度下降：在此变体中，梯度是在单个训练示例上计算的，并且在每个示例之后更新参数。
小批量梯度下降：在此变体中，梯度是在训练数据的一小部分上计算的，并且在每个小批量之后更新参数。

梯度下降用于各种机器学习应用，例如线性回归、逻辑回归和神经网络，以优化模型参数并提高其准确性。它是机器学习中的一种基本算法，对于训练具有大量数据的复杂模型至关重要。

在梯度下降的每次迭代中，参数θ都会根据上述公式进行更新，其中∇J(θ)是使用θ的当前值进行评估的。这意味着在每次迭代中，算法都会朝着成本函数最陡下降的方向迈出一步，步长由学习率决定。学习率决定了每次迭代所采取的步长，需要仔细选择以确保算法收敛到最优解。

梯度下降的实际用例：

梯度下降是机器学习中的一个基本优化算法，具有许多实际用例。以下是一些示例：

线性回归：在线性回归中，梯度下降用于寻找最小化预测值和实际值之间的平方误差和的最佳系数。
逻辑回归：在逻辑回归中，梯度下降用于寻找最小化交叉熵损失函数的最佳参数，该函数衡量预测概率和实际标签之间的差异。
神经网络：在深度学习中，梯度下降用于通过最小化损失函数来优化神经网络的权重和偏差，损失函数衡量预测输出和实际输出之间的差异。
支持向量机 (SVM)：在 SVM 中，梯度下降用于寻找以最大边距将数据点分成不同类别的最佳超平面。
降维：在主成分分析 (PCA) 等技术中，使用梯度下降来寻找捕获数据中最大方差的最佳特征向量。
聚类：在 k 均值等聚类算法中，梯度下降用于通过最小化数据点与其指定聚类质心之间的平方距离和来优化聚类的质心。

实施步骤：

选择一个模型和一个成本函数：

2.初始化参数：

设置想要优化的参数的初始值，例如模型的权重和偏差。

3.计算梯度：

通过对成本函数关于每个参数取偏导数来计算成本函数关于每个参数的梯度。

4.更新参数：

通过将负梯度乘以学习率来调整负梯度方向上的参数，从而控制更新的大小。

5.重复直至收敛：

迭代上述三个步骤，直到代价函数收敛到一个最小值或者一个令人满意的阈值，比如迭代之间代价函数的变化很小。

6.评估模型：

在单独的数据集上测试训练后的模型以评估其性能，例如准确率、精确率、召回率或 F1 分数。

请注意，梯度下降有不同的变体，例如批量梯度下降、随机梯度下降和小批量梯度下降，它们具有不同的计算和收敛特性。实现细节也可能因所使用的具体模型和库而异。

代码

import numpy as np import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D 
# 定义要最小化的函数（简单的二次函数）def  f ( x, y ):     return x** 2 + y** 2 
# 定义函数关于 x 和 y 的偏导数def  df_dx ( x, y ):     return  2 * x 
def  df_dy ( x, y ):     return  2 * y 
# 定义梯度下降算法def  gradient_descent ( start_x, start_y, learning_rate, num_iterations ):     # 初始化参数    x = start_x     y = start_y     history = [] 
    # 执行梯度下降迭代    for i in  range (num_iterations):         # 计算梯度        grad_x = df_dx(x, y)         grad_y = df_dy(x, y) 
        # 更新参数        x = x - learning_rate * grad_x         y = y - learning_rate * grad_y 
        # 保存参数的历史记录        history.append((x, y, f(x, y))) 
    return x, y, f(x, y), history 
# 定义用于绘制函数的网格x_range = np.arange(- 10 , 10 , 0.1 ) y_range = np.arange(- 10 , 10 , 0.1 ) X, Y = np.meshgrid(x_range, y_range) Z = f(X, Y) 
# 执行梯度下降并绘制结果start_x, start_y = 8 , 8 learning_rate = 0.1 num_iterations = 20 x_opt, y_opt, f_opt, history = gradient_descent(start_x, start_y, learning_rate, num_iterations) 
fig = plt.figure() ax = fig.add_subplot( 111 , projecting= '3d' ) ax.plot_surface(X, Y, Z, cmap= 'coolwarm' ) ax.scatter(* zip (*history), c= 'r' , marker= 'o' ) ax.set_xlabel( 'x' ) ax.set_ylabel( 'y' ) ax.set_zlabel( 'f(x, y)' ) plt.show()

此实现定义了一个简单的二次函数f(x, y) = x^2 + y^2及其偏导数df_dx(x, y) = 2x和df_dy(x, y) = 2y。然后，它定义了gradient_descent()函数，该函数以起点(start_x, start_y)、学习率learning_rate和迭代次数num_iterations作为输入，并返回函数的最佳点(x_opt, y_opt)和最小值f_opt，以及迭代过程中参数值的历史记录history。网格用于绘制函数，并使用在 3D 图中绘制梯度下降算法的结果matplotlib

python、matlab程序设计找我

— 完 —

进修编程

提升编程技能，学习编程技巧