Particle Swarm Optimization on Bin Packing

A step-by-step random-key PSO example, plus a discrete swap-velocity interpretation.

Exam-safe one-liner: PSO is naturally continuous, so for bin packing we either use random keys and decode by sorting + First Fit, or we redefine velocity as a list of swaps/moves that makes the current configuration closer to personal/global best configurations.

Problem Instance

Bin capacity C = 10. Six items:

Item	A	B	C	D	E	F
Weight	4	8	1	4	2	7

Fitness used in this example:

fitness = number_of_bins + 0.01 * slack_balance_penalty

The number of bins dominates. The small slack penalty only breaks ties between 3-bin packings.

Method 1: Random-Key PSO

This is the HW#5-style adaptation. A particle position is a real vector. Sort the keys to get an item order, then decode using First Fit. PSO changes the keys using velocity.

PSO update used here

This example uses the common HW-style global-best PSO:

v_new = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x) x_new = x + v_new

Parameters: w = 0.7, c1 = 1.5, c2 = 1.5, vmax = 0.5.

The full lecture version may also include informants/local-best as a separate term. This example keeps the arithmetic readable using personal best + global best.

Current particle position

The particle currently has these random keys:

Item	A	B	C	D	E	F
Position `x`	0.62	0.15	0.87	0.31	0.44	0.73
Velocity `v`	0.04	-0.02	0.01	0.03	-0.05	0.02

Sorting the keys gives this order:

B, D, E, A, F, C

Bin 1 load 10

B8E2

Bin 2 load 9

D4A4C1

Bin 3 load 7

Current fitness: 3.0467.

Personal best and global best

The particle remembers its own best position, and the swarm has a global best position.

Vector	A	B	C	D	E	F	Decoded order
`pbest`	0.62	0.85	0.31	0.45	0.24	0.12	F, E, C, D, A, B
`gbest`	0.41	0.90	0.33	0.52	0.22	0.10	F, E, C, A, D, B

Both decode to good 3-bin layouts such as:

Bin 1 load 10

F7E2C1

Bin 2 load 8

A4D4

Bin 3 load 8

Best fitness: 3.0267.

Draw random coefficients per dimension

Each item/dimension gets its own random numbers. This is the subtle exploration mechanism: each dimension can be pulled by a different amount.

Item	A	B	C	D	E	F
`r1` for personal pull	0.20	0.60	0.50	0.30	0.70	0.40
`r2` for global pull	0.50	0.30	0.80	0.40	0.20	0.60

If one random number were used for all dimensions, the particle would move along the same direction. Per-dimension randomness lets the velocity tilt sideways, so it explores more.

Compute the new velocity

For each item:

v_new = 0.7*v + 1.5*r1*(pbest - x) + 1.5*r2*(gbest - x)

Item	0.7*v	personal term	global term	raw v_new	after clamp [-0.5, 0.5]
A	0.028	0.000	-0.158	-0.130	-0.130
B	-0.014	0.630	0.338	0.954	0.500
C	0.007	-0.420	-0.648	-1.061	-0.500
D	0.021	0.063	0.126	0.210	0.210
E	-0.035	-0.210	-0.066	-0.311	-0.311
F	0.014	-0.366	-0.567	-0.919	-0.500

Update the position

Add the clamped velocity to the current position:

Item	A	B	C	D	E	F
Old `x`	0.620	0.150	0.870	0.310	0.440	0.730
New `v`	-0.130	0.500	-0.500	0.210	-0.311	-0.500
New `x`	0.491	0.650	0.370	0.520	0.129	0.230

New sorted order:

E, F, C, A, D, B

Decode the new position

Apply First Fit to the new order:

Bin 1 load 10

E2F7C1

Bin 2 load 8

A4D4

Bin 3 load 8

Position	Order	Bin loads	Fitness
Old current	B, D, E, A, F, C	10, 9, 7	3.0467
New current	E, F, C, A, D, B	10, 8, 8	3.0267

The particle improved, so we update this particle's personal best to the new position. If it beats the swarm's global best, we also update global best.

What Would CB and BSF Look Like?

Unlike DE, PSO has no greedy parent-child replacement. The particle can move to a worse current position in the next iteration. Therefore:

Curve	Expected PSO behavior	Why
Current best (CB)	Can oscillate above BSF	Particles keep moving even when their current positions get worse.
Best-so-far (BSF)	Monotone non-increasing	Personal/global best memory stores the best solution ever found.

Exam phrase: PSO preserves good solutions through memory, not through replacement. That is why CB can drift while BSF stays monotone.

Method 2: Discrete PSO With Swap Velocity

This is a native discrete adaptation. It is not ordinary continuous PSO. We redefine velocity as a list of swaps or moves that make the current ordering more similar to personal/global best orderings.

Start from the current order

current = [B, D, E, A, F, C]

Personal/global best suggest that the useful structure is:

best-like order = [F, E, C, A, D, B]

Velocity as pending swaps

A discrete "pull toward best" can be a short swap list:

Swap	Order after swap	Meaning
swap B and F	[F, D, E, A, B, C]	Move F earlier, like best order.
swap D and E	[F, E, D, A, B, C]	Move E earlier, like best order.
swap D and C	[F, E, C, A, B, D]	Move C earlier, like best order.

Applying only some swaps is the discrete version of using a smaller step size.

Decode after swaps

Order after applying the swaps:

F, E, C, A, B, D

Bin 1 load 10

F7E2C1

Bin 2 load 8

A4D4

Bin 3 load 8

This gives the same 3-bin structure. The key point is that "velocity" is no longer a numeric vector; it is a list of structure-changing moves.

Doctor-Style Answer

If asked how PSO can solve bin packing, answer:

"PSO is naturally continuous, so in HW#5 we used random-key encoding. Each particle is a vector of real-valued keys. Sorting the keys gives an item order, then First Fit decodes it into bins. The velocity update changes the keys using inertia, personal-best pull, and global-best pull. The weakness is that the optimizer works in key space, not directly in bin space. A more native discrete PSO would define velocity as a list of swaps or item moves that makes the current packing more similar to personal/global best packings."