Search

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

In this paper, we propose a vehicle routing problem with time windows (TWVRP). In this problem, we consider a hard time constraint that the fleet can only serve customers within a specific time window. To solve this problem, a hybrid ant colony (HACO) algorithm is proposed based on ant colony algorithm and mutation operation. The HACO algorithm proposed has three innovations: the first is to update pheromones with a new method; the second is the introduction of adaptive parameters; and the third is to add the mutation operation. A famous Solomon instance is used to evaluate the performance of the proposed algorithm. Experimental results show that HACO algorithm is effective against solving the problem of vehicle routing with time windows. Besides, the proposed algorithm also has practical implications for vehicle routing problem and the results show that it is applicable and effective in practical problems. [ABSTRACT FROM AUTHOR]

The quadratically constrained quadratic programming problem often appears in various fields such as engineering practice, management science and network communication. This paper mainly considers a non-convex quadratic programming problem with convex quadratic constraints. Firstly, the objective function of the problem is reconstructed into a form composed of only one convex function and several linear functions by using the eigenvalue decomposition technique of matrix. Then the reconstructed problem is converted to the equivalent problem with simple concave quadratic objective function in the outcome space by introducing appropriate auxiliary variables, and its feasible domain is convex. Based on the branch-and-bound framework which can guarantee the global optimality of the solution, a global optimization algorithm for solving the equivalent problem is proposed, which integrates the effective relaxation process and the branching process related to the outer approximation technique. Finally, the effectiveness and feasibility of the algorithm are illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

The Capacitated Vehicle Routing Problem (CVRP) is a classical combinatorial optimization problem, which objective is to minimize the vehicle travel distance. In this paper a hybrid ant colony optimization based on Fireworks Algorithm (FWA) is proposed to solve the CVRP. The main work of hybrid algorithm is reflected in three aspects: firstly, FWA is introduced on the basis of Ant Colony Optimization (ACO) algorithm to increase the diversity of algorithms and avoid falling into local optimum too early in the search process; secondly, the elite ant strategy is added to increase the attractiveness of the local optimal path to the ants; thirdly, the Max-Min Ant System (MMAS) is added to limit the pheromone value within a range to prevent the pheromone from increasing too fast on the path. In this paper, the proposed hybrid algorithm is tested in 71 instances and compared with other intelligent algorithms. Experimental results show that the proposed hybrid algorithm finds new best solutions and is competitive with other algorithms. [ABSTRACT FROM AUTHOR]

To apply biogeography-based optimization (BBO) to large scale optimization problems, this paper proposes a novel BBO variant based on feedback differential evolution mechanism and steepest descent method, referred to as FBBOSD. Firstly, the immigration refusal mechanism is proposed to eliminate the damage of inferior solutions to superior solutions. Secondly, the dynamic hybrid migration operator is designed to balance the exploration and exploitation, which makes BBO suitable for high-dimensional environment. Thirdly, the feedback differential evolution mechanism is designed to make FBBOSD can select mutation modes intelligently. Finally, the steepest descent method is creatively combined with BBO, which further improves the convergence accuracy. Meanwhile, a sequence convergence model is established to prove the convergence of FBBOSD. Quantitative evaluations: FBBOSD is compared with BBO, seven BBO variants and seven state-of-the-art evolutionary algorithms, respectively. The experimental results on 24 benchmark functions and CEC2017 show that FBBOSD outperforms all compared algorithms, and the dimension of solving optimization problems can reach 10,000. Then, FBBPOSD is applied to engineering design problems. The simulation results demonstrate that it is also effective on constrained optimization problems. In short, FBBOSD has excellent performance and outstanding stability, which is a new algorithm worthy of adoption and promotion. [ABSTRACT FROM AUTHOR]

To make biogeography-based optimization (BBO) suitable for large-scale optimization problems, this paper proposes a novel BBO variant based on marine predators algorithm (MPA) and steepest descent (SD) method, named BBOMPSD. Firstly, the example learning strategy is used to eliminate the damage of inferior solutions to superior solutions. Secondly, the hybrid migration operator is designed to make the population move rapidly to the global optimal solution, which improves the convergence speed and accuracy. Then, the Lévy and Brownian movements in MPA is combined with BBO to make the algorithm effectively balance the exploitation and exploration. BBOMPSD realizes free switching between local search and global search through the two movements. Finally, the SD method is merged with BBO, which further improves the convergence accuracy. Meanwhile, the sequence convergence model is established to prove the convergence of BBOMPSD. Comparing BBOMPSD with standard BBO, seven advanced BBO variants and seven state-of-the-art evolutionary algorithms on 24 benchmark functions and CEC2017 test set, the experimental results show that BBOMPSD outperforms all compared algorithms, and the dimension of solving global optimization problems can reach 5000. Applying it to engineering design problems, the results demonstrate that the proposed algorithm is also effective on real-world constrained optimization problems. [ABSTRACT FROM AUTHOR]

Opposition-based differential evolution (ODE) is a well-known DE variant that employs opposition-based learning (OBL) to accelerate the convergence speed. However, the existing OBL variants are population-based, which causes many shortcomings. The value of the jumping rate is not self-adaptively adjusted, so the algorithm easily traps into local optima. The population-based OBL wastes fitness evaluations when the algorithm converges to sub-optimal. In this paper, we proposed a novel OBL called subpopulation-based OBL (SPOBL) with a self-adaptive parameter control strategy. In SPOBL, the jumping rate acts on the individual, and the subpopulation is selected according to the individual's jumping rate. In the self-adaptive parameter control strategy, the surviving individual's jumping rate in each iteration will participate in the self-adaptive process. A generalized Lehmer mean is introduced to achieve an equilibrium between exploration and exploitation. We used DE and advanced DE variants combined with SPOBL to verify performance. The results of performance are evaluated on the CEC 2017 and CEC 2020 test suites. The SPOBL shows better performance compared to other OBL variants in terms of benchmark functions as well as real-world constrained optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of maximizing the sum of a concave–convex quadratic fractional function on a non-empty, bounded, convex quadratic feasible set, which is called the problem (QCQFP). By using a conventional semidefinite program (SDP) relaxation, QCQFP is reformulated as a class of linear fractional programming problems over the cone of positive semidefinite matrices, which we refer to these problems as SDFP. After expatiating the properties of SDFP, we transform SDFP into its equivalent problem (ESDFP) whose non-convexity is mainly reflected in the newly added nonlinear equality constraints. By relaxing these nonlinear equality constraints into linear constraints, a special SDP relaxation is generated for ESDFP. Based on these results, an effective branch-and-bound algorithm is designed, and its theoretical convergence and worst-case complexity are proved. Numerical experiments demonstrate that the proposed algorithm is effective and feasible. [ABSTRACT FROM AUTHOR]

Auxiliary function methods have been considered to be practical approaches for finding the global minimizer of multi-model functions.Filled function methods, as a typical representative of auxiliary function methods, obtain a global minimizer by minimizing the objective function and the filled function cyclically. In order to improve the efficiency of the filled function, this paper presents a new filled function which has the same local minimizers of the objective function, and these minimizers are all better than the current minimizer of the objective function. Therefore, it does not need to minimize the objective function except for the first iteration in the filled function method. Additionally, the proposed filled function excludes some disadvantages of conventional filled functions and a classical local optimization method can be applied directly to the new filled function to obtain a better minimizer of the original problem. Finally, numerical experiments are made and the results show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new filled function method for finding a global minimizer of global optimization with inequality constraints. The proposed filled function is a continuously differentiable function with only one parameter. Then, we can use classical local optimization methods to find a better minimizer of the proposed filled function with a few parameter adjustment. The numerical experiments are made and the results show that the proposed filled function method is effective. [ABSTRACT FROM AUTHOR]

Background: Recently, sparse unmixing has been successfully applied to spectral mixture analysis of remotely sensed hyperspectral images. Based on the assumption that the observed image signatures can be expressed in the form of linear combinations of a number of pure spectral signatures known in advance, unmixing of each mixed pixel in the scene is to find an optimal subset of signatures in a very large spectral library, which is cast into the framework of sparse regression. However, traditional sparse regression models, such as collaborative sparse regression, ignore the intrinsic geometric structure in the hyperspectral data. Results: In this paper, we propose a novel model, called manifold regularized collaborative sparse regression, by introducing a manifold regularization to the collaborative sparse regression model. The manifold regularization utilizes a graph Laplacian to incorporate the locally geometrical structure of the hyperspectral data. An algorithm based on alternating direction method of multipliers has been developed for the manifold regularized collaborative sparse regression model. Conclusions: Experimental results on both the simulated and real hyperspectral data sets have demonstrated the effectiveness of our proposed model. [ABSTRACT FROM AUTHOR]

In this paper, a new filled function method for finding a global minimizer of global optimization is proposed. The proposed filled function is continuously differentiable and only contains one parameter. It has no parameter sensitive terms. As a result, a general classical local optimization method can be used to find a better minimizer of the proposed filled function with easy parameter adjustment. Numerical experiments show that the proposed filled function method is effective. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]