Improved Ant Colony Algorithm For One-dimensional Cutting Stock Problem

This paper mainly introduces the basic ant colony algorithm, one-dimensional cutting stock problem and the improved ant colony algorithm in the application of one-dimensional cutting stock problem. The introduction starts with the basic ant colony algorithm, the production of the development process and applications of the ant colony algorithm researchs. Then we discuss the basic principles of the algorithm and some of the successful improved models based on the basic ant colony algorithm, as well as the comparison between ant colony algorithm and other searching algorithms.Next, this paper introduces the application of ant colony algorithm - one-dimensional cutting stock problem in detail, and also establishes a mathematical model whose target is the least sum of the residual material and the least raw material consumption. Following this is a simple example to illustrate the one-dimensional cutting stock problem and the basic steps to solve the interception program. At last,list several one-dimensional cutting stock algorithms which are usually used.The focus of this paper is to introduce the improved ant colony algorithm and its applications in one-dimension cutting stock problem. Although the ant colony algorithm makes a success in a series of difficult combinatorial optimization problem through its internal mechanism, the ant colony algorithm also has some drawbacks. First, when the ant group is larger, it will take a longer time to find a better path because the movement of some individuals in the ant group is random,; Second, it's easy to fall into local optimal solution problem as a result of strengthening the role of pheromones.Our job is to make an improved methods for the two shortcomings above. For the first one, we focus on the improvement on the efficiency of the algorithm and propose three strategies:(1)Reduce the number of the ants for each iteration. There is a great relationship between the number of ants and the time complexity of the algorithm. If the iteration has done for 5 times (or 10) and the optimal solution does not change or changes a little, the algorithm reduce a certain number of ants. Now genetic variation has been brought in, so the local optimal solution can be avoided.(2)Establish a candidate node set. Sort the distance between a city and its surroundings, and we choose the method that only select a fixed number of nodes nearby. So a lot of time can be reduced because not all the nodes need to be calculated.(3)Rank based updated pheromone. During the initial stage of ant colony algorithm iteration, all the paths that ants have traversed have to update pheromone which ensures the diversity of solutions. With the increasement of iteration, carry out cross-genetic algorithm, mutation operation to the solution and bring in the updating pheromone strategy which based on the optional rank based ant system. The strategy select the paths topωants following to update the pheromone, according to the quality of solutions. The pheromone on the path are controlled in the range-[τmin ,τmax].For the second shortcoming, this paper propose four strategies which focus on the ability to solve the problem:(1)Transition probability strategy. Select nodes in the candidate sets firstly as the next node, and the rest of the nodes can be chosen only after the candidates are finished.(2)Ant individual differences. Because the parametersα,βvalues are not identical in each probability function p of ant routing, the strategy of ant behavior is diversity. The improved ant colony algorithm performs the simulation of individual differences in nature. We can get a better result for the ants of different routing strategies effects each other than a single ant colony strategy.(3)Parametersα,βadaptive adjustment. At the initial stage , set theα,βto a smaller value, and this can expand the searching scope. Later, we can reduce the solution space by increasing the parametersα,βvalues, so the search can goes to a better path gradually and the form positive feedbacks. This will not only speed up the algorithm convergence rate but also find better solutions quicly when the algorithm falls into a local optimal path, because the roles of positive feedback are strengthened. So the algorithm can jump out of local optimal values in time.(4)Combined with the genetic algorithm. Hybrid genetic algorithm into the ant colony algorithm, so the improved ant colony algorithm gain the benefits of crossover and mutation of genetic algorithm. Enhance the capacity to find the overall optimal solution and speed up the algorithm convergence speed through the introduction of crossover operator and mutation operator. Replace the original path if the path length decreases after mutation, otherwise retain it.The improvement to basic ant colony algorithm has greatly enhanced the excution efficiency and calculation capacity. The improved algorithm has an obvious advantage in algorithm efficiency, mainly reflected in the significant reduce of selection number on Colony Road, and this is more obvious with the expansion of city size. The overall optimal solution algorithm for solving ability is obviously improved when efficiency is enhanced, which is mainly performed in self-adaptive parameters emerged with the advantages of genetic algorithm, strengthening the capacity of the overall solution.The second emphasis of this paper is proposing some useful suggestions by analyzing the various parameters (number of ants m, the information intensity of Q, the information heuristic factorα,β, as well as information residual coefficientρ) and their impact on the solutions. In this article, we analyze various parameters in the Ant Colony Algorithm probability function, try to summarize some priciples and get some constructive results.