共查询到19条相似文献,搜索用时 140 毫秒
1.
构造了求解一类带不等式约束的min-max-min问题的区间算法,其中目标函数和约束函数都是一阶连续可微函数,证明了方法的收敛性,给出了数值算例.该方法可以同时求出问题的最优值和全部全局最优解,是有效和可靠的. 相似文献
2.
一类约束不可微优化问题的区间极大熵方法 总被引:23,自引:0,他引:23
本文研究求解不等式约束离散minimax问题的区间算法,其中目标函数和约束函数是 C~1类函数.利用罚函数法和极大熵函数思想将问题转化为无约束可微优化问题,讨论了极大熵函数的区间扩张,证明了收敛性等性质,提出了无解区域删除原则,建立了区间极大熵算法,并给出了数值算例.该算法是收敛、可靠和有效的. 相似文献
3.
本文将熵函数的思想和区间分析相结合,构造了一类线性规划问题的区间调节熵算法,讨论了调节熵函数的区间扩张及其收敛阶,以及相关的区域删除检验原则,证明了算法的收敛性,给出了数值算例.理论与数值结果表明该方法是可靠和有效的. 相似文献
4.
求非光滑全局优化问题的区间算法 总被引:2,自引:0,他引:2
本文通过区间工具和目标函数的特殊导数提出了一个非光滑全局优化问题的区间算法,所提出的方法能给出问题的全部全局极小点及全局极小值,理论分析和数值结构均表明本文方法是有效的。 相似文献
5.
6.
7.
求多变量非光滑函数所有总体极小点的区间算法 总被引:2,自引:1,他引:1
本文通过区间分析和目标函数的特殊导数,建立寻求X^0属于R^n上一类非光滑函数所有总体极小点的区间算法。理论分析和数值结果均表明本文算法是可靠和有效的。 相似文献
8.
9.
提出利用Legendre小波函数去获得第一类Fredholm积分方程的数值解,函数定义在区间[0,1)上,然后结合Garlerkin方法将原问题转化为线性代数方程组.而且还对算法的收敛性和误差进行了分析,最后通过两个数值算例验证了所提算法的可行性及有效性. 相似文献
10.
为减小由于二进制编码的舍入误差对该问题计算结果的影响,对求解回归支持向量机的一种调节熵方法进行了区间扩张,讨论了区间函数的相关定理与收敛性.对设计的区间算法做了收敛性证明,并给出了数值实验,验证了方法与算法的可行性和有效性. 相似文献
11.
This paper considers the semi-resumable model of single machine scheduling with a non-availability period. The machine is
not available for processing during a given time interval. A job cannot be completed before the non-availability period will
have to partially restart after the machine has become available again. For the problem with objective of minimizing makespan,
the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed. For the problem with objective of minimizing total weighted completion time, an
approximation algorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latter problem are also
considered, and improved algorithms are given. 相似文献
12.
Christoph Dürr Maurice Queyranne Frits C.R. Spieksma Fabrice Talla Nobibon Gerhard J. Woeginger 《Discrete Applied Mathematics》2012,160(7-8):1094-1103
For a given set of intervals on the real line, we consider the problem of ordering the intervals with the goal of minimizing an objective function that depends on the exposed interval pieces (that is, the pieces that are not covered by earlier intervals in the ordering). This problem is motivated by an application in molecular biology that concerns the determination of the structure of the backbone of a protein.We present polynomial-time algorithms for several natural special cases of the problem that cover the situation where the interval boundaries are agreeably ordered and the situation where the interval set is laminar. Also the bottleneck variant of the problem is shown to be solvable in polynomial time. Finally we prove that the general problem is NP-hard, and that the existence of a constant-factor-approximation algorithm is unlikely. 相似文献
13.
Global Optimization using Dynamic Search Trajectories 总被引:1,自引:0,他引:1
Two global optimization algorithms are presented. Both algorithms attempt to minimize an unconstrained objective function through the modeling of dynamic search trajectories. The first, namely the Snyman–Fatti algorithm, originated in the 1980's and still appears an effective global optimization algorithm. The second algorithm is currently under development, and is denoted the modified bouncing ball algorithm. For both algorithms, the search trajectories are modified to increase the likelihood of convergence to a low local minimum. Numerical results illustrate the effectiveness of both algorithms. 相似文献
14.
Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce
optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable
solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMSMO. The PMSMO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure
to improve performance. The performance of PMSMO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the
literature and an industrial scheduling problem from the aluminum industry. 相似文献
15.
16.
Katsuhisa Ozaki Takeshi Ogita Siegfried M. Rump Shin’ichi Oishi 《Journal of Computational and Applied Mathematics》2012,236(7):1795-1814
We discuss several methods for real interval matrix multiplication. First, earlier studies of fast algorithms for interval matrix multiplication are introduced: naive interval arithmetic, interval arithmetic by midpoint-radius form by Oishi-Rump and its fast variant by Ogita-Oishi. Next, three new and fast algorithms are developed. The proposed algorithms require one, two or three matrix products, respectively. The point is that our algorithms quickly predict which terms become dominant radii in interval computations. We propose a hybrid method to predict which algorithm is suitable for optimizing performance and width of the result. Numerical examples are presented to show the efficiency of the proposed algorithms. 相似文献
17.
Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance 总被引:1,自引:0,他引:1
This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well. 相似文献
18.
The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence build better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification. 相似文献
19.
Ralph Baker Kearfott 《Journal of Global Optimization》2014,59(2-3):459-476
In branch and bound algorithms in constrained global optimization, a sharp upper bound on the global optimum is important for the overall efficiency of the branch and bound process. Software to find local optimizers, using floating point arithmetic, often computes an approximately feasible point close to an actual global optimizer. Not mathematically rigorous algorithms can simply evaluate the objective at such points to obtain approximate upper bounds. However, such points may actually be slightly infeasible, and the corresponding objective values may be slightly smaller than the global optimum. A consequence is that actual optimizers are occasionally missed, while the algorithm returns an approximate optimum and corresponding approximate optimizer that is occasionally far away from an actual global optimizer. In mathematically rigorous algorithms, objective values are accepted as upper bounds only if the point of evaluation is proven to be feasible. Such computational proofs of feasibility have been weak points in mathematically rigorous algorithms. This paper first reviews previously proposed automatic proofs of feasibility, then proposes an alternative technique. The alternative technique is tried on a test set that caused trouble for previous techniques, and is also employed in a mathematically rigorous branch and bound algorithm on that test set. 相似文献