共查询到20条相似文献,搜索用时 187 毫秒
1.
In this paper we propose an Ant Colony Optimisation (ACO) algorithm for defining the signal settings on urban networks following a local approach. This consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses to the same intersection, taking account of the effects of signal settings on costs and on user route choices. This problem, also known as Local Optimisation of Signal Settings (LOSS), has been widely studied in the literature and can be formulated as an asymmetric assignment problem. The proposed ACO algorithm is based on two kinds of behaviour of artificial ants which allow the LOSS problem to be solved: traditional behaviour based on the response to pheromones for simulating user route choice, and innovative behaviour based on the pressure of an ant stream for solving the signal setting definition problem. Our results on real-scale networks show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in traditional MSA (Method of Successive Averages) approaches. 相似文献
2.
《European Journal of Operational Research》2006,175(3):1682-1695
This paper concerns the urban road network design problem. In urban areas supply has usually been unable to keep pace with increasing demand: the only possibility is often to reorganise the current supply configuration in order to use existing resources efficiently. Thus, in urban areas signal settings and network topology (in particular lane layout) are the two major factors that can be handled by design models. Methods for the combined design of signal settings and topology are proposed in this paper. All the methods proceed in two stages: the first deals with integer variables (topology), while the second deals with continuous variables (signal settings). Some metaheuristics (Hill Climbing, Simulated Annealing, Tabu Search, Genetic Algorithms and Path Relinking) are specified for the topology design stage, and they are used singularly or jointly. The continuous part of the solution, with fixed topology is optimized through an algorithm for asymmetrical deterministic equilibrium assignment. This paper focuses on evaluating performances obtained by all the different algorithms proposed for the topology design stage. The algorithms are compared by applications to real networks, and some conclusions are drawn about their efficiency. 相似文献
3.
In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function,
subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing,
magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions
are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time
approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian
product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which
are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate
homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation
performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we
consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose
polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating
the effectiveness of the approximation algorithms studied. 相似文献
4.
The Energy Balance Principle (EBP) is well established for estimating the vibration levels of wind induced oscillations of single overhead transmission lines. The mathematical model, wherein a conductor is treated as a continuous system, results in a transcendental eigenvalue problem (EVP), which gives numerical difficulties in the case of bundled conductors. In this paper, different approaches for solving transcendental EVP and their relative merits are discussed. A new method named continuous spectrum approach provides a good engineering solution. Results from different approaches are compared. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
5.
Gabriele Eichfelder 《Computational Optimization and Applications》2009,44(2):249-273
In this paper several parameter dependent scalarization approaches for solving nonlinear multi-objective optimization problems
are discussed. It is shown that they can be considered as special cases of a scalarization problem by Pascoletti and Serafini
(or a modification of this problem).
Based on these connections theoretical results as well as a new algorithm for adaptively controlling the choice of the parameters
for generating almost equidistant approximations of the efficient set, lately developed for the Pascoletti-Serafini scalarization,
can be applied to these problems. For instance for such well-known scalarizations as the ε-constraint or the normal boundary intersection problem algorithms for adaptively generating high quality approximations are
derived. 相似文献
6.
Josef Kallrath 《Optimization Letters》2011,5(3):453-466
Based on the Greek term monolithos (stone consisting of one single block) Kallrath (Comput Chem Eng 33:1983–1993, 2009) introduced the term polylithic for modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved by tailor-made
methods involving several models and/or algorithmic components, in which the solution of one model is input to another one.
This can be exploited to initialize certain variables, or to provide bounds on them (problem-specific preprocessing). Mathematical
examples of polylithic approaches are decomposition techniques, or hybrid methods in which constructive heuristics and local
search improvement methods are coupled with exact MIP algorithms. Tailor-made polylithic solution approaches with thousands
or millions of solve statements are challenges on algebraic modeling languages. Local objects and procedural structures are
almost necessary. Warm-start and hot-start techniques can be essential. The effort of developing complex tailor-made polylithic
solutions is awarded by enabling us to solve real-world problems far beyond the limits of monolithic approaches and general
purpose solvers. 相似文献
7.
A non-linear area traffic control system with limited capacity is considered in this paper. Optimal signal settings and link capacity expansions can be determined while trip distribution and network flow are in equilibrium. This problem can be formulated as a non-linear mathematical program with equilibrium constraints. For the objective function a non-linear constrained optimization program for signal settings and link capacity expansion is determined. For the constraint set the elastic user equilibrium traffic assignment obeying Wardrop’s first principle can be formulated as a variational inequality. Since the constrained optimization problem is non-convex, only local optima can be obtained. In this paper, a novel algorithm using a non-smooth trust region approach is proposed. Numerical tests are performed using a real data city network and various example test networks in which the effectiveness and robustness of the proposed method are confirmed as compared to other well-known solution methods. 相似文献
8.
《European Journal of Operational Research》2006,169(2):508-519
Artificial neural networks (ANN) have been widely used for both classification and prediction. This paper is focused on the prediction problem in which an unknown function is approximated. ANNs can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e., to minimize the error over the training set). Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been successfully applied to solve this problem. In this paper we propose a path relinking implementation to solve the neural network training problem. Our method uses GRG, a gradient-based local NLP solver, as an improvement phase, while previous approaches used simpler local optimizers. The experimentation shows that the proposed procedure can compete with the best-known algorithms in terms of solution quality, consuming a reasonable computational effort. 相似文献
9.
Different methodologies have been introduced in recent years with the aim of approximating unknown functions. Basically, these methodologies are general frameworks for representing non-linear mappings from several input variables to several output variables. Research into this problem occurs in applied mathematics (multivariate function approximation), statistics (nonparametric multiple regression) and computer science (neural networks). However, since these methodologies have been proposed in different fields, most of the previous papers treat them in isolation, ignoring contributions in the other areas. In this paper we consider five well known approaches for function approximation. Specifically we target polynomial approximation, general additive models (Gam), local regression (Loess), multivariate additive regression splines (Mars) and artificial neural networks (Ann).Neural networks can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e. to minimize the error over the training set). Although the most popular method for Ann training is back propagation, other optimization methods based on metaheuristics have recently been adapted to this problem, outperforming classical approaches. In this paper we propose a short term memory tabu search method, coupled with path relinking and BFGS (a gradient-based local NLP solver) to provide high quality solutions to this problem. The experimentation with 15 functions previously reported shows that a feed-forward neural network with one hidden layer, trained with our procedure, can compete with the best-known approximating methods. The experimental results also show the effectiveness of a new mechanism to avoid overfitting in neural network training. 相似文献
10.
Enrico Malaguti 《4OR: A Quarterly Journal of Operations Research》2009,7(1):101-104
This is a summary of the author’s PhD thesis supervised by Paolo Toth and defended on 29 May 2007 at the Università di Bologna.
The thesis is written in English and is available from the author upon request. The first part of this work deals with the
Vertex Coloring Problem and its generalizations, for which models, bounds and algorithms are proposed. The Second Part is dedicated to a different
problem on graphs, namely a Routing Problem in telecommunication networks where not only the efficiency, but also the fairness of the solution is considered.
相似文献
11.
In this article, we study a class of problems where the sum of truncated convex functions is minimized. In statistical applications, they are commonly encountered when ?0-penalized models are fitted and usually lead to NP-Hard non-convex optimization problems. In this article, we propose a general algorithm for the global minimizer in low-dimensional settings. We also extend the algorithm to high-dimensional settings, where an approximate solution can be found efficiently. We introduce several applications where the sum of truncated convex functions is used, compare our proposed algorithm with other existing algorithms in simulation studies, and show its utility in edge-preserving image restoration on real data. 相似文献
12.
A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L2-convex functions and M2-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35 相似文献
13.
Dorit S. Hochbaum 《Annals of Operations Research》2007,153(1):257-296
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005. 相似文献
14.
《Operations Research Letters》2022,50(6):627-631
Distributed consensus optimization has received considerable attention in recent years and several distributed consensus-based algorithms have been proposed for (nonsmooth) convex and (smooth) nonconvex objective functions. However, the behavior of these distributed algorithms on nonconvex, nonsmooth and stochastic objective functions is not understood. Such class of functions and distributed setting are motivated by several applications, including problems in machine learning and signal processing. This paper presents the first convergence analysis of the decentralized stochastic subgradient method for such classes of problems, over networks modeled as undirected, fixed, graphs. 相似文献
15.
Neurodynamical Optimization 总被引:2,自引:0,他引:2
Dynamical (or ode) system and neural network approaches for optimization have been co-existed for two decades. The main feature of the two approaches is that a continuous path starting from the initial point can be generated and eventually the path will converge to the solution. This feature is quite different from conventional optimization methods where a sequence of points, or a discrete path, is generated. Even dynamical system and neural network approaches share many common features and structures, yet a complete comparison for the two approaches has not been available. In this paper, based on a detailed study on the two approaches, a new approach, termed neurodynamical approach, is introduced. The new neurodynamical approach combines the attractive features in both dynamical (or ode) system and neural network approaches. In addition, the new approach suggests a systematic procedure and framework on how to construct a neurodynamical system for both unconstrained and constrained problems. In analyzing the stability issues of the underlying dynamical (or ode) system, the neurodynamical approach adopts a new strategy, which avoids the Lyapunov function. Under the framework of this neurodynamical approach, strong theoretical results as well as promising numerical results are obtained. 相似文献
16.
M Colebrook J Gutiérrez S Alonso J Sicilia 《The Journal of the Operational Research Society》2002,53(12):1357-1366
Recent papers have developed efficient algorithms for the location of an undesirable (obnoxious) 1-center on general networks with n nodes and m edges. Even though the theoretical complexity of these algorithms is fine, the computational time required to get the solution can be diminished using a different model formulation and slightly improving the upper bounds. Thus, we present a new O(mn) algorithm, which is more straightforward and computationally faster than the previous ones. Computing time results comparing the former approaches with the proposed algorithm are supplied. 相似文献
17.
Global Minimization Algorithms for Holder Functions 总被引:1,自引:0,他引:1
This paper deals with the one-dimensional global optimization problem where the objective function satisfies a Hölder condition over a closed interval. A direct extension of the popular Piyavskii method proposed for Lipschitz functions to Hölder optimization requires an a priori estimate of the Hölder constant and solution to an equation of degree N at each iteration. In this paper a new scheme is introduced. Three algorithms are proposed for solving one-dimensional Hölder global optimization problems. All of them work without solving equations of degree N. The case (very often arising in applications) when a Hölder constant is not given a priori is considered. It is shown that local information about the objective function used inside the global procedure can accelerate the search signicantly. Numerical experiments show quite promising performance of the new algorithms. 相似文献
18.
This paper introduces a novel niching scheme called the q-nearest neighbors replacement (q-NNR) method in the framework of the steady-state GAs (SSGAs) for solving binary multimodal optimization problems. A detailed
comparison of the main niching approaches are presented first. The niching paradigm and difference of the selection-recombination
genetic algorithms (GAs) and the recombination-replacement SSGAs are discussed. Then the q-NNR is developed by adopting special replacement policies based on the SSGAs; a Boltzmann scheme for dynamically sizing the
nearest neighbors set is designed to achieve a speed-up and control the proportion of individuals adapted to different niches.
Finally, experiments are carried out on a set of test functions characterized by deception, epistasis, symmetry and multimodality.
The results are satisfactory and illustrate the effectivity and efficiency of the proposed niching method. 相似文献
19.
Approximating Networks and Extended Ritz Method for the Solution of Functional Optimization Problems
Zoppoli R. Sanguineti M. Parisini T. 《Journal of Optimization Theory and Applications》2002,112(2):403-440
Functional optimization problems can be solved analytically only if special assumptions are verified; otherwise, approximations are needed. The approximate method that we propose is based on two steps. First, the decision functions are constrained to take on the structure of linear combinations of basis functions containing free parameters to be optimized (hence, this step can be considered as an extension to the Ritz method, for which fixed basis functions are used). Then, the functional optimization problem can be approximated by nonlinear programming problems. Linear combinations of basis functions are called approximating networks when they benefit from suitable density properties. We term such networks nonlinear (linear) approximating networks if their basis functions contain (do not contain) free parameters. For certain classes of d-variable functions to be approximated, nonlinear approximating networks may require a number of parameters increasing moderately with d, whereas linear approximating networks may be ruled out by the curse of dimensionality. Since the cost functions of the resulting nonlinear programming problems include complex averaging operations, we minimize such functions by stochastic approximation algorithms. As important special cases, we consider stochastic optimal control and estimation problems. Numerical examples show the effectiveness of the method in solving optimization problems stated in high-dimensional settings, involving for instance several tens of state variables. 相似文献
20.
We review the modern approaches to the synthesis of robust H
∞ controllers that ensure optimal damping of oscillations in dynamical systems under uncertainty. In the synthesis method based
on Riccati equations, these many-parameter equations can be solved only when the parameters are contained in a bounded parallelepiped
with given boundaries. The synthesis of a robust H
∞ output control for systems with unknown bounded parameters is reducible to the solution of an optimization problem constrained
by a system of linear matrix inequalities. The proposed controller synthesis algorithms are implemented using standard MATLAB
procedures. The efficiency of the proposed methods and algorithms is demonstrated in application to optimal damping of oscillations
in a parametrically excited pendulum.
__________
Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 87–104, 2004. 相似文献