一种求解约束优化问题的改进差分进化算法

针对在处理约束优化问题时约束条件难以处理的问题,提出了一种求解约束优化问题的改进差分进化算法.即在每代进化前将群体分为可行个体和不可行个体两类,对不可行个体,用差量法将其逐个转化为可行个体,并保持种群规模不变,经过一序列的进化后,计算所有可行个体的适应度并找到问题的最优解.对5个经典函数进行了优化测试,测试结果表明提出的算法对求解约束优化问题是有效的.     

基于种群分类排序的约束优化遗传算法

针对约束优化问题,提出了一类将种群中的个体分类排序的思想.算法的特点在于:先将种群中的解分为可行解和不可行解两类,然后分别按照不同的标准排序.由于很多约束优化问题的最优解位于可行域的边界上或附近,所以排序时并不认为可行解一定优于不可行解.基于此分类排队思想,特别设计了只允许同等级个体进行交叉的新的交叉算子,称之为同等级交叉算子,以及基于一维搜索的变异算子.算法同时采用了保证固定比例不可行解的自适应策略.4个标准测试函数的数值仿真结果验证了算法的有效性.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

下层为凸标量优化的二层多目标规划问题的光滑化方法

以下层问题的最优性条件代替下层问题,将下层为凸标量优化的一类二层多目标规划问题转化为带互补约束的不可微多目标规划问题,采用扰动的Fischer-Burmeister函数对互补约束光滑化,得到了相应的光滑化多目标规划问题,分析了原问题的有效解与光滑化多目标规划问题有效解的关系,设计了求解该类二层多目标规划问题的光滑化算法,并分析了算法的收敛性.数值结果表明该光滑化方法是可行的.     

广义几何规划的全局优化算法

对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性.     

一类单调非凸约束最优规划修正的新型分枝定界算法

本文讨论了一类单调非凸约束最优规划的目标函数和约束集的结构特征性质.阐明了如何将所考虑的问题等价地转化为一个递增函数在另一个递增函数水平集上的极大优化问题.在此基础上提出了一个我们称之为修正的新型分枝定界算法.新算法的修正之处是在计算新的极点时,采用了一个有效的新的区域删除模式以构造越来越小的Polyblock集覆盖EnH且不舍y,以排除问题(P)可行域中不存在全局r最优解的部分.最后,证明了算法的收敛性.初步的数值实验表明算法是有效可行的,可应用于求解更广的一类非凸最优规划.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

求解稀疏分裂可行问题的一种投影算法

本文研究了稀疏分裂可行问题.通过将分裂可行问题转化为一个目标函数为凸函数的稀疏约束优化问题,设计一种梯度投影算法来求解此问题,获得了算法产生的点列可以收敛到稀疏分裂可行问题的一个解.用数值例子说明了算法的有效性.     

动态种群规模协同进化算法求解多目标投资组合优化问题

为了解决仅含预算约束的投资组合优化模型,提出一种基于种群密度的多目标协同进化算法.算法采用种群竞争的策略自适应的产生不定规模的种群,避免了固定种群规模的缺点.在进化过程中每个种群都会参考自身的最优个体以及竞争种群对自身的影响,超级个体集合存储进化过程中产生的最优解,通过最优个体的引导使算法快速收敛至Pareto前沿.实验结果表明,与NSGA-2算法相比,提出的算法在稳定性和收敛性都有很好的表现,是一种有效的多目标进化算法.     

求解0-1规划问题的改进差分进化算法

针对0-1规划问题,提出了一种新的智能优化方法——差分进化算法.首先利用佳点集法产生初始种群,大大提高了种群的多样性,再用牵引法处理约束条件,将进化中的不可行解逐步引入到可行解集,克服了罚函数法选择罚因子的困难,最后对10个0-1规划问题的算例进行测试,并将测试结果与其它算法进行了比较,结果表明:文章提出的算法具有较快的寻优能力和较好的全局搜索能力,是求解0-1规划问题的一种有效方法.     

Progressive genetic algorithm for solution of optimization problems with nonlinear equality and inequality constraints

A new approach, identified as progressive genetic algorithm (PGA), is proposed for the solutions of optimization problems with nonlinear equality and inequality constraints. Based on genetic algorithms (GAs) and iteration method, PGA divides the optimization process into two steps; iteration and search steps. In the iteration step, the constraints of the original problem are linearized using truncated Taylor series expansion, yielding an approximate problem with linearized constraints. In the search step, GA is applied to the problem with linearized constraints for the local optimal solution. The final solution is obtained from a progressive iterative process. Application of the proposed method to two simple examples is given to demonstrate the algorithm.     

The balanced linear programming problem

The Balanced Linear Programming Problem (BLPP) arises in situations which require equitable distribution of a scarce resource. The BLPP can be transformed to the standard form of the linear programming problem by introducing 2∥N∥ + 2 additional variables and 2∥N∥ additional constraints. This transformation is not desirable from the computational point of view for larger values of ∥N∥ as it increases the problem size substantially. It is also undesirable from a theoretical perspective as it might affect the special structure of the constraint matrix. In this paper, we develop an algorithm for the BLPP which does not require problem enlargement. The algorithm is based on the relationship between the BLPP and the minimax linear programming problem, and solving the latter problem parametrically. Our algorithm, in essence, performs steps that are similar to those performed in the parametric simplex method with parametric right hand side. We then adapt our algorithm for the network flow problem and this specialized algorithm can be applied on the network directly without maintaining the simplex tableau.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

Multiobjective big data optimization based on a hybrid salp swarm algorithm and differential evolution

This paper developed a multiobjective Big Data optimization approach based on a hybrid salp swarm algorithm and the differential evolution algorithm. The role of the differential evolution algorithm is to enhance the capability of the feature exploitation of the salp swarm algorithm because the operators of the differential evolution algorithm are used as local search operators. In general, the proposed method contains three stages. In the first stage, the population is generated, and the archive is initialized. The second stage updates the solutions using the hybrid salp swarm algorithm and the differential evolution algorithm, and the final stage determines the nondominated solutions and updates the archive. To assess the performance of the proposed approach, a series of experiments were performed. A set of single-objective and multiobjective problems from the 2015 Big Data optimization competition were tested; the dataset contained data with and without noise. The results of our experiments illustrated that the proposed approach outperformed other approaches, including the baseline nondominated sorting genetic algorithm, on all test problems. Moreover, for single-objective problems, the score value of the proposed method was better than that of the traditional multiobjective salp swarm algorithm. When compared with both algorithms, that is, the adaptive DE algorithm with external archive and the hybrid multiobjective firefly algorithm, its score was the largest. In contrast, for the multiobjective functions, the scores of the proposed algorithm were higher than that of the fireworks algorithm framework.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

Ant colony approach to constrained redundancy optimization in binary systems

This paper presents an ant colony optimization algorithm to address the constrained redundancy allocation problem in order to maximize system reliability for complex binary systems. The constraints involved, though separable, are both linear and non-linear. We couple an adaptive penalty function with the basic ant colony approach to handle highly constrained problems and embed a local search technique to find still better locally optimal solutions. The proposed algorithm has been tested on a large number of problems, containing even up to 500 subsystems, with both fixed and randomly generated parameters. Experimental results demonstrate the advantage of the proposed algorithm to solve similar types of problems.     

Discrete Capacity Assignment in IP networks using Particle Swarm Optimization

This paper presents a design methodology for IP networks under end-to-end Quality-of-Service (QoS) constraints. Particularly, we consider a more realistic problem formulation in which the link capacities of a general-topology packet network are discrete variables. This Discrete Capacity Assignment (DCA) problem can be classified as a constrained combinatorial optimization problem. A refined TCP/IP traffic modeling technique is also considered in order to estimate performance metrics for networks loaded by realistic traffic patterns. We propose a discrete variable Particle Swarm Optimization (PSO) procedure to find solutions for the problem. A simple approach called Bottleneck Link Heuristic (BLH) is also proposed to obtain admissible solutions in a fast way. The PSO performance, compared to that one of an exhaustive search (ES) procedure, suggests that the PSO algorithm provides a quite efficient approach to obtain (near) optimal solutions with small computational effort.     

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

An ant colony optimization approach for the multidimensional knapsack problem

Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore, a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches to the problem.     

A hybrid metaheuristic approach to the university course timetabling problem

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.