最优化算法概述以及常见分类
通俗的来说,最优化问题就是在一定的条件约束下,使得效果最好。最优化问题是一种数学问题,是研究在给定的约束之下如何求得某些因素的量,来使得某一指标达到最优的学科。
工程设计中最优化问题的一般说法是:选择一组参数,在满足一系列有关的限制条件的情况下,使得目标值达到最优。在进行工程设计的时候,将工程设计问题表示成数学问题,再用最优化的方法进行求解。
对于一组可以用列向量X表示的变量,数学模型我们可以描述为:
最优化问题可以分为函数优化问题和组合优化问题两大类。函数优化问题的对象是一定区间的连续变量,解决的是连续性问题;组合优化的对象解空间是离散状态,也就是解决的是离散问题。典型的组合优化问题有旅行商(Traveling salesman problem,TSP)问题、加工调度问题(Scheduling problem,如Flow-shop,Job-shop)、0-1背包问题(Knapsack problem)、装箱问题(Bin packing problem)、图着色问题(Graph coloring problem)、聚类问题(Clustering problem)等。
采用最优化算法解决实际问题主要分为两个大的步骤:
- 建立数学模型:对可行方案进行编码,约束条件以及目标函数的构造。
- 最优值得搜索策略:在约束条件下,在可行解里面搜索最优解的方法有穷举法,随机搜索以及启发式搜索算法。
最优化算法,其实就是一种搜索过程或规则,它是基于某种思想和机制,通过一定的途径或规则来得到满足用户要求的问题的解。
优化问题相关算法分类如下:
?
精确算法计算复杂性一般很大,只适合于求解小规模问题,在工程中往往不实用。
启发式算法:一个基于直观或经验构造的算法,在可接受的时间和空间开销下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。
元启发式算法(MetaHeuristic Algorigthm)是启发式算法的改进,它是随机算法与局部搜索算法相结合的产物。
个体启发:寻找相对最优
群体智能:寻找全局最优
?
参考:
[1]?https://blog.csdn.net/qq997843911/article/details/83445318
?