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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http