算法优化一般目标是:缩小搜索范围,以找到最佳(或接近最佳)的解决方案。
算法优化不得不提软件是OR-Tools :https://developers.google.com/optimization
安装:
python -m pip install --upgrade --user ortools# LINUX sudo apt-get -y install python3-dev python3-wheel python3-setuptools python3-six # for check version python3 --version python3 -c "import platform; print(platform.architecture()[0])" python3 -m pip --version # install python -m pip install -U --user ortools # uninstall python -m pip uninstall ortools # for test python -c "from ortools.linear_solver import pywraplp" # mac # brew update /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" brew update # install python3 brew install python python3 -m pip install -U --user wheel six # install and uninstall save as linux
使用:
OR-Tools是一个用于优化的开源软件套件,可解决世界上最棘手的问题,包括车辆路线,流量,整数和线性编程以及约束编程。vehicle routing, flows, integer and linear programming, and constraint programming.
车辆路线:找到在有限制的情况下(例如,“这辆卡车的重量不能超过20,000磅”或“必须在两个小时内完成所有送货”)来提取和运送包裹的车队的最佳路线。计划:针对一组固定的机器或其他资源,找到一组复杂任务的最佳计划,其中一些任务需要先执行。垃圾箱包装:将尽可能多的各种大小的物品装入最大容量的固定数量的垃圾箱中。 在大多数情况下,诸如此类的问题具有大量可能的解决方案,以至于计算机无法一一搜索它们。为了克服这个问题,OR-Tools使用最先进的算法来缩小搜索范围,以找到最佳(或接近最佳)的解决方案。
OR-Tools包括用于以下方面的求解器:
约束编程:用于找到表示为约束的问题的可行解决方案的一组技术(例如,一个房间不能同时用于两个事件,或者到农作物的距离必须小于软管的长度,或不超过五个电视节目可以立即录制)。线性和混合整数编程:Glop线性优化器在给定一组线性不等式作为约束的情况下,找到了线性目标函数的最优值(例如,分配人员到工作中,或在最小化成本的同时找到一组资源的最佳分配)。 Glop和混合整数编程软件SCIP也可以通过Google Apps脚本优化服务获得。车辆路线:一个专门的库,用于在给定约束的情况下识别最佳车辆路线。图算法:用于在图形,最小成本流,最大流和线性和分配中查找最短路径的代码。
什么是优化问题? 优化的目的是从大量可能的解决方案中找到最佳的解决方案。
假设一家运输公司使用卡车车队向其客户运送包裹。每天,公司必须为卡车分配包裹,然后为每辆卡车选择运送包裹的路线。根据卡车的总行驶距离以及可能的其他因素,每种可能的包裹和路线分配都有成本。问题在于如何选择成本最低的包裹和路线。
像所有优化问题一样,此问题包含以下元素:
目标-您要优化的数量。在上面的示例中,目标是最小化成本。要设置优化问题,您需要定义一个函数,该函数可以为任何可能的解决方案计算目标值。这称为目标函数objective function。在前面的示例中,目标函数将计算包裹和路线的任何分配的总成本。最佳解决方案是目标函数的值最佳的解决方案。 (“最佳”可以是最大值或最小值。)约束-根据问题的特定要求,对可能的解决方案集的约束。例如,如果运输公司无法将超过给定重量的包裹分配给卡车,这将对解决方案造成限制。一种可行的解决方案是满足问题的所有给定约束,而不必是最优的。 解决优化问题的第一步是确定目标和约束。
确定您要解决的问题的类型 世界上有许多不同类型的优化问题。对于每种类型的问题,都有不同的方法和算法来找到最佳解决方案。在开始编写程序来解决优化问题之前,您需要确定要处理的问题的类型,然后选择合适的求解器-一种用于查找最佳解决方案的算法。
Linear optimizationConstraint optimizationMixed-integer optimizationBin packingNetwork flowsAssignmentSchedulingRouting线性和约束优化请参考:https://blog.csdn.net/AS7062031/article/details/108327552