|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/discrete-optimization/
课程评论：没有评论
课程名称：离散优化数据科学启发式与元启发式方法 课程概述：离散优化是我们日常生活中经常使用的一个概念，例如在餐厅点餐、选择学习科目或尝试新活动时，我们常常需要在多个选择中找到最符合我们目标的最佳方案。当这种选择被形式化，即将目标及每个选项实现目标的能力量化时，我们就得到了一个可优化的数学表达式。 传统的优化方法是列举所有解决方案并从中选择最佳方案，这是解决任何优化问题的理想方式，理论上能始终找到全局最优解，但这种暴力解决方案仅适用于特征较少的小型问题。当问题的维度开始增加时，暴力求解因耗时而变得不可行。这时，我们需要寻找更好的解决方法，这引出了如贪心算法等启发式方法，尽管这种方法能快速给出可接受的解决方案，但不一定能找到最优解，从而产生了准确性与速度之间的权衡，而没有这种权衡，许多实际问题就无法解决。 优化问题通常被视为找到一系列城市间最短路线的过程，这被称为旅行商问题（TSP），大多数离散优化问题可以很容易地归约为TSP。课程中探讨了不同算法来解决这一问题，通过多个实例（如TSP和背包问题）来实际演示这些解决方法。 受自然启示的元启发式算法为优雅地解决离散优化问题提供了绝佳途径。例如，1990年代Marco Dorigo提出的蚁群优化算法（ACO），被视为解决TSP的最先进方法。课程将实时的真实案例与优化问题联系起来，并用数学语言进行阐述。课程逐步清晰地介绍了解决TSP的方法，通过不同的方法解决三个逐步增加难度的示例问题，并比较各自的结果。
Discrete Optimization is something all of us use in our daily activities when say, we order at a restaurant, decide which subject to study, take up a new activity… or look for a change. It comprises of choosing between alternatives that best suit some objective we have in mind. When such things are formalized, i.e. the objective and the ability of each choice to fulfill that objective are quantified, we get a mathematical expression of the problem we would optimize.The classical or statistical method of enumerating all solutions and choosing the best out of them is the ideal way of solving any optimization problem, and will always lead to the global optimal solution- however complex be the discrete optimization (or Combinatorics) problem. But such a brute force solution is only feasible for some smaller problems involving a handful of features. As soon as the dimension of the problem starts growing, brute force fails, sheerly from time considerations. We then have to think of better ways to solve… and come across methods or heuristics such as a greedy algorithm, which chooses the most beneficial solution step at each iteration. Such a procedure gives an acceptable solution fast enough, but not always able to find the shortest route (our original objective). This results in a compromise or trade-off between accuracy and speed, without which most practical problems would never be solved.The major treatise of optimization is considered equivalent to finding the shortest route through a series of cities. This comprises the generic Travelling Salesman Problem (TSP), generic in the sense that most discrete optimization problems can be reduced to the TSP very easily. Different algorithms can be employed to solve this problem. The solution methods in this discrete optimization course are practically illustrated with different instances of the TSP (and a knapsack problem) as examples.Nature-inspired metaheuristics give us some excellent ways to solve a discrete optimization problem in an elegant way. Ant Colony Optimization (ACO) is one such algorithm proposed by Marco Dorigo in the 1990's, and is considered a state-of-the-art method to solve the TSP.The course progressively relates live real-world experiences to optimization problems and casts them in the language of mathematics. The methods to solve the TSP is introduced lucidly, and with care. Three example problems of increasing difficulty are solved through different methods introduced in the course, and their individual results compared.
