Abstract: The theory of evolution is an instrument for optimization in the process of solution for problems of different nature with the main goal creating a population of eventual solutions using some of the most characteristic peculiarities of nature – heredity, changeability, selection and so on. Most of the current research on evolutionary optimization has concentrated on design of naturally inspired evolutionary algorithms to search for nondominated solutions. This is the inspiration behind this work to develop an evolutionary algorithm based on plant and animal breeding. The area of Selective Breeding is emerging as an active and attractive field involving models, techniques and applications of greater diversity. In this study, a novel evolutionary algorithm based on selective breeding is developed. Bin packing of N = n2 pieces in a massively parallel computing environment of n2 processors operating in SIMD mode is used for evaluating the performance of SBA algorithm. Results are compared with other packing algorithms reported in the literature. Selective Breeding Algorithm (SBA) is good problem solving technique for the Bin Packing (BP) application and it gives comparatively optimal result with other packing algorithms.
INTRODUCTION
Evolutionary computation is a generic term used to indicate any population-based metaheuristic optimization algorithm that uses mechanisms inspired by biological evolution, such as reproduction, mutation and recombination (Yang, 2011). Artificial selection practiced by breeders of agricultural plants and domesticated animals. Breeders of animals and plants in today's world are looking to produce organisms that will possess desirable characteristics, such as high crop yields, resistance to disease, high growth rate and many other phonotypical characteristics that will benefit the organism and species in the long term. This is usually done by crossing two members of the same species which possess dominant alleles for particular genes, such as long life and quick metabolism in one organism crossed with another organism possessing genes for fast growth and high yield. Since both these organisms have dominant genes for these desirable characteristics, when they are crossed they will produce at least some offspring that will show all of these desirable genetically characteristics. When such a cross occurs, the offspring is termed a hybrid, produced from two dissimilar parents who usually produce offspring with more desirable qualities (http://www.biology-online.org/2/12selectivebreeding.html).
Bin Packing (BP) problem is a NP-hard problem which consists of a finite set of items with different sizes and a set of bins with same capacity (Coffman et al., 1978). The aim of the BP problem is to partition the items between the bins so that the sum of item sizes in each bin is less than or equal to the capacity of bin (Garey and Johnson, 1979). Recently, most of BP problems reported in literature mainly concentrated on number of bins being used and cost function due to the major focus on traditional grouping problems, i.e., storage of goods and allocation of products etc. (Kang and Park, 2003). Bin packing is an optimization problem that plays an important role in many combinatorial problems existing in the areas of computer science and operations research. In this problem, a set of n objects having weights between 0 and 1 is placed in a set of unit bins so as to minimize the number of bins used. A number of heuristics have been developed to find solutions (Coffman et al., 1984).
There have been two different approaches taken in studying sequential approximation algorithms for bin packing. One has been to look at simple heuristics and to analyze their behavior (Berkey and Wang, 1989). First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) are two well-known algorithms developed by Coffman et al. (1983) were used to solve the BPP without conflict. The Minimum Bin Slack (MBS) heuristic of Gupta and Ho (1999) is bin-focused. At each step, an attempt is made to find a set of items that fits the bin capacity as much as possible. In the one dimensional bin packing problem, the goal is to minimize the number of bins that contain a given set of weights, subject to a limitation of the total weight each bin can contain (Kao, 1992; Pargas and Jain, 1993; Fleszar and Charalambous, 2011). Selective breeding algorithm must yield an acceptable solution while maximizing the utilization of the processors and minimizing the total interprocessor communication time. It is therefore important to choose an appropriate representation for both the pieces and the bins. The proposed algorithm distributes the pieces to the processors in such a manner that both the movement of pieces between processors and the packing time for the bins is minimized. The proposed algorithm increases the packing efficiency while decreasing the amount of internode communication that is necessary. Falkenauer (1996) developed a Grouping Genetic Algorithm (GGA) which is a Genetic Algorithm (GA) designed for bin packing problems. The GGA integrates problem specific information in its encoding and operators which is not a tailored GA.
Natural selection is nothing more than random variation in plants and animals. In total contrast, is ‘artificial selection’ or selective breeding. Evolutionists point to the results of selective breeding as an example of what natural selection accomplishes. But there is a vast difference between them. Several points should be kept in mind, among which are these: The results of breeding never cross the species line; they are always improvements within a species. There is a limit to how much change can be made. Beyond that limit, no further changes can be made. The wall imposed by the genetic code cannot be penetrated. "Improvements" through breeding may improve certain qualities but others will be weakened. The original was generally stronger and more vigorous than the "improved" varieties. After being left alone for a time, the improved varieties will slip back toward the original pattern. The very fact of success in breeding points out that intelligent mind caused it, by careful observation at each step. It is just that: "selective breeding” (Gjedrem, 1985).
Breeders continuously track which characteristics are possessed by each organism so when the breeding season comes once again, they can selectively breed the organisms to produce more favorable qualities in the offspring. The offspring will become heterozygous, meaning the allele for each characteristic will possess one dominant and one recessive gene. Most professional breeders have a true breeding cross (i.e., AAbb with AAbb) so that they will produce a gene bank of these qualities that can be crossed with aaBB to produce heterozygous offspring. This way the dominant features are retained in the first breeding group and can be passed on to offspring in the second instance. Suppose this is crossed with “aaBB” means, different combinations are possible. This kind of selecting parents for crossing is called artificial selection or selective breeding and poses no threat to nature from man manipulating the course of nature. It has allowed our species to increase the efficiency of the animals and plants we breed, such as increasing milk yield from cows by continuously breeding selected cows with one another to produce a hybrid (Gjedrem, 1997).
PROBLEM DESCRIPTION
The classical one dimensional bin packing problem consists of a set of pieces which must be packed into as few bins as possible. Each piece j has a weight wj and each bin has capacity c. The objective is to minimise the number of bins used, where each piece is assigned to one bin only and the weight of the pieces in each bin does not exceed c. A mathematical formulation of the bin packing problem is shown in equation:
Subject to:
where, yi is a binary variable indicating whether bin i contains pieces, xij indicates whether piece j is packed into bin i and n is the number of available bins.
PROPOSED SELECTIVE BREEDING ALGORITHM
SBA algorithm consists of following steps and in this algorithm, haploid means single chromosome/string and diploid means two chromosome/string. Figure 1 shows the working of selective breeding algorithm.
ALGORITHM
| • | Step 1: | Initialize the population |
| Fig. 1: | Flow chart for selective breeding algorithm |
| • | Step 2: | (i) Find the objective function value and breeding factor for each haploid. Breeding factor = 1/objective function value |
| (ii) Sort the population based on breeding factor (or) objective function value | ||
| • | Step 3: | (i) Divide the population into two sets (i.e., first five sequences as one set called dominant set and remaining sequences as another set called recessive set) |
| (ii) Form diploids (set of haploids) for breeding process which contains one dominant and one recessive sequence |
| • | Step 4: | Perform breeding process for all possible combinations of diploid by taking two at a time. Five set of diploid i.e., (1) R1r1 (2) R2r2 (3) R3r3 (4) R4r4 (5) R5r5 |
Consider two set of diploid (R4r4xR5r5). Possible breeds are:
By the same way, following diploid combinations are obtained:
| • | Step 5: | (i) Do fusion process for diploids obtained from breeding process. The possible breeds obtained while considering any two haploids is called one set. For each set, randomly select fusion points. Number of fusion points = length of the given haploid/2. At the fusion points interchange genes between parents |
| (ii) Divide each diploid into two haploids | ||
| • | Step 6: Selective breeding of particular genes runs the risk of losing some of the other genes from the gene pool altogether which is irreversible. This is called in-breeding depression. To avoid this, add 10% of haploid in each iteration. | |
| • | Step 7: Sort the haploids obtained from step 2, 4 and 5 based on breeding factor/objective function value and take first 10 haploids for next iteration | |
| • | Step 8: Go to step 3 and repeat the processes to the required No. of iterations | |
IMPLEMENTATION
The input data, consisting of a list of pieces placed in a two-dimensional array on the host machine. Each row of the array received the pieces that had sizes within a specified interval. These intervals are determined by an analysis of the piece size distribution. The packing loop is performed in parallel by all active processors. The size of each bin piece is broadcast in turn to all processors containing bin pieces. From the set of all processors that can pack the piece, the processor with the maximum self-address is selected to pack it.
| Table 1: | Input pieces (Berkey, 1988) |
By using SBA algorithm 49 bins are required for packing the input pieces given in Table 1. In grid pack algorithm 51 bins are needed to pack the same input pieces. The optimal packing of this piece set required 49 bins.
RESULTS AND DISCUSSION
The algorithm was tested with sets of data of size 100 and 1000. The results presented in Table 2 are the average of 5 runs for a data set of size 1000. It compares the results obtained by the selective breeding algorithm to those obtained by grid pack algorithm (Berkey, 1988) and parallel versions of the traditional next fit and first fit bin packing heuristics. The parallel next fit and parallel first fit algorithms that were used for comparison are adaptations of those presented by Berkey (1989). The input was unsorted, or sorted into non decreasing sequence, the selective breeding algorithm resulted in a packing that was much better than the packing obtained with either parallel next fit or parallel first fit. In the case where the pieces are sorted into nonincreasing order, the packing from selective breeding was still much better than grid pack algorithm, the Parallel Next Fit packing and was well comparable to the Parallel First Fit packing.
Three more algorithms namely genetic algorithm, artificial immune system also tested with same problem instances. Genetic algorithm is a meta-heuristic originally proposed by Holland J. (1975, 1992). Since then it has evolved into a powerful method for solving many hard combinatorial optimization problems a list of which can be found in many references (Gen and Cheng, 2000). Genetic algorithm used 497 bins for packing. Artificial Immune Systems (AIS) represent a field of biologically inspired computing that attempts to exploit theories, principles and concepts of modern immunology to design immune system-based applications in science and engineering (De Castro and Timmis et al., 2002). Artificial immune system packs the item with 505 bins. In sheep flocks heredity model algorithm string structure, hierarchical genetic operations (crossover and mutation) are introduced. They are (1): Sub-chromosome level genetic operation and (2): Chromosome (global) level genetic operation. This hierarchical operation is referred to as "multi-stage genetic operation"(Chandrasekaran et al., 2006). Using sheep flock heredity model algorithm test data is packed with 517 bins. Selective breeding algorithm gives a better solution than other algorithms which are used for the same problems. So selective breeding algorithm is a good problem solving technique for bin packing applications.
| Table 2: | Packing results for set of data size 1000 |
This algorithm may also be extended for other applications namely computer security, travelling salesman problem, scheduling and other functional areas. It is also used for three dimensional bin packing application and other types of packing applications.
CONCLUSION
The study proposes a novel evolutionary algorithm based on selective breeding. This selective breeding algorithm is then applied on bin packing problem in a massively parallel computing environment. Bin packing algorithm can be efficiently implemented in a SIMD processing environment. The use of data partitioning to initialize the packing appears to be a practical method of allocating the packing workload to a set of parallel processors while maintaining the integrity of the packing algorithm. The computational results show that the new SBA algorithm yields an optimal solution for the problems tested. Hence, the proposed new selective breeding algorithm is an effective approach for one dimensional bin packing problems.
NOTATIONS USED
| N | = | No. of haploids |
| R or Dom | = | Dominant haploid |
| r or Rec | = | Recessive haploid |
| t | = | Iteration number |
| SBA | = | Selective breeding algorithm |
| Breed | = | Breeding process |
| SIMD | = | Single instruction multiple data |
| C | = | Bin capacity |
| j | = | Each input piece |
| wj | = | Weight |
| n | = | No. of available bins |