Python 和 Java 代码实现:黄金分割法求解一维最优化问题

本文主要是介绍Python 和 Java 代码实现:黄金分割法求解一维最优化问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Python 和 Java 代码实现:黄金分割法求解一维最优化问题

  • 问题描述
    • 区间消去法
    • 黄金分割法
  • 代码实现
    • Python代码
    • Java代码
  • 求解实例

开启一个新系列的学习,这位大佬的文章写的很通透,且有代码实践,个人觉得只有自己把代码写出来了才是真的会了,我对自己的算法学习要求也是这样的,所以推荐!

问题描述

我不是运筹学科班出身,工作之前只做过梯度优化算法和智能优化算法在航天场景中的改进和应用。毕业后虽然选择了运筹优化算法工程师的道路,但却深知自己的运筹认知不够体系化,很想找些书,系统补一下这方面的基础内容。

不过现在国内的运筹学教材大多都是单纯形法起步,看起来挺费劲的。而且我的关注点有:算法原理、不同算法间的联系和区别、工程(Python/Java)实现等,很多内容书上也很难都有。所以我打算基于一些比较简单的优化问题为起点,从简单到复杂,自行去认识和理解这些运筹优化算法。

能想到的最简单的优化问题,应该就是一维最优化问题了:在一个搜索区间内,包含了目标函数的极小值点,而且是个单峰区间,即在该区间内目标函数只有一个极值,下图为一维最优化问题的示意图。图片

区间消去法

在这里插入图片描述

图片

按照以上逻辑不断选取两个点做对比,便可以不断缩小搜索区间,直至搜索区间的长度低于某阈值,即找到了极小值。

在这里插入图片描述

黄金分割法

区间消去法虽然给出了搜索区间缩小的原理,但是每次和该如何选择,却并没有给出具体方案。黄金分割法便在区间消去法的基础上,对c和d的选择做了约束,进而给出它们的确定逻辑:

在这里插入图片描述

代码实现

本文会基于Python和Java语言进行算法实现。Python代码简单,便于学习理解;Java运行速度快,便于工程应用;MATLAB版本就不考虑了,对运筹优化算法的学习和落地应用而言,MATLAB基本没有多少竞争力。

在这里插入图片描述

Python代码

以下的golden_section函数为黄金分割法的Python代码。除该代码外,主函数中还增加了一个for循环,该循环的目的是多次重复调用黄金分割法,以此评估Python代码的计算耗时。

import time  # 待优化函数  
def f(t):  return t ** 2 - t * 5 + 8  def golden_section(a, b, eps):  # 统计迭代次数  cnt = 0  while b - a > eps:  # 根据黄金分割法规则选择内部两点  c = a + (b - a) * 0.382  d = a + (b - a) * 0.618  # 区间消去原理  if f(c) < f(d):  b = d  else:  a = c  cnt += 1  # 两点的中点定义为最优解  return (a + b) / 2, f((a + b) / 2), cnt  if __name__ == '__main__':  # 参数设置  left_point = 1  right_point = 7  min_interval_value = 0.1  # 调用黄金分割法函数求解最小值  best_x, best_y, iter_cnt = 0, 0, 0  t0 = time.time()  for i in range(100000):  best_x, best_y, iter_cnt = golden_section(left_point, right_point, min_interval_value)  print('总耗时为:{} ms'.format((time.time() - t0) * 1000))  print('best_x: {}, best_y: {}, iter_cnt: {}.'.format(best_x, best_y, iter_cnt))  

Java代码

以下的goldenSection函数为黄金分割法的Java代码。与上文一样,主函数中也增加了一个for循环,以此评估Java代码的计算耗时。

public class GoldenSection {  // 主函数入口  public static void main(String[] args) {  // 参数设置  int leftPoint = 1;  int rightPoint = 7;  double minIntervalValue = 0.1;  long t0 = System.currentTimeMillis();  Solution best_solution = new Solution();  for (int i = 0; i < 100000; i++) {  // 调用黄金分割法函数求解最小值  best_solution = goldenSection(leftPoint, rightPoint, minIntervalValue);  }  System.out.println("计算总耗时为: " + (System.currentTimeMillis()-t0) + " ms");  // 输出优化结果  System.out.println("best_x: " + best_solution.best_x);  System.out.println("best_y: " + best_solution.best_y);  System.out.println("cnt: " + best_solution.cnt);  }  // 黄金分割法  private static Solution goldenSection(double a, double b, double eps) {  // 统计迭代次数  int cnt = 0;  while (b - a > eps) {  // 根据黄金分割法规则选择内部两点  double c = a + (b - a) * 0.382;  double d = a + (b - a) * 0.618;  // 区间消去原理  if (f(c) < f(d)) {  b = d;  } else {  a = c;  }  // 更新迭代次数  cnt ++;  }  // 构造最优解对象  Solution best_solution = new Solution();  best_solution.best_x = (a + b) / 2;  best_solution.best_y = f((a + b) / 2);  best_solution.cnt = cnt;  return best_solution;  }  // 待优化函数  private static double f(double t) {  return t * t - t * 5 + 8;  }  // 解对象  private static class Solution {  double best_x;  double best_y;  int cnt;  }  
}  

求解实例

首先运行Python代码,可以得到最优解为1.75,迭代次数为9次。计算100000次,共耗时515毫秒。

总耗时为:515.2740478515625 ms  
best_x: 2.5045211503093046, best_y: 1.7500204408001192, iter_cnt: 9.  

再运行Java代码,可以得到和Python代码相同的解。计算100000次,仅耗时11毫秒。相比之下,Java代码耗时仅为Python代码耗时的2%。对运筹优化算法来说,计算速度是非常重要的,所以如果代码能力允许,尽量使用Java。

计算总耗时为: 11 ms  
best_x: 2.5045211503093046  
best_y: 1.7500204408001192  
cnt: 9  

这篇关于Python 和 Java 代码实现:黄金分割法求解一维最优化问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/614094

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、