ABSTRACT

In design science, these two kinds of problems are mutually nested, however, the nesting could not blind us for the fact that their problem-solving and solution justification methods are different. The ant algorithms research field, builds on the idea that the study of the behavior of ant colonies or other social insects is interesting, because it provides models of distributed organization which could be utilized as a source of inspiration for the design of optimization and distributed control algorithms. In this paper, a relatively new type of hybridizing ant search algorithm is developed, and the results are compared against other algorithms. The intelligence of this heuristic approach is not portrayed by individual ants, but rather is expressed by the colony as a whole inspired by labor division and brood sorting. This solution obtained by this method will be evaluated against the one obtained by other traditional heuristics.

Keywords:Genetic Algorithm, Search, Ant Algorithms, No Fit Polygon, Simulated Annealing

1. Introduction

For cutting and packing problems, one or more pieces of material/space could be divided into smaller ones. Usually, the minimization for waste is the important aim for the combinatorial optimization. Also, it is an objective to minimize the size of the material, which is equivalent to maximizing the material utilization [1] [2] . The more usual target is to minimize the waste of the larger one. In this case, people should maximize the fabric utilization or minimize the fabric waste equivalently. Traditionally, nesting problems have been tackled mainly by heuristic methods, which try to generate good solutions for searching the solution space [3] [4] .

This paper focuses on the height of the bin, which is considered infinite with the aim of the evaluation function to minimize the height. On one hand, the convex polygons are considered. Only one bin is used (i.e., no concept of filling a bin), with the allowed guillotine cuts, which must be made from one edge to the next [5] [6] .

On the other hand, ant algorithm is relatively new search mechanism, which was initially applied to the Traveling Salesman Problem (TSP) problem [7] . The social behavior of ants is based on self-organization, a set of dynamical structure. A crucial feature of this interaction is that the system elements utilize only local information. In this scrnario, self-organization is a result of the interaction between the following four components: multiple renewal, randomness, positive feedback, negative feedback. As a result, models in terms of self-organization have recently been introduced by ethologists to study collective behavior in social insects [8] [9] . For example, a model of cooperative foraging in ants has been transformed into a set of optimization algorithms, now known as Ant Colony Optimization (ACO) [10] , tackling very hard computational problems, such as the TSP problem, the sequential ordering problem, various scheduling problems [11] [12] . More recently, ACO has been successfully applied to distributed control problems such as adaptive routing in communications networks [13] .

The other way of tackling combinatorial optimization problems, building mixed integer programming models and solving them with appropriate software, accounts for the resolution of Nesting Problems of very small size [14] , then an optimal solution could be found [15] . However, this is not possible, so only good solutions can be found, given for the partial solution and the next piece is placed [16] .

2. No Fit Polygon Positions

In this case, the combinatorial problem coexists with a geometric one, since solutions must be geometrically feasible: pieces may not overlap and should fit inside the plate completely. Also, the geometric constraints of the problem have been tackled with the No Fit Polygon. In Figure 1, most variants of the nesting problem is the problem of packing shapes within some regions without overlap. On the other hand, the strip packing variant accounts for a minimization of the length of a rectangular region. The No Fit Polygon (NFP) makes all arrangements, where two arbitrary polygons could take when the polygons touch but do not overlap.

3. Method Evaluation

3.1. Ants Colony Searching Routing

In Figure 2, with the scattering search process, useful information about the form or location of the global solution is typically contained in a diverse collection of elite solutions. In this algorithm, the weight of the best solution is increased when it is in use. The pheromones are updated only at the edges of the best route, so the general choice follows below. The nesting problem is NP-hard, while pheromone evaporation is the process concerning the pheromone trail intensity on the components decreases over time. As for most of the ideas of ACO stem from real ants, to differentiate between good and bad solutions, the genetic algorithms use an adaptive fitness function.

•   Nesting: A short name for this problem, which is often used in the existing literature.

•   Stencil: A domain specific name for the pieces/shapes/polygons to be packed.

•   Material: A general word for the packing region which can be utilized to describe garments, metal plates, wood and more.

Cooperating individuals colony. For real ant colonies, ant algorithms are composed of a population, or colony, of concurrent and asynchronous entities globally cooperating to find a good solution to the task under consideration. With daemon actions which cannot be performed by single ants, ants concurrently read/write on the problem states they visit, as explained in the next item.

Stigmergy and pheromone trail. While real ants deposit on the world’s state they visit a chemical substance, the pheromone, artificial ants change some numeric information locally stored in the problem’s state they visit. It implements a useful form of forgetting, favoring the exploration of new areas of the search space. From a practical point of view, this information takes into account the ant’s current performance and can be accessed for the state. Implicitly maintaining a pool of alternative partial routes is the way the system copes with changing conditions and allows it to be flexible and robust.

Shortest path searching and local moves. Artificial ants, as real ones, build solutions applying a probabilistic decision policy. This self-organizing, adaptive aspect of labor division could be explained by a simple behavioral threshold model: although each ant is equipped with a complete set of behavioral responses, different ants

have different threshold for different behaviors. Therefore, the selection is performed with an elitism strategy, when the new population first incorporates the best chromosome and, then, the remaining chromosomes are selected. 1) Artificial ants live in a discrete world and their moves consist of transitions from discrete states to discrete states. 2) Artificial ants have an internal state. 3) Artificial ants deposit an amount of pheromone which is a function of the quality of the solution found. 4) Artificial ants timing in pheromone laying is problem dependent.

3.2. Placing the Polygons with Search Process

Once all placements have been considered, the convergence in the neighborhood of the optimum is enhanced through the use of the local search methods. A colony of ants concurrently and asynchronously build solutions to a given discrete optimization problem, to reduce the search space, the so-called building blocks are used.

Ant System (AS) was the first ACO algorithm. The ant algorithms are most often hybridized by adding localsearch techniques. At each iteration of an algorithm, these techniques try to improve solutions found by the ants.

4. Hybridizing Ant Algorithms

4.1. Ant Decisions for TSP

We consider similar approaches for improving the ant algorithms. This phenomenon is discussed by considering what happens when an ant comes across an obstacle. However, as ants walk they deposit a pheromone trail. The ant-decision of node i is obtained by the composition of the local pheromone trail values as follows:

(1)

where is the amount of pheromone trail on arc (i, j) at time t, is the heuristic value of moving from node i to j, is the set of neighbors of node i, and α and β are two parameters. The probability with which an ant k chooses to go from city i to city:

(2)

where is the set of nodes in the neighborhood of node i that ant k has not visited yet.

4.2. Heuristic Algorithms

It is clear that the value depends on how well the ant has performed:

(3)

where, m is the number of ants at each iteration, and ρ(0, 1] is the pheromone trail decay coefficient. Routing in communications networks is a very good example of this aspect.

Where i is the polygon just placed and j is the polygon about to be placed. Routing is the mechanism that directs messages in a communications network from their source nodes to destination nodes. This would result in a low visibility value.

(4)

5. Testing and Results

The changes needed to handle repeated patterns have been implemented in C++ and incorporated in the nesting program 2DNest. All experiments are done on a machine with a 3 GHz Pentium 4 processor. Moreover, the technique can be easily extended to other difficult problems such as multidimensional scaling or data sorting.

The method will not be able to find the optimum. The first two rows (A, B, C and D, E, F) can be constructed without problems. This value indicates how the rectangle of a solution is going to be shaped. One could easily construct problem instances which would see considerable improvements. Due to the convex nature of the large polygon, the final polygon will not be placed in the position shown. It is interesting to note that the ACO method has a feature which makes it particularly appealing: it is explicitly formulated in terms of computational agents. The solution is one stock sheet on a given unit. Given the input data, the initial domains of the placement point of each polygon need to be computed.

It is clear that the approach has great potentialities for the control of fleets of industrial robots in unstructured environments. All results are averaged over ten runs. The results show the evaluation value as well as the bin height.

To find suitable values for the parameters that control the ant algorithm, the candidate list is generated on the basis of prior knowledge of the problem or data updated dynamically during the solution. It has various values, and reached a similar conclusion. Therefore in the remainder of our tests Q = 100. In order to find a good value for the evaporation parameter, using a trail importance, a = 1 and a visibility importance, b Î{0, 1, 2,…, 30}. The results from these tests are shown in Figures 3-5.

The pheromone values on all edges are set equal each other. All tests show the highest evaluation when b = 0. This is expected as when b = 0 the search is effectively transformed into randomized greedy search with multiple starting points. In order to see if our algorithm agrees with this a test was carried that set p = 0.5, a = 5 and b = {1,…, 20}. Figure 6 and Figure 7 show that this set of parameters produces worse results than when a = 1.

Having established a good parameter set, we uses test data 2 to confirm these values. It shows two runs that compare the effect of p on test data 2. This test appears to confirm that p = 0.5 is a good choice in the remaining tests. It is clear that a higher value of a leads to inferior solutions. As a result, the best results are attained on both sets of test data. An ant selects a node different from those in the list only when the list has been exhausted.

6. Conclusion

The ant algorithms have been applied to the nesting problem and the results are encouraging. We have presented an efficient heuristic solution method which can construct very good solutions for strip nesting problems in which the solution is going to be repeated. The virtual ants select routes on the graph by a probability rule, based on the pheromone value and heuristic methods for solving specific problems. Results are given for fairly large instances and they strongly indicate that this can give a considerable reduction of waste for problem instances in the garment industry. Experiments have attested that the ant algorithms ensure a good balance between the solution accuracy and the optimization time.

References