Parallel Genetic Algorithms and the 1D Bin Packing Problem

Introduction to Parallel Computing

The past few decades have witnessed the introduction of a wide range of technological innovations that have had an enormous impact on consumers, businesses, and governmental agencies. Computer-based applications in particular have been key in facilitating the delivery of a wide range of services and information, and computer processing speeds have consistently increased incrementally. Processing speeds, however, have a natural limit: electricity cannot travel faster than the speed of light. Even the optimal processing speeds attainable in the future will remain constrained in this regard. Nevertheless, alternative approaches — including parallel computing and genetic algorithms — can further increase the functionality of computers, and both are discussed in detail below.

In computing, the term "parallelism" is used to describe a system's architecture — in other words, "the organization and interconnection of components of computer systems" (Faulkner, Senker & Velho, 1999, p. 135). Although processing speeds have continued to roughly double every 18 months in accordance with Moore's Law, computers that use sequential architectures are still constrained in several ways in their ability to perform calculation functions. Regardless of how fast a computer operates in sequential architectural configurations, each separate instruction or processing operation must be completed before the next one can begin (Faulkner et al., 1999). Increases in processing speed can help sequential processing function more efficiently, but even here there is a fundamental constraint. As Faulkner and his associates emphasize, "This approach has its barriers, not least the speed of light since electrical signals cannot travel faster than light. Another way to increase the performance of computers is to find an alternative architecture" (Faulkner et al., 1999, p. 135).

In response to the need for faster and more efficient computer processing, a number of devices have been introduced during the past half-century that employ numerous processors operating in parallel to accomplish a single task (Faulkner et al., 1999). According to Faulkner and his associates, "Most of this development has involved the gradual introduction of parallelism into supercomputers. There are six main forms: concurrent input-output operations, pipelining, memory interleaving and hierarchy, parallel functional units, vector processing, and multiple central processors. However, none of these approaches completely abandons the sequential architecture" (1999, p. 136).

Parallel systems are comprised of a number of processors, each of which assumes responsibility for completing discrete portions of a processing job simultaneously. Although attempts to produce truly parallel processing began during the late 1960s, it was not until the 1980s that the approach became commercially viable with the introduction of so-called "field effect chips" (Faulkner et al., 1999). According to MacKenzie, "In field effect chips, current flows only in the surface plane of the microchip; in a bipolar chip, the current flows perpendicular to the chip as well as along it" (1998, p. 106). Based on the ability to mass-produce field effect chips with relative ease, highly integrated field effect technology introduced a number of opportunities for configuring large numbers of these chips in parallel architectures (MacKenzie, 1998). As Faulkner and his colleagues point out, "Although slower than the bipolar chips conventionally used in supercomputers, large numbers of [field effect chips] could be arrayed or configured in highly parallel architectures to achieve competitive processing speeds" (1999, p. 137).

Beginning in the 1980s, parallel architectures became increasingly competitive with so-called supercomputers. MacKenzie notes that, "Until the very end of the 1980s, these did not claim to rival mainstream supercomputing in absolute floating-point performance, promising instead a superior price-performance ratio. However, by the start of the 1990s, with the most advanced field effect chips (such as the million-transistor Intel i860) being claimed to offer on a single chip a floating-point processing performance approaching that of a 1976 Cray I, rivalry in absolute performance was growing" (1998, p. 107).

More recently, parallel computers have begun to compare favorably with supercomputers through the use of incremental parallelism; however, the primary advantage from the start has been the increased price-performance ratio achieved by reducing the costs associated with attaining the fastest processing speeds (Faulkner et al., 1999). Parallel computers differ from sequential processing methods in three basic ways related to their design, as described in Table 1 below.

Table 1: Basic Differences Between Parallel and Sequential Processing (Source: Faulkner et al., 1999, p. 138)

The type and number of processors, or "granularity." The majority of computers currently in use contain identical processors only; however, it is possible to conceive of heterogeneous machines working with different processors. The system may be either "coarse-grain" — composed of a small number of sophisticated processors — or "fine-grain" — employing a large number of simple processors.

The kind of instruction given to the different processors. Parallel-data computers, also known as single instruction stream/multiple data stream (SIMD), have all processors simultaneously executing the same operation on different parts of the data. Parallel-process computers, or multiple instruction stream/multiple data stream (MIMD), are able to divide large programs into many smaller ones that separate processors execute simultaneously.

The way processors are connected to one another and to memory units. In "shared memory" machines, communication between processors is via a common memory accessed through a network of connections or a memory bus, though this approach is hampered by the potential for "traffic jams." "Distributed memory" machines have some amount of memory attached to each processor, forming processor-memory pairs; communication is via a message-passing system. Various geometries have been devised, including the simple rectangular grid used by the distributed array processor (DAP), specialized geometries such as the Butterfly computer and the hypercube (both developed in the United States), and the British-designed transputer, in which connections between processors are "virtual" rather than hardwired.

It is important to note that parallel computing is not a zero-sum alternative to sequential processing. As Benkler emphasizes, "One must break up the problem into well-designed pieces that can run simultaneously, rather than having one processor wait for the other to finish, and there is overhead in managing the information input and output flows to and from the processors, both to each other and to the system memory" (2005, p. 273). The analysis of the performance-price ratio between parallel and sequential processing therefore requires an assessment of the benefits of integrating numerous separate processors against the costs of building these capacities into a single machine (Benkler, 2005). Benkler concludes that, "By the end of the twentieth century, most supercomputers were made of thousands of simple processors lashed together and parallelization became an important field of computer science" (Benkler, 2005, p. 274).

As the term suggests, evolutionary computing is founded on the same principles that Charles Darwin proposed in On the Origin of Species. Pennock notes that, "Computer scientists and engineers, inspired by the workings of evolution in nature, realized that they could apply the same powerful Darwinian mechanism in computers for practical purposes, such as for complex industrial design" (2007, p. 212). In recent years, evolutionary computing techniques have been used to develop algorithms for online decision-making applications (Karr, 2007).

Evolutionary Computing and Genetic Algorithms

Evolutionary computing has been used by the National Aeronautics and Space Administration (NASA) to good effect already by developing evolutionary algorithms that facilitate design and development. A research team at NASA's Ames Research Center, for example, used evolutionary computing techniques to automatically create the design for an antenna for use on a satellite in earth orbit. According to Plotkin, "The space antenna, which looks like an unwound paper clip, violated conventional wisdom about antenna design and confounded the human antenna engineers who first saw it. The NASA antenna was created using 'evolutionary computation' programs, so named because they solve problems in a way that mimics biological evolution, natural selection, and 'the survival of the fittest'" (2009, p. 23). It is important to note, however, that the "automatic" aspects of the design process are based on carefully formulated requirements that software engineers must develop based on the specific requirements of the initiative. In the case of the NASA space antenna, the "fitness criteria" specified that the antenna must be able to transmit and receive signals within certain frequency parameters and satisfy an overall size constraint, but these fitness criteria did not instruct the algorithm as to what types of materials should be used or how they should be configured (Plotkin, 2009).

In line with its Darwinian roots, evolutionary algorithms generate an initial random "population" of design permutations using computer modeling techniques based on specified fitness criteria (Plotkin, 2009). They then perform simulations of various design permutations to evaluate their congruence with the specified fitness criteria and select the one that best accomplishes the task, with the best designs serving as the foundation for subsequent generations (Plotkin, 2009). The biological analogies do not end there: evolutionary algorithms also marry some designs with others to produce hybrid designs that contain the most desirable attributes of their "parents" (Plotkin, 2009).

Furthermore, the evolutionary algorithms create mutations of previous designs through the introduction of different permutations, which are then evaluated against the original fitness criteria. The best designs are once again selected in an iterative process that may involve hundreds or even thousands of generations (Plotkin, 2009). According to Plotkin, "Designs are tested and refined quickly and inexpensively, potentially without ever having to build a single physical model until the final version is created. If all goes well, the result is one or more antennas that satisfy the human-provided fitness criteria to a high degree" (2009, p. 23).

Like evolutionary computing, the term "genetic algorithm" describes a computational method rather than the analysis of genetics, although the method can certainly be applied to that area of investigation. Clark and Mangel note that, "Terms such as genotype and evolution are used in a purely descriptive sense, referring to the computation, not to the underlying biology" (2000, p. 223). The fundamental principles of genetic algorithms can be depicted through the use of pseudo-code as follows:

begin initialize population; evaluate initial population; while not (stop condition) do begin: select organisms; select a genetic operator; generate new population by applying a genetic operator; evaluate newly generated population; end; end.

Although all genetic algorithms will be unique in some fashion, the foregoing structure is a common attribute of all such algorithms (Joh et al., 2001). The various permutations of genetic algorithms depend on what types of application domain issues are involved, including: (1) the specification of a representation scheme of the possible solutions; (2) the specification of the fitness function; (3) the choice of genetic operators; and (4) the choice of stop condition (Joh et al., 2001).

Each algorithmic generation depends on a single genetic operator and a set of human-provided parameters that direct the flow of the algorithm, including: (1) the size of a population; (2) the selection probabilities of genetic operators in each generation; (3) the number of organisms to be selected from a population; and (4) the application probabilities of reproduction and crossover to each selected organism and the mutation probability of each gene of the selected organism (Joh et al., 2001).

Researchers have found that genetic algorithms are especially useful for identifying solutions to optimization problems involving state spaces that exceed the abilities of stochastic dynamic programming approaches (Clark & Mangel, 2000). As an example, Clark and Mangel report that, "If there is a high level of environmental uncertainty and unpredictability such as a pelagic larva might encounter with highly variable oceanic currents, then it is difficult to store all of the environmental states for stochastic dynamic programming" (2000, p. 224). Comparable optimization problems might involve weather predictions that incorporate potentially billions of permutations of a wide range of environmental variables.

In sum, search algorithms based on genetic principles "evolve" over time, continually becoming more efficient in their operation (Sunal, Kerr & Sunal, 2003). As Sunal and his colleagues put it, "[Genetic algorithms] improve over time, working toward optimal solutions. Genetic algorithms learn from experiences, discarding characteristics when they do not facilitate an optimal solution" (2003, p. 72). Likewise, mutations may be introduced into the search algorithm if they appear to provide superior search results, with less efficient algorithms being discarded in an iterative fashion as many times as is necessary to achieve the desired results (Sunal et al., 2003). The use of genetic algorithms has been extended to a wide range of disciplines in recent years, including ecology, population genetics, and social systems, based on their ability to evolve and improve over time as they seek superior solutions and eliminate undesirable features (Joh, Arentze & Timmermans, 2001).

Computational models that draw their inspiration from the natural processes thought to direct evolution have been used to good effect in optimizing complex designs and are termed "evolutionary algorithms." According to Lim, Ong, Jin, Sendhoff, and Lee, "In Genetic Algorithms (GA), a subclass of EA, potential solutions are encoded into a simple chromosome-like data structure, and recombination and mutation operators are repeatedly applied to a population of such potential solutions until a certain termination condition is reached" (2006, p. 37). Genetic algorithms have attracted a great deal of interest from software engineers and researchers based on their ability to identify designs that are near the global optimum; however, thousands or tens of thousands of operations may be required using conventional genetic algorithms to identify near-optimal solutions (Lim et al., 2006).

Despite increases in computer processing speeds, the complexity of applications to which these algorithms have been applied has demanded a more elegant and efficient solution. Lim and his colleagues point out that, "The increasing use of time-consuming high-fidelity analysis codes in science and engineering for studying the effect of altering key design parameters on product performance has further led to even longer and intractable design cycle times" (2006, p. 37). It is possible to achieve superior operations with genetic algorithms by using them in parallel. According to Lim et al., "Fortunately, another well-known strength of genetic algorithms is the ability to partition the population of individuals among multiple computing nodes. Doing so allows sublinear speedups in computation and even super-linear speedups if possible algorithmic speedup is also considered" (2006, p. 37). The speedup of code refers to the extent to which performance gain is achieved by using multiple processors to run code in parallel compared to a single processor (Sadjadi, 2009).

Parallel Genetic Algorithms and the 1D Bin Packing Problem

Inspired by Charles Darwin's original concepts of biological evolution via natural selection, genetic algorithms seek to identify near-global optimal solutions from an initial set of entirely random guesses (Metcalfe & Charbonneau, 2003). Despite being applied to a wide range of industrial, environmental, educational, and commercial applications such as scheduling, the complexity and size of some operations means that tens of thousands or more iterations are required to develop near-global optimal solutions. As Haupt and Haupt (2004) emphasize, "Some optimization problems are so big that they have not been totally solved to date" (p. 200). Likewise, Cantu-Paz (1999) writes, "To solve some problems, genetic algorithms may require hundreds or thousands of function evaluations. Depending on the cost of each evaluation, the GA may take days, months or even years to find an acceptable solution" (p. 1).

Nevertheless, a growing body of research has shown that genetic algorithms can facilitate the search process in ways not otherwise possible without an inordinate amount of computing resources. The "evolutionary" and "biological" aspects of these approaches to optimization are the key to their efficiency. According to Lim and his associates, "Genetic Algorithms are probabilistic meta-heuristic methods inspired by the 'survival of the fittest' principle of neo-Darwinian theory of evolution. Artificial creatures are created and put into competition in a struggle for life and only the survivors are allowed to reproduce" (2006, p. 4). The iterative function of genetic algorithms is described as follows: "A new population will be created using biologically inspired operators such as crossover, mutation, and selection, and the process repeats until some search termination criteria are reached. A genetic algorithm without any structure is usually referred to as a panmictic genetic algorithm" (Lim et al., 2006, p. 4).

Just as genetic algorithms are extensions of evolutionary algorithms, parallel genetic algorithms are further extensions of panmictic genetic algorithms. Lim et al. add that, "The Parallel Genetic Algorithms (PGAs) are extensions of the panmictic GA. The well-known advantage of PGAs is their ability to facilitate speciation, a process by which different subpopulations evolve in diverse directions simultaneously. They have been shown to speed up the search process and to attain higher quality solutions on complex design problems" (2006, p. 4).

Besides parallel panmictic genetic algorithms, there are two other parallel-structured genetic algorithms currently in use — the so-called "island" and "cellular" genetic algorithms. These three fundamental models of parallel genetic algorithms, though similar in concept, differ in important practical ways as described in Table 2 below.

Table 2: Three Types of Parallel Genetic Algorithms (Source: Lim et al., 2006, p. 4)

Master-Slave PGA. In master-slave PGAs, it is assumed that there is only a single panmictic population — a canonical GA. Unlike the canonical GA, however, evaluations of individuals are distributed by scheduling fractions of the population among slave processing nodes. Such a model has the advantage of ease of implementation and does not alter the search behavior of a canonical GA.

Fine-Grained or Cellular PGA. Fine-grained PGA consists of a single spatially structured population. It is designed to run on closely linked massively parallel processing systems consisting of a large number of processing elements connected in a specific high-speed topology. Selection and mating in a fine-grained parallel GA are restricted to small groups; however, groups overlap to permit some interactions among all individuals so that good solutions may disseminate across the entire population. This type is also termed the cellular model PGA.

Multi-Population or Island PGA. Multiple-population PGA is more sophisticated, consisting of several subpopulations that exchange individuals occasionally. This exchange of individuals is called migration and is controlled by several parameters. Since it resembles the "island model" in population genetics — which considers relatively isolated demes — it is often known as the island model PGA.

Hierarchical PGA. The various PGA models may also be hybridized to produce Hierarchical PGA (HPGA) models. For instance, one may form a hierarchical PGA that combines a multi-population PGA at the upper level and a fine-grained PGA or master-slave PGA at the lower level. Essentially, any combination of two or more of the three basic PGA forms constitutes an HPGA.

With respect to the computer architecture needed for efficient use of genetic algorithms, the choice of computational methods involves a cost-benefit analysis concerning computer resources and desired outcomes. Haupt and Haupt (2004) report that, "Which method works best depends on the nature of the problem and the architecture of the parallel machine. The simplest method of building a parallel GA is the master-slave algorithm, which is basically a parallel implementation of a standard GA. One processor is the master and controls communication, sorting, and pairing" (p. 138). This method has some drawbacks, however, since the master must await feedback from slaves, and these algorithms only perform as fast as the slowest node (Haupt & Haupt, 2004). By contrast, Haupt and Haupt note that, "Even when speed and architecture are not primary factors, island algorithms often outperform GAs with a single population" (2004, p. 140). The cellular or fine-grained GA allows individual members of a subpopulation to interact with its neighbors, with the characteristics of the best individual diffusing slowly through the grid, "not allowing a single individual to dominate the population at an early stage" (Haupt & Haupt, 2004, pp. 140–141).

One-dimensional bin packing represents a longstanding problem in computing with a number of practical applications associated with the need to minimize space and/or time, making the use of genetic algorithms particularly useful. By any measure, the bin packing problem is challenging and complex, and a wide range of heuristic solutions have been proposed over the years — all sharing the overarching objective of packing a collection of objects into the minimum number of fixed-size "bins" (Coffman, Garey & Johnson, 1984). The bin packing problem is formalized as follows:

Continuous Bin-Packing (CBP): Given a set of objects I = {1…n}, with sizes s_i ∈ (0, 1], assign each object to a unique bin and minimize the total number of bins used, subject to the constraint that the sum of the sizes of all objects assigned to a bin does not exceed 1.

Discrete Bin-Packing (DBP): Given a set of objects I = {1…n}, with sizes s_i ∈ (0, L], assign each object to a unique bin and minimize the total number of bins used, subject to the constraint that the content of each bin does not exceed L (Chao, Harper & Quong, 1993).

With respect to the formalized CBP outlined above, the constraint that the content in each bin may not exceed the bin's capacity is termed the capacity constraint. For continuous bin-packing operations, each bin's capacity is 1 and all sizes are real numbers in (0, 1); for discrete bin-packing operations, each bin's capacity is L and all sizes are integer numbers in (0, L), with L << n normally (Chao et al., 1993).

The 1D bin packing problem does have some solutions available. The problem can be solved through the use of a specific genetic algorithm known as the "grouping genetic algorithm," or GGA (Falkenauer, 2008). Grouping genetic algorithms can be regarded as a special type of genetic algorithm specifically tailored for resolving grouping problems. According to Williams and Magazine (2007), "The Grouping Genetic Algorithm heuristic searches the space of all partitions of a set of jobs" (p. 19). In his seminal work, Falkenauer (1999) defined a grouping problem as one in which the task involves partitioning a group of objects into a collection of mutually disjoint subsets according to a group of problem-specific constraints that define valid and legal groupings. Falkenauer (1998) also described constraints in prior genetic algorithm implementations used to solve grouping problems — most prominently, the fact that conventional crossover operators functioned with the objects in a group rather than the groups themselves. To overcome this constraint, Falkenauer suggested an innovative encoding approach and operators that could manipulate the groups rather than the individual objects, terming the approach a heuristic grouping genetic algorithm (Williams & Magazine, 2007).

The NP-hard bin packing problem is frequently cited as a canonical example of the 1D bin packing problem. Assuming a finite set of "items" of various "sizes," the problem requires partitioning the entire set into various "bins" such that: (1) the total size of all items in any one bin does not exceed the bin's maximum capacity; and (2) the number of bins used is minimized. Bin packing was initially used in conjunction with a GGA by Falkenauer (1994), who determined that when grouping problems are considered, representations and genetic operators must be clearly defined to permit the promotion of groupings of objects — since these represent the fundamental building blocks of the problem — rather than the position of any one object in isolation. In the years since this seminal work, there have been a number of applications of these concepts to various grouping problems, with differing levels of success, including the equal piles problem, graph coloring, edge coloring, and the exam-timetabling problem (Lewis & Paechter, 2002).