Coloured quiver mutation for higher cluster categories

We define mutation on coloured quivers associated to tilting objects in higher cluster categories. We show that this operation is compatible with the mutation operation on the tilting objects. This gives a combinatorial approach to tilting in higher cluster categories and especially an algorithm to determine the Gabriel quivers of tilting objects in such categories.     

An evolutionary algorithm with the partial sequential forward floating search mutation for large-scale feature selection problems

Several meta-heuristic algorithms, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been developed for solving feature selection problems due to their efficiency for searching feature subset spaces in feature selection problems. Recently, hybrid GAs have been proposed to improve the performance of conventional GAs by embedding a local search operation, or sequential forward floating search mutation, into the GA. Existing hybrid algorithms may damage individuals’ genetic information obtained from genetic operations during the local improvement procedure because of a sequential process of the mutation operation and the local improvement operation. Another issue with a local search operation used in the existing hybrid algorithms is its inappropriateness for large-scale problems. Therefore, we propose a novel approach for solving large-sized feature selection problems, namely, an EA with a partial sequential forward floating search mutation (EAwPS). The proposed approach integrates a local search technique, that is, the partial sequential forward floating search mutation into an EA method. Two algorithms, EAwPS-binary representation (EAwPS-BR) for medium-sized problems and EAwPS-integer representation (EAwPS-IR) for large-sized problems, have been developed. The adaptation of a local improvement method into the EA speeds up the search and directs the search into promising solution areas. We compare the performance of the proposed algorithms with other popular meta-heuristic algorithms using the medium- and large-sized data sets. Experimental results demonstrate that the proposed EAwPS extracts better features within reasonable computational times.     

A novel differential evolution algorithm for binary optimization

Differential evolution (DE) is one of the most powerful stochastic search methods which was introduced originally for continuous optimization. In this sense, it is of low efficiency in dealing with discrete problems. In this paper we try to cover this deficiency through introducing a new version of DE algorithm, particularly designed for binary optimization. It is well-known that in its original form, DE maintains a differential mutation, a crossover and a selection operator for optimizing non-linear continuous functions. Therefore, developing the new binary version of DE algorithm, calls for introducing operators having the major characteristics of the original ones and being respondent to the structure of binary optimization problems. Using a measure of dissimilarity between binary vectors, we propose a differential mutation operator that works in continuous space while its consequence is used in the construction of the complete solution in binary space. This approach essentially enables us to utilize the structural knowledge of the problem through heuristic procedures, during the construction of the new solution. To verify effectiveness of our approach, we choose the uncapacitated facility location problem (UFLP)—one of the most frequently encountered binary optimization problems—and solve benchmark suites collected from OR-Library. Extensive computational experiments are carried out to find out the behavior of our algorithm under various setting of the control parameters and also to measure how well it competes with other state of the art binary optimization algorithms. Beside UFLP, we also investigate the suitably of our approach for optimizing numerical functions. We select a number of well-known functions on which we compare the performance of our approach with different binary optimization algorithms. Results testify that our approach is very efficient and can be regarded as a promising method for solving wide class of binary optimization problems.     

A Trigonometric Mutation Operation to Differential Evolution

Previous studies have shown that differential evolution is an efficient, effective and robust evolutionary optimization method. However, the convergence rate of differential evolution in optimizing a computationally expensive objective function still does not meet all our requirements, and attempting to speed up DE is considered necessary. In this paper, a new local search operation, trigonometric mutation, is proposed and embedded into the differential evolution algorithm. This modification enables the algorithm to get a better trade-off between the convergence rate and the robustness. Thus it can be possible to increase the convergence velocity of the differential evolution algorithm and thereby obtain an acceptable solution with a lower number of objective function evaluations. Such an improvement can be advantageous in many real-world problems where the evaluation of a candidate solution is a computationally expensive operation and consequently finding the global optimum or a good sub-optimal solution with the original differential evolution algorithm is too time-consuming, or even impossible within the time available. In this article, the mechanism of the trigonometric mutation operation is presented and analyzed. The modified differential evolution algorithm is demonstrated in cases of two well-known test functions, and is further examined with two practical training problems of neural networks. The obtained numerical simulation results are providing empirical evidences on the efficiency and effectiveness of the proposed modified differential evolution algorithm.     

A stable approach to Newton's method for general mathematical programming problems inR n

The usual approach to Newton's method for mathematical programming problems with equality constraints leads to the solution of linear systems ofn +m equations inn +m unknowns, wheren is the dimension of the space andm is the number of constraints. Moreover, these linear systems are never positive definite. It is our feeling that this approach is somewhat artificial, since in the unconstrained case the linear systems are very often positive definite. With this in mind, we present an alternate Newton-like approach for the constrained problem in which all the linear systems are of order less than or equal ton. Furthermore, when the Hessian of the Lagrangian at the solution is positive definite (a situation frequently occurring), all our systems will be positive definite. Hence, in all cases, our Newton-like method offers greater numerical stability. We demonstrate that the convergence properties of this Newton-like method are superior to those of the standard approach to Newton's method. The operation count for the new method using Gaussian elimination is of the same order as the operation count for the standard method. However, if the Hessian of the Lagrangian at the solution is positive definite and we use Cholesky decomposition, then the order of the operation count for the new method is half that for the standard approach to Newton's method. This theory is generalized to problems with both equality and inequality constraints.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

改进遗传算法求解TSP问题

提出了一种改进遗传算法求解 TSP.该方法在迭代初期引入不适应度函数作为评价标准 ,结合启发式交叉和边重组交叉算子设计了一种新的交叉算子 ,并对变异后个体进行免疫操作 .此外对操作后群体进行整理 ,删除群体中相同个体 ,得到规模为 N1的中间群体 ,对较优的 N -N 1个个体进行启发式变异 ,并将变异后个体补充进中间群体 ,生成规模为 N的新群体 ,这样保证群体中没有相同个体 ,从而保证群体多样性 .数值结果表明这种改进遗传算法是有效的 .     

Simultaneously Applying Multiple Mutation Operators in Genetic Algorithms

The mutation operation is critical to the success of genetic algorithms since it diversifies the search directions and avoids convergence to local optima. The earliest genetic algorithms use only one mutation operator in producing the next generation. Each problem, even each stage of the genetic process in a single problem, may require appropriately different mutation operators for best results. Determining which mutation operators should be used is quite difficult and is usually learned through experience or by trial-and-error. This paper proposes a new genetic algorithm, the dynamic mutation genetic algorithm, to resolve these difficulties. The dynamic mutation genetic algorithm simultaneously uses several mutation operators in producing the next generation. The mutation ratio of each operator changes according to evaluation results from the respective offspring it produces. Thus, the appropriate mutation operators can be expected to have increasingly greater effects on the genetic process. Experiments are reported that show the proposed algorithm performs better than most genetic algorithms with single mutation operators.     

Project Scheduling with Multiple Modes: A Genetic Algorithm

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.     

A Lagrangean relaxation based approach for the capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and capacity allocation problem in flexible manufacturing systems. A set of operations is selected to be processed and assigned to the machines together with their required tools. The purchase or usage of the required tools incurs a cost. The machines have scarce time and tool magazine capacities. The objective is to maximize the total weight of the assigned operations minus the total tooling costs. We use Lagrangean relaxation approach to obtain upper and lower bounds on the optimal objective function values. The computational experiments show that our approach provides near optimal bounds in reasonable solution times.     

Digital idle speed control of automotive engines: A safety problem for hybrid systems

We address the idle speed control problem in automotive electronics using hybrid methods to derive a digital control law with guaranteed properties. Associating a switching system with the hybrid system that describes the engine operation is crucial to developing a computationally feasible approach. For switching systems with minimum and maximum dwell times and controlled resets, we are able to derive digital control strategies with guaranteed properties that ensure safety. The proposed methodology, while motivated by the idle control problem, is of general interest for hybrid systems for which minimum and maximum dwell times can be established. In our modeling approach, we do not assume synchronization between sampling time and switching time. This is an important technical aspect in general, and in particular for our application, where there is no reason why sampling and switching should be synchronized. Some simulation results are included to demonstrate the effectiveness of the approach.     

An alternative framework to Lagrangian relaxation approach for job shop scheduling

A new Lagrangian relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.     

Differential evolution algorithms using hybrid mutation

Differential evolution (DE) has gained a lot of attention from the global optimization research community. It has proved to be a very robust algorithm for solving non-differentiable and non-convex global optimization problems. In this paper, we propose some modifications to the original algorithm. Specifically, we use the attraction-repulsion concept of electromagnetism-like (EM) algorithm to boost the mutation operation of the original differential evolution. We carried out a numerical study using a set of 50 test problems, many of which are inspired by practical applications. Results presented show the potential of this new approach.     

A solution approach for dynamic vehicle and crew scheduling

In this paper, we discuss the dynamic vehicle and crew scheduling problem and we propose a solution approach consisting of solving a sequence of optimization problems. Furthermore, we explain why it is useful to consider such a dynamic approach and compare it with a static one. Moreover, we perform a sensitivity analysis on our main assumption that the travel times of the trips are known exactly a certain amount of time before actual operation.We provide extensive computational results on some real-world data instances of a large public transport company in the Netherlands. Due to the complexity of the vehicle and crew scheduling problem, we solve only small and medium-sized instances with such a dynamic approach. We show that the results are good in the case of a single depot. However, in the multiple-depot case, the dynamic approach does not perform so well. We investigate why this is the case and conclude that the fact that the instance has to be split in several smaller ones, has a negative effect on the performance.     

Study of discrete automaton models of gene networks of nonregular structure using symbolic calculations

We introduce the discrete automaton models of gene networks with weight functions of vertices accounting for the various forms of the regulatory interaction of agents. We study the discrete mapping that describes the operation of a fragment of the gene network of the bacteria E. coli. For this mapping, we find its fixed points (stationary states) on using the SAT approach. We also study the mappings that are defined by the random graphs of the network which we generate in accordance with the Gilbert-Erdos-Renyi and Watts-Strogatz models. For these mappings, we find the fixed points and the length 2 and 3 cycles. This article can be regarded as a survey of our results on the discrete models of gene networks and the numerical methods for studying their operation.     

Differential evolution with generalized differentials

In this paper, we study the mutation operation of the differential evolution (DE) algorithm. In particular, we propose the differential of scaled vectors, called the ‘generalized differential’, as opposed to the existing scaled differential vector in the mutation of DE. We derive the probability distribution of points generated by the mutation with ‘generalized differentials’. We incorporate a vector-projection-based exploratory method within the new mutation scheme. The vector projection is not mandatory and it is only invoked if trial points continue to be unsuccessful. An algorithm is then proposed which implements the mutation strategy based on the difference of the scaled vectors as well as the vector projection technique. A numerical study is carried out using a set of 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the new algorithm is superior to DE.     

Solving machine-loading problem of a flexible manufacturing system with constraint-based genetic algorithm

Machine-loading problem of a flexible manufacturing system is known for its complexity. This problem encompasses various types of flexibility aspects pertaining to part selection and operation assignments along with constraints ranging from simple algebraic to potentially very complex conditional constraints. From the literature, it has been seen that simple genetic-algorithm-based heuristics for this problem lead to constraint violations and large number of generations. This paper extends the simple genetic algorithm and proposes a new methodology, constraint-based genetic algorithm (CBGA) to handle a complex variety of variables and constraints in a typical FMS-loading problem. To achieve this aim, three new genetic operators—constraint based: initialization, crossover, and mutation are introduced. The methodology developed here helps avoid getting trapped at local minima. The application of the algorithm is tested on standard data sets and its superiority is demonstrated. The solution approach is illustrated by a simple example and the robustness of the algorithm is tested on five well-known functions.     

Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation

The Biogeography-Based Optimization algorithm and its variants have been used widely for optimization problems. To get better performance, a novel Biogeography-Based Optimization algorithm with Hybrid migration and global-best Gaussian mutation is proposed in this paper. Firstly, a linearly dynamic random heuristic crossover strategy and an exponentially dynamic random differential mutation one are presented to form a hybrid migration operator, and the former is used to get stronger local search ability and the latter strengthen the global search ability. Secondly, a new global-best Gaussian mutation operator is put forward to balance exploration and exploitation better. Finally, a random opposition learning strategy is merged to avoid getting stuck in local optima. The experiments on the classical benchmark functions and the complexity functions from CEC-2013 and CEC-2017 test sets, and the Wilcoxon, Bonferroni-Holm and Friedman statistical tests are used to evaluate our algorithm. The results show that our algorithm obtains better performance and faster running speed compared with quite a few state-of-the-art competitive algorithms. In addition, experimental results on Minimum Spanning Tree and K-means clustering optimization show that our algorithm can cope with these two problems better than the comparison algorithms.     

Performance analysis in a re-entrant operation with combinational routing and yield probabilities

Queuing networks arising from multistage processes with probabilistic re-entrant lines are common in manufacturing environments. Probabilistic re-entrant operation is defined as lots entering the operation with different repeated cycle requirements. This paper extends our work [S. Kumar, M.K. Omar, Stochastic re-entrant line modeling for an environmental stress testing in a semiconductor assembly industry, Appl. Math. Comput. 173 (2006) 603–615.] and proposes a modified analytical method based on the mean value analysis (MVA) technique and considering a probabilistic re-entrant line with yield loss probabilities. Introducing probabilities consideration into the MVA approach will substantially increase the complexity of the modeling and results analysis. However, the contribution of this paper is the introduction of a solution methodology that can overcome such complexity and allow operational managers to compute performance measures such as total cycle time and the mean throughput.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.