一个求解非线性不等式约束优化问题的带有共轭梯度参数的广义梯度投影算法

本文提出一个求解非线性不等式约束优化问题的带有共轭梯度参数的广义梯度投影算法.算法中的共轭梯度参数是很容易得到的,且算法的初始点可以任意选取.而且,由于算法仅使用前一步搜索方向的信息,因而减少了计算量.在较弱条件下得到了算法的全局收敛性.数值结果表明算法是有效的.     

谱Hestenes-Stiefel共轭梯度算法及其收敛性

谱共轭梯度算法是求解大规模无约束最优化问题的有效算法之一.基于Hestenes-Stiefel算法与谱共轭梯度算法,提出一种谱Hestenes-Stiefel共轭梯度算法.在Wolfe线搜索下,算法产生的搜索方向具有下降性质,且全局收敛性也能得到证明.通过对CUTEr函数库中部分著名的函数进行试验,利用著名的DolanMore评价体系,展示了新算法的有效性.     

Wolfe搜索下的一种共轭梯度法

研究无约束优化问题的共轭梯度算法,提出了一种计算主要参数的新形式,分析了Wolfe搜索下该算法的全局收敛性.     

一个带重启步的改进PRP型谱共轭梯度法

Polak-Ribière-Polak (PRP)方法是经典共轭梯度法中数值表现较好的方法之一.结合Wolfe非精确线搜索准则对PRP公式进行改进,从而产生新的共轭参数,并基于新共轭参数设计新的谱参数,引入重启条件并构造新的重启方向,进而建立一个带重启步的谱共轭梯度算法.在常规假设及强Wolfe非精确线搜索步长准则下,...     

一种求解非线性无约束优化问题的充分下降的共轭梯度法

共轭梯度法是一类具有广泛应用的求解大规模无约束优化问题的方法. 提出了一种新的非线性共轭梯度(CG)法,理论分析显示新算法在多种线搜索条件下具有充分下降性. 进一步证明了新CG算法的全局收敛性定理. 最后,进行了大量数值实验,其结果表明与传统的几类CG方法相比,新算法具有更为高效的计算性能.     

带参数共轭梯度法簇的全局收敛性

共轭梯度法是最优化中最常用的方法之一,广泛地应用于求解大规模优化问题,其中参数β_k的不同选取可以构成不同的共轭梯度法.给出了一类含有三个参数的共轭梯度算法,这种算法能够在给定的条件下证明选定的β_k在每一步都能产生一个下降方向,同时在强Wolfe线搜索下,这种算法具有全局收敛性.     

种求解非线性无约束优化问题的充分下降的共轭梯度法

共轭梯度法是一类具有广泛应用的求解大规模无约束优化问题的方法.提出了一种新的非线性共轭梯度(CG)法,理论分析显示新算法在多种线搜索条件下具有充分下降性.进一步证明了新CG算法的全局收敛性定理.最后,进行了大量数值实验,其结果表明与传统的几类CG方法相比,新算法具有更为高效的计算性能.     

有界约束非线性优化问题的仿射共轭梯度路径法

本文提出仿射内点离散共轭梯度路径法解有界约束的非线性优化问题,通过构造预条件离散的共轭梯度路径解二次模型获得预选迭代方向,结合内点回代线搜索获得下一步的迭代,在合理的假设条件下,证明了算法的整体收敛性与局部超线性收敛速率,最后,数值结果表明了算法的有效性.     

Wolfe线搜索下新的共轭梯度法的全局收敛性

共轭梯度法是求解无约束优化问题的一种重要的方法.本文提出一族新的共轭梯度法,证明了其在推广的Wolfe非精确线搜索条件下具有全局收敛性.最后对算法进行了数值实验,实验结果验证了该算法的有效性.     

Wolfe步长规则下约束优化问题的共轭梯度投影算法

本文研究了约束优化问题min x∈Ωf(x).利用共轭梯度算法与GLP梯度投影思想相结合的方法,构造了一个新的共轭梯度投影算法,并在Wolfe线搜索下获得了该算法的全局收敛性结果.     

Random backtracking in backtrack search algorithms for satisfiability

This paper proposes the utilization of randomized backtracking within complete backtrack search algorithms for propositional satisfiability (SAT). In recent years, randomization has become pervasive in SAT algorithms. Incomplete algorithms for SAT, for example the ones based on local search, often resort to randomization. Complete algorithms also resort to randomization. These include state-of-the-art backtrack search SAT algorithms that often randomize variable selection heuristics. Moreover, it is plain that the introduction of randomization in other components of backtrack search SAT algorithms can potentially yield new competitive search strategies. As a result, we propose a stochastic backtrack search algorithm for SAT, that randomizes both the variable selection and the backtrack steps of the algorithm. In addition, we relate randomized backtracking with a more general form of backtracking, referred to as unrestricted backtracking. Finally, experimental results for different organizations of randomized backtracking are described and compared, providing empirical evidence that the new search algorithm for SAT is a very competitive approach for solving hard real-world instances.     

Multiobjective shortest path problems with lexicographic goal-based preferences

Multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new exact label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive.     

Particle swarm optimization with age-group topology for multimodal functions and data clustering

This paper proposes particle swarm optimization with age-group topology (PSOAG), a novel age-based particle swarm optimization (PSO). In this work, we present a new concept of age to measure the search ability of each particle in local area. To keep population diversity during searching, we separate particles to different age-groups by their age and particles in each age-group can only select the ones in younger groups or their own groups as their neighbourhoods. To allow search escape from local optima, the aging particles are regularly replaced by new and randomly generated ones. In addition, we design an age-group based parameter setting method, where particles in different age-groups have different parameters, to accelerate convergence. This algorithm is applied to nonlinear function optimization and data clustering problems for performance evaluation. In comparison against several PSO variants and other EAs, we find that the proposed algorithm provides significantly better performances on both the function optimization problems and the data clustering tasks.     

求解大规模极大极小问题的光滑化三项共轭梯度算法

基于指数罚函数,对最近提出的一种求解无约束优化问题的三项共轭梯度法进行了修正,并用它求解更复杂的大规模极大极小值问题.证明了该方法生成的搜索方向对每一个光滑子问题是充分下降方向,而且与所用的线搜索规则无关.以此为基础,设计了求解大规模极大极小值问题的算法,并在合理的假设下,证明了算法的全局收敛性.数值实验表明,该算法优于文献中已有的类似算法.     

Flow Search Approach and New Bounds for the m-Step Linear Conjugate Gradient Algorithm

A flow search approach is presented in this paper. In the approach, each iterative process involves a subproblem, whose variables are the stepsize parameters. Every feasible solution of the subproblem corresponds to some serial search stages, the stepsize parameters in different search stages may interact mutually, and their optimal values are determined by evaluating the total effect of the interaction. The main idea of the flow search approach is illustrated via the minimization of a convex quadratic function. Based on the flow search approach, some properties of the m-step linear conjugate gradient algorithm are analyzed and new bounds on its convergence rate are also presented. Theoretical and numerical results indicate that the new bounds are better than the well-known ones.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

Tabu Search When Noise is Present: An Illustration in the Context of Cause and Effect Analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.     

Using local search to find MSSes and MUSes

In this paper, a new complete technique to compute Maximal Satisfiable Subsets (MSSes) and Minimally Unsatisfiable Subformulas (MUSes) of sets of Boolean clauses is introduced. The approach improves the currently most efficient complete technique in several ways. It makes use of the powerful concept of critical clause and of a computationally inexpensive local search oracle to boost an exhaustive algorithm proposed by Liffiton and Sakallah. These features can allow exponential efficiency gains to be obtained. Accordingly, experimental studies show that this new approach outperforms the best current existing exhaustive ones.     

融合改进Tent混沌和模拟退火的灰狼算法

针对标准灰狼算法种群多样性差、后期收敛速度慢、易陷入局部最优的缺陷,提出一种改进灰狼算法.利用改进Tent混沌映射初始化种群,增加种群多样性;引入螺旋函数,提高算法收敛速度;融合模拟退火思想,避免陷入局部最优;设置搜索阈值,平衡全局搜索与局部搜索;利用改进Tent混沌映射产生新个体,替换性能较差个体并进行高斯扰动,增加寻优精度;将当前解和新解进行算术杂交,以保留当前解优点并减小扰动差异.使用基准测试函数和共享单车停车点选址及期初配置模型测试算法性能.结果表明,改进灰狼算法较标准灰狼算法、遗传算法和粒子群算法,收敛速度更快,寻优精度更高,性能更优越,并将该算法应用到共享单车停车选址上,验证了算法的有效性.     

A memetic algorithm for the team orienteering problem

The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 5 instances.