Research And Application On Discrete Swarm Intelligence Optimization

Many scientific,engineering and economic problems need the optimization of a set of decision-making variables with the aim of choosing the optimum one from many candidate schemes to minimize or maximize the objective function.The application of optimization methods is very extensive,and it involves a lot of problems and these problems have different characteristics.According to different principles,they can be divided into different classes.For example,according to the value type of the decision-making variable,they can be divided into two classes, function optimization problem and combinational optimization problem(namely, discrete optimization problem).The discrete optimization problem is an important optimization problem,and with the development of computer science,the science of the management and the technology of the modern production,it is getting more and more attention by the subjects of operational research,applied mathematics,computer science and management science.Most part of these problems being optimized is NP-hard problem.Since many years,people are trying to look for efficient algorithms to solve the combinational problem,and many efficient algorithms have been proposed,but NP problem is still a science difficulty problem in the 21century,and it is not solved in the complexity field of the theory informatics yet.Swarm intelligent optimization method is an emerging area of research,which provides an effective tool for solving complex optimization problems,and it has attracted extensively attentions from different research areas.The comprehensive and typical methods of swarm intelligence optimization are Ant Colony Optimization (ACO) and Particle Swarm Optimization(PSO).ACO was offered in 1991 by Marco Dorigo,an Italian researcher.And James Kennedy and Russell Eberhart offered PSO based on the simulating of birds colonys' and fish colonys' preying action in 1995. These methods received recognition in international optimization computing field rapidly because the methods are simple in concept,few in parameters,and easy in implementation,especially in solving complex combinational optimization problem,it was also applied successfully in engineering design and production optimization.In this dissertation,after the essential components of discrete particle swarm are searched systematically,a simple and effective binary discrete PSO is introduced.Then it gives a modified discrete PSO for linear order problem.The next,it presents a comparison of initial population generation schemes for permutation flowshop scheduling problem with the makespan criterion.Finally,it proposes a parallel multiple ant colonies optimization which can avoid some stagnating states of the iteration in the basic ACO.The main contributions and innovative viewpoints of this dissertation are summarized as follows:(1) In Search of the essential binary Discrete Particle Swarm.In this part,the canonical particle swarm algorithm is broken down into its essential components,and reinterpreting them in another ways as new program.After that,these essential components are recombined in a different manner which builds a fast and easy binary discrete PSO(BPSO).In this algorithm each particle represents a candidate solution of the problem being solved in which all solution elements can only be either 0 or 1.In next position of a particle,the probability of a certain particle element assuming a value of 0 or 1 is in positive proportion to value 0 or 1 of this element in the current position of the particle,the historic best position it experienced,and the historic best position experienced of its immediate neighbors in the topological population;but in negative proportion to value 0 or 1 of this element in the former position of the particle.This algorithm doesn't involve the meaning of velocity which is usually hard to be defined in the discrete PSO.Furthermore,it only use value proportion probability,and needn't sigrnoid function and quantitative limitation on any variable. Iterative formulas are simple,reliable and easy to understand.It provides a new angle of observation point to the essential of binary discrete PSO and a solid base for future research.Experimental results show that this algorithm is faster than the Standard binary discrete PSO on a suite of test functions,and that accuracy is improved for most benchmark functions used.A queen informant is also introduced.It informs all the other particles,but only the global best particle updates it.It has two parts and each part owns the same dimension as other particle.Each value in the queen informant represents the proportion probability of a particle element assuming a value of 0 or 1.Its updating rule is the same as that of pheromone in the ACO.It doesn't increase the number of function evaluations;however,it appears that it greatly speeds up the convergence. Simulation experiments also prove its efficiency and good performance.(2) Discrete Particle Swarm Optimization for Linear Order Problem.The linear order problem(LOP) consists of finding a permutation of the columns(and rows) of a matrix of weights in order to maximize the sum of the weights in the triangle above the main diagonal of this matrix.It is a NP-hard problem.This paper introduces a modified discrete PSO(DPSO) for LOP.It doesn't use exchange,crossover,mutation, insertion and deletion operators.But the positions of elements in solution permutation are stored in the particle instead of elements themselves.We only change our observation point of view and conceive the velocity as the shift in the position of elements.So the particle position is updated in much the same way as the canonical continuous PSO.Then the updated solution permutation was obtained by sorting the values of the updated position of elements.Experiments on instances in LOLIB show that the modified DPSO is promising in the linear order problem.It is suitable to the optimization of the kind of permutation problems in which solution absolute positioning of the elements is more important than relative positioning of the elements.(3) A Comparison of Initial Population Generation Schemes for Permutation Flowshop Scheduling Problem with the Makespan Criterion.Initializing a population of solutions is the first period in many swarm intelligence techniques,such as Genetic Algorithm(GA),Scatter Search(SS),Particle Swarm Optimization(PSO),Memetic Algorithm(MA),Differential Evolution Algorithm(DE),etc.These approaches are applied to solve permutation flowshop scheduling problem(PFSP).It is an open issue how to create a high-quality and diverse initial population in order to reduce the computational time of these techniques.However,previous comparative studies only involved the initial methods which produced only a single initial solution.This article compares the quality and diversity of the population which are created by different initial population constructions for minimizing makespan in PFSP on Taillard(1993)'s famous benchmarks.This paper can be seen as a starting point for future research needs of improving and developing better approaches to PFSP.You can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization implementations.And the efficiency of algorithms can be largely increased by selecting a good initial population.In a word, you can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization schemes we have analyzed.(4) Parallel Ant Colony Algorithm using both Pheromone Crossover and Repulsive Operator based on Multi-Optimum for TSP.At the same time,many ant colonies exist in parallel ant colony optimization.Making full use of this characteristic,it proposes a new method to induce local premature convergence.It introduces two operators: pheromone crossover and repulsive operator.It employs master/slave paradigm,star topology.Master processor locates in the center,and every slavery ant colony owns its pheromone array and parameters.Above all,several slavery ant colonies are created, and then they perform iterating and updating their pheromone arrays respectively. Once a colony ant system arrives at stagnating state,the master processor reinitializes it by using both pheromone arithmetic crossover and repulsive operator based on multi-optimum.At the same time,the main parametersα,βand p of algorithm are adjusted self-adaptively.It can avoid some stagnating states of the iteration in basic ant colony optimization.The contents of communication between master processor and slave processors only are some parameters and several sub-optimum solutions,the computation to communication time ratio is relatively small.In this paper,a parallel asynchronous algorithm process is also presented.At the end of this paper,the experimental result is presented to show the effectiveness of this method for TSP.