GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems

The multiple knapsack problem (MKP) forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms (GAs) for proving its efficiency. GAs use self-adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression (GPS) has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to improve the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by replacing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vector and to retain the best genes of the individuals. Each gene’s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene’s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment. TheMKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome portrays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.     

Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) concerns a wide variety of practical problems. It is strongly constrained and NP-hard; thus searching for an efficient heuristic approach for MMKP is of great significance. In this study, we attempt to solve MMKP by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). The algorithm used here follows the algorithmic scheme of max–min ant system for its outstanding performance in solving many other combinatorial optimization problems. The Lagrangian value of the item in MMKP, obtained from LR, is used as the heuristic factor in ACO since it performs best among the six domain-based heuristic factors we define. Furthermore, a novel infeasibility index is proposed for the development of a new repair operator, which converts possibly infeasible solutions into feasible ones. The proposed algorithm was compared with four existing algorithms by applying them to three groups of instances. Computational results demonstrate that the proposed algorithm is capable of producing competitive solutions.     

A New Heuristic for Solving the Multichoice Multidimensional Knapsack Problem

A new heuristic for solving the multichoice multidimensional knapsack problem (MMKP) is presented in this paper. The MMKP is first reduced to a multidimensional knapsack problem (MKP). A linear programming relaxation of the resulting MKP is solved, and a series of new values for the variables is computed. These values, pseudo-utility values, and resource value coefficients computed as well, are used in order to obtain a feasible solution for the original MMKP. Finally, the quality of the feasible solution is improved using the pseudo-utility values and the coefficient values of the objective function. Numerical results show that the performance of this approach is superior to that of previous techniques.     

Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence

The multi-dimensional knapsack problems (MKP) have a landscape called a rugged landscape, which may lead to local optima without any progress to optimal solution. Optimization requirement often involves searching amongst various solutions under multi-objective situations. Maintaining diversity and avoiding premature convergence while keeping the population size small and unique is one of the prime approaches to meet the requirements. In this paper, we propose a practical solution to the duplicity as well as premature convergence problem. We have introduced the concept of virtually compressed binary trie (VCBT) and tried to show that the VCBT can be naturally integrated with the genetic algorithm (GA) so that duplicates are completely eliminated while the trie size is kept reasonably small and practically feasible. Our binary trie coding scheme (BTCS) relies on problem-specific knowledge in fragmenting the search space into feasible and infeasible regions, and thus pruning the infeasible areas. Pruning of the trie occurs frequently and is dependent upon many parameters (other than the infeasibility) and the trie size is kept small throughout the whole process. Comparison tables are given for the performance of the BTCS and other good performing evolutionary algorithms found in literature for the MKP. Here, the optimization ability of the BTCS is compared against the GA given by Chu and Beasley; in particular, on a suite of standard MKP test instances from the OR library. The simulation results show that the proposed strategy significantly improves the computational efficiency of GA and generates robust and near-optimal solutions.     

Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem

The quadratic multiple knapsack problem (QMKP) concerns assigning a set of objects, which interact among themselves through paired profit values, to a set of capacity-constrained knapsacks such that the overall profit of the objects included in the knapsacks is maximized and the total weight of the objects in each knapsack does not exceed the capacity of the knapsack. In this paper we present a highly effective tabu search (TS) approach for QMKP that incorporates a hybridization scheme combining both feasible and infeasible local searches. The feasible local search focuses its search on the most relevant feasible solutions, while the infeasible local search explores a large search space composed of both feasible and infeasible solutions, and employs several tailored move selection rules to keep the infeasible solutions close to the feasible regions located in promising areas. Extensive computational results on a set of 60 benchmark instances in the literature illustrate that the new TS approach compares very favorably with the current state-of-the-art solution methods for QMKP. In particular, the TS approach finds improved best solutions for ten instances. We also analyze the hybridization scheme in the TS approach to ascertain its effect on the performance of the solution method.     

Extension of a hybrid Genetic Algorithm for nonlinear programming problems with equality and inequality constraints

As an extension of the hybrid Genetic Algorithm-HGA proposed by Tang et al. (Comput. Math. Appl. 36 (1998) 11), this paper focuses on the critical techniques in the application of the GA to nonlinear programming (NLP) problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible points/chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are proposed to formulate and evaluate the infeasible chromosomes. The extended version of concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain are introduced. Combining the new evaluation functions and weighted gradient direction search into the Genetic Algorithm, an extended hybrid Genetic Algorithm (EHGA) is developed to solve nonlinear programming (NLP) problems with equality and inequality constraints. Simulation shows that this new algorithm is efficient.Scope and purposeNon-linear Programming (NLP) problems with equality and inequality constraints is an important type of constrained optimization problems. Genetic Algorithm (GA) is one of the well known evolutionary computation techniques. In the application of GA to NLP problems, chromosomes randomly generated at the beginning and/or generated by genetic operators during the evolutionary process usually violate the constraints, resulting in infeasible chromosomes. Therefore, the handling of system constraints, particularly the nonlinear equation constraints, and the measurement and evaluation of infeasible chromosomes, are major concerns in GA. Penalty strategy in the construction of fitness function is commonly used to evaluate the infeasible chromosomes in some traditional AG methods. However, this approach essentially narrows down the search space by eliminating all infeasible chromosomes from the evolutionary process, and it may reduce the chances of finding better candidates for the global optimization. In particular, it absolutely ignores the information carried by the infeasible chromosomes itself. Therefore, formulating the infeasible chromosomes by embedding the relevant information into the evaluation function are important when applying GA to NLP.As an extension of the Hybrid Genetic Algorithm-HGA proposed by Tang et al. (1998), this paper focuses on the critical techniques in the application of GA to NLP problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are designed to formulate and evaluate the infeasible chromosomes. By introducing an extended version of the concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain, an extended hybrid Genetic Algorithm (EHGA) is developed for solving NLP problems with equality and inequality constraints.     

异构云系统中基于智能优化算法的多维资源公平分配

资源分配策略的研究一直是云计算领域研究的热点和难点,针对异构云计算环境下多维资源的公平分配问题,结合基因算法（GA）和差分进化算法（DE）,分别给出了两种兼顾分配公平性和效率的资源分配策略,改进了解矩阵表达式使异构云系统中的主资源公平分配（DRFH）模型转化成为整数线性规划（ILP）模型,并提出了基于最大任务数匹配值（MTM）的初始解产生机制和使不可行解转化为可行解的修正操作,以此提高算法的收敛速度,使其能够快速有效地得到最优分配方案。实验结果表明,基于GA和DE算法的多维资源公平分配策略可以得到近似最优解,在最大化最小主资源份额目标值和资源利用率方面明显优于Best-Fit DRFH和Distributed-DRFH,而且针对不同任务类型的资源需求,具有较强的自适应能力。     

一种基于新约束处理方法的遗传算法

针对目前的约束处理方法中存在的问题,提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索,对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难,使得约束处理问题简单化。实例测试结果表明,该约束处理方法的有效性。     

A genetic algorithm for finding a path subject to two constraints

Multi-constrained routing (MCR) aims to find the feasible path in the network that satisfies multiple independent constraints, it is usually used for routing multimedia traffic with quality-of-service (QoS) guarantees. It is well known that MCR is NP-complete. Heuristic and approximate algorithms for MCR are not effective in dynamic network environment for real-time applications when the state information of the network is out of date. This paper presents a genetic algorithm to solve the MCR problem subject to transmission delay and transmission success ratio. Three key design problems are investigated for this new algorithm, i.e., how to encode the problem in genetic representation, how to avoid the illegal chromosomes in the process of population initialization and genetic operation, and how to design effective genetic operator. We propose the gene structure (GS) to deal with the first problem, and the gene structure algorithm (GSA) to generate the GS. Based on the GS, we provide the heuristic chromosome initialization and mutation operator to solve the last two problems. Computer simulations show that the proposed GA exhibits much faster computation speed so as to satisfy the real-time requirement, and much higher rate of convergence than other algorithms. The results are relatively independent of problem types (network scales and topologies). Furthermore, simulation results show that the proposed GA is effective and efficient in dynamic network environment.     

混合分布估计算法求解随机Job shop 提前/拖期调度问题

针对加工时间具有随机特性的Job shop 调度问题, 提出基于分布估计算法的混合算法. 为增强分布估计算法的种群多样性, 定义了父代工序继承率并设计一种可保留父代个体优良结构特征的重组方法, 该方法在继承父代个体优良结构特征的同时避免了非法解的产生. 在个体选择评价阶段, 采用最优计算量分配策略为每个个体分配模拟量以提高个体评价的精确性. 仿真算例表明了所提出算法的有效性和鲁棒性.

     

基于环境Pareto 支配选择策略的有约束多目标差分进化算法

在处理有约束多目标问题的进化算法中, 目前普遍采用Deb 教授提出的约束占优的直接支配选择策略. 在约束处理中, 优秀不可行解与优秀可行解同样重要, 但在直接支配选择策略中, 不可行解被选择的几率很小. 针对此问题, 设计一种环境Pareto 支配的选择策略, 并基于此提出用于解决有约束多目标问题的差分进化算法. 对经典测试函数进行仿真计算, 结果表明, 与其他算法相比, 所提出的算法具有更高的收敛性和稳定性.

     

An evolutionary algorithm with directed weights for constrained multi-objective optimization

When solving constrained multi-objective optimization problems (CMOPs), keeping infeasible individuals with good objective values and small constraint violations in the population can improve the performance of the algorithms, since they provide the information about the optimal direction towards Pareto front. By taking the constraint violation as an objective, we propose a novel constraint-handling technique based on directed weights to deal with CMOPs. This paper adopts two types of weights, i.e. feasible and infeasible weights distributing on feasible and infeasible regions respectively, to guide the search to the promising region. To utilize the useful information contained in infeasible individuals, this paper uses infeasible weights to maintain a number of well-diversified infeasible individuals. Meanwhile, they are dynamically changed along with the evolution to prefer infeasible individuals with better objective values and smaller constraint violations. Furthermore, 18 test instances and 2 engineering design problems are used to evaluate the effectiveness of the proposed algorithm. Several numerical experiments indicate that the proposed algorithm outperforms four compared algorithms in terms of finding a set of well-distributed non-domination solutions.     

A simulated annealing approach to the traveling tournament problem

Automating the scheduling of sport leagues has received considerable attention in recent years, as these applications involve significant revenues and generate challenging combinatorial optimization problems. This paper considers the traveling tournament problem (TTP) which abstracts the salient features of major league baseball (MLB) in the United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores both feasible and infeasible schedules, uses a large neighborhood with complex moves, and includes advanced techniques such as strategic oscillation and reheats to balance the exploration of the feasible and infeasible regions and to escape local minima at very low temperatures. TTSA matches the best-known solutions on the small instances of the TTP and produces significant improvements over previous approaches on the larger instances. Moreover, TTSA is shown to be robust, because its worst solution quality over 50 runs is always smaller or equal to the best-known solutions. A Preliminary version of this paper was presented at the CP'AI'OR'03 Workshop.     

A genetic algorithm for the proportionate multiprocessor open shop

The multiprocessor open shop (MPOS) scheduling problem is NP-complete, a category of hard combinatorial optimization problems that have not received much attention in the literature. In this work, a special MPOS—a proportionate one—is introduced for the first time. Two original mixed integer programming formulations for the proportionate MPOS are developed and their complexity is discussed. Due to the complexity of the MPOS, this paper develops a compu-search methodology (a genetic algorithm (GA)) to schedule the shop with the objective of minimizing the makespan. In this novel GA, a clever chromosome representation of a schedule is developed that succinctly encodes a schedule of jobs across multiple stages. The innovative design of this chromosome enables any permutation of its genes to yield a feasible solution. This simple representation of an otherwise very complex schedule enables the genetic operators of crossover and mutation to easily manipulate a schedule as the algorithm iteratively searches for better schedules. A testbed of difficult instances of the problem are created to evaluate the performance of the GA. The solution for each instance is compared with a derived lower bound. Computational results reveal that the algorithm performs extremely well, demonstrating its potential to efficiently schedule MPOS problems. More importantly, successful experiments on large-scale problem instances suggest the readiness of the GA for industrial use.     

An efficient genetic algorithm for solving the quay crane scheduling problem

This paper addresses the quay crane scheduling problem (QCSP), which has been shown to be NP-complete. For this reason, a number of studies have proposed the use of genetic algorithm (GA) as the means to obtain the solution in reasonable time. This study extends the research in this area by utilizing the GA that is available in the latest version of Global Optimization Toolbox in MATLAB 7.13 to facilitate development. It aims to improve the efficiency of the GA search by (1) using an initial solution based on the S-LOAD rule developed by Sammarra, Cordeau, Laporte, and Monaco (2007), (2) using a new approach for defining the chromosomes (i.e., solution representation) to reduce the number of decision variables, and (3) using new procedures for calculating tighter lower and upper bounds for the decision variables. The effectiveness of the developed GA is tested using several benchmark instances proposed by Meisel and Bierwirth (2011). Compared to the current best-known solutions, experimental results show that the proposed GA is capable of finding the optimal or near-optimal solution in significantly shorter time for larger problems.     

Structural topology design optimization using Genetic Algorithms with a bit-array representation

In this paper, a bit-array representation method for structural topology optimization using the Genetic Algorithm (GA) is implemented. The importance of structural connectivity in a design is further emphasized by considering the total number of connected objects of each individual explicitly in an equality constraint function. To evaluate the constrained objective function, Deb’s constraint handling approach is further developed to ensure that feasible individuals are always better than infeasible ones in the population to improve the efficiency of the GA. A violation penalty method is proposed to drive the GA search towards the topologies with higher structural performance, less unusable material and fewer separate objects in the design domain. An identical initialization method is also proposed to improve the GA performance in dealing with problems with long narrow design domains. Numerical results of structural topology optimization problems of minimum weight and minimum compliance designs show the success of this bit-array representation method and suggest that the GA performance can be significantly improved by handling the design connectivity properly.     

Infeasibility handling in genetic algorithm using nested domains for production planning

In this paper we present a genetic algorithm with new components to tackle capacitated lot sizing and scheduling problems with sequence dependent setups that appear in a wide range of industries, from soft drink bottling to food manufacturing.Finding a feasible solution to highly constrained problems is often a very difficult task. Various strategies have been applied to deal with infeasible solutions throughout the search. We propose a new scheme of classifying individuals based on nested domains to determine the solutions according to the level of infeasibility, which in our case represents bands of additional production hours (overtime). Within each band, individuals are just differentiated by their fitness function. As iterations are conducted, the widths of the bands are dynamically adjusted to improve the convergence of the individuals into the feasible domain.The numerical experiments on highly capacitated instances show the effectiveness of this computational tractable approach to guide the search toward the feasible domain. Our approach outperforms other state-of-the-art approaches and commercial solvers.     

Solving fuzzy Multidimensional Multiple-Choice Knapsack Problems: The multi-start Partial Bound Enumeration method versus the efficient epsilon-constraint method

In this paper a new fuzzy Multidimensional Multiple-choice Knapsack Problem (MMKP) is proposed. In the proposed fuzzy MMKP, each item may belong to several groups according to a predefined fuzzy membership value. The total profit and the total cost of the knapsack problem are considered as two conflicting objectives. A mathematical approach and a heuristic algorithm are proposed to solve the fuzzy MMKP. One method is an improved version of a well-known exact multi-objective mathematical programming technique, called the efficient ?-constraint method. The second method is a heuristic algorithm called multi-start Partial-Bound Enumeration (PBE). Both methods are used to comparatively generate a set of non-dominated solutions for the fuzzy MMKP. The performance of the two methods is statistically compared with respect to a set of simulated benchmark cases using different diversity and accuracy metrics.     

Immigrant Population Search Algorithm for Solving Constrained Optimization Problems

This article introduces the Immigrant Population Search Algorithm (IPSA) inspired by the pattern of human population migration to find better habitats. The algorithm is viewed as a new optimization method for solving constrained optimization problems, and it belongs to the set of population-based algorithms that are proposed for combinatorial optimization. In this algorithm, the life environment is the solution space of the problem. Every point of this space is a solution for the problem, which may be feasible or infeasible, and the quality of life at that point is the value of fitness function for that solution. Each population group tries to investigate feasible and better habitats. In other words, it tries to optimize the problem. After the algorithm steps are described, the efficiency of the algorithm is compared to that of three other metaheuristic algorithms that are used to optimize some mathematic problems. The results show that the proposed algorithm performs better than the other three methods.     

遗传算法用于曲线的误差约束多边形近似

提出了一种求解曲线的误差约束多边形近似问题的遗传算法.其主要思想是:1)采用变长染色体编码机制,以减少存储空间和计算时间的消耗;2)针对问题的特点,提出了一种新的杂交算子——基因消去杂交,以尽可能地消去染色体上的冗余基因,从而提高算法的寻优能力;3)采用染色体修复策略处理遗传操作产生的不可行解,该策略通过迭代地向染色体追加有价值的候选基因来实现染色体的修复,并提出一种对染色体的候选基因进行评估的机制.通过实验评估并与其他遗传算法进行比较,结果表明,提出的算法性能更优越.