Local optimum

Résumé

In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which is the optimal solution among all possible solutions, not just those in a particular neighborhood of values. Importantly, a global optimum is necessarily a local optimum, but a local optimum is not necessarily a global optimum. Continuous domain When the function to be optimized is continuous, it may be possible to employ calculus to find local optima. If the first derivative exists everywhere, it can be equated to zero; if the function has an unbounded domain, for a point to be a local optimum it is necessary that it satisfy this equation. Then the second derivative test provides a sufficient condition for the point to be a local maximum or local minimum. Search techniques Local search or hill climbing methods for solving

Source officielle

https://en.wikipedia.org/wiki/Local_optimum

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (25)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (4)

Afficher plus

Unités associées

Chargement

Concepts associés (5)

Concepts associés

Chargement

Cours associés (16)

Cours associés

Chargement

Séances de cours associées (25)

Afficher plus

Séances de cours associées

Chargement

, ,

paper studies exploiting action-level learning (imitation) in the optimal control problem context. Cost functions defined by the optimal control methods are similar to the goal-level learning (emulation) in animals. However, imitating the robot's or others' (e.g. human's) previous experiences (demonstrations) could help the system to improve its performances. We propose to use demonstrations more efficiently by predicting an initialization for the optimal control problems (OCPs) and adding an imitation term to the cost functions. While the predicted initial guess initializes the OCPs close to their local optima, the imitation term guides the optimization, resulting in a faster convergence rate. We test our algorithm in a physical assistive task where a robot should help a human perform a sit-to-stand (STS) task. We define this task as two optimal control problems. The first OCP predicts the human's desired assistance and the other one controls the robot. We have tested our method on different experiments with different conditions for the human in which the robot should quickly solve the two optimization problems exploiting some demonstrations of how it can perform the task. Our proposed method reduced the number of iterations by more than 90% and 70% for the human assistance prediction and the robot controller, respectively, compared to the standard problem which does not take the demonstrations into account.

IEEE2021

Chargement

The Minimization of Public Facilities With Enhanced Genetic Algorithms Using War Elimination

Michael Mark

In this paper, we focus on the problem of minimizing a network of state facilities that provide essential public services (schools, offices, and hospitals). The goal is to reduce the size of the network in order to minimize the costs associated with it. However, it is essential that every customer should be able to access an appropriate service center within a reachable distance. This problem can arise in various scenarios, such as a government cutting back on public service spending in remote areas or as a reaction to changing demographics (population increase/decrease). In general, this task is NP-hard which makes the problem particularly hard to scale. Therefore, for larger problems, heuristic methods must be employed to find an approximation of the optimum. To solve this problem with satisfactory results, we have presented an enhanced version of the genetic algorithm based on war elimination and migration operations. This modification overcomes the well-known shortcoming of GAs when the population becomes gradually more and more similar, these results in a diversity decrease which in turn leads to a sub-optimal local minimum. We test the performance of the novel algorithm against the standard heuristic benchmarks on the widely accepted Beasley OR-library dataset for optimization problems. Finally, we provide a case study based on real data, where a municipality tries to minimize the number of schools in a region while satisfying accessibility and other region-specific constraints.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Chargement

Variable space search for graph coloring

Matthieu Plumettaz, Nicolas Zufferey

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms. (c) 2008 Elsevier B.V. All rights reserved.

2008

Chargement