| Ants are social insects that live in colonies and a very interesting aspect of several ant species'behavior is their ability to find shortest paths between the nest and the food sources.While walking between their nest and food sources,some ant species deposit a chemical called pheromone.In fact,experiments by some biologists have shown that ants probabilistically prefer paths that are marked by a high pheromone concentration:the stronger the pheromone trail,the higher its desirability.However,several biological studies show that the pheromone trails are very persistent(the pheromone can stay from several hours to several months depending on aspects sucn as the ant species,the pathtype,and so on),thus making less significant the influence of the evaporation in the shortest path searching behavior.It is difficult that ants forget a path with a high level of pheromone,although they have found a shorter one.Therefore,if this behavior is directly translated into the computer to design a search algorithm,we always can get an algorithm quickly getting stuck in local optima.Inspired by the foraging behavior of ants, many variants of ACO have been born and it has become a viable new approach to combinatorial optimization problems over the last couple of decades.The salient characteristics on this model are positive feedback,distributed computation,and the use of a constructive greedy heuristic. At present,the variants of ACO algorithms are based on a colony of artificial ants that work cooperatively and communicate through artificial pheromone trails.When walking on the edge of the graph,there are two kinds of information that guide the artificial ants'movement: Heuristic information,which measures the heuristic preference of moving from one node to another,and artificial pheromone trail information,which mimics the real pheromone that natural ants deposit.In contrast to many successful applications of combinatorial optimization problems,the theoretical research of Ant Colony Optimization(ACO) is rather weak.Up to now, only little mathematical proof results have been achieved showing that optimal solutions can be obtained in finite time.Moreover,how to determine the effect of the evaporation factor, a crucial parameter in ACO algorithm,and prove a phase transition from exponential to polynomial runtime,is really a complicated and defiant work.Evolutionary algorithm has strarted to receive significant attention during the last decade,although the origins can be traced back to the late 1950's.We describe the general structure and the working principles of different approaches, inlcluding genetic algorithms(GA),genetic programming(GP),evolution strategies(ES) and evolutionary programming(EP),and analyzed their representations,variation operators,reproduction and selection mechanism. Evolution programming (EP) that relies primarily on selection and mutation operators to search for solutions of optimization problems (OPs) is an important category of evolutionary algorithms. It. recently a series of new mutation operators have been proposed in order to improve the performance of EP. One prominent example is the fast EP (FEP) algorithm which employs a mutation operator based on the Cauchy distribution instead of the commonly used Gaussian distribution.Some research show that the interplay between the mutation operator and the selection mechanism plays a fundamental role in the behaviour of evolutionary programming. However, this interplay is still not completely understood.The adaptive parameters,also named step size control in EP play a significant role which controls the step size of the objective variables in the evolutionary process,but the step size of control are frequently lost and then make the search stagnate early.If applying the lower bound can maintain the step size,but it also constrains the objective variables from being further explored.Therefore, probing the balance between explore and exploit in evolutionary process is also a complicated and defiant work.The vehicle routing problem with time windows(VRPTW) is a bicriterion optimization problem. The aim is to minimize the set of routes, firstly, the number of vehicle used, and secondly,the total distance traveled by vehicles. For the widespread application and great value of economic, it has been widespread concern of scholars at home and abroad. In practical terms,the applications of the VRPTW include: school bus routing, newspaper and mail distribution,security patrol or maintenance services, air and rail schedule,and the collection of industrial waste,and so on.The main work is as follows:1. Gave a description of all kinds of Ant Colony Optimization, Evolutionary Programming and Mutation Operators, such as Gaussian mutation,Cauchymutation and Lévy mutation.etc.2.Analyzed the Lévy probability distribution who has two parameters,αandγ,αsatisfies 0 <α< 2andγis the scaling factor satisfyingγ> 0.The parameterαcontrols the shape of the probability distribution,especially in the tail region depending on the parameterα.That is,the samller the parameterα,the longer the tail.We generate four offspring withα= 1.0,1.3,1.7 and 2.0 from each parent as the candidates for the offspring.And then the best one out of four is chosen as the next offspring. This scheme is adaptive in the sense that different offspring can be chosen depending on the environment. 3.Propose a new Max-Min Ant SystemThe basic ideas of EP and ACO are quite different: EP uses the action of each individual, and it's search strategies does not care about where is the promising region it should go,but to escape local minima,while ACO use estimation with information included in population,and the ants generate new solution from the distribution of pheromone laid on the path.It is our contribution for us to see what results will be if these two kinds of optimization methodologies are connected together.On this point,this paper presents a hybrid algorithm that based on the framework of MMAS to utilize the advantages of both the idea of EP and ACO for VRPTW. HMMAS-VRPTW is organized with two artificial ant colonies designed to optimize the VRPTW:the first colony minimizes the number of vehicles while the second one minimizes the traveled distances.Cooperation between the colonies is performed by echanging information through pheromone updating.And then to strengthen the performance of the proposed framework, the Lévy Probability Distribution,which can generate any distribution between the Gaussian mutation that was better at finding a solution in the vicinity of the global optimum and the Cauchy mutation that performed better when the current search point was relatively farther away from the global optimum point,was used. By analyzing the difference between the vehicle routing problem with time window and traveling salesman problem, the state transition strategy of the max-min ant colony system is improved and the depot is duplicated a number of times equal to the number of available vehicles. These two colonies work by using independent pheromone trails but collaborate by sharing the global best feasible solution, and so it can decrease computing time and overcome early convergence. Some experimental study show that HMMAS-VRPTW is effective both in terms of solution quality and computation time. |
PDF Full Text Request