As one of the main contents of influence analysis, influence maximization is selecting a group of influential nodes with specified size in a given network to form a seed node set, and the influence spread cascaded by ...
详细信息
As one of the main contents of influence analysis, influence maximization is selecting a group of influential nodes with specified size in a given network to form a seed node set, and the influence spread cascaded by the selected seed node set can be maximized under a given propagation model. The research of influence maximization is helpful to understand social network and viral marketing. How to develop an effective algorithm to solve this problem in large-scale networks is still a challenge. In this paper, a discrete differential evolution algorithm based on community structure (CDDE) is proposed. At first, the fast Louvain algorithm is used to detect the community structure. On this basis, significant communities are defined and candidate nodes are extracted from each significant community. And then, an improved discrete differential evolution algorithm is proposed to obtain influential nodes. Furthermore, a population initialization strategy based on candidate nodes is designed, and the candidate nodes are also used to accelerate the discreteevolution process of the population. Experimental results on six real-world social networks show that the proposed CDDE is competitive with the comparison algorithms in terms of effectiveness and efficiency, and achieves comparable influence spread to CELF.
This paper deals with a distributed blocking flowshop scheduling problem, which tries to solve the blocking flowshop scheduling in distributed manufacturing environment. The optimization objective is to find a suitabl...
详细信息
This paper deals with a distributed blocking flowshop scheduling problem, which tries to solve the blocking flowshop scheduling in distributed manufacturing environment. The optimization objective is to find a suitable schedule, consisting of assigning jobs to at least two factories and sequencing the jobs assigned to each factory, to make the maximum completion time or makespan minimization. Two different mathematical models are proposed, and in view of the NP-hardness of the problem, a novel hybrid discretedifferentialevolution (DDE) algorithm is established. First, the problem solution is represented as several job permutations, each of which denotes the partial schedule at a certain factory. Second, four widely applied heuristics are generalized to the distributed environment for providing better initial solutions. Third, both operators of mutation and crossover are redesigned to perform the DDE directly based on the discrete permutations, and a biased section operator is used to increase the diversity of the searching information. Meanwhile, an effective local search based on distributed characteristics and an elitist retain strategy are integrated into the DDE framework to stress both local exploitation and global exploration. Taking into account the time cost, an effective speed-up technique is designed to enhance the algorithmic efficiency. In the experimental section, the parameters of DDE are calibrated by the Taguchi method. Experimental results derived from a wealth of test instances have demonstrated the algorithmic effectiveness, which further concludes that the proposed DDE algorithm is a suitable alternative approach for solving the problem under consideration.
in order to solve the motor train-sets scheduling problem, a hybrid discrete differential evolution algorithm is proposed. The mathematical model is established for minimizing the total continuous time of one motor tr...
详细信息
ISBN:
(纸本)9789881563958
in order to solve the motor train-sets scheduling problem, a hybrid discrete differential evolution algorithm is proposed. The mathematical model is established for minimizing the total continuous time of one motor train-sets station. A hybrid algorithm of discretedifferentialevolution with scatter search is submitted to solve the motor train-sets scheduling problem. With regard to the initial population, more advanced designs derive from scatter search. Diversification generation method generates trial solutions. improvement method transforms a trial solution into one or more enhanced trial solutions. In discretedifferentialevolution, new differential mutant and crossover operators are designed based on integer permutation. The performance of the proposed hybrid algorithm is tested on the model of the train-sets scheduling, which shows that it outperforms the compared algorithm. The optimal scheduling scheme can be obtained effectively to achieve the minimum total continuity time.
In order to solve the motor train-sets scheduling problem,a hybrid discrete differential evolution algorithm is *** mathematical model is established for minimizing the total continuous time of one motor train-sets st...
详细信息
In order to solve the motor train-sets scheduling problem,a hybrid discrete differential evolution algorithm is *** mathematical model is established for minimizing the total continuous time of one motor train-sets station.A hybrid algorithm of discretedifferentialevolution with scatter search is submitted to solve the motor train-sets scheduling *** regard to the initial population,more advanced designs derive from scatter *** generation method generates trial *** method transforms a trial solution into one or more enhanced trial *** discretedifferentialevolution,new differential mutant and crossover operators are designed based on integer *** performance of the proposed hybrid algorithm is tested on the model of the train-sets scheduling,which shows that it outperforms the compared *** optimal scheduling scheme can be obtained effectively to achieve the minimum total continuity time.
Batch processing machines (BPMs) simultaneously process multiple jobs in a batch, which are commonly used in many industrial systems. This paper studies the scheduling problem of uniform parallel batch processing mach...
详细信息
Batch processing machines (BPMs) simultaneously process multiple jobs in a batch, which are commonly used in many industrial systems. This paper studies the scheduling problem of uniform parallel batch processing machines with arbitrary job sizes. These batch processing machines have non-identical capacities and different speeds. The objective is to minimize the makespan (or maximize the machine utilization). We formulate this problem as a mixed integer programming model. Since the problem is strongly NP-hard, an effective differentialevolution-based hybrid algorithm is proposed for solving large-scale problems. Firstly, in this algorithm, individuals in the population are represented as discrete job sequences, and novel mutation and crossover operators are designed based on this representation. Next, a heuristic is developed to form batches and schedule the resulting batches on the uniform parallel machines. Then, the performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a random keys genetic algorithm (RKGA) and a particle swarm optimization (PSO) algorithm. Experimental results demonstrate the superiority of the proposed algorithm in terms of solution quality and robustness, especially for large-scale instances. (C) 2016 Elsevier B.V. All rights reserved.
Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported fro...
详细信息
Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported from a workstation to another by a material handling hoist. The existing literature mainly addressed how to find an optimal cyclic schedule to minimize the cycle time that measures the productivity of the lines. The material handling cost is an important factor that needs to be considered in practice but seldom addressed in the literature. This study focuses on a biobjective cyclic hoist scheduling problem to minimize the cycle time and the material handling cost simultaneously. We consider the reentrant workstations that are usually encountered in real-life lines but inevitably make the part flow more complicated. The problem is formulated as a biobjective linear programming model with a given hoist move sequence and transformed into finding a set of Pareto optimal hoist move sequences with respect to the bicriteria. To obtain the Pareto optimal or near-optimal front, a hybrid discretedifferentialevolution (DDE) algorithm is proposed. In this hybrid evolutional algorithm, the population is divided into several subpopulations according to the maximal work-in-process (WIP) level of the system and the sizes of subpopulations are dynamically adjusted to balance the exploration and exploitation of the search. We propose a constructive heuristic to generate initial subpopulations with different WIP levels, hybrid mutation and crossover operators, an evaluation method that can tackle infeasible individuals and a one-to-one greedy tabu selection method. Computational results on both benchmark instances and randomly generated instances show that our proposed hybrid DDE algorithm outperforms the basic DDE algorithm and can solve larger-size instances than the existing e-constraint method. (C) 2016 Elsevier Ltd. All rights reserved.
This paper addresses a dynamic scheduling problem in robotic cells, where a computer-controlled robot is responsible for handling materials between workstations. In such automated manufacturing systems, efficiently sc...
详细信息
ISBN:
(纸本)9781509028429
This paper addresses a dynamic scheduling problem in robotic cells, where a computer-controlled robot is responsible for handling materials between workstations. In such automated manufacturing systems, efficiently scheduling transportations of the material plays an important role in improving the throughput of the system. We consider an uncertain setting where more than one new jobs arrive at the system and need to be scheduled immediately. To reduce the disturbance occurred by frequently rescheduling or adjusting the existing schedule, we keep the existing schedule unchanged and insert the new jobs' processing operations and transportations into the available(idle) time intervals of the workstations and the robot, respectively. To get an optimal new schedule, the problem is formulated as a mixed integer programming model with the objective that minimizes the total completion time of the new jobs. As the NP-hard nature of the problem, a hybrid discretedifferentialevolution (DDE) algorithm is proposed to search for a near-optimal solution within a reasonable computational time. In the hybrid DDE, a extension heuristic method is developed to generate a local optimal solution provided that a new jobs inserting sequence is given, and the DDE is applied to search for an optimal or near-optimal new jobs inserting sequence. The computational results indicate that the hybrid DDE runs effectively to search for the optimal or near-optimal new schedules.
This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper...
详细信息
This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn-Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.
differentialevolution (DE) is one of the most prominent new evolutionary algorithms for solving real-valued optimization problems. In this article, a discrete hybrid differentialevolutionalgorithm is developed for ...
详细信息
differentialevolution (DE) is one of the most prominent new evolutionary algorithms for solving real-valued optimization problems. In this article, a discrete hybrid differentialevolutionalgorithm is developed for solving global numerical optimization problems with discrete variables. Orthogonal crossover is combined with DE crossover to achieve crossover operation, and the simplified quadratic interpolation (SQI) method is employed to improve the algorithm's local search ability. A mixed truncation procedure is incorporated in the operations of DE mutation and SQI to ensure that the integer restriction is satisfied. Numerical experiments on 40 test problems including seventeen large-scale problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method.
Aiming at the stochastic vehicle routing problems with simultaneous pickups and deliveries, a novel discrete differential evolution algorithm is proposed for routes optimization. The algorithm can directly be used for...
详细信息
ISBN:
(纸本)9783037856529
Aiming at the stochastic vehicle routing problems with simultaneous pickups and deliveries, a novel discrete differential evolution algorithm is proposed for routes optimization. The algorithm can directly be used for the discrete domain by special design. Computational simulations and comparisons based on a medium-sized problem of SVRPSPD is provided. Results demonstrate that the proposed algorithm obtains better results than the basic differentialevolutionalgorithm and the existing genetic algorithm.
暂无评论