2.1. Initialization

In the initialization of PIBSO, a population of units is generated randomly or under a rule. For a combinatorial optimization problem, the n-dimensional search space is denoted by Pⁿ. A state in Pⁿ is denoted by x_i = [x _i1, x _i2, … , x _in]^T ∈ Pⁿ, where i is the sequence number of state. For the kth variable of x_i, x _ik, the search space is P_k ⊂ Pⁿ. A state in P_k is denoted by s _km, and the number of s _km is denoted by Num _k. A unit vector, denoted by u_j = [u _j1, u _j2, … , u _jn]^T, is a x_i, where j is the sequence number of the unit in population. In P_k, each s _km has a probability to be selected as u _jk, and this probability is denoted by p _km. Here, p _km is initialized in [0, 1] randomly or under a rule and is not necessary to satisfy $\sum\nolimits_{m = 1}^{Num_k } {\,p_{km} }$ = 1, and u_j is selected from x_i. Apparently, the globally optimal u_j is the best combination of s _km. The population scale is set to a suited number according to the concrete optimization problem.

2.2. Fitness

The fitness of unit u_i, denoted by fit _i, evaluates the suitability of u_i for the objective of optimization, and u_i, with higher fitness value approaches closer to the global optimum than others with lower fitness values do. The definition of fitness depends on the concrete optimization problem.

2.3. Unit update

Each fit _i is normalized by

(1)$$norfit_i = \displaystyle{{\,fit_i - fit_{\min } } \over {\,fit_{\max } - fit_{\min }}},$$

where fit _max and fit _min are the maximum, and minimum, respectively, among fit _i.

The incremental factor related to u_i is denoted by w _i ∈ (0, 1) and is calculated by

(2)$$w_i =\displaystyle{{dr \times norfit_i } \over n}\comma$$

where dr ∈(0, 1] is the incremental ratio. Then, for the s _km included in u_i, that is, u _jk, its p _km is updated by

(3)$$\,p_{km} \lpar t + 1\rpar =p_{km} \lpar t\rpar \times \lpar 1 + w_i \rpar \comma$$

where t denotes the population generation.

If p _kq (t + 1) > 1 for s _kq, where 1 < q < Num _k, then p _km (t + 1) (m ≠ q) is calculated by

(4)$$\,p_{km} \lpar t + 1\rpar =p_{km} \lpar t\rpar - \lsqb p_{kq} \lpar t + 1\rpar - 1\rsqb$$

and then set as

(5)$$\,p_{kq} \lpar t + 1\rpar = 1.$$

If p _kq (t + 1) < 0 for s _kq, where 1 < q < Num _k, then set

(6)$$\,p_{kq} \lpar t + 1\rpar = 0.$$

When p _km(t) has been updated to p _km (t + 1), each u _ik (t) is updated by selecting a s _km from P_k to be u _ik (t + 1), based on p _km(t + 1) and a selection rule defined by users. Usually roulette wheel selection is adopted. Finally, u _ik(t + 1) forms u _i(t + 1).

2.4. Procedure of PIBSO

The procedure of PIBSO is described by the following:

• Step 1. Initialize a population of u_i and p _km with a suitable scale.

• Step 2. Evaluate the fitness fit _i of each u_i and normalize fit _i by Eq. (1).

• Step 3. For each u_i, find incremental factor w _i by Eq. (2) and update p _km of u _ik by Eqs. (3), (4), (5), and (6).

• Step 4. Update u _ik and form new u_i by selecting s _km based on p _km.

• Step 5. The updated u_i forms new generation.

• Step 6. Go back to Step 2 until the stop criterion is met.

2.5. Population evolution mechanism of PIBSO

In general, evolution of a u_i means the combination of s _km gets better and fit _i increases. Accordingly, each u _ik evolves into a better s _km. The unit update mechanism indicates that a worse u_i with lower fit _i makes p _km of u _ik be increased less than a better u_i with higher fit _i does. Thus, a s _km selected by more better u_i has a higher probability of being selected. It means that the difference of p _km between various s _km (which are selected by bigger amounts of better u_i) and s _km (which are selected by bigger amounts of worse u_i) expands gradually with the increase of generation number. This leads to the situation in which u_i tends to select better s _km and approaches the global optimum. Therefore, Steps 3, 4, and 5 of PIBSO push population to reach convergence. In contrast, p _km is influenced by all u_i, and conversely, p _km affects the quality of u_i. Therefore, u_i interacts each other. In addition, the incremental ratio dr in Eq. (2) determines the value of incremental factor w _i and controls the incremental velocity of p _km.

3.1. Problem statement

The typical sequential pick-and-place machine, shown schematically in Figure 1, consists of a movable placement head, a feeder carrier with slots, feeders, and a board holder. When a PCB has been transferred inside the machine by conveyor, the only movable mechanism, the placement head, moves from the starting point to a feeder to pick up a component. Then, the placement head travels to a prespecified position on the PCB to place the component. Next, the placement head travels to a feeder to pick up another component. This pick-and-place procedure is repeated until the assembly task has been completed. Eventually, when the last component has been placed, the placement head travels back to the starting point. Prior to production, components need to be stored in feeders and feeders need to be loaded on slots. In general, the placement head mounts only one component in a pick-and-place operation and moves directly between a feeder and a placement position. Moreover, a feeder stores only one type of components and a slot loads only one feeder.

Fig. 1. The typical pick-and-place placement machine.

During PCB production, the sequential pick-and-place machine completes two types of work: assigning feeders to slots and placing components onto the board in a sequence. To improve efficiency and cut down cost, the traveling time of the placement head, equivalently, the total length of the placement head traveling paths, need be reduced to the minimum. Consequently, optimization of PCB assembly is essentially a combinatorial optimization problem to find the shortest loop of the placement head.

3.2. Mathematical model

According to Ho and Ji (Reference Ho and Ji2007), the integer program model for PCBAOP on the sequential pick-and-place machine can be formulated as minimize

(7)$$z = \sum\limits_{i = 0}^n {\sum\limits_{\,j = 1\comma j \ne i}^n {\sum\limits_{t = 1}^\mu {\sum\limits_l^\mu {\lpar d_{il} + d_{lj} \rpar \times x_{ij} \times y_{t_j l} } } } } + \sum\limits_{i = 1}^n {d_{i0} \times x_{i0} }\comma$$

subject to

(8)$$\sum\limits_{i = 0}^n {x_{ij} } = 1\comma \quad \forall j= 0\comma \; 1\comma \; \ldots \comma \; n;\ i \ne j$$

(9)$$\sum\limits_{j = 0}^n {x_{ij} } = 1\comma \quad \forall i = 0\comma \; 1\comma \; \ldots \comma \; n;\ i \ne j$$

(10)$$u_i - u_j +n \times x_{ij} \le n - 1\comma \quad \forall i\comma \; j = 1\comma \; 2\comma \; \ldots \comma \; n;\ i \ne j$$

(11)$$\sum\limits_{t = 1}^\mu {y_{tl} = 1} \comma \quad \forall l = 1\comma \; 2\comma \; \ldots \comma \; \mu$$

(12)$$\sum\limits_{l = 1}^\mu {y_{tl} = 1} \comma \quad \forall t = 1\comma \; 2\comma \; \ldots \comma \; \mu$$

where i, j are the components (i, j = 0, 1, … , n); t is the component types (t = 1, 2, … , μ); l are feeders (l = 1, 2, … , μ); d _0l is the distance traveled from starting point to feeder l; d _lj is the distance traveled from feeder l to position of component j on PCB; d _il is the distance traveled from the position of component i to feeder l; d _i0 is the distance traveled from the position of component i to starting point; u _i is the placement order of component i; x _ij = 1 if component i is placed immediately prior to component j and 0 otherwise; and y _{t jl} = 1 if component j with component type t is stored in feeder l and 0 otherwise.

3.3. A PCB assembly example

The PCB assembly example PAT is used here to help understand the definitions and PIBSO application. Suppose in PAT, five components of three types will be mounted and four slots are on the feeder carrier. The distance between placement positions and slots, the distance from the starting point to slots, and the distance from the starting point to placement positions are shown in Table 1.

Table 1. The distances among placement positions, slots, and the starting point in PAT

Note: PAT, a printed circuit board assembly example.

3.4. Definitions

A tour of a placement head is a feasible loop of placement head travel, that is, the placement head travels from the starting point, picks and places all components repeatedly, and eventually returns to the starting point. In a tour, a path from a slot to a placement position is called a placement path, and a path from a placement position to a slot is called a pick path. Apparently, a tour is composed of placement paths, pick paths, and the path from the starting point to a slot as well as the path from a placement position to the starting point.

The placement distance is defined as the distance from a slot to a type of components, which is the sum of distances from the slot to placement positions on which components of the type are placed. For example, for PAT, according to Table 1, the placement distance from slot 1 to components of type 1 is the sum of the distance from slot 1 to position 1 and the distance from slot 1 to position 2, equal to 10. The placement distance matrix (PDM) is defined as the matrix in which each entry is a placement distance. Moreover, the rows correspond to the slots and the columns correspond to the types of components. As an example, the PDM of PAT is depicted as

$$\left[\matrix{10 & 22 & 12 \hfill \cr {\hskip 2pt 9} & 12 & {\hskip 3pt 7} \hfill \cr 11 & {\hskip 2pt 9} & {\hskip 3pt 2} \hfill \cr 17 & 13 & {\hskip 3pt 6} \hfill} \right]$$

The pick distance matrix (PiDM) is defined as the matrix in which the rows and columns correspond to slots and placement positions, respectively, and each entry is a pick distance. The starting point corresponds to the last column, with the assumption that the starting point is a placement position when the placement head starts a travel from it to a feeder to pick a component; meanwhile, it corresponds to the last row, with the assumption that it is a slot when the placement head travels from the placement position of the last mounted component back to it. The distance from the starting point to itself is set to positive infinity. As an example, the PiDM of PAT is depicted as

$$\left[\matrix{{\hskip 2pt 3} & 7 & {\hskip 2pt 6} & 16 & 12 & {\hskip 2pt 1} \hfill \cr {\hskip 2pt 5} & 4 & {\hskip 2pt 3} & {\hskip 2pt 9} & {\hskip 2pt 7} & {\hskip 2pt 2} \hfill \cr {\hskip 2pt 8} & 3 & {\hskip 2pt 5} & {\hskip 2pt 4} & {\hskip 2pt 2} & {\hskip 2pt 3} \hfill \cr 12 & 5 & 10 & {\hskip 2pt 3} & {\hskip 2pt 6} & {\hskip 2pt 4} \hfill \cr {\hskip 2pt 4} & 8 & {\hskip 2pt 7} & 17 & 13 & \infty \hfill} \right]$$

4.1. Initialization of probabilities of substates

If the path from the starting point to a slot and the path from a placement position to the starting point are assumed to be pick paths, a tour includes two parts: length of placement paths and length of pick paths. Each entry in PDM denotes a substate of placement paths. Each entry in PiDM denotes a substate of pick paths. According to Eq. (7), shorter paths are better and should have higher probabilities to be selected. Consequently, the probabilities of two types of substates are initialized as the reciprocals of placement distances and pick distances, respectively. The probability matrix of substates of placement paths is called feeder assignment probability matrix (FAPM). As one example in PAT, it is

$$\left[\matrix{0.100 & 0.045 & 0.083 \hfill \cr 0.111 & 0.083 & 0.143 \hfill \cr 0.091 & 0.111 & 0.500 \hfill \cr 0.059 & 0.077 & 0.167 \hfill} \right]$$

The probability matrix of substates of pick paths is called pick probability matrix (PPM). As one example in PAT, it is

$$\left[\matrix{0.333 & 0.143 & 0.167 & 0.063 & 0.083 & {\hskip 10pt 1} \hfill \cr 0.200 & 0.250 & 0.333 & 0.111 & 0.143 & 0.500 \hfill \cr 0.125 & 0.333 & 0.200 & 0.250 & 0.500 & 0.333 \hfill \cr 0.083 & 0.200 & 0.100 & 0.333 & 0.167 & 0.250 \hfill \cr 0.250 & 0.125 & 0.143 & 0.059 & 0.077 & {\hskip 10pt 0} \hfill} \right]$$

4.2. Unit generation rules

A unit includes two parts: a feeder assignment subunit (FASU) and a pick subunit (PSU). The former determines placement paths and the latter determines pick paths. The generation rules of two subunits are described below.

4.2.1. Generating FASU

The FASU is a vector, in which indexes denote slots and its elements are feeders (component types). In the procedure of generating a FASU, a slot is selected randomly, and then a feeder (component type) is selected for the slot by using roulette wheel selection. This process is repeated until all feeders are loaded. In roulette wheel selection, the roulette wheel consists of probabilities of types of components, that is, the related entries of the row (the row corresponds to the slot) in FAPM. When a feeder is selected by a slot, it will not be put in the roulette wheels for selecting feeders for other slots. In FASU, for the unused slots, the elements are set to zeros.

As one example in PAT, the process of generating a FASU denoted by fasu ₁ is described as follows. Slot 3 is selected, and the roulette wheel consists of 0.091, 0.111, and 0.500. Thus, the feeder of type 1 is selected. Next, slot 2 is selected, and the roulette wheel consists of 0.083 and 0.142. Thus, the feeder of type 3 is selected. At the end, slot 4 is selected, and the feeder of type 2 is assigned to slot 4. Consequently, fasu ₁ is worked out as

$$0 \quad {\rm Type3} \quad {\rm Type1} \quad {\rm Type2}$$

4.2.2. Generating a PSU associated with a FASU

When a FASU has been generated, an associated PSU needs to be generated. The PSU is a vector in which the indexes denote placement positions and the last index denotes the starting point, and its elements are the slots selected in the FASU. In the procedure of generating a PSU, a placement position is selected randomly, and then a slot is selected for the placement position by using roulette wheel selection. This process is repeated until all placement positions are assigned slots. In roulette wheel selection, the roulette wheel consists of probabilities of slots that are the related entries of the column (the column corresponds to the placement position) in PPM.

For PAT, as shown in Table 1, position 1 and 2 are of type 1, position 3 and 4 are of type 2, and position 5 is of type 3. Accordingly, for fasu ₁ in its associated PSU, slot 3 and 4 occur twice and slot 2 occurs once. As an example, the process of generating a PSU associated with fasu ₁, denoted by psu ₁, is described as follows. Position 4 is selected, and the roulette wheel consists of 0.111, 0.250, 0.333, and 0.059. Thus, slot 3 is selected. Next, position 1 is selected, and the roulette wheel consists of 0.200, 0.125, 0.083, and 0.250. Thus, slot 2 is selected. Next, position 2 is selected, and the roulette wheel consists of 0.250, 0.333, 0.200, and 0.125. Thus, slot 4 is selected. Next, position 3 is selected, and the roulette wheel consists of 0.200, 0.100, and 0.143. Thus, slot 3 is selected. Next, position 5 is selected, and the roulette wheel consists of 0.167 and 0.077. Then, the starting point is selected. At the end, slot 4 is assigned to the starting point. Thus psu ₁ is worked out as

$${\rm slot2} \quad {\rm slote4} \quad {\rm slot3} \quad {\rm slot3} \quad {\rm starting point} \quad {\rm slot4}$$

When a FASU and an associated PSU are generated, a unit is formed. For instance, the placement paths and the pick paths of the above generated unit are shown in Figure 2. For a unit, the length of tour is fixed no matter what the component placement sequence is. For example, as shown in Figure 2, the tour starting point → slot4 → position4 → slot3 → position2 → slot4 → position3 → slot3 → position1 → slot2 → position5 → starting point, and the tour starting point → slot4 → position3 → slot3 → position2 → slot4 → position4 → slot3 → position1 → slot2 → position5 → starting point have the same length. The reason is that each placement path and pick path need be passed once in a tour.

Fig. 2. The placement paths (solid lines) and the pick paths (dash lines) of the unit of fasu ₁ and psu ₁. Here, (1), (2), and (3) denote Type 1, 2, and 3 feeders, respectively, and ①, ②, ③, ④, and ⑤ denote Positions 1, 2, 3, 4, and 5, respectively.

4.3. Population update

The fitness is defined as the reciprocal of the length of a tour, that is, 1/z [z from Eq. (7)]. When a slot selects a feeder in FASU or a placement position selects a slot in PSU, the relevant substate probabilities increase in FAPM and PPM. The following example shows how FAPM, PPM, and population update.

For PAT, assume the scale of population is 5; in the first generation, the unit unit ₁ with length of 67 is

$$0 \quad {\rm ty3} \quad {\rm ty1} \quad {\rm ty2}\quad ({\rm \bf FASU})$$

$${\rm S2} \quad {\rm S4} \quad {\rm S3} \quad {\rm S3} \quad {\rm Stp} \quad {\rm S4}\quad ({\rm \bf PSU})$$

The lengths of other four units, unit ₂, unit ₃, unit ₄ and unit ₅, are 70, 56, 71, and 80, respectively. For each unit, the length of tour is normalized by Eq. (1), with fit _max = 80 and fit _min = 56. The results of normalization are

$$\matrix {norfit_1 & norfit_2 & norfit_3 & norfit_4 & norfit_5 \hfill \cr 0.46 & 0.58 & 0 & 0.63 & 1}$$

Set dr to 1, and then the incremental factors of units are

$$\matrix{ w_1 & w_2 & w_3 & w_4 & w_5 \hfill \cr 0.09 & 0.12 & 0 & 0.13 & 0.2}$$

Next, in FAPM and PPM, the entries relevant to each unit are updated. For unit ₁, in FAPM, entries (2, 3), (3, 1), and (4, 2) need to multiply (1 + w ₁) by Eq. (3), and in PPM, entries (1, 2), (2, 4), (3, 3), (4, 3), (5, 5), and (6, 4) need to multiply (1 + w ₁) by Eq. (3). The results are

$$\left[\matrix{0.100 & 0.045 & 0.083 \hfill \cr 0.111 & 0.083 & {\bi 0.156} \hfill \cr {\bi 0.099} & 0.111 & 0.500 \hfill \cr 0.059 & {\bi 0.084} & 0.167 \hfill} \right]$$

and

$$\left[\matrix{0.333 & 0.143 & 0.167 & 0.063 & 0.083 & {\hskip 10pt 1} \hfill \cr {\bi 0.218} & 0.250 & 0.333 & 0.111 & 0.143 & 0.500 \hfill \cr 0.125 & 0.333 & {\bi 0.218} & {\bi 0.273} & 0.500 & 0.333 \hfill \cr 0.083 & {\bi 0.218} & 0.100 & 0.333 & 0.167 & {\bi 0.273} \hfill \cr 0.250 & 0.125 & 0.143 & 0.059 & {\bi 0.084} & {\hskip 10pt 0} \hfill} \right]\comma$$

respectively. In the same way, FAPM and PPM are modified by unit ₂, unit ₃, unit ₄, and unit ₅ in sequence. In the next generation, new units are generated by using the updated FAPM and PPM so that population updates.

4.4. The process of PIBSO for PCBAOP

Set the scale of population to a suitable number. Initialize i = 0. Set the threshold thr to a suited value empirically. The process of PIBSO for PCBAOP is described as follows:

• Step 1. Let i = i + 1, and generate units to form a new generation of population denoted by $g_i $.

• Step 2. Find the average tour length of units, denoted by ave _i. Find the best unit with the shortest tour and denote its length by best _i.

• Step 3. Find incremental factors of all units and use them to modify FAPM and PPM.

• Step 4. If i < 0, go back to Step 1; else go to Step 5.

• Step 5. Let c = i. Find the average of |ave _c – ave _c−1|, |ave _c−1 – ave _c−2|, . . . , |ave _c−18 – ave _c−19|, and denote it by Ata.

• Step 6. If Ata < thr, then end the process and output the minimum among best _i as the near-optimum result; otherwise, return to Step 1.

The condition of convergence is defined as the average of |ave _i – ave _i−1| for the last 20 generationis less than his consideration derives from the following observation. During the process of evolution of units, the difference among units tails off and local optima occur frequently. However, it hardly happens that the population falls into a local optimum and cannot jump out in 20 consecutive generations. Thus, if units have little change for 20 consecutive generations, PIBSO reaches a nearly global optimum solution.